path: root/lib/Analysis/LoadValueNumbering.cpp

//===- LoadValueNumbering.cpp - Load Value #'ing Implementation -*- C++ -*-===//
//
//                     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 implements a value numbering pass that value numbers load and call
// instructions.  To do this, it finds lexically identical load instructions,
// and uses alias analysis to determine which loads are guaranteed to produce
// the same value.  To value number call instructions, it looks for calls to
// functions that do not write to memory which do not have intervening
// instructions that clobber the memory that is read from.
//
// This pass builds off of another value numbering pass to implement value
// numbering for non-load and non-call instructions.  It uses Alias Analysis so
// that it can disambiguate the load instructions.  The more powerful these base
// analyses are, the more powerful the resultant value numbering will be.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoadValueNumbering.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Type.h"
#include "llvm/Analysis/ValueNumbering.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Target/TargetData.h"
#include <set>
#include <algorithm>
using namespace llvm;

namespace {
  // FIXME: This should not be a FunctionPass.
  struct VISIBILITY_HIDDEN LoadVN : public FunctionPass, public ValueNumbering {

    /// Pass Implementation stuff.  This doesn't do any analysis.
    ///
    bool runOnFunction(Function &) { return false; }

    /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
    /// and Alias Analysis.
    ///
    virtual void getAnalysisUsage(AnalysisUsage &AU) const;

    /// getEqualNumberNodes - Return nodes with the same value number as the
    /// specified Value.  This fills in the argument vector with any equal
    /// values.
    ///
    virtual void getEqualNumberNodes(Value *V1,
                                     std::vector<Value*> &RetVals) const;

    /// deleteValue - This method should be called whenever an LLVM Value is
    /// deleted from the program, for example when an instruction is found to be
    /// redundant and is eliminated.
    ///
    virtual void deleteValue(Value *V) {
      getAnalysis<AliasAnalysis>().deleteValue(V);
    }

    /// copyValue - This method should be used whenever a preexisting value in
    /// the program is copied or cloned, introducing a new value.  Note that
    /// analysis implementations should tolerate clients that use this method to
    /// introduce the same value multiple times: if the analysis already knows
    /// about a value, it should ignore the request.
    ///
    virtual void copyValue(Value *From, Value *To) {
      getAnalysis<AliasAnalysis>().copyValue(From, To);
    }

    /// getCallEqualNumberNodes - Given a call instruction, find other calls
    /// that have the same value number.
    void getCallEqualNumberNodes(CallInst *CI,
                                 std::vector<Value*> &RetVals) const;
  };

  // Register this pass...
  RegisterPass<LoadVN> X("load-vn", "Load Value Numbering");

  // Declare that we implement the ValueNumbering interface
  RegisterAnalysisGroup<ValueNumbering> Y(X);
}

FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }


/// getAnalysisUsage - Does not modify anything.  It uses Value Numbering and
/// Alias Analysis.
///
void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesAll();
  AU.addRequiredTransitive<AliasAnalysis>();
  AU.addRequired<ValueNumbering>();
  AU.addRequiredTransitive<DominatorSet>();
  AU.addRequiredTransitive<TargetData>();
}

static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom,
                                Value *Ptr, unsigned Size, AliasAnalysis &AA,
                                std::set<BasicBlock*> &Visited,
                                std::map<BasicBlock*, bool> &TransparentBlocks){
  // If we have already checked out this path, or if we reached our destination,
  // stop searching, returning success.
  if (CurBlock == Dom || !Visited.insert(CurBlock).second)
    return true;

  // Check whether this block is known transparent or not.
  std::map<BasicBlock*, bool>::iterator TBI =
    TransparentBlocks.lower_bound(CurBlock);

  if (TBI == TransparentBlocks.end() || TBI->first != CurBlock) {
    // If this basic block can modify the memory location, then the path is not
    // transparent!
    if (AA.canBasicBlockModify(*CurBlock, Ptr, Size)) {
      TransparentBlocks.insert(TBI, std::make_pair(CurBlock, false));
      return false;
    }
    TransparentBlocks.insert(TBI, std::make_pair(CurBlock, true));
  } else if (!TBI->second)
    // This block is known non-transparent, so that path can't be either.
    return false;

  // The current block is known to be transparent.  The entire path is
  // transparent if all of the predecessors paths to the parent is also
  // transparent to the memory location.
  for (pred_iterator PI = pred_begin(CurBlock), E = pred_end(CurBlock);
       PI != E; ++PI)
    if (!isPathTransparentTo(*PI, Dom, Ptr, Size, AA, Visited,
                             TransparentBlocks))
      return false;
  return true;
}

/// getCallEqualNumberNodes - Given a call instruction, find other calls that
/// have the same value number.
void LoadVN::getCallEqualNumberNodes(CallInst *CI,
                                     std::vector<Value*> &RetVals) const {
  Function *CF = CI->getCalledFunction();
  if (CF == 0) return;  // Indirect call.
  AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
  AliasAnalysis::ModRefBehavior MRB = AA.getModRefBehavior(CF, CI);
  if (MRB != AliasAnalysis::DoesNotAccessMemory &&
      MRB != AliasAnalysis::OnlyReadsMemory)
    return;  // Nothing we can do for now.

  // Scan all of the arguments of the function, looking for one that is not
  // global.  In particular, we would prefer to have an argument or instruction
  // operand to chase the def-use chains of.
  Value *Op = CF;
  for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
    if (isa<Argument>(CI->getOperand(i)) ||
        isa<Instruction>(CI->getOperand(i))) {
      Op = CI->getOperand(i);
      break;
    }

  // Identify all lexically identical calls in this function.
  std::vector<CallInst*> IdenticalCalls;

  Function *CIFunc = CI->getParent()->getParent();
  for (Value::use_iterator UI = Op->use_begin(), E = Op->use_end(); UI != E;
       ++UI)
    if (CallInst *C = dyn_cast<CallInst>(*UI))
      if (C->getNumOperands() == CI->getNumOperands() &&
          C->getOperand(0) == CI->getOperand(0) &&
          C->getParent()->getParent() == CIFunc && C != CI) {
        bool AllOperandsEqual = true;
        for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
          if (C->getOperand(i) != CI->getOperand(i)) {
            AllOperandsEqual = false;
            break;
          }

        if (AllOperandsEqual)
          IdenticalCalls.push_back(C);
      }

  if (IdenticalCalls.empty()) return;

  // Eliminate duplicates, which could occur if we chose a value that is passed
  // into a call site multiple times.
  std::sort(IdenticalCalls.begin(), IdenticalCalls.end());
  IdenticalCalls.erase(std::unique(IdenticalCalls.begin(),IdenticalCalls.end()),
                       IdenticalCalls.end());

  // If the call reads memory, we must make sure that there are no stores
  // between the calls in question.
  //
  // FIXME: This should use mod/ref information.  What we really care about it
  // whether an intervening instruction could modify memory that is read, not
  // ANY memory.
  //
  if (MRB == AliasAnalysis::OnlyReadsMemory) {
    DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
    BasicBlock *CIBB = CI->getParent();
    for (unsigned i = 0; i != IdenticalCalls.size(); ++i) {