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/DenseMap.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;

//===----------------------------------------------------------------------===//
//                         ValueTable Class
//===----------------------------------------------------------------------===//

/// This class holds the mapping between values and value numbers.

namespace {
  class VISIBILITY_HIDDEN ValueTable {
    public:
      struct Expression {
        enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 
                              FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 
                              ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 
                              ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 
                              FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 
                              FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 
                              FCMPULT, FCMPULE, FCMPUNE };
    
        ExpressionOpcode opcode;
        uint32_t leftVN;
        uint32_t rightVN;
      
        bool operator< (const Expression& other) const {
          if (opcode < other.opcode)
            return true;
          else if (opcode > other.opcode)
            return false;
          else if (leftVN < other.leftVN)
            return true;
          else if (leftVN > other.leftVN)
            return false;
          else if (rightVN < other.rightVN)
            return true;
          else if (rightVN > other.rightVN)
            return false;
          else
            return false;
        }
      };
    
    private:
      DenseMap<Value*, uint32_t> valueNumbering;
      std::map<Expression, uint32_t> expressionNumbering;
  
      std::set<Expression> maximalExpressions;
      std::set<Value*> maximalValues;
  
      uint32_t nextValueNumber;
    
      Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
      Expression::ExpressionOpcode getOpcode(CmpInst* C);
    public:
      ValueTable() { nextValueNumber = 1; }
      uint32_t lookup_or_add(Value* V);
      uint32_t lookup(Value* V);
      void add(Value* V, uint32_t num);
      void clear();
      std::set<Expression>& getMaximalExpressions() {
        return maximalExpressions;
      
      }
      std::set<Value*>& getMaximalValues