<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Mar 27, 2015 at 11:52 AM, Diego Novillo <span dir="ltr"><<a href="mailto:dnovillo@google.com" target="_blank">dnovillo@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I've been trying to get rid of the loop scale limiting problem during<br>
BFI. Initially, this was saturating frequencies to the max side of the<br>
scale, so a double nested loop would get max frequencies in all the<br>
blocks (e.g., llvm/test/CodeGen/X86/lsr-i386.ll). This made the inner<br>
loop no hotter than the outer loop, so block placement would not<br>
bother aligning them.<br>
<br>
In convertFloatingToInteger() we are scaling the BFI frequencies so<br>
they fit an integer. The function tries to choose a scaling factor and<br>
warns about being careful so RA doesn't get confused. It chooses a<br>
scaling factor of 1 / Min, which almost always turns up to be 1.</blockquote><div><br></div><div>This is not necessarily true. If there are any conditional code in a acyclic region, the scale factor will be greater than 1.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> This<br>
was causing me grief in the double nested loop case because the inner<br>
loop had a freq of about 6e20 while the outer blocks had a frequency<br>
of 2e19. With a scaling factor of 1, we were saturating everything to<br>
UINT64_MAX.<br>
<br>
I changed it so it uses a scaling factor that puts the frequencies in<br>
[1, UINT32_MAX], but only if the Max frequency is outside that range.<br>
This is causing two failures in the testsuite, which seem to be caused<br>
by RA spilling differently. I believe that in CodeGen/X86/lsr-i386.ll<br>
we are hoisting into the wrong loop now, but I'm not sure.<br>
<br>
The other failure is in CodeGen/Thumb2/v8_IT_5.ll is different block<br>
placement. Which is a bit odd. The frequencies given by my changes are<br>
certainly different, but the body of the loop is given a<br>
disproportionately larger frequency than the others (much like in the<br>
original case). Though, I think what's going on here is that my<br>
changes are causing the smaller frequencies to be saturated down to 1:<br></blockquote><div><br></div><div>All these problems are related to infinite loops.</div><div><br></div><div>David </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Original:<br>
float-to-int: min = 0.0000004768367035, max = 2047.994141, factor = 16777232.0<br>
<br>
Printing analysis 'Block Frequency Analysis' for function 't':<br>
block-frequency-info: t<br>
- entry: float = 1.0, int = 16777232<br>
- if.then: float = 0.0000009536743164, int = 16<br>
- if.else: float = 0.9999990463, int = 16777216<br>
- if.then15: float = 0.0000009536734069, int = 16<br>
- if.else18: float = 0.9999980927, int = 16777200<br>
- if.then102: float = 0.0000009536734069, int = 16<br>
- cond.true10.i: float = 0.0000004768367035, int = 8<br>
- t.exit: float = 0.0000009536734069, int = 16<br>
- if.then115: float = 0.4999985695, int = 8388592<br>
- if.else145: float = 0.2499992847, int = 4194296<br>
- if.else163: float = 0.2499992847, int = 4194296<br>
- while.body172: float = 2047.994141, int = 34359672832<br>
<br>
<br>
-<br>
if.else173: float = 0.4999985695, int = 8388592<br>
<br>
<br>
<br>
My patch:<br>
float-to-int: min = 0.0000004768367035, max = 9223345648592486401.0,<br>
factor = 0.0000000004656626195<br>
<br>
block-frequency-info: t<br>
- entry: float = 1.0, int = 1<br>
- if.then: float = 0.0000009536743164, int = 1<br>
- if.else: float = 0.9999990463, int = 1<br>
- if.then15: float = 0.0000009536734069, int = 1<br>
- if.else18: float = 0.9999980927, int = 1<br>
- if.then102: float = 0.0000009536734069, int = 1<br>
- cond.true10.i: float = 0.0000004768367035, int = 1<br>
- t.exit: float = 0.0000009536734069, int = 1<br>
- if.then115: float = 0.4999985695, int = 1<br>
- if.else145: float = 0.2499992847, int = 1<br>
- if.else163: float = 0.2499992847, int = 1<br>
- while.body172: float = 9223345648592486401.0, int = 4294967295<br>
- if.else173: float = 0.4999985695, int = 1<br>
<br>
<br>
<br>
The scaling factor is so minuscule that I end up squashing every "low"<br>
frequency to 1. I think I need to smooth this better. In the meantime,<br>
I wanted to pick your brain. Maybe I'm completely off-base in my<br>
analysis.<br>
<br>
<br>
Thanks. Diego.<br>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div></div>