lib/Transforms/Scalar/StraightLineStrengthReduce.cpp

   1 //===-- StraightLineStrengthReduce.cpp - ------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements straight-line strength reduction (SLSR). Unlike loop
  11 // strength reduction, this algorithm is designed to reduce arithmetic
  12 // redundancy in straight-line code instead of loops. It has proven to be
  13 // effective in simplifying arithmetic statements derived from an unrolled loop.
  14 // It can also simplify the logic of SeparateConstOffsetFromGEP.
  15 //
  16 // There are many optimizations we can perform in the domain of SLSR. This file
  17 // for now contains only an initial step. Specifically, we look for strength
  18 // reduction candidates in the following forms:
  19 //
  20 // Form 1: B + i * S
  21 // Form 2: (B + i) * S
  22 // Form 3: &B[i * S]
  23 //
  24 // where S is an integer variable, and i is a constant integer. If we found two
  25 // candidates S1 and S2 in the same form and S1 dominates S2, we may rewrite S2
  26 // in a simpler way with respect to S1. For example,
  27 //
  28 // S1: X = B + i * S
  29 // S2: Y = B + i' * S   => X + (i' - i) * S
  30 //
  31 // S1: X = (B + i) * S
  32 // S2: Y = (B + i') * S => X + (i' - i) * S
  33 //
  34 // S1: X = &B[i * S]
  35 // S2: Y = &B[i' * S]   => &X[(i' - i) * S]
  36 //
  37 // Note: (i' - i) * S is folded to the extent possible.
  38 //
  39 // This rewriting is in general a good idea. The code patterns we focus on
  40 // usually come from loop unrolling, so (i' - i) * S is likely the same
  41 // across iterations and can be reused. When that happens, the optimized form
  42 // takes only one add starting from the second iteration.
  43 //
  44 // When such rewriting is possible, we call S1 a "basis" of S2. When S2 has
  45 // multiple bases, we choose to rewrite S2 with respect to its "immediate"
  46 // basis, the basis that is the closest ancestor in the dominator tree.
  47 //
  48 // TODO:
  49 //
  50 // - Floating point arithmetics when fast math is enabled.
  51 //
  52 // - SLSR may decrease ILP at the architecture level. Targets that are very
  53 //   sensitive to ILP may want to disable it. Having SLSR to consider ILP is
  54 //   left as future work.
  55 //
  56 // - When (i' - i) is constant but i and i' are not, we could still perform
  57 //   SLSR.
  58 #include <vector>
  59
  60 #include "llvm/ADT/DenseSet.h"
  61 #include "llvm/ADT/FoldingSet.h"
  62 #include "llvm/Analysis/ScalarEvolution.h"
  63 #include "llvm/Analysis/TargetTransformInfo.h"
  64 #include "llvm/IR/DataLayout.h"
  65 #include "llvm/IR/Dominators.h"
  66 #include "llvm/IR/IRBuilder.h"
  67 #include "llvm/IR/Module.h"
  68 #include "llvm/IR/PatternMatch.h"
  69 #include "llvm/Support/raw_ostream.h"
  70 #include "llvm/Transforms/Scalar.h"
  71 #include "llvm/Transforms/Utils/Local.h"
  72
  73 using namespace llvm;
  74 using namespace PatternMatch;
  75
  76 namespace {
  77
  78 class StraightLineStrengthReduce : public FunctionPass {
  79 public:
  80   // SLSR candidate. Such a candidate must be in one of the forms described in
  81   // the header comments.
  82   struct Candidate : public ilist_node<Candidate> {
  83     enum Kind {
  84       Invalid, // reserved for the default constructor
  85       Add,     // B + i * S
  86       Mul,     // (B + i) * S
  87       GEP,     // &B[..][i * S][..]
  88     };
  89
  90     Candidate()
  91         : CandidateKind(Invalid), Base(nullptr), Index(nullptr),
  92           Stride(nullptr), Ins(nullptr), Basis(nullptr) {}
  93     Candidate(Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
  94               Instruction *I)
  95         : CandidateKind(CT), Base(B), Index(Idx), Stride(S), Ins(I),
  96           Basis(nullptr) {}
  97     Kind CandidateKind;
  98     const SCEV *Base;
  99     // Note that Index and Stride of a GEP candidate do not necessarily have the
 100     // same integer type. In that case, during rewriting, Stride will be
 101     // sign-extended or truncated to Index's type.
 102     ConstantInt *Index;
 103     Value *Stride;
 104     // The instruction this candidate corresponds to. It helps us to rewrite a
 105     // candidate with respect to its immediate basis. Note that one instruction
 106     // can correspond to multiple candidates depending on how you associate the
 107     // expression. For instance,
 108     //
 109     // (a + 1) * (b + 2)
 110     //
 111     // can be treated as
 112     //
 113     // <Base: a, Index: 1, Stride: b + 2>
 114     //
 115     // or
 116     //
 117     // <Base: b, Index: 2, Stride: a + 1>
 118     Instruction *Ins;
 119     // Points to the immediate basis of this candidate, or nullptr if we cannot
 120     // find any basis for this candidate.
 121     Candidate *Basis;
 122   };
 123
 124   static char ID;
 125
 126   StraightLineStrengthReduce()
 127       : FunctionPass(ID), DL(nullptr), DT(nullptr), TTI(nullptr) {
 128     initializeStraightLineStrengthReducePass(*PassRegistry::getPassRegistry());
 129   }
 130
 131   void getAnalysisUsage(AnalysisUsage &AU) const override {
 132     AU.addRequired<DominatorTreeWrapperPass>();
 133     AU.addRequired<ScalarEvolution>();
 134     AU.addRequired<TargetTransformInfoWrapperPass>();
 135     // We do not modify the shape of the CFG.
 136     AU.setPreservesCFG();
 137   }
 138
 139   bool doInitialization(Module &M) override {
 140     DL = &M.getDataLayout();
 141     return false;
 142   }
 143
 144   bool runOnFunction(Function &F) override;
 145
 146 private:
 147   // Returns true if Basis is a basis for C, i.e., Basis dominates C and they
 148   // share the same base and stride.
 149   bool isBasisFor(const Candidate &Basis, const Candidate &C);
 150   // Returns whether the candidate can be folded into an addressing mode.
 151   bool isFoldable(const Candidate &C, TargetTransformInfo *TTI,
 152                   const DataLayout *DL);
 153   // Returns true if C is already in a simplest form and not worth being
 154   // rewritten.
 155   bool isSimplestForm(const Candidate &C);
 156   // Checks whether I is in a candidate form. If so, adds all the matching forms
 157   // to Candidates, and tries to find the immediate basis for each of them.
 158   void allocateCandidatesAndFindBasis(Instruction *I);
 159   // Allocate candidates and find bases for Add instructions.
 160   void allocateCandidatesAndFindBasisForAdd(Instruction *I);
 161   // Given I = LHS + RHS, factors RHS into i * S and makes (LHS + i * S) a
 162   // candidate.
 163   void allocateCandidatesAndFindBasisForAdd(Value *LHS, Value *RHS,
 164                                             Instruction *I);
 165   // Allocate candidates and find bases for Mul instructions.
 166   void allocateCandidatesAndFindBasisForMul(Instruction *I);
 167   // Splits LHS into Base + Index and, if succeeds, calls
 168   // allocateCandidatesAndFindBasis.
 169   void allocateCandidatesAndFindBasisForMul(Value *LHS, Value *RHS,
 170                                             Instruction *I);
 171   // Allocate candidates and find bases for GetElementPtr instructions.
 172   void allocateCandidatesAndFindBasisForGEP(GetElementPtrInst *GEP);
 173   // A helper function that scales Idx with ElementSize before invoking
 174   // allocateCandidatesAndFindBasis.
 175   void allocateCandidatesAndFindBasisForGEP(const SCEV *B, ConstantInt *Idx,
 176                                             Value *S, uint64_t ElementSize,
 177                                             Instruction *I);
 178   // Adds the given form <CT, B, Idx, S> to Candidates, and finds its immediate
 179   // basis.
 180   void allocateCandidatesAndFindBasis(Candidate::Kind CT, const SCEV *B,
 181                                       ConstantInt *Idx, Value *S,
 182                                       Instruction *I);
 183   // Rewrites candidate C with respect to Basis.
 184   void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis);
 185   // A helper function that factors ArrayIdx to a product of a stride and a
 186   // constant index, and invokes allocateCandidatesAndFindBasis with the
 187   // factorings.
 188   void factorArrayIndex(Value *ArrayIdx, const SCEV *Base, uint64_t ElementSize,
 189                         GetElementPtrInst *GEP);
 190   // Emit code that computes the "bump" from Basis to C. If the candidate is a
 191   // GEP and the bump is not divisible by the element size of the GEP, this
 192   // function sets the BumpWithUglyGEP flag to notify its caller to bump the
 193   // basis using an ugly GEP.
 194   static Value *emitBump(const Candidate &Basis, const Candidate &C,
 195                          IRBuilder<> &Builder, const DataLayout *DL,
 196                          bool &BumpWithUglyGEP);
 197
 198   const DataLayout *DL;
 199   DominatorTree *DT;
 200   ScalarEvolution *SE;
 201   TargetTransformInfo *TTI;
 202   ilist<Candidate> Candidates;
 203   // Temporarily holds all instructions that are unlinked (but not deleted) by
 204   // rewriteCandidateWithBasis. These instructions will be actually removed
 205   // after all rewriting finishes.
 206   std::vector<Instruction *> UnlinkedInstructions;
 207 };
 208 }  // anonymous namespace
 209
 210 char StraightLineStrengthReduce::ID = 0;
 211 INITIALIZE_PASS_BEGIN(StraightLineStrengthReduce, "slsr",
 212                       "Straight line strength reduction", false, false)
 213 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 214 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 215 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 216 INITIALIZE_PASS_END(StraightLineStrengthReduce, "slsr",
 217                     "Straight line strength reduction", false, false)
 218
 219 FunctionPass *llvm::createStraightLineStrengthReducePass() {
 220   return new StraightLineStrengthReduce();
 221 }
 222
 223 bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis,
 224                                             const Candidate &C) {
 225   return (Basis.Ins != C.Ins && // skip the same instruction
 226           // Basis must dominate C in order to rewrite C with respect to Basis.
 227           DT->dominates(Basis.Ins->getParent(), C.Ins->getParent()) &&
 228           // They share the same base, stride, and candidate kind.
 229           Basis.Base == C.Base &&
 230           Basis.Stride == C.Stride &&
 231           Basis.CandidateKind == C.CandidateKind);
 232 }
 233
 234 static bool isGEPFoldable(GetElementPtrInst *GEP,
 235                           const TargetTransformInfo *TTI,
 236                           const DataLayout *DL) {
 237   GlobalVariable *BaseGV = nullptr;
 238   int64_t BaseOffset = 0;
 239   bool HasBaseReg = false;
 240   int64_t Scale = 0;
 241
 242   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getPointerOperand()))
 243     BaseGV = GV;
 244   else
 245     HasBaseReg = true;
 246
 247   gep_type_iterator GTI = gep_type_begin(GEP);
 248   for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I, ++GTI) {
 249     if (isa<SequentialType>(*GTI)) {
 250       int64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType());
 251       if (ConstantInt *ConstIdx = dyn_cast<ConstantInt>(*I)) {
 252         BaseOffset += ConstIdx->getSExtValue() * ElementSize;
 253       } else {
 254         // Needs scale register.
 255         if (Scale != 0) {
 256           // No addressing mode takes two scale registers.
 257           return false;
 258         }
 259         Scale = ElementSize;
 260       }
 261     } else {
 262       StructType *STy = cast<StructType>(*GTI);
 263       uint64_t Field = cast<ConstantInt>(*I)->getZExtValue();
 264       BaseOffset += DL->getStructLayout(STy)->getElementOffset(Field);
 265     }
 266   }
 267   return TTI->isLegalAddressingMode(GEP->getType()->getElementType(), BaseGV,
 268                                     BaseOffset, HasBaseReg, Scale);
 269 }
 270
 271 // Returns whether (Base + Index * Stride) can be folded to an addressing mode.
 272 static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride,
 273                           TargetTransformInfo *TTI) {
 274   return TTI->isLegalAddressingMode(Base->getType(), nullptr, 0, true,
 275                                     Index->getSExtValue());
 276 }
 277
 278 bool StraightLineStrengthReduce::isFoldable(const Candidate &C,
 279                                             TargetTransformInfo *TTI,
 280                                             const DataLayout *DL) {
 281   if (C.CandidateKind == Candidate::Add)
 282     return isAddFoldable(C.Base, C.Index, C.Stride, TTI);
 283   if (C.CandidateKind == Candidate::GEP)
 284     return isGEPFoldable(cast<GetElementPtrInst>(C.Ins), TTI, DL);
 285   return false;
 286 }
 287
 288 // Returns true if GEP has zero or one non-zero index.
 289 static bool hasOnlyOneNonZeroIndex(GetElementPtrInst *GEP) {
 290   unsigned NumNonZeroIndices = 0;
 291   for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) {
 292     ConstantInt *ConstIdx = dyn_cast<ConstantInt>(*I);
 293     if (ConstIdx == nullptr || !ConstIdx->isZero())
 294       ++NumNonZeroIndices;
 295   }
 296   return NumNonZeroIndices <= 1;
 297 }
 298
 299 bool StraightLineStrengthReduce::isSimplestForm(const Candidate &C) {
 300   if (C.CandidateKind == Candidate::Add) {
 301     // B + 1 * S or B + (-1) * S
 302     return C.Index->isOne() || C.Index->isMinusOne();
 303   }
 304   if (C.CandidateKind == Candidate::Mul) {
 305     // (B + 0) * S
 306     return C.Index->isZero();
 307   }
 308   if (C.CandidateKind == Candidate::GEP) {
 309     // (char*)B + S or (char*)B - S
 310     return ((C.Index->isOne() || C.Index->isMinusOne()) &&
 311             hasOnlyOneNonZeroIndex(cast<GetElementPtrInst>(C.Ins)));
 312   }
 313   return false;
 314 }
 315
 316 // TODO: We currently implement an algorithm whose time complexity is linear in
 317 // the number of existing candidates. However, we could do better by using
 318 // ScopedHashTable. Specifically, while traversing the dominator tree, we could
 319 // maintain all the candidates that dominate the basic block being traversed in
 320 // a ScopedHashTable. This hash table is indexed by the base and the stride of
 321 // a candidate. Therefore, finding the immediate basis of a candidate boils down
 322 // to one hash-table look up.
 323 void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
 324     Candidate::Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
 325     Instruction *I) {
 326   Candidate C(CT, B, Idx, S, I);
 327   // SLSR can complicate an instruction in two cases:
 328   //
 329   // 1. If we can fold I into an addressing mode, computing I is likely free or
 330   // takes only one instruction.
 331   //
 332   // 2. I is already in a simplest form. For example, when
 333   //      X = B + 8 * S
 334   //      Y = B + S,
 335   //    rewriting Y to X - 7 * S is probably a bad idea.
 336   //
 337   // In the above cases, we still add I to the candidate list so that I can be
 338   // the basis of other candidates, but we leave I's basis blank so that I
 339   // won't be rewritten.
 340   if (!isFoldable(C, TTI, DL) && !isSimplestForm(C)) {
 341     // Try to compute the immediate basis of C.
 342     unsigned NumIterations = 0;
 343     // Limit the scan radius to avoid running in quadratice time.
 344     static const unsigned MaxNumIterations = 50;
 345     for (auto Basis = Candidates.rbegin();
 346          Basis != Candidates.rend() && NumIterations < MaxNumIterations;
 347          ++Basis, ++NumIterations) {
 348       if (isBasisFor(*Basis, C)) {
 349         C.Basis = &(*Basis);
 350         break;
 351       }
 352     }
 353   }
 354   // Regardless of whether we find a basis for C, we need to push C to the
 355   // candidate list so that it can be the basis of other candidates.
 356   Candidates.push_back(C);
 357 }
 358
 359 void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
 360     Instruction *I) {
 361   switch (I->getOpcode()) {
 362   case Instruction::Add:
 363     allocateCandidatesAndFindBasisForAdd(I);
 364     break;
 365   case Instruction::Mul:
 366     allocateCandidatesAndFindBasisForMul(I);
 367     break;
 368   case Instruction::GetElementPtr:
 369     allocateCandidatesAndFindBasisForGEP(cast<GetElementPtrInst>(I));
 370     break;
 371   }
 372 }
 373
 374 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
 375     Instruction *I) {
 376   // Try matching B + i * S.
 377   if (!isa<IntegerType>(I->getType()))
 378     return;
 379
 380   assert(I->getNumOperands() == 2 && "isn't I an add?");
 381   Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
 382   allocateCandidatesAndFindBasisForAdd(LHS, RHS, I);
 383   if (LHS != RHS)
 384     allocateCandidatesAndFindBasisForAdd(RHS, LHS, I);
 385 }
 386
 387 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
 388     Value *LHS, Value *RHS, Instruction *I) {
 389   Value *S = nullptr;
 390   ConstantInt *Idx = nullptr;
 391   if (match(RHS, m_Mul(m_Value(S), m_ConstantInt(Idx)))) {
 392     // I = LHS + RHS = LHS + Idx * S
 393     allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
 394   } else if (match(RHS, m_Shl(m_Value(S), m_ConstantInt(Idx)))) {
 395     // I = LHS + RHS = LHS + (S << Idx) = LHS + S * (1 << Idx)
 396     APInt One(Idx->getBitWidth(), 1);
 397     Idx = ConstantInt::get(Idx->getContext(), One << Idx->getValue());
 398     allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
 399   } else {
 400     // At least, I = LHS + 1 * RHS
 401     ConstantInt *One = ConstantInt::get(cast<IntegerType>(I->getType()), 1);
 402     allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), One, RHS,
 403                                    I);
 404   }
 405 }
 406
 407 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
 408     Value *LHS, Value *RHS, Instruction *I) {
 409   Value *B = nullptr;
 410   ConstantInt *Idx = nullptr;
 411   // Only handle the canonical operand ordering.
 412   if (match(LHS, m_Add(m_Value(B), m_ConstantInt(Idx)))) {
 413     // If LHS is in the form of "Base + Index", then I is in the form of
 414     // "(Base + Index) * RHS".
 415     allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
 416   } else {
 417     // Otherwise, at least try the form (LHS + 0) * RHS.
 418     ConstantInt *Zero = ConstantInt::get(cast<IntegerType>(I->getType()), 0);
 419     allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), Zero, RHS,
 420                                   I);
 421   }
 422 }
 423
 424 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
 425     Instruction *I) {
 426   // Try matching (B + i) * S.
 427   // TODO: we could extend SLSR to float and vector types.
 428   if (!isa<IntegerType>(I->getType()))
 429     return;
 430
 431   assert(I->getNumOperands() == 2 && "isn't I a mul?");
 432   Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
 433   allocateCandidatesAndFindBasisForMul(LHS, RHS, I);
 434   if (LHS != RHS) {
 435     // Symmetrically, try to split RHS to Base + Index.
 436     allocateCandidatesAndFindBasisForMul(RHS, LHS, I);
 437   }
 438 }
 439
 440 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
 441     const SCEV *B, ConstantInt *Idx, Value *S, uint64_t ElementSize,
 442     Instruction *I) {
 443   // I = B + sext(Idx *nsw S) * ElementSize
 444   //   = B + (sext(Idx) * sext(S)) * ElementSize
 445   //   = B + (sext(Idx) * ElementSize) * sext(S)
 446   // Casting to IntegerType is safe because we skipped vector GEPs.
 447   IntegerType *IntPtrTy = cast<IntegerType>(DL->getIntPtrType(I->getType()));
 448   ConstantInt *ScaledIdx = ConstantInt::get(
 449       IntPtrTy, Idx->getSExtValue() * (int64_t)ElementSize, true);
 450   allocateCandidatesAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I);
 451 }
 452
 453 void StraightLineStrengthReduce::factorArrayIndex(Value *ArrayIdx,
 454                                                   const SCEV *Base,
 455                                                   uint64_t ElementSize,
 456                                                   GetElementPtrInst *GEP) {
 457   // At least, ArrayIdx = ArrayIdx *nsw 1.
 458   allocateCandidatesAndFindBasisForGEP(
 459       Base, ConstantInt::get(cast<IntegerType>(ArrayIdx->getType()), 1),
 460       ArrayIdx, ElementSize, GEP);
 461   Value *LHS = nullptr;
 462   ConstantInt *RHS = nullptr;
 463   // One alternative is matching the SCEV of ArrayIdx instead of ArrayIdx
 464   // itself. This would allow us to handle the shl case for free. However,
 465   // matching SCEVs has two issues:
 466   //
 467   // 1. this would complicate rewriting because the rewriting procedure
 468   // would have to translate SCEVs back to IR instructions. This translation
 469   // is difficult when LHS is further evaluated to a composite SCEV.
 470   //
 471   // 2. ScalarEvolution is designed to be control-flow oblivious. It tends
 472   // to strip nsw/nuw flags which are critical for SLSR to trace into
 473   // sext'ed multiplication.
 474   if (match(ArrayIdx, m_NSWMul(m_Value(LHS), m_ConstantInt(RHS)))) {
 475     // SLSR is currently unsafe if i * S may overflow.
 476     // GEP = Base + sext(LHS *nsw RHS) * ElementSize
 477     allocateCandidatesAndFindBasisForGEP(Base, RHS, LHS, ElementSize, GEP);
 478   } else if (match(ArrayIdx, m_NSWShl(m_Value(LHS), m_ConstantInt(RHS)))) {
 479     // GEP = Base + sext(LHS <<nsw RHS) * ElementSize
 480     //     = Base + sext(LHS *nsw (1 << RHS)) * ElementSize
 481     APInt One(RHS->getBitWidth(), 1);
 482     ConstantInt *PowerOf2 =
 483         ConstantInt::get(RHS->getContext(), One << RHS->getValue());
 484     allocateCandidatesAndFindBasisForGEP(Base, PowerOf2, LHS, ElementSize, GEP);
 485   }
 486 }
 487
 488 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
 489     GetElementPtrInst *GEP) {
 490   // TODO: handle vector GEPs
 491   if (GEP->getType()->isVectorTy())
 492     return;
 493
 494   const SCEV *GEPExpr = SE->getSCEV(GEP);
 495   Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
 496
 497   gep_type_iterator GTI = gep_type_begin(GEP);
 498   for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) {
 499     if (!isa<SequentialType>(*GTI++))
 500       continue;
 501     Value *ArrayIdx = *I;
 502     // Compute the byte offset of this index.
 503     uint64_t ElementSize = DL->getTypeAllocSize(*GTI);
 504     const SCEV *ElementSizeExpr = SE->getSizeOfExpr(IntPtrTy, *GTI);
 505     const SCEV *ArrayIdxExpr = SE->getSCEV(ArrayIdx);
 506     ArrayIdxExpr = SE->getTruncateOrSignExtend(ArrayIdxExpr, IntPtrTy);
 507     const SCEV *LocalOffset =
 508         SE->getMulExpr(ArrayIdxExpr, ElementSizeExpr, SCEV::FlagNSW);
 509     // The base of this candidate equals GEPExpr less the byte offset of this
 510     // index.
 511     const SCEV *Base = SE->getMinusSCEV(GEPExpr, LocalOffset);
 512     factorArrayIndex(ArrayIdx, Base, ElementSize, GEP);
 513     // When ArrayIdx is the sext of a value, we try to factor that value as
 514     // well.  Handling this case is important because array indices are
 515     // typically sign-extended to the pointer size.
 516     Value *TruncatedArrayIdx = nullptr;
 517     if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx))))
 518       factorArrayIndex(TruncatedArrayIdx, Base, ElementSize, GEP);
 519   }
 520 }
 521
 522 // A helper function that unifies the bitwidth of A and B.
 523 static void unifyBitWidth(APInt &A, APInt &B) {
 524   if (A.getBitWidth() < B.getBitWidth())
 525     A = A.sext(B.getBitWidth());
 526   else if (A.getBitWidth() > B.getBitWidth())
 527     B = B.sext(A.getBitWidth());
 528 }
 529
 530 Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,
 531                                             const Candidate &C,
 532                                             IRBuilder<> &Builder,
 533                                             const DataLayout *DL,
 534                                             bool &BumpWithUglyGEP) {
 535   APInt Idx = C.Index->getValue(), BasisIdx = Basis.Index->getValue();
 536   unifyBitWidth(Idx, BasisIdx);
 537   APInt IndexOffset = Idx - BasisIdx;
 538
 539   BumpWithUglyGEP = false;
 540   if (Basis.CandidateKind == Candidate::GEP) {
 541     APInt ElementSize(
 542         IndexOffset.getBitWidth(),
 543         DL->getTypeAllocSize(
 544             cast<GetElementPtrInst>(Basis.Ins)->getType()->getElementType()));
 545     APInt Q, R;
 546     APInt::sdivrem(IndexOffset, ElementSize, Q, R);
 547     if (R.getSExtValue() == 0)
 548       IndexOffset = Q;
 549     else
 550       BumpWithUglyGEP = true;
 551   }
 552
 553   // Compute Bump = C - Basis = (i' - i) * S.
 554   // Common case 1: if (i' - i) is 1, Bump = S.
 555   if (IndexOffset.getSExtValue() == 1)
 556     return C.Stride;
 557   // Common case 2: if (i' - i) is -1, Bump = -S.
 558   if (IndexOffset.getSExtValue() == -1)
 559     return Builder.CreateNeg(C.Stride);
 560
 561   // Otherwise, Bump = (i' - i) * sext/trunc(S). Note that (i' - i) and S may
 562   // have different bit widths.
 563   IntegerType *DeltaType =
 564       IntegerType::get(Basis.Ins->getContext(), IndexOffset.getBitWidth());
 565   Value *ExtendedStride = Builder.CreateSExtOrTrunc(C.Stride, DeltaType);
 566   if (IndexOffset.isPowerOf2()) {
 567     // If (i' - i) is a power of 2, Bump = sext/trunc(S) << log(i' - i).
 568     ConstantInt *Exponent = ConstantInt::get(DeltaType, IndexOffset.logBase2());
 569     return Builder.CreateShl(ExtendedStride, Exponent);
 570   }
 571   if ((-IndexOffset).isPowerOf2()) {
 572     // If (i - i') is a power of 2, Bump = -sext/trunc(S) << log(i' - i).
 573     ConstantInt *Exponent =
 574         ConstantInt::get(DeltaType, (-IndexOffset).logBase2());
 575     return Builder.CreateNeg(Builder.CreateShl(ExtendedStride, Exponent));
 576   }
 577   Constant *Delta = ConstantInt::get(DeltaType, IndexOffset);
 578   return Builder.CreateMul(ExtendedStride, Delta);
 579 }
 580
 581 void StraightLineStrengthReduce::rewriteCandidateWithBasis(
 582     const Candidate &C, const Candidate &Basis) {
 583   assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base &&
 584          C.Stride == Basis.Stride);
 585   // We run rewriteCandidateWithBasis on all candidates in a post-order, so the
 586   // basis of a candidate cannot be unlinked before the candidate.
 587   assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked");
 588
 589   // An instruction can correspond to multiple candidates. Therefore, instead of
 590   // simply deleting an instruction when we rewrite it, we mark its parent as
 591   // nullptr (i.e. unlink it) so that we can skip the candidates whose
 592   // instruction is already rewritten.
 593   if (!C.Ins->getParent())
 594     return;
 595
 596   IRBuilder<> Builder(C.Ins);
 597   bool BumpWithUglyGEP;
 598   Value *Bump = emitBump(Basis, C, Builder, DL, BumpWithUglyGEP);
 599   Value *Reduced = nullptr; // equivalent to but weaker than C.Ins
 600   switch (C.CandidateKind) {
 601   case Candidate::Add:
 602   case Candidate::Mul:
 603     // C = Basis + Bump
 604     if (BinaryOperator::isNeg(Bump)) {
 605       // If Bump is a neg instruction, emit C = Basis - (-Bump).
 606       Reduced =
 607           Builder.CreateSub(Basis.Ins, BinaryOperator::getNegArgument(Bump));
 608       // We only use the negative argument of Bump, and Bump itself may be
 609       // trivially dead.
 610       RecursivelyDeleteTriviallyDeadInstructions(Bump);
 611     } else {
 612       Reduced = Builder.CreateAdd(Basis.Ins, Bump);
 613     }
 614     break;
 615   case Candidate::GEP:
 616     {
 617       Type *IntPtrTy = DL->getIntPtrType(C.Ins->getType());
 618       bool InBounds = cast<GetElementPtrInst>(C.Ins)->isInBounds();
 619       if (BumpWithUglyGEP) {
 620         // C = (char *)Basis + Bump
 621         unsigned AS = Basis.Ins->getType()->getPointerAddressSpace();
 622         Type *CharTy = Type::getInt8PtrTy(Basis.Ins->getContext(), AS);
 623         Reduced = Builder.CreateBitCast(Basis.Ins, CharTy);
 624         if (InBounds)
 625           Reduced =
 626               Builder.CreateInBoundsGEP(Builder.getInt8Ty(), Reduced, Bump);
 627         else
 628           Reduced = Builder.CreateGEP(Builder.getInt8Ty(), Reduced, Bump);
 629         Reduced = Builder.CreateBitCast(Reduced, C.Ins->getType());
 630       } else {
 631         // C = gep Basis, Bump
 632         // Canonicalize bump to pointer size.
 633         Bump = Builder.CreateSExtOrTrunc(Bump, IntPtrTy);
 634         if (InBounds)
 635           Reduced = Builder.CreateInBoundsGEP(nullptr, Basis.Ins, Bump);
 636         else
 637           Reduced = Builder.CreateGEP(nullptr, Basis.Ins, Bump);
 638       }
 639     }
 640     break;
 641   default:
 642     llvm_unreachable("C.CandidateKind is invalid");
 643   };
 644   Reduced->takeName(C.Ins);
 645   C.Ins->replaceAllUsesWith(Reduced);
 646   // Unlink C.Ins so that we can skip other candidates also corresponding to
 647   // C.Ins. The actual deletion is postponed to the end of runOnFunction.
 648   C.Ins->removeFromParent();
 649   UnlinkedInstructions.push_back(C.Ins);
 650 }
 651
 652 bool StraightLineStrengthReduce::runOnFunction(Function &F) {
 653   if (skipOptnoneFunction(F))
 654     return false;
 655
 656   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 657   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 658   SE = &getAnalysis<ScalarEvolution>();
 659   // Traverse the dominator tree in the depth-first order. This order makes sure
 660   // all bases of a candidate are in Candidates when we process it.
 661   for (auto node = GraphTraits<DominatorTree *>::nodes_begin(DT);
 662        node != GraphTraits<DominatorTree *>::nodes_end(DT); ++node) {
 663     for (auto &I : *node->getBlock())
 664       allocateCandidatesAndFindBasis(&I);
 665   }
 666
 667   // Rewrite candidates in the reverse depth-first order. This order makes sure
 668   // a candidate being rewritten is not a basis for any other candidate.
 669   while (!Candidates.empty()) {
 670     const Candidate &C = Candidates.back();
 671     if (C.Basis != nullptr) {
 672       rewriteCandidateWithBasis(C, *C.Basis);
 673     }
 674     Candidates.pop_back();
 675   }
 676
 677   // Delete all unlink instructions.
 678   for (auto *UnlinkedInst : UnlinkedInstructions) {
 679     for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; ++I) {
 680       Value *Op = UnlinkedInst->getOperand(I);
 681       UnlinkedInst->setOperand(I, nullptr);
 682       RecursivelyDeleteTriviallyDeadInstructions(Op);
 683     }
 684     delete UnlinkedInst;
 685   }
 686   bool Ret = !UnlinkedInstructions.empty();
 687   UnlinkedInstructions.clear();
 688   return Ret;
 689 }