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/Instructions.h"
  21 #include "llvm/Analysis/InductionVariable.h"
  22 #include "llvm/Analysis/LoopInfo.h"
  23 #include "llvm/Support/CFG.h"
  24 #include "llvm/Target/TargetData.h"
  25 #include "llvm/Transforms/Utils/Local.h"
  26 #include "Support/Debug.h"
  27 #include "Support/Statistic.h"
  28 using namespace llvm;
  29
  30 namespace {
  31   Statistic<> NumRemoved ("indvars", "Number of aux indvars removed");
  32   Statistic<> NumInserted("indvars", "Number of canonical indvars added");
  33
  34   class IndVarSimplify : public FunctionPass {
  35     LoopInfo *Loops;
  36     TargetData *TD;
  37   public:
  38     virtual bool runOnFunction(Function &) {
  39       Loops = &getAnalysis<LoopInfo>();
  40       TD = &getAnalysis<TargetData>();
  41
  42       // Induction Variables live in the header nodes of loops
  43       bool Changed = false;
  44       for (unsigned i = 0, e = Loops->getTopLevelLoops().size(); i != e; ++i)
  45         Changed |= runOnLoop(Loops->getTopLevelLoops()[i]);
  46       return Changed;
  47     }
  48
  49     unsigned getTypeSize(const Type *Ty) {
  50       if (unsigned Size = Ty->getPrimitiveSize())
  51         return Size;
  52       return TD->getTypeSize(Ty);  // Must be a pointer
  53     }
  54
  55     bool runOnLoop(Loop *L);
  56
  57     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  58       AU.addRequired<TargetData>();   // Need pointer size
  59       AU.addRequired<LoopInfo>();
  60       AU.addRequiredID(LoopSimplifyID);
  61       AU.addPreservedID(LoopSimplifyID);
  62       AU.setPreservesCFG();
  63     }
  64   };
  65   RegisterOpt<IndVarSimplify> X("indvars", "Canonicalize Induction Variables");
  66 }
  67
  68 Pass *llvm::createIndVarSimplifyPass() {
  69   return new IndVarSimplify();
  70 }
  71
  72
  73 bool IndVarSimplify::runOnLoop(Loop *Loop) {
  74   // Transform all subloops before this loop...
  75   bool Changed = false;
  76   for (unsigned i = 0, e = Loop->getSubLoops().size(); i != e; ++i)
  77     Changed |= runOnLoop(Loop->getSubLoops()[i]);
  78
  79   // Get the header node for this loop.  All of the phi nodes that could be
  80   // induction variables must live in this basic block.
  81   //
  82   BasicBlock *Header = Loop->getHeader();
  83
  84   // Loop over all of the PHI nodes in the basic block, calculating the
  85   // induction variables that they represent... stuffing the induction variable
  86   // info into a vector...
  87   //
  88   std::vector<InductionVariable> IndVars;    // Induction variables for block
  89   BasicBlock::iterator AfterPHIIt = Header->begin();
  90   for (; PHINode *PN = dyn_cast<PHINode>(AfterPHIIt); ++AfterPHIIt)
  91     IndVars.push_back(InductionVariable(PN, Loops));
  92   // AfterPHIIt now points to first non-phi instruction...
  93
  94   // If there are no phi nodes in this basic block, there can't be indvars...
  95   if (IndVars.empty()) return Changed;
  96
  97   // Loop over the induction variables, looking for a canonical induction
  98   // variable, and checking to make sure they are not all unknown induction
  99   // variables.  Keep track of the largest integer size of the induction
 100   // variable.
 101   //
 102   InductionVariable *Canonical = 0;
 103   unsigned MaxSize = 0;
 104
 105   for (unsigned i = 0; i != IndVars.size(); ++i) {
 106     InductionVariable &IV = IndVars[i];
 107
 108     if (IV.InductionType != InductionVariable::Unknown) {
 109       unsigned IVSize = getTypeSize(IV.Phi->getType());
 110
 111       if (IV.InductionType == InductionVariable::Canonical &&
 112           !isa<PointerType>(IV.Phi->getType()) && IVSize >= MaxSize)
 113         Canonical = &IV;
 114
 115       if (IVSize > MaxSize) MaxSize = IVSize;
 116
 117       // If this variable is larger than the currently identified canonical
 118       // indvar, the canonical indvar is not usable.
 119       if (Canonical && IVSize > getTypeSize(Canonical->Phi->getType()))
 120         Canonical = 0;
 121     }
 122   }
 123
 124   // No induction variables, bail early... don't add a canonical indvar
 125   if (MaxSize == 0) return Changed;
 126
 127   // Okay, we want to convert other induction variables to use a canonical
 128   // indvar.  If we don't have one, add one now...
 129   if (!Canonical) {
 130     // Create the PHI node for the new induction variable, and insert the phi
 131     // node at the start of the PHI nodes...
 132     const Type *IVType;
 133     switch (MaxSize) {
 134     default: assert(0 && "Unknown integer type size!");
 135     case 1: IVType = Type::UByteTy; break;
 136     case 2: IVType = Type::UShortTy; break;
 137     case 4: IVType = Type::UIntTy; break;
 138     case 8: IVType = Type::ULongTy; break;
 139     }
 140
 141     PHINode *PN = new PHINode(IVType, "cann-indvar", Header->begin());
 142
 143     // Create the increment instruction to add one to the counter...
 144     Instruction *Add = BinaryOperator::create(Instruction::Add, PN,
 145                                               ConstantUInt::get(IVType, 1),
 146                                               "next-indvar", AfterPHIIt);
 147
 148     // Figure out which block is incoming and which is the backedge for the loop
 149     BasicBlock *Incoming, *BackEdgeBlock;
 150     pred_iterator PI = pred_begin(Header);
 151     assert(PI != pred_end(Header) && "Loop headers should have 2 preds!");
 152     if (Loop->contains(*PI)) {  // First pred is back edge...
 153       BackEdgeBlock = *PI++;
 154       Incoming      = *PI++;
 155     } else {
 156       Incoming      = *PI++;
 157       BackEdgeBlock = *PI++;
 158     }
 159     assert(PI == pred_end(Header) && "Loop headers should have 2 preds!");
 160
 161     // Add incoming values for the PHI node...
 162     PN->addIncoming(Constant::getNullValue(IVType), Incoming);
 163     PN->addIncoming(Add, BackEdgeBlock);
 164
 165     // Analyze the new induction variable...
 166     IndVars.push_back(InductionVariable(PN, Loops));
 167     assert(IndVars.back().InductionType == InductionVariable::Canonical &&
 168            "Just inserted canonical indvar that is not canonical!");
 169     Canonical = &IndVars.back();
 170     ++NumInserted;
 171     Changed = true;
 172   } else {
 173     // If we have a canonical induction variable, make sure that it is the first
 174     // one in the basic block.
 175     if (&Header->front() != Canonical->Phi)
 176       Header->getInstList().splice(Header->begin(), Header->getInstList(),
 177                                    Canonical->Phi);
 178   }
 179
 180   DEBUG(std::cerr << "Induction variables:\n");
 181
 182   // Get the current loop iteration count, which is always the value of the
 183   // canonical phi node...
 184   //
 185   PHINode *IterCount = Canonical->Phi;
 186
 187   // Loop through and replace all of the auxiliary induction variables with
 188   // references to the canonical induction variable...
 189   //
 190   for (unsigned i = 0; i != IndVars.size(); ++i) {
 191     InductionVariable *IV = &IndVars[i];
 192
 193     DEBUG(IV->print(std::cerr));
 194
 195     while (isa<PHINode>(AfterPHIIt)) ++AfterPHIIt;
 196
 197     // Don't modify the canonical indvar or unrecognized indvars...
 198     if (IV != Canonical && IV->InductionType != InductionVariable::Unknown) {
 199       const Type *IVTy = IV->Phi->getType();
 200       if (isa<PointerType>(IVTy))    // If indexing into a pointer, make the
 201         IVTy = TD->getIntPtrType();  // index the appropriate type.
 202
 203       Instruction *Val = IterCount;
 204       if (!isa<ConstantInt>(IV->Step) ||   // If the step != 1
 205           !cast<ConstantInt>(IV->Step)->equalsInt(1)) {
 206
 207         // If the types are not compatible, insert a cast now...
 208         if (Val->getType() != IVTy)
 209           Val = new CastInst(Val, IVTy, Val->getName(), AfterPHIIt);
 210         if (IV->Step->getType() != IVTy)
 211           IV->Step = new CastInst(IV->Step, IVTy, IV->Step->getName(),
 212                                   AfterPHIIt);
 213
 214         Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step,
 215                                      IV->Phi->getName()+"-scale", AfterPHIIt);
 216       }
 217
 218       // If this is a pointer indvar...
 219       if (isa<PointerType>(IV->Phi->getType())) {
 220         std::vector<Value*> Idx;
 221         // FIXME: this should not be needed when we fix PR82!
 222         if (Val->getType() != Type::LongTy)
 223           Val = new CastInst(Val, Type::LongTy, Val->getName(), AfterPHIIt);
 224         Idx.push_back(Val);
 225         Val = new GetElementPtrInst(IV->Start, Idx,
 226                                     IV->Phi->getName()+"-offset",
 227                                     AfterPHIIt);
 228
 229       } else if (!isa<Constant>(IV->Start) ||   // If Start != 0...
 230                  !cast<Constant>(IV->Start)->isNullValue()) {
 231         // If the types are not compatible, insert a cast now...
 232         if (Val->getType() != IVTy)
 233           Val = new CastInst(Val, IVTy, Val->getName(), AfterPHIIt);
 234         if (IV->Start->getType() != IVTy)
 235           IV->Start = new CastInst(IV->Start, IVTy, IV->Start->getName(),
 236                                    AfterPHIIt);
 237
 238         // Insert the instruction after the phi nodes...
 239         Val = BinaryOperator::create(Instruction::Add, Val, IV->Start,
 240                                      IV->Phi->getName()+"-offset", AfterPHIIt);
 241       }
 242
 243       // If the PHI node has a different type than val is, insert a cast now...
 244       if (Val->getType() != IV->Phi->getType())
 245         Val = new CastInst(Val, IV->Phi->getType(), Val->getName(), AfterPHIIt);
 246
 247       // Replace all uses of the old PHI node with the new computed value...
 248       IV->Phi->replaceAllUsesWith(Val);
 249
 250       // Move the PHI name to it's new equivalent value...
 251       std::string OldName = IV->Phi->getName();
 252       IV->Phi->setName("");
 253       Val->setName(OldName);
 254
 255       // Get the incoming values used by the PHI node
 256       std::vector<Value*> PHIOps;
 257       PHIOps.reserve(IV->Phi->getNumIncomingValues());
 258       for (unsigned i = 0, e = IV->Phi->getNumIncomingValues(); i != e; ++i)
 259         PHIOps.push_back(IV->Phi->getIncomingValue(i));
 260
 261       // Delete the old, now unused, phi node...
 262       Header->getInstList().erase(IV->Phi);
 263
 264       // If the PHI is the last user of any instructions for computing PHI nodes
 265       // that are irrelevant now, delete those instructions.
 266       while (!PHIOps.empty()) {
 267         Instruction *MaybeDead = dyn_cast<Instruction>(PHIOps.back());
 268         PHIOps.pop_back();
 269
 270         if (MaybeDead && isInstructionTriviallyDead(MaybeDead)) {
 271           PHIOps.insert(PHIOps.end(), MaybeDead->op_begin(),
 272                         MaybeDead->op_end());
 273           MaybeDead->getParent()->getInstList().erase(MaybeDead);
 274
 275           // Erase any duplicates entries in the PHIOps list.
 276           std::vector<Value*>::iterator It =
 277             std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
 278           while (It != PHIOps.end()) {
 279             PHIOps.erase(It);
 280             It = std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
 281           }
 282
 283           // Erasing the instruction could invalidate the AfterPHI iterator!
 284           AfterPHIIt = Header->begin();
 285         }
 286       }
 287
 288       Changed = true;
 289       ++NumRemoved;
 290     }
 291   }
 292
 293   return Changed;
 294 }
 295