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 #define DEBUG_TYPE "indvar"
  18 #include "llvm/Transforms/Scalar.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/Type.h"
  21 #include "llvm/Instructions.h"
  22 #include "llvm/Analysis/InductionVariable.h"
  23 #include "llvm/Analysis/LoopInfo.h"
  24 #include "llvm/Support/CFG.h"
  25 #include "llvm/Target/TargetData.h"
  26 #include "llvm/Transforms/Utils/Local.h"
  27 #include "Support/Debug.h"
  28 #include "Support/Statistic.h"
  29 using namespace llvm;
  30
  31 namespace {
  32   Statistic<> NumRemoved ("indvars", "Number of aux indvars removed");
  33   Statistic<> NumInserted("indvars", "Number of canonical indvars added");
  34
  35   class IndVarSimplify : public FunctionPass {
  36     LoopInfo *Loops;
  37     TargetData *TD;
  38     bool Changed;
  39   public:
  40     virtual bool runOnFunction(Function &) {
  41       Loops = &getAnalysis<LoopInfo>();
  42       TD = &getAnalysis<TargetData>();
  43       Changed = false;
  44
  45       // Induction Variables live in the header nodes of loops
  46       for (LoopInfo::iterator I = Loops->begin(), E = Loops->end(); I != E; ++I)
  47         runOnLoop(*I);
  48       return Changed;
  49     }
  50
  51     unsigned getTypeSize(const Type *Ty) {
  52       if (unsigned Size = Ty->getPrimitiveSize())
  53         return Size;
  54       return TD->getTypeSize(Ty);  // Must be a pointer
  55     }
  56
  57     Value *ComputeAuxIndVarValue(InductionVariable &IV, Value *CIV);
  58     void ReplaceIndVar(InductionVariable &IV, Value *Counter);
  59
  60     void runOnLoop(Loop *L);
  61
  62     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  63       AU.addRequired<TargetData>();   // Need pointer size
  64       AU.addRequired<LoopInfo>();
  65       AU.addRequiredID(LoopSimplifyID);
  66       AU.addPreservedID(LoopSimplifyID);
  67       AU.setPreservesCFG();
  68     }
  69   };
  70   RegisterOpt<IndVarSimplify> X("indvars", "Canonicalize Induction Variables");
  71 }
  72
  73 Pass *llvm::createIndVarSimplifyPass() {
  74   return new IndVarSimplify();
  75 }
  76
  77
  78 void IndVarSimplify::runOnLoop(Loop *Loop) {
  79   // Transform all subloops before this loop...
  80   for (LoopInfo::iterator I = Loop->begin(), E = Loop->end(); I != E; ++I)
  81     runOnLoop(*I);
  82
  83   // Get the header node for this loop.  All of the phi nodes that could be
  84   // induction variables must live in this basic block.
  85   //
  86   BasicBlock *Header = Loop->getHeader();
  87
  88   // Loop over all of the PHI nodes in the basic block, calculating the
  89   // induction variables that they represent... stuffing the induction variable
  90   // info into a vector...
  91   //
  92   std::vector<InductionVariable> IndVars;    // Induction variables for block
  93   BasicBlock::iterator AfterPHIIt = Header->begin();
  94   for (; PHINode *PN = dyn_cast<PHINode>(AfterPHIIt); ++AfterPHIIt)
  95     IndVars.push_back(InductionVariable(PN, Loops));
  96   // AfterPHIIt now points to first non-phi instruction...
  97
  98   // If there are no phi nodes in this basic block, there can't be indvars...
  99   if (IndVars.empty()) return;
 100
 101   // Loop over the induction variables, looking for a canonical induction
 102   // variable, and checking to make sure they are not all unknown induction
 103   // variables.  Keep track of the largest integer size of the induction
 104   // variable.
 105   //
 106   InductionVariable *Canonical = 0;
 107   unsigned MaxSize = 0;
 108
 109   for (unsigned i = 0; i != IndVars.size(); ++i) {
 110     InductionVariable &IV = IndVars[i];
 111
 112     if (IV.InductionType != InductionVariable::Unknown) {
 113       unsigned IVSize = getTypeSize(IV.Phi->getType());
 114
 115       if (IV.InductionType == InductionVariable::Canonical &&
 116           !isa<PointerType>(IV.Phi->getType()) && IVSize >= MaxSize)
 117         Canonical = &IV;
 118
 119       if (IVSize > MaxSize) MaxSize = IVSize;
 120
 121       // If this variable is larger than the currently identified canonical
 122       // indvar, the canonical indvar is not usable.
 123       if (Canonical && IVSize > getTypeSize(Canonical->Phi->getType()))
 124         Canonical = 0;
 125     }
 126   }
 127
 128   // No induction variables, bail early... don't add a canonical indvar
 129   if (MaxSize == 0) return;
 130
 131
 132   // Figure out what the exit condition of the loop is.  We can currently only
 133   // handle loops with a single exit.  If we cannot figure out what the
 134   // termination condition is, we leave this variable set to null.
 135   //
 136   SetCondInst *TermCond = 0;
 137   if (Loop->getExitBlocks().size() == 1) {
 138     // Get ExitingBlock - the basic block in the loop which contains the branch
 139     // out of the loop.
 140     BasicBlock *Exit = Loop->getExitBlocks()[0];
 141     pred_iterator PI = pred_begin(Exit);
 142     assert(PI != pred_end(Exit) && "Should have one predecessor in loop!");
 143     BasicBlock *ExitingBlock = *PI;
 144     assert(++PI == pred_end(Exit) && "Exit block should have one pred!");
 145     assert(Loop->isLoopExit(ExitingBlock) && "Exiting block is not loop exit!");
 146
 147     // Since the block is in the loop, yet branches out of it, we know that the
 148     // block must end with multiple destination terminator.  Which means it is
 149     // either a conditional branch, a switch instruction, or an invoke.
 150     if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) {
 151       assert(BI->isConditional() && "Unconditional branch has multiple succs?");
 152       TermCond = dyn_cast<SetCondInst>(BI->getCondition());
 153     } else {
 154       // NOTE: if people actually exit loops with switch instructions, we could
 155       // handle them, but I don't think this is important enough to spend time
 156       // thinking about.
 157       assert(isa<SwitchInst>(ExitingBlock->getTerminator()) ||
 158              isa<InvokeInst>(ExitingBlock->getTerminator()) &&
 159              "Unknown multi-successor terminator!");
 160     }
 161   }
 162
 163   if (TermCond)
 164     DEBUG(std::cerr << "INDVAR: Found termination condition: " << *TermCond);
 165
 166   // Okay, we want to convert other induction variables to use a canonical
 167   // indvar.  If we don't have one, add one now...
 168   if (!Canonical) {
 169     // Create the PHI node for the new induction variable, and insert the phi
 170     // node at the start of the PHI nodes...
 171     const Type *IVType;
 172     switch (MaxSize) {
 173     default: assert(0 && "Unknown integer type size!");
 174     case 1: IVType = Type::UByteTy; break;
 175     case 2: IVType = Type::UShortTy; break;
 176     case 4: IVType = Type::UIntTy; break;
 177     case 8: IVType = Type::ULongTy; break;
 178     }
 179
 180     PHINode *PN = new PHINode(IVType, "cann-indvar", Header->begin());
 181
 182     // Create the increment instruction to add one to the counter...
 183     Instruction *Add = BinaryOperator::create(Instruction::Add, PN,
 184                                               ConstantUInt::get(IVType, 1),
 185                                               "next-indvar", AfterPHIIt);
 186
 187     // Figure out which block is incoming and which is the backedge for the loop
 188     BasicBlock *Incoming, *BackEdgeBlock;
 189     pred_iterator PI = pred_begin(Header);
 190     assert(PI != pred_end(Header) && "Loop headers should have 2 preds!");
 191     if (Loop->contains(*PI)) {  // First pred is back edge...
 192       BackEdgeBlock = *PI++;
 193       Incoming      = *PI++;
 194     } else {
 195       Incoming      = *PI++;
 196       BackEdgeBlock = *PI++;
 197     }
 198     assert(PI == pred_end(Header) && "Loop headers should have 2 preds!");
 199
 200     // Add incoming values for the PHI node...
 201     PN->addIncoming(Constant::getNullValue(IVType), Incoming);
 202     PN->addIncoming(Add, BackEdgeBlock);
 203
 204     // Analyze the new induction variable...
 205     IndVars.push_back(InductionVariable(PN, Loops));
 206     assert(IndVars.back().InductionType == InductionVariable::Canonical &&
 207            "Just inserted canonical indvar that is not canonical!");
 208     Canonical = &IndVars.back();
 209     ++NumInserted;
 210     Changed = true;
 211     DEBUG(std::cerr << "INDVAR: Inserted canonical iv: " << *PN);
 212   } else {
 213     // If we have a canonical induction variable, make sure that it is the first
 214     // one in the basic block.
 215     if (&Header->front() != Canonical->Phi)
 216       Header->getInstList().splice(Header->begin(), Header->getInstList(),
 217                                    Canonical->Phi);
 218     DEBUG(std::cerr << "IndVar: Existing canonical iv used: "
 219                     << *Canonical->Phi);
 220   }
 221
 222   DEBUG(std::cerr << "INDVAR: Replacing Induction variables:\n");
 223
 224   // Get the current loop iteration count, which is always the value of the
 225   // canonical phi node...
 226   //
 227   PHINode *IterCount = Canonical->Phi;
 228
 229   // Loop through and replace all of the auxiliary induction variables with
 230   // references to the canonical induction variable...
 231   //
 232   for (unsigned i = 0; i != IndVars.size(); ++i) {
 233     InductionVariable *IV = &IndVars[i];
 234
 235     DEBUG(IV->print(std::cerr));
 236
 237     // Don't modify the canonical indvar or unrecognized indvars...
 238     if (IV != Canonical && IV->InductionType != InductionVariable::Unknown) {
 239       ReplaceIndVar(*IV, IterCount);
 240       Changed = true;
 241       ++NumRemoved;
 242     }
 243   }
 244 }
 245
 246 /// ComputeAuxIndVarValue - Given an auxillary induction variable, compute and
 247 /// return a value which will always be equal to the induction variable PHI, but
 248 /// is based off of the canonical induction variable CIV.
 249 ///
 250 Value *IndVarSimplify::ComputeAuxIndVarValue(InductionVariable &IV, Value *CIV){
 251   Instruction *Phi = IV.Phi;
 252   const Type *IVTy = Phi->getType();
 253   if (isa<PointerType>(IVTy))    // If indexing into a pointer, make the
 254     IVTy = TD->getIntPtrType();  // index the appropriate type.
 255
 256   BasicBlock::iterator AfterPHIIt = Phi;
 257   while (isa<PHINode>(AfterPHIIt)) ++AfterPHIIt;
 258
 259   Value *Val = CIV;
 260   if (Val->getType() != IVTy)
 261     Val = new CastInst(Val, IVTy, Val->getName(), AfterPHIIt);
 262
 263   if (!isa<ConstantInt>(IV.Step) ||   // If the step != 1
 264       !cast<ConstantInt>(IV.Step)->equalsInt(1)) {
 265
 266     // If the types are not compatible, insert a cast now...
 267     if (IV.Step->getType() != IVTy)
 268       IV.Step = new CastInst(IV.Step, IVTy, IV.Step->getName(), AfterPHIIt);
 269
 270     Val = BinaryOperator::create(Instruction::Mul, Val, IV.Step,
 271                                  Phi->getName()+"-scale", AfterPHIIt);
 272   }
 273
 274   // If this is a pointer indvar...
 275   if (isa<PointerType>(Phi->getType())) {
 276     std::vector<Value*> Idx;
 277     // FIXME: this should not be needed when we fix PR82!
 278     if (Val->getType() != Type::LongTy)
 279       Val = new CastInst(Val, Type::LongTy, Val->getName(), AfterPHIIt);
 280     Idx.push_back(Val);
 281     Val = new GetElementPtrInst(IV.Start, Idx,
 282                                 Phi->getName()+"-offset",
 283                                 AfterPHIIt);
 284
 285   } else if (!isa<Constant>(IV.Start) ||   // If Start != 0...
 286              !cast<Constant>(IV.Start)->isNullValue()) {
 287     // If the types are not compatible, insert a cast now...
 288     if (IV.Start->getType() != IVTy)
 289       IV.Start = new CastInst(IV.Start, IVTy, IV.Start->getName(),
 290                                AfterPHIIt);
 291
 292     // Insert the instruction after the phi nodes...
 293     Val = BinaryOperator::create(Instruction::Add, Val, IV.Start,
 294                                  Phi->getName()+"-offset", AfterPHIIt);
 295   }
 296
 297   // If the PHI node has a different type than val is, insert a cast now...
 298   if (Val->getType() != Phi->getType())
 299     Val = new CastInst(Val, Phi->getType(), Val->getName(), AfterPHIIt);
 300
 301   // Move the PHI name to it's new equivalent value...
 302   std::string OldName = Phi->getName();
 303   Phi->setName("");
 304   Val->setName(OldName);
 305
 306   return Val;
 307 }
 308
 309 // ReplaceIndVar - Replace all uses of the specified induction variable with
 310 // expressions computed from the specified loop iteration counter variable.
 311 // Return true if instructions were deleted.
 312 void IndVarSimplify::ReplaceIndVar(InductionVariable &IV, Value *CIV) {
 313   Value *IndVarVal = 0;
 314   PHINode *Phi = IV.Phi;
 315
 316   assert(Phi->getNumOperands() == 4 &&
 317          "Only expect induction variables in canonical loops!");
 318
 319   // Remember the incoming values used by the PHI node
 320   std::vector<Value*> PHIOps;
 321   PHIOps.reserve(2);
 322   PHIOps.push_back(Phi->getIncomingValue(0));
 323   PHIOps.push_back(Phi->getIncomingValue(1));
 324
 325   // Delete all of the operands of the PHI node... so that the to-be-deleted PHI
 326   // node does not cause any expressions to be computed that would not otherwise
 327   // be.
 328   Phi->dropAllReferences();
 329
 330   // Now that we are rid of unneeded uses of the PHI node, replace any remaining
 331   // ones with the appropriate code using the canonical induction variable.
 332   while (!Phi->use_empty()) {
 333     Instruction *U = cast<Instruction>(Phi->use_back());
 334
 335     // TODO: Perform LFTR here if possible
 336     if (0) {
 337
 338     } else {
 339       // Replace all uses of the old PHI node with the new computed value...
 340       if (IndVarVal == 0)
 341         IndVarVal = ComputeAuxIndVarValue(IV, CIV);
 342       U->replaceUsesOfWith(Phi, IndVarVal);
 343     }
 344   }
 345
 346   // If the PHI is the last user of any instructions for computing PHI nodes
 347   // that are irrelevant now, delete those instructions.
 348   while (!PHIOps.empty()) {
 349     Instruction *MaybeDead = dyn_cast<Instruction>(PHIOps.back());
 350     PHIOps.pop_back();
 351
 352     if (MaybeDead && isInstructionTriviallyDead(MaybeDead) &&
 353         (!isa<PHINode>(MaybeDead) ||
 354          MaybeDead->getParent() != Phi->getParent())) {
 355       PHIOps.insert(PHIOps.end(), MaybeDead->op_begin(),
 356                     MaybeDead->op_end());
 357       MaybeDead->getParent()->getInstList().erase(MaybeDead);
 358
 359       // Erase any duplicates entries in the PHIOps list.
 360       std::vector<Value*>::iterator It =
 361         std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
 362       while (It != PHIOps.end()) {
 363         PHIOps.erase(It);
 364         It = std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
 365       }
 366     }
 367   }
 368
 369   // Delete the old, now unused, phi node...
 370   Phi->getParent()->getInstList().erase(Phi);
 371 }
 372