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