Skip to content
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.

Sign up for GitHub

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

Jump to bottom

N^2 (or worse) algorithms in phi elimination and livevars #1250

Closed
lattner opened this issue Aug 12, 2006 · 7 comments
Closed

N^2 (or worse) algorithms in phi elimination and livevars #1250

lattner opened this issue Aug 12, 2006 · 7 comments
Assignees
@isanbard
Labels
bugzilla Issues migrated from bugzilla llvm:codegen slow-compile

Comments

@lattner
Copy link
Collaborator

lattner commented Aug 12, 2006

Bugzilla Link 878
Resolution FIXED
Resolved on Feb 22, 2010 12:46
Version 1.0
OS All
Attachments testcase

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
@lattner
Copy link
Collaborator Author

lattner commented Aug 12, 2006

assigned to @isanbard

@isanbard
Copy link
Contributor

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

@isanbard
Copy link
Contributor

Next, we need to fix the Live Variable Analysis time wasting execut-a-ma-tron.

@isanbard
Copy link
Contributor

PHI Elimination fixed here:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060925/038149.html

@isanbard
Copy link
Contributor

REALLY fixed with this patch:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060925/038173.html

@lattner
Copy link
Collaborator Author

lattner commented Sep 28, 2006

Nice work Bill, verified that this works now. I'll open a new bug to track the livevars compile time issue.

@lattner
Copy link
Collaborator Author

lattner commented Nov 27, 2021

mentioned in issue llvm/llvm-bugzilla-archive#929

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 3, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@isanbard isanbard

Labels
bugzilla Issues migrated from bugzilla llvm:codegen slow-compile
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@isanbard @lattner