Chris Lattner | 74542b6 | 2002-08-30 20:29:02 +0000 | [diff] [blame^] | 1 | //===- ValueNumbering.cpp - Value #'ing Implementation ----------*- C++ -*-===// |
| 2 | // |
| 3 | // This file implements the non-abstract Value Numbering methods as well as a |
| 4 | // default implementation for the analysis group. |
| 5 | // |
| 6 | //===----------------------------------------------------------------------===// |
| 7 | |
| 8 | #include "llvm/Analysis/BasicValueNumbering.h" |
| 9 | #include "llvm/Support/InstVisitor.h" |
| 10 | #include "llvm/BasicBlock.h" |
| 11 | #include "llvm/Type.h" |
| 12 | #include "llvm/iMemory.h" |
| 13 | #include "llvm/InstrTypes.h" |
| 14 | |
| 15 | // Register the ValueNumbering interface, providing a nice name to refer to. |
| 16 | static RegisterAnalysisGroup<ValueNumbering> X("Value Numbering"); |
| 17 | |
| 18 | /// ValueNumbering destructor: DO NOT move this to the header file for |
| 19 | /// ValueNumbering or else clients of the ValueNumbering class may not depend on |
| 20 | /// the ValueNumbering.o file in the current .a file, causing alias analysis |
| 21 | /// support to not be included in the tool correctly! |
| 22 | /// |
| 23 | ValueNumbering::~ValueNumbering() {} |
| 24 | |
| 25 | //===----------------------------------------------------------------------===// |
| 26 | // BasicValueNumbering Pass Implementation |
| 27 | //===----------------------------------------------------------------------===// |
| 28 | // |
| 29 | // Because of the way .a files work, the implementation of the |
| 30 | // BasicValueNumbering class MUST be in the ValueNumbering file itself, or else |
| 31 | // we run the risk of ValueNumbering being used, but the default implementation |
| 32 | // not being linked into the tool that uses it. As such, we register and |
| 33 | // implement the class here. |
| 34 | // |
| 35 | namespace { |
| 36 | // Register this pass... |
| 37 | RegisterOpt<BasicValueNumbering> |
| 38 | X("basicvn", "Basic Value Numbering (default GVN impl)"); |
| 39 | |
| 40 | // Declare that we implement the ValueNumbering interface |
| 41 | RegisterAnalysisGroup<ValueNumbering, BasicValueNumbering, true> Y; |
| 42 | } // End of anonymous namespace |
| 43 | |
| 44 | namespace { |
| 45 | /// BVNImpl - Implement BasicValueNumbering in terms of a visitor class that |
| 46 | /// handles the different types of instructions as appropriate. |
| 47 | /// |
| 48 | struct BVNImpl : public InstVisitor<BVNImpl> { |
| 49 | std::vector<Value*> &RetVals; |
| 50 | BVNImpl(std::vector<Value*> &RV) : RetVals(RV) {} |
| 51 | |
| 52 | void visitBinaryOperator(Instruction &I); |
| 53 | void visitGetElementPtrInst(GetElementPtrInst &I); |
| 54 | void visitCastInst(CastInst &I); |
| 55 | void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); } |
| 56 | void visitInstruction(Instruction &) { |
| 57 | // Cannot value number calls or terminator instructions... |
| 58 | } |
| 59 | }; |
| 60 | } |
| 61 | |
| 62 | // getEqualNumberNodes - Return nodes with the same value number as the |
| 63 | // specified Value. This fills in the argument vector with any equal values. |
| 64 | // |
| 65 | void BasicValueNumbering::getEqualNumberNodes(Value *V, |
| 66 | std::vector<Value*> &RetVals) const { |
| 67 | assert(V->getType() != Type::VoidTy && |
| 68 | "Can only value number non-void values!"); |
| 69 | // We can only handle the case where I is an instruction! |
| 70 | if (Instruction *I = dyn_cast<Instruction>(V)) |
| 71 | BVNImpl(RetVals).visit(I); |
| 72 | } |
| 73 | |
| 74 | void BVNImpl::visitCastInst(CastInst &CI) { |
| 75 | Instruction &I = (Instruction&)CI; |
| 76 | Value *Op = I.getOperand(0); |
| 77 | Function *F = I.getParent()->getParent(); |
| 78 | |
| 79 | for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); |
| 80 | UI != UE; ++UI) |
| 81 | if (Instruction *Other = dyn_cast<Instruction>(*UI)) |
| 82 | // Check to see if this new cast is not I, but has the same operand... |
| 83 | if (Other != &I && Other->getOpcode() == I.getOpcode() && |
| 84 | Other->getOperand(0) == Op && // Is the operand the same? |
| 85 | // Is it embeded in the same function? (This could be false if LHS |
| 86 | // is a constant or global!) |
| 87 | Other->getParent()->getParent() == F && |
| 88 | |
| 89 | // Check that the types are the same, since this code handles casts... |
| 90 | Other->getType() == I.getType()) { |
| 91 | |
| 92 | // These instructions are identical. Add to list... |
| 93 | RetVals.push_back(Other); |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | |
| 98 | // isIdenticalBinaryInst - Return true if the two binary instructions are |
| 99 | // identical. |
| 100 | // |
| 101 | static inline bool isIdenticalBinaryInst(const Instruction &I1, |
| 102 | const Instruction *I2) { |
| 103 | // Is it embeded in the same function? (This could be false if LHS |
| 104 | // is a constant or global!) |
| 105 | if (I1.getOpcode() != I2->getOpcode() || |
| 106 | I1.getParent()->getParent() != I2->getParent()->getParent()) |
| 107 | return false; |
| 108 | |
| 109 | // They are identical if both operands are the same! |
| 110 | if (I1.getOperand(0) == I2->getOperand(0) && |
| 111 | I1.getOperand(1) == I2->getOperand(1)) |
| 112 | return true; |
| 113 | |
| 114 | // If the instruction is commutative and associative, the instruction can |
| 115 | // match if the operands are swapped! |
| 116 | // |
| 117 | if ((I1.getOperand(0) == I2->getOperand(1) && |
| 118 | I1.getOperand(1) == I2->getOperand(0)) && |
| 119 | (I1.getOpcode() == Instruction::Add || |
| 120 | I1.getOpcode() == Instruction::Mul || |
| 121 | I1.getOpcode() == Instruction::And || |
| 122 | I1.getOpcode() == Instruction::Or || |
| 123 | I1.getOpcode() == Instruction::Xor)) |
| 124 | return true; |
| 125 | |
| 126 | return false; |
| 127 | } |
| 128 | |
| 129 | void BVNImpl::visitBinaryOperator(Instruction &I) { |
| 130 | Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); |
| 131 | Function *F = I.getParent()->getParent(); |
| 132 | |
| 133 | for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end(); |
| 134 | UI != UE; ++UI) |
| 135 | if (Instruction *Other = dyn_cast<Instruction>(*UI)) |
| 136 | // Check to see if this new binary operator is not I, but same operand... |
| 137 | if (Other != &I && isIdenticalBinaryInst(I, Other)) { |
| 138 | // These instructions are identical. Handle the situation. |
| 139 | RetVals.push_back(Other); |
| 140 | } |
| 141 | } |
| 142 | |
| 143 | // IdenticalComplexInst - Return true if the two instructions are the same, by |
| 144 | // using a brute force comparison. This is useful for instructions with an |
| 145 | // arbitrary number of arguments. |
| 146 | // |
| 147 | static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) { |
| 148 | assert(I1->getOpcode() == I2->getOpcode()); |
| 149 | // Equal if they are in the same function... |
| 150 | return I1->getParent()->getParent() == I2->getParent()->getParent() && |
| 151 | // And return the same type... |
| 152 | I1->getType() == I2->getType() && |
| 153 | // And have the same number of operands... |
| 154 | I1->getNumOperands() == I2->getNumOperands() && |
| 155 | // And all of the operands are equal. |
| 156 | std::equal(I1->op_begin(), I1->op_end(), I2->op_begin()); |
| 157 | } |
| 158 | |
| 159 | void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) { |
| 160 | Value *Op = I.getOperand(0); |
| 161 | Function *F = I.getParent()->getParent(); |
| 162 | |
| 163 | for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); |
| 164 | UI != UE; ++UI) |
| 165 | if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI)) |
| 166 | // Check to see if this new getelementptr is not I, but same operand... |
| 167 | if (Other != &I && IdenticalComplexInst(&I, Other)) { |
| 168 | // These instructions are identical. Handle the situation. |
| 169 | RetVals.push_back(Other); |
| 170 | } |
| 171 | } |