llvm dev - Jun 2013 - [LLVMdev] BlockFrequency spill weights

[Splitting this out from the original thread to reduce noise in it]


On 17.06.2013, at 18:43, Jakob Stoklund Olesen <stoklund at 2pi.dk> wrote:
> 
> On Jun 17, 2013, at 7:03 AM, Benjamin Kramer <benny.kra at gmail.com>
wrote:
> 
>> 
>> On 17.06.2013, at 15:56, Diego Novillo <dnovillo at google.com>
wrote:
>> 
>>> On 2013-06-15 16:39 , Benjamin Kramer wrote:
>>>> Do you want to take over this effort or should I poke more at
it?
>>> 
>>> Since you've already started, it's easier if you poke more
at it. Thanks.  I've got a whole bunch of other things to go through.
>> 
>> OK, will do.
>> 
>> 
>> Jakob any comments on the patch? The only interesting part is in
LiveIntervals::getSpillWeight. Do we have to scale the values somehow there?
> 
> Yes, BlockFrequency::getFrequency() is poorly named, it returns a fixpoint
number. I think you should scale it to be relative to the entry block frequency.
> 
> +LiveIntervals::getSpillWeight(bool isDef, bool isUse, BlockFrequency freq)
{
> +  return (isDef + isUse) * freq.getFrequency();
> }
> 
> This computation can overflow.
Yep, I went down the easy route and converted it to floating point arithmetic.
Is that OK here?
> 
> @@ -178,9 +180,10 @@ bool
SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
> 
>   // Compute total ingoing and outgoing block frequencies for all bundles.
>   BlockFrequency.resize(mf.getNumBlockIDs());
> +  MachineBlockFrequencyInfo &MBFI =
getAnalysis<MachineBlockFrequencyInfo>();
>   for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I)
{
> -    float Freq = LiveIntervals::getSpillWeight(true, false,
> -                                               loops->getLoopDepth(I));
> +    float Freq > +        LiveIntervals::getSpillWeight(true, false,
MBFI.getBlockFreq(I));
>     unsigned Num = I->getNumber();
>     BlockFrequency[Num] = Freq;
> 
> I think you should leave LiveIntervals out of this and just the block
frequency directly, scaled as above. The getSpillWeight() function is just used
here to get the non-overflowing frequency approximation.
Fixed.
> 
> Otherwise, looks good.
The attached patch also fixes the regression tests that failed. Mostly minor
changes in register allocation. The SPARC one is a bit scary because an
instruction now gets moved across inline assembly into a delay slot. Do you know
if that is a safe transformation?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: block-frequency-spilling.patch
Type: application/octet-stream
Size: 25635 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130617/351386be/attachment.obj>
-------------- next part --------------


- Ben

On Jun 17, 2013, at 10:48 AM, Benjamin Kramer <benny.kra at gmail.com>
wrote:
> [Splitting this out from the original thread to reduce noise in it]
> 
> 
> On 17.06.2013, at 18:43, Jakob Stoklund Olesen <stoklund at 2pi.dk>
wrote:
>> +LiveIntervals::getSpillWeight(bool isDef, bool isUse, BlockFrequency
freq) {
>> +  return (isDef + isUse) * freq.getFrequency();
>> }
>> 
>> This computation can overflow.
> 
> Yep, I went down the easy route and converted it to floating point
arithmetic. Is that OK here?
Yes, that should be fine.

+LiveIntervals::getSpillWeight(bool isDef, bool isUse, BlockFrequency freq) {
+  float EntryFreq = BlockFrequency::getEntryFrequency();
+  return (isDef + isUse) * (freq.getFrequency() / EntryFreq);

Nitpick: The float division can be constant folded and turned into a
multiplication:

  const float Scale = 1.0f / getEntryFrequency();
  return (isDef + isUse) * (freq.getFrequency() * Scale);

I wouldn’t trust the compiler to do that without -fast-math.
> The attached patch also fixes the regression tests that failed. Mostly
minor changes in register allocation. The SPARC one is a bit scary because an
instruction now gets moved across inline assembly into a delay slot. Do you know
if that is a safe transformation?
That sounds OK. As long as it is safe to move that instruction across the inline
asm.
> <block-frequency-spilling.patch>
LGTM

Thanks,
/jakob

On Mon, Jun 17, 2013 at 11:03 AM, Jakob Stoklund Olesen <stoklund at
2pi.dk>wrote:
> >> This computation can overflow.
> >
> > Yep, I went down the easy route and converted it to floating point
> arithmetic. Is that OK here?
>
> Yes, that should be fine.

I really don't think this is fine. I would like for LLVM to not rely on
floating point arithmetic on the host.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130617/686d2702/attachment.html>