[LLVMbugs] [Bug 929] livevars takes 50% of codegen time (N^2 algorithm?)

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=929

isanbard at gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED



------- Additional Comments From isanbard at gmail.com  2006-10-03 02:21 -------
Fixed:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20061002/038239.html
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20061002/038238.html

Before:

$ llvm.obj/Debug/bin/llc interpret.bc -time-passes -f -fast
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 81.9564 seconds (150.8072 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  37.2380 ( 46.0%)   0.4395 ( 40.1%)  37.6775 ( 45.9%)  78.9992 ( 52.3%)  Live Variable Analysis
   7.1519 (  8.8%)   0.2003 ( 18.3%)   7.3523 (  8.9%)  20.3752 ( 13.5%)  X86 DAG->DAG Instruction 
Selection
   9.9280 ( 12.2%)   0.2185 ( 19.9%)  10.1466 ( 12.3%)  18.4788 ( 12.2%)  Eliminate PHI nodes for 
register allocation

After:

llvm.obj/Debug/bin/llc interpret.bc -time-passes -f -fast
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 46.5941 seconds (78.4110 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  14.2680 ( 31.1%)   0.1674 ( 19.7%)  14.4354 ( 30.9%)  23.9314 ( 30.5%)  Linear Scan Register Allocator
  10.0606 ( 21.9%)   0.2507 ( 29.5%)  10.3114 ( 22.1%)  17.3218 ( 22.0%)  Eliminate PHI nodes for 
register allocation
   9.8416 ( 21.5%)   0.1711 ( 20.1%)  10.0128 ( 21.4%)  16.7627 ( 21.3%)  Live Interval Analysis




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