LLVM API Documentation
00001 //===- ValueNumbering.cpp - Value #'ing Implementation ----------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the non-abstract Value Numbering methods as well as a 00011 // default implementation for the analysis group. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Analysis/ValueNumbering.h" 00016 #include "llvm/Support/InstVisitor.h" 00017 #include "llvm/BasicBlock.h" 00018 #include "llvm/Instructions.h" 00019 #include "llvm/Pass.h" 00020 #include "llvm/Type.h" 00021 using namespace llvm; 00022 00023 // Register the ValueNumbering interface, providing a nice name to refer to. 00024 static RegisterAnalysisGroup<ValueNumbering> X("Value Numbering"); 00025 00026 /// ValueNumbering destructor: DO NOT move this to the header file for 00027 /// ValueNumbering or else clients of the ValueNumbering class may not depend on 00028 /// the ValueNumbering.o file in the current .a file, causing alias analysis 00029 /// support to not be included in the tool correctly! 00030 /// 00031 ValueNumbering::~ValueNumbering() {} 00032 00033 //===----------------------------------------------------------------------===// 00034 // Basic ValueNumbering Pass Implementation 00035 //===----------------------------------------------------------------------===// 00036 // 00037 // Because of the way .a files work, the implementation of the BasicVN class 00038 // MUST be in the ValueNumbering file itself, or else we run the risk of 00039 // ValueNumbering being used, but the default implementation not being linked 00040 // into the tool that uses it. As such, we register and implement the class 00041 // here. 00042 // 00043 00044 namespace { 00045 /// BasicVN - This class is the default implementation of the ValueNumbering 00046 /// interface. It walks the SSA def-use chains to trivially identify 00047 /// lexically identical expressions. This does not require any ahead of time 00048 /// analysis, so it is a very fast default implementation. 00049 /// 00050 struct BasicVN : public ImmutablePass, public ValueNumbering { 00051 /// getEqualNumberNodes - Return nodes with the same value number as the 00052 /// specified Value. This fills in the argument vector with any equal 00053 /// values. 00054 /// 00055 /// This is where our implementation is. 00056 /// 00057 virtual void getEqualNumberNodes(Value *V1, 00058 std::vector<Value*> &RetVals) const; 00059 }; 00060 00061 // Register this pass... 00062 RegisterOpt<BasicVN> 00063 X("basicvn", "Basic Value Numbering (default GVN impl)"); 00064 00065 // Declare that we implement the ValueNumbering interface 00066 RegisterAnalysisGroup<ValueNumbering, BasicVN, true> Y; 00067 00068 /// BVNImpl - Implement BasicVN in terms of a visitor class that 00069 /// handles the different types of instructions as appropriate. 00070 /// 00071 struct BVNImpl : public InstVisitor<BVNImpl> { 00072 std::vector<Value*> &RetVals; 00073 BVNImpl(std::vector<Value*> &RV) : RetVals(RV) {} 00074 00075 void handleBinaryInst(Instruction &I); 00076 void visitBinaryOperator(BinaryOperator &I) { 00077 handleBinaryInst((Instruction&)I); 00078 } 00079 void visitGetElementPtrInst(GetElementPtrInst &I); 00080 void visitCastInst(CastInst &I); 00081 void visitShiftInst(ShiftInst &I) { handleBinaryInst((Instruction&)I); } 00082 void visitInstruction(Instruction &) { 00083 // Cannot value number calls or terminator instructions... 00084 } 00085 }; 00086 } 00087 00088 // getEqualNumberNodes - Return nodes with the same value number as the 00089 // specified Value. This fills in the argument vector with any equal values. 00090 // 00091 void BasicVN::getEqualNumberNodes(Value *V, std::vector<Value*> &RetVals) const{ 00092 assert(V->getType() != Type::VoidTy && 00093 "Can only value number non-void values!"); 00094 // We can only handle the case where I is an instruction! 00095 if (Instruction *I = dyn_cast<Instruction>(V)) 00096 BVNImpl(RetVals).visit(I); 00097 } 00098 00099 void BVNImpl::visitCastInst(CastInst &CI) { 00100 Instruction &I = (Instruction&)CI; 00101 Value *Op = I.getOperand(0); 00102 Function *F = I.getParent()->getParent(); 00103 00104 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); 00105 UI != UE; ++UI) 00106 if (CastInst *Other = dyn_cast<CastInst>(*UI)) 00107 // Check that the types are the same, since this code handles casts... 00108 if (Other->getType() == I.getType() && 00109 // Is it embedded in the same function? (This could be false if LHS 00110 // is a constant or global!) 00111 Other->getParent()->getParent() == F && 00112 // Check to see if this new cast is not I. 00113 Other != &I) { 00114 // These instructions are identical. Add to list... 00115 RetVals.push_back(Other); 00116 } 00117 } 00118 00119 00120 // isIdenticalBinaryInst - Return true if the two binary instructions are 00121 // identical. 00122 // 00123 static inline bool isIdenticalBinaryInst(const Instruction &I1, 00124 const Instruction *I2) { 00125 // Is it embedded in the same function? (This could be false if LHS 00126 // is a constant or global!) 00127 if (I1.getOpcode() != I2->getOpcode() || 00128 I1.getParent()->getParent() != I2->getParent()->getParent()) 00129 return false; 00130 00131 // They are identical if both operands are the same! 00132 if (I1.getOperand(0) == I2->getOperand(0) && 00133 I1.getOperand(1) == I2->getOperand(1)) 00134 return true; 00135 00136 // If the instruction is commutative, the instruction can match if the 00137 // operands are swapped! 00138 // 00139 if ((I1.getOperand(0) == I2->getOperand(1) && 00140 I1.getOperand(1) == I2->getOperand(0)) && 00141 I1.isCommutative()) 00142 return true; 00143 00144 return false; 00145 } 00146 00147 void BVNImpl::handleBinaryInst(Instruction &I) { 00148 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 00149 Function *F = I.getParent()->getParent(); 00150 00151 for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end(); 00152 UI != UE; ++UI) 00153 if (Instruction *Other = dyn_cast<Instruction>(*UI)) 00154 // Check to see if this new binary operator is not I, but same operand... 00155 if (Other != &I && isIdenticalBinaryInst(I, Other)) { 00156 // These instructions are identical. Handle the situation. 00157 RetVals.push_back(Other); 00158 } 00159 } 00160 00161 // IdenticalComplexInst - Return true if the two instructions are the same, by 00162 // using a brute force comparison. This is useful for instructions with an 00163 // arbitrary number of arguments. 00164 // 00165 static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) { 00166 assert(I1->getOpcode() == I2->getOpcode()); 00167 // Equal if they are in the same function... 00168 return I1->getParent()->getParent() == I2->getParent()->getParent() && 00169 // And return the same type... 00170 I1->getType() == I2->getType() && 00171 // And have the same number of operands... 00172 I1->getNumOperands() == I2->getNumOperands() && 00173 // And all of the operands are equal. 00174 std::equal(I1->op_begin(), I1->op_end(), I2->op_begin()); 00175 } 00176 00177 void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) { 00178 Value *Op = I.getOperand(0); 00179 00180 // Try to pick a local operand if possible instead of a constant or a global 00181 // that might have a lot of uses. 00182 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) 00183 if (isa<Instruction>(I.getOperand(i)) || isa<Argument>(I.getOperand(i))) { 00184 Op = I.getOperand(i); 00185 break; 00186 } 00187 00188 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); 00189 UI != UE; ++UI) 00190 if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI)) 00191 // Check to see if this new getelementptr is not I, but same operand... 00192 if (Other != &I && IdenticalComplexInst(&I, Other)) { 00193 // These instructions are identical. Handle the situation. 00194 RetVals.push_back(Other); 00195 } 00196 } 00197 00198 void llvm::BasicValueNumberingStub() { }