<div dir="ltr"><div><br></div><div>I happened to have a program that seemed to compile into quite non</div><div>optimal machine code and some spare time, so I decided this was a good</div><div>opportunity to learn more about optimization passes.</div><div><br></div><div>Now I think I figured out what is going on - but I'm stuck and would</div><div>appreciate some help on how to continue. Please check that my</div><div>conclusions are correct and answer my questions towards the end - or</div><div>tell me that I'm asking the wrong questions. Or just what I can do to</div><div>fix the bug.</div><div><br></div><div><br></div><div>Given this simple program:</div><div><br></div><div>// ---8<---------- [interesting.c]</div><div>unsigned char dst[DEFINEME] __attribute__((aligned (64)));</div><div>unsigned char src[DEFINEME] __attribute__((aligned (64)));</div><div><br></div><div>void copy_7bits(void)</div><div>{</div><div><span class="gmail-Apple-tab-span" style="white-space:pre">      </span>for (int i = 0; i < DEFINEME; i++)</div><div><span class="gmail-Apple-tab-span" style="white-space:pre">          </span>dst[i] = src[i] & 0x7f;</div><div>}</div><div>// ---8<----------------------------------</div><div><br></div><div>compiled with:</div><div><br></div><div>clang -march=haswell -O3 -S -o - interesting.c -DDEFINEME=160</div><div><br></div><div>it generates some interesting stuff which basically amounts to:</div><div><br></div><div>  vmovaps .LCPI0_0(%rip), %ymm0   # ymm0 = [127,....,127]</div><div>  vandps  src(%rip), %ymm0, %ymm1</div><div>  vandps  src+32(%rip), %ymm0, %ymm2</div><div>  vandps  src+64(%rip), %ymm0, %ymm3</div><div>  vandps  src+96(%rip), %ymm0, %ymm0</div><div>  vmovaps %ymm1, dst(%rip)</div><div>  vmovaps %ymm2, dst+32(%rip)</div><div>  vmovaps %ymm3, dst+64(%rip)</div><div>  vmovaps %ymm0, dst+96(%rip)</div><div><br></div><div>This looks ok, and when -DDEFINEME=128 this is the actual result. But</div><div>now I compiled with -DDEFINEME=160 so there is another 32 bytes to be</div><div>processed. What it looks like is like this:</div><div><br></div><div>  movb    src+128(%rip), %al</div><div>  andb    $127, %al</div><div>  movb    %al, dst+128(%rip)</div><div>  movb    src+129(%rip), %al</div><div>  andb    $127, %al</div><div>  movb    %al, dst+129(%rip)</div><div>  ....</div><div>  ....  Guess I don't need to show 87 more instructions</div><div>  ....  here to get my point accross</div><div>  ....</div><div>  movb    src+158(%rip), %al</div><div>  andb    $127, %al</div><div>  movb    %al, dst+158(%rip)</div><div>  movb    src+159(%rip), %al</div><div>  andb    $127, %al</div><div>  movb    %al, dst+159(%rip)</div><div><br></div><div><br></div><div><br></div><div>From what I can tell the loop vectorizer comes to the conclusion that</div><div>it is a good idea to interleave the loop 4 times. As the loop has a</div><div>trip count of 160, which is 5 trips after vectorization it leaves a</div><div>remainder of 32 trips which does not get vectorized.</div><div><br></div><div>Then this remainder then gets unrolled in a later unrolling pass.</div><div><br></div><div><br></div><div>* Question on interleaving</div><div><br></div><div>TinyTripCountInterleaveThreshold what is the reasoning behind this</div><div>128? This measures in number of trips before vectorization? Shouldn't</div><div>this be number of trips after vectorization, as that is the trip count</div><div>that is relevant after vectorization?</div><div><br></div><div>E.g:</div><div><br></div><div>--- a/lib/Transforms/Vectorize/LoopVectorize.cpp</div><div>+++ b/lib/Transforms/Vectorize/LoopVectorize.cpp</div><div>@@ -6382,7 +6382,7 @@ unsigned LoopVectorizationCostModel::selectInterleaveCount(bool OptForSize,</div><div> </div><div>   // Do not interleave loops with a relatively small trip count.</div><div>   unsigned TC = PSE.getSE()->getSmallConstantTripCount(TheLoop);</div><div>-  if (TC > 1 && TC < TinyTripCountInterleaveThreshold)</div><div>+  if (TC > 1 && (TC / VF) < TinyTripCountInterleaveThreshold)</div><div>     return 1;</div><div> </div><div>   unsigned TargetNumRegisters = TTI.getNumberOfRegisters(VF > 1);</div><div>---</div><div><br></div><div>This patch makes my the generated code for the example with</div><div>DEFINEME=160 look good and fully vectorized and unrolled.</div><div><br></div><div>However it obviously doesn't help for cases like DEFINEME=4128 where</div><div>it generates a vectorized loop with an interleaving of 4 which will</div><div>cover the 4096 first iterations, and then leaves the remaining 32 as</div><div>bytes scalars.</div><div><br></div><div><br></div><div>* Question on how to fix it?</div><div><br></div><div>Where should the remainder be vectorized? Is the loop vectorizer</div><div>supposed to leave the tail unvectorized even if it has a known trip</div><div>count? Does it leave it there in hope that slp or bb vectorizer will</div><div>pick it up after it has been unrolled?</div><div><br></div><div>I did a experiment and removed the 'Hints.setAlreadyVectorized' call</div><div>on the remainder loop (= the original loop) and added an extra</div><div>instance of the loop vectorizer just before the unroll pass. That does</div><div>nicely vectorize the remainder loop. (but it redundantly loads the</div><div>mask again from memory into the register it already has it in - but I</div><div>guess that would be cleaned up by some other pass)</div><div><br></div><div><br></div><div>* Question on fishy codegen on memcpy</div><div><br></div><div>By removing the '& 0x7f' part - i.e making it a memcpy I get even more</div><div>surprising effects in codegen. (I need to compile with -fno-builtin</div><div>for this, as the loop idiom finder nicely detects it as a memcpy</div><div>otherwise. (Here could be a question 3b - what are the exact semantics</div><div>of -fno-builtin. I would expect -fno-builtin to mean don't mess with</div><div>my "memcpy" - don't add or remove any memcpy calls. But I would also</div><div>expect it to still recognize the loop as a memcpy, as long as the</div><div>llvm.memcpy intrinsic not is lowered to a call to library memcpy.))</div><div><br></div><div>(again with a original tripcount of 160).</div><div><br></div><div>Now this is generated for the tail:</div><div><br></div><div>        movzwl  src+144(%rip), %eax</div><div>        movw    %ax, dst+144(%rip)</div><div>        movl    src+146(%rip), %eax</div><div>        movl    %eax, dst+146(%rip)</div><div>        movzwl  src+150(%rip), %eax</div><div>        movw    %ax, dst+150(%rip)</div><div>        movzwl  src+152(%rip), %eax</div><div>        movw    %ax, dst+152(%rip)</div><div>        movzwl  src+154(%rip), %eax</div><div>        movw    %ax, dst+154(%rip)</div><div>        movzwl  src+156(%rip), %eax</div><div>        movw    %ax, dst+156(%rip)</div><div>        movb    src+158(%rip), %al</div><div>        movb    %al, dst+158(%rip)</div><div>        movb    src+159(%rip), %al</div><div>        movb    %al, dst+159(%rip)</div><div><br></div><div>so the backend combines the movb's. But in a very strange way. It</div><div>starts with a 16bit move, than a 32bitmov, which after then becomes</div><div>unaligned, and the two final ones are not combined.</div><div><br></div><div><br></div><div><br></div><div>thanks for reading all the way here.</div><div><br></div></div>