736 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements straight-line strength reduction (SLSR). Unlike loop10// strength reduction, this algorithm is designed to reduce arithmetic11// redundancy in straight-line code instead of loops. It has proven to be12// 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 file16// for now contains only an initial step. Specifically, we look for strength17// reduction candidates in the following forms:18//19// Form 1: B + i * S20// Form 2: (B + i) * S21// Form 3: &B[i * S]22//23// where S is an integer variable, and i is a constant integer. If we found two24// candidates S1 and S2 in the same form and S1 dominates S2, we may rewrite S225// in a simpler way with respect to S1. For example,26//27// S1: X = B + i * S28// S2: Y = B + i' * S => X + (i' - i) * S29//30// S1: X = (B + i) * S31// S2: Y = (B + i') * S => X + (i' - i) * S32//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 on39// usually come from loop unrolling, so (i' - i) * S is likely the same40// across iterations and can be reused. When that happens, the optimized form41// 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 has44// 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 very52// sensitive to ILP may want to disable it. Having SLSR to consider ILP is53// left as future work.54//55// - When (i' - i) is constant but i and i' are not, we could still perform56// 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/Instruction.h"72#include "llvm/IR/Instructions.h"73#include "llvm/IR/Module.h"74#include "llvm/IR/Operator.h"75#include "llvm/IR/PatternMatch.h"76#include "llvm/IR/Type.h"77#include "llvm/IR/Value.h"78#include "llvm/InitializePasses.h"79#include "llvm/Pass.h"80#include "llvm/Support/Casting.h"81#include "llvm/Support/DebugCounter.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 91using namespace llvm;92using namespace PatternMatch;93 94static const unsigned UnknownAddressSpace =95 std::numeric_limits<unsigned>::max();96 97DEBUG_COUNTER(StraightLineStrengthReduceCounter, "slsr-counter",98 "Controls whether rewriteCandidateWithBasis is executed.");99 100namespace {101 102class StraightLineStrengthReduceLegacyPass : public FunctionPass {103 const DataLayout *DL = nullptr;104 105public:106 static char ID;107 108 StraightLineStrengthReduceLegacyPass() : FunctionPass(ID) {109 initializeStraightLineStrengthReduceLegacyPassPass(110 *PassRegistry::getPassRegistry());111 }112 113 void getAnalysisUsage(AnalysisUsage &AU) const override {114 AU.addRequired<DominatorTreeWrapperPass>();115 AU.addRequired<ScalarEvolutionWrapperPass>();116 AU.addRequired<TargetTransformInfoWrapperPass>();117 // We do not modify the shape of the CFG.118 AU.setPreservesCFG();119 }120 121 bool doInitialization(Module &M) override {122 DL = &M.getDataLayout();123 return false;124 }125 126 bool runOnFunction(Function &F) override;127};128 129class StraightLineStrengthReduce {130public:131 StraightLineStrengthReduce(const DataLayout *DL, DominatorTree *DT,132 ScalarEvolution *SE, TargetTransformInfo *TTI)133 : DL(DL), DT(DT), SE(SE), TTI(TTI) {}134 135 // SLSR candidate. Such a candidate must be in one of the forms described in136 // the header comments.137 struct Candidate {138 enum Kind {139 Invalid, // reserved for the default constructor140 Add, // B + i * S141 Mul, // (B + i) * S142 GEP, // &B[..][i * S][..]143 };144 145 Candidate() = default;146 Candidate(Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,147 Instruction *I)148 : CandidateKind(CT), Base(B), Index(Idx), Stride(S), Ins(I) {}149 150 Kind CandidateKind = Invalid;151 152 const SCEV *Base = nullptr;153 154 // Note that Index and Stride of a GEP candidate do not necessarily have the155 // same integer type. In that case, during rewriting, Stride will be156 // sign-extended or truncated to Index's type.157 ConstantInt *Index = nullptr;158 159 Value *Stride = nullptr;160 161 // The instruction this candidate corresponds to. It helps us to rewrite a162 // candidate with respect to its immediate basis. Note that one instruction163 // can correspond to multiple candidates depending on how you associate the164 // expression. For instance,165 //166 // (a + 1) * (b + 2)167 //168 // can be treated as169 //170 // <Base: a, Index: 1, Stride: b + 2>171 //172 // or173 //174 // <Base: b, Index: 2, Stride: a + 1>175 Instruction *Ins = nullptr;176 177 // Points to the immediate basis of this candidate, or nullptr if we cannot178 // find any basis for this candidate.179 Candidate *Basis = nullptr;180 };181 182 bool runOnFunction(Function &F);183 184private:185 // Returns true if Basis is a basis for C, i.e., Basis dominates C and they186 // share the same base and stride.187 bool isBasisFor(const Candidate &Basis, const Candidate &C);188 189 // Returns whether the candidate can be folded into an addressing mode.190 bool isFoldable(const Candidate &C, TargetTransformInfo *TTI,191 const DataLayout *DL);192 193 // Returns true if C is already in a simplest form and not worth being194 // rewritten.195 bool isSimplestForm(const Candidate &C);196 197 // Checks whether I is in a candidate form. If so, adds all the matching forms198 // to Candidates, and tries to find the immediate basis for each of them.199 void allocateCandidatesAndFindBasis(Instruction *I);200 201 // Allocate candidates and find bases for Add instructions.202 void allocateCandidatesAndFindBasisForAdd(Instruction *I);203 204 // Given I = LHS + RHS, factors RHS into i * S and makes (LHS + i * S) a205 // candidate.206 void allocateCandidatesAndFindBasisForAdd(Value *LHS, Value *RHS,207 Instruction *I);208 // Allocate candidates and find bases for Mul instructions.209 void allocateCandidatesAndFindBasisForMul(Instruction *I);210 211 // Splits LHS into Base + Index and, if succeeds, calls212 // allocateCandidatesAndFindBasis.213 void allocateCandidatesAndFindBasisForMul(Value *LHS, Value *RHS,214 Instruction *I);215 216 // Allocate candidates and find bases for GetElementPtr instructions.217 void allocateCandidatesAndFindBasisForGEP(GetElementPtrInst *GEP);218 219 // A helper function that scales Idx with ElementSize before invoking220 // allocateCandidatesAndFindBasis.221 void allocateCandidatesAndFindBasisForGEP(const SCEV *B, ConstantInt *Idx,222 Value *S, uint64_t ElementSize,223 Instruction *I);224 225 // Adds the given form <CT, B, Idx, S> to Candidates, and finds its immediate226 // basis.227 void allocateCandidatesAndFindBasis(Candidate::Kind CT, const SCEV *B,228 ConstantInt *Idx, Value *S,229 Instruction *I);230 231 // Rewrites candidate C with respect to Basis.232 void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis);233 234 // A helper function that factors ArrayIdx to a product of a stride and a235 // constant index, and invokes allocateCandidatesAndFindBasis with the236 // factorings.237 void factorArrayIndex(Value *ArrayIdx, const SCEV *Base, uint64_t ElementSize,238 GetElementPtrInst *GEP);239 240 // Emit code that computes the "bump" from Basis to C.241 static Value *emitBump(const Candidate &Basis, const Candidate &C,242 IRBuilder<> &Builder, const DataLayout *DL);243 244 const DataLayout *DL = nullptr;245 DominatorTree *DT = nullptr;246 ScalarEvolution *SE;247 TargetTransformInfo *TTI = nullptr;248 std::list<Candidate> Candidates;249 250 // Temporarily holds all instructions that are unlinked (but not deleted) by251 // rewriteCandidateWithBasis. These instructions will be actually removed252 // after all rewriting finishes.253 std::vector<Instruction *> UnlinkedInstructions;254};255 256} // end anonymous namespace257 258char StraightLineStrengthReduceLegacyPass::ID = 0;259 260INITIALIZE_PASS_BEGIN(StraightLineStrengthReduceLegacyPass, "slsr",261 "Straight line strength reduction", false, false)262INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)263INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)264INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)265INITIALIZE_PASS_END(StraightLineStrengthReduceLegacyPass, "slsr",266 "Straight line strength reduction", false, false)267 268FunctionPass *llvm::createStraightLineStrengthReducePass() {269 return new StraightLineStrengthReduceLegacyPass();270}271 272bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis,273 const Candidate &C) {274 return (Basis.Ins != C.Ins && // skip the same instruction275 // They must have the same type too. Basis.Base == C.Base276 // doesn't guarantee their types are the same (PR23975).277 Basis.Ins->getType() == C.Ins->getType() &&278 // Basis must dominate C in order to rewrite C with respect to Basis.279 DT->dominates(Basis.Ins->getParent(), C.Ins->getParent()) &&280 // They share the same base, stride, and candidate kind.281 Basis.Base == C.Base && Basis.Stride == C.Stride &&282 Basis.CandidateKind == C.CandidateKind);283}284 285static bool isGEPFoldable(GetElementPtrInst *GEP,286 const TargetTransformInfo *TTI) {287 SmallVector<const Value *, 4> Indices(GEP->indices());288 return TTI->getGEPCost(GEP->getSourceElementType(), GEP->getPointerOperand(),289 Indices) == TargetTransformInfo::TCC_Free;290}291 292// Returns whether (Base + Index * Stride) can be folded to an addressing mode.293static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride,294 TargetTransformInfo *TTI) {295 // Index->getSExtValue() may crash if Index is wider than 64-bit.296 return Index->getBitWidth() <= 64 &&297 TTI->isLegalAddressingMode(Base->getType(), nullptr, 0, true,298 Index->getSExtValue(), UnknownAddressSpace);299}300 301bool StraightLineStrengthReduce::isFoldable(const Candidate &C,302 TargetTransformInfo *TTI,303 const DataLayout *DL) {304 if (C.CandidateKind == Candidate::Add)305 return isAddFoldable(C.Base, C.Index, C.Stride, TTI);306 if (C.CandidateKind == Candidate::GEP)307 return isGEPFoldable(cast<GetElementPtrInst>(C.Ins), TTI);308 return false;309}310 311// Returns true if GEP has zero or one non-zero index.312static bool hasOnlyOneNonZeroIndex(GetElementPtrInst *GEP) {313 unsigned NumNonZeroIndices = 0;314 for (Use &Idx : GEP->indices()) {315 ConstantInt *ConstIdx = dyn_cast<ConstantInt>(Idx);316 if (ConstIdx == nullptr || !ConstIdx->isZero())317 ++NumNonZeroIndices;318 }319 return NumNonZeroIndices <= 1;320}321 322bool StraightLineStrengthReduce::isSimplestForm(const Candidate &C) {323 if (C.CandidateKind == Candidate::Add) {324 // B + 1 * S or B + (-1) * S325 return C.Index->isOne() || C.Index->isMinusOne();326 }327 if (C.CandidateKind == Candidate::Mul) {328 // (B + 0) * S329 return C.Index->isZero();330 }331 if (C.CandidateKind == Candidate::GEP) {332 // (char*)B + S or (char*)B - S333 return ((C.Index->isOne() || C.Index->isMinusOne()) &&334 hasOnlyOneNonZeroIndex(cast<GetElementPtrInst>(C.Ins)));335 }336 return false;337}338 339// TODO: We currently implement an algorithm whose time complexity is linear in340// the number of existing candidates. However, we could do better by using341// ScopedHashTable. Specifically, while traversing the dominator tree, we could342// maintain all the candidates that dominate the basic block being traversed in343// a ScopedHashTable. This hash table is indexed by the base and the stride of344// a candidate. Therefore, finding the immediate basis of a candidate boils down345// to one hash-table look up.346void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(347 Candidate::Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,348 Instruction *I) {349 Candidate C(CT, B, Idx, S, I);350 // SLSR can complicate an instruction in two cases:351 //352 // 1. If we can fold I into an addressing mode, computing I is likely free or353 // takes only one instruction.354 //355 // 2. I is already in a simplest form. For example, when356 // X = B + 8 * S357 // Y = B + S,358 // rewriting Y to X - 7 * S is probably a bad idea.359 //360 // In the above cases, we still add I to the candidate list so that I can be361 // the basis of other candidates, but we leave I's basis blank so that I362 // won't be rewritten.363 if (!isFoldable(C, TTI, DL) && !isSimplestForm(C)) {364 // Try to compute the immediate basis of C.365 unsigned NumIterations = 0;366 // Limit the scan radius to avoid running in quadratice time.367 static const unsigned MaxNumIterations = 50;368 for (auto Basis = Candidates.rbegin();369 Basis != Candidates.rend() && NumIterations < MaxNumIterations;370 ++Basis, ++NumIterations) {371 if (isBasisFor(*Basis, C)) {372 C.Basis = &(*Basis);373 break;374 }375 }376 }377 // Regardless of whether we find a basis for C, we need to push C to the378 // candidate list so that it can be the basis of other candidates.379 Candidates.push_back(C);380}381 382void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(383 Instruction *I) {384 switch (I->getOpcode()) {385 case Instruction::Add:386 allocateCandidatesAndFindBasisForAdd(I);387 break;388 case Instruction::Mul:389 allocateCandidatesAndFindBasisForMul(I);390 break;391 case Instruction::GetElementPtr:392 allocateCandidatesAndFindBasisForGEP(cast<GetElementPtrInst>(I));393 break;394 }395}396 397void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(398 Instruction *I) {399 // Try matching B + i * S.400 if (!isa<IntegerType>(I->getType()))401 return;402 403 assert(I->getNumOperands() == 2 && "isn't I an add?");404 Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);405 allocateCandidatesAndFindBasisForAdd(LHS, RHS, I);406 if (LHS != RHS)407 allocateCandidatesAndFindBasisForAdd(RHS, LHS, I);408}409 410void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(411 Value *LHS, Value *RHS, Instruction *I) {412 Value *S = nullptr;413 ConstantInt *Idx = nullptr;414 if (match(RHS, m_Mul(m_Value(S), m_ConstantInt(Idx)))) {415 // I = LHS + RHS = LHS + Idx * S416 allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);417 } else if (match(RHS, m_Shl(m_Value(S), m_ConstantInt(Idx)))) {418 // I = LHS + RHS = LHS + (S << Idx) = LHS + S * (1 << Idx)419 APInt One(Idx->getBitWidth(), 1);420 Idx = ConstantInt::get(Idx->getContext(), One << Idx->getValue());421 allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);422 } else {423 // At least, I = LHS + 1 * RHS424 ConstantInt *One = ConstantInt::get(cast<IntegerType>(I->getType()), 1);425 allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), One, RHS,426 I);427 }428}429 430// Returns true if A matches B + C where C is constant.431static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C) {432 return match(A, m_c_Add(m_Value(B), m_ConstantInt(C)));433}434 435// Returns true if A matches B | C where C is constant.436static bool matchesOr(Value *A, Value *&B, ConstantInt *&C) {437 return match(A, m_c_Or(m_Value(B), m_ConstantInt(C)));438}439 440void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(441 Value *LHS, Value *RHS, Instruction *I) {442 Value *B = nullptr;443 ConstantInt *Idx = nullptr;444 if (matchesAdd(LHS, B, Idx)) {445 // If LHS is in the form of "Base + Index", then I is in the form of446 // "(Base + Index) * RHS".447 allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);448 } else if (matchesOr(LHS, B, Idx) && haveNoCommonBitsSet(B, Idx, *DL)) {449 // If LHS is in the form of "Base | Index" and Base and Index have no common450 // bits set, then451 // Base | Index = Base + Index452 // and I is thus in the form of "(Base + Index) * RHS".453 allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);454 } else {455 // Otherwise, at least try the form (LHS + 0) * RHS.456 ConstantInt *Zero = ConstantInt::get(cast<IntegerType>(I->getType()), 0);457 allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), Zero, RHS,458 I);459 }460}461 462void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(463 Instruction *I) {464 // Try matching (B + i) * S.465 // TODO: we could extend SLSR to float and vector types.466 if (!isa<IntegerType>(I->getType()))467 return;468 469 assert(I->getNumOperands() == 2 && "isn't I a mul?");470 Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);471 allocateCandidatesAndFindBasisForMul(LHS, RHS, I);472 if (LHS != RHS) {473 // Symmetrically, try to split RHS to Base + Index.474 allocateCandidatesAndFindBasisForMul(RHS, LHS, I);475 }476}477 478void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(479 const SCEV *B, ConstantInt *Idx, Value *S, uint64_t ElementSize,480 Instruction *I) {481 // I = B + sext(Idx *nsw S) * ElementSize482 // = B + (sext(Idx) * sext(S)) * ElementSize483 // = B + (sext(Idx) * ElementSize) * sext(S)484 // Casting to IntegerType is safe because we skipped vector GEPs.485 IntegerType *PtrIdxTy = cast<IntegerType>(DL->getIndexType(I->getType()));486 ConstantInt *ScaledIdx = ConstantInt::get(487 PtrIdxTy, Idx->getSExtValue() * (int64_t)ElementSize, true);488 allocateCandidatesAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I);489}490 491void StraightLineStrengthReduce::factorArrayIndex(Value *ArrayIdx,492 const SCEV *Base,493 uint64_t ElementSize,494 GetElementPtrInst *GEP) {495 // At least, ArrayIdx = ArrayIdx *nsw 1.496 allocateCandidatesAndFindBasisForGEP(497 Base, ConstantInt::get(cast<IntegerType>(ArrayIdx->getType()), 1),498 ArrayIdx, ElementSize, GEP);499 Value *LHS = nullptr;500 ConstantInt *RHS = nullptr;501 // One alternative is matching the SCEV of ArrayIdx instead of ArrayIdx502 // itself. This would allow us to handle the shl case for free. However,503 // matching SCEVs has two issues:504 //505 // 1. this would complicate rewriting because the rewriting procedure506 // would have to translate SCEVs back to IR instructions. This translation507 // is difficult when LHS is further evaluated to a composite SCEV.508 //509 // 2. ScalarEvolution is designed to be control-flow oblivious. It tends510 // to strip nsw/nuw flags which are critical for SLSR to trace into511 // sext'ed multiplication.512 if (match(ArrayIdx, m_NSWMul(m_Value(LHS), m_ConstantInt(RHS)))) {513 // SLSR is currently unsafe if i * S may overflow.514 // GEP = Base + sext(LHS *nsw RHS) * ElementSize515 allocateCandidatesAndFindBasisForGEP(Base, RHS, LHS, ElementSize, GEP);516 } else if (match(ArrayIdx, m_NSWShl(m_Value(LHS), m_ConstantInt(RHS)))) {517 // GEP = Base + sext(LHS <<nsw RHS) * ElementSize518 // = Base + sext(LHS *nsw (1 << RHS)) * ElementSize519 APInt One(RHS->getBitWidth(), 1);520 ConstantInt *PowerOf2 =521 ConstantInt::get(RHS->getContext(), One << RHS->getValue());522 allocateCandidatesAndFindBasisForGEP(Base, PowerOf2, LHS, ElementSize, GEP);523 }524}525 526void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(527 GetElementPtrInst *GEP) {528 // TODO: handle vector GEPs529 if (GEP->getType()->isVectorTy())530 return;531 532 SmallVector<const SCEV *, 4> IndexExprs;533 for (Use &Idx : GEP->indices())534 IndexExprs.push_back(SE->getSCEV(Idx));535 536 gep_type_iterator GTI = gep_type_begin(GEP);537 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {538 if (GTI.isStruct())539 continue;540 541 const SCEV *OrigIndexExpr = IndexExprs[I - 1];542 IndexExprs[I - 1] = SE->getZero(OrigIndexExpr->getType());543 544 // The base of this candidate is GEP's base plus the offsets of all545 // indices except this current one.546 const SCEV *BaseExpr = SE->getGEPExpr(cast<GEPOperator>(GEP), IndexExprs);547 Value *ArrayIdx = GEP->getOperand(I);548 uint64_t ElementSize = GTI.getSequentialElementStride(*DL);549 if (ArrayIdx->getType()->getIntegerBitWidth() <=550 DL->getIndexSizeInBits(GEP->getAddressSpace())) {551 // Skip factoring if ArrayIdx is wider than the index size, because552 // ArrayIdx is implicitly truncated to the index size.553 factorArrayIndex(ArrayIdx, BaseExpr, ElementSize, GEP);554 }555 // When ArrayIdx is the sext of a value, we try to factor that value as556 // well. Handling this case is important because array indices are557 // typically sign-extended to the pointer index size.558 Value *TruncatedArrayIdx = nullptr;559 if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx))) &&560 TruncatedArrayIdx->getType()->getIntegerBitWidth() <=561 DL->getIndexSizeInBits(GEP->getAddressSpace())) {562 // Skip factoring if TruncatedArrayIdx is wider than the pointer size,563 // because TruncatedArrayIdx is implicitly truncated to the pointer size.564 factorArrayIndex(TruncatedArrayIdx, BaseExpr, ElementSize, GEP);565 }566 567 IndexExprs[I - 1] = OrigIndexExpr;568 }569}570 571// A helper function that unifies the bitwidth of A and B.572static void unifyBitWidth(APInt &A, APInt &B) {573 if (A.getBitWidth() < B.getBitWidth())574 A = A.sext(B.getBitWidth());575 else if (A.getBitWidth() > B.getBitWidth())576 B = B.sext(A.getBitWidth());577}578 579Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,580 const Candidate &C,581 IRBuilder<> &Builder,582 const DataLayout *DL) {583 APInt Idx = C.Index->getValue(), BasisIdx = Basis.Index->getValue();584 unifyBitWidth(Idx, BasisIdx);585 APInt IndexOffset = Idx - BasisIdx;586 587 // Compute Bump = C - Basis = (i' - i) * S.588 // Common case 1: if (i' - i) is 1, Bump = S.589 if (IndexOffset == 1)590 return C.Stride;591 // Common case 2: if (i' - i) is -1, Bump = -S.592 if (IndexOffset.isAllOnes())593 return Builder.CreateNeg(C.Stride);594 595 // Otherwise, Bump = (i' - i) * sext/trunc(S). Note that (i' - i) and S may596 // have different bit widths.597 IntegerType *DeltaType =598 IntegerType::get(Basis.Ins->getContext(), IndexOffset.getBitWidth());599 Value *ExtendedStride = Builder.CreateSExtOrTrunc(C.Stride, DeltaType);600 if (IndexOffset.isPowerOf2()) {601 // If (i' - i) is a power of 2, Bump = sext/trunc(S) << log(i' - i).602 ConstantInt *Exponent = ConstantInt::get(DeltaType, IndexOffset.logBase2());603 return Builder.CreateShl(ExtendedStride, Exponent);604 }605 if (IndexOffset.isNegatedPowerOf2()) {606 // If (i - i') is a power of 2, Bump = -sext/trunc(S) << log(i' - i).607 ConstantInt *Exponent =608 ConstantInt::get(DeltaType, (-IndexOffset).logBase2());609 return Builder.CreateNeg(Builder.CreateShl(ExtendedStride, Exponent));610 }611 Constant *Delta = ConstantInt::get(DeltaType, IndexOffset);612 return Builder.CreateMul(ExtendedStride, Delta);613}614 615void StraightLineStrengthReduce::rewriteCandidateWithBasis(616 const Candidate &C, const Candidate &Basis) {617 if (!DebugCounter::shouldExecute(StraightLineStrengthReduceCounter))618 return;619 620 assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base &&621 C.Stride == Basis.Stride);622 // We run rewriteCandidateWithBasis on all candidates in a post-order, so the623 // basis of a candidate cannot be unlinked before the candidate.624 assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked");625 626 // An instruction can correspond to multiple candidates. Therefore, instead of627 // simply deleting an instruction when we rewrite it, we mark its parent as628 // nullptr (i.e. unlink it) so that we can skip the candidates whose629 // instruction is already rewritten.630 if (!C.Ins->getParent())631 return;632 633 IRBuilder<> Builder(C.Ins);634 Value *Bump = emitBump(Basis, C, Builder, DL);635 Value *Reduced = nullptr; // equivalent to but weaker than C.Ins636 switch (C.CandidateKind) {637 case Candidate::Add:638 case Candidate::Mul: {639 // C = Basis + Bump640 Value *NegBump;641 if (match(Bump, m_Neg(m_Value(NegBump)))) {642 // If Bump is a neg instruction, emit C = Basis - (-Bump).643 Reduced = Builder.CreateSub(Basis.Ins, NegBump);644 // We only use the negative argument of Bump, and Bump itself may be645 // trivially dead.646 RecursivelyDeleteTriviallyDeadInstructions(Bump);647 } else {648 // It's tempting to preserve nsw on Bump and/or Reduced. However, it's649 // usually unsound, e.g.,650 //651 // X = (-2 +nsw 1) *nsw INT_MAX652 // Y = (-2 +nsw 3) *nsw INT_MAX653 // =>654 // Y = X + 2 * INT_MAX655 //656 // Neither + and * in the resultant expression are nsw.657 Reduced = Builder.CreateAdd(Basis.Ins, Bump);658 }659 break;660 }661 case Candidate::GEP: {662 bool InBounds = cast<GetElementPtrInst>(C.Ins)->isInBounds();663 // C = (char *)Basis + Bump664 Reduced = Builder.CreatePtrAdd(Basis.Ins, Bump, "", InBounds);665 break;666 }667 default:668 llvm_unreachable("C.CandidateKind is invalid");669 };670 Reduced->takeName(C.Ins);671 C.Ins->replaceAllUsesWith(Reduced);672 // Unlink C.Ins so that we can skip other candidates also corresponding to673 // C.Ins. The actual deletion is postponed to the end of runOnFunction.674 C.Ins->removeFromParent();675 UnlinkedInstructions.push_back(C.Ins);676}677 678bool StraightLineStrengthReduceLegacyPass::runOnFunction(Function &F) {679 if (skipFunction(F))680 return false;681 682 auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);683 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();684 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();685 return StraightLineStrengthReduce(DL, DT, SE, TTI).runOnFunction(F);686}687 688bool StraightLineStrengthReduce::runOnFunction(Function &F) {689 // Traverse the dominator tree in the depth-first order. This order makes sure690 // all bases of a candidate are in Candidates when we process it.691 for (const auto Node : depth_first(DT))692 for (auto &I : *(Node->getBlock()))693 allocateCandidatesAndFindBasis(&I);694 695 // Rewrite candidates in the reverse depth-first order. This order makes sure696 // a candidate being rewritten is not a basis for any other candidate.697 while (!Candidates.empty()) {698 const Candidate &C = Candidates.back();699 if (C.Basis != nullptr) {700 rewriteCandidateWithBasis(C, *C.Basis);701 }702 Candidates.pop_back();703 }704 705 // Delete all unlink instructions.706 for (auto *UnlinkedInst : UnlinkedInstructions) {707 for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; ++I) {708 Value *Op = UnlinkedInst->getOperand(I);709 UnlinkedInst->setOperand(I, nullptr);710 RecursivelyDeleteTriviallyDeadInstructions(Op);711 }712 UnlinkedInst->deleteValue();713 }714 bool Ret = !UnlinkedInstructions.empty();715 UnlinkedInstructions.clear();716 return Ret;717}718 719PreservedAnalyses720StraightLineStrengthReducePass::run(Function &F, FunctionAnalysisManager &AM) {721 const DataLayout *DL = &F.getDataLayout();722 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);723 auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);724 auto *TTI = &AM.getResult<TargetIRAnalysis>(F);725 726 if (!StraightLineStrengthReduce(DL, DT, SE, TTI).runOnFunction(F))727 return PreservedAnalyses::all();728 729 PreservedAnalyses PA;730 PA.preserveSet<CFGAnalyses>();731 PA.preserve<DominatorTreeAnalysis>();732 PA.preserve<ScalarEvolutionAnalysis>();733 PA.preserve<TargetIRAnalysis>();734 return PA;735}736