<div dir="ltr"><div><div>Hi Matthias,<br><br></div>I've been fixing similar problems recently (eg, <a href="https://llvm.org/bugs/show_bug.cgi?id=28476" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=28476</a> ). I think your example (the test in zext-or-icmp.ll) is another missed application of DeMorgan's Law:<br><br>char foo(char a, char b) {<br> return (((a & 1) == 0) | (b == 0));<br>}<br><br>char goo(char a, char b) {<br> return !(((a & 1) != 0) & (b != 0));<br>}<br><br></div>Make sure I didn't botch that translation: the 1st is the C equivalent of zext-or-icmp.ll, and the 2nd is what we really want it to be optimized to instead of what's shown in that test case.<br><br>define i8 @foo(i8 %a, i8 %b) {<br> %and = and i8 %a, 1<br> %cmp = icmp eq i8 %b, 0<br> %xor = xor i8 %and, 1<br> %zext = zext i1 %cmp to i8<br> %or = or i8 %zext, %xor<br> ret i8 %or<br>}<br><br>define i8 @goo(i8 %a, i8 %b) {<br> %cmp = icmp ne i8 %b, 0<br> %zext = zext i1 %cmp to i8<br> %and = and i8 %zext, %a<br> %xor = xor i8 %and, 1<br> ret i8 %xor<br>}<br><br><div>The 2nd function is the better IR (one less logic op), so you need to add a transform to produce that and get rid of the existing limitation. Any InstCombine folds that rely on bypassing an earlier fold are wrong IMO.<br><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 21, 2016 at 6:07 AM, Matthias Reisinger via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all,<br>
<br>
I have a question regarding a transformation that is carried out in InstCombine, which has been introduced by r48715. It unfolds expressions of the form `zext(or(icmp, (icmp)))` to `or(zext(icmp), zext(icmp)))` to expose pairs of `zext(icmp)`. In a subsequent iteration these `zext(icmp)` pairs could then (possibly) be optimized by another optimization (which has already been there before r48715), to replace them by bitwise or integer operations. The code in question is located in `visitZExt()` in InstCombineCasts.cpp:<br>
<br>
```<br>
if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src))<br>
return transformZExtICmp(ICI, CI);<br>
<br>
BinaryOperator *SrcI = dyn_cast<BinaryOperator>(Src);<br>
if (SrcI && SrcI->getOpcode() == Instruction::Or) {<br>
// zext (or icmp, icmp) --> or (zext icmp), (zext icmp) if at least one<br>
// of the (zext icmp) will be transformed.<br>
ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0));<br>
ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1));<br>
if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() &&<br>
(transformZExtICmp(LHS, CI, false) ||<br>
transformZExtICmp(RHS, CI, false))) {<br>
Value *LCast = Builder->CreateZExt(LHS, CI.getType(), LHS->getName());<br>
Value *RCast = Builder->CreateZExt(RHS, CI.getType(), RHS->getName());<br>
return BinaryOperator::Create(Instruction::Or, LCast, RCast);<br>
}<br>
}<br>
```<br>
<br>
The first two lines do the actual `zext(icmp)` optimization. The remaining lines have been added by r48715 and do the mentioned unfolding. However, in `foldCastedBitwiseLogic()` there happens a reverse of the above unfolding, which transforms `logic(cast(A), cast(B))` to `cast(logic(A, B))`:<br>
<br>
```<br>
if ((!isa<ICmpInst>(Cast0Src) || !isa<ICmpInst>(Cast1Src)) &&<br>
shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {<br>
Value *NewOp = Builder->CreateBinOp(LogicOpc, Cast0Src, Cast1Src,<br>
I.getName());<br>
return CastInst::Create(CastOpcode, NewOp, DestTy);<br>
}<br>
```<br>
<br>
The `(!isa<ICmpInst>(Cast0Src) || !isa<ICmpInst>(Cast1Src))` part has been added by r48715 in order to ensure that InstCombine does not enter an endless loop, switching back and forth between the two transformations. There was also added an InstCombine test case `zext-or-icmp.ll` that would enter such an endless loop, if this check would not be present. However, it also generally permits `foldCastedBitwiseLogic()` from folding operations with two icmps as operands. Something like<br>
<br>
```<br>
%1 = icmp sgt i64 %a, %b<br>
%2 = zext i1 %1 to i8<br>
%3 = icmp slt i64 %a, %c<br>
%4 = zext i1 %3 to i8<br>
%5 = and i8 %2, %4<br>
```<br>
<br>
would not be able to be transformed, even though the contained `zext icmp` pairs will also not be able to be optimized by `transformZExtICmp()` above, and the casts will survive. Therefore, in r275989 (<a href="https://reviews.llvm.org/D22511" rel="noreferrer" target="_blank">https://reviews.llvm.org/D22511</a>) I tried to narrow the check in `foldCastedBitwiseLogic()` to allow the folding of casts in the presence of icmps. For the above example this would result in:<br>
<br>
```<br>
%1 = icmp sgt i64 %a, %b<br>
%2 = icmp slt i64 %a, %c<br>
%3 = and i1 %1, %2<br>
%4 = zext i1 %3 to i8<br>
```<br>
<br>
Despite `zext-or-icmp.ll` did not enter an endless loop with my change, it later turned out the assumptions that I took in r275989 were too optimistic and endless loops might still occur, which has been pointed out by Benjamin Kramer in <a href="http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160718/374347.html" rel="noreferrer" target="_blank">http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160718/374347.html</a> and it has therefore been reverted.<br>
<br>
I apologize in advance for this possibly naive question, but I was wondering whether it is feasible to remove the unfolding introduced by r48715 in order to enable a cast-folding like on the example above. I've also already tested this and run all of LLVM's test cases via the `make check` target and it seems that the only test case relies on this unfolding is the mentioned `zext-or-icmp.ll`. I don't know if Evan Chang is still responsible for this code region, but since he is the original author of the commit, I thought it would be safe to include him here (I hope it's the right email address).<br>
<br>
Thank you in advance for your thoughts on this!<br>
<br>
Best regards,<br>
Matthias<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div><br></div>