From 5d461d20aea308471f2a31b718a274bfee28b60c Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Wed, 21 Apr 2004 22:22:01 +0000
Subject: [PATCH] Implement a fixme.  The helps loops that have induction
 variables of different types in them.  Instead of creating an induction
 variable for all types, it creates a single induction variable and casts to
 the other sizes.  This generates this code:

no_exit:                ; preds = %entry, %no_exit
        %indvar = phi uint [ %indvar.next, %no_exit ], [ 0, %entry ]            ; <uint> [#uses=4]
***     %j.0.0 = cast uint %indvar to short             ; <short> [#uses=1]
        %indvar = cast uint %indvar to int              ; <int> [#uses=1]
        %tmp.7 = getelementptr short* %P, uint %indvar          ; <short*> [#uses=1]
        store short %j.0.0, short* %tmp.7
        %inc.0 = add int %indvar, 1             ; <int> [#uses=2]
        %tmp.2 = setlt int %inc.0, %N           ; <bool> [#uses=1]
        %indvar.next = add uint %indvar, 1              ; <uint> [#uses=1]
        br bool %tmp.2, label %no_exit, label %loopexit

instead of:

no_exit:                ; preds = %entry, %no_exit
        %indvar = phi ushort [ %indvar.next, %no_exit ], [ 0, %entry ]          ; <ushort> [#uses=2]
***     %indvar = phi uint [ %indvar.next, %no_exit ], [ 0, %entry ]            ; <uint> [#uses=3]
        %indvar = cast uint %indvar to int              ; <int> [#uses=1]
        %indvar = cast ushort %indvar to short          ; <short> [#uses=1]
        %tmp.7 = getelementptr short* %P, uint %indvar          ; <short*> [#uses=1]
        store short %indvar, short* %tmp.7
        %inc.0 = add int %indvar, 1             ; <int> [#uses=2]
        %tmp.2 = setlt int %inc.0, %N           ; <bool> [#uses=1]
        %indvar.next = add uint %indvar, 1
***     %indvar.next = add ushort %indvar, 1
        br bool %tmp.2, label %no_exit, label %loopexit

This is an improvement in register pressure, but probably doesn't happen that
often.

The more important fix will be to get rid of the redundant add.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13101 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/IndVarSimplify.cpp | 37 +++++++++++++-----------
 1 file changed, 20 insertions(+), 17 deletions(-)

diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index d375dcf4a91..b69e0a181e8 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -390,10 +390,8 @@ void IndVarSimplify::runOnLoop(Loop *L) {
   // Compute the type of the largest recurrence expression.
   //
   const Type *LargestType = IndVars[0].first->getType();
-  bool DifferingSizes = false;
   for (unsigned i = 1, e = IndVars.size(); i != e; ++i) {
     const Type *Ty = IndVars[i].first->getType();
-    DifferingSizes |= Ty->getPrimitiveSize() != LargestType->getPrimitiveSize();
     if (Ty->getPrimitiveSize() > LargestType->getPrimitiveSize())
       LargestType = Ty;
   }
@@ -411,30 +409,35 @@ void IndVarSimplify::runOnLoop(Loop *L) {
   if (!isa<SCEVCouldNotCompute>(IterationCount))
     LinearFunctionTestReplace(L, IterationCount, Rewriter);
 
-#if 0
-  // If there were induction variables of other sizes, cast the primary
-  // induction variable to the right size for them, avoiding the need for the
-  // code evaluation methods to insert induction variables of different sizes.
-  // FIXME!
-  if (DifferingSizes) {
-    std::map<unsigned, Value*> InsertedSizes;
-    for (unsigned i = 0, e = IndVars.size(); i != e; ++i) {
-    }    
-  }
-#endif
-
   // Now that we have a canonical induction variable, we can rewrite any
   // recurrences in terms of the induction variable.  Start with the auxillary
   // induction variables, and recursively rewrite any of their uses.
   BasicBlock::iterator InsertPt = Header->begin();
   while (isa<PHINode>(InsertPt)) ++InsertPt;
 
+  // If there were induction variables of other sizes, cast the primary
+  // induction variable to the right size for them, avoiding the need for the
+  // code evaluation methods to insert induction variables of different sizes.
+  std::map<unsigned, Value*> InsertedSizes;
+  InsertedSizes[LargestType->getPrimitiveSize()] = IndVar;
   while (!IndVars.empty()) {
     PHINode *PN = IndVars.back().first;
-    Value *NewVal = Rewriter.ExpandCodeFor(IndVars.back().second, InsertPt,
-                                           PN->getType());
+
+    const Type *Ty = PN->getType()->getUnsignedVersion();
+    Value *&IV = InsertedSizes[Ty->getPrimitiveSize()];
+    if (IV == 0) {
+      // Insert a new cast instruction, which will hold this recurrence.
+      std::string Name = PN->getName();
+      PN->setName("");
+      IV = new CastInst(IndVar, Ty, Name, InsertPt);
+    }
+
+    Value *V = IV;
+    if (PN->getType() != Ty)
+      V = new CastInst(V, PN->getType(), V->getName(), InsertPt);
+
     // Replace the old PHI Node with the inserted computation.
-    PN->replaceAllUsesWith(NewVal);
+    PN->replaceAllUsesWith(V);
     DeadInsts.insert(PN);
     IndVars.pop_back();
     ++NumRemoved;
-- 
2.34.1