LiveVariables/LiveInterval on huge functions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

LiveVariables/LiveInterval on huge functions

Török Edwin
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.

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.

I am writing a pass to do this split at llvm IR level. What do you think?

--Edwin
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

Evan Cheng-2

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.

>
>
> 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? If you can make the decision earlier,  
than it can default to the local register allocator path which doesn't  
require LiveIntervalAnalysis.


>
>
> 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.

Evan


>
>
> --Edwin
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

Török Edwin
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
those.

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,
--Edwin




_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

Török Edwin
Török Edwin wrote:

> 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?

most of functions called by SelectCode get a -30000 cost reduction
because they are internal.
Even if Caller.size() is 40000, the penalty is only 2000, thus we still
have negative costs.

Removing the /20 factor from here improves the situation a lot, however
I think there is  a reason for /20, and it can't be just removed:
InlineCost += Caller->size()/20;


Best regards,
--Edwin


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

dag-7
In reply to this post by Török Edwin
On Monday 14 April 2008 03:39, Török Edwin wrote:

> 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?

Some functions are just big.  Consider production versions of the WRF code
from spec 2006.  It is machine-generated and can be HUGE!


> >> 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 ;)

Another option is regioned compilation.  Generally, I think degrading
optimization (using a local allocator rather than a global one) is hackish.
Regioning does degrade optimization due to visibility limits, but it doesn't
require special-casing which flavors of optimization are run based on code
size.

I would very much like to see some kind of regioning make its way into llvm
at some point.  I'd do it myself if I had free cycles, which I don't.  :(

                                                         -Dave

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

Chris Lattner
In reply to this post by Török Edwin
On Mon, 14 Apr 2008, [ISO-8859-1] Török Edwin wrote:

>> 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?
>
> most of functions called by SelectCode get a -30000 cost reduction
> because they are internal.
> Even if Caller.size() is 40000, the penalty is only 2000, thus we still
> have negative costs.
>
> Removing the /20 factor from here improves the situation a lot, however
> I think there is  a reason for /20, and it can't be just removed:
> InlineCost += Caller->size()/20;
This sounds like unanticipated fallout from Evan's recent tweaks of the
inliner.  Evan, thoughts?

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

Evan Cheng-2

On Apr 14, 2008, at 10:43 AM, Chris Lattner wrote:

> On Mon, 14 Apr 2008, [ISO-8859-1] Török Edwin wrote:
>>> 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?
>>
>> most of functions called by SelectCode get a -30000 cost reduction
>> because they are internal.
>> Even if Caller.size() is 40000, the penalty is only 2000, thus we  
>> still
>> have negative costs.
>>
>> Removing the /20 factor from here improves the situation a lot,  
>> however
>> I think there is  a reason for /20, and it can't be just removed:
>> InlineCost += Caller->size()/20;
>
> This sounds like unanticipated fallout from Evan's recent tweaks of  
> the inliner.  Evan, thoughts?

Previously the inliner assign each basic block cost of 20. So this  
line is simply estimating the number of caller basic blocks. My tweak  
simply removed the number of basic blocks from the equation so the  
cost of a callee is simply number of instructions * 5. I don't think  
it should / would impact this case. Edwin, can you revert 49061 and  
48725 to see if they have any impact?

The -30000 cost reduction for internal function does seem excessive  
though.

Evan

>
>
> -Chris
>
> --
> http://nondot.org/sabre/
> http://llvm.org/


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

Chris Lattner
On Mon, 14 Apr 2008, Evan Cheng wrote:

>>  This sounds like unanticipated fallout from Evan's recent tweaks of the
>>  inliner.  Evan, thoughts?
>
> Previously the inliner assign each basic block cost of 20. So this line is
> simply estimating the number of caller basic blocks. My tweak simply removed
> the number of basic blocks from the equation so the cost of a callee is
> simply number of instructions * 5. I don't think it should / would impact
> this case. Edwin, can you revert 49061 and 48725 to see if they have any
> impact?
>
> The -30000 cost reduction for internal function does seem excessive though.

Right, so now the cost estimate of the function is much lower than it was
before.  This isn't itself a problem, but it means that the 30000 bonus
for being called at one callsite should also be reduced to match, seem
reasonable?

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

Evan Cheng-2
Sure, it makes sense. I'll take a look at it.

Evan

On Apr 14, 2008, at 3:09 PM, Chris Lattner wrote:

> On Mon, 14 Apr 2008, Evan Cheng wrote:
>>> This sounds like unanticipated fallout from Evan's recent tweaks  
>>> of the  inliner.  Evan, thoughts?
>>
>> Previously the inliner assign each basic block cost of 20. So this  
>> line is simply estimating the number of caller basic blocks. My  
>> tweak simply removed the number of basic blocks from the equation  
>> so the cost of a callee is simply number of instructions * 5. I  
>> don't think it should / would impact this case. Edwin, can you  
>> revert 49061 and 48725 to see if they have any impact?
>>
>> The -30000 cost reduction for internal function does seem excessive  
>> though.
>
> Right, so now the cost estimate of the function is much lower than  
> it was before.  This isn't itself a problem, but it means that the  
> 30000 bonus for being called at one callsite should also be reduced  
> to match, seem reasonable?
>
> -Chris
>
> --
> http://nondot.org/sabre/
> http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

Török Edwin
In reply to this post by Evan Cheng-2
Evan Cheng wrote:

> On Apr 14, 2008, at 10:43 AM, Chris Lattner wrote:
>
>  
>> On Mon, 14 Apr 2008, [ISO-8859-1] Török Edwin wrote:
>>    
>>>> 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?
>>>>        
>>> most of functions called by SelectCode get a -30000 cost reduction
>>> because they are internal.
>>> Even if Caller.size() is 40000, the penalty is only 2000, thus we  
>>> still
>>> have negative costs.
>>>
>>> Removing the /20 factor from here improves the situation a lot,  
>>> however
>>> I think there is  a reason for /20, and it can't be just removed:
>>> InlineCost += Caller->size()/20;
>>>      
>> This sounds like unanticipated fallout from Evan's recent tweaks of  
>> the inliner.  Evan, thoughts?
>>    
>
> Previously the inliner assign each basic block cost of 20. So this  
> line is simply estimating the number of caller basic blocks. My tweak  
> simply removed the number of basic blocks from the equation so the  
> cost of a callee is simply number of instructions * 5. I don't think  
> it should / would impact this case. Edwin, can you revert 49061 and  
> 48725 to see if they have any impact?
>  

Reverting 49061 does have an impact. I can compile the testcase withing
1.1G of memory, and memory usage was rising slowly (except for a quick
500M->1G jump).
The patch couldn't be reverted cleanly, I had to manually revert parts
of it.

Best regards,
--Edwin


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: LiveVariables/LiveInterval on huge functions

Evan Cheng-2

On Apr 14, 2008, at 11:16 PM, Török Edwin wrote:

> Evan Cheng wrote:
>> On Apr 14, 2008, at 10:43 AM, Chris Lattner wrote:
>>
>>
>>> On Mon, 14 Apr 2008, [ISO-8859-1] Török Edwin wrote:
>>>
>>>>> 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?
>>>>>
>>>> most of functions called by SelectCode get a -30000 cost reduction
>>>> because they are internal.
>>>> Even if Caller.size() is 40000, the penalty is only 2000, thus we
>>>> still
>>>> have negative costs.
>>>>
>>>> Removing the /20 factor from here improves the situation a lot,
>>>> however
>>>> I think there is  a reason for /20, and it can't be just removed:
>>>> InlineCost += Caller->size()/20;
>>>>
>>> This sounds like unanticipated fallout from Evan's recent tweaks of
>>> the inliner.  Evan, thoughts?
>>>
>>
>> Previously the inliner assign each basic block cost of 20. So this
>> line is simply estimating the number of caller basic blocks. My tweak
>> simply removed the number of basic blocks from the equation so the
>> cost of a callee is simply number of instructions * 5. I don't think
>> it should / would impact this case. Edwin, can you revert 49061 and
>> 48725 to see if they have any impact?
>>
>
> Reverting 49061 does have an impact. I can compile the testcase  
> withing
> 1.1G of memory, and memory usage was rising slowly (except for a quick
> 500M->1G jump).

Thanks.

>
> The patch couldn't be reverted cleanly, I had to manually revert parts
> of it.

I don't actually want to revert the patch. I'll tweak the heuristics  
though.

Evan

>
>
> Best regards,
> --Edwin
>
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev