linearscan regalloc is n^2 in the number of registers #919
Description
| Bugzilla Link | 547 |
| Resolution | FIXED |
| Resolved on | Feb 22, 2010 12:47 |
| Version | trunk |
| OS | All |
| Attachments | function-level profile of llc building some ia64 code |
| Reporter | LLVM Bugzilla Contributor |
Extended Description
the simple register allocator is basically evil on ia64 (no really, 1mb of
assembly suddenly becomes 10mb), but it is fast. At first glance, linearscan
appears to be roughly O(n^2) in the number of registers it has to worry about,
and it does become nasty on larger codes. Here are some numbers:
Here are compile times for smg2000.llvm.bc with a release build of llc, all on
the same Itanium machine:
-march=x86: 3.3sec
-march=alpha: 7.3sec
-march=ppc32: 7.6sec
-march=ia64: 16.8sec
something's not right here. ;) register allocation should be easier if you
have tons to play with! :)
attaching a detailed profile of this (for the ia64 case), just in case the
numbers above look suspicious. ;)
speaking of suspicious, has anyone seen this frog?
a8888888a a8888888a
d88888888888b d88888888888b
888P~~~~~~~Y888 888P~~~~~~~Y888
d88^ ^88a88^ ^88b
88P Y888P Y88
88 __ 888 __ 88
88 dd8b 888 d88b 88
88 Y88P 888 Y88P 88
88, ~~ ,888, ~~ ,88
Y88, ,88Y88, ,88P
_Y88b d88P Y88b d88P_
a88p88888888888^ ^88888888888q88a
d8P~ Y888888888~ ~888888888P ~Y8b
d8P ~~~~~~ ~~~~~~ Y8b
d88 88b
88P Y88
88 88
88 .... .... 88
88 :::::: :::::: 88
88 :::::: :::::: 88
88 `::::' `::::' 88
88 **a a** 88
88 ~ab da~ 88
a d88b Y8a a8P d8P
8a__a88888 Ya. .dP 88P
a88888888888a___________=8a_a8=___a88P
88888P ~~*8888888888888888888888888888888P
88~~~ ~Y88888888888888888888888888888888b
d8P 88 ::::: ::::: ::::: 888888888b
d88 8P ::::: ::::: ::::: 88~~~~Y888888b
Y88 d8 ::::: ::::: ::::: 88 ~~~Y888b
~8ba 8P ::::: d88a:a88b ::::: 88 ~Y88
88ba d8 ::::: 8888a8888 ::::: 88 88^
~Y8b___8P ::::: 8888:8888 ::::: 88 aP
~Y8888 ::::: Y88:::88P ::::: 88 a8a
88P ::::: ::::: ::::: 88b____a88a
88 ::::: ::::: ::::: 88888888P
88 ::::: ::::: ::::: 8PY8888