From 3688f268cb31dbfb5b36131d96af668fa2fc6a8d Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Fri, 15 Aug 2008 21:31:02 +0000 Subject: Remove GCSE, ValueNumbering, and LoadValueNumbering. These have been deprecated for almost a year; it's finally time for them to go away. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54822 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ValueNumbering.cpp | 286 ---------------------------------------- 1 file changed, 286 deletions(-) delete mode 100644 lib/Analysis/ValueNumbering.cpp (limited to 'lib/Analysis/ValueNumbering.cpp') diff --git a/lib/Analysis/ValueNumbering.cpp b/lib/Analysis/ValueNumbering.cpp deleted file mode 100644 index 55323eaa9e..0000000000 --- a/lib/Analysis/ValueNumbering.cpp +++ /dev/null @@ -1,286 +0,0 @@ -//===- ValueNumbering.cpp - Value #'ing Implementation ----------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// 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" -#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/Support/Compiler.h" -using namespace llvm; - -char ValueNumbering::ID = 0; -// Register the ValueNumbering interface, providing a nice name to refer to. -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 -/// the ValueNumbering.o file in the current .a file, causing alias analysis -/// support to not be included in the tool correctly! -/// -ValueNumbering::~ValueNumbering() {} - -//===----------------------------------------------------------------------===// -// Basic ValueNumbering Pass Implementation -//===----------------------------------------------------------------------===// -// -// Because of the way .a files work, the implementation of the BasicVN class -// MUST be in the ValueNumbering file itself, or else we run the risk of -// ValueNumbering being used, but the default implementation not being linked -// 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 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. - /// - /// This is where our implementation is. - /// - virtual void getEqualNumberNodes(Value *V1, - std::vector &RetVals) const; - }; -} - -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 -static RegisterAnalysisGroup Y(X); - -namespace { - /// BVNImpl - Implement BasicVN in terms of a visitor class that - /// handles the different types of instructions as appropriate. - /// - struct VISIBILITY_HIDDEN BVNImpl : public InstVisitor { - std::vector &RetVals; - 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); } - 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. - } - }; -} - -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. -// -void BasicVN::getEqualNumberNodes(Value *V, std::vector &RetVals) const{ - assert(V->getType() != Type::VoidTy && - "Can only value number non-void values!"); - // We can only handle the case where I is an instruction! - if (Instruction *I = dyn_cast(V)) - BVNImpl(RetVals).visit(I); -} - -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 (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 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 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, the instruction can match if the - // operands are swapped! - // - if ((I1.getOperand(0) == I2->getOperand(1) && - I1.getOperand(1) == I2->getOperand(0)) && - I1.isCommutative()) - return true; - - 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); - - 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)) { - // These instructions are identical. Handle the situation. - RetVals.push_back(Other); - } -} - -// IdenticalComplexInst - Return true if the two instructions are the same, by -// using a brute force comparison. This is useful for instructions with an -// arbitrary number of arguments. -// -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() && - // And return the same type... - I1->getType() == I2->getType() && - // And have the same number of operands... - I1->getNumOperands() == I2->getNumOperands() && - // And all of the operands are equal. - std::equal(I1->op_begin(), I1->op_end(), I2->op_begin()); -} - -void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) { - Value *Op = I.getOperand(0); - - // Try to pick a local operand if possible instead of a constant or a global - // that might have a lot of uses. - for (User::op_iterator i = I.op_begin() + 1, e = I.op_end(); i != e; ++i) - if (isa(*i) || isa(*i)) { - Op = *i; - break; - } - - for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); - UI != UE; ++UI) - if (GetElementPtrInst *Other = dyn_cast(*UI)) - // Check to see if this new getelementptr is not I, but same operand... - if (Other != &I && IdenticalComplexInst(&I, Other)) { - // These instructions are identical. Handle the situation. - 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) -- cgit v1.2.3