X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FValueNumbering.cpp;h=bdb9422c238a5ed83809e755f3cae2762d830ab3;hb=2f0d1ea864ff0fe59c5a2b35390a82fad2865b61;hp=0ca280106ba71392c19f377641cad920d7988f50;hpb=2b37d7cf28b1382420b5e4007042feeb66d21ac8;p=oota-llvm.git diff --git a/lib/Analysis/ValueNumbering.cpp b/lib/Analysis/ValueNumbering.cpp index 0ca280106ba..bdb9422c238 100644 --- a/lib/Analysis/ValueNumbering.cpp +++ b/lib/Analysis/ValueNumbering.cpp @@ -19,8 +19,10 @@ #include "llvm/Instructions.h" #include "llvm/Pass.h" #include "llvm/Type.h" +#include "llvm/Support/Compiler.h" using namespace llvm; +char ValueNumbering::ID = 0; // Register the ValueNumbering interface, providing a nice name to refer to. static RegisterAnalysisGroup X("Value Numbering"); @@ -48,7 +50,11 @@ namespace { /// lexically identical expressions. This does not require any ahead of time /// analysis, so it is a very fast default implementation. /// - struct BasicVN : public ImmutablePass, public ValueNumbering { + struct VISIBILITY_HIDDEN BasicVN + : public ImmutablePass, public ValueNumbering { + static char ID; // Class identification, replacement for typeinfo + BasicVN() : ImmutablePass((intptr_t)&ID) {} + /// getEqualNumberNodes - Return nodes with the same value number as the /// specified Value. This fills in the argument vector with any equal /// values. @@ -59,29 +65,36 @@ namespace { std::vector &RetVals) const; }; + char BasicVN::ID = 0; // Register this pass... - RegisterOpt + RegisterPass X("basicvn", "Basic Value Numbering (default GVN impl)"); // Declare that we implement the ValueNumbering interface - RegisterAnalysisGroup Y; + RegisterAnalysisGroup Y(X); /// BVNImpl - Implement BasicVN in terms of a visitor class that /// handles the different types of instructions as appropriate. /// - struct BVNImpl : public InstVisitor { + struct VISIBILITY_HIDDEN BVNImpl : public InstVisitor { std::vector &RetVals; BVNImpl(std::vector &RV) : RetVals(RV) {} - void handleBinaryInst(Instruction &I); - void visitBinaryOperator(BinaryOperator &I) { - handleBinaryInst((Instruction&)I); - } - void visitGetElementPtrInst(GetElementPtrInst &I); void visitCastInst(CastInst &I); - void visitShiftInst(ShiftInst &I) { handleBinaryInst((Instruction&)I); } + void visitGetElementPtrInst(GetElementPtrInst &I); + void visitCmpInst(CmpInst &I); + + void handleBinaryInst(Instruction &I); + void visitBinaryOperator(Instruction &I) { handleBinaryInst(I); } + void visitShiftInst(Instruction &I) { handleBinaryInst(I); } + void visitExtractElementInst(Instruction &I) { handleBinaryInst(I); } + + void handleTernaryInst(Instruction &I); + void visitSelectInst(Instruction &I) { handleTernaryInst(I); } + void visitInsertElementInst(Instruction &I) { handleTernaryInst(I); } + void visitShuffleVectorInst(Instruction &I) { handleTernaryInst(I); } void visitInstruction(Instruction &) { - // Cannot value number calls or terminator instructions... + // Cannot value number calls or terminator instructions. } }; } @@ -107,8 +120,10 @@ void BVNImpl::visitCastInst(CastInst &CI) { for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); UI != UE; ++UI) if (CastInst *Other = dyn_cast(*UI)) - // Check that the types are the same, since this code handles casts... - if (Other->getType() == I.getType() && + // Check that the opcode is the same + if (Other->getOpcode() == Instruction::CastOps(I.getOpcode()) && + // Check that the destination types are the same + Other->getType() == I.getType() && // Is it embedded in the same function? (This could be false if LHS // is a constant or global!) Other->getParent()->getParent() == F && @@ -119,6 +134,28 @@ void BVNImpl::visitCastInst(CastInst &CI) { } } +void BVNImpl::visitCmpInst(CmpInst &CI1) { + Value *LHS = CI1.getOperand(0); + for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end(); + UI != UE; ++UI) + if (CmpInst *CI2 = dyn_cast(*UI)) + // Check to see if this compare instruction is not CI, but same opcode, + // same predicate, and in the same function. + if (CI2 != &CI1 && CI2->getOpcode() == CI1.getOpcode() && + CI2->getPredicate() == CI1.getPredicate() && + CI2->getParent()->getParent() == CI1.getParent()->getParent()) + // If the operands are the same + if ((CI2->getOperand(0) == CI1.getOperand(0) && + CI2->getOperand(1) == CI1.getOperand(1)) || + // Or the compare is commutative and the operands are reversed + (CI1.isCommutative() && + CI2->getOperand(0) == CI1.getOperand(1) && + CI2->getOperand(1) == CI1.getOperand(0))) + // Then the instructiosn are identical, add to list. + RetVals.push_back(CI2); +} + + // isIdenticalBinaryInst - Return true if the two binary instructions are // identical. @@ -131,6 +168,11 @@ static inline bool isIdenticalBinaryInst(const Instruction &I1, I1.getParent()->getParent() != I2->getParent()->getParent()) return false; + // If they are CmpInst instructions, check their predicates + if (CmpInst *CI1 = dyn_cast(&const_cast(I1))) + if (CI1->getPredicate() != cast(I2)->getPredicate()) + return false; + // They are identical if both operands are the same! if (I1.getOperand(0) == I2->getOperand(0) && I1.getOperand(1) == I2->getOperand(1)) @@ -147,6 +189,24 @@ static inline bool isIdenticalBinaryInst(const Instruction &I1, return false; } +// isIdenticalTernaryInst - Return true if the two ternary instructions are +// identical. +// +static inline bool isIdenticalTernaryInst(const Instruction &I1, + const Instruction *I2) { + // Is it embedded in the same function? (This could be false if LHS + // is a constant or global!) + if (I1.getParent()->getParent() != I2->getParent()->getParent()) + return false; + + // They are identical if all operands are the same! + return I1.getOperand(0) == I2->getOperand(0) && + I1.getOperand(1) == I2->getOperand(1) && + I1.getOperand(2) == I2->getOperand(2); +} + + + void BVNImpl::handleBinaryInst(Instruction &I) { Value *LHS = I.getOperand(0); @@ -198,4 +258,23 @@ void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) { } } -void llvm::BasicValueNumberingStub() { } +void BVNImpl::handleTernaryInst(Instruction &I) { + Value *Op0 = I.getOperand(0); + Instruction *OtherInst; + + for (Value::use_iterator UI = Op0->use_begin(), UE = Op0->use_end(); + UI != UE; ++UI) + if ((OtherInst = dyn_cast(*UI)) && + OtherInst->getOpcode() == I.getOpcode()) { + // Check to see if this new select is not I, but has the same operands. + if (OtherInst != &I && isIdenticalTernaryInst(I, OtherInst)) { + // These instructions are identical. Handle the situation. + RetVals.push_back(OtherInst); + } + + } +} + + +// Ensure that users of ValueNumbering.h will link with this file +DEFINING_FILE_FOR(BasicValueNumbering)