<div dir="ltr"><div>Do we want to use btq?<br><br></div>On many x64_64 processors, shrq/andq is "hard-coded", but btq will execute in microcode, and will likely be worse performing.<br><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jan 19, 2015 at 1:57 AM, Chris Sears <span dir="ltr"><<a href="mailto:chris.sears@gmail.com" target="_blank">chris.sears@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Sure. Attached is the file but here are the functions. The first uses a fixed bit offset. The second has a indexed bit offset. Compiling with llc -O3, LLVM version 3.7.0svn, it compiles the IR from IsBitSetB() using btq<span style="white-space:pre-wrap"> </span>%rsi, %rdi. Good. But then it compiles IsBitSetA() with shrq/andq, which is is pretty much what Clang had generated as IR.<div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div>shrq<span style="white-space:pre-wrap"> </span>$25, %rdi</div><div>andq<span style="white-space:pre-wrap"> </span>$1, %rdi</div></blockquote><div><br></div><div>LLVM should be able to replace these two with a single X86_64 instruction: btq reg,25</div><div>The generated code is correct in both cases. It just isn't optimized in the immediate operatnd case.</div><div><div><br></div><div><div>unsigned long long IsBitSetA(unsigned long long val)</div><div>{</div><div> return (val & (1ULL<<25)) != 0ULL;</div><div>}</div><div><br></div><div>unsigned long long IsBitSetB(unsigned long long val, int index)</div><div>{</div><div> return (val & (1ULL<<index)) != 0ULL;</div><div>}</div></div><div><br></div></div></div><div class="gmail_extra"><div><div class="h5"><br><div class="gmail_quote">On Sun, Jan 18, 2015 at 10:02 PM, Mehdi Amini <span dir="ltr"><<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Hi,<div><br></div><div>Can you provide a reproducible example? I feel especially your first IR sample is incomplete.</div><div>If you can also make more explicit how is the generated code wrong?</div><div><br></div><div>You can give a C file if you are sure that it is reproducible with the current clang.</div><div><br></div><div>Thanks,</div><div><br></div><div>Mehdi</div><div><br><div><blockquote type="cite"><div><div><div>On Jan 18, 2015, at 5:13 PM, Chris Sears <<a href="mailto:chris.sears@gmail.com" target="_blank">chris.sears@gmail.com</a>> wrote:</div><br></div></div><div><div><div><div dir="ltr">I'm tracking down an X86 code generation malfeasance regarding BT (bit test) and I have some questions.<div><br></div><div>This IR <b>matches</b> and then <i>X86TargetLowering::LowerToBT </i><b>is called:</b></div><div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>%and = and i64 %shl, %val <i> ; (val & (1 << index)) != 0 ; </i>bit test with a <b>register</b> index</div></blockquote><div><br></div><div>This IR <b>does not match</b> and so <i>X86TargetLowering::LowerToBT </i><b>is not called<i>:</i></b></div><div><br></div><div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px">%and = lshr i64 %val, 25 <i> ; (val & (1 </i><i><< 25)) != 0 ; </i>bit test with an <b>immediate</b> index<br></blockquote></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div>%conv = and i64 %and, 1</div></div></blockquote><div><br></div><div>Let's back that up a bit. Clang emits this IR. These expressions start out life in C as <i>and with a left shifted masking bit</i>, and are then converted into IR as <i>right shifted values anded with a masking bit</i>.</div><div><br></div><div>This IR then remains untouched until <i>Expand ISel Pseudo-instructions</i> in llc (-O3). At that point, <i>LowerToBT</i> is called on the REGISTER version and substitutes in a BT reg,reg instruction:</div><div><br></div><div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div>btq<span style="white-space:pre-wrap"> </span>%rsi, %rdi ## <MCInst #312 BT64rr</div></div></blockquote><br></div><div>The IMMEDIATE version doesn't match the pattern and so <i>LowerToBT</i> is not called.</div><div><br></div><div><b>Question</b>: This is during <i>pseudo instruction expansion</i>. How could <i>LowerToBT'</i>s caller have enough context to match the immediate IR version? In fact, lli isn't calling <i>LowerToBT</i> so it isn't matching. But isn't this really a <i>peephole optimization</i> issue?</div><div><br></div><div>LLVM has a generic peephole optimizer, <i>CodeGen/PeepholeOptimizer.cpp </i>which has exactly one subclass in <i>NVPTXTargetMachine.cpp.</i></div><div><br></div><div>But isn't it better to deal with X86 <i>LowerToBT</i> in a <i>PeepholeOptimizer</i> subclass where you have a small window of instructions rather than during pseudo instruction expansion where you have really one instruction? <i>PeepholeOptimizer </i>doesn't seem to be getting much attention and certainly no attention at the subclass level.</div><div><br></div><div>Bluntly, expansion is about expansion. Peephole optimization is the opposite.</div><div><div><div><br></div></div></div><div><b>Question</b>: Regardless, why is <i>LowerToBT</i> not being called for the IMMEDIATE version? I suppose you could look at the preceding instruction in the DAG. That seems a bit hacky<i>.</i></div><div><i><br></i></div><div>Another approach using <i>LowerToBT</i> would be to match <i>lshr reg/imm</i> first and then if the <i>following</i> instruction was an <i>and reg,1 </i>replace both with a BT<i>. </i>It doesn't look like <i>LowerToBT</i> as is can do that right now since it is matching the <i>and</i> instruction.</div><div><br></div><div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div>SDValue X86TargetLowering::LowerToBT(<b>SDValue <u>And</u></b>, ISD::CondCode CC, SDLoc dl, SelectionDAG &DAG) const { ... }</div></div></blockquote><br></div><div>But I think this is better done in a subclass of <i>CodeGen/PeepholeOptimizer.cpp.</i></div><div><i><br></i></div><div>thanks.</div><div><br></div></div></div></div>
_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">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></div></blockquote></div><br></div></div></blockquote></div><br><br clear="all"><div><br></div></div></div><span class="HOEnZb"><font color="#888888">-- <br><div>Ite Ursi</div>
</font></span></div>
<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>