[LLVMbugs] [Bug 11699] New: non-linear algorithm in x86_32 register allocator

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=11699

             Bug #: 11699
           Summary: non-linear algorithm in x86_32 register allocator
           Product: new-bugs
           Version: trunk
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: kcc at google.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


Reproducer (tried on r147487) extracted from a real life program. 
Looks like x86_32 register allocator has some non-linear algorithm which
explodes on large inputs, especially when AddressSanitizer instrumentation is
applied. 
Also, clang dies with SEGV on a huge input (might be a different bug). 

---------------- run this bash script: -----------
#!/bin/bash                                                                     
gen() {                                                                         
  N=$1                                                                          
  echo "#include <ext/hash_map>"                                                
  echo "static  __gnu_cxx::hash_map<int, int> x;"                               
  echo "void foo() {"                                                           
  for((i=0;i<$N; i++)); do                                                      
    echo "x[$i] = $RANDOM;"                                                     
  done                                                                          
  echo "}"                                                                      
}                                                                               

run() {                                                                         
  export TIMEFORMAT="--- %R --- $@"                                             
  time "$@"                                                                     
}                                                                               


for((n=512;n<=8192; n*=2)); do                                                  
  echo $n                                                                       
  gen $n > a.cc                                                                 
  run g++ -m32 -w -c -O2 a.cc                                                   
  run clang++ -m32 -w -c -O2 a.cc                                               
  run clang++ -m32 -w -c -O2 a.cc -faddress-sanitizer                           
  rm -f a.cc                                                                    
done             

---------------- end bash script -----------


512
--- 0.644 --- g++ -m32 -w -c -O2 a.cc
--- 1.297 --- clang++ -m32 -w -c -O2 a.cc
--- 9.358 --- clang++ -m32 -w -c -O2 a.cc -faddress-sanitizer
1024
--- 1.075 --- g++ -m32 -w -c -O2 a.cc
--- 2.871 --- clang++ -m32 -w -c -O2 a.cc
--- 30.950 --- clang++ -m32 -w -c -O2 a.cc -faddress-sanitizer
2048
--- 2.506 --- g++ -m32 -w -c -O2 a.cc
--- 7.724 --- clang++ -m32 -w -c -O2 a.cc
--- 130.324 --- clang++ -m32 -w -c -O2 a.cc -faddress-sanitizer
4096
--- 6.909 --- g++ -m32 -w -c -O2 a.cc
--- 24.520 --- clang++ -m32 -w -c -O2 a.cc
--- 739.267 --- clang++ -m32 -w -c -O2 a.cc -faddress-sanitizer
8192
--- 21.421 --- g++ -m32 -w -c -O2 a.cc
clang: error: unable to execute command: Segmentation fault
clang: error: clang frontend command failed due to signal (use -v to see
invocation)




The profile looks like this (N=2048): 
w/o -faddress-sanitizer:
    8.84% ::RegisterCoalescer::JoinIntervals
    8.24% llvm::LiveInterval::join
    4.80% ::LCSSA::runOnLoop
    4.30% void std::__adjust_heap
    2.79% ComputeUltimateVN

With -faddress-sanitizer:
   35.92% ::RegisterCoalescer::JoinIntervals
   25.48% llvm::LiveInterval::join
   10.03% llvm::LiveInterval::find
    7.74% ComputeUltimateVN
    2.22% llvm::SmallVectorImpl<llvm::VNInfo*>::push_back

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.