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