<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">According to Agner’s docs, many CPUs have slower BT than TEST; Haswell has only 0.5 inverse throughput as opposed to 0.25, Atom has 1 instead of 0.5, and Silvermont can’t even dual-issue BT (it locks both ALUs). So while BT does seem have a shorter instruction encoding than TEST for TEST reg, imm32 where imm32 has one bit set, it might not be the best idea to always change TEST reg, 0x1000 to BT reg, 12…</div><div class=""><br class=""></div><div class="">Fiona</div><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 22, 2015, at 1:17 PM, Mehdi Amini <<a href="mailto:mehdi.amini@apple.com" class="">mehdi.amini@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=us-ascii" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div class=""><br class=""><blockquote type="cite" class=""><div class="">Begin forwarded message:</div><br class="Apple-interchange-newline"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, 'Helvetica Neue', Helvetica, sans-serif;" class=""><b class="">Date: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">January 18, 2015 at 10:57:33 PM PST<br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, 'Helvetica Neue', Helvetica, sans-serif;" class=""><b class="">Subject: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class=""><b class="">Re: [LLVMdev] X86TargetLowering::LowerToBT</b><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, 'Helvetica Neue', Helvetica, sans-serif;" class=""><b class="">From: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">Chris Sears <<a href="mailto:chris.sears@gmail.com" class="">chris.sears@gmail.com</a>><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, 'Helvetica Neue', Helvetica, sans-serif;" class=""><b class="">To: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">Mehdi Amini <<a href="mailto:mehdi.amini@apple.com" class="">mehdi.amini@apple.com</a>><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, 'Helvetica Neue', Helvetica, sans-serif;" class=""><b class="">Cc: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">LLVM Developers Mailing List <<a href="mailto:llvmdev@cs.uiuc.edu" class="">llvmdev@cs.uiuc.edu</a>><br class=""></span></div><br class=""><div class=""><div dir="ltr" class="">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" class=""> </span>%rsi, %rdi. Good. But then it compiles IsBitSetA() with shrq/andq, which is is pretty much what Clang had generated as IR.<div class=""><br class=""></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px" class=""><div class="">shrq<span class="" style="white-space:pre"> </span>$25, %rdi</div><div class="">andq<span style="white-space:pre" class=""> </span>$1, %rdi</div></blockquote><div class=""><br class=""></div><div class="">LLVM should be able to replace these two with a single X86_64 instruction: btq reg,25</div><div class="">The generated code is correct in both cases. It just isn't optimized in the immediate operatnd case.</div><div class=""><div class=""><br class=""></div><div class=""><div class="">unsigned long long IsBitSetA(unsigned long long val)</div><div class="">{</div><div class=""> return (val & (1ULL<<25)) != 0ULL;</div><div class="">}</div><div class=""><br class=""></div><div class="">unsigned long long IsBitSetB(unsigned long long val, int index)</div><div class="">{</div><div class=""> return (val & (1ULL<<index)) != 0ULL;</div><div class="">}</div></div><div class=""><br class=""></div></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Sun, Jan 18, 2015 at 10:02 PM, Mehdi Amini <span dir="ltr" class=""><<a href="mailto:mehdi.amini@apple.com" target="_blank" class="">mehdi.amini@apple.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="">Hi,<div class=""><br class=""></div><div class="">Can you provide a reproducible example? I feel especially your first IR sample is incomplete.</div><div class="">If you can also make more explicit how is the generated code wrong?</div><div class=""><br class=""></div><div class="">You can give a C file if you are sure that it is reproducible with the current clang.</div><div class=""><br class=""></div><div class="">Thanks,</div><div class=""><br class=""></div><div class="">Mehdi</div><div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class=""><div class="h5"><div class="">On Jan 18, 2015, at 5:13 PM, Chris Sears <<a href="mailto:chris.sears@gmail.com" target="_blank" class="">chris.sears@gmail.com</a>> wrote:</div><br class=""></div></div><div class=""><div class=""><div class="h5"><div dir="ltr" class="">I'm tracking down an X86 code generation malfeasance regarding BT (bit test) and I have some questions.<div class=""><br class=""></div><div class="">This IR <b class="">matches</b> and then <i class="">X86TargetLowering::LowerToBT </i><b class="">is called:</b></div><div class=""><br class=""></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px" class=""><div class="">%and = and i64 %shl, %val <i class=""> ; (val & (1 << index)) != 0 ; </i>bit test with a <b class="">register</b> index</div></blockquote><div class=""><br class=""></div><div class="">This IR <b class="">does not match</b> and so <i class="">X86TargetLowering::LowerToBT </i><b class="">is not called<i class="">:</i></b></div><div class=""><br class=""></div><div class=""><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px" class="">%and = lshr i64 %val, 25 <i class=""> ; (val & (1 </i><i class=""><< 25)) != 0 ; </i>bit test with an <b class="">immediate</b> index<br class=""></blockquote></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px" class=""><div class=""><div class="">%conv = and i64 %and, 1</div></div></blockquote><div class=""><br class=""></div><div class="">Let's back that up a bit. Clang emits this IR. These expressions start out life in C as <i class="">and with a left shifted masking bit</i>, and are then converted into IR as <i class="">right shifted values anded with a masking bit</i>.</div><div class=""><br class=""></div><div class="">This IR then remains untouched until <i class="">Expand ISel Pseudo-instructions</i> in llc (-O3). At that point, <i class="">LowerToBT</i> is called on the REGISTER version and substitutes in a BT reg,reg instruction:</div><div class=""><br class=""></div><div class=""><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px" class=""><div class=""><div class="">btq<span style="white-space:pre-wrap" class=""> </span>%rsi, %rdi ## <MCInst #312 BT64rr</div></div></blockquote><br class=""></div><div class="">The IMMEDIATE version doesn't match the pattern and so <i class="">LowerToBT</i> is not called.</div><div class=""><br class=""></div><div class=""><b class="">Question</b>: This is during <i class="">pseudo instruction expansion</i>. How could <i class="">LowerToBT'</i>s caller have enough context to match the immediate IR version? In fact, lli isn't calling <i class="">LowerToBT</i> so it isn't matching. But isn't this really a <i class="">peephole optimization</i> issue?</div><div class=""><br class=""></div><div class="">LLVM has a generic peephole optimizer, <i class="">CodeGen/PeepholeOptimizer.cpp </i>which has exactly one subclass in <i class="">NVPTXTargetMachine.cpp.</i></div><div class=""><br class=""></div><div class="">But isn't it better to deal with X86 <i class="">LowerToBT</i> in a <i class="">PeepholeOptimizer</i> subclass where you have a small window of instructions rather than during pseudo instruction expansion where you have really one instruction? <i class="">PeepholeOptimizer </i>doesn't seem to be getting much attention and certainly no attention at the subclass level.</div><div class=""><br class=""></div><div class="">Bluntly, expansion is about expansion. Peephole optimization is the opposite.</div><div class=""><div class=""><div class=""><br class=""></div></div></div><div class=""><b class="">Question</b>: Regardless, why is <i class="">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 class="">.</i></div><div class=""><i class=""><br class=""></i></div><div class="">Another approach using <i class="">LowerToBT</i> would be to match <i class="">lshr reg/imm</i> first and then if the <i class="">following</i> instruction was an <i class="">and reg,1 </i>replace both with a BT<i class="">. </i>It doesn't look like <i class="">LowerToBT</i> as is can do that right now since it is matching the <i class="">and</i> instruction.</div><div class=""><br class=""></div><div class=""><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px" class=""><div class=""><div class="">SDValue X86TargetLowering::LowerToBT(<b class="">SDValue <u class="">And</u></b>, ISD::CondCode CC, SDLoc dl, SelectionDAG &DAG) const { ... }</div></div></blockquote><br class=""></div><div class="">But I think this is better done in a subclass of <i class="">CodeGen/PeepholeOptimizer.cpp.</i></div><div class=""><i class=""><br class=""></i></div><div class="">thanks.</div><div class=""><br class=""></div></div></div></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank" class="">http://llvm.cs.uiuc.edu</a><br class=""><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br class=""></div></blockquote></div><br class=""></div></div></blockquote></div><br class=""><br clear="all" class=""><div class=""><br class=""></div>-- <br class=""><div class="gmail_signature">Ite Ursi</div>
</div>
</div></blockquote></div></div><span id="cid:12495F10-A2F6-4924-9AB8-2AF351416746@apple.com"><tst.c></span><meta http-equiv="Content-Type" content="text/html charset=us-ascii" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><blockquote type="cite" class=""><div class=""></div></blockquote></div><br class=""></div></div></blockquote></div><br class=""></body></html>