diff options
author | Evan Cheng <evan.cheng@apple.com> | 2009-02-17 00:13:06 +0000 |
---|---|---|
committer | Evan Cheng <evan.cheng@apple.com> | 2009-02-17 00:13:06 +0000 |
commit | 5a6c1a840ad343c0ed2fa54a0edb50b61f828f0f (patch) | |
tree | 1268fd6b81fa26857be92b2f24662d01504f8806 | |
parent | 1a5e936c53acda949afd8fa21b5a837b1d9fede9 (diff) | |
download | llvm-5a6c1a840ad343c0ed2fa54a0edb50b61f828f0f.tar.gz llvm-5a6c1a840ad343c0ed2fa54a0edb50b61f828f0f.tar.bz2 llvm-5a6c1a840ad343c0ed2fa54a0edb50b61f828f0f.tar.xz |
Strengthen the "non-constant stride must dominate loop preheader" check.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64703 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 8 | ||||
-rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpressions.h | 18 | ||||
-rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 40 | ||||
-rw-r--r-- | lib/Transforms/Scalar/LoopStrengthReduce.cpp | 13 | ||||
-rw-r--r-- | test/Transforms/LoopStrengthReduce/pr3399.ll | 32 |
5 files changed, 102 insertions, 9 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 0786b51f53..d94329d265 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -89,6 +89,10 @@ namespace llvm { const SCEVHandle &Conc, ScalarEvolution &SE) 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; + /// print - Print out the internal representation of this scalar to the /// specified stream. This should really only be used for debugging /// purposes. @@ -124,6 +128,10 @@ namespace llvm { const SCEVHandle &Conc, ScalarEvolution &SE) const; + virtual bool dominates(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); diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 652a99d0fc..61bb25a03b 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -20,6 +20,7 @@ namespace llvm { class ConstantInt; class ConstantRange; class APInt; + class DominatorTree; enum SCEVTypes { // These should be ordered in terms of increasing complexity to make the @@ -58,6 +59,10 @@ namespace llvm { return this; } + bool dominates(BasicBlock *BB, DominatorTree *DT) const { + return true; + } + virtual void print(std::ostream &OS) const; void print(std::ostream *OS) const { if (OS) print(*OS); } @@ -100,6 +105,8 @@ namespace llvm { return SE.getTruncateExpr(H, Ty); } + virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; + virtual void print(std::ostream &OS) const; void print(std::ostream *OS) const { if (OS) print(*OS); } @@ -142,6 +149,8 @@ namespace llvm { return SE.getZeroExtendExpr(H, Ty); } + bool dominates(BasicBlock *BB, DominatorTree *DT) const; + virtual void print(std::ostream &OS) const; void print(std::ostream *OS) const { if (OS) print(*OS); } @@ -184,6 +193,8 @@ namespace llvm { return SE.getSignExtendExpr(H, Ty); } + bool dominates(BasicBlock *BB, DominatorTree *DT) const; + virtual void print(std::ostream &OS) const; void print(std::ostream *OS) const { if (OS) print(*OS); } @@ -250,6 +261,8 @@ namespace llvm { const SCEVHandle &Conc, ScalarEvolution &SE) const; + bool dominates(BasicBlock *BB, DominatorTree *DT) const; + virtual const char *getOperationStr() const = 0; virtual const Type *getType() const { return getOperand(0)->getType(); } @@ -343,6 +356,7 @@ namespace llvm { return SE.getUDivExpr(L, R); } + bool dominates(BasicBlock *BB, DominatorTree *DT) const; virtual const Type *getType() const; @@ -437,6 +451,8 @@ namespace llvm { const SCEVHandle &Conc, ScalarEvolution &SE) const; + bool dominates(BasicBlock *BB, DominatorTree *DT) const; + virtual void print(std::ostream &OS) const; void print(std::ostream *OS) const { if (OS) print(*OS); } @@ -518,6 +534,8 @@ namespace llvm { return this; } + bool dominates(BasicBlock *BB, DominatorTree *DT) const; + virtual const Type *getType() const; virtual void print(std::ostream &OS) const; diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 59e76c0538..4e0dba7e04 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -66,6 +66,7 @@ #include "llvm/GlobalVariable.h" #include "llvm/Instructions.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Assembly/Writer.h" #include "llvm/Transforms/Scalar.h" @@ -205,6 +206,10 @@ SCEVTruncateExpr::~SCEVTruncateExpr() { SCEVTruncates->erase(std::make_pair(Op, Ty)); } +bool SCEVTruncateExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + return Op->dominates(BB, DT); +} + void SCEVTruncateExpr::print(std::ostream &OS) const { OS << "(truncate " << *Op << " to " << *Ty << ")"; } @@ -227,6 +232,10 @@ SCEVZeroExtendExpr::~SCEVZeroExtendExpr() { SCEVZeroExtends->erase(std::make_pair(Op, Ty)); } +bool SCEVZeroExtendExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + return Op->dominates(BB, DT); +} + void SCEVZeroExtendExpr::print(std::ostream &OS) const { OS << "(zeroextend " << *Op << " to " << *Ty << ")"; } @@ -249,6 +258,10 @@ SCEVSignExtendExpr::~SCEVSignExtendExpr() { SCEVSignExtends->erase(std::make_pair(Op, Ty)); } +bool SCEVSignExtendExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + return Op->dominates(BB, DT); +} + void SCEVSignExtendExpr::print(std::ostream &OS) const { OS << "(signextend " << *Op << " to " << *Ty << ")"; } @@ -306,6 +319,14 @@ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, return this; } +bool SCEVCommutativeExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + if (!getOperand(i)->dominates(BB, DT)) + return false; + } + return true; +} + // SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular // input. Don't use a SCEVHandle here, or else the object will never be @@ -317,6 +338,10 @@ SCEVUDivExpr::~SCEVUDivExpr() { SCEVUDivs->erase(std::make_pair(LHS, RHS)); } +bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + return LHS->dominates(BB, DT) && RHS->dominates(BB, DT); +} + void SCEVUDivExpr::print(std::ostream &OS) const { OS << "(" << *LHS << " /u " << *RHS << ")"; } @@ -337,6 +362,15 @@ SCEVAddRecExpr::~SCEVAddRecExpr() { Operands.end()))); } +bool SCEVAddRecExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + if (!getOperand(i)->dominates(BB, DT)) + return false; + } + return true; +} + + SCEVHandle SCEVAddRecExpr:: replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, const SCEVHandle &Conc, @@ -391,6 +425,12 @@ bool SCEVUnknown::isLoopInvariant(const Loop *L) const { return true; } +bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const { + if (Instruction *I = dyn_cast<Instruction>(getValue())) + return DT->dominates(I->getParent(), BB); + return true; +} + const Type *SCEVUnknown::getType() const { return V->getType(); } diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 055114c215..0945a5759f 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -438,16 +438,11 @@ static bool getSCEVStartAndStride(const SCEVHandle &SH, Loop *L, Start = SE->getAddExpr(Start, AddRec->getOperand(0)); if (!isa<SCEVConstant>(AddRec->getOperand(1))) { - // If stride is an instruction, make sure it dominates the loop header. + // If stride is an instruction, make sure it dominates the loop preheader. // Otherwise we could end up with a use before def situation. - if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(AddRec->getOperand(1))) { - if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) { - BasicBlock *StrideBB = I->getParent(); - BasicBlock *Preheader = L->getLoopPreheader(); - if (!DT->dominates(StrideBB, Preheader)) - return false; - } - } + BasicBlock *Preheader = L->getLoopPreheader(); + if (!AddRec->getOperand(1)->dominates(Preheader, DT)) + return false; DOUT << "[" << L->getHeader()->getName() << "] Variable stride: " << *AddRec << "\n"; diff --git a/test/Transforms/LoopStrengthReduce/pr3399.ll b/test/Transforms/LoopStrengthReduce/pr3399.ll new file mode 100644 index 0000000000..9d2f5eda1b --- /dev/null +++ b/test/Transforms/LoopStrengthReduce/pr3399.ll @@ -0,0 +1,32 @@ +; RUN: llvm-as < %s | opt -loop-reduce | llvm-dis +; PR3399 + +@g_53 = external global i32 ; <i32*> [#uses=1] + +define i32 @foo() nounwind { +bb5.thread: + br label %bb + +bb: ; preds = %bb5, %bb5.thread + %indvar = phi i32 [ 0, %bb5.thread ], [ %indvar.next, %bb5 ] ; <i32> [#uses=2] + br i1 false, label %bb5, label %bb1 + +bb1: ; preds = %bb + %l_2.0.reg2mem.0 = sub i32 0, %indvar ; <i32> [#uses=1] + %0 = volatile load i32* @g_53, align 4 ; <i32> [#uses=1] + %1 = trunc i32 %l_2.0.reg2mem.0 to i16 ; <i16> [#uses=1] + %2 = trunc i32 %0 to i16 ; <i16> [#uses=1] + %3 = mul i16 %2, %1 ; <i16> [#uses=1] + %4 = icmp eq i16 %3, 0 ; <i1> [#uses=1] + br i1 %4, label %bb7, label %bb2 + +bb2: ; preds = %bb2, %bb1 + br label %bb2 + +bb5: ; preds = %bb + %indvar.next = add i32 %indvar, 1 ; <i32> [#uses=1] + br label %bb + +bb7: ; preds = %bb1 + ret i32 1 +} |