[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

     }
   }
 
+  // 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;
 }
 

llvm/lib/Transforms/Utils/Local.cpp

         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));

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

 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()

   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:    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)

 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()

 ; 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()

 ; 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()

   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]]

   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()

   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()

   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
 }