From 406fc0cb49e1255d2caea1b943dd17bd4dda775d Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Wed, 20 Sep 2006 17:04:01 +0000 Subject: [PATCH] Use a total ordering to compare instructions. Fixes infinite loop in resolve(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@30540 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/PredicateSimplifier.cpp | 188 ++++++++++-------- .../2006-09-20-ResolveCycle.ll | 28 +++ 2 files changed, 129 insertions(+), 87 deletions(-) create mode 100644 test/Transforms/PredicateSimplifier/2006-09-20-ResolveCycle.ll diff --git a/lib/Transforms/Scalar/PredicateSimplifier.cpp b/lib/Transforms/Scalar/PredicateSimplifier.cpp index b9006b63e10..8dc1a4d7d09 100644 --- a/lib/Transforms/Scalar/PredicateSimplifier.cpp +++ b/lib/Transforms/Scalar/PredicateSimplifier.cpp @@ -49,60 +49,30 @@ namespace { Statistic<> NumInstruction("predsimplify", "Number of instructions removed"); - /// Returns true if V1 is a better choice than V2. Note that it is - /// not a total ordering. - struct compare { - bool operator()(Value *V1, Value *V2) const { - if (isa(V1)) { - if (!isa(V2)) { - return true; - } - } else if (isa(V1)) { - if (!isa(V2) && !isa(V2)) { - return true; - } - } - if (User *U = dyn_cast(V2)) { - for (User::const_op_iterator I = U->op_begin(), E = U->op_end(); - I != E; ++I) { - if (*I == V1) { - return true; - } - } - } - return false; - } - }; - - /// Used for choosing the canonical Value in a synonym set. - /// Leaves the better choice in V1. - static void order(Value *&V1, Value *&V2) { - static compare c; - if (c(V2, V1)) - std::swap(V1, V2); - } + class PropertySet; /// Similar to EquivalenceClasses, this stores the set of equivalent - /// types. Beyond EquivalenceClasses, it allows the user to specify - /// which element will act as leader through a StrictWeakOrdering - /// function. - template + /// types. Beyond EquivalenceClasses, it allows us to specify which + /// element will act as leader. + template class VISIBILITY_HIDDEN Synonyms { std::map mapping; std::vector leaders; - StrictWeak swo; + PropertySet *PS; public: typedef unsigned iterator; typedef const unsigned const_iterator; + Synonyms(PropertySet *PS) : PS(PS) {} + // Inspection bool empty() const { return leaders.empty(); } - unsigned countLeaders() const { + typename std::vector::size_type countLeaders() const { return leaders.size(); } @@ -151,50 +121,8 @@ namespace { /// Combine two sets referring to the same element, inserting the /// elements as needed. Returns a valid iterator iff two already /// existing disjoint synonym sets were combined. The iterator - /// points to the removed element. - iterator unionSets(ElemTy E1, ElemTy E2) { - if (swo(E2, E1)) std::swap(E1, E2); - - iterator I1 = findLeader(E1), - I2 = findLeader(E2); - - if (!I1 && !I2) { // neither entry is in yet - leaders.push_back(E1); - I1 = leaders.size(); - mapping[E1] = I1; - mapping[E2] = I1; - return 0; - } - - if (!I1 && I2) { - mapping[E1] = I2; - std::swap(getLeader(I2), E1); - return 0; - } - - if (I1 && !I2) { - mapping[E2] = I1; - return 0; - } - - if (I1 == I2) return 0; - - // This is the case where we have two sets, [%a1, %a2, %a3] and - // [%p1, %p2, %p3] and someone says that %a2 == %p3. We need to - // combine the two synsets. - - if (I1 > I2) --I1; - - for (std::map::iterator I = mapping.begin(), - E = mapping.end(); I != E; ++I) { - if (I->second == I2) I->second = I1; - else if (I->second > I2) --I->second; - } - - leaders.erase(leaders.begin() + I2 - 1); - - return I2; - } + /// points to the no longer existing element. + iterator unionSets(ElemTy E1, ElemTy E2); /// Returns an iterator pointing to the synonym set containing /// element e. If none exists, a new one is created and returned. @@ -212,13 +140,51 @@ namespace { /// Represents the set of equivalent Value*s and provides insertion /// and fast lookup. Also stores the set of inequality relationships. class PropertySet { + /// Returns true if V1 is a better choice than V2. Note that it is + /// not a total ordering. + bool compare(Value *V1, Value *V2) const { + if (isa(V1)) { + if (!isa(V2)) { + return true; + } + } else if (isa(V1)) { + if (!isa(V2) && !isa(V2)) { + return true; + } + } + if (Instruction *I1 = dyn_cast(V1)) { + if (Instruction *I2 = dyn_cast(V2)) { + BasicBlock *BB1 = I1->getParent(), + *BB2 = I2->getParent(); + if (BB1 == BB2) { + for (BasicBlock::const_iterator I = BB1->begin(), E = BB1->end(); + I != E; ++I) { + if (&*I == I1) return true; + if (&*I == I2) return false; + } + assert(0 && "Instructions not found in parent BasicBlock?"); + } else + return DT->getNode(BB1)->properlyDominates(DT->getNode(BB2)); + } + } + return false; + } + struct Property; public: - class Synonyms union_find; + /// Choose the canonical Value in a synonym set. + /// Leaves the more canonical choice in V1. + void order(Value *&V1, Value *&V2) const { + if (compare(V2, V1)) std::swap(V1, V2); + } + + PropertySet(DominatorTree *DT) : union_find(this), DT(DT) {} + + class Synonyms union_find; typedef std::vector::iterator PropertyIterator; typedef std::vector::const_iterator ConstPropertyIterator; - typedef Synonyms::iterator SynonymIterator; + typedef Synonyms::iterator SynonymIterator; enum Ops { EQ, @@ -231,7 +197,7 @@ namespace { } Value *lookup(Value *V) const { - Synonyms::iterator SI = union_find.findLeader(V); + SynonymIterator SI = union_find.findLeader(V); if (!SI) return NULL; return union_find.getLeader(SI); } @@ -313,7 +279,7 @@ namespace { // Represents Head OP [Tail1, Tail2, ...] // For example: %x != %a, %x != %b. struct VISIBILITY_HIDDEN Property { - typedef Synonyms::iterator Iter; + typedef SynonymIterator Iter; Property(Ops opcode, Iter i1, Iter i2) : Opcode(opcode), I1(i1), I2(i2) @@ -421,6 +387,7 @@ namespace { } } + DominatorTree *DT; public: #ifdef DEBUG void debug(std::ostream &os) const { @@ -484,6 +451,52 @@ namespace { RegisterPass X("predsimplify", "Predicate Simplifier"); + + template + typename Synonyms::iterator + Synonyms::unionSets(ElemTy E1, ElemTy E2) { + PS->order(E1, E2); + + iterator I1 = findLeader(E1), + I2 = findLeader(E2); + + if (!I1 && !I2) { // neither entry is in yet + leaders.push_back(E1); + I1 = leaders.size(); + mapping[E1] = I1; + mapping[E2] = I1; + return 0; + } + + if (!I1 && I2) { + mapping[E1] = I2; + std::swap(getLeader(I2), E1); + return 0; + } + + if (I1 && !I2) { + mapping[E2] = I1; + return 0; + } + + if (I1 == I2) return 0; + + // This is the case where we have two sets, [%a1, %a2, %a3] and + // [%p1, %p2, %p3] and someone says that %a2 == %p3. We need to + // combine the two synsets. + + if (I1 > I2) --I1; + + for (std::map::iterator I = mapping.begin(), + E = mapping.end(); I != E; ++I) { + if (I->second == I2) I->second = I1; + else if (I->second > I2) --I->second; + } + + leaders.erase(leaders.begin() + I2 - 1); + + return I2; + } } FunctionPass *llvm::createPredicateSimplifierPass() { @@ -494,7 +507,7 @@ bool PredicateSimplifier::runOnFunction(Function &F) { DT = &getAnalysis(); modified = false; - PropertySet KnownProperties; + PropertySet KnownProperties(DT); visitBasicBlock(DT->getRootNode()->getBlock(), KnownProperties); return modified; } @@ -614,6 +627,7 @@ void PredicateSimplifier::visitInstruction(Instruction *I, if (V != I) { modified = true; ++NumInstruction; + DEBUG(std::cerr << "Removing " << *I); I->replaceAllUsesWith(V); I->eraseFromParent(); return; diff --git a/test/Transforms/PredicateSimplifier/2006-09-20-ResolveCycle.ll b/test/Transforms/PredicateSimplifier/2006-09-20-ResolveCycle.ll new file mode 100644 index 00000000000..6b456b9502d --- /dev/null +++ b/test/Transforms/PredicateSimplifier/2006-09-20-ResolveCycle.ll @@ -0,0 +1,28 @@ +; RUN: llvm-as < %s | opt -predsimplify -disable-output + +void %gs_image_next() { +entry: + %tmp = load uint* null ; [#uses=2] + br bool false, label %cond_next21, label %UnifiedReturnBlock + +cond_next21: ; preds = %entry + br bool false, label %cond_next42, label %UnifiedReturnBlock + +cond_next42: ; preds = %cond_next21 + br label %cond_true158 + +cond_next134: ; preds = %cond_true158 + %tmp1571 = seteq uint 0, %min ; [#uses=0] + ret void + +cond_true158: ; preds = %cond_true158, %cond_next42 + %tmp47 = sub uint %tmp, 0 ; [#uses=2] + %tmp49 = setle uint %tmp47, 0 ; [#uses=1] + %min = select bool %tmp49, uint %tmp47, uint 0 ; [#uses=2] + %tmp92 = add uint %min, 0 ; [#uses=1] + %tmp101 = seteq uint %tmp92, %tmp ; [#uses=1] + br bool %tmp101, label %cond_next134, label %cond_true158 + +UnifiedReturnBlock: ; preds = %cond_next21, %entry + ret void +} -- 2.34.1