lib/Transforms/Scalar/IndVarSimplify.cpp

   1 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Guarantees that all loops with identifiable, linear, induction variables will
  11 // be transformed to have a single, canonical, induction variable.  After this
  12 // pass runs, it guarantees the the first PHI node of the header block in the
  13 // loop is the canonical induction variable if there is one.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/Analysis/InductionVariable.h"
  19 #include "llvm/Analysis/LoopInfo.h"
  20 #include "llvm/iPHINode.h"
  21 #include "llvm/iOther.h"
  22 #include "llvm/Type.h"
  23 #include "llvm/Constants.h"
  24 #include "llvm/Support/CFG.h"
  25 #include "Support/Debug.h"
  26 #include "Support/Statistic.h"
  27 #include "Support/STLExtras.h"
  28
  29 namespace {
  30   Statistic<> NumRemoved ("indvars", "Number of aux indvars removed");
  31   Statistic<> NumInserted("indvars", "Number of canonical indvars added");
  32 }
  33
  34 // InsertCast - Cast Val to Ty, setting a useful name on the cast if Val has a
  35 // name...
  36 //
  37 static Instruction *InsertCast(Value *Val, const Type *Ty,
  38                                Instruction *InsertBefore) {
  39   return new CastInst(Val, Ty, Val->getName()+"-casted", InsertBefore);
  40 }
  41
  42 static bool TransformLoop(LoopInfo *Loops, Loop *Loop) {
  43   // Transform all subloops before this loop...
  44   bool Changed = reduce_apply_bool(Loop->getSubLoops().begin(),
  45                                    Loop->getSubLoops().end(),
  46                               std::bind1st(std::ptr_fun(TransformLoop), Loops));
  47   // Get the header node for this loop.  All of the phi nodes that could be
  48   // induction variables must live in this basic block.
  49   //
  50   BasicBlock *Header = Loop->getHeader();
  51
  52   // Loop over all of the PHI nodes in the basic block, calculating the
  53   // induction variables that they represent... stuffing the induction variable
  54   // info into a vector...
  55   //
  56   std::vector<InductionVariable> IndVars;    // Induction variables for block
  57   BasicBlock::iterator AfterPHIIt = Header->begin();
  58   for (; PHINode *PN = dyn_cast<PHINode>(AfterPHIIt); ++AfterPHIIt)
  59     IndVars.push_back(InductionVariable(PN, Loops));
  60   // AfterPHIIt now points to first non-phi instruction...
  61
  62   // If there are no phi nodes in this basic block, there can't be indvars...
  63   if (IndVars.empty()) return Changed;
  64
  65   // Loop over the induction variables, looking for a canonical induction
  66   // variable, and checking to make sure they are not all unknown induction
  67   // variables.
  68   //
  69   bool FoundIndVars = false;
  70   InductionVariable *Canonical = 0;
  71   for (unsigned i = 0; i < IndVars.size(); ++i) {
  72     if (IndVars[i].InductionType == InductionVariable::Canonical &&
  73         !isa<PointerType>(IndVars[i].Phi->getType()))
  74       Canonical = &IndVars[i];
  75     if (IndVars[i].InductionType != InductionVariable::Unknown)
  76       FoundIndVars = true;
  77   }
  78
  79   // No induction variables, bail early... don't add a canonical indvar
  80   if (!FoundIndVars) return Changed;
  81
  82   // Okay, we want to convert other induction variables to use a canonical
  83   // indvar.  If we don't have one, add one now...
  84   if (!Canonical) {
  85     // Create the PHI node for the new induction variable, and insert the phi
  86     // node at the start of the PHI nodes...
  87     PHINode *PN = new PHINode(Type::UIntTy, "cann-indvar", Header->begin());
  88
  89     // Create the increment instruction to add one to the counter...
  90     Instruction *Add = BinaryOperator::create(Instruction::Add, PN,
  91                                               ConstantUInt::get(Type::UIntTy,1),
  92                                               "add1-indvar", AfterPHIIt);
  93
  94     // Figure out which block is incoming and which is the backedge for the loop
  95     BasicBlock *Incoming, *BackEdgeBlock;
  96     pred_iterator PI = pred_begin(Header);
  97     assert(PI != pred_end(Header) && "Loop headers should have 2 preds!");
  98     if (Loop->contains(*PI)) {  // First pred is back edge...
  99       BackEdgeBlock = *PI++;
 100       Incoming      = *PI++;
 101     } else {
 102       Incoming      = *PI++;
 103       BackEdgeBlock = *PI++;
 104     }
 105     assert(PI == pred_end(Header) && "Loop headers should have 2 preds!");
 106
 107     // Add incoming values for the PHI node...
 108     PN->addIncoming(Constant::getNullValue(Type::UIntTy), Incoming);
 109     PN->addIncoming(Add, BackEdgeBlock);
 110
 111     // Analyze the new induction variable...
 112     IndVars.push_back(InductionVariable(PN, Loops));
 113     assert(IndVars.back().InductionType == InductionVariable::Canonical &&
 114            "Just inserted canonical indvar that is not canonical!");
 115     Canonical = &IndVars.back();
 116     ++NumInserted;
 117     Changed = true;
 118   } else {
 119     // If we have a canonical induction variable, make sure that it is the first
 120     // one in the basic block.
 121     if (&Header->front() != Canonical->Phi)
 122       Header->getInstList().splice(Header->begin(), Header->getInstList(),
 123                                    Canonical->Phi);
 124   }
 125
 126   DEBUG(std::cerr << "Induction variables:\n");
 127
 128   // Get the current loop iteration count, which is always the value of the
 129   // canonical phi node...
 130   //
 131   PHINode *IterCount = Canonical->Phi;
 132
 133   // Loop through and replace all of the auxiliary induction variables with
 134   // references to the canonical induction variable...
 135   //
 136   for (unsigned i = 0; i < IndVars.size(); ++i) {
 137     InductionVariable *IV = &IndVars[i];
 138
 139     DEBUG(IV->print(std::cerr));
 140
 141     // Don't do math with pointers...
 142     const Type *IVTy = IV->Phi->getType();
 143     if (isa<PointerType>(IVTy)) IVTy = Type::ULongTy;
 144
 145     // Don't modify the canonical indvar or unrecognized indvars...
 146     if (IV != Canonical && IV->InductionType != InductionVariable::Unknown) {
 147       Instruction *Val = IterCount;
 148       if (!isa<ConstantInt>(IV->Step) ||   // If the step != 1
 149           !cast<ConstantInt>(IV->Step)->equalsInt(1)) {
 150
 151         // If the types are not compatible, insert a cast now...
 152         if (Val->getType() != IVTy)
 153           Val = InsertCast(Val, IVTy, AfterPHIIt);
 154         if (IV->Step->getType() != IVTy)
 155           IV->Step = InsertCast(IV->Step, IVTy, AfterPHIIt);
 156
 157         Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step,
 158                                      IV->Phi->getName()+"-scale", AfterPHIIt);
 159       }
 160
 161       // If the start != 0
 162       if (IV->Start != Constant::getNullValue(IV->Start->getType())) {
 163         // If the types are not compatible, insert a cast now...
 164         if (Val->getType() != IVTy)
 165           Val = InsertCast(Val, IVTy, AfterPHIIt);
 166         if (IV->Start->getType() != IVTy)
 167           IV->Start = InsertCast(IV->Start, IVTy, AfterPHIIt);
 168
 169         // Insert the instruction after the phi nodes...
 170         Val = BinaryOperator::create(Instruction::Add, Val, IV->Start,
 171                                      IV->Phi->getName()+"-offset", AfterPHIIt);
 172       }
 173
 174       // If the PHI node has a different type than val is, insert a cast now...
 175       if (Val->getType() != IV->Phi->getType())
 176         Val = InsertCast(Val, IV->Phi->getType(), AfterPHIIt);
 177
 178       // Replace all uses of the old PHI node with the new computed value...
 179       IV->Phi->replaceAllUsesWith(Val);
 180
 181       // Move the PHI name to it's new equivalent value...
 182       std::string OldName = IV->Phi->getName();
 183       IV->Phi->setName("");
 184       Val->setName(OldName);
 185
 186       // Delete the old, now unused, phi node...
 187       Header->getInstList().erase(IV->Phi);
 188       Changed = true;
 189       ++NumRemoved;
 190     }
 191   }
 192
 193   return Changed;
 194 }
 195
 196 namespace {
 197   struct InductionVariableSimplify : public FunctionPass {
 198     virtual bool runOnFunction(Function &) {
 199       LoopInfo &LI = getAnalysis<LoopInfo>();
 200
 201       // Induction Variables live in the header nodes of loops
 202       return reduce_apply_bool(LI.getTopLevelLoops().begin(),
 203                                LI.getTopLevelLoops().end(),
 204                                std::bind1st(std::ptr_fun(TransformLoop), &LI));
 205     }
 206
 207     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 208       AU.addRequired<LoopInfo>();
 209       AU.addRequiredID(LoopSimplifyID);
 210       AU.setPreservesCFG();
 211     }
 212   };
 213   RegisterOpt<InductionVariableSimplify> X("indvars",
 214                                            "Canonicalize Induction Variables");
 215 }
 216
 217 Pass *createIndVarSimplifyPass() {
 218   return new InductionVariableSimplify();
 219 }