From 890e1a040155e8b69d258bc18ba7f0769c7c989a Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Thu, 28 Jun 2007 23:51:21 +0000 Subject: [PATCH] Add support for performing GVNPRE on select instructions. This fixes test/Transforms/GVNPRE/select.ll. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37783 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/GVNPRE.cpp | 70 ++++++++++++++++++++++++++------ 1 file changed, 57 insertions(+), 13 deletions(-) diff --git a/lib/Transforms/Scalar/GVNPRE.cpp b/lib/Transforms/Scalar/GVNPRE.cpp index 94f5d281426..e6e7cb20989 100644 --- a/lib/Transforms/Scalar/GVNPRE.cpp +++ b/lib/Transforms/Scalar/GVNPRE.cpp @@ -59,7 +59,7 @@ namespace { FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, - SHUFFLE }; + SHUFFLE, SELECT }; ExpressionOpcode opcode; uint32_t firstVN; @@ -101,10 +101,11 @@ namespace { Expression create_expression(ShuffleVectorInst* V); Expression create_expression(ExtractElementInst* C); Expression create_expression(InsertElementInst* V); + Expression create_expression(SelectInst* V); public: ValueTable() { nextValueNumber = 1; } uint32_t lookup_or_add(Value* V); - uint32_t lookup(Value* V); + uint32_t lookup(Value* V) const; void add(Value* V, uint32_t num); void clear(); void erase(Value* v); @@ -279,6 +280,17 @@ ValueTable::Expression ValueTable::create_expression(InsertElementInst* I) { return e; } +ValueTable::Expression ValueTable::create_expression(SelectInst* I) { + Expression e; + + e.firstVN = lookup_or_add(I->getCondition()); + e.secondVN = lookup_or_add(I->getTrueValue()); + e.thirdVN = lookup_or_add(I->getFalseValue()); + e.opcode = Expression::SELECT; + + return e; +} + //===----------------------------------------------------------------------===// // ValueTable External Functions //===----------------------------------------------------------------------===// @@ -346,6 +358,19 @@ uint32_t ValueTable::lookup_or_add(Value* V) { } else if (InsertElementInst* U = dyn_cast(V)) { Expression e = create_expression(U); + std::map::iterator EI = expressionNumbering.find(e); + if (EI != expressionNumbering.end()) { + valueNumbering.insert(std::make_pair(V, EI->second)); + return EI->second; + } else { + expressionNumbering.insert(std::make_pair(e, nextValueNumber)); + valueNumbering.insert(std::make_pair(V, nextValueNumber)); + + return nextValueNumber++; + } + } else if (SelectInst* U = dyn_cast(V)) { + Expression e = create_expression(U); + std::map::iterator EI = expressionNumbering.find(e); if (EI != expressionNumbering.end()) { valueNumbering.insert(std::make_pair(V, EI->second)); @@ -364,7 +389,7 @@ uint32_t ValueTable::lookup_or_add(Value* V) { /// lookup - Returns the value number of the specified value. Fails if /// the value has not yet been numbered. -uint32_t ValueTable::lookup(Value* V) { +uint32_t ValueTable::lookup(Value* V) const { DenseMap::iterator VI = valueNumbering.find(V); if (VI != valueNumbering.end()) return VI->second; @@ -579,7 +604,8 @@ Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) { } // Ternary Operations - } else if (isa(V) || isa(V)) { + } else if (isa(V) || isa(V) || + isa(V)) { User* U = cast(V); Value* newOp1 = 0; @@ -619,6 +645,8 @@ Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) { else if (InsertElementInst* I = dyn_cast(U)) newVal = new InsertElementInst(newOp1, newOp2, newOp3, I->getName()+".expr"); + else if (SelectInst* I = dyn_cast(U)) + newVal = new SelectInst(newOp1, newOp2, newOp3, I->getName()+".expr"); uint32_t v = VN.lookup_or_add(newVal); @@ -700,7 +728,8 @@ void GVNPRE::clean(SmallPtrSet& set, BitVector& presentInSet) { } // Handle ternary ops - } else if (isa(v) || isa(v)) { + } else if (isa(v) || isa(v) || + isa(v)) { User* U = cast(v); bool lhsValid = !isa(U->getOperand(0)); @@ -759,7 +788,8 @@ void GVNPRE::topo_sort(SmallPtrSet& set, std::vector& vec) { } // Handle ternary ops - } else if (isa(e) || isa(e)) { + } else if (isa(e) || isa(e) || + isa(e)) { User* U = cast(e); Value* l = find_leader(set, VN.lookup(U->getOperand(0))); Value* r = find_leader(set, VN.lookup(U->getOperand(1))); @@ -797,6 +827,7 @@ void GVNPRE::dump(const SmallPtrSet& s) const { DOUT << "{ "; for (SmallPtrSet::iterator I = s.begin(), E = s.end(); I != E; ++I) { + DOUT << "" << VN.lookup(*I) << ": "; DEBUG((*I)->dump()); } DOUT << "}\n\n"; @@ -828,7 +859,7 @@ bool GVNPRE::elimination() { if (isa(BI) || isa(BI) || isa(BI) || isa(BI) || - isa(BI)) { + isa(BI) || isa(BI)) { Value *leader = find_leader(availableOut[BB], VN.lookup(BI)); if (leader != 0) @@ -913,7 +944,8 @@ void GVNPRE::buildsets_availout(BasicBlock::iterator I, } // Handle ternary ops - } else if (isa(I) || isa(I)) { + } else if (isa(I) || isa(I) || + isa(I)) { User* U = cast(I); Value* leftValue = U->getOperand(0); Value* rightValue = U->getOperand(1); @@ -1157,7 +1189,8 @@ void GVNPRE::insertion_pre(Value* e, BasicBlock* BB, isa(U->getOperand(0)) || isa(U->getOperand(0)) || isa(U->getOperand(0)) || - isa(U->getOperand(0))) + isa(U->getOperand(0)) || + isa(U->getOperand(0))) s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0))); else s1 = U->getOperand(0); @@ -1167,7 +1200,8 @@ void GVNPRE::insertion_pre(Value* e, BasicBlock* BB, isa(U->getOperand(1)) || isa(U->getOperand(1)) || isa(U->getOperand(1)) || - isa(U->getOperand(1))) + isa(U->getOperand(1)) || + isa(U->getOperand(1))) s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1))); else s2 = U->getOperand(1); @@ -1175,12 +1209,14 @@ void GVNPRE::insertion_pre(Value* e, BasicBlock* BB, // Ternary Operators Value* s3 = 0; if (isa(U) || - isa(U)) + isa(U) || + isa(U)) if (isa(U->getOperand(2)) || isa(U->getOperand(2)) || isa(U->getOperand(2)) || isa(U->getOperand(2)) || - isa(U->getOperand(2))) + isa(U->getOperand(2)) || + isa(U->getOperand(2))) s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2))); else s3 = U->getOperand(2); @@ -1203,6 +1239,11 @@ void GVNPRE::insertion_pre(Value* e, BasicBlock* BB, else if (ExtractElementInst* S = dyn_cast(U)) newVal = new ExtractElementInst(s1, s2, S->getName()+".gvnpre", (*PI)->getTerminator()); + else if (SelectInst* S = dyn_cast(U)) + newVal = new SelectInst(S->getCondition(), S->getTrueValue(), + S->getFalseValue(), S->getName()+".gvnpre", + (*PI)->getTerminator()); + VN.add(newVal, VN.lookup(U)); @@ -1248,7 +1289,7 @@ unsigned GVNPRE::insertion_mergepoint(std::vector& workList, if (isa(e) || isa(e) || isa(e) || isa(e) || - isa(e)) { + isa(e) || isa(e)) { if (find_leader(availableOut[D->getIDom()->getBlock()], VN.lookup(e)) != 0) continue; @@ -1366,6 +1407,9 @@ bool GVNPRE::runOnFunction(Function &F) { buildsets(F); for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { + DOUT << "AVAIL_OUT: " << FI->getName() << "\n"; + dump(availableOut[FI]); + DOUT << "\n"; DOUT << "ANTIC_IN: " << FI->getName() << "\n"; dump(anticipatedIn[FI]); DOUT << "\n\n"; -- 2.34.1