[LLVMbugs] [Bug 11302] New: quadratic compile time in SUnit::ComputeHeight and SUnit::setHeightDirty

[bugzilla-daemon at llvm.org]

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

             Bug #: 11302
           Summary: quadratic compile time in SUnit::ComputeHeight and
                    SUnit::setHeightDirty
           Product: new-bugs
           Version: trunk
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: kcc at google.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


The attached test cases have N calls of the following kind: 
   bar(16981, 6504, "11844");

compiling a test with 2*N such calls takes 4x more time than compiling N calls. 
I am using r143407

% for n in 8 16 32 64; do echo n=${n}000; time ./my_clang++ -c -O2
manycalls$n.cc ; done
n=8000
TIME: real: 2.432; user: 2.300; system: 0.060
n=16000
TIME: real: 11.824; user: 11.570; system: 0.120
n=32000
TIME: real: 59.008; user: 58.650; system: 0.230
n=64000
TIME: real: 151.948; user: 150.950; system: 0.670

Profile looks like this:
   45.11%             llvm::SUnit::ComputeHeight()
   34.51%             llvm::SUnit::setHeightDirty()
    1.52%             llvm::MachineInstr::addRegisterDead(unsigned int,
llvm::TargetRegisterInfo const*, bool)
    0.75%             llvm::SelectionDAG::AssignTopologicalOrder()

gcc is much faster and does not look quadratic

% for n in 8 16 32 64; do echo n=${n}000; time g++ -c -O2 manycalls$n.cc ; done
n=8000
TIME: real: 1.682; user: 1.620; system: 0.060
n=16000
TIME: real: 3.618; user: 3.550; system: 0.060
n=32000
TIME: real: 7.685; user: 7.410; system: 0.250
n=64000
TIME: real: 16.265; user: 15.810; system: 0.380

-- 
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.