From dc0e8fb9f9512622f55f73e1a434caa5c0915694 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Wed, 17 Nov 2010 21:41:58 +0000 Subject: [PATCH] Move SCEV::dominates and properlyDominates to ScalarEvolution. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119570 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 24 +-- .../Analysis/ScalarEvolutionExpressions.h | 28 ---- lib/Analysis/ScalarEvolution.cpp | 149 +++++++++++------- lib/Analysis/ScalarEvolutionExpander.cpp | 4 +- lib/Transforms/Scalar/LoopStrengthReduce.cpp | 24 ++- 5 files changed, 112 insertions(+), 117 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 333b11ca9d7..30b019cd44c 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -99,14 +99,6 @@ namespace llvm { /// indirect operand. virtual bool hasOperand(const SCEV *Op) const = 0; - /// dominates - Return true if elements that makes up this SCEV dominates - /// the specified basic block. - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; - - /// properlyDominates - Return true if elements that makes up this SCEV - /// properly dominate the specified basic block. - virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const = 0; - /// print - Print out the internal representation of this scalar to the /// specified stream. This should really only be used for debugging /// purposes. @@ -150,14 +142,6 @@ namespace llvm { virtual void print(raw_ostream &OS) const; virtual bool hasOperand(const SCEV *Op) const; - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - - virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVCouldNotCompute *S) { return true; } static bool classof(const SCEV *S); @@ -699,6 +683,14 @@ namespace llvm { /// to compute the value of the expression at any particular loop iteration. bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); + /// dominates - Return true if elements that makes up the given SCEV + /// dominate the specified basic block. + bool dominates(const SCEV *S, BasicBlock *BB) const; + + /// properlyDominates - Return true if elements that makes up the given SCEV + /// properly dominate the specified basic block. + bool properlyDominates(const SCEV *S, BasicBlock *BB) const; + virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 8cb533a1f29..4d956355018 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -48,14 +48,6 @@ namespace llvm { return false; } - bool dominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - virtual void print(raw_ostream &OS) const; /// Methods for support type inquiry through isa, cast, and dyn_cast: @@ -84,10 +76,6 @@ namespace llvm { return Op == O || Op->hasOperand(O); } - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVCastExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -188,10 +176,6 @@ namespace llvm { virtual bool hasOperand(const SCEV *O) const; - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - virtual const Type *getType() const { return getOperand(0)->getType(); } bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); } @@ -309,10 +293,6 @@ namespace llvm { return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O); } - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - virtual const Type *getType() const; void print(raw_ostream &OS) const; @@ -357,10 +337,6 @@ namespace llvm { getLoop()); } - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - /// isAffine - Return true if this is an affine AddRec (i.e., it represents /// an expressions A+B*x where A and B are loop invariant values. bool isAffine() const { @@ -496,10 +472,6 @@ namespace llvm { return false; } - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - virtual const Type *getType() const; virtual void print(raw_ostream &OS) const; diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index d641e8a708b..8b7d8f2740f 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -197,14 +197,6 @@ SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID, unsigned SCEVTy, const SCEV *op, const Type *ty) : SCEV(ID, SCEVTy), Op(op), Ty(ty) {} -bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { - return Op->dominates(BB, DT); -} - -bool SCEVCastExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - return Op->properlyDominates(BB, DT); -} - SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op, const Type *ty) : SCEVCastExpr(ID, scTruncate, op, ty) { @@ -252,20 +244,6 @@ void SCEVCommutativeExpr::print(raw_ostream &OS) const { OS << ")"; } -bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { - for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) - if (!(*I)->dominates(BB, DT)) - return false; - return true; -} - -bool SCEVNAryExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) - if (!(*I)->properlyDominates(BB, DT)) - return false; - return true; -} - bool SCEVNAryExpr::hasOperand(const SCEV *O) const { for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) { const SCEV *S = *I; @@ -275,14 +253,6 @@ bool SCEVNAryExpr::hasOperand(const SCEV *O) const { return false; } -bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { - return LHS->dominates(BB, DT) && RHS->dominates(BB, DT); -} - -bool SCEVUDivExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - return LHS->properlyDominates(BB, DT) && RHS->properlyDominates(BB, DT); -} - void SCEVUDivExpr::print(raw_ostream &OS) const { OS << "(" << *LHS << " /u " << *RHS << ")"; } @@ -296,21 +266,6 @@ const Type *SCEVUDivExpr::getType() const { return RHS->getType(); } -bool -SCEVAddRecExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { - return DT->dominates(L->getHeader(), BB) && - SCEVNAryExpr::dominates(BB, DT); -} - -bool -SCEVAddRecExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - // This uses a "dominates" query instead of "properly dominates" query because - // the instruction which produces the addrec's value is a PHI, and a PHI - // effectively properly dominates its entire containing block. - return DT->dominates(L->getHeader(), BB) && - SCEVNAryExpr::properlyDominates(BB, DT); -} - void SCEVAddRecExpr::print(raw_ostream &OS) const { OS << "{" << *Operands[0]; for (unsigned i = 1, e = NumOperands; i != e; ++i) @@ -348,18 +303,6 @@ void SCEVUnknown::allUsesReplacedWith(Value *New) { setValPtr(New); } -bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const { - if (Instruction *I = dyn_cast(getValue())) - return DT->dominates(I->getParent(), BB); - return true; -} - -bool SCEVUnknown::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - if (Instruction *I = dyn_cast(getValue())) - return DT->properlyDominates(I->getParent(), BB); - return true; -} - const Type *SCEVUnknown::getType() const { return getValue()->getType(); } @@ -4921,7 +4864,7 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, // as both operands could be addrecs loop-invariant in each other's loop. if (const SCEVAddRecExpr *AR = dyn_cast(RHS)) { const Loop *L = AR->getLoop(); - if (isLoopInvariant(LHS, L) && LHS->properlyDominates(L->getHeader(), DT)) { + if (isLoopInvariant(LHS, L) && properlyDominates(LHS, L->getHeader())) { std::swap(LHS, RHS); Pred = ICmpInst::getSwappedPredicate(Pred); Changed = true; @@ -6059,3 +6002,93 @@ bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) { llvm_unreachable("Unknown SCEV kind!"); return false; } + +bool ScalarEvolution::dominates(const SCEV *S, BasicBlock *BB) const { + switch (S->getSCEVType()) { + case scConstant: + return true; + case scTruncate: + case scZeroExtend: + case scSignExtend: + return dominates(cast(S)->getOperand(), BB); + case scAddRecExpr: { + const SCEVAddRecExpr *AR = cast(S); + if (!DT->dominates(AR->getLoop()->getHeader(), BB)) + return false; + } + // FALL THROUGH into SCEVNAryExpr handling. + case scAddExpr: + case scMulExpr: + case scUMaxExpr: + case scSMaxExpr: { + const SCEVNAryExpr *NAry = cast(S); + for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); + I != E; ++I) + if (!dominates(*I, BB)) + return false; + return true; + } + case scUDivExpr: { + const SCEVUDivExpr *UDiv = cast(S); + return dominates(UDiv->getLHS(), BB) && dominates(UDiv->getRHS(), BB); + } + case scUnknown: + if (Instruction *I = + dyn_cast(cast(S)->getValue())) + return DT->dominates(I->getParent(), BB); + return true; + case scCouldNotCompute: + llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); + return false; + default: break; + } + llvm_unreachable("Unknown SCEV kind!"); + return false; +} + +bool ScalarEvolution::properlyDominates(const SCEV *S, BasicBlock *BB) const { + switch (S->getSCEVType()) { + case scConstant: + return true; + case scTruncate: + case scZeroExtend: + case scSignExtend: + return properlyDominates(cast(S)->getOperand(), BB); + case scAddRecExpr: { + // This uses a "dominates" query instead of "properly dominates" query + // because the instruction which produces the addrec's value is a PHI, and + // a PHI effectively properly dominates its entire containing block. + const SCEVAddRecExpr *AR = cast(S); + if (!DT->dominates(AR->getLoop()->getHeader(), BB)) + return false; + } + // FALL THROUGH into SCEVNAryExpr handling. + case scAddExpr: + case scMulExpr: + case scUMaxExpr: + case scSMaxExpr: { + const SCEVNAryExpr *NAry = cast(S); + for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); + I != E; ++I) + if (!properlyDominates(*I, BB)) + return false; + return true; + } + case scUDivExpr: { + const SCEVUDivExpr *UDiv = cast(S); + return properlyDominates(UDiv->getLHS(), BB) && + properlyDominates(UDiv->getRHS(), BB); + } + case scUnknown: + if (Instruction *I = + dyn_cast(cast(S)->getValue())) + return DT->properlyDominates(I->getParent(), BB); + return true; + case scCouldNotCompute: + llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); + return false; + default: break; + } + llvm_unreachable("Unknown SCEV kind!"); + return false; +} diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index 409d9b5f7fa..d9eb8c1ca65 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -990,7 +990,7 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { // Strip off any non-loop-dominating component from the addrec start. const SCEV *Start = Normalized->getStart(); const SCEV *PostLoopOffset = 0; - if (!Start->properlyDominates(L->getHeader(), SE.DT)) { + if (!SE.properlyDominates(Start, L->getHeader())) { PostLoopOffset = Start; Start = SE.getConstant(Normalized->getType(), 0); Normalized = @@ -1002,7 +1002,7 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { // Strip off any non-loop-dominating component from the addrec step. const SCEV *Step = Normalized->getStepRecurrence(SE); const SCEV *PostLoopScale = 0; - if (!Step->dominates(L->getHeader(), SE.DT)) { + if (!SE.dominates(Step, L->getHeader())) { PostLoopScale = Step; Step = SE.getConstant(Normalized->getType(), 1); Normalized = diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 7bc06632c90..6c72c3cb9fb 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -210,8 +210,7 @@ struct Formula { Formula() : ScaledReg(0) {} - void InitialMatch(const SCEV *S, Loop *L, - ScalarEvolution &SE, DominatorTree &DT); + void InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE); unsigned getNumRegs() const; const Type *getType() const; @@ -232,9 +231,9 @@ struct Formula { static void DoInitialMatch(const SCEV *S, Loop *L, SmallVectorImpl &Good, SmallVectorImpl &Bad, - ScalarEvolution &SE, DominatorTree &DT) { + ScalarEvolution &SE) { // Collect expressions which properly dominate the loop header. - if (S->properlyDominates(L->getHeader(), &DT)) { + if (SE.properlyDominates(S, L->getHeader())) { Good.push_back(S); return; } @@ -243,18 +242,18 @@ static void DoInitialMatch(const SCEV *S, Loop *L, if (const SCEVAddExpr *Add = dyn_cast(S)) { for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); I != E; ++I) - DoInitialMatch(*I, L, Good, Bad, SE, DT); + DoInitialMatch(*I, L, Good, Bad, SE); return; } // Look at addrec operands. if (const SCEVAddRecExpr *AR = dyn_cast(S)) if (!AR->getStart()->isZero()) { - DoInitialMatch(AR->getStart(), L, Good, Bad, SE, DT); + DoInitialMatch(AR->getStart(), L, Good, Bad, SE); DoInitialMatch(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0), AR->getStepRecurrence(SE), AR->getLoop()), - L, Good, Bad, SE, DT); + L, Good, Bad, SE); return; } @@ -266,7 +265,7 @@ static void DoInitialMatch(const SCEV *S, Loop *L, SmallVector MyGood; SmallVector MyBad; - DoInitialMatch(NewMul, L, MyGood, MyBad, SE, DT); + DoInitialMatch(NewMul, L, MyGood, MyBad, SE); const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue( SE.getEffectiveSCEVType(NewMul->getType()))); for (SmallVectorImpl::const_iterator I = MyGood.begin(), @@ -286,11 +285,10 @@ static void DoInitialMatch(const SCEV *S, Loop *L, /// InitialMatch - Incorporate loop-variant parts of S into this Formula, /// attempting to keep all loop-invariant and loop-computable values in a /// single base register. -void Formula::InitialMatch(const SCEV *S, Loop *L, - ScalarEvolution &SE, DominatorTree &DT) { +void Formula::InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) { SmallVector Good; SmallVector Bad; - DoInitialMatch(S, L, Good, Bad, SE, DT); + DoInitialMatch(S, L, Good, Bad, SE); if (!Good.empty()) { const SCEV *Sum = SE.getAddExpr(Good); if (!Sum->isZero()) @@ -2096,7 +2094,7 @@ void LSRInstance::CollectFixupsAndInitialFormulae() { void LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) { Formula F; - F.InitialMatch(S, L, SE, DT); + F.InitialMatch(S, L, SE); bool Inserted = InsertFormula(LU, LUIdx, F); assert(Inserted && "Initial formula already exists!"); (void)Inserted; } @@ -2330,7 +2328,7 @@ void LSRInstance::GenerateCombinations(LSRUse &LU, unsigned LUIdx, for (SmallVectorImpl::const_iterator I = Base.BaseRegs.begin(), E = Base.BaseRegs.end(); I != E; ++I) { const SCEV *BaseReg = *I; - if (BaseReg->properlyDominates(L->getHeader(), &DT) && + if (SE.properlyDominates(BaseReg, L->getHeader()) && !SE.hasComputableLoopEvolution(BaseReg, L)) Ops.push_back(BaseReg); else -- 2.34.1