From 86c98145b268a0d10e062792f98bc8eea6b639b4 Mon Sep 17 00:00:00 2001
From: Andrew Trick <atrick@apple.com>
Date: Wed, 20 Jul 2011 05:32:06 +0000
Subject: [PATCH] indvars: Added getInsertPointForUses to find a valid place to
 truncate the IV.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135568 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/IndVarSimplify.cpp      | 47 +++++++++++++------
 .../IndVarSimplify/no-iv-rewrite.ll           | 39 +++++++++++++++
 2 files changed, 71 insertions(+), 15 deletions(-)

diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index 3a2674875c7..50140d92598 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -216,6 +216,36 @@ bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) {
   return true;
 }
 
+/// Determine the insertion point for this user. By default, insert immediately
+/// before the user. SCEVExpander or LICM will hoist loop invariants out of the
+/// loop. For PHI nodes, there may be multiple uses, so compute the nearest
+/// common dominator for the incoming blocks.
+static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
+                                          DominatorTree *DT) {
+  PHINode *PHI = dyn_cast<PHINode>(User);
+  if (!PHI)
+    return User;
+
+  Instruction *InsertPt = 0;
+  for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
+    if (PHI->getIncomingValue(i) != Def)
+      continue;
+
+    BasicBlock *InsertBB = PHI->getIncomingBlock(i);
+    if (!InsertPt) {
+      InsertPt = InsertBB->getTerminator();
+      continue;
+    }
+    InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
+    InsertPt = InsertBB->getTerminator();
+  }
+  assert(InsertPt && "Missing phi operand");
+  assert(!isa<Instruction>(Def) ||
+         DT->dominates(cast<Instruction>(Def), InsertPt) &&
+         "def does not dominate all uses");
+  return InsertPt;
+}
+
 //===----------------------------------------------------------------------===//
 // RewriteNonIntegerIVs and helpers. Prefer integer IVs.
 //===----------------------------------------------------------------------===//
@@ -697,18 +727,7 @@ void IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) {
     // hoist loop invariants out of the loop. For PHI nodes, there may be
     // multiple uses, so compute the nearest common dominator for the
     // incoming blocks.
-    Instruction *InsertPt = User;
-    if (PHINode *PHI = dyn_cast<PHINode>(InsertPt))
-      for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
-        if (PHI->getIncomingValue(i) == Op) {
-          if (InsertPt == User)
-            InsertPt = PHI->getIncomingBlock(i)->getTerminator();
-          else
-            InsertPt =
-              DT->findNearestCommonDominator(InsertPt->getParent(),
-                                             PHI->getIncomingBlock(i))
-                    ->getTerminator();
-        }
+    Instruction *InsertPt = getInsertPointForUses(User, Op, DT);
 
     // Now expand it into actual Instructions and patch it into place.
     Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt);
@@ -1023,9 +1042,7 @@ Instruction *WidenIV::WidenIVUse(NarrowIVDefUse DU) {
     // This user does not evaluate to a recurence 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.
-    Use *U = std::find(DU.NarrowUse->op_begin(), DU.NarrowUse->op_end(),
-                       DU.NarrowDef);
-    IRBuilder<> Builder(*U);
+    IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT));
     Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
     DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
     return 0;
diff --git a/test/Transforms/IndVarSimplify/no-iv-rewrite.ll b/test/Transforms/IndVarSimplify/no-iv-rewrite.ll
index a6073c2f8d3..eb8cef66c69 100644
--- a/test/Transforms/IndVarSimplify/no-iv-rewrite.ll
+++ b/test/Transforms/IndVarSimplify/no-iv-rewrite.ll
@@ -350,3 +350,42 @@ latch:                         ; preds = %for.inc50.i
 exit:
   ret void
 }
+
+; Test a widened IV that is used by a phi on different paths within the loop.
+;
+; CHECK: for.body:
+; CHECK: phi i64
+; CHECK: trunc i64
+; CHECK: if.then:
+; CHECK: for.inc:
+; CHECK: phi i32
+; CHECK: for.end:
+define void @phiUsesTrunc() nounwind {
+entry:
+  br i1 undef, label %for.body, label %for.end
+
+for.body:
+  %iv = phi i32 [ %inc, %for.inc ], [ 1, %entry ]
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  br i1 undef, label %if.then33, label %for.inc
+
+if.then33:
+  br label %for.inc
+
+if.else:
+  br i1 undef, label %if.then97, label %for.inc
+
+if.then97:
+  %idxprom100 = sext i32 %iv to i64
+  br label %for.inc
+
+for.inc:
+  %kmin.1 = phi i32 [ %iv, %if.then33 ], [ 0, %if.then ], [ %iv, %if.then97 ], [ 0, %if.else ]
+  %inc = add nsw i32 %iv, 1
+  br i1 undef, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
-- 
2.34.1