[SimplifyIndVar] Avoid generating truncate instructions with non-hoisted Load operand.

[az]

Summary

One of the transformation done by the SimplyIndVar is to widen instructions, eliminate sign/zero extend instructions, and reduce the generation of truncate instructions when legal. Let's consider the following common C code fragment within a loop:
p = *(base + x*i); // i is the loop induction variable

If x is some load instruction that is hoisted outside the loop by LICM, then SimplyIndVar generates optimal code by not emitting any truncate instructions after widening. In case x is not hoisted, then the code generated is sub-optimal and it is mainly because SimplyIndVar relies on scalar evolution that can not handle loop variant expression. This patch handle the non-hoisted case and generates similar code to the hoisted case (see output of .ll file with and without patch).

The performance effect of redundant truncate and extend instructions can be big on strength reduction and on the backend when choosing the appropriate addressing mode.

No performance change on spec for ARM A72 but significant improvement on proprietary benchmark. Note that an alternative to this patch is to move SimplifyIndVar pass after PRE because PRE hoists more loop invariant code than LICM given that it uses a less conservative but expensive version of alias analysis. We opted not to make any change into pass ordering which can affect performance more than a local change.

[efriedma]

How does the code generation actually change on aarch64? As far as I can tell, you're basically just changing an "sxtw #2" to an "lsl #2"; does that save a uop on A72?

Note that an alternative to this patch is to move SimplifyIndVar pass after PRE because PRE hoists more loop invariant code than LICM given that it uses a less conservative but expensive version of alias analysis.

That might work in some cases, but not in general, so this is probably worth solving anyway...

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1408

Not sure the getExtendExpr helper is actually buying anything, given you have to check the extension kind anyway.

1460

It probably isn't a good idea to create a new multiply without erasing the old one.

llvm/test/Transforms/IndVarSimplify/iv-widen-elim-ext.ll

310

Please fix the testcase so this load isn't dead (to make the testcase less fragile).

[az]

In D49151#1158061, @efriedma wrote:

How does the code generation actually change on aarch64? As far as I can tell, you're basically just changing an "sxtw #2" to an "lsl #2"; does that save a uop on A72?

For the unit test case added in this patch, it does not show much in terms of performance. It only shows how SimplifyIndVar, without the patch, generates different code for similar multiply instructions (%mul = ... and %mul1= ...) that differ only in the first operand being hoisted outside the loop or not. For the hoisted case, it widens the multiply, inserts a sign extend outside the loop, and removes the sign extend instruction that comes after mul. In the non-hoisted case, it adds a truncate instruction and leaves the sign extend after the multiply. This patch tries to make SimplifyIndVar generates the same code for both cases especially that code for the hoisted case seems more efficient and cleaner to work with for passes that runs later. In order to see performance improvement due to this patch, let's consider this C Code:
struct info1 { int C };
struct info2 { int data };
void foo(struct info1* in, struct info2* out, int N, unsigned char* p) {

     int p0, p1, p2;
     for (int x = 1; x < N; ++x) {
       p0 = *(p + (x+1) * in->C);
       p1 = *(p + (x-1) * in->C);
       p2 = *(p + (x-2) * in->C);
       out[N + x].data = p0 - p1 + p2;
     }
return;

}
Without the Patch, here is the AArch64 assembly:

ldr     w9, [x0]
add     x11, x1, w2, sxtw #2
mov     w12, w2
mov     w8, wzr
add     x11, x11, #4            // =4
neg     w10, w9
sub     x12, x12, #1            // =1
lsl     w13, w9, #1

.LBB0_2: // %for.body

                                    // =>This Inner Loop Header: Depth=1
add     w15, w13, w8
ldrb    w14, [x3, w8, sxtw]
ldrb    w15, [x3, w15, sxtw]
add     w16, w10, w8
ldrb    w16, [x3, w16, sxtw]
add     w8, w8, w9
subs    x12, x12, #1            // =1
sub     w14, w15, w14
add     w14, w14, w16
str     w14, [x11], #4
b.ne    .LBB0_2

.LBB0_3: // %for.cond.cleanup

ret

With the patch, here is the AArch64 generated assembly

ldrsw   x8, [x0]
add     x10, x1, w2, sxtw #2
mov     w12, w2
sub     x12, x12, #1            // =1
add     x10, x10, #4            // =4
neg     x9, x8
lsl     x11, x8, #1

.LBB0_2: // %for.body

                                    // =>This Inner Loop Header: Depth=1
ldrb    w13, [x3, x11]
ldrb    w15, [x3]
ldrb    w14, [x3, x9]
add     x3, x3, x8
sub     w13, w13, w15
add     w13, w13, w14
subs    x12, x12, #1            // =1
str     w13, [x10], #4
b.ne    .LBB0_2

.LBB0_3: // %for.cond.cleanup

ret

There is a performance improvement with the patch due to the fact that most variables involved in computing the addresses of the ldrb instructions are computed outside the loop. The redundant truncate and sign extend instructions that goes into loop strength reduction and in particular induction rewrite does not allow this pass to generate the most efficient code.

[az]

[az]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1408

I took the code that does the non-scalar evolution legality check (opcode = {add..}, call to hasNoSignWrap(), etc.) and put it, as is, in a function called getExtendExpr that both existing code and patch code calls it. It may have a little bit of redundancy but I can rewrite it if needed by un-putting it in a function and replicate what I need in terms of legality check.

1460

Actually, this is cloning the use instruction and not removing it yet. The old instruction is removed by the defining instruction when we return up the call chain if it has no other use. This is my understanding of how things worked with widening the use. However, I am adding some code in the new revision to immediately remove the new instruction when not useful. I used to leave the instruction unused and hoping that it will be removed by dead code elimination.

[az]

Ping

[efriedma]

Your example doesn't really help make the case for this patch. The load in that test is actually loop-invariant; we just don't figure that out until after indvars transforms the induction variable. Probably LICM could be fixed to handle this case earlier. Then ultimately, the multiply goes away; the extra operation you're trying to get rid of is actually the sign-extension of a PHI node created by LSR. LSR and/or SCEV could probably be fixed so this produces an i64 PHI instead. Either of those fixes would be more straightforward and more obviously profitable.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1408

Okay, it's probably fine as-is.

1460

We need to make sure to avoid the situation where after this transform runs, there's an i32 multiply and an i64 multiply. It's possible IV rewriting could lead to this sort of situation anyway in certain edge cases, I guess (haven't looked too closely), but multiplies are relatively expensive, and i64 multiplies are more expensive than i32 multiplies.

Actually, more generally, we probably need to weigh the extra cost of the multiply; on multiple targets, an i64 multiply is substantially slower than an i32 multiply.

[az]

In D49151#1174443, @efriedma wrote:

Your example doesn't really help make the case for this patch. The load in that test is actually loop-invariant; we just don't figure that out until after indvars transforms the induction variable. Probably LICM could be fixed to handle this case earlier. Then ultimately, the multiply goes away; the extra operation you're trying to get rid of is actually the sign-extension of a PHI node created by LSR. LSR and/or SCEV could probably be fixed so this produces an i64 PHI instead. Either of those fixes would be more straightforward and more obviously profitable.

My example is a greatly simplified example of the actual benchmark but you are absolutely right on the suggestion that we should solve this problem in LICM. If we can do that, SimplifyIndVar would work with clean hoisted loads and LICM would be improved in general. That was my original approach too and a good portion of the work for this performance issue was spent on trying to improve LICM/AA. What I found out is that LICM uses a simple/fast but conservative Type-Based Alias Analysis (AliasSet). I would have to make major changes to that alias analysis to solve my problem and it is unlikely to have it accepted given the strong push back against adding too much complexity into AliasSet. Then, I also thought about making LICM use the more accurate but expansive MemDep alias analysis in a similar way that GVN based PRE uses it (Memdep gives good Alias Analysis info for my real benchmark). But given that the LICM pass is called numerous times, this would add substantial compile time. Given that I did not have an agreeable fix in LICM/AA, I went to the next best place to put a fix which is SimplifyIndVar. It is the next best place because 1) it is there where the truncate instruction and inefficient code is first generated, 2) it is an early pass and I prefer that we clean code early on instead of letting inefficient IR go through other passes, and 3) It makes the IndvarSimp widening optimization more solid because let's consider we have two similar C examples with the only difference being one with a Load inside the loop and the other with a Load outside the loop (LICM could not hoist because of real legality issue or because of limitation of licm such as my case). The widening generates quite different IRs for both cases even though the Load being outside or inside is irrelevant to widening itself. In other words, we want it to generate similar type of code for closely similar input IR.

[az]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1460

Good catch.
I updated the patch so that it does not generate two versions of the instructions, an i32 and i64 (for the example below a two versions of the multiply is a possibility). I have done so by making sure that the instruction in question is consumed by a s/z extend instruction to get a full benefit of widening and eliminate the extend instruction. Having said that, it is most likely the original code is suffering from the same issue of generating multiple version of the instructions. I will look at it post the patch.
As for the general idea of adding a cost model for the widening optimization, it is worth investigating it (may be along with the other optimizations within SimplifyIndVar in case they do not have a cost model). In case you are aware of such examples, please share but I think you have good point. We are transforming the code by widening and elimination of some instructions without checking on profitability.

[az]

Some cleaning and update to comments.

[sebpop]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1422

clang-format

1444

Variable names should start with a Capital letter.

1452

Rewrite like so:

if (!isa<SCEVSignExtendExpr>(ExtendOperExpr))
  return false;

1458

idem: use isa<> shorter format.

1493

Can you please remove all the unneeded parentheses?
Also I find it more clear if you first check for all cases that exit the loop with WideningUseful = false; break;

1497

There is a path on which we would transform the code in this rAUW stmt, and in a later iteration will fail in the else break clause.
Can we transform this loop such that we split the analysis phase from code generation part? Maybe by using a vector of the things to be replaced. The analysis part that may fail with return false; should be moved before // Generating a widening use instruction.
You can also split all the code gen part in a separate function that does not fail, and call it from below...

1603

... and call it from here.

if (analysisFails())
  return nullptr;
codeGenWiden();

[sebpop]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1603

this should be:

if (analysisSucceeds()) {
   codeGenWiden();
   return nullptr;
}

[az]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1493

Removed one. I tried to remove another one that should work fine based on C precedence rule, but I got some compiler warning. So, it is slightly better but still parentheses heavy.

1603

Done what you have in mind which is completely separate analysis from code Gen but I still kept them in the same function with clearly marked analysis phase and codegen phase mainly because they share code that may need to be re-executed if separated. I Can separate them into two functions if you still think that this small enhancement to widening need an analysis function and a code gen function.

[sebpop]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1469

Let's break this down into smaller statements that can be read with ease:
here is my suggestion

if (ExtKind == SignExtended) {
  for () {
    auto *User = ...;
    if (isa<SExtInst>(User) && User->getType() == WideType)
      continue;
    return false;
  }
} else { // ExtKind == ZeroExtended
  for () {
    auto *User = ...;
    if (isa<ZExtInst>(User) && User->getType() == WideType)
      continue;
    return false;
  }
}

1603

Let's split the function into two smaller ones.

[sebpop]

The patch looks good to me.
Please address the last two comments and then apply.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1468

Let's simplify the loop like so:

for () {
  ZExtInst *User = dyn_cast<ZExtInst>(U.getUser());
  if (!User || User->getType() != WideType)
    return false;
}

and the same for the signExtend loop.

1535

please remove return stmt.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

protected:
   WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
 
   const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
                               unsigned OpCode) const;
 
   Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter);
 
   bool widenLoopCompare(NarrowIVDefUse DU);
+  const SCEV * getExtendExpr(NarrowIVDefUse DU);
+  bool widenVariantLoadUse(NarrowIVDefUse DU);
 
   void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
 };
 
 } // end anonymous namespace
 
 /// Perform a quick domtree based check for loop invariance assuming that V is
 /// used within the loop. LoopInfo::isLoopInvariant() seems gratuitous for this
const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
   if (OpCode == Instruction::Sub)
     return SE->getMinusSCEV(LHS, RHS);
   if (OpCode == Instruction::Mul)
     return SE->getMulExpr(LHS, RHS);
 
   llvm_unreachable("Unsupported opcode.");
 }
 
+/// Get the SCEV Extend Expression of the other operand in the use instruction
+/// of DU (i.e. the one that is not defined in the defining instruction in DU).
+const SCEV * WidenIV::getExtendExpr(NarrowIVDefUse DU) {
+  Instruction *NarrowUse = DU.NarrowUse;
+  Instruction *NarrowDef = DU.NarrowDef;
+
+  // Handle the common case of add<nsw/nuw>
+  const unsigned OpCode = NarrowUse->getOpcode();
+  // Only Add/Sub/Mul instructions are supported.
+  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
+      OpCode != Instruction::Mul)
+    return nullptr;
+
+  // Check whether the other operand is the first or the second operand.
+  unsigned ExtendOperIdx = DU.NarrowUse->getOperand(0) == NarrowDef ? 1 : 0;
+  assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
+
+  const SCEV *ExtendOperExpr = nullptr;
+  const OverflowingBinaryOperator *OBO =
+    cast<OverflowingBinaryOperator>(NarrowUse);
+  ExtendKind ExtKind = getExtendKind(NarrowDef);
+  if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
+    ExtendOperExpr = SE->getSignExtendExpr(
+      SE->getSCEV(NarrowUse->getOperand(ExtendOperIdx)), WideType);
+  else if(ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
+    ExtendOperExpr = SE->getZeroExtendExpr(
+      SE->getSCEV(NarrowUse->getOperand(ExtendOperIdx)), WideType);
+  else
+    return nullptr;
+
+  return ExtendOperExpr;
+}
+
 /// No-wrap operations can transfer sign extension of their result to their
 /// operands. Generate the SCEV value for the widened operation without
 /// actually modifying the IR yet. If the expression after extending the
 /// operands is an AddRec for this loop, return the AddRec and the kind of
 /// extension used.
 WidenIV::WidenedRecTy WidenIV::getExtendedOperandRecurrence(NarrowIVDefUse DU) {
-  // Handle the common case of add<nsw/nuw>
-  const unsigned OpCode = DU.NarrowUse->getOpcode();
-  // Only Add/Sub/Mul instructions supported yet.
-  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
-      OpCode != Instruction::Mul)
+  const SCEV* ExtendOperExpr = getExtendExpr(DU);
+  if (!ExtendOperExpr)
     return {nullptr, Unknown};
 
+  const unsigned OpCode = DU.NarrowUse->getOpcode();
+
   // One operand (NarrowDef) has already been extended to WideDef. Now determine
   // if extending the other will lead to a recurrence.
   const unsigned ExtendOperIdx =
       DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
   assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
 
-  const SCEV *ExtendOperExpr = nullptr;
-  const OverflowingBinaryOperator *OBO =
-    cast<OverflowingBinaryOperator>(DU.NarrowUse);
   ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
-  if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
-    ExtendOperExpr = SE->getSignExtendExpr(
-      SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
-  else if(ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
-    ExtendOperExpr = SE->getZeroExtendExpr(
-      SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
-  else
-    return {nullptr, Unknown};
 
   // When creating this SCEV expr, don't apply the current operations NSW or NUW
   // flags. This instruction may be guarded by control flow that the no-wrap
   // behavior depends on. Non-control-equivalent instructions can be mapped to
   // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
   // semantics to those operations.
   const SCEV *lhs = SE->getSCEV(DU.WideDef);
   const SCEV *rhs = ExtendOperExpr;
bool WidenIV::widenLoopCompare(NarrowIVDefUse DU) {
   // Widen the other operand of the compare, if necessary.
   if (CastWidth < IVWidth) {
     Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
     DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
   }
   return true;
 }
 
+/// If the narrow use is an instruction whose two operands are the defining
+/// instruction of DU and a load instruction, then we have the following:
+/// if the load is hoisted outside the loop, then we do not reach this function
+/// as scalar evolution analysis works fine in widenIVUse with variables
+/// hoisted outside the loop and efficient code is subsequently generated by
+/// not emitting truncate instructions. But when the load is not hoisted
+/// (whether due to limitation in alias analysis or other), then scalar
+/// evolution can not proceed with loop variant values and inefficient code
+/// is generated. This function handles the non-hoisted load special case by
+/// making the optimization generate the same type of code for hoisted and
+/// non-hoisted load (widen use and eliminate sign extend instruction).
+/// This special case is important especially when the induction variables are
+/// affecting addressing mode in code generation.
+bool WidenIV::widenVariantLoadUse(NarrowIVDefUse DU) {
+  const SCEV* ExtendOperExpr = getExtendExpr(DU);
+  if (!ExtendOperExpr)
+    return false;
+
+  Instruction *NarrowUse = DU.NarrowUse;
+  Instruction *NarrowDef = DU.NarrowDef;
+  Instruction *WideDef = DU.WideDef;
+
+  // The operand that is not defined by NarrowDef of DU. Let's call it the
+  // other operand.
+  unsigned ExtendOperIdx = NarrowUse->getOperand(0) == NarrowDef ? 1 : 0;
+
+  // We are interested in the other operand being a load instruction.
+  // But, we should look into relaxing this restriction later on.
+  auto *I = dyn_cast<Instruction>(NarrowUse->getOperand(ExtendOperIdx));
+  if (I && I->getOpcode() != Instruction::Load)
+    return false;
+
+  // Verifying that Defining operand is an AddRec
+  const SCEV *op1 = SE->getSCEV(WideDef);
+  const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(op1);
+  if (!AddRecOp1 || AddRecOp1->getLoop() != L)
+    return false;
+  // Verifying that other operand is an Extend.
+  ExtendKind ExtKind = getExtendKind(NarrowDef);
+  if (ExtKind == SignExtended)
+  {
+    const SCEVSignExtendExpr *AddRecOp2 = dyn_cast<SCEVSignExtendExpr>(ExtendOperExpr);
+    if (!AddRecOp2)
+      return false;
+  }
+  else
+  {
+    const SCEVZeroExtendExpr *AddRecOp2 = dyn_cast<SCEVZeroExtendExpr>(ExtendOperExpr);
+    if (!AddRecOp2)
+      return false;
+  }
+
+  LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
+
+  // Generating a widening use instruction.
+  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
+                   ? WideDef
+                   : createExtendInst(NarrowUse->getOperand(0), WideType,
+                                      ExtKind, NarrowUse);
+  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
+                   ? WideDef
+                   : createExtendInst(NarrowUse->getOperand(1), WideType,
+                                      ExtKind, NarrowUse);
+
+  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
+  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
+                                        NarrowBO->getName());
+  IRBuilder<> Builder(NarrowUse);
+  Builder.Insert(WideBO);
+  WideBO->copyIRFlags(NarrowBO);
+
+  if (ExtKind == SignExtended)
+    ExtendKindMap[NarrowUse] = SignExtended;
+  else
+    ExtendKindMap[NarrowUse] = ZeroExtended;
+
+  // Check if widening the use eliminates sign/zero extend instructions.
+  bool WideningUseful = false;
+  for (Use &U : NarrowUse->uses()) {
+    auto *User = cast<Instruction>(U.getUser());
+
+    if (((isa<SExtInst>(User) && (getExtendKind(NarrowUse) == SignExtended)) ||
+        (isa<ZExtInst>(User) && (getExtendKind(NarrowUse) == ZeroExtended))) &&
+        (User->getType() == WideType)) {
+        LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User
+                          << " replaced by " << *WideBO << "\n");
+        ++NumElimExt;
+        User->replaceAllUsesWith(WideBO);
+        DeadInsts.emplace_back(User);
+        WideningUseful = true;
+      }
+      else {
+        WideningUseful = false;
+        break;
+      }
+  }
+
+  // In case the widened instruction is not comsumed by s/z extend instrunction
+  // and is hence not useful, we throw it away.
+  if (!WideningUseful) {
+    LLVM_DEBUG(dbgs() << "Widening use not useful: " << *WideBO << "\n");
+    DeadInsts.emplace_back(WideBO);
+  }
+  return WideningUseful;
+}
+
 /// Determine whether an individual user of the narrow IV can be widened. If so,
 /// return the wide clone of the user.
 Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
   assert(ExtendKindMap.count(DU.NarrowDef) &&
          "Should already know the kind of extension used to widen NarrowDef");
 
   // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
   if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
if (LI->getLoopFor(UsePhi->getParent()) != L) {
         UsePhi->replaceAllUsesWith(Trunc);
         DeadInsts.emplace_back(UsePhi);
         LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
                           << *WidePhi << "\n");
       }
       return nullptr;
     }
   }
 
   // This narrow use can be widened by a sext if it's non-negative or its narrow
   // def was widended by a sext. Same for zext.
   auto canWidenBySExt = [&]() {
     return DU.NeverNegative || getExtendKind(DU.NarrowDef) == SignExtended;
   };
   auto canWidenByZExt = [&]() {
     return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ZeroExtended;
   };
Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
 
   assert((WideAddRec.first == nullptr) == (WideAddRec.second == Unknown));
   if (!WideAddRec.first) {
     // If use is a loop condition, try to promote the condition instead of
     // truncating the IV first.
     if (widenLoopCompare(DU))
       return nullptr;
 
+    // We are here about to generate a truncate instruction because the scalar
+    // evolution expression computed earlier in WideAddRec.first does not
+    // indicate a polynomial induction expression. In that case, look at
+    // the operands of the use instruction to determine if we can still widen
+    // the use instead of truncating its operand.
+    if (widenVariantLoadUse(DU))
+      return nullptr;
+
     // This user does not evaluate to a recurrence after widening, so don't
     // follow it. Instead insert a Trunc to kill off the original use,
     // eventually isolating the original narrow IV so it can be removed.
     truncateIVUse(DU, DT, LI);
     return nullptr;
   }
   // Assume block terminators cannot evaluate to a recurrence. We can't to
   // insert a Trunc after a terminator if there happens to be a critical edge.

llvm/test/Transforms/IndVarSimplify/iv-widen-elim-ext.ll

 
 for.cond.for.end_crit_edge:                       ; preds = %for.inc
   br label %for.end
 
 for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
   %call = call i32 @dummy(i32* getelementptr inbounds ([100 x i32], [100 x i32]* @a, i32 0, i32 0), i32* getelementptr inbounds ([100 x i32], [100 x i32]* @b, i32 0, i32 0))
   ret i32 0
 }
+
+%struct.image = type {i32, i32}
+define i32 @foo4(%struct.image* %input, i32 %length, i32* %in) {
+entry:
+  %stride = getelementptr inbounds %struct.image, %struct.image* %input, i64 0, i32 1
+  %0 = load i32, i32* %stride, align 4
+  %cmp17 = icmp sgt i32 %length, 1
+  br i1 %cmp17, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:                                   ; preds = %entry
+  %channel = getelementptr inbounds %struct.image, %struct.image* %input, i64 0, i32 0
+  br label %for.body
+
+for.cond.cleanup.loopexit:                        ; preds = %for.body
+  %1 = phi i32 [ %6, %for.body ]
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
+  %2 = phi i32 [ 0, %entry ], [ %1, %for.cond.cleanup.loopexit ]
+  ret i32 %2
+
+; mul instruction below is widened instead of generating a truncate instruction for it
+; regardless if Load operand of mul is inside or outside the loop (we have both cases).
+; CHECK: for.body:
+; CHECK-NOT: trunc
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %x.018 = phi i32 [ 1, %for.body.lr.ph ], [ %add, %for.body ]
+  %add = add nuw nsw i32 %x.018, 1
+  %3 = load i32, i32* %channel, align 8
+  %mul = mul nsw i32 %3, %add
+  %idx.ext = sext i32 %mul to i64
+  %add.ptr = getelementptr inbounds i32, i32* %in, i64 %idx.ext
+  %4 = load i32, i32* %add.ptr, align 4
+  %mul1 = mul nsw i32 %0, %add
+  %idx.ext1 = sext i32 %mul1 to i64
+  %add.ptr1 = getelementptr inbounds i32, i32* %in, i64 %idx.ext1
+  %5 = load i32, i32* %add.ptr1, align 4
+  %6 = add i32 %4, %5
+  %cmp = icmp slt i32 %add, %length
+  br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit
+}
+
+
+define i32 @foo5(%struct.image* %input, i32 %length, i32* %in) {
+entry:
+  %stride = getelementptr inbounds %struct.image, %struct.image* %input, i64 0, i32 1
+  %0 = load i32, i32* %stride, align 4
+  %cmp17 = icmp sgt i32 %length, 1
+  br i1 %cmp17, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:                                   ; preds = %entry
+  %channel = getelementptr inbounds %struct.image, %struct.image* %input, i64 0, i32 0
+  br label %for.body
+
+for.cond.cleanup.loopexit:                        ; preds = %for.body
+  %1 = phi i32 [ %7, %for.body ]
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
+  %2 = phi i32 [ 0, %entry ], [ %1, %for.cond.cleanup.loopexit ]
+  ret i32 %2
+
+; This example is the same as above except that the first mul is used in two places 
+; and this may result in having two versions of the multiply: an i32 and i64 version.
+; In this case, keep the trucate instructions to avoid this redundancy. 
+; CHECK: for.body:
+; CHECK: trunc
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %x.018 = phi i32 [ 1, %for.body.lr.ph ], [ %add, %for.body ]
+  %add = add nuw nsw i32 %x.018, 1
+  %3 = load i32, i32* %channel, align 8
+  %mul = mul nsw i32 %3, %add
+  %idx.ext = sext i32 %mul to i64
+  %add.ptr = getelementptr inbounds i32, i32* %in, i64 %idx.ext
+  %4 = load i32, i32* %add.ptr, align 4
+  %mul1 = mul nsw i32 %0, %add
+  %idx.ext1 = sext i32 %mul1 to i64
+  %add.ptr1 = getelementptr inbounds i32, i32* %in, i64 %idx.ext1
+  %5 = load i32, i32* %add.ptr1, align 4
+  %6 = add i32 %4, %5
+  %7 = add i32 %6, %mul
+  %cmp = icmp slt i32 %add, %length
+  br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit
+}