SparsePropagation.h

//===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements an abstract sparse conditional propagation algorithm,
// modeled after SCCP, but with a customizable lattice function.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_SPARSE_PROPAGATION_H
#define LLVM_ANALYSIS_SPARSE_PROPAGATION_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include <vector>
#include <set>

namespace llvm {
  class Value;
  class Constant;
  class Argument;
  class Instruction;
  class PHINode;
  class TerminatorInst;
  class BasicBlock;
  class Function;
  class SparseSolver;
  class raw_ostream;

  template<typename T> class SmallVectorImpl;
  
class AbstractLatticeFunction {
public:
  typedef void *LatticeVal;
private:
  LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
public:
  AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
                          LatticeVal untrackedVal) {
    UndefVal = undefVal;
    OverdefinedVal = overdefinedVal;
    UntrackedVal = untrackedVal;
  }
  virtual ~AbstractLatticeFunction();
  
  LatticeVal getUndefVal()       const { return UndefVal; }
  LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
  LatticeVal getUntrackedVal()   const { return UntrackedVal; }
  
  virtual bool IsUntrackedValue(Value *V) {
    return false;
  }
  
  virtual LatticeVal ComputeConstant(Constant *C) {
    return getOverdefinedVal(); // always safe
  }

  virtual bool IsSpecialCasedPHI(PHINode *PN) {
    return false;
  }
  
  virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) {
    return 0;
  }

  virtual LatticeVal ComputeArgument(Argument *I) {
    return getOverdefinedVal(); // always safe
  }
  
  virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
    return getOverdefinedVal(); // always safe, never useful.
  }
  
  virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) {
    return getOverdefinedVal(); // always safe, never useful.
  }
  
  virtual void PrintValue(LatticeVal V, raw_ostream &OS);
};

  
class SparseSolver {
  typedef AbstractLatticeFunction::LatticeVal LatticeVal;
  
  AbstractLatticeFunction *LatticeFunc;
  
  DenseMap<Value*, LatticeVal> ValueState;  // The state each value is in.
  SmallPtrSet<BasicBlock*, 16> BBExecutable;   // The bbs that are executable.
  
  std::vector<Instruction*> InstWorkList;   // Worklist of insts to process.
  
  std::vector<BasicBlock*> BBWorkList;  // The BasicBlock work list
  
  typedef std::pair<BasicBlock*,BasicBlock*> Edge;
  std::set<Edge> KnownFeasibleEdges;
  
  SparseSolver(const SparseSolver&);    // DO NOT IMPLEMENT
  void operator=(const SparseSolver&);  // DO NOT IMPLEMENT
public:
  explicit SparseSolver(AbstractLatticeFunction *Lattice)
    : LatticeFunc(Lattice) {}
  ~SparseSolver() {
    delete LatticeFunc;
  }
  
  void Solve(Function &F);
  
  void Print(Function &F, raw_ostream &OS) const;

  LatticeVal getLatticeState(Value *V) const {
    DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
    return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
  }
  
  LatticeVal getOrInitValueState(Value *V);
  
  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To,
                      bool AggressiveUndef = false);

  bool isBlockExecutable(BasicBlock *BB) const {
    return BBExecutable.count(BB);
  }
  
private:
  void UpdateState(Instruction &Inst, LatticeVal V);
  
  void MarkBlockExecutable(BasicBlock *BB);
  
  void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
  
  void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs,
                             bool AggressiveUndef);
  
  void visitInst(Instruction &I);
  void visitPHINode(PHINode &I);
  void visitTerminatorInst(TerminatorInst &TI);

};

} // end namespace llvm

#endif // LLVM_ANALYSIS_SPARSE_PROPAGATION_H

---