[SimplifyIndVars] Eliminate redundant truncs

[mkazantsev]

Summary

This patch adds logic to deal with the following constructions:

%iv = phi i64 ...
%trunc = trunc i64 %iv to i32
%cmp = icmp <pred> i32 %trunc, %invariant

Replacing it with

%iv = phi i64 ...
%cmp = icmp <pred> i64 %iv, sext/zext(%invariant)

In case if it is legal. Specifically, if %iv has signed comparison users, it is
required that sext(trunc(%iv)) == %iv, and if it has unsigned comparison
uses then we require zext(trunc(%iv)) == %iv. The current implementation
bails if %trunc has other uses than icmp, but in theory we can handle more
cases here (e.g. if the user of trunc is bitcast).

[reames]

lib/Transforms/Utils/SimplifyIndVar.cpp

514 ↗

(On Diff #150450)

This appears to be treating eq/ne as unsigned? Is that intentional? If so, probably worth a comment.

580 ↗

(On Diff #150450)

I'm missing something. Why do this via a new Trunc specific routine that has to look at users instead of just looking at the icmp directly? We do end up processing it don't we?

[mkazantsev]

lib/Transforms/Utils/SimplifyIndVar.cpp

514 ↗

(On Diff #150450)

Yes it is, we prefer zext over sext for canonicalization needs in case if there is no difference, as well as we prefer unsigned comparison over signed.

580 ↗

(On Diff #150450)

No, we never process this icmp(trunc(iv), constant).

[mkazantsev]

lib/Transforms/Utils/SimplifyIndVar.cpp

580 ↗

(On Diff #150450)

Clarification: the analysis stops at this point.

CastInst *Cast = dyn_cast<CastInst>(UseInst);
if (V && Cast) {
  V->visitCast(Cast);
  continue;
}

We don't push its users here. Not sure if we should.

[mkazantsev]

lib/Transforms/Utils/SimplifyIndVar.cpp

514 ↗

(On Diff #150450)

We can be smarter here.

[reames]

LGTM w/comments addressed before landing.

lib/Transforms/Utils/SimplifyIndVar.cpp

523 ↗

(On Diff #151108)

Naming wise, including Legal is bit confusing. Maybe DoesSExtCollapse or IsSExtPrpfitable?

530 ↗

(On Diff #151108)

Again, legal here is odd since as you say at the top, it's always legal to extend both sides.

555 ↗

(On Diff #151108)

I think you're better off placing these in the loop and then letting existing code hoist. Specifically, this code hoists about a possible condition in the predecessor (i.e. when it's not a preheader) and while that's legal, it might not be always profitable.

You can handle the simple cases canonically by placing in the loop and calling L->makeLoopInvariant(I) on them.

574 ↗

(On Diff #151108)

This is fine for the moment, but I want to note a couple of possible follow-ups:

1. We could update signed users even if we can't updated unsigned users or vice versa.
2. We could allow unrelated users.
3. If we encounter a non-canonical signed compare (i.e. one which could be represented as a unsigned compare), maybe we should emit the zext form directly?

These are explicitly out of scope for this patch.

[reames]

Thinking about this further, I see another opportunity for a follow on improvement, sketched below in comments.

test/Transforms/IndVarSimplify/eliminate-trunc.ll

157 ↗

(On Diff #151108)

I think the same basic logic as sketched for the other LFTR problem works here as well. Just with a [SINT_MIN, SINT_MAX-1] initial range for IV.

242 ↗

(On Diff #151108)

I think this case is actually something missing in SCEV. Let me walk through the logic by which we should be able to handle this.
IV is known to be [0, UINT32_MAX-1] inclusive - since it must be less than some value %n and the trunc doesn't change behavior before that point.
Thus, IV + 1 is known to not nuw wrap in the 32 bit domain.
Thus, trunc(IV+1) doesn't loose any bits.
Thus zext(trunc(IV+1)) == IV+1.

I think we're probably missing a range check somewhere inside the getZeroExt routine.

Note this logic only works for strict less than. Doing it for ule wouldn't work.

[mkazantsev]

lib/Transforms/Utils/SimplifyIndVar.cpp

555 ↗

(On Diff #151108)

Ok, let us follow "don't make worse" strategy and insert new comparisons in location of old ones.

572 ↗

(On Diff #151108)

We should not erase instructions here. It should be added to DeadInsts instead. Potential memory corruption (I don't have such test, though).

574 ↗

(On Diff #151108)

Ok, I will add a comment on that.

[mkazantsev]

test/Transforms/IndVarSimplify/eliminate-trunc.ll

242 ↗

(On Diff #151108)

We are not missing anything. narrow.iv gets removed by our transform. But LFTR manages to insert it back when replacing ult with ne. It is non-profitable behavior in LFTR.

llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp

public:
     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
 
     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
 
     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
     bool replaceIVUserWithLoopInvariant(Instruction *UseInst);
 
     bool eliminateOverflowIntrinsic(CallInst *CI);
+    bool eliminateTrunc(TruncInst *TI);
     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
     bool makeIVComparisonInvariant(ICmpInst *ICmp, Value *IVOperand);
     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
     void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
                              bool IsSigned);
     void replaceRemWithNumerator(BinaryOperator *Rem);
     void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
     void replaceSRemWithURem(BinaryOperator *Rem);
for (auto *EVI : ToDelete)
     EVI->eraseFromParent();
 
   if (CI->use_empty())
     CI->eraseFromParent();
 
   return true;
 }
 
+bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
+  // It is always legal to replace
+  //   icmp <pred> i32 trunc(iv), n
+  // with
+  //   icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
+  // Or with
+  //   icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
+  // Or with either of these if pred is an equality predicate.
+  //
+  // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
+  // every comparison which uses trunc, it means that we can replace each of
+  // them with comparison of iv against sext/zext(n). We no longer need trunc
+  // after that.
+  //
+  // TODO: Should we do this if we can widen *some* comparisons, but not all
+  // of them? Sometimes it is enough to enable other optimizations, but the
+  // trunc instruction will stay in the loop.
+  Value *IV = TI->getOperand(0);
+  Type *IVTy = IV->getType();
+  const SCEV *IVSCEV = SE->getSCEV(IV);
+  const SCEV *TISCEV = SE->getSCEV(TI);
+
+  // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
+  // get rid of trunc
+  bool DoesSExtCollapse = false;
+  bool DoesZExtCollapse = false;
+  if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
+    DoesSExtCollapse = true;
+  if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
+    DoesZExtCollapse = true;
+
+  // If neither sext nor zext does collapse, it is not profitable to do any
+  // transform. Bail.
+  if (!DoesSExtCollapse && !DoesZExtCollapse)
+    return false;
+
+  // Collect users of the trunc that look like comparisons against invariants.
+  // Bail if we find something different.
+  SmallVector<ICmpInst *, 4> ICmpUsers;
+  for (auto *U : TI->users()) {
+    if (ICmpInst *ICI = dyn_cast<ICmpInst>(U)) {
+      if (ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) {
+        assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
+        // If we cannot get rid of trunc, bail.
+        if (ICI->isSigned() && !DoesSExtCollapse)
+          return false;
+        if (ICI->isUnsigned() && !DoesZExtCollapse)
+          return false;
+        // For equality, either signed or unsigned works.
+        ICmpUsers.push_back(ICI);
+      } else
+        return false;
+    } else
+      return false;
+  }
+
+  // Replace all comparisons against trunc with comparisons against IV.
+  for (auto *ICI : ICmpUsers) {
+    auto *Op1 = ICI->getOperand(1);
+    Instruction *Ext = nullptr;
+    // For signed/unsigned predicate, replace the old comparison with comparison
+    // of immediate IV against sext/zext of the invariant argument. If we can
+    // use either sext or zext (i.e. we are dealing with equality predicate),
+    // then prefer zext as a more canonical form.
+    // TODO: If we see a signed comparison which can be turned into unsigned,
+    // we can do it here for canonicalization purposes.
+    if (ICI->isUnsigned() || (ICI->isEquality() && DoesZExtCollapse)) {
+      assert(DoesZExtCollapse && "Unprofitable zext?");
+      Ext = new ZExtInst(Op1, IVTy, "zext", ICI);
+    } else {
+      assert(DoesSExtCollapse && "Unprofitable sext?");
+      Ext = new SExtInst(Op1, IVTy, "sext", ICI);
+    }
+    bool Changed;
+    L->makeLoopInvariant(Ext, Changed);
+    (void)Changed;
+    ICmpInst *NewICI = new ICmpInst(ICI, ICI->getPredicate(), IV, Ext);
+    ICI->replaceAllUsesWith(NewICI);
+    DeadInsts.emplace_back(ICI);
+  }
+
+  // Trunc no longer needed.
+  TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
+  DeadInsts.emplace_back(TI);
+  return true;
+}
+
 /// Eliminate an operation that consumes a simple IV and has no observable
 /// side-effect given the range of IV values.  IVOperand is guaranteed SCEVable,
 /// but UseInst may not be.
 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
                                      Instruction *IVOperand) {
   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
     eliminateIVComparison(ICmp, IVOperand);
     return true;
   }
   if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
     bool IsSRem = Bin->getOpcode() == Instruction::SRem;
     if (IsSRem || Bin->getOpcode() == Instruction::URem) {
       simplifyIVRemainder(Bin, IVOperand, IsSRem);
       return true;
     }
 
     if (Bin->getOpcode() == Instruction::SDiv)
       return eliminateSDiv(Bin);
   }
 
   if (auto *CI = dyn_cast<CallInst>(UseInst))
     if (eliminateOverflowIntrinsic(CI))
       return true;
 
+  if (auto *TI = dyn_cast<TruncInst>(UseInst))
+    if (eliminateTrunc(TI))
+      return true;
+
   if (eliminateIdentitySCEV(UseInst, IVOperand))
     return true;
 
   return false;
 }
 
 static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) {
   if (auto *BB = L->getLoopPreheader())

llvm/trunk/test/Transforms/IndVarSimplify/ada-loops.ll

 ; RUN: opt < %s -indvars -S | FileCheck %s
 ;
 ; PR1301
 
 ; Do a bunch of analysis and prove that the loops can use an i32 trip
 ; count without casting.
 ;
 ; Note that all four functions should actually be converted to
 ; memset. However, this test case validates indvars behavior.  We
 ; don't check that phis are "folded together" because that is a job
 ; for loop strength reduction. But indvars must remove sext, zext, and add i8.
 ;
-; CHECK-NOT: {{sext|zext|add i8}}
 
 ; ModuleID = 'ada.bc'
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-n8:16:32"
 target triple = "i686-pc-linux-gnu"
 
+; CHECK-LABEL: @kinds__sbytezero
+; CHECK:         bb.thread:
+; CHECK:         sext
+; CHECK:         bb:
+; CHECK-NOT:     {{sext i8|zext i8|add i8|trunc}}
+
 define void @kinds__sbytezero([256 x i32]* nocapture %a) nounwind {
 bb.thread:
   %tmp46 = getelementptr [256 x i32], [256 x i32]* %a, i32 0, i32 0    ; <i32*> [#uses=1]
   store i32 0, i32* %tmp46
   br label %bb
 
 bb:   ; preds = %bb, %bb.thread
   %i.0.reg2mem.0 = phi i8 [ -128, %bb.thread ], [ %tmp8, %bb ]    ; <i8> [#uses=1]
   %tmp8 = add i8 %i.0.reg2mem.0, 1    ; <i8> [#uses=3]
   %tmp1 = sext i8 %tmp8 to i32    ; <i32> [#uses=1]
   %tmp3 = add i32 %tmp1, 128    ; <i32> [#uses=1]
   %tmp4 = getelementptr [256 x i32], [256 x i32]* %a, i32 0, i32 %tmp3    ; <i32*> [#uses=1]
   store i32 0, i32* %tmp4
   %0 = icmp eq i8 %tmp8, 127    ; <i1> [#uses=1]
   br i1 %0, label %return, label %bb
 
 return:   ; preds = %bb
   ret void
 }
 
+; CHECK-LABEL: @kinds__ubytezero
+
 define void @kinds__ubytezero([256 x i32]* nocapture %a) nounwind {
 bb.thread:
   %tmp35 = getelementptr [256 x i32], [256 x i32]* %a, i32 0, i32 0    ; <i32*> [#uses=1]
   store i32 0, i32* %tmp35
   br label %bb
 
 bb:   ; preds = %bb, %bb.thread
   %i.0.reg2mem.0 = phi i8 [ 0, %bb.thread ], [ %tmp7, %bb ]    ; <i8> [#uses=1]

llvm/trunk/test/Transforms/IndVarSimplify/eliminate-trunc.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -indvars -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; General case: without extra knowledge, trunc cannot be eliminated.
+define void @test_00(i64 %start, i32 %n) {
+;
+; CHECK-LABEL: @test_00(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
+; CHECK-NEXT:    [[NARROW_IV:%.*]] = trunc i64 [[IV]] to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[NARROW_IV]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ %start, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp slt i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+
+define void @test_01(i32 %n) {
+;
+; CHECK-LABEL: @test_01(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i64 [[IV]], [[SEXT]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp slt i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Max value at which we can eliminate trunc: SINT_MAX - 1.
+define void @test_02(i32 %n) {
+;
+; CHECK-LABEL: @test_02(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 2147483646, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i64 [[IV]], [[SEXT]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 2147483646, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp slt i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; If we start from SINT_MAX then the predicate is always false.
+define void @test_03(i32 %n) {
+;
+; CHECK-LABEL: @test_03(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [2147483647, %entry], [%iv.next, %loop]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp slt i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Minimum value at which we can apply the transform: SINT_MIN + 1.
+define void @test_04(i32 %n) {
+;
+; CHECK-LABEL: @test_04(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ -2147483647, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i64 [[IV]], [[SEXT]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ -2147483647, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp slt i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; FIXME: Harmful LFTR should be thrown away.
+define void @test_05(i32 %n) {
+;
+; CHECK-LABEL: @test_05(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ -2147483648, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ -2147483648, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp slt i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Trunc changes the actual value of the IV, so it is invalid to remove it: SINT_MIN - 1.
+define void @test_06(i32 %n) {
+;
+; CHECK-LABEL: @test_06(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ -2147483649, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[NARROW_IV:%.*]] = trunc i64 [[IV]] to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[NARROW_IV]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ -2147483649, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp slt i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; General case: without extra knowledge, trunc cannot be eliminated.
+define void @test_00_unsigned(i64 %start, i32 %n) {
+; CHECK-LABEL: @test_00_unsigned(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
+; CHECK-NEXT:    [[NARROW_IV:%.*]] = trunc i64 [[IV]] to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[NARROW_IV]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ %start, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp ult i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; FIXME: Harmful LFTR should be thrown away.
+define void @test_01_unsigned(i32 %n) {
+; CHECK-LABEL: @test_01_unsigned(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp ult i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Max value at which we can eliminate trunc: UINT_MAX - 1.
+define void @test_02_unsigned(i32 %n) {
+; CHECK-LABEL: @test_02_unsigned(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 4294967294, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i64 [[IV]], [[ZEXT]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 4294967294, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp ult i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; If we start from UINT_MAX then the predicate is always false.
+define void @test_03_unsigned(i32 %n) {
+; CHECK-LABEL: @test_03_unsigned(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 4294967295, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp ult i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Minimum value at which we can apply the transform: UINT_MIN.
+define void @test_04_unsigned(i32 %n) {
+; CHECK-LABEL: @test_04_unsigned(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp ult i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Start from 1.
+define void @test_05_unsigned(i32 %n) {
+; CHECK-LABEL: @test_05_unsigned(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i64 [[IV]], [[ZEXT]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 1, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp ult i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Trunc changes the actual value of the IV, so it is invalid to remove it: UINT_MIN - 1.
+define void @test_06_unsigned(i32 %n) {
+; CHECK-LABEL: @test_06_unsigned(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ -1, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[NARROW_IV:%.*]] = trunc i64 [[IV]] to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[NARROW_IV]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ -1, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp ult i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Do not eliminate trunc if it is used by something different from icmp.
+define void @test_07(i32* %p, i32 %n) {
+; CHECK-LABEL: @test_07(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[NARROW_IV:%.*]] = trunc i64 [[IV]] to i32
+; CHECK-NEXT:    store i32 [[NARROW_IV]], i32* [[P:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[NARROW_IV]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  store i32 %narrow.iv, i32* %p
+  %cmp = icmp slt i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Check that we can eliminate both signed and unsigned compare.
+define void @test_08(i32 %n) {
+; CHECK-LABEL: @test_08(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[N]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i64 [[IV]], [[SEXT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[IV]], [[ZEXT]]
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[TMP0]], [[TMP1]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 1, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp1 = icmp slt i32 %narrow.iv, %n
+  %cmp2 = icmp ult i32 %narrow.iv, %n
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Widen NE as unsigned.
+define void @test_09(i32 %n) {
+; CHECK-LABEL: @test_09(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ne i64 [[IV]], [[ZEXT]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %cmp = icmp ne i32 %narrow.iv, %n
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Widen NE as signed.
+define void @test_10(i32 %n) {
+; CHECK-LABEL: @test_10(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ -100, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ne i64 [[IV]], [[SEXT]]
+; CHECK-NEXT:    [[NEGCMP:%.*]] = icmp slt i64 [[IV]], -10
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[TMP0]], [[NEGCMP]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [ -100, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %trunccmp = icmp ne i32 %narrow.iv, %n
+  %negcmp = icmp slt i64 %iv, -10
+  %cmp = and i1 %trunccmp, %negcmp
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}

llvm/trunk/test/Transforms/IndVarSimplify/widen-loop-comp.ll

 
 define i32 @test10(i32 %v) {
 ; CHECK-LABEL: @test10(
  entry:
 ; CHECK-NOT: zext
   br label %loop
 
  loop:
+; CHECK: [[WIDE_V:%[a-z0-9]+]] = sext i32 %v to i64
 ; CHECK: loop:
 ; CHECK: %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ 0, %entry ]
 ; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 ; CHECK: [[MUL:%[a-z0-9]+]] = mul nsw i64 %indvars.iv, -1
-; CHECK: [[MUL_TRUNC:%[a-z0-9]+]] = trunc i64 [[MUL]] to i32
-; CHECK: [[CMP:%[a-z0-9]+]] = icmp eq i32 [[MUL_TRUNC]], %v
+; CHECK: [[CMP:%[a-z0-9]+]] = icmp eq i64 [[MUL]], [[WIDE_V]]
 ; CHECK: call void @consume.i1(i1 [[CMP]])
 
   %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ]
   %i.inc = add i32 %i, 1
   %iv = mul i32 %i, -1
   %cmp = icmp eq i32 %iv, %v
   call void @consume.i1(i1 %cmp)
   %be.cond = icmp slt i32 %i.inc, 11
   %ext = sext i32 %iv to i64
   call void @consume.i64(i64 %ext)
   br i1 %be.cond, label %loop, label %leave
 
  leave:
   ret i32 22
 }