-
Notifications
You must be signed in to change notification settings - Fork 12.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
N^2 (or worse) algorithms in phi elimination and livevars #1250
Comments
assigned to @isanbard |
Here's what I get by linearizing the analysis of the PHI nodes up front instead of piece-meal. ===-------------------------------------------------------------------------=== ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name --- |
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. |
mentioned in issue llvm/llvm-bugzilla-archive#929 |
Extended Description
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
The text was updated successfully, but these errors were encountered: