Greedy Register Allocator taking a loooong time on module with many cleanups

[Quuxplusone]

Bugzilla Link	PR11811
Status	NEW
Importance	P enhancement
Reported by	Duncan Sands (baldrick@free.fr)
Reported on	2012-01-20 08:08:15 -0800
Last modified on	2012-01-24 12:11:21 -0800
Version	trunk
Hardware	PC Linux
CC	llvm-bugs@lists.llvm.org, rafael@espindo.la, stoklund@2pi.dk
Fixed by commit(s)
Attachments	cleanup1.C (36935 bytes, text/x-c++src) cleanup1.ll.gz (397600 bytes, application/x-gzip)
Blocks
Blocked by
See also

Created attachment 7912
Original C++ testcase

This is the gcc testcase cleanup1.C (attached).  At -O1 gcc takes less than 4
seconds to compile it, while dragonegg takes 20 minutes or so.  Almost all of
the time is spent in codegen, and almost all of that is in register allocation,
namely Global Splitting.  To reproduce, run llc on the attached gzipped .ll
file.

$ llc cleanup1.ll -time-passes
...
===-------------------------------------------------------------------------===
                              Register Allocation
===-------------------------------------------------------------------------===
  Total Execution Time: 919.5335 seconds (920.2625 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  908.0848 ( 98.8%)   0.2160 ( 93.1%)  908.3008 ( 98.8%)  908.9710 ( 98.8%)  Global Splitting
  10.9647 (  1.2%)   0.0160 (  6.9%)  10.9807 (  1.2%)  11.0408 (  1.2%)  Evict
   0.1200 (  0.0%)   0.0000 (  0.0%)   0.1200 (  0.0%)   0.1249 (  0.0%)  Spiller
...
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 929.9901 seconds (930.7424 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  919.4535 ( 98.9%)   0.2320 ( 56.9%)  919.6855 ( 98.9%)  920.4247 ( 98.9%)  Greedy Register Allocator
   2.8242 (  0.3%)   0.0000 (  0.0%)   2.8242 (  0.3%)   2.8260 (  0.3%)  Simple Register Coalescing

[Quuxplusone]

Attached cleanup1.C (36935 bytes, text/x-c++src): Original C++ testcase

[Quuxplusone]

Attached cleanup1.ll.gz (397600 bytes, application/x-gzip): gzipped .ll testcase

[Quuxplusone]

Thanks, Duncan. opt -view-cfg seems to be causing similar problems in GraphViz ;-)

[Quuxplusone]

Would you like me to create a smaller version of the testcase?

[Quuxplusone]

No, I can do that myself from the attached file.