[LLVMbugs] [Bug 878] NEW: N^2 (or worse) algorithms in phi elimination and livevars

[bugzilla-daemon at cs.uiuc.edu]

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

           Summary: N^2 (or worse) algorithms in phi elimination and
                    livevars
           Product: libraries
           Version: 1.0
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Common Code Generator Code
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: sabre at nondot.org


On this testcase, identifier  by Duraid, phi elim and live vars take silly amounts of time with a debug 
build:

$ llc interpret.bc -time-passes -f -fast
...
  69.7995 ( 58.3%)   0.4539 ( 54.2%)  70.2535 ( 58.2%)  76.5351 ( 58.5%)  Eliminate PHI nodes for 
register allocation
  26.6705 ( 22.2%)   0.1758 ( 21.0%)  26.8463 ( 22.2%)  29.5193 ( 22.5%)  Live Variable Analysis
   9.8426 (  8.2%)   0.0544 (  6.5%)   9.8970 (  8.2%)  10.5023 (  8.0%)  Linear Scan Register Allocator
   7.1498 (  5.9%)   0.0757 (  9.0%)   7.2256 (  5.9%)   7.7176 (  5.9%)  Live Interval Analysis

The PHI elim time is spent in these loops:

  for (MachineBasicBlock::pred_iterator PI = MBB.pred_begin(),
         E = MBB.pred_end(); PI != E; ++PI)
    for (MachineBasicBlock::succ_iterator SI = (*PI)->succ_begin(),
           E = (*PI)->succ_end(); SI != E; ++SI)
      for (MachineBasicBlock::iterator BBI = (*SI)->begin(), E = (*SI)->end();
           BBI != E && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
        for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
          VRegPHIUseCount[BBI->getOperand(i).getReg()]++;

... which are obvious badness.

-Chris



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.