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/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.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;

STATISTIC(NumInstRemoved, "Number of instructions removed");
STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");

STATISTIC(IPNumInstRemoved, "Number ofinstructions removed by IPSCCP");
STATISTIC(IPNumDeadBlocks , "Number of basic blocks unreachable by IPSCCP");
STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");

namespace {
/// LatticeVal class - This class represents the different lattice values that
/// an LLVM value may occupy.  It is a simple class with value semantics.
///
class LatticeVal {
  enum {
    /// undefined - This LLVM Value has no known value yet.
    undefined,
    
    /// constant - This LLVM Value has a specific constant value.
    constant,

    /// forcedconstant - This LLVM Value was thought to be undef until
    /// ResolvedUndefsIn.  This is treated just like 'constant', but if merged
    /// with another (different) constant, it goes to overdefined, instead of
    /// asserting.
    forcedconstant,
    
    /// overdefined - This instruction is not known to be constant, and we know
    /// it has a value.
    overdefined
  } 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) {
      if (LatticeValue == undefined) {
        LatticeValue = constant;
        ConstantVal = V;
      } else {
        assert(LatticeValue == forcedconstant && 
               "Cannot move from overdefined to constant!");
        // Stay at forcedconstant if the constant is the same.
        if (V == ConstantVal) return false;
        
        // Otherwise, we go to overdefined.  Assumptions made based on the
        // forced value are possibly wrong.  Assuming this is another constant
        // could expose a contradiction.
        LatticeValue = overdefined;
      }
      return true;
    } else {
      assert(ConstantVal == V && "Marking constant with different value");
    }
    return false;
  }

  inline void markForcedConstant(Constant *V) {
    assert(LatticeValue == undefined && "Can't force a defined value!");
    LatticeValue = forcedconstant;
    ConstantVal = V;
  }
  
  inline bool isUndefined() const { return LatticeValue == undefined; }
  inline bool isConstant() const {
    return LatticeValue == constant || LatticeValue == forcedconstant;
  }
  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...

  /// GlobalValue - If we are tracking any values for the contents of a global
  /// variable, we keep a mapping from the constant accessor to the element of
  /// the global, to the currently known value.  If the value becomes
  /// overdefined, it's entry is simply removed from this map.
  hash_map<GlobalVariable*, LatticeVal> TrackedGlobals;

  /// 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) {
    DOUT << "Marking Block Executable: " << BB->getName() << "\n";
    BBExecutable.insert(BB);   // Basic block is executable!
    BBWorkList.push_back(BB);  // Add the block to the work list!
  }

  /// TrackValueOfGlobalVariable - 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 TrackValueOfGlobalVariable(GlobalVariable *GV) {
    const Type *ElTy = GV->getType()->getElementType();
    if (ElTy->isFirstClassType()) {
      LatticeVal &IV = TrackedGlobals[GV];
      if (!isa<UndefValue>(GV->getInitializer()))
        IV.markConstant(GV->getInitializer());
    }
  }

  /// 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];