[LLVMbugs] [Bug 547] NEW: linearscan regalloc is n^2 in the number of registers

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.cs.uiuc.edu/bugs/show_bug.cgi?id=547

           Summary: linearscan regalloc is n^2 in the number of registers
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Register Allocator
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: duraid at octopus.com.au


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



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.