From 5be18e84766fb495b0bde3c8244c1df459a18683 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Tue, 19 May 2009 02:15:55 +0000 Subject: [PATCH] Teach SCEVExpander to expand arithmetic involving pointers into GEP instructions. It attempts to create high-level multi-operand GEPs, though in cases where this isn't possible it falls back to casting the pointer to i8* and emitting a GEP with that. Using GEP instructions instead of ptrtoint+arithmetic+inttoptr helps pointer analyses that don't use ScalarEvolution, such as BasicAliasAnalysis. Also, make the AddrModeMatcher more aggressive in handling GEPs. Previously it assumed that operand 0 of a GEP would require a register in almost all cases. It now does extra checking and can do more matching if operand 0 of the GEP is foldable. This fixes a problem that was exposed by SCEVExpander using GEPs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72093 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 1 + .../llvm/Analysis/ScalarEvolutionExpander.h | 17 +- lib/Analysis/ScalarEvolution.cpp | 7 + lib/Analysis/ScalarEvolutionExpander.cpp | 177 ++++++++++++++++-- lib/Transforms/Scalar/IndVarSimplify.cpp | 12 +- lib/Transforms/Scalar/LoopStrengthReduce.cpp | 25 +-- lib/Transforms/Utils/AddrModeMatcher.cpp | 61 +++--- .../Transforms/IndVarSimplify/preserve-gep.ll | 39 ++++ .../2009-04-28-no-reduce-mul.ll | 3 +- 9 files changed, 270 insertions(+), 72 deletions(-) create mode 100644 test/Transforms/IndVarSimplify/preserve-gep.ll diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index d43d2449ebe..43fc2bde330 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -213,6 +213,7 @@ namespace llvm { /// class ScalarEvolution : public FunctionPass { friend class SCEVCallbackVH; + friend class SCEVExpander; /// F - The function we are analyzing. /// diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index e06abd7c6bb..cf2ad10e25a 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -28,7 +28,6 @@ namespace llvm { /// memory. struct SCEVExpander : public SCEVVisitor { ScalarEvolution &SE; - LoopInfo &LI; std::map InsertedExpressions; std::set InsertedValues; @@ -36,10 +35,8 @@ namespace llvm { friend struct SCEVVisitor; public: - SCEVExpander(ScalarEvolution &se, LoopInfo &li) - : SE(se), LI(li) {} - - LoopInfo &getLoopInfo() const { return LI; } + explicit SCEVExpander(ScalarEvolution &se) + : SE(se) {} /// clear - Erase the contents of the InsertedExpressions map so that users /// trying to expand the same expression into multiple BasicBlocks or @@ -83,8 +80,9 @@ namespace llvm { /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the - /// SCEVExpander's current insertion point. - Value *expandCodeFor(SCEVHandle SH, const Type *Ty); + /// SCEVExpander's current insertion point. If a type is specified, the + /// result will be expanded to have that type, with a cast if necessary. + Value *expandCodeFor(SCEVHandle SH, const Type *Ty = 0); /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the @@ -110,6 +108,11 @@ namespace llvm { Value *RHS, BasicBlock::iterator InsertPt); private: + /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP + /// instead of using ptrtoint+arithmetic+inttoptr. + Value *expandAddToGEP(const SCEVAddExpr *S, const PointerType *PTy, + const Type *Ty, Value *V); + Value *expand(const SCEV *S); Value *visitConstant(const SCEVConstant *S) { diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index eaa847aa10d..0857014863b 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -456,6 +456,13 @@ namespace { if (const SCEVUnknown *LU = dyn_cast(LHS)) { const SCEVUnknown *RU = cast(RHS); + // Order pointer values after integer values. This helps SCEVExpander + // form GEPs. + if (isa(LU->getType()) && !isa(RU->getType())) + return false; + if (isa(RU->getType()) && !isa(LU->getType())) + return true; + // Compare getValueID values. if (LU->getValue()->getValueID() != RU->getValue()->getValueID()) return LU->getValue()->getValueID() < RU->getValue()->getValueID(); diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index fd132746ad1..36b6206a9bc 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -15,6 +15,7 @@ #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Target/TargetData.h" using namespace llvm; /// InsertCastOfTo - Insert a cast of V to the specified type, doing what @@ -130,10 +131,9 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, BasicBlock::iterator IP = InsertPt; --IP; for (; ScanLimit; --IP, --ScanLimit) { - if (BinaryOperator *BinOp = dyn_cast(IP)) - if (BinOp->getOpcode() == Opcode && BinOp->getOperand(0) == LHS && - BinOp->getOperand(1) == RHS) - return BinOp; + if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && + IP->getOperand(1) == RHS) + return IP; if (IP == BlockBegin) break; } } @@ -144,9 +144,156 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, return BO; } +/// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP +/// instead of using ptrtoint+arithmetic+inttoptr. +Value *SCEVExpander::expandAddToGEP(const SCEVAddExpr *S, + const PointerType *PTy, + const Type *Ty, + Value *V) { + const Type *ElTy = PTy->getElementType(); + SmallVector GepIndices; + std::vector Ops = S->getOperands(); + bool AnyNonZeroIndices = false; + Ops.pop_back(); + + // Decend down the pointer's type and attempt to convert the other + // operands into GEP indices, at each level. The first index in a GEP + // indexes into the array implied by the pointer operand; the rest of + // the indices index into the element or field type selected by the + // preceding index. + for (;;) { + APInt ElSize = APInt(SE.getTypeSizeInBits(Ty), + ElTy->isSized() ? SE.TD->getTypeAllocSize(ElTy) : 0); + std::vector NewOps; + std::vector ScaledOps; + for (unsigned i = 0, e = Ops.size(); i != e; ++i) { + if (ElSize != 0) { + if (const SCEVConstant *C = dyn_cast(Ops[i])) + if (!C->getValue()->getValue().srem(ElSize)) { + ConstantInt *CI = + ConstantInt::get(C->getValue()->getValue().sdiv(ElSize)); + SCEVHandle Div = SE.getConstant(CI); + ScaledOps.push_back(Div); + continue; + } + if (const SCEVMulExpr *M = dyn_cast(Ops[i])) + if (const SCEVConstant *C = dyn_cast(M->getOperand(0))) + if (C->getValue()->getValue() == ElSize) { + for (unsigned j = 1, f = M->getNumOperands(); j != f; ++j) + ScaledOps.push_back(M->getOperand(j)); + continue; + } + if (const SCEVUnknown *U = dyn_cast(Ops[i])) + if (BinaryOperator *BO = dyn_cast(U->getValue())) + if (BO->getOpcode() == Instruction::Mul) + if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) + if (CI->getValue() == ElSize) { + ScaledOps.push_back(SE.getUnknown(BO->getOperand(0))); + continue; + } + if (ElSize == 1) { + ScaledOps.push_back(Ops[i]); + continue; + } + } + NewOps.push_back(Ops[i]); + } + Ops = NewOps; + AnyNonZeroIndices |= !ScaledOps.empty(); + Value *Scaled = ScaledOps.empty() ? + Constant::getNullValue(Ty) : + expandCodeFor(SE.getAddExpr(ScaledOps), Ty); + GepIndices.push_back(Scaled); + + // Collect struct field index operands. + if (!Ops.empty()) + while (const StructType *STy = dyn_cast(ElTy)) { + if (const SCEVConstant *C = dyn_cast(Ops[0])) + if (SE.getTypeSizeInBits(C->getType()) <= 64) { + const StructLayout &SL = *SE.TD->getStructLayout(STy); + uint64_t FullOffset = C->getValue()->getZExtValue(); + if (FullOffset < SL.getSizeInBytes()) { + unsigned ElIdx = SL.getElementContainingOffset(FullOffset); + GepIndices.push_back(ConstantInt::get(Type::Int32Ty, ElIdx)); + ElTy = STy->getTypeAtIndex(ElIdx); + Ops[0] = + SE.getConstant(ConstantInt::get(Ty, + FullOffset - + SL.getElementOffset(ElIdx))); + AnyNonZeroIndices = true; + continue; + } + } + break; + } + + if (const ArrayType *ATy = dyn_cast(ElTy)) { + ElTy = ATy->getElementType(); + continue; + } + break; + } + + // If none of the operands were convertable to proper GEP indices, cast + // the base to i8* and do an ugly getelementptr with that. It's still + // better than ptrtoint+arithmetic+inttoptr at least. + if (!AnyNonZeroIndices) { + V = InsertNoopCastOfTo(V, + Type::Int8Ty->getPointerTo(PTy->getAddressSpace())); + Value *Idx = expand(SE.getAddExpr(Ops)); + Idx = InsertNoopCastOfTo(Idx, Ty); + + // Fold a GEP with constant operands. + if (Constant *CLHS = dyn_cast(V)) + if (Constant *CRHS = dyn_cast(Idx)) + return ConstantExpr::get(Instruction::GetElementPtr, CLHS, CRHS); + + // Do a quick scan to see if we have this GEP nearby. If so, reuse it. + unsigned ScanLimit = 6; + BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); + if (InsertPt != BlockBegin) { + // Scanning starts from the last instruction before InsertPt. + BasicBlock::iterator IP = InsertPt; + --IP; + for (; ScanLimit; --IP, --ScanLimit) { + if (IP->getOpcode() == Instruction::GetElementPtr && + IP->getOperand(0) == V && IP->getOperand(1) == Idx) + return IP; + if (IP == BlockBegin) break; + } + } + + Value *GEP = GetElementPtrInst::Create(V, Idx, "scevgep", InsertPt); + InsertedValues.insert(GEP); + return GEP; + } + + // Insert a pretty getelementptr. + Value *GEP = GetElementPtrInst::Create(V, + GepIndices.begin(), + GepIndices.end(), + "scevgep", InsertPt); + Ops.push_back(SE.getUnknown(GEP)); + InsertedValues.insert(GEP); + return expand(SE.getAddExpr(Ops)); +} + Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { const Type *Ty = SE.getEffectiveSCEVType(S->getType()); Value *V = expand(S->getOperand(S->getNumOperands()-1)); + + // Turn things like ptrtoint+arithmetic+inttoptr into GEP. This helps + // BasicAliasAnalysis analyze the result. However, it suffers from the + // underlying bug described in PR2831. Addition in LLVM currently always + // has two's complement wrapping guaranteed. However, the semantics for + // getelementptr overflow are ambiguous. In the common case though, this + // expansion gets used when a GEP in the original code has been converted + // into integer arithmetic, in which case the resulting code will be no + // more undefined than it was originally. + if (SE.TD) + if (const PointerType *PTy = dyn_cast(V->getType())) + return expandAddToGEP(S, PTy, Ty, V); + V = InsertNoopCastOfTo(V, Ty); // Emit a bunch of add instructions @@ -157,7 +304,7 @@ Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { } return V; } - + Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { const Type *Ty = SE.getEffectiveSCEVType(S->getType()); int FirstOp = 0; // Set if we should emit a subtract. @@ -206,15 +353,10 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { // {X,+,F} --> X + {0,+,F} if (!S->getStart()->isZero()) { - Value *Start = expand(S->getStart()); - Start = InsertNoopCastOfTo(Start, Ty); - std::vector NewOps(S->op_begin(), S->op_end()); + std::vector NewOps(S->getOperands()); NewOps[0] = SE.getIntegerSCEV(0, Ty); Value *Rest = expand(SE.getAddRecExpr(NewOps, L)); - Rest = InsertNoopCastOfTo(Rest, Ty); - - // FIXME: look for an existing add to use. - return InsertBinop(Instruction::Add, Rest, Start, InsertPt); + return expand(SE.getAddExpr(S->getStart(), SE.getUnknown(Rest))); } // {0,+,1} --> Insert a canonical induction variable into the loop! @@ -265,7 +407,7 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { // point loop. If we can, move the multiply to the outer most loop that it // is safe to be in. BasicBlock::iterator MulInsertPt = getInsertionPoint(); - Loop *InsertPtLoop = LI.getLoopFor(MulInsertPt->getParent()); + Loop *InsertPtLoop = SE.LI->getLoopFor(MulInsertPt->getParent()); if (InsertPtLoop != L && InsertPtLoop && L->contains(InsertPtLoop->getHeader())) { do { @@ -363,10 +505,13 @@ Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { Value *SCEVExpander::expandCodeFor(SCEVHandle SH, const Type *Ty) { // Expand the code for this SCEV. - assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && - "non-trivial casts should be done with the SCEVs directly!"); Value *V = expand(SH); - return InsertNoopCastOfTo(V, Ty); + if (Ty) { + assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && + "non-trivial casts should be done with the SCEVs directly!"); + V = InsertNoopCastOfTo(V, Ty); + } + return V; } Value *SCEVExpander::expand(const SCEV *S) { diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index 2287f20086c..56bb4fea92c 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -172,7 +172,7 @@ ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, // Expand the code for the iteration count into the preheader of the loop. BasicBlock *Preheader = L->getLoopPreheader(); - Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), + Value *ExitCnt = Rewriter.expandCodeFor(RHS, CmpIndVar->getType(), Preheader->getTerminator()); // Insert a new icmp_ne or icmp_eq instruction before the branch. @@ -218,7 +218,7 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, // Scan all of the instructions in the loop, looking at those that have // extra-loop users and which are recurrences. - SCEVExpander Rewriter(*SE, *LI); + SCEVExpander Rewriter(*SE); // We insert the code into the preheader of the loop if the loop contains // multiple exit blocks, or in the exit block if there is exactly one. @@ -386,7 +386,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { } // Create a rewriter object which we'll use to transform the code with. - SCEVExpander Rewriter(*SE, *LI); + SCEVExpander Rewriter(*SE); // Now that we know the largest of of the induction variable expressions // in this loop, insert a canonical induction variable of the largest size. @@ -478,7 +478,7 @@ void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType, BasicBlock::iterator I = Rewriter.getInsertionPoint(); // Expand loop-invariant values in the loop preheader. They will // be sunk to the exit block later, if possible. - NewVal = + NewVal = Rewriter.expandCodeFor(AR, LargestType, L->getLoopPreheader()->getTerminator()); Rewriter.setInsertionPoint(I); @@ -523,7 +523,7 @@ void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType, NewAR = SE->getAddExpr(NewAR, PromotedOffset); // Expand the addrec into instructions. - Value *V = Rewriter.expandCodeFor(NewAR, LargestType); + Value *V = Rewriter.expandCodeFor(NewAR); // Insert an explicit cast if necessary to truncate the value // down to the original stride type. This is done outside of @@ -533,7 +533,7 @@ void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType, if (SE->getTypeSizeInBits(IVTy) != SE->getTypeSizeInBits(LargestType)) NewAR = SE->getTruncateExpr(NewAR, IVTy); if (Rewriter.isInsertedExpression(NewAR)) - V = Rewriter.expandCodeFor(NewAR, IVTy); + V = Rewriter.expandCodeFor(NewAR); else { V = Rewriter.InsertCastOfTo(CastInst::getCastOpcode(V, false, IVTy, false), diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 0427bc1ac56..557f34bc14e 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -367,12 +367,14 @@ namespace { void RewriteInstructionToUseNewBase(const SCEVHandle &NewBase, Instruction *InsertPt, SCEVExpander &Rewriter, Loop *L, Pass *P, + LoopInfo &LI, SmallVectorImpl &DeadInsts); Value *InsertCodeForBaseAtPosition(const SCEVHandle &NewBase, const Type *Ty, SCEVExpander &Rewriter, - Instruction *IP, Loop *L); + Instruction *IP, Loop *L, + LoopInfo &LI); void dump() const; }; } @@ -386,12 +388,12 @@ void BasedUser::dump() const { Value *BasedUser::InsertCodeForBaseAtPosition(const SCEVHandle &NewBase, const Type *Ty, SCEVExpander &Rewriter, - Instruction *IP, Loop *L) { + Instruction *IP, Loop *L, + LoopInfo &LI) { // Figure out where we *really* want to insert this code. In particular, if // the user is inside of a loop that is nested inside of L, we really don't // want to insert this expression before the user, we'd rather pull it out as // many loops as possible. - LoopInfo &LI = Rewriter.getLoopInfo(); Instruction *BaseInsertPt = IP; // Figure out the most-nested loop that IP is in. @@ -405,8 +407,7 @@ Value *BasedUser::InsertCodeForBaseAtPosition(const SCEVHandle &NewBase, InsertLoop = InsertLoop->getParentLoop(); } - Value *Base = Rewriter.expandCodeFor(NewBase, NewBase->getType(), - BaseInsertPt); + Value *Base = Rewriter.expandCodeFor(NewBase, 0, BaseInsertPt); SCEVHandle NewValSCEV = SE->getUnknown(Base); @@ -439,6 +440,7 @@ Value *BasedUser::InsertCodeForBaseAtPosition(const SCEVHandle &NewBase, void BasedUser::RewriteInstructionToUseNewBase(const SCEVHandle &NewBase, Instruction *NewBasePt, SCEVExpander &Rewriter, Loop *L, Pass *P, + LoopInfo &LI, SmallVectorImpl &DeadInsts) { if (!isa(Inst)) { // By default, insert code at the user instruction. @@ -468,7 +470,7 @@ void BasedUser::RewriteInstructionToUseNewBase(const SCEVHandle &NewBase, } Value *NewVal = InsertCodeForBaseAtPosition(NewBase, OperandValToReplace->getType(), - Rewriter, InsertPt, L); + Rewriter, InsertPt, L, LI); // Replace the use of the operand Value with the new Phi we just created. Inst->replaceUsesOfWith(OperandValToReplace, NewVal); @@ -527,7 +529,7 @@ void BasedUser::RewriteInstructionToUseNewBase(const SCEVHandle &NewBase, PN->getIncomingBlock(i)->getTerminator() : OldLoc->getParent()->getTerminator(); Code = InsertCodeForBaseAtPosition(NewBase, PN->getType(), - Rewriter, InsertPt, L); + Rewriter, InsertPt, L, LI); DOUT << " Changing PHI use to "; DEBUG(WriteAsOperand(*DOUT, Code, /*PrintType=*/false)); @@ -1580,8 +1582,8 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, << *Stride << ":\n" << " Common base: " << *CommonExprs << "\n"; - SCEVExpander Rewriter(*SE, *LI); - SCEVExpander PreheaderRewriter(*SE, *LI); + SCEVExpander Rewriter(*SE); + SCEVExpander PreheaderRewriter(*SE); BasicBlock *Preheader = L->getLoopPreheader(); Instruction *PreInsertPt = Preheader->getTerminator(); @@ -1636,8 +1638,7 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, // Emit the code for Base into the preheader. Value *BaseV = 0; if (!Base->isZero()) { - BaseV = PreheaderRewriter.expandCodeFor(Base, Base->getType(), - PreInsertPt); + BaseV = PreheaderRewriter.expandCodeFor(Base, 0, PreInsertPt); DOUT << " INSERTING code for BASE = " << *Base << ":"; if (BaseV->hasName()) @@ -1758,7 +1759,7 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, RewriteExpr = SE->getAddExpr(RewriteExpr, SE->getUnknown(BaseV)); User.RewriteInstructionToUseNewBase(RewriteExpr, NewBasePt, - Rewriter, L, this, + Rewriter, L, this, *LI, DeadInsts); // Mark old value we replaced as possibly dead, so that it is eliminated diff --git a/lib/Transforms/Utils/AddrModeMatcher.cpp b/lib/Transforms/Utils/AddrModeMatcher.cpp index b820dd3f8d5..71049fa212d 100644 --- a/lib/Transforms/Utils/AddrModeMatcher.cpp +++ b/lib/Transforms/Utils/AddrModeMatcher.cpp @@ -255,43 +255,44 @@ bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode, // Save the valid addressing mode in case we can't match. ExtAddrMode BackupAddrMode = AddrMode; - - // Check that this has no base reg yet. If so, we won't have a place to - // put the base of the GEP (assuming it is not a null ptr). - bool SetBaseReg = true; - if (isa(AddrInst->getOperand(0))) - SetBaseReg = false; // null pointer base doesn't need representation. - else if (AddrMode.HasBaseReg) - return false; // Base register already specified, can't match GEP. - else { - // Otherwise, we'll use the GEP base as the BaseReg. + unsigned OldSize = AddrModeInsts.size(); + + // See if the scale and offset amount is valid for this target. + AddrMode.BaseOffs += ConstantOffset; + + // Match the base operand of the GEP. + if (!MatchAddr(AddrInst->getOperand(0), Depth+1)) { + // If it couldn't be matched, just stuff the value in a register. + if (AddrMode.HasBaseReg) { + AddrMode = BackupAddrMode; + AddrModeInsts.resize(OldSize); + return false; + } AddrMode.HasBaseReg = true; AddrMode.BaseReg = AddrInst->getOperand(0); } - - // See if the scale and offset amount is valid for this target. - AddrMode.BaseOffs += ConstantOffset; - + + // Match the remaining variable portion of the GEP. if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale, Depth)) { + // If it couldn't be matched, try stuffing the base into a register + // instead of matching it, and retrying the match of the scale. AddrMode = BackupAddrMode; - return false; + AddrModeInsts.resize(OldSize); + if (AddrMode.HasBaseReg) + return false; + AddrMode.HasBaseReg = true; + AddrMode.BaseReg = AddrInst->getOperand(0); + AddrMode.BaseOffs += ConstantOffset; + if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), + VariableScale, Depth)) { + // If even that didn't work, bail. + AddrMode = BackupAddrMode; + AddrModeInsts.resize(OldSize); + return false; + } } - - // If we have a null as the base of the GEP, folding in the constant offset - // plus variable scale is all we can do. - if (!SetBaseReg) return true; - - // If this match succeeded, we know that we can form an address with the - // GepBase as the basereg. Match the base pointer of the GEP more - // aggressively by zeroing out BaseReg and rematching. If the base is - // (for example) another GEP, this allows merging in that other GEP into - // the addressing mode we're forming. - AddrMode.HasBaseReg = false; - AddrMode.BaseReg = 0; - bool Success = MatchAddr(AddrInst->getOperand(0), Depth+1); - assert(Success && "MatchAddr should be able to fill in BaseReg!"); - Success=Success; + return true; } } diff --git a/test/Transforms/IndVarSimplify/preserve-gep.ll b/test/Transforms/IndVarSimplify/preserve-gep.ll new file mode 100644 index 00000000000..2c8c224fb90 --- /dev/null +++ b/test/Transforms/IndVarSimplify/preserve-gep.ll @@ -0,0 +1,39 @@ +; RUN: llvm-as < %s | opt -indvars | llvm-dis > %t +; RUN: not grep ptrtoint %t +; RUN: not grep inttoptr %t +; RUN: grep getelementptr %t | count 1 + +; Indvars shouldn't leave getelementptrs expanded out as +; inttoptr+ptrtoint in its output in common cases. + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" +target triple = "x86_64-unknown-linux-gnu" + %struct.Foo = type { i32, i32, [10 x i32], i32 } + +define void @me(%struct.Foo* nocapture %Bar) nounwind { +entry: + br i1 false, label %return, label %bb.nph + +bb.nph: ; preds = %entry + br label %bb + +bb: ; preds = %bb1, %bb.nph + %i.01 = phi i64 [ %4, %bb1 ], [ 0, %bb.nph ] ; [#uses=3] + %0 = getelementptr %struct.Foo* %Bar, i64 %i.01, i32 2, i64 3 ; [#uses=1] + %1 = load i32* %0, align 4 ; [#uses=1] + %2 = mul i32 %1, 113 ; [#uses=1] + %3 = getelementptr %struct.Foo* %Bar, i64 %i.01, i32 2, i64 3 ; [#uses=1] + store i32 %2, i32* %3, align 4 + %4 = add i64 %i.01, 1 ; [#uses=2] + br label %bb1 + +bb1: ; preds = %bb + %phitmp = icmp sgt i64 %4, 19999 ; [#uses=1] + br i1 %phitmp, label %bb1.return_crit_edge, label %bb + +bb1.return_crit_edge: ; preds = %bb1 + br label %return + +return: ; preds = %bb1.return_crit_edge, %entry + ret void +} diff --git a/test/Transforms/LoopStrengthReduce/2009-04-28-no-reduce-mul.ll b/test/Transforms/LoopStrengthReduce/2009-04-28-no-reduce-mul.ll index f873b3d73e2..e1c9642ce81 100644 --- a/test/Transforms/LoopStrengthReduce/2009-04-28-no-reduce-mul.ll +++ b/test/Transforms/LoopStrengthReduce/2009-04-28-no-reduce-mul.ll @@ -1,4 +1,5 @@ -; RUN: llvm-as < %s | opt -loop-reduce | llvm-dis | grep {mul.*%lsr.iv} | count 2 +; RUN: llvm-as < %s | opt -loop-reduce | llvm-dis \ +; RUN: | grep {getelementptr.*%lsr.iv.*%lsr.iv.*} ; The multiply in bb2 must not be reduced to an add, as the sext causes the ; %1 argument to become negative after a while. ; ModuleID = '' -- 2.34.1