lib/Analysis/ValueNumbering.cpp

   1 //===- ValueNumbering.cpp - Value #'ing Implementation ----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the non-abstract Value Numbering methods as well as a
  11 // default implementation for the analysis group.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/ValueNumbering.h"
  16 #include "llvm/Support/InstVisitor.h"
  17 #include "llvm/BasicBlock.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/Pass.h"
  20 #include "llvm/Type.h"
  21 using namespace llvm;
  22
  23 // Register the ValueNumbering interface, providing a nice name to refer to.
  24 static RegisterAnalysisGroup<ValueNumbering> X("Value Numbering");
  25
  26 /// ValueNumbering destructor: DO NOT move this to the header file for
  27 /// ValueNumbering or else clients of the ValueNumbering class may not depend on
  28 /// the ValueNumbering.o file in the current .a file, causing alias analysis
  29 /// support to not be included in the tool correctly!
  30 ///
  31 ValueNumbering::~ValueNumbering() {}
  32
  33 //===----------------------------------------------------------------------===//
  34 // Basic ValueNumbering Pass Implementation
  35 //===----------------------------------------------------------------------===//
  36 //
  37 // Because of the way .a files work, the implementation of the BasicVN class
  38 // MUST be in the ValueNumbering file itself, or else we run the risk of
  39 // ValueNumbering being used, but the default implementation not being linked
  40 // into the tool that uses it.  As such, we register and implement the class
  41 // here.
  42 //
  43
  44 namespace {
  45   /// BasicVN - This class is the default implementation of the ValueNumbering
  46   /// interface.  It walks the SSA def-use chains to trivially identify
  47   /// lexically identical expressions.  This does not require any ahead of time
  48   /// analysis, so it is a very fast default implementation.
  49   ///
  50   struct BasicVN : public ImmutablePass, public ValueNumbering {
  51     /// getEqualNumberNodes - Return nodes with the same value number as the
  52     /// specified Value.  This fills in the argument vector with any equal
  53     /// values.
  54     ///
  55     /// This is where our implementation is.
  56     ///
  57     virtual void getEqualNumberNodes(Value *V1,
  58                                      std::vector<Value*> &RetVals) const;
  59   };
  60
  61   // Register this pass...
  62   RegisterOpt<BasicVN>
  63   X("basicvn", "Basic Value Numbering (default GVN impl)");
  64
  65   // Declare that we implement the ValueNumbering interface
  66   RegisterAnalysisGroup<ValueNumbering, BasicVN, true> Y;
  67
  68   /// BVNImpl - Implement BasicVN in terms of a visitor class that
  69   /// handles the different types of instructions as appropriate.
  70   ///
  71   struct BVNImpl : public InstVisitor<BVNImpl> {
  72     std::vector<Value*> &RetVals;
  73     BVNImpl(std::vector<Value*> &RV) : RetVals(RV) {}
  74
  75     void handleBinaryInst(Instruction &I);
  76     void visitBinaryOperator(BinaryOperator &I) {
  77       handleBinaryInst((Instruction&)I);
  78     }
  79     void visitGetElementPtrInst(GetElementPtrInst &I);
  80     void visitCastInst(CastInst &I);
  81     void visitShiftInst(ShiftInst &I) { handleBinaryInst((Instruction&)I); }
  82     void visitInstruction(Instruction &) {
  83       // Cannot value number calls or terminator instructions...
  84     }
  85   };
  86 }
  87
  88 // getEqualNumberNodes - Return nodes with the same value number as the
  89 // specified Value.  This fills in the argument vector with any equal values.
  90 //
  91 void BasicVN::getEqualNumberNodes(Value *V, std::vector<Value*> &RetVals) const{
  92   assert(V->getType() != Type::VoidTy &&
  93          "Can only value number non-void values!");
  94   // We can only handle the case where I is an instruction!
  95   if (Instruction *I = dyn_cast<Instruction>(V))
  96     BVNImpl(RetVals).visit(I);
  97 }
  98
  99 void BVNImpl::visitCastInst(CastInst &CI) {
 100   Instruction &I = (Instruction&)CI;
 101   Value *Op = I.getOperand(0);
 102   Function *F = I.getParent()->getParent();
 103
 104   for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
 105        UI != UE; ++UI)
 106     if (CastInst *Other = dyn_cast<CastInst>(*UI))
 107       // Check that the types are the same, since this code handles casts...
 108       if (Other->getType() == I.getType() &&
 109           // Is it embedded in the same function?  (This could be false if LHS
 110           // is a constant or global!)
 111           Other->getParent()->getParent() == F &&
 112           // Check to see if this new cast is not I.
 113           Other != &I) {
 114         // These instructions are identical.  Add to list...
 115         RetVals.push_back(Other);
 116       }
 117 }
 118
 119
 120 // isIdenticalBinaryInst - Return true if the two binary instructions are
 121 // identical.
 122 //
 123 static inline bool isIdenticalBinaryInst(const Instruction &I1,
 124                                          const Instruction *I2) {
 125   // Is it embedded in the same function?  (This could be false if LHS
 126   // is a constant or global!)
 127   if (I1.getOpcode() != I2->getOpcode() ||
 128       I1.getParent()->getParent() != I2->getParent()->getParent())
 129     return false;
 130
 131   // They are identical if both operands are the same!
 132   if (I1.getOperand(0) == I2->getOperand(0) &&
 133       I1.getOperand(1) == I2->getOperand(1))
 134     return true;
 135
 136   // If the instruction is commutative, the instruction can match if the
 137   // operands are swapped!
 138   //
 139   if ((I1.getOperand(0) == I2->getOperand(1) &&
 140        I1.getOperand(1) == I2->getOperand(0)) &&
 141       I1.isCommutative())
 142     return true;
 143
 144   return false;
 145 }
 146
 147 void BVNImpl::handleBinaryInst(Instruction &I) {
 148   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 149   Function *F = I.getParent()->getParent();
 150
 151   for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end();
 152        UI != UE; ++UI)
 153     if (Instruction *Other = dyn_cast<Instruction>(*UI))
 154       // Check to see if this new binary operator is not I, but same operand...
 155       if (Other != &I && isIdenticalBinaryInst(I, Other)) {
 156         // These instructions are identical.  Handle the situation.
 157         RetVals.push_back(Other);
 158       }
 159 }
 160
 161 // IdenticalComplexInst - Return true if the two instructions are the same, by
 162 // using a brute force comparison.  This is useful for instructions with an
 163 // arbitrary number of arguments.
 164 //
 165 static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) {
 166   assert(I1->getOpcode() == I2->getOpcode());
 167   // Equal if they are in the same function...
 168   return I1->getParent()->getParent() == I2->getParent()->getParent() &&
 169     // And return the same type...
 170     I1->getType() == I2->getType() &&
 171     // And have the same number of operands...
 172     I1->getNumOperands() == I2->getNumOperands() &&
 173     // And all of the operands are equal.
 174     std::equal(I1->op_begin(), I1->op_end(), I2->op_begin());
 175 }
 176
 177 void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) {
 178   Value *Op = I.getOperand(0);
 179
 180   // Try to pick a local operand if possible instead of a constant or a global
 181   // that might have a lot of uses.
 182   for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i)
 183     if (isa<Instruction>(I.getOperand(i)) || isa<Argument>(I.getOperand(i))) {
 184       Op = I.getOperand(i);
 185       break;
 186     }
 187
 188   for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
 189        UI != UE; ++UI)
 190     if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI))
 191       // Check to see if this new getelementptr is not I, but same operand...
 192       if (Other != &I && IdenticalComplexInst(&I, Other)) {
 193         // These instructions are identical.  Handle the situation.
 194         RetVals.push_back(Other);
 195       }
 196 }
 197
 198 void llvm::BasicValueNumberingStub() { }