[InstCombine] Make `isFreeToInvert` check recursively.

[goldstein.w.n]

Summary

Some Instructions (select/min/max) are inverted by just inverting the
operands. So the answer of whether they are free to invert is really
just whether the operands are free to invert.

[nikic]

The change itself looks fine to me, but the test changes don't look particularly compelling...

llvm/test/Transforms/LoopVectorize/reduction-inloop.ll

1362

This looks like a regression?

[goldstein.w.n]

llvm/test/Transforms/LoopVectorize/reduction-inloop.ll

1362

agreed. Will fix before proceeding.

[goldstein.w.n]

In D159056#4624311, @nikic wrote:

The change itself looks fine to me, but the test changes don't look particularly compelling...

Okay,

So the regression is fundementally because for i1 select we canonicalize:
select C, false, A -> select ~C, A, false
and
select C, A, true -> select ~C, true, A.
This is to put the select into logical and/or form which is necessary for
A LOT of simplifications.

I started a preliminary patch to only do the canonicalization if it wouldn't
add a new instruction and the test results look good (maybe 30-40 tests
save 1-5 instructions, no regressions). That being said, I think a large
part of the reason for this is the vast majority of our test cases are
very simple so we usually get away with a free canonicalzation, and most
of the cases we just don't canonicalize the tests are only a few instructions
long and aren't really banging and logical and/or patterns.

The easy solution here is to create the canonicalized version -> run
the simplifications -> if we simplify return that, otherwise pop canonicalized
version. But thats not really a good coding pattern.

The other approach is to go through all and/or logic and update it to
also recognize !and and !or.

Or maybe another reasonable possibility?
What do you think?

Edit: Personally feel like pushing/popping at the very least makes more
sense than creating known unnecessary instructions.

[goldstein.w.n]

In D159056#4626378, @goldstein.w.n wrote:

In D159056#4624311, @nikic wrote:

The change itself looks fine to me, but the test changes don't look particularly compelling...

Okay,

So the regression is fundementally because for i1 select we canonicalize:
select C, false, A -> select ~C, A, false
and
select C, A, true -> select ~C, true, A.
This is to put the select into logical and/or form which is necessary for
A LOT of simplifications.

I started a preliminary patch to only do the canonicalization if it wouldn't
add a new instruction and the test results look good (maybe 30-40 tests
save 1-5 instructions, no regressions). That being said, I think a large
part of the reason for this is the vast majority of our test cases are
very simple so we usually get away with a free canonicalzation, and most
of the cases we just don't canonicalize the tests are only a few instructions
long and aren't really banging and logical and/or patterns.

The easy solution here is to create the canonicalized version -> run
the simplifications -> if we simplify return that, otherwise pop canonicalized
version. But thats not really a good coding pattern.

The other approach is to go through all and/or logic and update it to
also recognize !and and !or.

Or maybe another reasonable possibility?

Another thought it that even it

What do you think?

Edit: Personally feel like pushing/popping at the very least makes more
sense than creating known unnecessary instructions.

This actually isn't so easy.

In D159056#4626378, @goldstein.w.n wrote:

In D159056#4624311, @nikic wrote:

The change itself looks fine to me, but the test changes don't look particularly compelling...

Okay,

So the regression is fundementally because for i1 select we canonicalize:
select C, false, A -> select ~C, A, false
and
select C, A, true -> select ~C, true, A.
This is to put the select into logical and/or form which is necessary for
A LOT of simplifications.

I started a preliminary patch to only do the canonicalization if it wouldn't
add a new instruction and the test results look good (maybe 30-40 tests
save 1-5 instructions, no regressions). That being said, I think a large
part of the reason for this is the vast majority of our test cases are
very simple so we usually get away with a free canonicalzation, and most
of the cases we just don't canonicalize the tests are only a few instructions
long and aren't really banging and logical and/or patterns.

The easy solution here is to create the canonicalized version -> run
the simplifications -> if we simplify return that, otherwise pop canonicalized
version. But thats not really a good coding pattern.

The other approach is to go through all and/or logic and update it to
also recognize !and and !or.

Or maybe another reasonable possibility?

Another thought is that even if it costs an extra instruction logical and/or form
is more canonical and can be cleaned up elsewhere (i.e at selectiondaglowering).

What do you think?

Edit: Personally feel like pushing/popping at the very least makes more
sense than creating known unnecessary instructions.

Went with making all the (and/or cmp0, cmp1) work on just components of comparison so we can just drop the canonicalization w.o losing the folds.

[Allen]

llvm/include/llvm/Transforms/InstCombine/InstCombiner.h

263

does it make sense to restrict the condition of recursion call? then the case predicated_or_dominates_reduction will not be touched.

+    if (match(V,
+              m_Select(PatternMatch::m_Value(), m_Not(PatternMatch::m_Value(A)),
+                       m_Not(PatternMatch::m_Value(B)))) ||
+        match(V, m_MaxOrMin(m_Not(PatternMatch::m_Value(A)),
+                            m_Not(PatternMatch::m_Value(B)))))

[goldstein.w.n]

Rebase (fixed regressions)

[goldstein.w.n]

llvm/include/llvm/Transforms/InstCombine/InstCombiner.h

263

Think that somewhat defeats the purpose of the change.
Have D159327 and D159328 which hopefully should fix the regression.

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Abandoning and resubmitting on GH.

llvm/include/llvm/Transforms/InstCombine/InstCombiner.h

public:
   }
 
   /// Return true if the specified value is free to invert (apply ~ to).
   /// This happens in cases where the ~ can be eliminated.  If WillInvertAllUses
   /// is true, work under the assumption that the caller intends to remove all
   /// uses of V and only keep uses of ~V.
   ///
   /// See also: canFreelyInvertAllUsersOf()
-  static bool isFreeToInvert(Value *V, bool WillInvertAllUses) {
+  static bool isFreeToInvert(Value *V, bool WillInvertAllUses,
+                             unsigned Depth = 0) {
     // ~(~(X)) -> X.
     if (match(V, m_Not(PatternMatch::m_Value())))
       return true;
 
     // Constants can be considered to be not'ed values.
     if (match(V, PatternMatch::m_AnyIntegralConstant()))
       return true;
 
+    if (Depth++ >= MaxAnalysisRecursionDepth)
+      return false;
+
+    // The rest of the cases require that we invert all uses so don't bother
+    // doing the analysis if we know we can't use the result.
+    if (!WillInvertAllUses)
+      return false;
+
     // Compares can be inverted if all of their uses are being modified to use
     // the ~V.
     if (isa<CmpInst>(V))
-      return WillInvertAllUses;
+      return true;
 
-    // If `V` is of the form `A + Constant` then `-1 - V` can be folded into
-    // `(-1 - Constant) - A` if we are willing to invert all of the uses.
-    if (match(V, m_Add(PatternMatch::m_Value(), PatternMatch::m_ImmConstant())))
-      return WillInvertAllUses;
-
-    // If `V` is of the form `Constant - A` then `-1 - V` can be folded into
-    // `A + (-1 - Constant)` if we are willing to invert all of the uses.
-    if (match(V, m_Sub(PatternMatch::m_ImmConstant(), PatternMatch::m_Value())))
-      return WillInvertAllUses;
-
-    // Selects with invertible operands are freely invertible
-    if (match(V,
-              m_Select(PatternMatch::m_Value(), m_Not(PatternMatch::m_Value()),
-                       m_Not(PatternMatch::m_Value()))))
-      return WillInvertAllUses;
-
-    // Min/max may be in the form of intrinsics, so handle those identically
-    // to select patterns.
-    if (match(V, m_MaxOrMin(m_Not(PatternMatch::m_Value()),
-                            m_Not(PatternMatch::m_Value()))))
-      return WillInvertAllUses;
+    Value *A, *B;
+    // If `V` is of the form `A + B` then `-1 - V` can be folded into
+    // `~B - A` or `~A - B` if we are willing to invert all of the uses.
+    if (match(V, m_Add(PatternMatch::m_Value(A), PatternMatch::m_Value(B))))
+      return isFreeToInvert(A, A->hasOneUse(), Depth) ||
+             isFreeToInvert(B, B->hasOneUse(), Depth);
+
+    // If `V` is of the form `A - B` then `-1 - V` can be folded into
+    // `~A + B` if we are willing to invert all of the uses.
+    if (match(V, m_Sub(PatternMatch::m_Value(A), PatternMatch::m_Value())))
+      return isFreeToInvert(A, A->hasOneUse(), Depth);
+
+    // Selects/min/max with invertible operands are freely invertible
+    if (match(V, m_Select(PatternMatch::m_Value(), PatternMatch::m_Value(A),
+                          PatternMatch::m_Value(B))) ||
+        match(V,
+              m_MaxOrMin(PatternMatch::m_Value(A), PatternMatch::m_Value(B))))
+      return isFreeToInvert(A, A->hasOneUse(), Depth) &&
+             isFreeToInvert(B, B->hasOneUse(), Depth);
 
     return false;
   }
 
   /// Given i1 V, can every user of V be freely adapted if V is changed to !V ?
   /// InstCombine's freelyInvertAllUsersOf() must be kept in sync with this fn.
   /// NOTE: for Instructions only!
   ///

llvm/test/Transforms/InstCombine/minmax-intrinsics.ll

;
   call void @use(i8 %m2)
   %m3 = call i8 @llvm.smin.i8(i8 %m1, i8 %m2)
   %not = xor i8 %m3, -1
   ret i8 %not
 }
 
 define i8 @sub_not_min_max(i8 %r, i8 %g, i8 %b) {
 ; CHECK-LABEL: @sub_not_min_max(
-; CHECK-NEXT:    [[NOTR:%.*]] = xor i8 [[R:%.*]], -1
 ; CHECK-NEXT:    [[NOTG:%.*]] = xor i8 [[G:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTG]])
 ; CHECK-NEXT:    [[NOTB:%.*]] = xor i8 [[B:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTB]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[NOTR]], i8 [[NOTG]])
-; CHECK-NEXT:    [[K:%.*]] = call i8 @llvm.smin.i8(i8 [[M]], i8 [[NOTB]])
-; CHECK-NEXT:    [[CK:%.*]] = sub i8 [[NOTR]], [[K]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.smax.i8(i8 [[R:%.*]], i8 [[G]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.smax.i8(i8 [[TMP1]], i8 [[B]])
+; CHECK-NEXT:    [[CK:%.*]] = sub i8 [[TMP2]], [[R]]
 ; CHECK-NEXT:    ret i8 [[CK]]
 ;
   %notr = xor i8 %r, -1
   %notg = xor i8 %g, -1
   call void @use(i8 %notg)
   %notb = xor i8 %b, -1
   call void @use(i8 %notb)
   %m = call i8 @llvm.smin.i8(i8 %notr, i8 %notg)
   %k = call i8 @llvm.smin.i8(i8 %m, i8 %notb)
   %ck = sub i8 %notr, %k
   ret i8 %ck
 }
 
 define i8 @sub_not_min_max_uses1(i8 %r, i8 %g, i8 %b) {
 ; CHECK-LABEL: @sub_not_min_max_uses1(
 ; CHECK-NEXT:    [[NOTR:%.*]] = xor i8 [[R:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTR]])
 ; CHECK-NEXT:    [[NOTG:%.*]] = xor i8 [[G:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTG]])
 ; CHECK-NEXT:    [[NOTB:%.*]] = xor i8 [[B:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTB]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[NOTR]], i8 [[NOTG]])
-; CHECK-NEXT:    [[K:%.*]] = call i8 @llvm.smin.i8(i8 [[M]], i8 [[NOTB]])
-; CHECK-NEXT:    [[CK:%.*]] = sub i8 [[NOTR]], [[K]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.smax.i8(i8 [[R]], i8 [[G]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.smax.i8(i8 [[TMP1]], i8 [[B]])
+; CHECK-NEXT:    [[CK:%.*]] = sub i8 [[TMP2]], [[R]]
 ; CHECK-NEXT:    ret i8 [[CK]]
 ;
   %notr = xor i8 %r, -1
   call void @use(i8 %notr)
   %notg = xor i8 %g, -1
   call void @use(i8 %notg)
   %notb = xor i8 %b, -1
   call void @use(i8 %notb)

llvm/test/Transforms/InstCombine/pr63791.ll

 ; CHECK:       for.cond.i:
 ; CHECK-NEXT:    br i1 false, label [[FOR_COND_I]], label [[FOR_COND5_PREHEADER_I:%.*]]
 ; CHECK:       for.cond1.loopexit.i:
 ; CHECK-NEXT:    store i1 true, ptr poison, align 1
 ; CHECK-NEXT:    br i1 poison, label [[FOR_COND_I]], label [[FOR_COND5_PREHEADER_I]]
 ; CHECK:       for.cond5.preheader.i:
 ; CHECK-NEXT:    br i1 false, label [[FOR_INC19_I:%.*]], label [[FOR_COND1_LOOPEXIT_I:%.*]]
 ; CHECK:       for.inc19.i:
-; CHECK-NEXT:    br i1 false, label [[FOR_INC19_I]], label [[FOR_COND1_LOOPEXIT_I]]
+; CHECK-NEXT:    br i1 true, label [[FOR_COND1_LOOPEXIT_I]], label [[FOR_INC19_I]]
 ;
 entry:
   br label %for.cond.i
 
 for.cond.i:                                       ; preds = %for.cond1.loopexit.i, %for.cond.i, %entry
   %phi1 = phi ptr [ @j, %entry ], [ @j, %for.cond.i ], [ null, %for.cond1.loopexit.i ]
   %load1 = load i32, ptr %phi1, align 4
   br i1 false, label %for.cond.i, label %for.cond5.preheader.i

llvm/test/Transforms/LoopVectorize/reduction-inloop.ll

 define i32 @predicated_or_dominates_reduction(ptr %b) {
 ; CHECK-LABEL: @predicated_or_dominates_reduction(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[PRED_LOAD_CONTINUE6:%.*]] ]
-; CHECK-NEXT:    [[VEC_PHI:%.*]] = phi i32 [ undef, [[VECTOR_PH]] ], [ [[TMP51:%.*]], [[PRED_LOAD_CONTINUE6]] ]
+; CHECK-NEXT:    [[VEC_PHI:%.*]] = phi i32 [ undef, [[VECTOR_PH]] ], [ [[TMP49:%.*]], [[PRED_LOAD_CONTINUE6]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = or i32 [[INDEX]], 1
 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[INDEX]], 2
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[INDEX]], 3
 ; CHECK-NEXT:    [[TMP3:%.*]] = sext i32 [[INDEX]] to i64
 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds [0 x %struct.e], ptr [[B:%.*]], i64 0, i64 [[TMP3]], i32 1
 ; CHECK-NEXT:    [[TMP5:%.*]] = sext i32 [[TMP0]] to i64
 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds [0 x %struct.e], ptr [[B]], i64 0, i64 [[TMP5]], i32 1
 ; CHECK-NEXT:    [[TMP7:%.*]] = sext i32 [[TMP1]] to i64

 ; CHECK:       pred.load.if5:
 ; CHECK-NEXT:    [[TMP39:%.*]] = sext i32 [[TMP2]] to i64
 ; CHECK-NEXT:    [[TMP40:%.*]] = getelementptr inbounds [0 x %struct.e], ptr [[B]], i64 0, i64 [[TMP39]]
 ; CHECK-NEXT:    [[TMP41:%.*]] = load i32, ptr [[TMP40]], align 4
 ; CHECK-NEXT:    [[TMP42:%.*]] = insertelement <4 x i32> [[TMP37]], i32 [[TMP41]], i64 3
 ; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE6]]
 ; CHECK:       pred.load.continue6:
 ; CHECK-NEXT:    [[TMP43:%.*]] = phi <4 x i32> [ [[TMP37]], [[PRED_LOAD_CONTINUE4]] ], [ [[TMP42]], [[PRED_LOAD_IF5]] ]
-; CHECK-NEXT:    [[TMP44:%.*]] = icmp ne <4 x i32> [[TMP43]], zeroinitializer
-; CHECK-NEXT:    [[TMP45:%.*]] = select <4 x i1> [[TMP19]], <4 x i1> [[TMP44]], <4 x i1> zeroinitializer
-; CHECK-NEXT:    [[TMP46:%.*]] = xor <4 x i1> [[TMP19]], <i1 true, i1 true, i1 true, i1 true>
-; CHECK-NEXT:    [[TMP47:%.*]] = or <4 x i1> [[TMP45]], [[TMP46]]
-; CHECK-NEXT:    [[TMP48:%.*]] = bitcast <4 x i1> [[TMP47]] to i4
-; CHECK-NEXT:    [[TMP49:%.*]] = call i4 @llvm.ctpop.i4(i4 [[TMP48]]), !range [[RNG42:![0-9]+]]
-; CHECK-NEXT:    [[TMP50:%.*]] = zext i4 [[TMP49]] to i32
-; CHECK-NEXT:    [[TMP51]] = add i32 [[VEC_PHI]], [[TMP50]]
+; CHECK-NEXT:    [[TMP44:%.*]] = icmp eq <4 x i32> [[TMP43]], zeroinitializer
+; CHECK-NEXT:    [[NOT_:%.*]] = xor <4 x i1> [[TMP19]], <i1 true, i1 true, i1 true, i1 true>
+; CHECK-NEXT:    [[TMP45:%.*]] = select <4 x i1> [[NOT_]], <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i1> [[TMP44]]
+; CHECK-NEXT:    [[DOTNOT7:%.*]] = and <4 x i1> [[TMP45]], [[TMP19]]
+; CHECK-NEXT:    [[NOT__NOT7:%.*]] = xor <4 x i1> [[DOTNOT7]], <i1 true, i1 true, i1 true, i1 true>
+; CHECK-NEXT:    [[TMP46:%.*]] = bitcast <4 x i1> [[NOT__NOT7]] to i4
+; CHECK-NEXT:    [[TMP47:%.*]] = call i4 @llvm.ctpop.i4(i4 [[TMP46]]), !range [[RNG42:![0-9]+]]
+; CHECK-NEXT:    [[TMP48:%.*]] = zext i4 [[TMP47]] to i32
+; CHECK-NEXT:    [[TMP49]] = add i32 [[VEC_PHI]], [[TMP48]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 4
-; CHECK-NEXT:    [[TMP52:%.*]] = icmp eq i32 [[INDEX_NEXT]], 1000
-; CHECK-NEXT:    br i1 [[TMP52]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP43:![0-9]+]]
+; CHECK-NEXT:    [[TMP50:%.*]] = icmp eq i32 [[INDEX_NEXT]], 1000
+; CHECK-NEXT:    br i1 [[TMP50]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP43:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    br i1 true, label [[FOR_COND_CLEANUP:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.cond.cleanup:
-; CHECK-NEXT:    [[A_1_LCSSA:%.*]] = phi i32 [ poison, [[FOR_INC:%.*]] ], [ [[TMP51]], [[MIDDLE_BLOCK]] ]
+; CHECK-NEXT:    [[A_1_LCSSA:%.*]] = phi i32 [ poison, [[FOR_INC:%.*]] ], [ [[TMP49]], [[MIDDLE_BLOCK]] ]
 ; CHECK-NEXT:    ret i32 [[A_1_LCSSA]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    br i1 poison, label [[LOR_LHS_FALSE:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       lor.lhs.false:
 ; CHECK-NEXT:    br i1 poison, label [[FOR_INC]], label [[IF_THEN]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc: