[InstCombine] canonicalize icmp predicate feeding select

[spatel]

Summary

This canonicalization was suggested in D33172 as a way to make InstCombine behavior more uniform. We have this transform for icmp+br, so unless there's some reason that icmp+select should be treated differently, I think we should do the same thing here.

The benefit comes from increasing the chances of creating identical instructions. This is shown in the tests in logical-select.ll (PR32791). InstCombine doesn't fold those directly, but EarlyCSE can simplify the identical cmps, and then InstCombine can fold the selects together.

The possible regression for the tests in select.ll raises questions about poison/undef:
http://lists.llvm.org/pipermail/llvm-dev/2017-May/113261.html

...but I think that transform is just as likely to be triggered by this canonicalization as it is to be missed, so we're just pointing out a commutation deficiency in the pattern matching:
https://reviews.llvm.org/rL228409

[davide]

If the goal of this is to expose more opportunities for congruent expressions maybe GVN itself should do this canonicalization, maybe? Some algorithms perform, e.g., reassociation to catch more cases.
See, e.g.
http://www.sable.mcgill.ca/~hendren/621/karthikhandouts.pdf

[spatel]

In D34242#783298, @davide wrote:

If the goal of this is to expose more opportunities for congruent expressions maybe GVN itself should do this canonicalization, maybe? Some algorithms perform, e.g., reassociation to catch more cases.
See, e.g.
http://www.sable.mcgill.ca/~hendren/621/karthikhandouts.pdf

Are you suggesting a change to GVN as an independent improvement or as a substitute for this transform in InstCombine? As I mentioned, I think this patch makes InstCombine behavior more predictable and consistent (because we already have this transform for cmp+br).

[spatel]

Ping.

[efriedma]

LGTM.

lib/Transforms/InstCombine/InstCombineSelect.cpp

Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
 
   if (Value *V = SimplifySelectInst(CondVal, TrueVal, FalseVal,
                                     SQ.getWithInstruction(&SI)))
     return replaceInstUsesWith(SI, V);
 
   if (Instruction *I = canonicalizeSelectToShuffle(SI))
     return I;
 
+  // Canonicalize a one-use integer compare with a non-canonical predicate by
+  // inverting the predicate and swapping the select operands. This matches a
+  // compare canonicalization for conditional branches.
+  // TODO: Should we do the same for FP compares?
+  CmpInst::Predicate Pred;
+  if (match(CondVal, m_OneUse(m_ICmp(Pred, m_Value(), m_Value()))) &&
+      !isCanonicalPredicate(Pred)) {
+    // Swap true/false values and condition.
+    CmpInst *Cond = cast<CmpInst>(CondVal);
+    Cond->setPredicate(CmpInst::getInversePredicate(Pred));
+    SI.setOperand(1, FalseVal);
+    SI.setOperand(2, TrueVal);
+    SI.swapProfMetadata();
+    Worklist.Add(Cond);
+    return &SI;
+  }
+
   if (SelType->getScalarType()->isIntegerTy(1) &&
       TrueVal->getType() == CondVal->getType()) {
     if (match(TrueVal, m_One())) {
       // Change: A = select B, true, C --> A = or B, C
       return BinaryOperator::CreateOr(CondVal, FalseVal);
     }
     if (match(TrueVal, m_Zero())) {
       // Change: A = select B, false, C --> A = and !B, C

test/Transforms/InstCombine/ffs-1.ll

 }
 
 ; Check ffs(x) -> x != 0 ? (i32)llvm.cttz(x) + 1 : 0.
 
 define i32 @test_simplify13(i32 %x) {
 ; ALL-LABEL: @test_simplify13(
 ; ALL-NEXT:    [[CTTZ:%.*]] = call i32 @llvm.cttz.i32(i32 %x, i1 true)
 ; ALL-NEXT:    [[TMP1:%.*]] = add nuw nsw i32 [[CTTZ]], 1
-; ALL-NEXT:    [[TMP2:%.*]] = icmp ne i32 %x, 0
-; ALL-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 [[TMP1]], i32 0
+; ALL-NEXT:    [[TMP2:%.*]] = icmp eq i32 %x, 0
+; ALL-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 0, i32 [[TMP1]]
 ; ALL-NEXT:    ret i32 [[TMP3]]
 ;
   %ret = call i32 @ffs(i32 %x)
   ret i32 %ret
 }
 
 define i32 @test_simplify14(i32 %x) {
 ; GENERIC-LABEL: @test_simplify14(
 ; GENERIC-NEXT:    [[RET:%.*]] = call i32 @ffsl(i32 %x)
 ; GENERIC-NEXT:    ret i32 [[RET]]
 ;
 ; TARGET-LABEL: @test_simplify14(
 ; TARGET-NEXT:    [[CTTZ:%.*]] = call i32 @llvm.cttz.i32(i32 %x, i1 true)
 ; TARGET-NEXT:    [[TMP1:%.*]] = add nuw nsw i32 [[CTTZ]], 1
-; TARGET-NEXT:    [[TMP2:%.*]] = icmp ne i32 %x, 0
-; TARGET-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 [[TMP1]], i32 0
+; TARGET-NEXT:    [[TMP2:%.*]] = icmp eq i32 %x, 0
+; TARGET-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 0, i32 [[TMP1]]
 ; TARGET-NEXT:    ret i32 [[TMP3]]
 ;
   %ret = call i32 @ffsl(i32 %x)
   ret i32 %ret
 }
 
 define i32 @test_simplify15(i64 %x) {
 ; GENERIC-LABEL: @test_simplify15(
 ; GENERIC-NEXT:    [[RET:%.*]] = call i32 @ffsll(i64 %x)
 ; GENERIC-NEXT:    ret i32 [[RET]]
 ;
 ; TARGET-LABEL: @test_simplify15(
 ; TARGET-NEXT:    [[CTTZ:%.*]] = call i64 @llvm.cttz.i64(i64 %x, i1 true)
 ; TARGET-NEXT:    [[TMP1:%.*]] = add nuw nsw i64 [[CTTZ]], 1
 ; TARGET-NEXT:    [[TMP2:%.*]] = trunc i64 [[TMP1]] to i32
-; TARGET-NEXT:    [[TMP3:%.*]] = icmp ne i64 %x, 0
-; TARGET-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i32 [[TMP2]], i32 0
+; TARGET-NEXT:    [[TMP3:%.*]] = icmp eq i64 %x, 0
+; TARGET-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i32 0, i32 [[TMP2]]
 ; TARGET-NEXT:    ret i32 [[TMP4]]
 ;
   %ret = call i32 @ffsll(i64 %x)
   ret i32 %ret
 }
 

test/Transforms/InstCombine/icmp.ll

;
   %s = select i1 %cmp, i32 10000, i32 0
   ret i32 %s
 }
 
 define i32 @f7(i32 %a, i32 %b) {
 ; CHECK-LABEL: @f7(
 ; CHECK-NEXT:    [[CMP_UNSHIFTED:%.*]] = xor i32 %a, %b
 ; CHECK-NEXT:    [[CMP_MASK:%.*]] = and i32 [[CMP_UNSHIFTED]], 511
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[CMP:%.*]].mask, 0
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[CMP]], i32 10000, i32 0
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[CMP_MASK]], 0
+; CHECK-NEXT:    [[S:%.*]] = select i1 [[CMP]], i32 0, i32 10000
 ; CHECK-NEXT:    ret i32 [[S]]
 ;
   %sext = shl i32 %a, 23
   %sext6 = shl i32 %b, 23
   %cmp = icmp ne i32 %sext, %sext6
   %s = select i1 %cmp, i32 10000, i32 0
   ret i32 %s
 }

test/Transforms/InstCombine/logical-select.ll

;
   %iftmp.0.0 = select i1 %t0, i32 -1, i32 0
   %t1 = and i32 %iftmp.0.0, %c
   %iftmp = select i1 %t0, i32 0, i32 -1
   %t2 = and i32 %iftmp, %d
   %t3 = or i32 %t1, %t2
   ret i32 %t3
 }
 
-; TODO: For the next 4 tests, are there potential canonicalizations and/or folds for these
-; in InstCombine? Independent of that, tests like this that may not show any transforms 
-; still have value because they can help identify conflicting canonicalization rules that 
-; lead to infinite looping. 
-
 ; PR32791 - https://bugs.llvm.org//show_bug.cgi?id=32791
-; Fold two selects with inverted predicates and zero operands.
+; The 2nd compare/select are canonicalized, so CSE and another round of instcombine or some other pass will fold this.
+
 define i32 @fold_inverted_icmp_preds(i32 %a, i32 %b, i32 %c, i32 %d) {
 ; CHECK-LABEL: @fold_inverted_icmp_preds(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 %a, %b
 ; CHECK-NEXT:    [[SEL1:%.*]] = select i1 [[CMP1]], i32 %c, i32 0
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sge i32 %a, %b
-; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[CMP2]], i32 %d, i32 0
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 %a, %b
+; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[CMP2]], i32 0, i32 %d
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SEL1]], [[SEL2]]
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %cmp1 = icmp slt i32 %a, %b
   %sel1 = select i1 %cmp1, i32 %c, i32 0
   %cmp2 = icmp sge i32 %a, %b
   %sel2 = select i1 %cmp2, i32 %d, i32 0
   %or = or i32 %sel1, %sel2
   ret i32 %or
 }
 
+; The 2nd compare/select are canonicalized, so CSE and another round of instcombine or some other pass will fold this.
+
 define i32 @fold_inverted_icmp_preds_reverse(i32 %a, i32 %b, i32 %c, i32 %d) {
 ; CHECK-LABEL: @fold_inverted_icmp_preds_reverse(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 %a, %b
 ; CHECK-NEXT:    [[SEL1:%.*]] = select i1 [[CMP1]], i32 0, i32 %c
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sge i32 %a, %b
-; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[CMP2]], i32 0, i32 %d
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 %a, %b
+; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[CMP2]], i32 %d, i32 0
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SEL1]], [[SEL2]]
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %cmp1 = icmp slt i32 %a, %b
   %sel1 = select i1 %cmp1, i32 0, i32 %c
   %cmp2 = icmp sge i32 %a, %b
   %sel2 = select i1 %cmp2, i32 0, i32 %d
   %or = or i32 %sel1, %sel2
   ret i32 %or
 }
 
+; TODO: Should fcmp have the same sort of predicate canonicalization as icmp?
+
 define i32 @fold_inverted_fcmp_preds(float %a, float %b, i32 %c, i32 %d) {
 ; CHECK-LABEL: @fold_inverted_fcmp_preds(
 ; CHECK-NEXT:    [[CMP1:%.*]] = fcmp olt float %a, %b
 ; CHECK-NEXT:    [[SEL1:%.*]] = select i1 [[CMP1]], i32 %c, i32 0
 ; CHECK-NEXT:    [[CMP2:%.*]] = fcmp uge float %a, %b
 ; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[CMP2]], i32 %d, i32 0
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SEL1]], [[SEL2]]
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %cmp1 = fcmp olt float %a, %b
   %sel1 = select i1 %cmp1, i32 %c, i32 0
   %cmp2 = fcmp uge float %a, %b
   %sel2 = select i1 %cmp2, i32 %d, i32 0
   %or = or i32 %sel1, %sel2
   ret i32 %or
 }
 
+; The 2nd compare/select are canonicalized, so CSE and another round of instcombine or some other pass will fold this.
+
 define <2 x i32> @fold_inverted_icmp_vector_preds(<2 x i32> %a, <2 x i32> %b, <2 x i32> %c, <2 x i32> %d) {
 ; CHECK-LABEL: @fold_inverted_icmp_vector_preds(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne <2 x i32> %a, %b
-; CHECK-NEXT:    [[SEL1:%.*]] = select <2 x i1> [[CMP1]], <2 x i32> %c, <2 x i32> zeroinitializer
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq <2 x i32> %a, %b
+; CHECK-NEXT:    [[SEL1:%.*]] = select <2 x i1> [[CMP1]], <2 x i32> zeroinitializer, <2 x i32> %c
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq <2 x i32> %a, %b
 ; CHECK-NEXT:    [[SEL2:%.*]] = select <2 x i1> [[CMP2]], <2 x i32> %d, <2 x i32> zeroinitializer
 ; CHECK-NEXT:    [[OR:%.*]] = or <2 x i32> [[SEL1]], [[SEL2]]
 ; CHECK-NEXT:    ret <2 x i32> [[OR]]
 ;
   %cmp1 = icmp ne <2 x i32> %a, %b
   %sel1 = select <2 x i1> %cmp1, <2 x i32> %c, <2 x i32> <i32 0, i32 0>
   %cmp2 = icmp eq <2 x i32> %a, %b

test/Transforms/InstCombine/max-of-nots.ll

;
   %c1 = icmp slt i32 %s0, %xor_x
   %smax96 = select i1 %c1, i32 %xor_x, i32 %s0
   ret i32 %smax96
 }
 
  ; negative test case (i.e. can not simplify) : ABS(MIN(NOT x,y))
 define i32 @abs_of_min_of_not(i32 %x, i32 %y) {
 ; CHECK-LABEL: @abs_of_min_of_not(
-; CHECK-NEXT: xor
-; CHECK-NEXT: add
-; CHECK-NEXT: icmp sge
-; CHECK-NEXT: select
-; CHECK-NEXT: icmp sgt
-; CHECK-NEXT: sub
-; CHECK-NEXT: select
-; CHECK-NEXT: ret
+; CHECK-NEXT:    [[XORD:%.*]] = xor i32 %x, -1
+; CHECK-NEXT:    [[YADD:%.*]] = add i32 %y, 2
+; CHECK-NEXT:    [[COND_I:%.*]] = icmp slt i32 [[YADD]], [[XORD]]
+; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[COND_I]], i32 [[YADD]], i32 [[XORD]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[MIN]], -1
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[MIN]]
+; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP2]], i32 [[MIN]], i32 [[SUB]]
+; CHECK-NEXT:    ret i32 [[ABS]]
+;
 
   %xord = xor i32 %x, -1
   %yadd = add i32 %y, 2
   %cond.i = icmp sge i32 %yadd, %xord
   %min = select i1 %cond.i, i32 %xord, i32 %yadd
   %cmp2 = icmp sgt i32 %min, -1
   %sub = sub i32 0, %min
   %abs = select i1 %cmp2, i32 %min, i32 %sub

test/Transforms/InstCombine/select-with-bitwise-ops.ll

;
   %2 = icmp ne i64 %1, 0
   %3 = select i1 %2, i32 40, i32 42
   ret i32 %3
 }
 
 define i32 @test66(i64 %x) {
 ; CHECK-LABEL: @test66(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i64 %x, 4294967296
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 40, i32 42
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 42, i32 40
 ; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %1 = and i64 %x, 4294967296
   %2 = icmp ne i64 %1, 0
   %3 = select i1 %2, i32 40, i32 42
   ret i32 %3
 }
 

test/Transforms/InstCombine/select.ll

entry:
   %tmp = load i8*, i8** %x1
   store i8* %tmp, i8** %y1
   %p = select i1 %flag, i128* %x2, i128* %y
   %v = load i128, i128* %p
   ret i128 %v
 }
 
 define i32 @test_select_select0(i32 %a, i32 %r0, i32 %r1, i32 %v1, i32 %v2) {
-  ; CHECK-LABEL: @test_select_select0(
-  ; CHECK: %[[C0:.*]] = icmp sge i32 %a, %v1
-  ; CHECK-NEXT: %[[C1:.*]] = icmp slt i32 %a, %v2
-  ; CHECK-NEXT: %[[C:.*]] = and i1 %[[C1]], %[[C0]]
-  ; CHECK-NEXT: %[[SEL:.*]] = select i1 %[[C]], i32 %r0, i32 %r1
-  ; CHECK-NEXT: ret i32 %[[SEL]]
+; CHECK-NEXT:    [[C0:%.*]] = icmp slt i32 %a, %v1
+; CHECK-NEXT:    [[S0:%.*]] = select i1 [[C0]], i32 %r1, i32 %r0
+; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 %a, %v2
+; CHECK-NEXT:    [[S1:%.*]] = select i1 [[C1]], i32 [[S0]], i32 %r1
+; CHECK-NEXT:    ret i32 [[S1]]
+;
   %c0 = icmp sge i32 %a, %v1
   %s0 = select i1 %c0, i32 %r0, i32 %r1
   %c1 = icmp slt i32 %a, %v2
   %s1 = select i1 %c1, i32 %s0, i32 %r1
   ret i32 %s1
 }
 
 define i32 @test_select_select1(i32 %a, i32 %r0, i32 %r1, i32 %v1, i32 %v2) {
-  ; CHECK-LABEL: @test_select_select1(
-  ; CHECK: %[[C0:.*]] = icmp sge i32 %a, %v1
-  ; CHECK-NEXT: %[[C1:.*]] = icmp slt i32 %a, %v2
-  ; CHECK-NEXT: %[[C:.*]] = or i1 %[[C1]], %[[C0]]
-  ; CHECK-NEXT: %[[SEL:.*]] = select i1 %[[C]], i32 %r0, i32 %r1
-  ; CHECK-NEXT: ret i32 %[[SEL]]
+; CHECK-NEXT:    [[C0:%.*]] = icmp slt i32 %a, %v1
+; CHECK-NEXT:    [[S0:%.*]] = select i1 [[C0]], i32 %r1, i32 %r0
+; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 %a, %v2
+; CHECK-NEXT:    [[S1:%.*]] = select i1 [[C1]], i32 %r0, i32 [[S0]]
+; CHECK-NEXT:    ret i32 [[S1]]
+;
   %c0 = icmp sge i32 %a, %v1
   %s0 = select i1 %c0, i32 %r0, i32 %r1
   %c1 = icmp slt i32 %a, %v2
   %s1 = select i1 %c1, i32 %r0, i32 %s0
   ret i32 %s1
 }
 
 define i32 @PR23757(i32 %x) {

test/Transforms/LoopVectorize/if-conversion.ll

 ;      k = k * 5 + 3;
 ;
 ;    a[i] = k;  <---- K is a phi node that becomes vector-select.
 ;  }
 ;}
 
 ;CHECK-LABEL: @function0(
 ;CHECK: load <4 x i32>
-;CHECK: icmp sle <4 x i32>
+;CHECK: icmp sgt <4 x i32>
 ;CHECK: mul <4 x i32>
 ;CHECK: add <4 x i32>
 ;CHECK: select <4 x i1>
 ;CHECK: ret i32
 define i32 @function0(i32* nocapture %a, i32* nocapture %b, i32 %start, i32 %end) nounwind uwtable ssp {
 entry:
   %cmp16 = icmp slt i32 %start, %end
   br i1 %cmp16, label %for.body.lr.ph, label %for.end

test/Transforms/LoopVectorize/minmax_reduction.ll

 
 for.end:
   ret i32 %max.red.0
 }
 
 ; SGE -> SLT
 ; Turn this into a min reduction (select inputs are reversed).
 ; CHECK-LABEL: @sge_min_red(
-; CHECK: icmp sge <2 x i32>
+; CHECK: icmp slt <2 x i32>
 ; CHECK: select <2 x i1>
 ; CHECK: middle.block
 ; CHECK: icmp slt <2 x i32>
 ; CHECK: select i1
 
 define i32 @sge_min_red(i32 %max) {
 entry:
   br label %for.body

 
 for.end:
   ret i32 %max.red.0
 }
 
 ; SLE -> SGT
 ; Turn this into a max reduction (select inputs are reversed).
 ; CHECK-LABEL: @sle_min_red(
-; CHECK: icmp sle <2 x i32>
+; CHECK: icmp sgt <2 x i32>
 ; CHECK: select <2 x i1>
 ; CHECK: middle.block
 ; CHECK: icmp sgt <2 x i32>
 ; CHECK: select i1
 
 define i32 @sle_min_red(i32 %max) {
 entry:
   br label %for.body

 
 for.end:
   ret i32 %max.red.0
 }
 
 ; UGE -> ULT
 ; Turn this into a min reduction (select inputs are reversed).
 ; CHECK-LABEL: @uge_min_red(
-; CHECK: icmp uge <2 x i32>
+; CHECK: icmp ult <2 x i32>
 ; CHECK: select <2 x i1>
 ; CHECK: middle.block
 ; CHECK: icmp ult <2 x i32>
 ; CHECK: select i1
 
 define i32 @uge_min_red(i32 %max) {
 entry:
   br label %for.body

 
 for.end:
   ret i32 %max.red.0
 }
 
 ; ULE -> UGT
 ; Turn this into a max reduction (select inputs are reversed).
 ; CHECK-LABEL: @ule_min_red(
-; CHECK: icmp ule <2 x i32>
+; CHECK: icmp ugt <2 x i32>
 ; CHECK: select <2 x i1>
 ; CHECK: middle.block
 ; CHECK: icmp ugt <2 x i32>
 ; CHECK: select i1
 
 define i32 @ule_min_red(i32 %max) {
 entry:
   br label %for.body