[LLVMdev] Live Intervals vs. Live Variables

Roman Levenstein romixlev at yahoo.com
Wed Apr 4 00:35:53 PDT 2007

--- Evan Cheng <evan.cheng at apple.com> wrote:
> I do want to comment on the "conservative" nature of  
> LiveIntervalAnalysis. I think the comment is misleading and is  
> probably just a relic of early implementation. The biggest problem  
> with the current implementation is the overly aggressive copy  
> coalescer. Right now the register allocator cannot split live ranges.
> So if the coalescer has formed a long live interval it will causes  
> lots of interferences (and thus lots of spills).
> I would encourage those who are interested in implementing new  
> register allocators for LLVM to think about this issue. I do not  
> believe it's possible to build a noticeably "better" allocator if it 
> is relying on the existing live interval information.

You are right. Therefore, for my implementation of Wimmer's linear scan
algorithm I have rewritten the LiveIntervalAnalysis pass and
LiveInterval class. Basically, it does not do coalescing during the
LiveIntervalAnalysis stage. Instead I use register hints as indication
that two registers can be probably coalesced, or better said - can be
assigned to the same physical register. This avoids building long live
coalesced intervals that have a lot of interferences. It also speeds up
the analysis. BTW, I also do not use live interval weights computed by
the LiveIntervalAnalysis, though I might cosidering using them again
for better determination of registers to be split or spilled. 


It's here! Your new message!  
Get new email alerts with the free Yahoo! Toolbar.

More information about the llvm-dev mailing list