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/Constants.h"
  19 #include "llvm/Type.h"
  20 #include "llvm/iPHINode.h"
  21 #include "llvm/iOther.h"
  22 #include "llvm/Analysis/InductionVariable.h"
  23 #include "llvm/Analysis/LoopInfo.h"
  24 #include "llvm/Support/CFG.h"
  25 #include "llvm/Transforms/Utils/Local.h"
  26 #include "Support/Debug.h"
  27 #include "Support/Statistic.h"
  28 #include "Support/STLExtras.h"
  29 #include <algorithm>
  30 using 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     while (isa<PHINode>(AfterPHIIt)) ++AfterPHIIt;
 145
 146     // Don't do math with pointers...
 147     const Type *IVTy = IV->Phi->getType();
 148     if (isa<PointerType>(IVTy)) IVTy = Type::ULongTy;
 149
 150     // Don't modify the canonical indvar or unrecognized indvars...
 151     if (IV != Canonical && IV->InductionType != InductionVariable::Unknown) {
 152       Instruction *Val = IterCount;
 153       if (!isa<ConstantInt>(IV->Step) ||   // If the step != 1
 154           !cast<ConstantInt>(IV->Step)->equalsInt(1)) {
 155
 156         // If the types are not compatible, insert a cast now...
 157         if (Val->getType() != IVTy)
 158           Val = InsertCast(Val, IVTy, AfterPHIIt);
 159         if (IV->Step->getType() != IVTy)
 160           IV->Step = InsertCast(IV->Step, IVTy, AfterPHIIt);
 161
 162         Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step,
 163                                      IV->Phi->getName()+"-scale", AfterPHIIt);
 164       }
 165
 166       // If the start != 0
 167       if (IV->Start != Constant::getNullValue(IV->Start->getType())) {
 168         // If the types are not compatible, insert a cast now...
 169         if (Val->getType() != IVTy)
 170           Val = InsertCast(Val, IVTy, AfterPHIIt);
 171         if (IV->Start->getType() != IVTy)
 172           IV->Start = InsertCast(IV->Start, IVTy, AfterPHIIt);
 173
 174         // Insert the instruction after the phi nodes...
 175         Val = BinaryOperator::create(Instruction::Add, Val, IV->Start,
 176                                      IV->Phi->getName()+"-offset", AfterPHIIt);
 177       }
 178
 179       // If the PHI node has a different type than val is, insert a cast now...
 180       if (Val->getType() != IV->Phi->getType())
 181         Val = InsertCast(Val, IV->Phi->getType(), AfterPHIIt);
 182
 183       // Replace all uses of the old PHI node with the new computed value...
 184       IV->Phi->replaceAllUsesWith(Val);
 185
 186       // Move the PHI name to it's new equivalent value...
 187       std::string OldName = IV->Phi->getName();
 188       IV->Phi->setName("");
 189       Val->setName(OldName);
 190
 191       // Get the incoming values used by the PHI node
 192       std::vector<Value*> PHIOps;
 193       PHIOps.reserve(IV->Phi->getNumIncomingValues());
 194       for (unsigned i = 0, e = IV->Phi->getNumIncomingValues(); i != e; ++i)
 195         PHIOps.push_back(IV->Phi->getIncomingValue(i));
 196
 197       // Delete the old, now unused, phi node...
 198       Header->getInstList().erase(IV->Phi);
 199
 200       // If the PHI is the last user of any instructions for computing PHI nodes
 201       // that are irrelevant now, delete those instructions.
 202       while (!PHIOps.empty()) {
 203         Instruction *MaybeDead = dyn_cast<Instruction>(PHIOps.back());
 204         PHIOps.pop_back();
 205
 206         if (MaybeDead && isInstructionTriviallyDead(MaybeDead)) {
 207           PHIOps.insert(PHIOps.end(), MaybeDead->op_begin(),
 208                         MaybeDead->op_end());
 209           MaybeDead->getParent()->getInstList().erase(MaybeDead);
 210
 211           // Erase any duplicates entries in the PHIOps list.
 212           std::vector<Value*>::iterator It =
 213             std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
 214           while (It != PHIOps.end()) {
 215             PHIOps.erase(It);
 216             It = std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
 217           }
 218
 219           // Erasing the instruction could invalidate the AfterPHI iterator!
 220           AfterPHIIt = Header->begin();
 221         }
 222       }
 223
 224       Changed = true;
 225       ++NumRemoved;
 226     }
 227   }
 228
 229   return Changed;
 230 }
 231
 232 namespace {
 233   struct InductionVariableSimplify : public FunctionPass {
 234     virtual bool runOnFunction(Function &) {
 235       LoopInfo &LI = getAnalysis<LoopInfo>();
 236
 237       // Induction Variables live in the header nodes of loops
 238       return reduce_apply_bool(LI.getTopLevelLoops().begin(),
 239                                LI.getTopLevelLoops().end(),
 240                                std::bind1st(std::ptr_fun(TransformLoop), &LI));
 241     }
 242
 243     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 244       AU.addRequired<LoopInfo>();
 245       AU.addRequiredID(LoopSimplifyID);
 246       AU.setPreservesCFG();
 247     }
 248   };
 249   RegisterOpt<InductionVariableSimplify> X("indvars",
 250                                            "Canonicalize Induction Variables");
 251 }
 252
 253 Pass *llvm::createIndVarSimplifyPass() {
 254   return new InductionVariableSimplify();
 255 }
 256