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

//===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
// 
//                     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 sparse conditional constant propagation and merging:
//
// Specifically, this:
//   * Assumes values are constant unless proven otherwise
//   * Assumes BasicBlocks are dead unless proven otherwise
//   * Proves values to be constant, and replaces them with constants
//   * Proves conditional branches to be unconditional
//
// Notice that:
//   * This pass has a habit of making definitions be dead.  It is a good idea
//     to to run a DCE pass sometime after running this pass.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Type.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Transforms/Utils/Local.h"
#include "Support/Debug.h"
#include "Support/hash_map"
#include "Support/Statistic.h"
#include "Support/STLExtras.h"
#include <algorithm>
#include <set>
using namespace llvm;

// InstVal class - This class represents the different lattice values that an 
// instruction may occupy.  It is a simple class with value semantics.
//
namespace {
  Statistic<> NumInstRemoved("sccp", "Number of instructions removed");

class InstVal {
  enum { 
    undefined,           // This instruction has no known value
    constant,            // This instruction has a constant value
    overdefined          // This instruction has an unknown value
  } LatticeValue;        // The current lattice position
  Constant *ConstantVal; // If Constant value, the current value
public:
  inline InstVal() : LatticeValue(undefined), ConstantVal(0) {}

  // markOverdefined - Return true if this is a new status to be in...
  inline bool markOverdefined() {
    if (LatticeValue != overdefined) {
      LatticeValue = overdefined;
      return true;
    }
    return false;
  }

  // markConstant - Return true if this is a new status for us...
  inline bool markConstant(Constant *V) {
    if (LatticeValue != constant) {
      LatticeValue = constant;
      ConstantVal = V;
      return true;
    } else {
      assert(ConstantVal == V && "Marking constant with different value");
    }
    return false;
  }

  inline bool isUndefined()   const { return LatticeValue == undefined; }
  inline bool isConstant()    const { return LatticeValue == constant; }
  inline bool isOverdefined() const { return LatticeValue == overdefined; }

  inline Constant *getConstant() const {
    assert(isConstant() && "Cannot get the constant of a non-constant!");
    return ConstantVal;
  }
};

} // end anonymous namespace


//===----------------------------------------------------------------------===//
// SCCP Class
//
// This class does all of the work of Sparse Conditional Constant Propagation.
//
namespace {
class SCCP : public FunctionPass, public InstVisitor<SCCP> {
  std::set<BasicBlock*>     BBExecutable;// The basic blocks that are executable
  hash_map<Value*, InstVal> ValueState;  // The state each value is in...

  // The reason for two worklists is that overdefined is the lowest state
  // on the lattice, and moving things to overdefined as fast as possible
  // makes SCCP converge much faster.
  // By having a separate worklist, we accomplish this because everything
  // possibly overdefined will become overdefined at the soonest possible
  // point.
  std::vector<Instruction*> OverdefinedInstWorkList;// The overdefined 
                                                    // instruction work list
  std::vector<Instruction*> InstWorkList;// The instruction work list


  std::vector<BasicBlock*>  BBWorkList;  // The BasicBlock work list

  /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not
  /// overdefined, despite the fact that the PHI node is overdefined.
  std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs;

  /// KnownFeasibleEdges - Entries in this set are edges which have already had
  /// PHI nodes retriggered.
  typedef std::pair<BasicBlock*,BasicBlock*> Edge;
  std::set<Edge> KnownFeasibleEdges;
public:

  // runOnFunction - Run the Sparse Conditional Constant Propagation algorithm,
  // and return true if the function was modified.
  //
  bool runOnFunction(Function &F);

  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
    AU.setPreservesCFG();
  }


  //===--------------------------------------------------------------------===//
  // The implementation of this class
  //
private:
  friend class InstVisitor<SCCP>;        // Allow callbacks from visitor

  // markConstant - Make a value be marked as "constant".  If the value
  // is not already a constant, add it to the instruction work list so that 
  // the users of the instruction are updated later.
  //
  inline void markConstant(InstVal &IV, Instruction *I, Constant *C) {
    if (IV.markConstant(C)) {
      DEBUG(std::cerr << "markConstant: " << *C << ": " << *I);
      InstWorkList.push_back(I);
    }
  }
  inline void markConstant(Instruction *I, Constant *C) {
    markConstant(ValueState[I], I, C);
  }

  // markOverdefined - Make a value be marked as "overdefined". If the
  // value is not already overdefined, add it to the overdefined instruction 
  // work list so that the users of the instruction are updated later.
  
  inline void markOverdefined(InstVal &IV, Instruction *I) {
    if (IV.markOverdefined()) {
      DEBUG(std::cerr << "markOverdefined: " << *I);
      OverdefinedInstWorkList.push_back(I);  // Only instructions go on the work list
    }
  }
  inline void markOverdefined(Instruction *I) {
    markOverdefined(ValueState[I], I);
  }

  // getValueState - Return the InstVal object that corresponds to the value.
  // This function is necessary because not all values should start out in the
  // underdefined state... Argument's should be overdefined, and
  // constants should be marked as constants.  If a value is not known to be an
  // Instruction object, then use this accessor to get its value from the map.
  //
  inline InstVal &getValueState(Value *V) {
    hash_map<Value*, InstVal>::iterator I = ValueState.find(V);
    if (I != ValueState.end()) return I->second;  // Common case, in the map
      
    if (