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
Created attachment 379 [details] testcase
Here's what I get by linearizing the analysis of the PHI nodes up front instead of piece-meal. ===-------------------------------------------------------------------------=== ... Pass execution timing report ... ===-------------------------------------------------------------------------=== Total Execution Time: 74.1619 seconds (81.9658 wall clock) ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name --- 36.5917 ( 49.9%) 0.3353 ( 40.1%) 36.9271 ( 49.7%) 40.3710 ( 49.2%) Live Variable Analysis 14.2137 ( 19.3%) 0.1160 ( 13.8%) 14.3297 ( 19.3%) 16.2099 ( 19.7%) Linear Scan Register Allocator 8.5713 ( 11.6%) 0.1059 ( 12.6%) 8.6773 ( 11.7%) 9.4419 ( 11.5%) Live Interval Analysis 6.9700 ( 9.5%) 0.1390 ( 16.6%) 7.1090 ( 9.5%) 8.1781 ( 9.9%) X86 DAG->DAG Instruction Selection 4.1610 ( 5.6%) 0.1051 ( 12.5%) 4.2662 ( 5.7%) 4.6674 ( 5.6%) Eliminate PHI nodes for register allocation 1.2148 ( 1.6%) 0.0110 ( 1.3%) 1.2259 ( 1.6%) 1.3296 ( 1.6%) Module Verifier
Next, we need to fix the Live Variable Analysis time wasting execut-a-ma-tron.
PHI Elimination fixed here: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060925/038149.html
REALLY fixed with this patch: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060925/038173.html
Nice work Bill, verified that this works now. I'll open a new bug to track the livevars compile time issue.