[InstCombine] Refactor optimization of zext(or(icmp, icmp)) to enable more aggressive cast-folding

[mreisinger]

Summary

InstCombine unfolds expressions of the form zext(or(icmp, icmp)) to or(zext(icmp), zext(icmp)) such that in a later iteration of InstCombine the exposed zext(icmp) instructions can be optimized. We now combine this unfolding and the subsequent zext(icmp) optimization to be performed together. Since the unfolding doesn't happen separately anymore, we also again enable the folding of logic(cast(icmp), cast(icmp)) expressions to cast(logic(icmp, icmp)) which had been disabled due to its interference with the unfolding transformation.

Tested via make check and lnt.

Background

For a better understanding on how it came to this change we subsequently summarize its history. In commit r275989 we've already tried to enable the folding of logic(cast(icmp), cast(icmp)) to cast(logic(icmp, icmp)) which had to be reverted in r276106 because it could lead to an endless loop in InstCombine (also see http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160718/374347.html). The root of this problem is that in visitZExt() in InstCombineCasts.cpp there also exists a reverse of the above folding transformation, that unfolds zext(or(icmp, icmp)) to or(zext(icmp), zext(icmp)) in order to expose zext(icmp) operations which would then possibly be eliminated by subsequent iterations of InstCombine. However, before these zext(icmp) would be eliminated the folding from r275989 could kick in and cause InstCombine to endlessly switch back and forth between the folding and the unfolding transformation. This is the reason why we now combine the zext-unfolding and the elimination of the exposed zext(icmp) to happen at one go because this enables us to still allow the cast-folding in logic(cast(icmp), cast(icmp)) without entering an endless loop again.

Details on the submitted changes

• In visitZExt() we combine the unfolding and optimization of zext instructions.
• In transformZExtICmp() we have to use Builder->CreateIntCast() instead of CastInst::CreateIntegerCast() to make sure that the new CastInst is inserted in a BasicBlock. The new calls to transformZExtICmp() that we introduce in visitZExt() would otherwise cause according assertions to be triggered (in our case this happend, for example, with lnt for the MultiSource/Applications/sqlite3 and SingleSource/Regression/C++/EH/recursive-throw tests). The subsequent usage of replaceInstUsesWith() is necessary to ensure that the new CastInst replaces the ZExtInst accordingly.
• In InstCombineAndOrXor.cpp we again allow the folding of casts on icmp instructions.
• The instruction order in the optimized IR for the zext-or-icmp.ll test case is different with the introduced changes.
• The test cases in zext.ll have been adopted from the reverted commits r275989 and r276105.

[spatel]

I was out of the office last week, so now I'm just catching up. cc'ing @majnemer and @eli.friedman for their expertise.

[mreisinger]

Hi Sanjay, thank you for jumping in and for adding subscribers!

Best,
Matthias

[majnemer]

LGTM

[mreisinger]

Cool, thank you for reviewing! Since I don't have commit privileges, somebody else may have to merge this. Should I therefore rebase and reupload the patch?

[mreisinger]

I now rebased the patch (I thereby also replaced my introduced cast<>s by dyn_cast<>s which is cleaner now, sorry for this post-acceptance change). I also reran make check and lnt now and the tests pass - all but the MultiSource/Benchmarks/MiBench/consumer-typeset/consumer-typeset.execution_time in lnt, but this seems to be independent from my changes since it also fails when testing with a clean llvm build that doesn't include my patch (I ran lnt via myvirtualenv/bin/lnt runtest nt --sandbox /tmp --cc ~/opt/llvm_release+asserts/bin/clang --test-suite ~/repos/llvm-test-suite). I don't know if that's a known issue, but at least I could not find an according bugzilla entry - I'll try to further investigate this.

Best,
Matthias

[grosser]

Committed in https://llvm.org/svn/llvm-project/llvm/trunk@277635

[mreisinger]

Thank you for committing!

Best,
Matthias

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) {
   auto CastOpcode = Cast0->getOpcode();
   if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy())
     return nullptr;
 
   Value *Cast0Src = Cast0->getOperand(0);
   Value *Cast1Src = Cast1->getOperand(0);
 
   // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
-  if ((!isa<ICmpInst>(Cast0Src) || !isa<ICmpInst>(Cast1Src)) &&
-      shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
+  if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
     Value *NewOp = Builder->CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
                                         I.getName());
     return CastInst::Create(CastOpcode, NewOp, DestTy);
   }
 
   // For now, only 'and'/'or' have optimizations after this.
   if (LogicOpc == Instruction::Xor)
     return nullptr;

lib/Transforms/InstCombine/InstCombineCasts.cpp

if ((Op1CV == 0 || Op1CV.isPowerOf2()) &&
 
         if ((Op1CV != 0) == isNE) { // Toggle the low bit.
           Constant *One = ConstantInt::get(In->getType(), 1);
           In = Builder->CreateXor(In, One);
         }
 
         if (CI.getType() == In->getType())
           return replaceInstUsesWith(CI, In);
-        return CastInst::CreateIntegerCast(In, CI.getType(), false/*ZExt*/);
+
+        Value *IntCast = Builder->CreateIntCast(In, CI.getType(), false);
+        return replaceInstUsesWith(CI, IntCast);
       }
     }
   }
 
   // icmp ne A, B is equal to xor A, B when A and B only really have one bit.
   // It is also profitable to transform icmp eq into not(xor(A, B)) because that
   // may lead to additional simplifications.
   if (ICI->isEquality() && CI.getType() == ICI->getOperand(0)->getType()) {
if (TruncInst *CSrc = dyn_cast<TruncInst>(Src)) {   // A->B->C cast
     }
   }
 
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src))
     return transformZExtICmp(ICI, CI);
 
   BinaryOperator *SrcI = dyn_cast<BinaryOperator>(Src);
   if (SrcI && SrcI->getOpcode() == Instruction::Or) {
-    // zext (or icmp, icmp) --> or (zext icmp), (zext icmp) if at least one
-    // of the (zext icmp) will be transformed.
+    // zext (or icmp, icmp) -> or (zext icmp), (zext icmp) if at least one
+    // of the (zext icmp) can be eliminated. If so, immediately perform the
+    // according elimination.
     ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0));
     ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1));
     if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() &&
         (transformZExtICmp(LHS, CI, false) ||
          transformZExtICmp(RHS, CI, false))) {
-      Value *LCast = Builder->CreateZExt(LHS, CI.getType(), LHS->getName());
-      Value *RCast = Builder->CreateZExt(RHS, CI.getType(), RHS->getName());
-      return BinaryOperator::Create(Instruction::Or, LCast, RCast);
+      // zext (or icmp, icmp) -> or (zext icmp), (zext icmp)
+      auto *LCast = cast<ZExtInst>(
+          Builder->CreateZExt(LHS, CI.getType(), LHS->getName()));
+      auto *RCast = cast<ZExtInst>(
+          Builder->CreateZExt(RHS, CI.getType(), RHS->getName()));
+      BinaryOperator *Or =
+          BinaryOperator::Create(Instruction::Or, LCast, RCast);
+
+      // Perform the elimination.
+      transformZExtICmp(LHS, *LCast);
+      transformZExtICmp(RHS, *LCast);
+
+      return Or;
     }
   }
 
   // zext(trunc(X) & C) -> (X & zext(C)).
   Constant *C;
   Value *X;
   if (SrcI &&
       match(SrcI, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Constant(C)))) &&

test/Transforms/InstCombine/zext-or-icmp.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; Remove an icmp by using its operand in the subsequent logic directly.
 
 define i8 @zext_or_icmp_icmp(i8 %a, i8 %b) {
   %mask = and i8 %a, 1
   %toBool1 = icmp eq i8 %mask, 0
   %toBool2 = icmp eq i8 %b, 0
   %bothCond = or i1 %toBool1, %toBool2
   %zext = zext i1 %bothCond to i8
   ret i8 %zext
 
 ; CHECK-LABEL: zext_or_icmp_icmp(
 ; CHECK-NEXT:    %mask = and i8 %a, 1
 ; CHECK-NEXT:    %toBool2 = icmp eq i8 %b, 0
-; CHECK-NEXT:    %1 = xor i8 %mask, 1
 ; CHECK-NEXT:    %toBool22 = zext i1 %toBool2 to i8
+; CHECK-NEXT:    %1 = xor i8 %mask, 1
 ; CHECK-NEXT:    %zext = or i8 %1, %toBool22
 ; CHECK-NEXT:    ret i8 %zext
 }
 

test/Transforms/InstCombine/zext.ll

 ; CHECK-NEXT:    ret <2 x i64> [[ZEXT2]]
 ;
   %zext1 = zext <2 x i1> %a to <2 x i32>
   %xor = xor <2 x i32> %zext1, <i32 1, i32 1>
   %zext2 = zext <2 x i32> %xor to <2 x i64>
   ret <2 x i64> %zext2
 }
 
+; Assert that zexts in and(zext(icmp), zext(icmp)) can be folded.
+; CHECK-LABEL: @fold_and_zext_icmp(
+; CHECK-NEXT:    [[ICMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK-NEXT:    [[ICMP2:%.*]] = icmp slt i64 %a, %c
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[ICMP1]], [[ICMP2]]
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[AND]] to i8
+; CHECK-NEXT:    ret i8 [[ZEXT]]
+define i8 @fold_and_zext_icmp(i64 %a, i64 %b, i64 %c) {
+  %1 = icmp sgt i64 %a, %b
+  %2 = zext i1 %1 to i8
+  %3 = icmp slt i64 %a, %c
+  %4 = zext i1 %3 to i8
+  %5 = and i8 %2, %4
+  ret i8 %5
+}
+
+; Assert that zexts in or(zext(icmp), zext(icmp)) can be folded.
+; CHECK-LABEL: @fold_or_zext_icmp(
+; CHECK-NEXT:    [[ICMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK-NEXT:    [[ICMP2:%.*]] = icmp slt i64 %a, %c
+; CHECK-NEXT:    [[OR:%.*]] = or i1 [[ICMP1]], [[ICMP2]]
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[OR]] to i8
+; CHECK-NEXT:    ret i8 [[ZEXT]]
+define i8 @fold_or_zext_icmp(i64 %a, i64 %b, i64 %c) {
+  %1 = icmp sgt i64 %a, %b
+  %2 = zext i1 %1 to i8
+  %3 = icmp slt i64 %a, %c
+  %4 = zext i1 %3 to i8
+  %5 = or i8 %2, %4
+  ret i8 %5
+}
+
+; Assert that zexts in xor(zext(icmp), zext(icmp)) can be folded.
+; CHECK-LABEL: @fold_xor_zext_icmp(
+; CHECK-NEXT:    [[ICMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK-NEXT:    [[ICMP2:%.*]] = icmp slt i64 %a, %c
+; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[ICMP1]], [[ICMP2]]
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[XOR]] to i8
+; CHECK-NEXT:    ret i8 [[ZEXT]]
+define i8 @fold_xor_zext_icmp(i64 %a, i64 %b, i64 %c) {
+  %1 = icmp sgt i64 %a, %b
+  %2 = zext i1 %1 to i8
+  %3 = icmp slt i64 %a, %c
+  %4 = zext i1 %3 to i8
+  %5 = xor i8 %2, %4
+  ret i8 %5
+}
+
+; Assert that zexts in logic(zext(icmp), zext(icmp)) are also folded accross
+; nested logical operators.
+; CHECK-LABEL: @fold_nested_logic_zext_icmp(
+; CHECK-NEXT:    [[ICMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK-NEXT:    [[ICMP2:%.*]] = icmp slt i64 %a, %c
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[ICMP1]], [[ICMP2]]
+; CHECK-NEXT:    [[ICMP3:%.*]] = icmp eq i64 %a, %d
+; CHECK-NEXT:    [[OR:%.*]] = or i1 [[AND]], [[ICMP3]]
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[OR]] to i8
+; CHECK-NEXT:    ret i8 [[ZEXT]]
+define i8 @fold_nested_logic_zext_icmp(i64 %a, i64 %b, i64 %c, i64 %d) {
+  %1 = icmp sgt i64 %a, %b
+  %2 = zext i1 %1 to i8
+  %3 = icmp slt i64 %a, %c
+  %4 = zext i1 %3 to i8
+  %5 = and i8 %2, %4
+  %6 = icmp eq i64 %a, %d
+  %7 = zext i1 %6 to i8
+  %8 = or i8 %5, %7
+  ret i8 %8
+}