X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FStraightLineStrengthReduce.cpp;h=453503ab61da66a433d472a5475b087bb53a161c;hb=4d3b6d43ccb62f3bfdbae650541e88514f24a16b;hp=3c1916f923e8102a082e240f86a50027f6095a04;hpb=cf57d81b6ef8623e9503f3c5b2477a92b5e2a552;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp b/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp index 3c1916f923e..453503ab61d 100644 --- a/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp +++ b/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp @@ -15,48 +15,53 @@ // // There are many optimizations we can perform in the domain of SLSR. This file // for now contains only an initial step. Specifically, we look for strength -// reduction candidates in two forms: +// reduction candidates in the following forms: // -// Form 1: (B + i) * S -// Form 2: &B[i * S] +// Form 1: B + i * S +// Form 2: (B + i) * S +// Form 3: &B[i * S] // // where S is an integer variable, and i is a constant integer. If we found two -// candidates +// candidates S1 and S2 in the same form and S1 dominates S2, we may rewrite S2 +// in a simpler way with respect to S1. For example, // -// S1: X = (B + i) * S -// S2: Y = (B + i') * S +// S1: X = B + i * S +// S2: Y = B + i' * S => X + (i' - i) * S // -// or +// S1: X = (B + i) * S +// S2: Y = (B + i') * S => X + (i' - i) * S // // S1: X = &B[i * S] -// S2: Y = &B[i' * S] -// -// and S1 dominates S2, we call S1 a basis of S2, and can replace S2 with -// -// Y = X + (i' - i) * S +// S2: Y = &B[i' * S] => &X[(i' - i) * S] // -// or +// Note: (i' - i) * S is folded to the extent possible. // -// Y = &X[(i' - i) * S] +// This rewriting is in general a good idea. The code patterns we focus on +// usually come from loop unrolling, so (i' - i) * S is likely the same +// across iterations and can be reused. When that happens, the optimized form +// takes only one add starting from the second iteration. // -// where (i' - i) * S is folded to the extent possible. When S2 has multiple -// bases, we pick the one that is closest to S2, or S2's "immediate" basis. +// When such rewriting is possible, we call S1 a "basis" of S2. When S2 has +// multiple bases, we choose to rewrite S2 with respect to its "immediate" +// basis, the basis that is the closest ancestor in the dominator tree. // // TODO: // -// - Handle candidates in the form of B + i * S -// // - Floating point arithmetics when fast math is enabled. // // - SLSR may decrease ILP at the architecture level. Targets that are very // sensitive to ILP may want to disable it. Having SLSR to consider ILP is // left as future work. +// +// - When (i' - i) is constant but i and i' are not, we could still perform +// SLSR. #include #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" @@ -64,6 +69,7 @@ #include "llvm/IR/PatternMatch.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Local.h" using namespace llvm; using namespace PatternMatch; @@ -72,13 +78,12 @@ namespace { class StraightLineStrengthReduce : public FunctionPass { public: - // SLSR candidate. Such a candidate must be in the form of - // (Base + Index) * Stride - // or - // Base[..][Index * Stride][..] + // SLSR candidate. Such a candidate must be in one of the forms described in + // the header comments. struct Candidate : public ilist_node { enum Kind { Invalid, // reserved for the default constructor + Add, // B + i * S Mul, // (B + i) * S GEP, // &B[..][i * S][..] }; @@ -92,14 +97,14 @@ public: Basis(nullptr) {} Kind CandidateKind; const SCEV *Base; - // Note that Index and Stride of a GEP candidate may not have the same - // integer type. In that case, during rewriting, Stride will be + // Note that Index and Stride of a GEP candidate do not necessarily have the + // same integer type. In that case, during rewriting, Stride will be // sign-extended or truncated to Index's type. ConstantInt *Index; Value *Stride; // The instruction this candidate corresponds to. It helps us to rewrite a // candidate with respect to its immediate basis. Note that one instruction - // can corresponds to multiple candidates depending on how you associate the + // can correspond to multiple candidates depending on how you associate the // expression. For instance, // // (a + 1) * (b + 2) @@ -143,31 +148,43 @@ private: // Returns true if Basis is a basis for C, i.e., Basis dominates C and they // share the same base and stride. bool isBasisFor(const Candidate &Basis, const Candidate &C); + // Returns whether the candidate can be folded into an addressing mode. + bool isFoldable(const Candidate &C, TargetTransformInfo *TTI, + const DataLayout *DL); + // Returns true if C is already in a simplest form and not worth being + // rewritten. + bool isSimplestForm(const Candidate &C); // Checks whether I is in a candidate form. If so, adds all the matching forms // to Candidates, and tries to find the immediate basis for each of them. - void allocateCandidateAndFindBasis(Instruction *I); + void allocateCandidatesAndFindBasis(Instruction *I); + // Allocate candidates and find bases for Add instructions. + void allocateCandidatesAndFindBasisForAdd(Instruction *I); + // Given I = LHS + RHS, factors RHS into i * S and makes (LHS + i * S) a + // candidate. + void allocateCandidatesAndFindBasisForAdd(Value *LHS, Value *RHS, + Instruction *I); // Allocate candidates and find bases for Mul instructions. - void allocateCandidateAndFindBasisForMul(Instruction *I); + void allocateCandidatesAndFindBasisForMul(Instruction *I); // Splits LHS into Base + Index and, if succeeds, calls - // allocateCandidateAndFindBasis. - void allocateCandidateAndFindBasisForMul(Value *LHS, Value *RHS, - Instruction *I); + // allocateCandidatesAndFindBasis. + void allocateCandidatesAndFindBasisForMul(Value *LHS, Value *RHS, + Instruction *I); // Allocate candidates and find bases for GetElementPtr instructions. - void allocateCandidateAndFindBasisForGEP(GetElementPtrInst *GEP); + void allocateCandidatesAndFindBasisForGEP(GetElementPtrInst *GEP); // A helper function that scales Idx with ElementSize before invoking - // allocateCandidateAndFindBasis. - void allocateCandidateAndFindBasisForGEP(const SCEV *B, ConstantInt *Idx, - Value *S, uint64_t ElementSize, - Instruction *I); + // allocateCandidatesAndFindBasis. + void allocateCandidatesAndFindBasisForGEP(const SCEV *B, ConstantInt *Idx, + Value *S, uint64_t ElementSize, + Instruction *I); // Adds the given form to Candidates, and finds its immediate // basis. - void allocateCandidateAndFindBasis(Candidate::Kind CT, const SCEV *B, - ConstantInt *Idx, Value *S, - Instruction *I); + void allocateCandidatesAndFindBasis(Candidate::Kind CT, const SCEV *B, + ConstantInt *Idx, Value *S, + Instruction *I); // Rewrites candidate C with respect to Basis. void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis); // A helper function that factors ArrayIdx to a product of a stride and a - // constant index, and invokes allocateCandidateAndFindBasis with the + // constant index, and invokes allocateCandidatesAndFindBasis with the // factorings. void factorArrayIndex(Value *ArrayIdx, const SCEV *Base, uint64_t ElementSize, GetElementPtrInst *GEP); @@ -187,7 +204,7 @@ private: // Temporarily holds all instructions that are unlinked (but not deleted) by // rewriteCandidateWithBasis. These instructions will be actually removed // after all rewriting finishes. - DenseSet UnlinkedInstructions; + std::vector UnlinkedInstructions; }; } // anonymous namespace @@ -215,9 +232,9 @@ bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis, Basis.CandidateKind == C.CandidateKind); } -static bool isCompletelyFoldable(GetElementPtrInst *GEP, - const TargetTransformInfo *TTI, - const DataLayout *DL) { +static bool isGEPFoldable(GetElementPtrInst *GEP, + const TargetTransformInfo *TTI, + const DataLayout *DL) { GlobalVariable *BaseGV = nullptr; int64_t BaseOffset = 0; bool HasBaseReg = false; @@ -252,85 +269,193 @@ static bool isCompletelyFoldable(GetElementPtrInst *GEP, BaseOffset, HasBaseReg, Scale); } -// TODO: We currently implement an algorithm whose time complexity is linear to -// the number of existing candidates. However, a better algorithm exists. We -// could depth-first search the dominator tree, and maintain a hash table that -// contains all candidates that dominate the node being traversed. This hash -// table is indexed by the base and the stride of a candidate. Therefore, -// finding the immediate basis of a candidate boils down to one hash-table look -// up. -void StraightLineStrengthReduce::allocateCandidateAndFindBasis( - Candidate::Kind CT, const SCEV *B, ConstantInt *Idx, Value *S, - Instruction *I) { - if (GetElementPtrInst *GEP = dyn_cast(I)) { - // If &B[Idx * S] fits into an addressing mode, do not turn it into - // non-free computation. - if (isCompletelyFoldable(GEP, TTI, DL)) - return; +// Returns whether (Base + Index * Stride) can be folded to an addressing mode. +static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride, + TargetTransformInfo *TTI) { + return TTI->isLegalAddressingMode(Base->getType(), nullptr, 0, true, + Index->getSExtValue()); +} + +bool StraightLineStrengthReduce::isFoldable(const Candidate &C, + TargetTransformInfo *TTI, + const DataLayout *DL) { + if (C.CandidateKind == Candidate::Add) + return isAddFoldable(C.Base, C.Index, C.Stride, TTI); + if (C.CandidateKind == Candidate::GEP) + return isGEPFoldable(cast(C.Ins), TTI, DL); + return false; +} + +// Returns true if GEP has zero or one non-zero index. +static bool hasOnlyOneNonZeroIndex(GetElementPtrInst *GEP) { + unsigned NumNonZeroIndices = 0; + for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) { + ConstantInt *ConstIdx = dyn_cast(*I); + if (ConstIdx == nullptr || !ConstIdx->isZero()) + ++NumNonZeroIndices; + } + return NumNonZeroIndices <= 1; +} + +bool StraightLineStrengthReduce::isSimplestForm(const Candidate &C) { + if (C.CandidateKind == Candidate::Add) { + // B + 1 * S or B + (-1) * S + return C.Index->isOne() || C.Index->isMinusOne(); + } + if (C.CandidateKind == Candidate::Mul) { + // (B + 0) * S + return C.Index->isZero(); + } + if (C.CandidateKind == Candidate::GEP) { + // (char*)B + S or (char*)B - S + return ((C.Index->isOne() || C.Index->isMinusOne()) && + hasOnlyOneNonZeroIndex(cast(C.Ins))); } + return false; +} +// TODO: We currently implement an algorithm whose time complexity is linear in +// the number of existing candidates. However, we could do better by using +// ScopedHashTable. Specifically, while traversing the dominator tree, we could +// maintain all the candidates that dominate the basic block being traversed in +// a ScopedHashTable. This hash table is indexed by the base and the stride of +// a candidate. Therefore, finding the immediate basis of a candidate boils down +// to one hash-table look up. +void StraightLineStrengthReduce::allocateCandidatesAndFindBasis( + Candidate::Kind CT, const SCEV *B, ConstantInt *Idx, Value *S, + Instruction *I) { Candidate C(CT, B, Idx, S, I); - // Try to compute the immediate basis of C. - unsigned NumIterations = 0; - // Limit the scan radius to avoid running forever. - static const unsigned MaxNumIterations = 50; - for (auto Basis = Candidates.rbegin(); - Basis != Candidates.rend() && NumIterations < MaxNumIterations; - ++Basis, ++NumIterations) { - if (isBasisFor(*Basis, C)) { - C.Basis = &(*Basis); - break; + // SLSR can complicate an instruction in two cases: + // + // 1. If we can fold I into an addressing mode, computing I is likely free or + // takes only one instruction. + // + // 2. I is already in a simplest form. For example, when + // X = B + 8 * S + // Y = B + S, + // rewriting Y to X - 7 * S is probably a bad idea. + // + // In the above cases, we still add I to the candidate list so that I can be + // the basis of other candidates, but we leave I's basis blank so that I + // won't be rewritten. + if (!isFoldable(C, TTI, DL) && !isSimplestForm(C)) { + // Try to compute the immediate basis of C. + unsigned NumIterations = 0; + // Limit the scan radius to avoid running in quadratice time. + static const unsigned MaxNumIterations = 50; + for (auto Basis = Candidates.rbegin(); + Basis != Candidates.rend() && NumIterations < MaxNumIterations; + ++Basis, ++NumIterations) { + if (isBasisFor(*Basis, C)) { + C.Basis = &(*Basis); + break; + } } } // Regardless of whether we find a basis for C, we need to push C to the - // candidate list. + // candidate list so that it can be the basis of other candidates. Candidates.push_back(C); } -void StraightLineStrengthReduce::allocateCandidateAndFindBasis(Instruction *I) { +void StraightLineStrengthReduce::allocateCandidatesAndFindBasis( + Instruction *I) { switch (I->getOpcode()) { + case Instruction::Add: + allocateCandidatesAndFindBasisForAdd(I); + break; case Instruction::Mul: - allocateCandidateAndFindBasisForMul(I); + allocateCandidatesAndFindBasisForMul(I); break; case Instruction::GetElementPtr: - allocateCandidateAndFindBasisForGEP(cast(I)); + allocateCandidatesAndFindBasisForGEP(cast(I)); break; } } -void StraightLineStrengthReduce::allocateCandidateAndFindBasisForMul( +void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd( + Instruction *I) { + // Try matching B + i * S. + if (!isa(I->getType())) + return; + + assert(I->getNumOperands() == 2 && "isn't I an add?"); + Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); + allocateCandidatesAndFindBasisForAdd(LHS, RHS, I); + if (LHS != RHS) + allocateCandidatesAndFindBasisForAdd(RHS, LHS, I); +} + +void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd( + Value *LHS, Value *RHS, Instruction *I) { + Value *S = nullptr; + ConstantInt *Idx = nullptr; + if (match(RHS, m_Mul(m_Value(S), m_ConstantInt(Idx)))) { + // I = LHS + RHS = LHS + Idx * S + allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I); + } else if (match(RHS, m_Shl(m_Value(S), m_ConstantInt(Idx)))) { + // I = LHS + RHS = LHS + (S << Idx) = LHS + S * (1 << Idx) + APInt One(Idx->getBitWidth(), 1); + Idx = ConstantInt::get(Idx->getContext(), One << Idx->getValue()); + allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I); + } else { + // At least, I = LHS + 1 * RHS + ConstantInt *One = ConstantInt::get(cast(I->getType()), 1); + allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), One, RHS, + I); + } +} + +// Returns true if A matches B + C where C is constant. +static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C) { + return (match(A, m_Add(m_Value(B), m_ConstantInt(C))) || + match(A, m_Add(m_ConstantInt(C), m_Value(B)))); +} + +// Returns true if A matches B | C where C is constant. +static bool matchesOr(Value *A, Value *&B, ConstantInt *&C) { + return (match(A, m_Or(m_Value(B), m_ConstantInt(C))) || + match(A, m_Or(m_ConstantInt(C), m_Value(B)))); +} + +void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul( Value *LHS, Value *RHS, Instruction *I) { Value *B = nullptr; ConstantInt *Idx = nullptr; - // Only handle the canonical operand ordering. - if (match(LHS, m_Add(m_Value(B), m_ConstantInt(Idx)))) { + if (matchesAdd(LHS, B, Idx)) { // If LHS is in the form of "Base + Index", then I is in the form of // "(Base + Index) * RHS". - allocateCandidateAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I); + allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I); + } else if (matchesOr(LHS, B, Idx) && haveNoCommonBitsSet(B, Idx, *DL)) { + // If LHS is in the form of "Base | Index" and Base and Index have no common + // bits set, then + // Base | Index = Base + Index + // and I is thus in the form of "(Base + Index) * RHS". + allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I); } else { // Otherwise, at least try the form (LHS + 0) * RHS. ConstantInt *Zero = ConstantInt::get(cast(I->getType()), 0); - allocateCandidateAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), Zero, RHS, - I); + allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), Zero, RHS, + I); } } -void StraightLineStrengthReduce::allocateCandidateAndFindBasisForMul( +void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul( Instruction *I) { // Try matching (B + i) * S. // TODO: we could extend SLSR to float and vector types. if (!isa(I->getType())) return; + assert(I->getNumOperands() == 2 && "isn't I a mul?"); Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); - allocateCandidateAndFindBasisForMul(LHS, RHS, I); + allocateCandidatesAndFindBasisForMul(LHS, RHS, I); if (LHS != RHS) { // Symmetrically, try to split RHS to Base + Index. - allocateCandidateAndFindBasisForMul(RHS, LHS, I); + allocateCandidatesAndFindBasisForMul(RHS, LHS, I); } } -void StraightLineStrengthReduce::allocateCandidateAndFindBasisForGEP( +void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP( const SCEV *B, ConstantInt *Idx, Value *S, uint64_t ElementSize, Instruction *I) { // I = B + sext(Idx *nsw S) * ElementSize @@ -340,21 +465,19 @@ void StraightLineStrengthReduce::allocateCandidateAndFindBasisForGEP( IntegerType *IntPtrTy = cast(DL->getIntPtrType(I->getType())); ConstantInt *ScaledIdx = ConstantInt::get( IntPtrTy, Idx->getSExtValue() * (int64_t)ElementSize, true); - allocateCandidateAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I); + allocateCandidatesAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I); } void StraightLineStrengthReduce::factorArrayIndex(Value *ArrayIdx, const SCEV *Base, uint64_t ElementSize, GetElementPtrInst *GEP) { - // At least, ArrayIdx = ArrayIdx *s 1. - allocateCandidateAndFindBasisForGEP( + // At least, ArrayIdx = ArrayIdx *nsw 1. + allocateCandidatesAndFindBasisForGEP( Base, ConstantInt::get(cast(ArrayIdx->getType()), 1), ArrayIdx, ElementSize, GEP); Value *LHS = nullptr; ConstantInt *RHS = nullptr; - // TODO: handle shl. e.g., we could treat (S << 2) as (S * 4). - // // One alternative is matching the SCEV of ArrayIdx instead of ArrayIdx // itself. This would allow us to handle the shl case for free. However, // matching SCEVs has two issues: @@ -369,41 +492,51 @@ void StraightLineStrengthReduce::factorArrayIndex(Value *ArrayIdx, if (match(ArrayIdx, m_NSWMul(m_Value(LHS), m_ConstantInt(RHS)))) { // SLSR is currently unsafe if i * S may overflow. // GEP = Base + sext(LHS *nsw RHS) * ElementSize - allocateCandidateAndFindBasisForGEP(Base, RHS, LHS, ElementSize, GEP); + allocateCandidatesAndFindBasisForGEP(Base, RHS, LHS, ElementSize, GEP); + } else if (match(ArrayIdx, m_NSWShl(m_Value(LHS), m_ConstantInt(RHS)))) { + // GEP = Base + sext(LHS <getBitWidth(), 1); + ConstantInt *PowerOf2 = + ConstantInt::get(RHS->getContext(), One << RHS->getValue()); + allocateCandidatesAndFindBasisForGEP(Base, PowerOf2, LHS, ElementSize, GEP); } } -void StraightLineStrengthReduce::allocateCandidateAndFindBasisForGEP( +void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP( GetElementPtrInst *GEP) { // TODO: handle vector GEPs if (GEP->getType()->isVectorTy()) return; - const SCEV *GEPExpr = SE->getSCEV(GEP); - Type *IntPtrTy = DL->getIntPtrType(GEP->getType()); + SmallVector IndexExprs; + for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) + IndexExprs.push_back(SE->getSCEV(*I)); gep_type_iterator GTI = gep_type_begin(GEP); - for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) { + for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I) { if (!isa(*GTI++)) continue; - Value *ArrayIdx = *I; - // Compute the byte offset of this index. + + const SCEV *OrigIndexExpr = IndexExprs[I - 1]; + IndexExprs[I - 1] = SE->getConstant(OrigIndexExpr->getType(), 0); + + // The base of this candidate is GEP's base plus the offsets of all + // indices except this current one. + const SCEV *BaseExpr = SE->getGEPExpr(GEP->getSourceElementType(), + SE->getSCEV(GEP->getPointerOperand()), + IndexExprs, GEP->isInBounds()); + Value *ArrayIdx = GEP->getOperand(I); uint64_t ElementSize = DL->getTypeAllocSize(*GTI); - const SCEV *ElementSizeExpr = SE->getSizeOfExpr(IntPtrTy, *GTI); - const SCEV *ArrayIdxExpr = SE->getSCEV(ArrayIdx); - ArrayIdxExpr = SE->getTruncateOrSignExtend(ArrayIdxExpr, IntPtrTy); - const SCEV *LocalOffset = - SE->getMulExpr(ArrayIdxExpr, ElementSizeExpr, SCEV::FlagNSW); - // The base of this candidate equals GEPExpr less the byte offset of this - // index. - const SCEV *Base = SE->getMinusSCEV(GEPExpr, LocalOffset); - factorArrayIndex(ArrayIdx, Base, ElementSize, GEP); + factorArrayIndex(ArrayIdx, BaseExpr, ElementSize, GEP); // When ArrayIdx is the sext of a value, we try to factor that value as // well. Handling this case is important because array indices are // typically sign-extended to the pointer size. Value *TruncatedArrayIdx = nullptr; if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx)))) - factorArrayIndex(TruncatedArrayIdx, Base, ElementSize, GEP); + factorArrayIndex(TruncatedArrayIdx, BaseExpr, ElementSize, GEP); + + IndexExprs[I - 1] = OrigIndexExpr; } } @@ -437,6 +570,7 @@ Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis, else BumpWithUglyGEP = true; } + // Compute Bump = C - Basis = (i' - i) * S. // Common case 1: if (i' - i) is 1, Bump = S. if (IndexOffset.getSExtValue() == 1) @@ -444,9 +578,24 @@ Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis, // Common case 2: if (i' - i) is -1, Bump = -S. if (IndexOffset.getSExtValue() == -1) return Builder.CreateNeg(C.Stride); - // Otherwise, Bump = (i' - i) * sext/trunc(S). - ConstantInt *Delta = ConstantInt::get(Basis.Ins->getContext(), IndexOffset); - Value *ExtendedStride = Builder.CreateSExtOrTrunc(C.Stride, Delta->getType()); + + // Otherwise, Bump = (i' - i) * sext/trunc(S). Note that (i' - i) and S may + // have different bit widths. + IntegerType *DeltaType = + IntegerType::get(Basis.Ins->getContext(), IndexOffset.getBitWidth()); + Value *ExtendedStride = Builder.CreateSExtOrTrunc(C.Stride, DeltaType); + if (IndexOffset.isPowerOf2()) { + // If (i' - i) is a power of 2, Bump = sext/trunc(S) << log(i' - i). + ConstantInt *Exponent = ConstantInt::get(DeltaType, IndexOffset.logBase2()); + return Builder.CreateShl(ExtendedStride, Exponent); + } + if ((-IndexOffset).isPowerOf2()) { + // If (i - i') is a power of 2, Bump = -sext/trunc(S) << log(i' - i). + ConstantInt *Exponent = + ConstantInt::get(DeltaType, (-IndexOffset).logBase2()); + return Builder.CreateNeg(Builder.CreateShl(ExtendedStride, Exponent)); + } + Constant *Delta = ConstantInt::get(DeltaType, IndexOffset); return Builder.CreateMul(ExtendedStride, Delta); } @@ -454,6 +603,9 @@ void StraightLineStrengthReduce::rewriteCandidateWithBasis( const Candidate &C, const Candidate &Basis) { assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base && C.Stride == Basis.Stride); + // We run rewriteCandidateWithBasis on all candidates in a post-order, so the + // basis of a candidate cannot be unlinked before the candidate. + assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked"); // An instruction can correspond to multiple candidates. Therefore, instead of // simply deleting an instruction when we rewrite it, we mark its parent as @@ -467,8 +619,19 @@ void StraightLineStrengthReduce::rewriteCandidateWithBasis( Value *Bump = emitBump(Basis, C, Builder, DL, BumpWithUglyGEP); Value *Reduced = nullptr; // equivalent to but weaker than C.Ins switch (C.CandidateKind) { + case Candidate::Add: case Candidate::Mul: - Reduced = Builder.CreateAdd(Basis.Ins, Bump); + // C = Basis + Bump + if (BinaryOperator::isNeg(Bump)) { + // If Bump is a neg instruction, emit C = Basis - (-Bump). + Reduced = + Builder.CreateSub(Basis.Ins, BinaryOperator::getNegArgument(Bump)); + // We only use the negative argument of Bump, and Bump itself may be + // trivially dead. + RecursivelyDeleteTriviallyDeadInstructions(Bump); + } else { + Reduced = Builder.CreateAdd(Basis.Ins, Bump); + } break; case Candidate::GEP: { @@ -480,7 +643,8 @@ void StraightLineStrengthReduce::rewriteCandidateWithBasis( Type *CharTy = Type::getInt8PtrTy(Basis.Ins->getContext(), AS); Reduced = Builder.CreateBitCast(Basis.Ins, CharTy); if (InBounds) - Reduced = Builder.CreateInBoundsGEP(Reduced, Bump); + Reduced = + Builder.CreateInBoundsGEP(Builder.getInt8Ty(), Reduced, Bump); else Reduced = Builder.CreateGEP(Builder.getInt8Ty(), Reduced, Bump); Reduced = Builder.CreateBitCast(Reduced, C.Ins->getType()); @@ -489,7 +653,7 @@ void StraightLineStrengthReduce::rewriteCandidateWithBasis( // Canonicalize bump to pointer size. Bump = Builder.CreateSExtOrTrunc(Bump, IntPtrTy); if (InBounds) - Reduced = Builder.CreateInBoundsGEP(Basis.Ins, Bump); + Reduced = Builder.CreateInBoundsGEP(nullptr, Basis.Ins, Bump); else Reduced = Builder.CreateGEP(nullptr, Basis.Ins, Bump); } @@ -500,11 +664,10 @@ void StraightLineStrengthReduce::rewriteCandidateWithBasis( }; Reduced->takeName(C.Ins); C.Ins->replaceAllUsesWith(Reduced); - C.Ins->dropAllReferences(); // Unlink C.Ins so that we can skip other candidates also corresponding to // C.Ins. The actual deletion is postponed to the end of runOnFunction. C.Ins->removeFromParent(); - UnlinkedInstructions.insert(C.Ins); + UnlinkedInstructions.push_back(C.Ins); } bool StraightLineStrengthReduce::runOnFunction(Function &F) { @@ -519,7 +682,7 @@ bool StraightLineStrengthReduce::runOnFunction(Function &F) { for (auto node = GraphTraits::nodes_begin(DT); node != GraphTraits::nodes_end(DT); ++node) { for (auto &I : *node->getBlock()) - allocateCandidateAndFindBasis(&I); + allocateCandidatesAndFindBasis(&I); } // Rewrite candidates in the reverse depth-first order. This order makes sure @@ -533,8 +696,13 @@ bool StraightLineStrengthReduce::runOnFunction(Function &F) { } // Delete all unlink instructions. - for (auto I : UnlinkedInstructions) { - delete I; + for (auto *UnlinkedInst : UnlinkedInstructions) { + for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; ++I) { + Value *Op = UnlinkedInst->getOperand(I); + UnlinkedInst->setOperand(I, nullptr); + RecursivelyDeleteTriviallyDeadInstructions(Op); + } + delete UnlinkedInst; } bool Ret = !UnlinkedInstructions.empty(); UnlinkedInstructions.clear();