X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FValueNumbering.cpp;h=55323eaa9ed1be7b86aceb5246aa5d4d92756b21;hb=51cd9d6e073932fcb37f1857c66249d6c7d368ee;hp=fb3bed05531ac37b2155f1037229c6e6d9f9c2a6;hpb=7f8897f22e88271cfa114998a4d6088e7c8e8e11;p=oota-llvm.git diff --git a/lib/Analysis/ValueNumbering.cpp b/lib/Analysis/ValueNumbering.cpp index fb3bed05531..55323eaa9ed 100644 --- a/lib/Analysis/ValueNumbering.cpp +++ b/lib/Analysis/ValueNumbering.cpp @@ -2,14 +2,18 @@ // // 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 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. // +// The ValueNumbering analysis pass is mostly deprecated. It is only used by the +// Global Common Subexpression Elimination pass, which is deprecated by the +// Global Value Numbering pass (which does its value numbering on its own). +// //===----------------------------------------------------------------------===// #include "llvm/Analysis/Passes.h" @@ -19,10 +23,12 @@ #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"); +static RegisterAnalysisGroup V("Value Numbering"); /// ValueNumbering destructor: DO NOT move this to the header file for /// ValueNumbering or else clients of the ValueNumbering class may not depend on @@ -48,7 +54,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. @@ -58,23 +68,27 @@ namespace { virtual void getEqualNumberNodes(Value *V1, std::vector &RetVals) const; }; +} - // Register this pass... - RegisterPass - X("basicvn", "Basic Value Numbering (default GVN impl)"); +char BasicVN::ID = 0; +// Register this pass... +static RegisterPass +X("basicvn", "Basic Value Numbering (default GVN impl)", false, true); - // Declare that we implement the ValueNumbering interface - RegisterAnalysisGroup Y; +// Declare that we implement the ValueNumbering interface +static 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) {} + explicit BVNImpl(std::vector &RV) : RetVals(RV) {} void visitCastInst(CastInst &I); void visitGetElementPtrInst(GetElementPtrInst &I); + void visitCmpInst(CmpInst &I); void handleBinaryInst(Instruction &I); void visitBinaryOperator(Instruction &I) { handleBinaryInst(I); } @@ -112,8 +126,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 && @@ -124,6 +140,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. @@ -136,6 +174,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)) @@ -205,9 +248,9 @@ void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) { // 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); + for (User::op_iterator i = I.op_begin() + 1, e = I.op_end(); i != e; ++i) + if (isa(*i) || isa(*i)) { + Op = *i; break; }