quadratic build time due to llvm::SpillPlacement::addLinks

[ramosian-glider]

Originally reported on Google Code with ID 69

large protobufs (http://code.google.com/p/protobuf/) cause very slow compile time 
with clang -O2 -faddress-sanitizer. 

Repro: 
#!/bin/bash                                                                       



cat <<EOF
message Person {
  required string name = 1;
  required int32 id = 2;        // Unique ID number for this person.
  optional string email = 3;
EOF

for((i=4;i<$1; i++)); do
  echo "  optional string s$i = $i;"
done

cat << EOF
}
EOF


for size in 250 500 1000; do ./zzz.sh $size > zzz.proto ; ./src/protoc --cpp_out=z
zzz.proto ; clang -E -O2 z/*.cc -Iz -Isrc -o $size.cc; time clang -c -O2 $size.cc -faddress-sanitizer;
 done 
TIME: real: 16.805; user: 16.630; system: 0.130
TIME: real: 65.340; user: 64.760; system: 0.400
TIME: real: 294.377; user: 292.620; system: 1.020

Profile: 
    41.17% llvm::SpillPlacement::addLinks(llvm::ArrayRef<unsigned int>)
     3.49% llvm::LiveInterval::extendIntervalEndTo(llvm::LiveRange*, llvm::SlotIndex)

Reported by konstantin.s.serebryany on 2012-04-25 13:53:57

---

- _Attachment: [1000.cc.bz2](https://storage.googleapis.com/google-code-attachments/address-sanitizer/issue-69/comment-0/1000.cc.bz2)_

[ramosian-glider]

Issue 68 has been merged into this issue.

Reported by konstantin.s.serebryany on 2012-04-25 13:56:05

[ramosian-glider]

LLVM r157174  noticeably improved the speed here.

Reported by konstantin.s.serebryany on 2012-05-21 07:15:50

[ramosian-glider]

The time is still quadratic, but better than before: 

125: 6 sec
250: 16 sec
500: 50 sec
1000: 170 sec
2000: 723 sec

Reported by konstantin.s.serebryany on 2012-05-21 08:59:01

[ramosian-glider]

This one can now be closed. 
A related problem is tracked as issue 61

Reported by konstantin.s.serebryany on 2012-05-22 08:19:50

• Status changed: Fixed

[ramosian-glider]

Adding Project:AddressSanitizer as part of GitHub migration.

Reported by ramosian.glider on 2015-07-30 09:12:59

• Labels added: ProjectAddressSanitizer