Index: lib/Transforms/Scalar/StraightLineStrengthReduce.cpp =================================================================== --- lib/Transforms/Scalar/StraightLineStrengthReduce.cpp +++ lib/Transforms/Scalar/StraightLineStrengthReduce.cpp @@ -15,19 +15,30 @@ // // 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 candidate in the form of +// reduction candidates in two forms: // -// (B + i) * S +// Form 1: (B + i) * S +// Form 2: &B[i * S] // -// where B and S are integer constants or variables, and i is a constant -// integer. If we found two such candidates +// where S is an integer variable, and i is a constant integer. If we found two +// candidates // -// S1: X = (B + i) * S S2: Y = (B + i') * S +// S1: X = (B + i) * S +// S2: Y = (B + i') * S +// +// or +// +// 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 // +// or +// +// Y = &X[(i' - i) * S] +// // 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. // @@ -35,8 +46,6 @@ // // - Handle candidates in the form of B + i * S // -// - Handle candidates in the form of pointer arithmetics. e.g., B[i * S] -// // - Floating point arithmetics when fast math is enabled. // // - SLSR may decrease ILP at the architecture level. Targets that are very @@ -45,6 +54,10 @@ #include #include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Module.h" @@ -58,14 +71,27 @@ namespace { class StraightLineStrengthReduce : public FunctionPass { - public: +public: // SLSR candidate. Such a candidate must be in the form of // (Base + Index) * Stride + // or + // Base[..][Index * Stride][..] struct Candidate : public ilist_node { - Candidate(Value *B = nullptr, ConstantInt *Idx = nullptr, - Value *S = nullptr, Instruction *I = nullptr) - : Base(B), Index(Idx), Stride(S), Ins(I), Basis(nullptr) {} - Value *Base; + enum Type { + Invalid, // reserved for the default constructor + Mul, // (B + i) * S + GEP, // &B[..][i * S][..] + }; + + Candidate() + : CandidateType(Invalid), Base(nullptr), Index(nullptr), + Stride(nullptr), Ins(nullptr), Basis(nullptr) {} + Candidate(Type CT, const SCEV *B, ConstantInt *Idx, Value *S, + Instruction *I) + : CandidateType(CT), Base(B), Index(Idx), Stride(S), Ins(I), + Basis(nullptr) {} + Type CandidateType; + const SCEV *Base; ConstantInt *Index; Value *Stride; // The instruction this candidate corresponds to. It helps us to rewrite a @@ -90,33 +116,61 @@ static char ID; - StraightLineStrengthReduce() : FunctionPass(ID), DT(nullptr) { + StraightLineStrengthReduce() + : FunctionPass(ID), DL(nullptr), DT(nullptr), TTI(nullptr) { initializeStraightLineStrengthReducePass(*PassRegistry::getPassRegistry()); } void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); + AU.addRequired(); + AU.addRequired(); // We do not modify the shape of the CFG. AU.setPreservesCFG(); } + bool doInitialization(Module &M) override { + DL = &M.getDataLayout(); + return false; + } + bool runOnFunction(Function &F) override; - private: +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); // 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); - // Given that I is in the form of "(B + Idx) * S", adds this form to - // Candidates, and finds its immediate basis. - void allocateCandidateAndFindBasis(Value *B, ConstantInt *Idx, Value *S, + // Allocate candidates and find bases for Mul instructions. + void allocateCandidateAndFindBasisForMul(BinaryOperator *I); + // Allocate candidates and find bases for GetElementPtr instructions. + void allocateCandidateAndFindBasisForGEP(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); + // Adds the given form to Candidates, and finds its immediate + // basis. + void allocateCandidateAndFindBasis(Candidate::Type 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); + // Emit code that computes the "bump" from Basis to C. If the candidates are + // GEPs and the bump is divisible by the leaf element size, this function sets + // the BumpWithGEP flag to notify its caller to bump the basis using GEPs + // which keep more pointer information. + static Value *emitBump(const Candidate &Basis, const Candidate &C, + IRBuilder<> &Builder, const DataLayout *DL, + bool &BumpWithGEP); + const DataLayout *DL; DominatorTree *DT; + ScalarEvolution *SE; + TargetTransformInfo *TTI; ilist Candidates; // Temporarily holds all instructions that are unlinked (but not deleted) by // rewriteCandidateWithBasis. These instructions will be actually removed @@ -129,6 +183,8 @@ INITIALIZE_PASS_BEGIN(StraightLineStrengthReduce, "slsr", "Straight line strength reduction", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_END(StraightLineStrengthReduce, "slsr", "Straight line strength reduction", false, false) @@ -141,9 +197,47 @@ return (Basis.Ins != C.Ins && // skip the same instruction // Basis must dominate C in order to rewrite C with respect to Basis. DT->dominates(Basis.Ins->getParent(), C.Ins->getParent()) && - // They share the same base and stride. + // They share the same base, stride, and candidate type. Basis.Base == C.Base && - Basis.Stride == C.Stride); + Basis.Stride == C.Stride && + Basis.CandidateType == C.CandidateType); +} + +static bool isCompletelyFoldable(GetElementPtrInst *GEP, + const TargetTransformInfo *TTI, + const DataLayout *DL) { + GlobalVariable *BaseGV = nullptr; + int64_t BaseOffset = 0; + bool HasBaseReg = false; + int64_t Scale = 0; + + if (GlobalVariable *GV = dyn_cast(GEP->getPointerOperand())) { + BaseGV = GV; + } else { + HasBaseReg = true; + } + gep_type_iterator GTI = gep_type_begin(GEP); + for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I, ++GTI) { + if (isa(*GTI)) { + int64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType()); + if (ConstantInt *ConstIdx = dyn_cast(*I)) { + BaseOffset += ConstIdx->getSExtValue() * ElementSize; + } else { + // Needs scale register. + if (Scale != 0) { + // No addressing mode takes two scale registers. + return false; + } + Scale = ElementSize; + } + } else { + StructType *STy = cast(*GTI); + uint64_t Field = cast(*I)->getZExtValue(); + BaseOffset += DL->getStructLayout(STy)->getElementOffset(Field); + } + } + return TTI->isLegalAddressingMode(GEP->getType()->getElementType(), BaseGV, + BaseOffset, HasBaseReg, Scale); } // TODO: We currently implement an algorithm whose time complexity is linear to @@ -153,11 +247,19 @@ // 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(Value *B, - ConstantInt *Idx, - Value *S, - Instruction *I) { - Candidate C(B, Idx, S, I); +void StraightLineStrengthReduce::allocateCandidateAndFindBasis( + Candidate::Type CT, const SCEV *B, ConstantInt *Idx, Value *S, + Instruction *I) { + assert(Idx->getType() == S->getType()); + + if (GetElementPtrInst *GEP = dyn_cast(I)) { + // If &B[Idx * S] fits into an addressing mode, do not turn it into + // non-free computation. + if (TTI && isCompletelyFoldable(GEP, TTI, DL)) + return; + } + + 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. @@ -176,60 +278,179 @@ } void StraightLineStrengthReduce::allocateCandidateAndFindBasis(Instruction *I) { - Value *B = nullptr; - ConstantInt *Idx = nullptr; - // "(Base + Index) * Stride" must be a Mul instruction at the first hand. - if (I->getOpcode() == Instruction::Mul) { - if (IntegerType *ITy = dyn_cast(I->getType())) { - Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); - for (unsigned Swapped = 0; Swapped < 2; ++Swapped) { - // Only handle the canonical operand ordering. - if (match(LHS, m_Add(m_Value(B), m_ConstantInt(Idx)))) { - // If LHS is in the form of "Base + Index", then I is in the form of - // "(Base + Index) * RHS". - allocateCandidateAndFindBasis(B, Idx, RHS, I); - } else { - // Otherwise, at least try the form (LHS + 0) * RHS. - allocateCandidateAndFindBasis(LHS, ConstantInt::get(ITy, 0), RHS, I); + switch (I->getOpcode()) { + case Instruction::Mul: + allocateCandidateAndFindBasisForMul(cast(I)); + break; + case Instruction::GetElementPtr: + allocateCandidateAndFindBasisForGEP(cast(I)); + break; + } +} + +void StraightLineStrengthReduce::allocateCandidateAndFindBasisForMul( + BinaryOperator *I) { + // Try matching (B + i) * S. + // TODO: we could extend SLSR to float and vector types. + IntegerType *ITy = dyn_cast(I->getType()); + if (!ITy) + return; + + Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); + for (unsigned Swapped = 0; Swapped < 2; ++Swapped) { + Value *B = nullptr; + ConstantInt *Idx = nullptr; + // Only handle the canonical operand ordering. + if (match(LHS, m_Add(m_Value(B), m_ConstantInt(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); + } else { + // Otherwise, at least try the form (LHS + 0) * RHS. + allocateCandidateAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), + ConstantInt::get(ITy, 0), RHS, I); + } + // Swap LHS and RHS so that we also cover the cases where LHS is the stride. + if (LHS == RHS) + break; + std::swap(LHS, RHS); + } +} + +void StraightLineStrengthReduce::allocateCandidateAndFindBasisForGEP( + const SCEV *B, ConstantInt *Idx, Value *S, uint64_t ElementSize, + Instruction *I) { + // I = B + sext(Idx *s S) *s ElementSize + APInt MaxValue = APInt::getSignedMaxValue(Idx->getType()->getBitWidth()); + if (MaxValue.getZExtValue() >= ElementSize) { + // In most cases, we can simplify the expression by pushing ElementSize into + // the sext. We then have I = B + sext((Idx * ElementSize) *s S). + ConstantInt *ScaledIdx = ConstantInt::get( + Idx->getType(), Idx->getSExtValue() * (int64_t)ElementSize, true); + allocateCandidateAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I); + } +} + +void StraightLineStrengthReduce::allocateCandidateAndFindBasisForGEP( + GetElementPtrInst *GEP) { + // TODO: handle vector GEPs + if (GEP->getType()->isVectorTy()) + return; + + const SCEV *GEPExpr = SE->getSCEV(GEP); + Type *IntPtrTy = DL->getIntPtrType(GEP->getType()); + + gep_type_iterator GTI = gep_type_begin(GEP); + for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) { + if (!isa(*GTI++)) + continue; + Value *Idx = *I; + // Compute the byte offset of this index. + uint64_t ElementSize = DL->getTypeAllocSize(*GTI); + const SCEV *ElementSizeExpr = SE->getSizeOfExpr(IntPtrTy, *GTI); + const SCEV *IdxExpr = SE->getSCEV(Idx); + IdxExpr = SE->getTruncateOrSignExtend(IdxExpr, IntPtrTy); + const SCEV *LocalOffset = + SE->getMulExpr(IdxExpr, ElementSizeExpr, SCEV::FlagNSW); + // The base of this candidate equals GEPExpr less the byte offset of this + // index. + const SCEV *Base = SE->getMinusSCEV(GEPExpr, LocalOffset); + for (unsigned Stripped = 0; Stripped < 2; ++Stripped) { + // At least, Idx = Idx *s 1. + allocateCandidateAndFindBasisForGEP( + Base, ConstantInt::get(cast(Idx->getType()), 1), Idx, + ElementSize, GEP); + Value *LHS = nullptr; + ConstantInt *RHS = nullptr; + // TODO: handle shl. e.g., we could treat (S << 2) as (S * 4). + if (match(Idx, m_Mul(m_Value(LHS), m_ConstantInt(RHS)))) { + // SLSR is currently unsafe if i * S may overflow. + if (cast(Idx)->hasNoSignedWrap()) { + // GEP = Base + sext(LHS *s RHS) *s ElementSize + allocateCandidateAndFindBasisForGEP(Base, RHS, LHS, ElementSize, GEP); } - // Swap LHS and RHS so that we also cover the cases where LHS is the - // stride. - if (LHS == RHS) - break; - std::swap(LHS, RHS); } + // Strips the sext from LastIdx and try factoring again. + if (!match(Idx, m_SExt(m_Value(Idx)))) + break; + } + } +} + +Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis, + const Candidate &C, + IRBuilder<> &Builder, + const DataLayout *DL, + bool &BumpWithGEP) { + BumpWithGEP = false; + APInt IndexOffset = C.Index->getValue() - Basis.Index->getValue(); + if (Basis.CandidateType == Candidate::GEP) { + APInt ElementSize( + IndexOffset.getBitWidth(), + DL->getTypeAllocSize( + cast(Basis.Ins)->getType()->getElementType())); + APInt Q, R; + APInt::sdivrem(IndexOffset, ElementSize, Q, R); + if (R.getSExtValue() == 0) { + BumpWithGEP = true; + IndexOffset = Q; } } + // Compute Bump = C - Basis = (i' - i) * S. + if (IndexOffset.getSExtValue() == 1) { + // If (i' - i) is 1, Bump = S. + return C.Stride; + } + if (IndexOffset.getSExtValue() == -1) { + // If (i' - i) is -1, Bump = -S. + return Builder.CreateNeg(C.Stride); + } + // Otherwise, Bump = (i' - i) * S. + return Builder.CreateMul( + C.Stride, ConstantInt::get(Basis.Ins->getContext(), IndexOffset)); } void StraightLineStrengthReduce::rewriteCandidateWithBasis( const Candidate &C, const Candidate &Basis) { + assert(C.CandidateType == Basis.CandidateType && C.Base == Basis.Base && + C.Stride == Basis.Stride); + // An instruction can correspond to multiple candidates. Therefore, instead of // simply deleting an instruction when we rewrite it, we mark its parent as // nullptr (i.e. unlink it) so that we can skip the candidates whose // instruction is already rewritten. if (!C.Ins->getParent()) return; - assert(C.Base == Basis.Base && C.Stride == Basis.Stride); - // Basis = (B + i) * S - // C = (B + i') * S - // ==> - // C = Basis + (i' - i) * S + IRBuilder<> Builder(C.Ins); - ConstantInt *IndexOffset = ConstantInt::get( - C.Ins->getContext(), C.Index->getValue() - Basis.Index->getValue()); - Value *Reduced; - // TODO: preserve nsw/nuw in some cases. - if (IndexOffset->isOne()) { - // If (i' - i) is 1, fold C into Basis + S. - Reduced = Builder.CreateAdd(Basis.Ins, C.Stride); - } else if (IndexOffset->isMinusOne()) { - // If (i' - i) is -1, fold C into Basis - S. - Reduced = Builder.CreateSub(Basis.Ins, C.Stride); - } else { - Value *Bump = Builder.CreateMul(C.Stride, IndexOffset); + bool BumpWithGEP; + Value *Bump = emitBump(Basis, C, Builder, DL, BumpWithGEP); + Value *Reduced = nullptr; // equivalent to but weaker than C.Ins + switch (C.CandidateType) { + case Candidate::Mul: Reduced = Builder.CreateAdd(Basis.Ins, Bump); - } + break; + case Candidate::GEP: + { + Type *IntPtrTy = DL->getIntPtrType(C.Ins->getType()); + // We prefer bumping with GEP because GEPs keep more pointer information. + if (BumpWithGEP) { + // C = gep Basis, Bump + // Canonicalize bump to pointer size. + Bump = Builder.CreateSExtOrTrunc(Bump, IntPtrTy); + Reduced = Builder.CreateInBoundsGEP(Basis.Ins, Bump); + } else { + // C = inttoptr(ptrtoint(Basis) + Bump) + Reduced = Builder.CreatePtrToInt(Basis.Ins, IntPtrTy); + Reduced = Builder.CreateAdd(Reduced, Bump, "", false, true); + Reduced = Builder.CreateIntToPtr(Reduced, C.Ins->getType()); + } + } + break; + default: + assert(false && "CandidateType is invalid"); + }; Reduced->takeName(C.Ins); C.Ins->replaceAllUsesWith(Reduced); C.Ins->dropAllReferences(); @@ -243,7 +464,15 @@ if (skipOptnoneFunction(F)) return false; + if (TargetTransformInfoWrapperPass *TTIP = + getAnalysisIfAvailable()) { + TTI = &TTIP->getTTI(F); + } else { + TTI = nullptr; + } + DT = &getAnalysis().getDomTree(); + SE = &getAnalysis(); // Traverse the dominator tree in the depth-first order. This order makes sure // all bases of a candidate are in Candidates when we process it. for (auto node = GraphTraits::nodes_begin(DT); Index: test/Transforms/StraightLineStrengthReduce/X86/lit.local.cfg =================================================================== --- /dev/null +++ test/Transforms/StraightLineStrengthReduce/X86/lit.local.cfg @@ -0,0 +1,2 @@ +if not 'X86' in config.root.targets: + config.unsupported = True Index: test/Transforms/StraightLineStrengthReduce/X86/no-slsr.ll =================================================================== --- /dev/null +++ test/Transforms/StraightLineStrengthReduce/X86/no-slsr.ll @@ -0,0 +1,30 @@ +; RUN: opt < %s -slsr -gvn -dce -S | FileCheck %s + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Do not perform SLSR on &input[s] and &input[s * 2] which fit into addressing +; modes of X86. +define i32 @slsr_gep(i32* %input, i64 %s) { +; CHECK-LABEL: @slsr_gep( + ; v0 = input[0]; + %p0 = getelementptr inbounds i32, i32* %input, i64 0 + %v0 = load i32, i32* %p0 + + ; v1 = input[s]; + %p1 = getelementptr inbounds i32, i32* %input, i64 %s +; CHECK: %p1 = getelementptr inbounds i32, i32* %input, i64 %s + %v1 = load i32, i32* %p1 + + ; v2 = input[s * 2]; + %s2 = mul nsw i64 %s, 2 + %p2 = getelementptr inbounds i32, i32* %input, i64 %s2 +; CHECK: %p2 = getelementptr inbounds i32, i32* %input, i64 %s2 + %v2 = load i32, i32* %p2 + + ; return v0 + v1 + v2; + %1 = add i32 %v0, %v1 + %2 = add i32 %1, %v2 + ret i32 %2 +} + Index: test/Transforms/StraightLineStrengthReduce/slsr-gep.ll =================================================================== --- /dev/null +++ test/Transforms/StraightLineStrengthReduce/slsr-gep.ll @@ -0,0 +1,109 @@ +; RUN: opt < %s -slsr -gvn -dce -S | FileCheck %s + +target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64" + +define i32 @slsr_gep(i32* %input, i64 %s) { +; CHECK-LABEL: @slsr_gep( + ; v0 = input[0]; + %p0 = getelementptr inbounds i32, i32* %input, i64 0 + %v0 = load i32, i32* %p0 + + ; v1 = input[s]; + %p1 = getelementptr inbounds i32, i32* %input, i64 %s +; CHECK: %p1 = getelementptr inbounds i32, i32* %input, i64 %s + %v1 = load i32, i32* %p1 + + ; v2 = input[s * 2]; + %s2 = mul nsw i64 %s, 2 + %p2 = getelementptr inbounds i32, i32* %input, i64 %s2 +; CHECK: %p2 = getelementptr inbounds i32, i32* %p1, i64 %s + %v2 = load i32, i32* %p2 + + ; return v0 + v1 + v2; + %1 = add i32 %v0, %v1 + %2 = add i32 %1, %v2 + ret i32 %2 +} + +define i32 @slsr_gep_sext(i32* %input, i32 %s) { +; CHECK-LABEL: @slsr_gep_sext( + ; v0 = input[0]; + %p0 = getelementptr inbounds i32, i32* %input, i64 0 + %v0 = load i32, i32* %p0 + + ; v1 = input[(long)s]; + %t = sext i32 %s to i64 + %p1 = getelementptr inbounds i32, i32* %input, i64 %t +; CHECK: %p1 = getelementptr inbounds i32, i32* %input, i64 %t + %v1 = load i32, i32* %p1 + + ; v2 = input[(long)(s * 2)]; + %s2 = mul nsw i32 %s, 2 + %t2 = sext i32 %s2 to i64 + %p2 = getelementptr inbounds i32, i32* %input, i64 %t2 +; CHECK: %p2 = getelementptr inbounds i32, i32* %p1, i64 %t + %v2 = load i32, i32* %p2 + + ; return v0 + v1 + v2; + %1 = add i32 %v0, %v1 + %2 = add i32 %1, %v2 + ret i32 %2 +} + +define i32 @slsr_gep_2d([10 x [5 x i32]]* %input, i64 %s, i64 %t) { +; CHECK-LABEL: @slsr_gep_2d( + ; v0 = input[s][t]; + %p0 = getelementptr inbounds [10 x [5 x i32]], [10 x [5 x i32]]* %input, i64 0, i64 %s, i64 %t + %v0 = load i32, i32* %p0 + + ; v1 = input[s * 2][t]; + %s2 = mul nsw i64 %s, 2 +; CHECK: [[BUMP:%[a-zA-Z0-9]+]] = mul i64 %s, 5 + %p1 = getelementptr inbounds [10 x [5 x i32]], [10 x [5 x i32]]* %input, i64 0, i64 %s2, i64 %t +; CHECK: %p1 = getelementptr inbounds i32, i32* %p0, i64 [[BUMP]] + %v1 = load i32, i32* %p1 + + ; v2 = input[s * 3][t]; + %s3 = mul nsw i64 %s, 3 + %p2 = getelementptr inbounds [10 x [5 x i32]], [10 x [5 x i32]]* %input, i64 0, i64 %s3, i64 %t +; CHECK: %p2 = getelementptr inbounds i32, i32* %p1, i64 [[BUMP]] + %v2 = load i32, i32* %p2 + + ; return v0 + v1 + v2; + %1 = add i32 %v0, %v1 + %2 = add i32 %1, %v2 + ret i32 %2 +} + +%struct.S = type <{ i64, i32 }> + +; In this case, the bump +; = (char *)&input[s * 2][t].f1 - (char *)&input[s][t].f1 +; = 60 * s +; which may not be divisible by typeof(input[s][t].f1) = 8. Therefore, we +; rewrite the candidates using byte offset instead of index offset as in +; @slsr_gep_2d. +define i64 @slsr_gep_uglygep([10 x [5 x %struct.S]]* %input, i64 %s, i64 %t) { +; CHECK-LABEL: @slsr_gep_uglygep( + ; v0 = input[s][t].f1; + %p0 = getelementptr inbounds [10 x [5 x %struct.S]], [10 x [5 x %struct.S]]* %input, i64 0, i64 %s, i64 %t, i32 0 + %v0 = load i64, i64* %p0 + + ; v1 = input[s * 2][t].f1; + %s2 = mul nsw i64 %s, 2 +; CHECK: [[BUMP:%[a-zA-Z0-9]+]] = mul i64 %s, 60 + %p1 = getelementptr inbounds [10 x [5 x %struct.S]], [10 x [5 x %struct.S]]* %input, i64 0, i64 %s2, i64 %t, i32 0 +; CHECK: add nsw i64 %{{[0-9]+}}, [[BUMP]] + %v1 = load i64, i64* %p1 + + ; v2 = input[s * 3][t].f1; + %s3 = mul nsw i64 %s, 3 + %p2 = getelementptr inbounds [10 x [5 x %struct.S]], [10 x [5 x %struct.S]]* %input, i64 0, i64 %s3, i64 %t, i32 0 +; CHECK: add nsw i64 %{{[0-9]+}}, [[BUMP]] + %v2 = load i64, i64* %p2 + + ; return v0 + v1 + v2; + %1 = add i64 %v0, %v1 + %2 = add i64 %1, %v2 + ret i64 %2 +} Index: test/Transforms/StraightLineStrengthReduce/slsr-mul.ll =================================================================== --- test/Transforms/StraightLineStrengthReduce/slsr-mul.ll +++ test/Transforms/StraightLineStrengthReduce/slsr-mul.ll @@ -1,5 +1,7 @@ ; RUN: opt < %s -slsr -gvn -dce -S | FileCheck %s +target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64" + declare i32 @foo(i32 %a) define i32 @slsr1(i32 %b, i32 %s) {