[LLVMdev] fix for loop scale limiting in BFI

[Chandler Carruth]

On Fri, Mar 27, 2015 at 11:52 AM, Diego Novillo <dnovillo at google.com> wrote:

> I changed it so it uses a scaling factor that puts the frequencies in
> [1, UINT32_MAX], but only if the Max frequency is outside that range.
> This is causing two failures in the testsuite, which seem to be caused
> by RA spilling differently. I believe that in CodeGen/X86/lsr-i386.ll
> we are hoisting into the wrong loop now, but I'm not sure.
>
> The other failure is in CodeGen/Thumb2/v8_IT_5.ll is different block
> placement. Which is a bit odd. The frequencies given by my changes are
> certainly different, but the body of the loop is given a
> disproportionately larger frequency than the others (much like in the
> original case).  Though, I think what's going on here is that my
> changes are causing the smaller frequencies to be saturated down to 1:
>
> Original:
> float-to-int: min = 0.0000004768367035, max = 2047.994141, factor =
> 16777232.0
>
> Printing analysis 'Block Frequency Analysis' for function 't':
>   block-frequency-info: t
>    - entry: float = 1.0, int = 16777232
>    - if.then: float = 0.0000009536743164, int = 16
>    - if.else: float = 0.9999990463, int = 16777216
>    - if.then15: float = 0.0000009536734069, int = 16
>    - if.else18: float = 0.9999980927, int = 16777200
>    - if.then102: float = 0.0000009536734069, int = 16
>    - cond.true10.i: float = 0.0000004768367035, int = 8
>    - t.exit: float = 0.0000009536734069, int = 16
>    - if.then115: float = 0.4999985695, int = 8388592
>    - if.else145: float = 0.2499992847, int = 4194296
>    - if.else163: float = 0.2499992847, int = 4194296
>    - while.body172: float = 2047.994141, int = 34359672832
>
>
>                                                            -
> if.else173: float = 0.4999985695, int = 8388592
>
>
>
> My patch:
> float-to-int: min = 0.0000004768367035, max = 9223345648592486401.0,
> factor = 0.0000000004656626195
>
> block-frequency-info: t
>  - entry: float = 1.0, int = 1
>  - if.then: float = 0.0000009536743164, int = 1
>  - if.else: float = 0.9999990463, int = 1
>  - if.then15: float = 0.0000009536734069, int = 1
>  - if.else18: float = 0.9999980927, int = 1
>  - if.then102: float = 0.0000009536734069, int = 1
>  - cond.true10.i: float = 0.0000004768367035, int = 1
>  - t.exit: float = 0.0000009536734069, int = 1
>  - if.then115: float = 0.4999985695, int = 1
>  - if.else145: float = 0.2499992847, int = 1
>  - if.else163: float = 0.2499992847, int = 1
>  - while.body172: float = 9223345648592486401.0, int = 4294967295
>  - if.else173: float = 0.4999985695, int = 1
>
>
>
> The scaling factor is so minuscule that I end up squashing every "low"
> frequency to 1. I think I need to smooth this better. In the meantime,
> I wanted to pick your brain. Maybe I'm completely off-base in my
> analysis.
>

This all makes sense to me.

I think we should do at least one thing and maybe two things:

1) I wonder if there is a reason that we *need* to scale down to a 32-bit
max? Even if we increase the max though, I suspect we'll still see cases
where this doesn't work well. It's interesting that we hit 32-bit limits so
quickly when using synthetic loop estimates.

2) I think we should use a non-linear scale once the range exceeds [1,
MAX]. We were already doing some of this and I think we just need to do
more. I could see either a quadratic or exponential scaling technique
working well... Or one of the interpolation scaling techniques. I think
we'll have to experiment to identify the best one. In particular, I'm
imagining we'll want to play with both quadratic and exponential scales in
both directions: compressing the high frequencies and compressing the low
frequencies. And if neither is good, we may need an interpolation that
compresses both the high and low frequencies.

(Naturally, I'm interested in other ideas for how to handle this as well...)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150327/545bd8e7/attachment.html>