diff options
author | Andrew Trick <atrick@apple.com> | 2011-10-07 23:46:21 +0000 |
---|---|---|
committer | Andrew Trick <atrick@apple.com> | 2011-10-07 23:46:21 +0000 |
commit | c5701910604cdf65811fabd31d41e38f1d1d4eb1 (patch) | |
tree | 87ebc36baa56af35d74481785773869df6290130 | |
parent | 9eb6b4d91b83448ec818089754c74bbdcf7dfd7a (diff) | |
download | llvm-c5701910604cdf65811fabd31d41e38f1d1d4eb1.tar.gz llvm-c5701910604cdf65811fabd31d41e38f1d1d4eb1.tar.bz2 llvm-c5701910604cdf65811fabd31d41e38f1d1d4eb1.tar.xz |
LSR should only reuse phis that match its formula.
Fixes rdar://problem/5064068
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141442 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpander.h | 19 | ||||
-rw-r--r-- | lib/Analysis/ScalarEvolutionExpander.cpp | 174 | ||||
-rw-r--r-- | lib/Transforms/Scalar/LoopStrengthReduce.cpp | 1 |
3 files changed, 129 insertions, 65 deletions
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index c883d7f17e..f7bab30836 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -64,6 +64,11 @@ namespace llvm { /// in a more literal form. bool CanonicalMode; + /// When invoked from LSR, the expander is in "strength reduction" mode. The + /// only difference is that phi's are only reused if they are already in + /// "expanded" form. + bool LSRMode; + typedef IRBuilder<true, TargetFolder> BuilderType; BuilderType Builder; @@ -73,7 +78,8 @@ namespace llvm { /// SCEVExpander - Construct a SCEVExpander in "canonical" mode. explicit SCEVExpander(ScalarEvolution &se, const char *name) : SE(se), IVName(name), IVIncInsertLoop(0), IVIncInsertPos(0), - CanonicalMode(true), Builder(se.getContext(), TargetFolder(se.TD)) {} + CanonicalMode(true), LSRMode(false), + Builder(se.getContext(), TargetFolder(se.TD)) {} /// clear - Erase the contents of the InsertedExpressions map so that users /// trying to expand the same expression into multiple BasicBlocks or @@ -88,8 +94,7 @@ namespace llvm { /// canonical induction variable of the specified type for the specified /// loop (inserting one if there is none). A canonical induction variable /// starts at zero and steps by one on each iteration. - PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, - Type *Ty); + PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty); /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the @@ -127,13 +132,14 @@ namespace llvm { /// is useful for late optimization passes. void disableCanonicalMode() { CanonicalMode = false; } + void enableLSRMode() { LSRMode = true; } + /// clearInsertPoint - Clear the current insertion point. This is useful /// if the instruction that had been serving as the insertion point may /// have been deleted. void clearInsertPoint() { Builder.ClearInsertionPoint(); } - private: LLVMContext &getContext() const { return SE.getContext(); } @@ -208,6 +214,11 @@ namespace llvm { void restoreInsertPoint(BasicBlock *BB, BasicBlock::iterator I); + bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); + + bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L, + Type *ExpandTy); + Value *expandAddRecExprLiterally(const SCEVAddRecExpr *); PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, const Loop *L, diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index 2eafdb906f..3229c3c915 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -17,6 +17,7 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/IntrinsicInst.h" #include "llvm/LLVMContext.h" +#include "llvm/Support/Debug.h" #include "llvm/Target/TargetData.h" #include "llvm/ADT/STLExtras.h" @@ -843,6 +844,82 @@ static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest, } } +/// Determine if this is a well-behaved chain of instructions leading back to +/// the PHI. If so, it may be reused by expanded expressions. +bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, + const Loop *L) { + if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) || + (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV))) + return false; + // If any of the operands don't dominate the insert position, bail. + // Addrec operands are always loop-invariant, so this can only happen + // if there are instructions which haven't been hoisted. + if (L == IVIncInsertLoop) { + for (User::op_iterator OI = IncV->op_begin()+1, + OE = IncV->op_end(); OI != OE; ++OI) + if (Instruction *OInst = dyn_cast<Instruction>(OI)) + if (!SE.DT->dominates(OInst, IVIncInsertPos)) + return false; + } + // Advance to the next instruction. + IncV = dyn_cast<Instruction>(IncV->getOperand(0)); + if (!IncV) + return false; + + if (IncV->mayHaveSideEffects()) + return false; + + if (IncV != PN) + return true; + + return isNormalAddRecExprPHI(PN, IncV, L); +} + +/// Determine if this cyclic phi is in a form that would have been generated by +/// LSR. We don't care if the phi was actually expanded in this pass, as long +/// as it is in a low-cost form, for example, no implied multiplication. This +/// should match any patterns generated by getAddRecExprPHILiterally and +/// expandAddtoGEP. +bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, + const Loop *L, Type *ExpandTy) { + switch (IncV->getOpcode()) { + // Check for a simple Add/Sub or GEP of a loop invariant step. + case Instruction::Add: + case Instruction::Sub: + return IncV->getOperand(0) == PN + && L->isLoopInvariant(IncV->getOperand(1)); + case Instruction::BitCast: + IncV = dyn_cast<GetElementPtrInst>(IncV->getOperand(0)); + if (!IncV) + return false; + // fall-thru to GEP handling + case Instruction::GetElementPtr: { + // This must be a pointer addition of constants (pretty) or some number of + // address-size elements (ugly). + for (Instruction::op_iterator I = IncV->op_begin()+1, E = IncV->op_end(); + I != E; ++I) { + if (isa<Constant>(*I)) + continue; + // ugly geps have 2 operands. + // i1* is used by the expander to represent an address-size element. + if (IncV->getNumOperands() != 2) + return false; + unsigned AS = cast<PointerType>(ExpandTy)->getAddressSpace(); + if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS) + && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS)) + return false; + break; + } + IncV = dyn_cast<Instruction>(IncV->getOperand(0)); + if (IncV && IncV->getOpcode() == Instruction::BitCast) + IncV = dyn_cast<Instruction>(IncV->getOperand(0)); + return IncV == PN; + } + default: + return false; + } +} + /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand /// the base addrec, which is the addrec without any non-loop-dominating /// values, and return the PHI. @@ -854,70 +931,45 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position"); // Reuse a previously-inserted PHI, if present. - for (BasicBlock::iterator I = L->getHeader()->begin(); - PHINode *PN = dyn_cast<PHINode>(I); ++I) - if (SE.isSCEVable(PN->getType()) && - (SE.getEffectiveSCEVType(PN->getType()) == - SE.getEffectiveSCEVType(Normalized->getType())) && - SE.getSCEV(PN) == Normalized) - if (BasicBlock *LatchBlock = L->getLoopLatch()) { - Instruction *IncV = - cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock)); - - // Determine if this is a well-behaved chain of instructions leading - // back to the PHI. It probably will be, if we're scanning an inner - // loop already visited by LSR for example, but it wouldn't have - // to be. + BasicBlock *LatchBlock = L->getLoopLatch(); + if (LatchBlock) { + for (BasicBlock::iterator I = L->getHeader()->begin(); + PHINode *PN = dyn_cast<PHINode>(I); ++I) { + if (!SE.isSCEVable(PN->getType()) || + (SE.getEffectiveSCEVType(PN->getType()) != + SE.getEffectiveSCEVType(Normalized->getType())) || + SE.getSCEV(PN) != Normalized) + continue; + + Instruction *IncV = + cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock)); + + if (LSRMode) { + if (!isExpandedAddRecExprPHI(PN, IncV, L, ExpandTy)) + continue; + } + else { + if (!isNormalAddRecExprPHI(PN, IncV, L)) + continue; + } + // Ok, the add recurrence looks usable. + // Remember this PHI, even in post-inc mode. + InsertedValues.insert(PN); + // Remember the increment. + rememberInstruction(IncV); + if (L == IVIncInsertLoop) do { - if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) || - (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV))) { - IncV = 0; - break; - } - // If any of the operands don't dominate the insert position, bail. - // Addrec operands are always loop-invariant, so this can only happen - // if there are instructions which haven't been hoisted. - if (L == IVIncInsertLoop) { - for (User::op_iterator OI = IncV->op_begin()+1, - OE = IncV->op_end(); OI != OE; ++OI) - if (Instruction *OInst = dyn_cast<Instruction>(OI)) - if (!SE.DT->dominates(OInst, IVIncInsertPos)) { - IncV = 0; - break; - } - } - if (!IncV) + if (SE.DT->dominates(IncV, IVIncInsertPos)) break; - // Advance to the next instruction. - IncV = dyn_cast<Instruction>(IncV->getOperand(0)); - if (!IncV) - break; - if (IncV->mayHaveSideEffects()) { - IncV = 0; - break; - } + // Make sure the increment is where we want it. But don't move it + // down past a potential existing post-inc user. + IncV->moveBefore(IVIncInsertPos); + IVIncInsertPos = IncV; + IncV = cast<Instruction>(IncV->getOperand(0)); } while (IncV != PN); - - if (IncV) { - // Ok, the add recurrence looks usable. - // Remember this PHI, even in post-inc mode. - InsertedValues.insert(PN); - // Remember the increment. - IncV = cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock)); - rememberInstruction(IncV); - if (L == IVIncInsertLoop) - do { - if (SE.DT->dominates(IncV, IVIncInsertPos)) - break; - // Make sure the increment is where we want it. But don't move it - // down past a potential existing post-inc user. - IncV->moveBefore(IVIncInsertPos); - IVIncInsertPos = IncV; - IncV = cast<Instruction>(IncV->getOperand(0)); - } while (IncV != PN); - return PN; - } - } + return PN; + } + } // Save the original insertion point so we can restore it when we're done. BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 4b6c55e162..26fc03b18b 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -3770,6 +3770,7 @@ LSRInstance::ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, SCEVExpander Rewriter(SE, "lsr"); Rewriter.disableCanonicalMode(); + Rewriter.enableLSRMode(); Rewriter.setIVIncInsertPos(L, IVIncInsertPos); // Expand the new value definitions and update the users. |