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 #include <algorithm>
  29
  30 namespace llvm {
  31
  32 namespace {
  33   Statistic<> NumRemoved ("indvars", "Number of aux indvars removed");
  34   Statistic<> NumInserted("indvars", "Number of canonical indvars added");
  35 }
  36
  37 // InsertCast - Cast Val to Ty, setting a useful name on the cast if Val has a
  38 // name...
  39 //
  40 static Instruction *InsertCast(Value *Val, const Type *Ty,
  41                                Instruction *InsertBefore) {
  42   return new CastInst(Val, Ty, Val->getName()+"-casted", InsertBefore);
  43 }
  44
  45 static bool TransformLoop(LoopInfo *Loops, Loop *Loop) {
  46   // Transform all subloops before this loop...
  47   bool Changed = reduce_apply_bool(Loop->getSubLoops().begin(),
  48                                    Loop->getSubLoops().end(),
  49                               std::bind1st(std::ptr_fun(TransformLoop), Loops));
  50   // Get the header node for this loop.  All of the phi nodes that could be
  51   // induction variables must live in this basic block.
  52   //
  53   BasicBlock *Header = Loop->getHeader();
  54
  55   // Loop over all of the PHI nodes in the basic block, calculating the
  56   // induction variables that they represent... stuffing the induction variable
  57   // info into a vector...
  58   //
  59   std::vector<InductionVariable> IndVars;    // Induction variables for block
  60   BasicBlock::iterator AfterPHIIt = Header->begin();
  61   for (; PHINode *PN = dyn_cast<PHINode>(AfterPHIIt); ++AfterPHIIt)
  62     IndVars.push_back(InductionVariable(PN, Loops));
  63   // AfterPHIIt now points to first non-phi instruction...
  64
  65   // If there are no phi nodes in this basic block, there can't be indvars...
  66   if (IndVars.empty()) return Changed;
  67
  68   // Loop over the induction variables, looking for a canonical induction
  69   // variable, and checking to make sure they are not all unknown induction
  70   // variables.
  71   //
  72   bool FoundIndVars = false;
  73   InductionVariable *Canonical = 0;
  74   for (unsigned i = 0; i < IndVars.size(); ++i) {
  75     if (IndVars[i].InductionType == InductionVariable::Canonical &&
  76         !isa<PointerType>(IndVars[i].Phi->getType()))
  77       Canonical = &IndVars[i];
  78     if (IndVars[i].InductionType != InductionVariable::Unknown)
  79       FoundIndVars = true;
  80   }
  81
  82   // No induction variables, bail early... don't add a canonical indvar
  83   if (!FoundIndVars) return Changed;
  84
  85   // Okay, we want to convert other induction variables to use a canonical
  86   // indvar.  If we don't have one, add one now...
  87   if (!Canonical) {
  88     // Create the PHI node for the new induction variable, and insert the phi
  89     // node at the start of the PHI nodes...
  90     PHINode *PN = new PHINode(Type::UIntTy, "cann-indvar", Header->begin());
  91
  92     // Create the increment instruction to add one to the counter...
  93     Instruction *Add = BinaryOperator::create(Instruction::Add, PN,
  94                                               ConstantUInt::get(Type::UIntTy,1),
  95                                               "add1-indvar", AfterPHIIt);
  96
  97     // Figure out which block is incoming and which is the backedge for the loop
  98     BasicBlock *Incoming, *BackEdgeBlock;
  99     pred_iterator PI = pred_begin(Header);
 100     assert(PI != pred_end(Header) && "Loop headers should have 2 preds!");
 101     if (Loop->contains(*PI)) {  // First pred is back edge...
 102       BackEdgeBlock = *PI++;
 103       Incoming      = *PI++;
 104     } else {
 105       Incoming      = *PI++;
 106       BackEdgeBlock = *PI++;
 107     }
 108     assert(PI == pred_end(Header) && "Loop headers should have 2 preds!");
 109
 110     // Add incoming values for the PHI node...
 111     PN->addIncoming(Constant::getNullValue(Type::UIntTy), Incoming);
 112     PN->addIncoming(Add, BackEdgeBlock);
 113
 114     // Analyze the new induction variable...
 115     IndVars.push_back(InductionVariable(PN, Loops));
 116     assert(IndVars.back().InductionType == InductionVariable::Canonical &&
 117            "Just inserted canonical indvar that is not canonical!");
 118     Canonical = &IndVars.back();
 119     ++NumInserted;
 120     Changed = true;
 121   } else {
 122     // If we have a canonical induction variable, make sure that it is the first
 123     // one in the basic block.
 124     if (&Header->front() != Canonical->Phi)
 125       Header->getInstList().splice(Header->begin(), Header->getInstList(),
 126                                    Canonical->Phi);
 127   }
 128
 129   DEBUG(std::cerr << "Induction variables:\n");
 130
 131   // Get the current loop iteration count, which is always the value of the
 132   // canonical phi node...
 133   //
 134   PHINode *IterCount = Canonical->Phi;
 135
 136   // Loop through and replace all of the auxiliary induction variables with
 137   // references to the canonical induction variable...
 138   //
 139   for (unsigned i = 0; i < IndVars.size(); ++i) {
 140     InductionVariable *IV = &IndVars[i];
 141
 142     DEBUG(IV->print(std::cerr));
 143
 144     // Don't do math with pointers...
 145     const Type *IVTy = IV->Phi->getType();
 146     if (isa<PointerType>(IVTy)) IVTy = Type::ULongTy;
 147
 148     // Don't modify the canonical indvar or unrecognized indvars...
 149     if (IV != Canonical && IV->InductionType != InductionVariable::Unknown) {
 150       Instruction *Val = IterCount;
 151       if (!isa<ConstantInt>(IV->Step) ||   // If the step != 1
 152           !cast<ConstantInt>(IV->Step)->equalsInt(1)) {
 153
 154         // If the types are not compatible, insert a cast now...
 155         if (Val->getType() != IVTy)
 156           Val = InsertCast(Val, IVTy, AfterPHIIt);
 157         if (IV->Step->getType() != IVTy)
 158           IV->Step = InsertCast(IV->Step, IVTy, AfterPHIIt);
 159
 160         Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step,
 161                                      IV->Phi->getName()+"-scale", AfterPHIIt);
 162       }
 163
 164       // If the start != 0
 165       if (IV->Start != Constant::getNullValue(IV->Start->getType())) {
 166         // If the types are not compatible, insert a cast now...
 167         if (Val->getType() != IVTy)
 168           Val = InsertCast(Val, IVTy, AfterPHIIt);
 169         if (IV->Start->getType() != IVTy)
 170           IV->Start = InsertCast(IV->Start, IVTy, AfterPHIIt);
 171
 172         // Insert the instruction after the phi nodes...
 173         Val = BinaryOperator::create(Instruction::Add, Val, IV->Start,
 174                                      IV->Phi->getName()+"-offset", AfterPHIIt);
 175       }
 176
 177       // If the PHI node has a different type than val is, insert a cast now...
 178       if (Val->getType() != IV->Phi->getType())
 179         Val = InsertCast(Val, IV->Phi->getType(), AfterPHIIt);
 180
 181       // Replace all uses of the old PHI node with the new computed value...
 182       IV->Phi->replaceAllUsesWith(Val);
 183
 184       // Move the PHI name to it's new equivalent value...
 185       std::string OldName = IV->Phi->getName();
 186       IV->Phi->setName("");
 187       Val->setName(OldName);
 188
 189       // Delete the old, now unused, phi node...
 190       Header->getInstList().erase(IV->Phi);
 191
 192       // If the PHI is the last user of any instructions for computing PHI nodes
 193       // that are irrelevant now, delete those instructions.
 194       while (!PHIOps.empty()) {
 195         Instruction *MaybeDead = dyn_cast<Instruction>(PHIOps.back());
 196         PHIOps.pop_back();
 197
 198         if (MaybeDead && isInstructionTriviallyDead(MaybeDead)) {
 199           PHIOps.insert(PHIOps.end(), MaybeDead->op_begin(),
 200                         MaybeDead->op_end());
 201           MaybeDead->getParent()->getInstList().erase(MaybeDead);
 202
 203           // Erase any duplicates entries in the PHIOps list.
 204           std::vector<Value*>::iterator It =
 205             std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
 206           while (It != PHIOps.end()) {
 207             PHIOps.erase(It);
 208             It = std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
 209           }
 210
 211           // Erasing the instruction could invalidate the AfterPHI iterator!
 212           AfterPHIIt = Header->begin();
 213         }
 214       }
 215
 216       Changed = true;
 217       ++NumRemoved;
 218     }
 219   }
 220
 221   return Changed;
 222 }
 223
 224 namespace {
 225   struct InductionVariableSimplify : public FunctionPass {
 226     virtual bool runOnFunction(Function &) {
 227       LoopInfo &LI = getAnalysis<LoopInfo>();
 228
 229       // Induction Variables live in the header nodes of loops
 230       return reduce_apply_bool(LI.getTopLevelLoops().begin(),
 231                                LI.getTopLevelLoops().end(),
 232                                std::bind1st(std::ptr_fun(TransformLoop), &LI));
 233     }
 234
 235     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 236       AU.addRequired<LoopInfo>();
 237       AU.addRequiredID(LoopSimplifyID);
 238       AU.setPreservesCFG();
 239     }
 240   };
 241   RegisterOpt<InductionVariableSimplify> X("indvars",
 242                                            "Canonicalize Induction Variables");
 243 }
 244
 245 Pass *createIndVarSimplifyPass() {
 246   return new InductionVariableSimplify();
 247 }
 248
 249 } // End llvm namespace