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