X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FValueNumbering.cpp;h=bdb9422c238a5ed83809e755f3cae2762d830ab3;hb=04fa56932052f416ea911fe65615ebecbf154f6d;hp=519d9dbf97f08656b4a1d34b9be0919a53949665;hpb=c3a388143bad475aa0a565db3a2401cfc1df7273;p=oota-llvm.git diff --git a/lib/Analysis/ValueNumbering.cpp b/lib/Analysis/ValueNumbering.cpp index 519d9dbf97f..bdb9422c238 100644 --- a/lib/Analysis/ValueNumbering.cpp +++ b/lib/Analysis/ValueNumbering.cpp @@ -1,17 +1,28 @@ //===- ValueNumbering.cpp - Value #'ing Implementation ----------*- C++ -*-===// // +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// // This file implements the non-abstract Value Numbering methods as well as a // default implementation for the analysis group. // //===----------------------------------------------------------------------===// +#include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ValueNumbering.h" #include "llvm/Support/InstVisitor.h" #include "llvm/BasicBlock.h" +#include "llvm/Instructions.h" #include "llvm/Pass.h" #include "llvm/Type.h" -#include "llvm/iMemory.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"); @@ -32,13 +43,18 @@ ValueNumbering::~ValueNumbering() {} // into the tool that uses it. As such, we register and implement the class // here. // + namespace { /// BasicVN - This class is the default implementation of the ValueNumbering /// interface. It walks the SSA def-use chains to trivially identify /// 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. @@ -49,35 +65,42 @@ 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; -} // End of anonymous namespace + RegisterAnalysisGroup Y(X); -namespace { /// 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. } }; } +ImmutablePass *llvm::createBasicVNPass() { return new BasicVN(); } + // getEqualNumberNodes - Return nodes with the same value number as the // specified Value. This fills in the argument vector with any equal values. // @@ -93,66 +116,105 @@ void BVNImpl::visitCastInst(CastInst &CI) { Instruction &I = (Instruction&)CI; Value *Op = I.getOperand(0); Function *F = I.getParent()->getParent(); - + for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); UI != UE; ++UI) - if (Instruction *Other = dyn_cast(*UI)) - // Check to see if this new cast is not I, but has the same operand... - if (Other != &I && Other->getOpcode() == I.getOpcode() && - Other->getOperand(0) == Op && // Is the operand the same? - // Is it embeded in the same function? (This could be false if LHS + if (CastInst *Other = dyn_cast(*UI)) + // 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 && - - // Check that the types are the same, since this code handles casts... - Other->getType() == I.getType()) { - + // Check to see if this new cast is not I. + Other != &I) { // These instructions are identical. Add to list... RetVals.push_back(Other); } } +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. // static inline bool isIdenticalBinaryInst(const Instruction &I1, const Instruction *I2) { - // Is it embeded in the same function? (This could be false if LHS + // Is it embedded in the same function? (This could be false if LHS // is a constant or global!) if (I1.getOpcode() != I2->getOpcode() || 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)) return true; - - // If the instruction is commutative and associative, the instruction can - // match if the operands are swapped! + + // If the instruction is commutative, the instruction can match if the + // operands are swapped! // if ((I1.getOperand(0) == I2->getOperand(1) && I1.getOperand(1) == I2->getOperand(0)) && - (I1.getOpcode() == Instruction::Add || - I1.getOpcode() == Instruction::Mul || - I1.getOpcode() == Instruction::And || - I1.getOpcode() == Instruction::Or || - I1.getOpcode() == Instruction::Xor)) + I1.isCommutative()) return true; return false; } -void BVNImpl::handleBinaryInst(Instruction &I) { - Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); - Function *F = I.getParent()->getParent(); +// 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); + for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end(); UI != UE; ++UI) if (Instruction *Other = dyn_cast(*UI)) // Check to see if this new binary operator is not I, but same operand... - if (Other != &I && isIdenticalBinaryInst(I, Other)) { + if (Other != &I && isIdenticalBinaryInst(I, Other)) { // These instructions are identical. Handle the situation. RetVals.push_back(Other); } @@ -162,7 +224,8 @@ void BVNImpl::handleBinaryInst(Instruction &I) { // using a brute force comparison. This is useful for instructions with an // arbitrary number of arguments. // -static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) { +static inline bool IdenticalComplexInst(const Instruction *I1, + const Instruction *I2) { assert(I1->getOpcode() == I2->getOpcode()); // Equal if they are in the same function... return I1->getParent()->getParent() == I2->getParent()->getParent() && @@ -176,8 +239,15 @@ static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) { void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) { Value *Op = I.getOperand(0); - Function *F = I.getParent()->getParent(); - + + // Try to pick a local operand if possible instead of a constant or a global + // that might have a lot of uses. + for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) + if (isa(I.getOperand(i)) || isa(I.getOperand(i))) { + Op = I.getOperand(i); + break; + } + for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); UI != UE; ++UI) if (GetElementPtrInst *Other = dyn_cast(*UI)) @@ -187,3 +257,24 @@ void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) { RetVals.push_back(Other); } } + +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)