[LLVMdev] LiveVariables/LiveInterval on huge functions

Török Edwin edwintorok at gmail.com
Mon Apr 14 01:39:02 PDT 2008

Evan Cheng wrote:
> On Apr 13, 2008, at 1:28 PM, Török Edwin wrote:
>> Hi,
>> In PR2193 LiveVariables runs out of memory on a 512M limit, after
>> processing 11557 basicblocks.
>> VirtRegInfo has ~180000 entries with ~700 bytes each.
>> If I give it more memory (1.5G) it runs out of memory in LiveInterval.
> Some of the information kept by LiveVariables are somewhat redundant  
> and can be removed. I think there was talk of folding much of its  
> computation into LiveIntervalAnalysis. It's not clear whether that  
> would make a difference without careful analysis.
> It's not clear to me what to do about LiveInterval. It does keep a lot  
> of information but it's all essential.
> I suspect StrongPHIElimination may help the situation somewhat but  
> again I can't guess its impact.

Another question to ask, is why that function became so large in the
first place [X86DAGToDAGISel::SelectCode(llvm::SDOperand)]
We have inline limits, don't we?

>> I don't see any easy solution to reduce memory usage, but should we
>> optimize such a huge function at once?
>> If the function is over some reasonable limit (5k basic-blocks?) we
>> could split it into smaller functions, and avoid
>> these problems.
> But what is the right limit? How do you estimate the limit given  
> different host configuration? 

I think having a limit is better than having none. It will prevent
memory usage to get out of control.
The memory usage of LiveVariables/LiveInterval looks like O(N^2) to me,
if we limit N, the memory usage can differ at most by a constant factor.
Having a function twice the size, won't suddenly require 4x the memory.
Determining a right limit, to fit exactly into a given amount of memory
is hard.
We could gather some statistics on medium and maximum basic-block count
in applications from llvm-test. Then choose a default value, and allow
the user to override via a command-line option.

For example once gcc once gave me a warning, something like: more than
15000 BBs, disabling gcse (IIRC, I can't find the source file that gave
me that warning anymore).
Disabling an optimization entirely doesn't seem the best choice to me, I
think it is better if we split it into smaller functions, and optimize

But maybe the right solution is to avoid generating functions that
large, instead of splitting it afterwards.
> If you can make the decision earlier,  
> than it can default to the local register allocator path which doesn't  
> require LiveIntervalAnalysis.

Yep, the local allocator works.
How much worse is the performance of generated code with the local
allocator vs. the default?

>> I am writing a pass to do this split at llvm IR level. What do you  
>> think?
> This functionality sounds useful, but I am not sure it's the *right*  
> fix. We should definitely try harder to make codegen more scalable.  
> But it's not a trivial problem.

Good point. If we have the size-limiting pass, we could become lazy and
not care of scalability too much. So maybe it is better if I don't write
it ;)

Best regards,

More information about the llvm-dev mailing list