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.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "sccp"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/IPO.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 "llvm/Support/CallSite.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/hash_map"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <set>
using namespace llvm;

// LatticeVal class - This class represents the different lattice values that an
// instruction may occupy.  It is a simple class with value semantics.
//
namespace {

class LatticeVal {
  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 LatticeVal() : 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


//===----------------------------------------------------------------------===//
//
/// SCCPSolver - This class is a general purpose solver for Sparse Conditional
/// Constant Propagation.
///
class SCCPSolver : public InstVisitor<SCCPSolver> {
  std::set<BasicBlock*>     BBExecutable;// The basic blocks that are executable
  hash_map<Value*, LatticeVal> ValueState;  // The state each value is in...

  /// TrackedFunctionRetVals - If we are tracking arguments into and the return
  /// value out of a function, it will have an entry in this map, indicating
  /// what the known return value for the function is.
  hash_map<Function*, LatticeVal> TrackedFunctionRetVals;

  // 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<Value*> OverdefinedInstWorkList;
  std::vector<Value*> InstWorkList;


  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:

  /// MarkBlockExecutable - This method can be used by clients to mark all of
  /// the blocks that are known to be intrinsically live in the processed unit.
  void MarkBlockExecutable(BasicBlock *BB) {
    DEBUG(std::cerr << "Marking Block Executable: " << BB->getName() << "\n");
    BBExecutable.insert(BB);   // Basic block is executable!
    BBWorkList.push_back(BB);  // Add the block to the work list!
  }

  /// TrackValueOfGlobalVariableIfPossible - Clients can use this method to
  /// inform the SCCPSolver that it should track loads and stores to the
  /// specified global variable if it can.  This is only legal to call if
  /// performing Interprocedural SCCP.
  void TrackValueOfGlobalVariableIfPossible(GlobalVariable *GV);

  /// AddTrackedFunction - If the SCCP solver is supposed to track calls into
  /// and out of the specified function (which cannot have its address taken),
  /// this method must be called.
  void AddTrackedFunction(Function *F) {
    assert(F->hasInternalLinkage() && "Can only track internal functions!");
    // Add an entry, F -> undef.
    TrackedFunctionRetVals[F];
  }

  /// Solve - Solve for constants and executable blocks.
  ///
  void Solve();

  /// ResolveBranchesIn - While solving the dataflow for a function, we assume
  /// that branches on undef values cannot reach any of their successors.
  /// However, this is not a safe assumption.  After we solve dataflow, this
  /// method should be use to handle this.  If this returns true, the solver
  /// should be rerun.
  bool ResolveBranchesIn(Function &F);

  /// getExecutableBlocks - Once we have solved for constants, return the set of
  /// blocks that is known to be executable.
  std::set<BasicBlock*> &getExecutableBlocks() {
    return BBExecutable;
  }

  /// getValueMapping - Once we have solved for constants, return the mapping of
  /// LLVM values to LatticeVals.
  hash_map<Value*, LatticeVal> &getValueMapping() {
    return ValueState;
  }

private:
  // 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(LatticeVal &IV, Value *V, Constant *C) {
    if (IV.markConstant(C)) {
      DEBUG(std::cerr << "markConstant: " << *C << ": " << *V);
      InstWorkList.push_back(V);
    }
  }
  inline void markConstant(Value *V, Constant *C) {
    markConstant(ValueState[V], V, 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(LatticeVal &IV, Value *V) {
    if (IV.markOverdefined()) {
      DEBUG(std::cerr << "markOverdefined: " << *V);
      // Only instructions go on the work list
      OverdefinedInstWorkList.push_back(V);
    }
  }