[InstCombine] Canonicalize widenable.conditions for ease of pattern matching (and cases)

[reames]

Summary

Canonicalize and expressions involving widenable.conditions in two ways:

1. Treat widenable.conditions are more complex (and thus placed on the LHS) as compared to other instructions
2. Sink widenable.conditions to the outermost and in any and-tree.
3. Remove redundant widenable.conditions within a single and-tree.

The net effect is that we merge two widenable branches (say via SimplifyCFG realizing they share a slowpath branch), we can canonicalize back to a simple widenable branch with some set of conditions and a single WC call.

Note that this needs to land after D70502 as it swaps the current right operand preference for the WC. The current choice is problematic as instcombine will happily swap operands such that e.g. an argument is on the right instead.

[reames]

(add context to diff)

[ebrevnov]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1978

It's hard for me to match this comment to real code. Maybe just say "Swap OP1 & Op2 if Op2 is WC and Op1 is not" or "Canonicalize WC to LHS if RHS is not WC"?

1993

That will change evaluation order between A and B.

1994

This comment confused me a bit. My initial understanding was that next 'if' should handle this case . It took me a while to understand that it is actually handled by one of the previous 'if'. May be reformulate in terms:
A can't be WC because...
B can't be WC because...

2003

??? C can't be WC because...???

[reames]

Abandoning an old review I'm not going to return to any time soon.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(&I, m_c_And(m_OneUse(m_AShr(m_NSWSub(m_Value(Y), m_Value(X)),
                                           m_APInt(ShAmt))),
                           m_Deferred(X))) &&
         *ShAmt == Ty->getScalarSizeInBits() - 1) {
       Value *NewICmpInst = Builder.CreateICmpSGT(X, Y);
       return SelectInst::Create(NewICmpInst, X, ConstantInt::getNullValue(Ty));
     }
   }
 
+  // Canonicalize widenable.conditions for ease of pattern matching
+  {
+    // Canonicalize WC to left when compexity is equal (otherwise, it's already there)
+    if (match(Op1, m_Intrinsic<Intrinsic::experimental_widenable_condition>()) &&
+        !match(Op0, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
+      I.swapOperands();
+      return &I;
+    }
+
+    // If we have more than one WC involved in an expression, kill one if
+    // either would leave the condition trivially widenable.  
+    if (match(Op0, m_Intrinsic<Intrinsic::experimental_widenable_condition>()) &&
+        match(Op1, m_Intrinsic<Intrinsic::experimental_widenable_condition>()) &&
+        Op0->hasOneUse() && Op1->hasOneUse())
+      return replaceInstUsesWith(I, Op0);
+    
+    Value *X, *Y;
+    // (WC & B) & A --> (A & B) & WC
+    // (B & WC) & A is canonicalized to previous
+    // A can't be WC due to canonicalize to LHS
+    if (match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y)))) &&
+        match(X, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
+      cast<Instruction>(Op0)->setOperand(0, Op1);
+      I.setOperand(1, X);
+      return &I;
+    }
+    // A & (WC & C) --> WC & (A & C)
+    // A & (B & WC) is canonicalized to previous
+    // A might be WC
+    if (match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y)))) &&
+        match(X, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
+      if (!match(Op0, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
+        cast<Instruction>(Op1)->setOperand(0, Op0);
+        I.setOperand(0, X);
+        return &I;
+      } else if (Op0->hasOneUse() && X->hasOneUse()) {
+        // Exact same case as WC & Wc2 above, except there's an extra condition
+        // (Y) involved.
+        return replaceInstUsesWith(I, Op1);
+      }
+    }
+  }
   return nullptr;
 }
 
 Instruction *InstCombiner::matchBSwap(BinaryOperator &Or) {
   assert(Or.getOpcode() == Instruction::Or && "bswap requires an 'or'");
   Value *Op0 = Or.getOperand(0), *Op1 = Or.getOperand(1);
 
   // Look through zero extends.

llvm/lib/Transforms/Utils/Local.cpp

bool llvm::wouldInstructionBeTriviallyDead(Instruction *I,
   // Special case intrinsics that "may have side effects" but can be deleted
   // when dead.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     // Safe to delete llvm.stacksave and launder.invariant.group if dead.
     if (II->getIntrinsicID() == Intrinsic::stacksave ||
         II->getIntrinsicID() == Intrinsic::launder_invariant_group)
       return true;
 
+    // A widenable condition without uses is useless.
+    if (II->getIntrinsicID() == Intrinsic::experimental_widenable_condition)
+      return true;
+
     // Lifetime intrinsics are dead when their right-hand is undef.
     if (II->isLifetimeStartOrEnd())
       return isa<UndefValue>(II->getArgOperand(1));
 
     // Assumptions are dead if their condition is trivially true.  Guards on
     // true are operationally no-ops.  In the future we can consider more
     // sophisticated tradeoffs for guards considering potential for check
     // widening, but for now we keep things simple.

llvm/test/Transforms/InstCombine/widenable-conditions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
+define i1 @test0(i1 %a) {
+; CHECK-LABEL: @test0(
+; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[A:%.*]]
+; CHECK-NEXT:    ret i1 [[AND]]
+;
+  %wc = call i1 @llvm.experimental.widenable.condition()
+  %and = and i1 %a, %wc
+  ret i1 %and
+}
+
 define i1 @test1(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[WC]], [[B:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[A:%.*]]
+; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[LHS]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %lhs = and i1 %b, %wc
   %and = and i1 %lhs, %a
   ret i1 %and
 }
 
-; Negative test - profitability of dropping WC from first use unclear
+; Negative test - %lhs and %and must remain correlated for any value of %wc
 define i1 @test1b(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test1b(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[WC]], [[B:%.*]]
 ; CHECK-NEXT:    call void @use(i1 [[LHS]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %lhs = and i1 %b, %wc
   call void @use(i1 %lhs)
   %and = and i1 %lhs, %a
   ret i1 %and
 }
 
 ; multiple uses of A, B, WC doesn't change result
 define i1 @test1c(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test1c(
 ; CHECK-NEXT:    call void @use(i1 [[A:%.*]])
 ; CHECK-NEXT:    call void @use(i1 [[B:%.*]])
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    call void @use(i1 [[WC]])
-; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[WC]], [[B]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[A]]
+; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[A]], [[B]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[LHS]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   call void @use(i1 %a)
   call void @use(i1 %b)
   %wc = call i1 @llvm.experimental.widenable.condition()
   call void @use(i1 %wc)
   %lhs = and i1 %b, %wc
   %and = and i1 %lhs, %a
   ret i1 %and
 }
 
 define i1 @test2(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[WC]], [[B:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[A:%.*]]
+; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[LHS]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %lhs = and i1 %wc, %b
   %and = and i1 %lhs, %a
   ret i1 %and
 }
 
 ; To test the rhs side, an instruction on lhs to prevent complexity
 ; canonicalization reducing to above.
 define i1 @test3(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[RHS:%.*]] = and i1 [[WC]], [[C:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[RHS]]
+; CHECK-NEXT:    [[RHS:%.*]] = and i1 [[LHS]], [[C:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[RHS]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %lhs = and i1 %a, %b
   %rhs = and i1 %c, %wc
   %and = and i1 %lhs, %rhs
   ret i1 %and
 }
 
 define i1 @test4(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[RHS:%.*]] = and i1 [[WC]], [[C:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[RHS]]
+; CHECK-NEXT:    [[RHS:%.*]] = and i1 [[LHS]], [[C:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[RHS]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %lhs = and i1 %a, %b
   %rhs = and i1 %wc, %c
   %and = and i1 %lhs, %rhs
   ret i1 %and
 }
 
-define i1 @test5(i1 %a, i1 %b) {
+define i1 @test5() {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    ret i1 [[WC]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %and = and i1 %wc, %wc
   ret i1 %and
 }
 
-define i1 @test6(i1 %a, i1 %b) {
+define i1 @test6() {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[WC2:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[WC2]]
-; CHECK-NEXT:    ret i1 [[AND]]
+; CHECK-NEXT:    ret i1 [[WC]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %wc2 = call i1 @llvm.experimental.widenable.condition()
   %and = and i1 %wc, %wc2
   ret i1 %and
 }
 
-define i1 @test7(i1 %a, i1 %b) {
-; CHECK-LABEL: @test7(
+; It's tempting to pick the WC with more than one use, but that leaves this
+; expression in a form which isn't (trivially) widenable.  It's better to
+; leave a single use WC as part of the expression.
+define i1 @test6_neg1() {
+; CHECK-LABEL: @test6_neg1(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    call void @use(i1 [[WC]])
 ; CHECK-NEXT:    [[WC2:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[WC2]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   call void @use(i1 %wc)
   %wc2 = call i1 @llvm.experimental.widenable.condition()
   %and = and i1 %wc, %wc2
   ret i1 %and
 }
 
-define i1 @test8(i1 %a, i1 %b) {
+define i1 @test8(i1 %a) {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[WC2:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    call void @use(i1 [[WC2]])
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[WC2]]
-; CHECK-NEXT:    ret i1 [[AND]]
+; CHECK-NEXT:    [[RHS:%.*]] = and i1 [[WC]], [[A:%.*]]
+; CHECK-NEXT:    ret i1 [[RHS]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %wc2 = call i1 @llvm.experimental.widenable.condition()
-  call void @use(i1 %wc2)
-  %and = and i1 %wc, %wc2
+  %rhs = and i1 %wc, %a
+  %and = and i1 %wc2, %rhs
   ret i1 %and
 }
 
 
 declare void @use(i1)
 declare i1 @llvm.experimental.widenable.condition()