lib/Transforms/Scalar/LoopStrengthReduce.cpp

   1 //===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Nate Begeman and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass performs a strength reduction on array references inside loops that
  11 // have as one or more of their components the loop induction variable.  This is
  12 // accomplished by creating a new Value to hold the initial value of the array
  13 // access for the first iteration, and then creating a new GEP instruction in
  14 // the loop to increment the value by the appropriate amount.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/Transforms/Scalar.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Type.h"
  22 #include "llvm/DerivedTypes.h"
  23 #include "llvm/Analysis/Dominators.h"
  24 #include "llvm/Analysis/LoopInfo.h"
  25 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  26 #include "llvm/Support/CFG.h"
  27 #include "llvm/Support/GetElementPtrTypeIterator.h"
  28 #include "llvm/Transforms/Utils/Local.h"
  29 #include "llvm/Target/TargetData.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/Support/Debug.h"
  32 #include <algorithm>
  33 #include <set>
  34 using namespace llvm;
  35
  36 namespace {
  37   Statistic<> NumReduced ("loop-reduce", "Number of GEPs strength reduced");
  38
  39   class GEPCache {
  40   public:
  41     GEPCache() : CachedPHINode(0), Map() {}
  42
  43     GEPCache *get(Value *v) {
  44       std::map<Value *, GEPCache>::iterator I = Map.find(v);
  45       if (I == Map.end())
  46         I = Map.insert(std::pair<Value *, GEPCache>(v, GEPCache())).first;
  47       return &I->second;
  48     }
  49
  50     PHINode *CachedPHINode;
  51     std::map<Value *, GEPCache> Map;
  52   };
  53
  54   struct IVUse {
  55     /// Users - Keep track of all of the users of this stride as well as the
  56     /// initial value.
  57     std::vector<std::pair<SCEVHandle, Instruction*> > Users;
  58     std::vector<Instruction *> UserOperands;
  59
  60     void addUser(SCEVHandle &SH, Instruction *U, Instruction *V) {
  61       Users.push_back(std::make_pair(SH, U));
  62       UserOperands.push_back(V);
  63     }
  64   };
  65
  66
  67   class LoopStrengthReduce : public FunctionPass {
  68     LoopInfo *LI;
  69     DominatorSet *DS;
  70     ScalarEvolution *SE;
  71     const TargetData *TD;
  72     const Type *UIntPtrTy;
  73     bool Changed;
  74
  75     /// MaxTargetAMSize - This is the maximum power-of-two scale value that the
  76     /// target can handle for free with its addressing modes.
  77     unsigned MaxTargetAMSize;
  78
  79     /// IVUsesByStride - Keep track of all uses of induction variables that we
  80     /// are interested in.  The key of the map is the stride of the access.
  81     std::map<Value*, IVUse> IVUsesByStride;
  82
  83     /// CastedBasePointers - As we need to lower getelementptr instructions, we
  84     /// cast the pointer input to uintptr_t.  This keeps track of the casted
  85     /// values for the pointers we have processed so far.
  86     std::map<Value*, Value*> CastedBasePointers;
  87
  88     /// DeadInsts - Keep track of instructions we may have made dead, so that
  89     /// we can remove them after we are done working.
  90     std::set<Instruction*> DeadInsts;
  91   public:
  92     LoopStrengthReduce(unsigned MTAMS = 1)
  93       : MaxTargetAMSize(MTAMS) {
  94     }
  95
  96     virtual bool runOnFunction(Function &) {
  97       LI = &getAnalysis<LoopInfo>();
  98       DS = &getAnalysis<DominatorSet>();
  99       SE = &getAnalysis<ScalarEvolution>();
 100       TD = &getAnalysis<TargetData>();
 101       UIntPtrTy = TD->getIntPtrType();
 102       Changed = false;
 103
 104       for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
 105         runOnLoop(*I);
 106       return Changed;
 107     }
 108
 109     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 110       AU.setPreservesCFG();
 111       AU.addRequiredID(LoopSimplifyID);
 112       AU.addRequired<LoopInfo>();
 113       AU.addRequired<DominatorSet>();
 114       AU.addRequired<TargetData>();
 115       AU.addRequired<ScalarEvolution>();
 116     }
 117   private:
 118     void runOnLoop(Loop *L);
 119     bool AddUsersIfInteresting(Instruction *I, Loop *L);
 120     void AnalyzeGetElementPtrUsers(GetElementPtrInst *GEP, Instruction *I,
 121                                    Loop *L);
 122
 123     void StrengthReduceStridedIVUsers(Value *Stride, IVUse &Uses, Loop *L,
 124                                       bool isOnlyStride);
 125
 126     void strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
 127                            GEPCache* GEPCache,
 128                            Instruction *InsertBefore,
 129                            std::set<Instruction*> &DeadInsts);
 130     void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
 131   };
 132   RegisterOpt<LoopStrengthReduce> X("loop-reduce",
 133                                     "Strength Reduce GEP Uses of Ind. Vars");
 134 }
 135
 136 FunctionPass *llvm::createLoopStrengthReducePass(unsigned MaxTargetAMSize) {
 137   return new LoopStrengthReduce(MaxTargetAMSize);
 138 }
 139
 140 /// DeleteTriviallyDeadInstructions - If any of the instructions is the
 141 /// specified set are trivially dead, delete them and see if this makes any of
 142 /// their operands subsequently dead.
 143 void LoopStrengthReduce::
 144 DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
 145   while (!Insts.empty()) {
 146     Instruction *I = *Insts.begin();
 147     Insts.erase(Insts.begin());
 148     if (isInstructionTriviallyDead(I)) {
 149       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 150         if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
 151           Insts.insert(U);
 152       SE->deleteInstructionFromRecords(I);
 153       I->eraseFromParent();
 154       Changed = true;
 155     }
 156   }
 157 }
 158
 159
 160 /// CanReduceSCEV - Return true if we can strength reduce this scalar evolution
 161 /// in the specified loop.
 162 static bool CanReduceSCEV(const SCEVHandle &SH, Loop *L) {
 163   SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SH);
 164   if (!AddRec || AddRec->getLoop() != L) return false;
 165
 166   // FIXME: Generalize to non-affine IV's.
 167   if (!AddRec->isAffine()) return false;
 168
 169   // FIXME: generalize to IV's with more complex strides (must emit stride
 170   // expression outside of loop!)
 171   if (isa<SCEVConstant>(AddRec->getOperand(1)))
 172     return true;
 173
 174   // We handle steps by unsigned values, because we know we won't have to insert
 175   // a cast for them.
 176   if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(AddRec->getOperand(1)))
 177     if (SU->getValue()->getType()->isUnsigned())
 178       return true;
 179
 180   // Otherwise, no, we can't handle it yet.
 181   return false;
 182 }
 183
 184
 185 /// GetAdjustedIndex - Adjust the specified GEP sequential type index to match
 186 /// the size of the pointer type, and scale it by the type size.
 187 static SCEVHandle GetAdjustedIndex(const SCEVHandle &Idx, uint64_t TySize,
 188                                    const Type *UIntPtrTy) {
 189   SCEVHandle Result = Idx;
 190   if (Result->getType()->getUnsignedVersion() != UIntPtrTy) {
 191     if (UIntPtrTy->getPrimitiveSize() < Result->getType()->getPrimitiveSize())
 192       Result = SCEVTruncateExpr::get(Result, UIntPtrTy);
 193     else
 194       Result = SCEVZeroExtendExpr::get(Result, UIntPtrTy);
 195   }
 196
 197   // This index is scaled by the type size being indexed.
 198   if (TySize != 1)
 199     Result = SCEVMulExpr::get(Result,
 200                               SCEVConstant::get(ConstantUInt::get(UIntPtrTy,
 201                                                                   TySize)));
 202   return Result;
 203 }
 204
 205 /// AnalyzeGetElementPtrUsers - Analyze all of the users of the specified
 206 /// getelementptr instruction, adding them to the IVUsesByStride table.  Note
 207 /// that we only want to analyze a getelementptr instruction once, and it can
 208 /// have multiple operands that are uses of the indvar (e.g. A[i][i]).  Because
 209 /// of this, we only process a GEP instruction if its first recurrent operand is
 210 /// "op", otherwise we will either have already processed it or we will sometime
 211 /// later.
 212 void LoopStrengthReduce::AnalyzeGetElementPtrUsers(GetElementPtrInst *GEP,
 213                                                    Instruction *Op, Loop *L) {
 214   // Analyze all of the subscripts of this getelementptr instruction, looking
 215   // for uses that are determined by the trip count of L.  First, skip all
 216   // operands the are not dependent on the IV.
 217
 218   // Build up the base expression.  Insert an LLVM cast of the pointer to
 219   // uintptr_t first.
 220   Value *BasePtr;
 221   if (Constant *CB = dyn_cast<Constant>(GEP->getOperand(0)))
 222     BasePtr = ConstantExpr::getCast(CB, UIntPtrTy);
 223   else {
 224     Value *&BP = CastedBasePointers[GEP->getOperand(0)];
 225     if (BP == 0) {
 226       BasicBlock::iterator InsertPt;
 227       if (isa<Argument>(GEP->getOperand(0))) {
 228         InsertPt = GEP->getParent()->getParent()->begin()->begin();
 229       } else {
 230         InsertPt = cast<Instruction>(GEP->getOperand(0));
 231         if (InvokeInst *II = dyn_cast<InvokeInst>(GEP->getOperand(0)))
 232           InsertPt = II->getNormalDest()->begin();
 233         else
 234           ++InsertPt;
 235       }
 236
 237       // Do not insert casts into the middle of PHI node blocks.
 238       while (isa<PHINode>(InsertPt)) ++InsertPt;
 239
 240       BP = new CastInst(GEP->getOperand(0), UIntPtrTy,
 241                         GEP->getOperand(0)->getName(), InsertPt);
 242     }
 243     BasePtr = BP;
 244   }
 245
 246   SCEVHandle Base = SCEVUnknown::get(BasePtr);
 247
 248   gep_type_iterator GTI = gep_type_begin(GEP);
 249   unsigned i = 1;
 250   for (; GEP->getOperand(i) != Op; ++i, ++GTI) {
 251     // If this is a use of a recurrence that we can analyze, and it comes before
 252     // Op does in the GEP operand list, we will handle this when we process this
 253     // operand.
 254     if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
 255       const StructLayout *SL = TD->getStructLayout(STy);
 256       unsigned Idx = cast<ConstantUInt>(GEP->getOperand(i))->getValue();
 257       uint64_t Offset = SL->MemberOffsets[Idx];
 258       Base = SCEVAddExpr::get(Base, SCEVUnknown::getIntegerSCEV(Offset,
 259                                                                 UIntPtrTy));
 260     } else {
 261       SCEVHandle Idx = SE->getSCEV(GEP->getOperand(i));
 262
 263       // If this operand is reducible, and it's not the one we are looking at
 264       // currently, do not process the GEP at this time.
 265       if (CanReduceSCEV(Idx, L))
 266         return;
 267       Base = SCEVAddExpr::get(Base, GetAdjustedIndex(Idx,
 268                              TD->getTypeSize(GTI.getIndexedType()), UIntPtrTy));
 269     }
 270   }
 271
 272   // Get the index, convert it to intptr_t.
 273   SCEVHandle GEPIndexExpr =
 274     GetAdjustedIndex(SE->getSCEV(Op), TD->getTypeSize(GTI.getIndexedType()),
 275                      UIntPtrTy);
 276
 277   // Process all remaining subscripts in the GEP instruction.
 278   for (++i, ++GTI; i != GEP->getNumOperands(); ++i, ++GTI)
 279     if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
 280       const StructLayout *SL = TD->getStructLayout(STy);
 281       unsigned Idx = cast<ConstantUInt>(GEP->getOperand(i))->getValue();
 282       uint64_t Offset = SL->MemberOffsets[Idx];
 283       Base = SCEVAddExpr::get(Base, SCEVUnknown::getIntegerSCEV(Offset,
 284                                                                 UIntPtrTy));
 285     } else {
 286       SCEVHandle Idx = SE->getSCEV(GEP->getOperand(i));
 287       if (CanReduceSCEV(Idx, L)) {   // Another IV subscript
 288         GEPIndexExpr = SCEVAddExpr::get(GEPIndexExpr,
 289                     GetAdjustedIndex(Idx, TD->getTypeSize(GTI.getIndexedType()),
 290                                    UIntPtrTy));
 291         assert(CanReduceSCEV(GEPIndexExpr, L) &&
 292                "Cannot reduce the sum of two reducible SCEV's??");
 293       } else {
 294         Base = SCEVAddExpr::get(Base, GetAdjustedIndex(Idx,
 295                              TD->getTypeSize(GTI.getIndexedType()), UIntPtrTy));
 296       }
 297     }
 298
 299   assert(CanReduceSCEV(GEPIndexExpr, L) && "Non reducible idx??");
 300
 301   // FIXME: If the base is not loop invariant, we currently cannot emit this.
 302   if (!Base->isLoopInvariant(L)) {
 303     DEBUG(std::cerr << "IGNORING GEP due to non-invaiant base: "
 304                     << *Base << "\n");
 305     return;
 306   }
 307
 308   Base = SCEVAddExpr::get(Base, cast<SCEVAddRecExpr>(GEPIndexExpr)->getStart());
 309   SCEVHandle Stride = cast<SCEVAddRecExpr>(GEPIndexExpr)->getOperand(1);
 310
 311   DEBUG(std::cerr << "GEP BASE  : " << *Base << "\n");
 312   DEBUG(std::cerr << "GEP STRIDE: " << *Stride << "\n");
 313
 314   Value *Step = 0;   // Step of ISE.
 315   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride))
 316     /// Always get the step value as an unsigned value.
 317     Step = ConstantExpr::getCast(SC->getValue(),
 318                                SC->getValue()->getType()->getUnsignedVersion());
 319   else
 320     Step = cast<SCEVUnknown>(Stride)->getValue();
 321   assert(Step->getType()->isUnsigned() && "Bad step value!");
 322
 323
 324   // Now that we know the base and stride contributed by the GEP instruction,
 325   // process all users.
 326   for (Value::use_iterator UI = GEP->use_begin(), E = GEP->use_end();
 327        UI != E; ++UI) {
 328     Instruction *User = cast<Instruction>(*UI);
 329
 330     // Do not infinitely recurse on PHI nodes.
 331     if (isa<PHINode>(User) && User->getParent() == L->getHeader())
 332       continue;
 333
 334     // If this is an instruction defined in a nested loop, or outside this loop,
 335     // don't mess with it.
 336     if (LI->getLoopFor(User->getParent()) != L)
 337       continue;
 338
 339     DEBUG(std::cerr << "FOUND USER: " << *User
 340           << "   OF STRIDE: " << *Step << " BASE = " << *Base << "\n");
 341
 342
 343     // Okay, we found a user that we cannot reduce.  Analyze the instruction
 344     // and decide what to do with it.
 345     IVUsesByStride[Step].addUser(Base, User, GEP);
 346   }
 347 }
 348
 349 /// AddUsersIfInteresting - Inspect the specified instruction.  If it is a
 350 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
 351 /// return true.  Otherwise, return false.
 352 bool LoopStrengthReduce::AddUsersIfInteresting(Instruction *I, Loop *L) {
 353   if (I->getType() == Type::VoidTy) return false;
 354   SCEVHandle ISE = SE->getSCEV(I);
 355   if (!CanReduceSCEV(ISE, L)) return false;
 356
 357   SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(ISE);
 358   SCEVHandle Start = AR->getStart();
 359
 360   // Get the step value, canonicalizing to an unsigned integer type so that
 361   // lookups in the map will match.
 362   Value *Step = 0;   // Step of ISE.
 363   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(AR->getOperand(1)))
 364     /// Always get the step value as an unsigned value.
 365     Step = ConstantExpr::getCast(SC->getValue(),
 366                                SC->getValue()->getType()->getUnsignedVersion());
 367   else
 368     Step = cast<SCEVUnknown>(AR->getOperand(1))->getValue();
 369   assert(Step->getType()->isUnsigned() && "Bad step value!");
 370
 371   std::set<GetElementPtrInst*> AnalyzedGEPs;
 372
 373   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;++UI){
 374     Instruction *User = cast<Instruction>(*UI);
 375
 376     // Do not infinitely recurse on PHI nodes.
 377     if (isa<PHINode>(User) && User->getParent() == L->getHeader())
 378       continue;
 379
 380     // If this is an instruction defined in a nested loop, or outside this loop,
 381     // don't mess with it.
 382     if (LI->getLoopFor(User->getParent()) != L)
 383       continue;
 384
 385     // Next, see if this user is analyzable itself!
 386     if (!AddUsersIfInteresting(User, L)) {
 387       if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
 388         // If this is a getelementptr instruction, figure out what linear
 389         // expression of induction variable is actually being used.
 390         //
 391         if (AnalyzedGEPs.insert(GEP).second)   // Not already analyzed?
 392           AnalyzeGetElementPtrUsers(GEP, I, L);
 393       } else {
 394         DEBUG(std::cerr << "FOUND USER: " << *User
 395               << "   OF SCEV: " << *ISE << "\n");
 396
 397         // Okay, we found a user that we cannot reduce.  Analyze the instruction
 398         // and decide what to do with it.
 399         IVUsesByStride[Step].addUser(Start, User, I);
 400       }
 401     }
 402   }
 403   return true;
 404 }
 405
 406 namespace {
 407   /// BasedUser - For a particular base value, keep information about how we've
 408   /// partitioned the expression so far.
 409   struct BasedUser {
 410     /// Inst - The instruction using the induction variable.
 411     Instruction *Inst;
 412
 413     /// Op - The value to replace with the EmittedBase.
 414     Value *Op;
 415
 416     /// Imm - The immediate value that should be added to the base immediately
 417     /// before Inst, because it will be folded into the imm field of the
 418     /// instruction.
 419     SCEVHandle Imm;
 420
 421     /// EmittedBase - The actual value* to use for the base value of this
 422     /// operation.  This is null if we should just use zero so far.
 423     Value *EmittedBase;
 424
 425     BasedUser(Instruction *I, Value *V, const SCEVHandle &IMM)
 426       : Inst(I), Op(V), Imm(IMM), EmittedBase(0) {}
 427
 428
 429     // No need to compare these.
 430     bool operator<(const BasedUser &BU) const { return 0; }
 431
 432     void dump() const;
 433   };
 434 }
 435
 436 void BasedUser::dump() const {
 437   std::cerr << " Imm=" << *Imm;
 438   if (EmittedBase)
 439     std::cerr << "  EB=" << *EmittedBase;
 440
 441   std::cerr << "   Inst: " << *Inst;
 442 }
 443
 444 /// isTargetConstant - Return true if the following can be referenced by the
 445 /// immediate field of a target instruction.
 446 static bool isTargetConstant(const SCEVHandle &V) {
 447
 448   // FIXME: Look at the target to decide if &GV is a legal constant immediate.
 449   if (isa<SCEVConstant>(V)) return true;
 450
 451   return false;     // ENABLE this for x86
 452
 453   if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V))
 454     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(SU->getValue()))
 455       if (CE->getOpcode() == Instruction::Cast)
 456         if (isa<GlobalValue>(CE->getOperand(0)))
 457           // FIXME: should check to see that the dest is uintptr_t!
 458           return true;
 459   return false;
 460 }
 461
 462 /// GetImmediateValues - Look at Val, and pull out any additions of constants
 463 /// that can fit into the immediate field of instructions in the target.
 464 static SCEVHandle GetImmediateValues(SCEVHandle Val, bool isAddress) {
 465   if (!isAddress)
 466     return SCEVUnknown::getIntegerSCEV(0, Val->getType());
 467   if (isTargetConstant(Val))
 468     return Val;
 469
 470   SCEVAddExpr *SAE = dyn_cast<SCEVAddExpr>(Val);
 471   if (SAE) {
 472     unsigned i = 0;
 473     for (; i != SAE->getNumOperands(); ++i)
 474       if (isTargetConstant(SAE->getOperand(i))) {
 475         SCEVHandle ImmVal = SAE->getOperand(i);
 476
 477         // If there are any other immediates that we can handle here, pull them
 478         // out too.
 479         for (++i; i != SAE->getNumOperands(); ++i)
 480           if (isTargetConstant(SAE->getOperand(i)))
 481             ImmVal = SCEVAddExpr::get(ImmVal, SAE->getOperand(i));
 482         return ImmVal;
 483       }
 484   }
 485
 486   return SCEVUnknown::getIntegerSCEV(0, Val->getType());
 487 }
 488
 489 /// StrengthReduceStridedIVUsers - Strength reduce all of the users of a single
 490 /// stride of IV.  All of the users may have different starting values, and this
 491 /// may not be the only stride (we know it is if isOnlyStride is true).
 492 void LoopStrengthReduce::StrengthReduceStridedIVUsers(Value *Stride,
 493                                                       IVUse &Uses, Loop *L,
 494                                                       bool isOnlyStride) {
 495   // Transform our list of users and offsets to a bit more complex table.  In
 496   // this new vector, the first entry for each element is the base of the
 497   // strided access, and the second is the BasedUser object for the use.  We
 498   // progressively move information from the first to the second entry, until we
 499   // eventually emit the object.
 500   std::vector<std::pair<SCEVHandle, BasedUser> > UsersToProcess;
 501   UsersToProcess.reserve(Uses.Users.size());
 502
 503   SCEVHandle ZeroBase = SCEVUnknown::getIntegerSCEV(0,
 504                                               Uses.Users[0].first->getType());
 505
 506   for (unsigned i = 0, e = Uses.Users.size(); i != e; ++i)
 507     UsersToProcess.push_back(std::make_pair(Uses.Users[i].first,
 508                                             BasedUser(Uses.Users[i].second,
 509                                                       Uses.UserOperands[i],
 510                                                       ZeroBase)));
 511
 512   // First pass, figure out what we can represent in the immediate fields of
 513   // instructions.  If we can represent anything there, move it to the imm
 514   // fields of the BasedUsers.
 515   for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) {
 516     bool isAddress = isa<LoadInst>(UsersToProcess[i].second.Inst) ||
 517                      isa<StoreInst>(UsersToProcess[i].second.Inst);
 518     UsersToProcess[i].second.Imm = GetImmediateValues(UsersToProcess[i].first,
 519                                                       isAddress);
 520     UsersToProcess[i].first = SCEV::getMinusSCEV(UsersToProcess[i].first,
 521                                                  UsersToProcess[i].second.Imm);
 522
 523     DEBUG(std::cerr << "BASE: " << *UsersToProcess[i].first);
 524     DEBUG(UsersToProcess[i].second.dump());
 525   }
 526
 527   SCEVExpander Rewriter(*SE, *LI);
 528   BasicBlock  *Preheader = L->getLoopPreheader();
 529   Instruction *PreInsertPt = Preheader->getTerminator();
 530   Instruction *PhiInsertBefore = L->getHeader()->begin();
 531
 532   assert(isa<PHINode>(PhiInsertBefore) &&
 533          "How could this loop have IV's without any phis?");
 534   PHINode *SomeLoopPHI = cast<PHINode>(PhiInsertBefore);
 535   assert(SomeLoopPHI->getNumIncomingValues() == 2 &&
 536          "This loop isn't canonicalized right");
 537   BasicBlock *LatchBlock =
 538    SomeLoopPHI->getIncomingBlock(SomeLoopPHI->getIncomingBlock(0) == Preheader);
 539
 540   // FIXME: This loop needs increasing levels of intelligence.
 541   // STAGE 0: just emit everything as its own base.  <-- We are here
 542   // STAGE 1: factor out common vars from bases, and try and push resulting
 543   //          constants into Imm field.
 544   // STAGE 2: factor out large constants to try and make more constants
 545   //          acceptable for target loads and stores.
 546   std::sort(UsersToProcess.begin(), UsersToProcess.end());
 547
 548   while (!UsersToProcess.empty()) {
 549     // Create a new Phi for this base, and stick it in the loop header.
 550     Value *Replaced = UsersToProcess.front().second.Op;
 551     const Type *ReplacedTy = Replaced->getType();
 552     PHINode *NewPHI = new PHINode(ReplacedTy, Replaced->getName()+".str",
 553                                   PhiInsertBefore);
 554
 555     // Emit the initial base value into the loop preheader, and add it to the
 556     // Phi node.
 557     Value *BaseV = Rewriter.expandCodeFor(UsersToProcess.front().first,
 558                                           PreInsertPt, ReplacedTy);
 559     NewPHI->addIncoming(BaseV, Preheader);
 560
 561     // Emit the increment of the base value before the terminator of the loop
 562     // latch block, and add it to the Phi node.
 563     SCEVHandle Inc = SCEVAddExpr::get(SCEVUnknown::get(NewPHI),
 564                                       SCEVUnknown::get(Stride));
 565
 566     Value *IncV = Rewriter.expandCodeFor(Inc, LatchBlock->getTerminator(),
 567                                          ReplacedTy);
 568     IncV->setName(NewPHI->getName()+".inc");
 569     NewPHI->addIncoming(IncV, LatchBlock);
 570
 571     // Emit the code to add the immediate offset to the Phi value, just before
 572     // the instruction that we identified as using this stride and base.
 573     // First, empty the SCEVExpander's expression map  so that we are guaranteed
 574     // to have the code emitted where we expect it.
 575     Rewriter.clear();
 576     SCEVHandle NewValSCEV = SCEVAddExpr::get(SCEVUnknown::get(NewPHI),
 577                                              UsersToProcess.front().second.Imm);
 578     Value *newVal = Rewriter.expandCodeFor(NewValSCEV,
 579                                            UsersToProcess.front().second.Inst,
 580                                            ReplacedTy);
 581
 582     // Replace the use of the operand Value with the new Phi we just created.
 583     DEBUG(std::cerr << "REPLACING: " << *Replaced << "IN: " <<
 584           *UsersToProcess.front().second.Inst << "WITH: "<< *newVal << '\n');
 585     UsersToProcess.front().second.Inst->replaceUsesOfWith(Replaced, newVal);
 586
 587     // Mark old value we replaced as possibly dead, so that it is elminated
 588     // if we just replaced the last use of that value.
 589     DeadInsts.insert(cast<Instruction>(Replaced));
 590
 591     UsersToProcess.erase(UsersToProcess.begin());
 592     ++NumReduced;
 593
 594     // TODO: Next, find out which base index is the most common, pull it out.
 595   }
 596
 597   // IMPORTANT TODO: Figure out how to partition the IV's with this stride, but
 598   // different starting values, into different PHIs.
 599
 600   // BEFORE writing this, it's probably useful to handle GEP's.
 601
 602   // NOTE: pull all constants together, for REG+IMM addressing, include &GV in
 603   // 'IMM' if the target supports it.
 604 }
 605
 606
 607 void LoopStrengthReduce::runOnLoop(Loop *L) {
 608   // First step, transform all loops nesting inside of this loop.
 609   for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I)
 610     runOnLoop(*I);
 611
 612   // Next, find all uses of induction variables in this loop, and catagorize
 613   // them by stride.  Start by finding all of the PHI nodes in the header for
 614   // this loop.  If they are induction variables, inspect their uses.
 615   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
 616     AddUsersIfInteresting(I, L);
 617
 618   // If we have nothing to do, return.
 619   //if (IVUsesByStride.empty()) return;
 620
 621   // FIXME: We can widen subreg IV's here for RISC targets.  e.g. instead of
 622   // doing computation in byte values, promote to 32-bit values if safe.
 623
 624   // FIXME: Attempt to reuse values across multiple IV's.  In particular, we
 625   // could have something like "for(i) { foo(i*8); bar(i*16) }", which should be
 626   // codegened as "for (j = 0;; j+=8) { foo(j); bar(j+j); }" on X86/PPC.  Need
 627   // to be careful that IV's are all the same type.  Only works for intptr_t
 628   // indvars.
 629
 630   // If we only have one stride, we can more aggressively eliminate some things.
 631   bool HasOneStride = IVUsesByStride.size() == 1;
 632
 633   for (std::map<Value*, IVUse>::iterator SI = IVUsesByStride.begin(),
 634          E = IVUsesByStride.end(); SI != E; ++SI)
 635     StrengthReduceStridedIVUsers(SI->first, SI->second, L, HasOneStride);
 636
 637   // Clean up after ourselves
 638   if (!DeadInsts.empty()) {
 639     DeleteTriviallyDeadInstructions(DeadInsts);
 640
 641     BasicBlock::iterator I = L->getHeader()->begin();
 642     PHINode *PN;
 643     while ((PN = dyn_cast<PHINode>(I))) {
 644       ++I;  // Preincrement iterator to avoid invalidating it when deleting PN.
 645
 646       // At this point, we know that we have killed one or more GEP instructions.
 647       // It is worth checking to see if the cann indvar is also dead, so that we
 648       // can remove it as well.  The requirements for the cann indvar to be
 649       // considered dead are:
 650       // 1. the cann indvar has one use
 651       // 2. the use is an add instruction
 652       // 3. the add has one use
 653       // 4. the add is used by the cann indvar
 654       // If all four cases above are true, then we can remove both the add and
 655       // the cann indvar.
 656       // FIXME: this needs to eliminate an induction variable even if it's being
 657       // compared against some value to decide loop termination.
 658       if (PN->hasOneUse()) {
 659         BinaryOperator *BO = dyn_cast<BinaryOperator>(*(PN->use_begin()));
 660         if (BO && BO->hasOneUse()) {
 661           if (PN == *(BO->use_begin())) {
 662             DeadInsts.insert(BO);
 663             // Break the cycle, then delete the PHI.
 664             PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 665             SE->deleteInstructionFromRecords(PN);
 666             PN->eraseFromParent();
 667           }
 668         }
 669       }
 670     }
 671     DeleteTriviallyDeadInstructions(DeadInsts);
 672   }
 673
 674   IVUsesByStride.clear();
 675   CastedBasePointers.clear();
 676   return;
 677 }