[InstCombine] Fix PR17564: don't fold [zs]ext into phi.

[lebedev.ri]

Summary

Motivational case is highlighted in PR17564:

int f(int x) {
    return (x & 1) || (x & 2);
}

If the function return type is bool, then the IR is just and+icmp.
But if it is int, then it has select, and whatnot.
https://godbolt.org/g/uTJVVo

If one analyzes -print-after-all, thing appear to go bad when we fold zext into phi.
If we don't do that, then the behavior is the same as with i1, and PR17564 is fixed.

Also, the second part is needed, to get rid of select if possible,
e.g. https://godbolt.org/g/iAYRup, but that is another issue.

Now, i'm not quite sure whether *this* fix is correct?
Two other tests changed, but those changes do not look harmful?

Testing: ninja check-llvm

Fixes PR17564.

If this makes sense i'll commit test changes as NFC, and rebase.

[lebedev.ri]

D45108 will also solve PR17564, so if this is the wrong approach, it can be closed i suppose.

[spatel]

Avoiding instcombine folds is fragile. There's no guarantee that the IR isn't already in the form we're trying to avoid when we start instcombine, so we would fail to optimize in that case. Also, some of the tests show the benefit of the existing transform - we eliminate an instruction by changing the type of the phi.

I think we should solve this using something like D45108 instead, but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

[lebedev.ri]

In D45065#1054271, @spatel wrote:

Avoiding instcombine folds is fragile. There's no guarantee that the IR isn't already in the form we're trying to avoid when we start instcombine, so we would fail to optimize in that case.

Yes, i understand.

Also, some of the tests show the benefit of the existing transform - we eliminate an instruction by changing the type of the phi.

Uhm, which one specifically? As far as i can see, all tests here end up with the same instructions, just some are moved around.
But in @icmp_div2 we actually loose an instruction, and always return 1.

I think we should solve this using something like D45108 instead

but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

Hmm, right, somehow i missed those when looking where to work on D45108

So, i should close this?

[spatel]

In D45065#1054274, @lebedev.ri wrote:

In D45065#1054271, @spatel wrote:

Also, some of the tests show the benefit of the existing transform - we eliminate an instruction by changing the type of the phi.

Uhm, which one specifically? As far as i can see, all tests here end up with the same instructions, just some are moved around.

@zext_of_phi / @sext_of_phi - currently, in those tests we absorb the zext/sext into the phi removing an instruction, right?

But in @icmp_div2 we actually loose an instruction, and always return 1.

I think that's an interesting and independent case. It looks like we're losing information because of the order of the folds? Or maybe we're missing an instsimplify for phi with an undef operand?

Hmm, right, somehow i missed those when looking where to work on D45108

Yes, that code is a mess. Any preliminary cleanup patches to organize and comment it would be appreciated. I've been putting off refactoring decomposeBitTestICmp() to include the cases for ICMP_EQ / ICMP_NE, but this bug may be the needed motivation.

So, i should close this?

Yes.

[lebedev.ri]

Will continue in D45108

[lebedev.ri]

In D45065#1054271, @spatel wrote:

but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

Uhm, you know, i have added return nullptr; or return false; as the first statement in those functions, and even then those folds (@just_select, @zext_of_select, @sext_of_select) in this diff still happen.
So i'm not quite sure where they are happening...

[lebedev.ri]

In D45065#1056907, @lebedev.ri wrote:

In D45065#1054271, @spatel wrote:

but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

Uhm, you know, i have added return nullptr; or return false; as the first statement in those functions, and even then those folds (@just_select, @zext_of_select, @sext_of_select) in this diff still happen.
So i'm not quite sure where they are happening...

Right, of course, that is handled by https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/InstCombine/InstCombineSelect.cpp#L1418-L1452
Continuing to look...

lib/Transforms/InstCombine/InstCombineCasts.cpp

 }
 
 Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
   // If this zero extend is only used by a truncate, let the truncate be
   // eliminated before we try to optimize this zext.
   if (CI.hasOneUse() && isa<TruncInst>(CI.user_back()))
     return nullptr;
 
+  Value *Src = CI.getOperand(0);
+
+  // If this zero extend is of phi, keep it that way.
+  // This may allow further simplifications.
+  if (CI.hasOneUse() && isa<PHINode>(Src))
+    return nullptr;
+
   // If one of the common conversion will work, do it.
   if (Instruction *Result = commonCastTransforms(CI))
     return Result;
 
-  Value *Src = CI.getOperand(0);
   Type *SrcTy = Src->getType(), *DestTy = CI.getType();
 
   // Attempt to extend the entire input expression tree to the destination
   // type.   Only do this if the dest type is a simple type, don't convert the
   // expression tree to something weird like i93 unless the source is also
   // strange.
   unsigned BitsToClear;
   if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) &&

 }
 
 Instruction *InstCombiner::visitSExt(SExtInst &CI) {
   // If this sign extend is only used by a truncate, let the truncate be
   // eliminated before we try to optimize this sext.
   if (CI.hasOneUse() && isa<TruncInst>(CI.user_back()))
     return nullptr;
 
+  Value *Src = CI.getOperand(0);
+
+  // If this zero extend is of phi, keep it that way.
+  // This may allow further simplifications.
+  if (CI.hasOneUse() && isa<PHINode>(Src))
+    return nullptr;
+
   if (Instruction *I = commonCastTransforms(CI))
     return I;
 
-  Value *Src = CI.getOperand(0);
   Type *SrcTy = Src->getType(), *DestTy = CI.getType();
 
   // If we know that the value being extended is positive, we can use a zext
   // instead.
   KnownBits Known = computeKnownBits(Src, 0, &CI);
   if (Known.isNonNegative()) {
     Value *ZExt = Builder.CreateZExt(Src, DestTy);
     return replaceInstUsesWith(CI, ZExt);

test/Transforms/InstCombine/ext-of-select-of-bittest.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; https://bugs.llvm.org/show_bug.cgi?id=17564
+
+; If we thread zext/sext into phi, we won't be able to get rid of select
+; later on, so don't do that.
+
+define zeroext i1 @just_phi(i32) {
+; CHECK-LABEL: @just_phi(
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 1
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP7:%.*]]
+; CHECK:         [[TMP5:%.*]] = and i32 [[TMP0]], 4
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ne i32 [[TMP5]], 0
+; CHECK-NEXT:    br label [[TMP7]]
+; CHECK:         [[TMP8:%.*]] = phi i1 [ true, [[TMP1:%.*]] ], [ [[TMP6]], [[TMP4]] ]
+; CHECK-NEXT:    ret i1 [[TMP8]]
+;
+  %2 = and i32 %0, 1
+  %3 = icmp ne i32 %2, 0
+  br i1 %3, label %7, label %4
+
+  %5 = and i32 %0, 4
+  %6 = icmp ne i32 %5, 0
+  br label %7
+
+  %8 = phi i1 [ true, %1 ], [ %6, %4 ]
+  ret i1 %8
+}
+
+define i32 @zext_of_phi(i32) {
+; CHECK-LABEL: @zext_of_phi(
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 1
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP7:%.*]]
+; CHECK:         [[TMP5:%.*]] = and i32 [[TMP0]], 4
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ne i32 [[TMP5]], 0
+; CHECK-NEXT:    br label [[TMP7]]
+; CHECK:         [[TMP8:%.*]] = phi i1 [ true, [[TMP1:%.*]] ], [ [[TMP6]], [[TMP4]] ]
+; CHECK-NEXT:    [[TMP9:%.*]] = zext i1 [[TMP8]] to i32
+; CHECK-NEXT:    ret i32 [[TMP9]]
+;
+  %2 = and i32 %0, 1
+  %3 = icmp ne i32 %2, 0
+  br i1 %3, label %7, label %4
+
+  %5 = and i32 %0, 4
+  %6 = icmp ne i32 %5, 0
+  br label %7
+
+  %8 = phi i1 [ true, %1 ], [ %6, %4 ]
+  %9 = zext i1 %8 to i32
+  ret i32 %9
+}
+
+define i32 @sext_of_phi(i32) {
+; CHECK-LABEL: @sext_of_phi(
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 1
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP7:%.*]]
+; CHECK:         [[TMP5:%.*]] = and i32 [[TMP0]], 4
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ne i32 [[TMP5]], 0
+; CHECK-NEXT:    br label [[TMP7]]
+; CHECK:         [[TMP8:%.*]] = phi i1 [ true, [[TMP1:%.*]] ], [ [[TMP6]], [[TMP4]] ]
+; CHECK-NEXT:    [[TMP9:%.*]] = sext i1 [[TMP8]] to i32
+; CHECK-NEXT:    ret i32 [[TMP9]]
+;
+  %2 = and i32 %0, 1
+  %3 = icmp ne i32 %2, 0
+  br i1 %3, label %7, label %4
+
+  %5 = and i32 %0, 4
+  %6 = icmp ne i32 %5, 0
+  br label %7
+
+  %8 = phi i1 [ true, %1 ], [ %6, %4 ]
+  %9 = sext i1 %8 to i32
+  ret i32 %9
+}
+
+; After instcombine those ^ are transformed into these \/,
+; which are then simplified into icmp.
+
+define zeroext i1 @just_select(i32) {
+; CHECK-LABEL: @just_select(
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 5
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
+;
+  %2 = and i32 %0, 1
+  %3 = icmp eq i32 %2, 0
+  %4 = and i32 %0, 4
+  %5 = icmp ne i32 %4, 0
+  %6 = select i1 %3, i1 %5, i1 true
+  ret i1 %6
+}
+
+define i32 @zext_of_select(i32) {
+; CHECK-LABEL: @zext_of_select(
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 5
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP4:%.*]] = zext i1 [[TMP3]] to i32
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+  %2 = and i32 %0, 1
+  %3 = icmp eq i32 %2, 0
+  %4 = and i32 %0, 4
+  %5 = icmp ne i32 %4, 0
+  %6 = select i1 %3, i1 %5, i1 true
+  %7 = zext i1 %6 to i32
+  ret i32 %7
+}
+
+
+define i32 @sext_of_select(i32) {
+; CHECK-LABEL: @sext_of_select(
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 5
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP4:%.*]] = sext i1 [[TMP3]] to i32
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+  %2 = and i32 %0, 1
+  %3 = icmp eq i32 %2, 0
+  %4 = and i32 %0, 4
+  %5 = icmp ne i32 %4, 0
+  %6 = select i1 %3, i1 %5, i1 true
+  %7 = sext i1 %6 to i32
+  ret i32 %7
+}

test/Transforms/InstCombine/icmp-div-constant.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; PR30281 - https://llvm.org/bugs/show_bug.cgi?id=30281
 
 ; All of these tests contain foldable division-by-constant instructions, but we
 ; can't assert that those folds have occurred before we process the later icmp.
 
 define i32 @icmp_div(i16 %a, i16 %c) {
 ; CHECK-LABEL: @icmp_div(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 %a, 0
-; CHECK-NEXT:    br i1 [[TOBOOL]], label %then, label %exit
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 [[A:%.*]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[THEN:%.*]], label [[EXIT:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[NOT_CMP:%.*]] = icmp eq i16 %c, 0
-; CHECK-NEXT:    [[PHITMP1:%.*]] = sext i1 [[NOT_CMP]] to i32
-; CHECK-NEXT:    br label %exit
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[C:%.*]], 0
+; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ -1, %entry ], [ [[PHITMP1]], %then ]
-; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[CMP]], [[THEN]] ]
+; CHECK-NEXT:    [[ADD:%.*]] = sext i1 [[PHI]] to i32
+; CHECK-NEXT:    ret i32 [[ADD]]
 ;
 entry:
   %tobool = icmp eq i16 %a, 0
   br i1 %tobool, label %then, label %exit
 
 then:
   %div = sdiv i16 %c, -1
   %cmp = icmp ne i16 %div, 0
   br label %exit
 
 exit:
   %phi = phi i1 [ false, %entry ], [ %cmp, %then ]
   %zext = zext i1 %phi to i32
   %add = add nsw i32 %zext, -1
   ret i32 %add
 }
 
 define i32 @icmp_div2(i16 %a, i16 %c) {
 ; CHECK-LABEL: @icmp_div2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 %a, 0
-; CHECK-NEXT:    br i1 [[TOBOOL]], label %then, label %exit
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 [[A:%.*]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[THEN:%.*]], label [[EXIT:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    br label %exit
+; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ -1, %entry ], [ 0, %then ]
-; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK-NEXT:    ret i32 -1
 ;
 entry:
   %tobool = icmp eq i16 %a, 0
   br i1 %tobool, label %then, label %exit
 
 then:
   %div = sdiv i16 %c, 0
   %cmp = icmp ne i16 %div, 0
   br label %exit
 
 exit:
   %phi = phi i1 [ false, %entry ], [ %cmp, %then ]
   %zext = zext i1 %phi to i32
   %add = add nsw i32 %zext, -1
   ret i32 %add
 }
 
 define i32 @icmp_div3(i16 %a, i16 %c) {
 ; CHECK-LABEL: @icmp_div3(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 %a, 0
-; CHECK-NEXT:    br i1 [[TOBOOL]], label %then, label %exit
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 [[A:%.*]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[THEN:%.*]], label [[EXIT:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[NOT_CMP:%.*]] = icmp eq i16 %c, 0
-; CHECK-NEXT:    [[PHITMP1:%.*]] = sext i1 [[NOT_CMP]] to i32
-; CHECK-NEXT:    br label %exit
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[C:%.*]], 0
+; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ -1, %entry ], [ [[PHITMP1]], %then ]
-; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[CMP]], [[THEN]] ]
+; CHECK-NEXT:    [[ADD:%.*]] = sext i1 [[PHI]] to i32
+; CHECK-NEXT:    ret i32 [[ADD]]
 ;
 entry:
   %tobool = icmp eq i16 %a, 0
   br i1 %tobool, label %then, label %exit
 
 then:
   %div = sdiv i16 %c, 1
   %cmp = icmp ne i16 %div, 0

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

 ; CHECK-NEXT:    [[MUL3:%.*]] = mul nuw nsw i64 [[CONV]], [[CONV2]]
 ; CHECK-NEXT:    [[CONV6:%.*]] = and i64 [[MUL3]], 4294967295
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[CONV6]], [[MUL3]]
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label [[LOR_RHS:%.*]], label [[LOR_END:%.*]]
 ; CHECK:       lor.rhs:
 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[MUL3]], [[TMP2]]
 ; CHECK-NEXT:    [[CONV4:%.*]] = trunc i64 [[AND]] to i32
 ; CHECK-NEXT:    [[TOBOOL7:%.*]] = icmp eq i32 [[CONV4]], 0
-; CHECK-NEXT:    [[PHITMP:%.*]] = zext i1 [[TOBOOL7]] to i32
 ; CHECK-NEXT:    br label [[LOR_END]]
 ; CHECK:       lor.end:
-; CHECK-NEXT:    [[TMP3:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[PHITMP]], [[LOR_RHS]] ]
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[TOBOOL7]], [[LOR_RHS]] ]
+; CHECK-NEXT:    [[CONV8:%.*]] = zext i1 [[TMP3]] to i32
+; CHECK-NEXT:    ret i32 [[CONV8]]
 ;
 entry:
   %conv = zext i32 %0 to i64
   %conv1 = sext i8 %1 to i32
   %mul = mul i32 %conv1, 1945964878
   %sh_prom = trunc i64 %2 to i32
   %shr = lshr i32 %mul, %sh_prom
   %conv2 = zext i32 %shr to i64