Bugzilla – Bug 547
linearscan regalloc is n^2 in the number of registers
Last modified: 2005-10-29 01:57:11
You need to log in before you can comment on or make changes to this bug.
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
Created an attachment (id=223) [details] function-level profile of llc building some ia64 code
Times today for SMG2000 x86: 3.606s alpha: 5.691s ipf: 5.887s ppc: 6.482s