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