<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=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><br class=""></div><div class=""><blockquote type="cite" class=""><div class="">On 21 Apr 2017, at 2:23 PM, Michael Clark <<a href="mailto:michaeljclark@mac.com" class="">michaeljclark@mac.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On 21 Apr 2017, at 12:30 PM, Kaylor, Andrew <<a href="mailto:andrew.kaylor@intel.com" class="">andrew.kaylor@intel.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="WordSection1" style="page: WordSection1; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">I think it’s generally true that whenever branches can reliably be predicted branching is faster than a cmov that involves speculative execution, and I would guess that your assessment regarding looping on input values is probably correct.</span></div></div></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div><div class=""><div class="">Yes it’s based on an assumption that val <= LLONG_MAX i.e. branch predict success, which may not always be the case, but to break branch predict it would require an unpredictable sequence of values <= LLONG_MAX and > LLONG_MAX. I was curious and microbenchmarked it:</div><div class=""><br class=""></div><div class="">- <a href="https://godbolt.org/g/ytgk7l" class="">https://godbolt.org/g/ytgk7l</a></div><div class=""><br class=""></div><div class="">Best of 10 runs on a MacBookPro Ivy Bridge Intel Core i7-3740QM</div><div class=""><br class=""></div><div class="">$ time fcvt-branch</div><div class=""><br class="">real<span class="Apple-tab-span" style="white-space: pre;">   </span>0m0.208s<br class="">user<span class="Apple-tab-span" style="white-space: pre;"> </span>0m0.201s<br class="">sys<span class="Apple-tab-span" style="white-space: pre;">  </span>0m0.002s<br class=""><br class=""></div><div class="">$ time fcvt-cmov<br class=""><br class="">real<span class="Apple-tab-span" style="white-space: pre;">        </span>0m0.241s<br class="">user<span class="Apple-tab-span" style="white-space: pre;"> </span>0m0.235s<br class="">sys<span class="Apple-tab-span" style="white-space: pre;">  </span>0m0.002s<br class=""></div></div><br class=""><blockquote type="cite" 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 class="WordSection1" style="page: WordSection1; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="color: rgb(31, 73, 125); font-family: Calibri, sans-serif; font-size: 11pt;" class=""> </span><span style="color: rgb(31, 73, 125); font-family: Calibri, sans-serif; font-size: 11pt;" class="">I believe the code that actually creates most of the transformation you’re interested in here is in SelectionDAGLegalize::ExpandNode() in LegalizeDAG.cpp.  The X86 backend sets a table entry indicating that FP_TO_UINT should be expanded for these value types, but the actual expansion is in target-independent code.  This is what it looks like in the version I last fetched:</span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class=""> <span class="Apple-converted-space"> </span></span><span style="font-size: 9.5pt; font-family: Consolas; color: blue;" class="">case</span><span style="font-size: 9.5pt; font-family: Consolas;" class=""><span class="Apple-converted-space"> </span>ISD::FP_TO_UINT: {<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    SDValue True, False;<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    EVT VT =  Node->getOperand(0).getValueType();<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    EVT NVT = Node->getValueType(0);<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    APFloat apf(DAG.EVTToAPFloatSemantics(VT),<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">                APInt::getNullValue(VT.getSizeInBits()));<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    APInt x = APInt::getSignBit(NVT.getSizeInBits());<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    (</span><span style="font-size: 9.5pt; font-family: Consolas; color: blue;" class="">void</span><span style="font-size: 9.5pt; font-family: Consolas;" class="">)apf.convertFromAPInt(x,<span class="Apple-converted-space"> </span></span><span style="font-size: 9.5pt; font-family: Consolas; color: blue;" class="">false</span><span style="font-size: 9.5pt; font-family: Consolas;" class="">, APFloat::rmNearestTiesToEven);<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    Tmp1 = DAG.getConstantFP(apf, dl, VT);<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    Tmp2 = DAG.getSetCC(dl, getSetCCResultType(VT),<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">                        Node->getOperand(0),<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">                        Tmp1, ISD::SETLT);<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    True = DAG.getNode(ISD::FP_TO_SINT, dl, NVT, Node->getOperand(0));<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">   <span class="Apple-converted-space"> </span></span><span style="font-size: 9.5pt; font-family: Consolas; color: green;" class="">// TODO: Should any fast-math-flags be set for the FSUB?</span><span style="font-size: 9.5pt; font-family: Consolas;" class=""><o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    False = DAG.getNode(ISD::FP_TO_SINT, dl, NVT,<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">                        DAG.getNode(ISD::FSUB, dl, VT,<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">                                    Node->getOperand(0), Tmp1));<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    False = DAG.getNode(ISD::XOR, dl, NVT, False,<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">                        DAG.getConstant(x, dl, NVT));<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    Tmp1 = DAG.getSelect(dl, NVT, Tmp2, True, False);<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">    Results.push_back(Tmp1);<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">   <span class="Apple-converted-space"> </span></span><span style="font-size: 9.5pt; font-family: Consolas; color: blue;" class="">break</span><span style="font-size: 9.5pt; font-family: Consolas;" class="">;<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9.5pt; font-family: Consolas;" class="">  }</span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">The tricky bit here is that this code is asking for a Select and then something else will decide whether that select should be implemented as a branch or a cmov.</span></div></div></div></blockquote><div class=""><br class=""></div><div class="">Good. I had found ISD::FP_TO_UINT but had not found the target-independent code as I was digging in llvm/lib/Target/X86. I had in fact just started looking at the target-independent code after realising it was likely not target specific. This issue could potentially effect any hard float target with IEEE-754 accrued exceptions and conditional moves as the unconditional FSUB will set INEXACT.</div><div class=""><br class=""></div><div class="">I can see comments in lib/Target/X86//X86ISelLowering.cpp LowerSELECT regarding selection of branch or cmov and wonder if the DAG can be matched there or whether the fix is in target-independent code.</div><div class=""><br class=""></div><div class="">It seems like a SELECT node with any sufficiently large number of child nodes should use a branch instead of a conditional move. I wonder about the cost model for predicate logic  and cmov. Modern branch predictors are actually pretty good so if LLVM X86 is using predication when the cost of a branch is less it could result in a loss of performance. I’m now curious about more general possibility of controlling whether SELECT is lowered to branches or predication using cmov. Can this be controlled? Anecdotally, the RISC-V CPU architects recommend branches over predicate logic as in their case (Rocket) branch mis-predict is only 3 cycles.</div><div class=""><br class=""></div><div class="">BTW - semi off-topic. The RISC-V interpreter I am working on seems to be a pathological test case for the LLVM/Clang optimiser (-O3) compared with GCC (-O3) with LLVM/Clang producing code that runs nearly twice as slow as GCC. I don’t know exactly what I’ve done for this to happen; too many switch statements I suspect. Branchy code versus predication perhaps? Branchiness might also explain GCC’s lead on SciMark Monte Carlo assuming Monte Carlo is branchy. Now I am guessing, although after some googling I see that clang generates x86_64 asm that prefers predication versus branches in gcc. Note this CPU simulator test requires the RISC-V GCC toolchain to be installed.</div><div class=""><br class=""></div><div class="">Here is a step by step for anyone interested in a pathological optimiser test case for Clang:</div><div class=""><br class=""></div><div class="">- <a href="https://github.com/riscv/riscv-gnu-toolchain/" class="">https://github.com/riscv/riscv-gnu-toolchain/</a></div><div class="">- <a href="https://github.com/michaeljclark/riscv-meta/" class="">https://github.com/michaeljclark/riscv-meta/</a></div><div class=""><br class=""></div><div class="">$ git clone <a href="https://github.com/riscv/riscv-gnu-toolchain.git" class="">https://github.com/riscv/riscv-gnu-toolchain.git</a></div><div class="">$ git clone <a href="https://github.com/michaeljclark/riscv-meta.git" class="">https://github.com/michaeljclark/riscv-meta.git</a></div><div class="">$ cd riscv-gnu-toolchain</div><div class="">$ export RISCV=/opt/riscv-gnu-toolchain</div><div class="">$ ./configure --prefix=$RISCV</div><div class="">$ make</div><div class="">$ cd ..</div><div class="">$ cd riscv-meta</div><div class="">$ git submodule update --init --recursive</div><div class="">$ export RISCV=/opt/riscv-gnu-toolchain</div><div class="">$ make -j4 CXX=g++ V=1</div><div class="">$ make test-build</div><div class="">$ time ./build/linux_x86_64/bin/rv-sim build/riscv64-unknown-elf/bin/test-sha512</div></div><div class="">ebdd6f20865ff41e3613b633b93c9b89c15d58fd9d64497f5b22554a7fe33757357cfa622f6fb4f40beadc02d18539ecd79e2da126b662839d296c41acbc2</div><div class=""><br class="">real<span class="Apple-tab-span" style="white-space:pre">  </span>0m28.280s<br class="">user<span class="Apple-tab-span" style="white-space:pre">  </span>0m28.280s<br class="">sys<span class="Apple-tab-span" style="white-space:pre">   </span>0m0.000s<br class=""><br class=""></div><div class=""><div class="">$ make clean</div><div class="">$ make -j4 CXX=clang++-3.9 V=1</div><div class="">$ make test-build</div><div class="">$ time ./build/linux_x86_64/bin/rv-sim build/riscv64-unknown-elf/bin/test-sha512<br class="">ebdd6f20865ff41e3613b633b93c9b89c15d58fd9d64497f5b22554a7fe33757357cfa622f6fb4f40beadc02d18539ecd79e2da126b662839d296c41acbc2<br class=""><br class="">real<span class="Apple-tab-span" style="white-space:pre">    </span>0m52.533s<br class="">user<span class="Apple-tab-span" style="white-space:pre">  </span>0m52.532s<br class="">sys<span class="Apple-tab-span" style="white-space:pre">   </span>0m0.000s<br class=""><br class=""></div><div class="">$ g++ --version<br class="">g++ (Debian 6.3.0-6) 6.3.0 20170205<br class="">Copyright (C) 2016 Free Software Foundation, Inc.<br class="">This is free software; see the source for copying conditions.  There is NO<br class="">warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.<br class=""><br class=""><div class="">$ clang++-3.9 --version</div><div class="">clang version 3.9.0-6 (tags/RELEASE_390/final)<br class="">Target: x86_64-pc-linux-gnu<br class="">Thread model: posix<br class="">InstalledDir: /usr/bin<br class=""><br class=""></div><div class=""><br class=""></div></div><div class="">There is also a RISC-V -> x86_64 JIT engine (x86_64 JIT currently for the RISC-V integer ISAt, hard float coming soon…):</div><div class=""><br class=""></div><div class="">$ time ./build/linux_x86_64/bin/rv-jit build/riscv64-unknown-elf/bin/test-sha512<br class="">ebdd6f20865ff41e3613b633b93c9b89c15d58fd9d64497f5b22554a7fe33757357cfa622f6fb4f40beadc02d18539ecd79e2da126b662839d296c41acbc2<br class=""><br class="">real<span class="Apple-tab-span" style="white-space:pre">   </span>0m0.838s<br class="">user<span class="Apple-tab-span" style="white-space:pre">   </span>0m0.840s<br class="">sys<span class="Apple-tab-span" style="white-space:pre">    </span>0m0.000s<br class=""><br class=""></div><div class=""><br class=""></div><div class="">Clang and GCC produce typical native code that performs the same.</div><div class=""><br class=""></div><div class="">$ clang -O3 src/test/test-sha512.c -o test-sha512<br class="">$ time ./test-sha512 <br class="">ebdd6f20865ff41e3613b633b93c9b89c15d58fd9d64497f5b22554a7fe33757357cfa622f6fb4f40beadc02d18539ecd79e2da126b662839d296c41acbc2<br class=""><br class="">real<span class="Apple-tab-span" style="white-space:pre">       </span>0m0.285s<br class="">user<span class="Apple-tab-span" style="white-space:pre">   </span>0m0.280s<br class="">sys<span class="Apple-tab-span" style="white-space:pre">    </span>0m0.004s<br class=""></div><div class=""><br class=""></div><div class="">$ gcc -O3 src/test/test-sha512.c -o test-sha512 <br class="">$ time ./test-sha512 <br class="">ebdd6f20865ff41e3613b633b93c9b89c15d58fd9d64497f5b22554a7fe33757357cfa622f6fb4f40beadc02d18539ecd79e2da126b662839d296c41acbc2<br class=""><br class="">real<span class="Apple-tab-span" style="white-space:pre">  </span>0m0.285s<br class="">user<span class="Apple-tab-span" style="white-space:pre">   </span>0m0.284s<br class="">sys<span class="Apple-tab-span" style="white-space:pre">    </span>0m0.000s<br class=""><br class=""></div><div class="">Michael.</div></div></div></blockquote></div><br class=""></div></div></div></div></div></body></html>