path: root/lib/Transforms/Scalar/GVNPRE.cpp

//===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the Owen Anderson and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass performs a hybrid of global value numbering and partial redundancy
// elimination, known as GVN-PRE.  It performs partial redundancy elimination on
// values, rather than lexical expressions, allowing a more comprehensive view 
// the optimization.  It replaces redundant values with uses of earlier 
// occurences of the same value.  While this is beneficial in that it eliminates
// unneeded computation, it also increases register pressure by creating large
// live ranges, and should be used with caution on platforms that are very 
// sensitive to register pressure.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "gvnpre"
#include "llvm/Value.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include <algorithm>
#include <deque>
#include <map>
#include <vector>
#include <set>
using namespace llvm;

struct ExprLT {
  bool operator()(Value* left, Value* right) {
    if (BinaryOperator* leftBO = dyn_cast<BinaryOperator>(left)) {
      if (BinaryOperator* rightBO = dyn_cast<BinaryOperator>(right))
        return cmpBinaryOperator(leftBO, rightBO);
      else
        if (isa<CmpInst>(right)) {
          return false;
        } else {
          return true;
        }
    } else if (CmpInst* leftCmp = dyn_cast<CmpInst>(left)) {
      if (CmpInst* rightCmp = dyn_cast<CmpInst>(right))
        return cmpComparison(leftCmp, rightCmp);
      else
        return true;
    } else {
      if (isa<BinaryOperator>(right) || isa<CmpInst>(right))
        return false;
      else
        return left < right;
    }
  }
  
  bool cmpBinaryOperator(BinaryOperator* left, BinaryOperator* right) {
    if (left->getOpcode() != right->getOpcode())
      return left->getOpcode() < right->getOpcode();
    else if ((*this)(left->getOperand(0), right->getOperand(0)))
      return true;
    else if ((*this)(right->getOperand(0), left->getOperand(0)))
      return false;
    else
      return (*this)(left->getOperand(1), right->getOperand(1));
  }
  
  bool cmpComparison(CmpInst* left, CmpInst* right) {
    if (left->getOpcode() != right->getOpcode())
      return left->getOpcode() < right->getOpcode();
    else if (left->getPredicate() != right->getPredicate())
      return left->getPredicate() < right->getPredicate();
    else if ((*this)(left->getOperand(0), right->getOperand(0)))
      return true;
    else if ((*this)(right->getOperand(0), left->getOperand(0)))
      return false;
    else
      return (*this)(left->getOperand(1), right->getOperand(1));
  }
};

namespace {

  class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
    bool runOnFunction(Function &F);
  public:
    static char ID; // Pass identification, replacement for typeid
    GVNPRE() : FunctionPass((intptr_t)&ID) { nextValueNumber = 1; }

  private:
    uint32_t nextValueNumber;
    typedef std::map<Value*, uint32_t, ExprLT> ValueTable;
    ValueTable VN;
    std::set<Value*, ExprLT> MS;
    std::vector<Instruction*> createdExpressions;
    
    std::map<BasicBlock*, std::set<Value*, ExprLT> > availableOut;
    std::map<BasicBlock*, std::set<Value*, ExprLT> > anticipatedIn;
    
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesCFG();
      AU.addRequired<DominatorTree>();
      AU.addRequired<PostDominatorTree>();
    }
  
    // Helper fuctions
    // FIXME: eliminate or document these better
    void dump(const std::set<Value*>& s) const;
    void dump_unique(const std::set<Value*, ExprLT>& s) const;
    void clean(std::set<Value*, ExprLT>& set);
    bool add(Value* V, uint32_t number);
    Value* find_leader(std::set<Value*, ExprLT>& vals,
                       Value