poolalloc/lib/Macroscopic/StructureFieldVisitor.h

//===-- StructureFieldVisitor.h - Macroscopic DS inspector ------*- C++ -*-===//
// 
//                     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 defines the public interface to the LatticeValue and
// StructureFieldVisitor classes.
//
//===----------------------------------------------------------------------===//

#ifndef MACROSCOPIC_STRUCTUREFIELDVISITOR_H
#define MACROSCOPIC_STRUCTUREFIELDVISITOR_H

#include <set>
#include <map>
#include <vector>

namespace llvm {
  class Type;
  class Constant;
  class Instruction;
  class LoadInst;
  class CallInst;
  class StoreInst;
  class EquivClassGraphs;
  class DSNode;
  class DSGraph;

namespace Macroscopic {

/// FindAllDataStructures - Inspect the program specified by ECG, adding to
/// 'Nodes' all of the data structures node in the program that contain the
/// "IncludeFlags" and do not contain "ExcludeFlags" node flags.  If
/// OnlyHomogenous is true, only type-homogenous nodes are considered.
void FindAllDataStructures(std::set<DSNode*> &Nodes, unsigned IncludeFlags,
                           unsigned ExcludeFlags, bool OnlyHomogenous,
                           EquivClassGraphs &ECG);

//===----------------------------------------------------------------------===//
/// Visit types - This describes an enum specifying which methods are
/// overloaded in the concrete implementation of the LatticeValue class.
namespace Visit {
  enum {
    Loads = 1,
    Stores = 2,
    Allocs = 4,
    Deallocs = 8,
    // ...
  };
}

//===----------------------------------------------------------------------===//
/// LatticeValue - Describe.
///
class LatticeValue {
  DSNode *Node;
  std::vector<unsigned> Idxs;  // The index path to get to this field.
  const Type *FieldTy;         // The type of this field.
public:
  LatticeValue(DSNode *N, const std::vector<unsigned> &I,
               const Type *Ty) : Node(N), Idxs(I), FieldTy(Ty) {}
  virtual ~LatticeValue() {}

  DSNode *getNode() const { return Node; }
  DSGraph &getParentGraph() const;

  const std::vector<unsigned> &getIndices() const { return Idxs; }
  const Type *getFieldType() const { return FieldTy; }

  /// getFieldOffset - Get the byte offset of this field from the start of the
  /// node.
  ///
  unsigned getFieldOffset() const;

  /// dump - Print debugging information about this class.
  ///
  virtual void dump() const;

  /// mergeInValue - Merge the information from the RHS lattice value (which is
  /// guaranteed to be the same dynamic type as 'this') into this lattice value.
  /// If the resultant value hits bottom, return true.  This is used for
  /// interprocedural analysis.
  ///
  virtual bool mergeInValue(const LatticeValue *RHS) {
    return true;
  }
  
  //===--------------------------------------------------------------------===//
  // Visitation methods - These methods update the current lattice state
  // based on the information in the operation.  If the lattice value reaches
  // bottom, the method implementation should return true so that analysis
  // can be stopped as early as possible.  Visitation methods are grouped by
  // their Visitation class.

  // All lattice values must implement these.

  /// visitRecognizedCall - The node for this lattice value is passed into some
  /// external function that is "known" by the Local analysis pass (e.g. atoi).
  /// By default, this stops any analysis of the node.
  ///
  virtual bool visitRecognizedCall(Instruction &I) {
    return true;
  }
  
  // Load Vistation methods.
  virtual bool visitLoad(LoadInst &);

  // Store Visitation methods.
  virtual bool visitStore(StoreInst &);
  virtual bool visitGlobalInit(Constant *InitVal);
  virtual bool visitMemSet(CallInst &I) {
    return visitRecognizedCall((Instruction&)I);
  }
};

//===----------------------------------------------------------------------===//
/// CombinedLatticeValue - Describe.
///
template<typename L1, typename L2>
class CombinedLatticeValue : public LatticeValue {
  L1 LV1; L2 LV2;
  bool LV1Bottom, LV2Bottom;
public:
  CombinedLatticeValue(DSNode *Node, const std::vector<unsigned> &Idxs,
                       const Type *FieldTy)
    : LatticeValue(Node, Idxs, FieldTy), LV1(Node, Idxs, FieldTy),
      LV2(Node, Idxs, FieldTy), LV1Bottom(false), LV2Bottom(false) {}
      
  static unsigned getInterestingEvents() {
    return L1::getInterestingEvents() | L2::getInterestingEvents();
  }

  static CombinedLatticeValue *create(DSNode *Node,
                                      const std::vector<unsigned> &Idxs,
                                      const Type *FieldTy) {
    return new CombinedLatticeValue(Node, Idxs, FieldTy);      
  }

  void dump() const {
    if (!LV1Bottom) LV1.dump();
    if (!LV2Bottom) LV2.dump();
  }

  virtual bool mergeInValue(const LatticeValue *RHSLV) {
    const CombinedLatticeValue *RHS =
      static_cast<const CombinedLatticeValue *>(RHSLV);
    LV1Bottom |= RHS->LV1Bottom;
    LV2Bottom |= RHS->LV2Bottom;
    if (!LV1Bottom) LV1Bottom = LV1.mergeInValue(&RHS->LV1);
    if (!LV2Bottom) LV2Bottom = LV2.mergeInValue(&RHS->LV2);
    return LV1Bottom & LV2Bottom;
  }
  
  virtual bool visitRecognizedCall(Instruction &I) {
    if (!LV1Bottom) LV1Bottom = LV1.visitRecognizedCall(I);
    if (!LV2Bottom) LV2Bottom = LV2.visitRecognizedCall(I);
    return LV1Bottom & LV2Bottom;
  }
  
  // Load Vistation methods.
  virtual bool visitLoad(LoadInst &LI) {
    if (!LV1Bottom && (L1::getInterestingEvents() & Visit::Loads))
      LV1Bottom = LV1.visitLoad(LI);
    if (!LV2Bottom && (L2::getInterestingEvents() & Visit::Loads))
      LV2Bottom = LV2.visitLoad(LI);
    return LV1Bottom & LV2Bottom;
  }

  // Store Visitation methods.
  virtual bool visitStore(StoreInst &SI) {
    if (!LV1Bottom && (L1::getInterestingEvents() & Visit::Stores))
      LV1Bottom = LV1.visitStore(SI);
    if (!LV2Bottom && (L2::getInterestingEvents() & Visit::Stores))
      LV2Bottom = LV2.visitStore(SI);
    return LV1Bottom & LV2Bottom;
  }

  virtual bool visitGlobalInit(Constant *InitVal) {
    if (!LV1Bottom && (L1::getInterestingEvents() & Visit::Stores))
      LV1Bottom = LV1.visitGlobalInit(InitVal);
    if (!LV2Bottom && (L2::getInterestingEvents() & Visit::Stores))
      LV2Bottom = LV2.visitGlobalInit(InitVal);
    return LV1Bottom & LV2Bottom;
  }

  virtual bool visitMemSet(CallInst &I) {
    if (!LV1Bottom && (L1::getInterestingEvents() & Visit::Stores))
      LV1Bottom = LV1.visitMemSet(I);
    if (!LV2Bottom && (L2::getInterestingEvents() & Visit::Stores))
      LV2Bottom = LV2.visitMemSet(I);
    return LV1Bottom & LV2Bottom;
  }
};


//===----------------------------------------------------------------------===//
/// StructureFieldVisitorBase - This implements all of the heavy lifting
/// for the StructureFieldVisitor class.  This class should not be used
/// directly, see it (below) for usage.
///
class StructureFieldVisitorBase {
  unsigned Callbacks;     // Bitfield containing bits from Macroscopic::Visit
  EquivClassGraphs &ECG;
  
  std::map<DSGraph*, std::multimap<DSNode*,LatticeValue*> > CalleeFnFacts;

  // createLatticeValue - Provide a virtual ctor for the concrete lattice value.
  virtual LatticeValue* createLatticeValue(DSNode *Node,
                                           const std::vector<unsigned> &Idxs,
                                           const Type *FieldTy) = 0;
protected:
  // Only allow this to be subclassed.
  StructureFieldVisitorBase(unsigned CB, EquivClassGraphs &ecg)
    : Callbacks(CB), ECG(ecg) {}
  virtual ~StructureFieldVisitorBase() {}
  
  
  std::set<LatticeValue*> visitNodes(const std::set<DSNode*> &Nodes);
  void visitFields(std::set<LatticeValue*> &Fields);

private:
  void visitGraph(DSGraph &DSG, std::multimap<DSNode*, LatticeValue*> &NodeLVs);
  std::multimap<DSNode*, LatticeValue*> &getCalleeFacts(DSGraph &DSG);

  void AddLatticeValuesForFields(DSNode *N, const Type *Ty,
                                 const std::vector<unsigned> &Idxs,
                                 std::set<LatticeValue*> &Values);
  void AddLatticeValuesForNode(DSNode *N, std::set<LatticeValue*> &Values);
  void ProcessNodesReachableFromGlobals(DSGraph &DSG,
                             std::multimap<DSNode*,LatticeValue*> &NodeLVs);

};



//===----------------------------------------------------------------------===//
/// FIXME: Describe
template<typename ConcLatticeVal>
class StructureFieldVisitor : public StructureFieldVisitorBase {
public:
  // FIXME: We really want to be able to infer which methods LatticeVal
  // overloads from the base class using template metaprogramming techniques.
  StructureFieldVisitor(EquivClassGraphs &ECG)
    : StructureFieldVisitorBase(ConcLatticeVal::getInterestingEvents(), ECG) {}

  /// visit - Visit the specified set of data structure nodes, recursively
  /// visiting all accesses to structure fields defined in those nodes.  This
  /// method returns a set of lattice values that have not reached bottom.
  std::set<ConcLatticeVal*> visit(const std::set<DSNode*> &Nodes) {
    std::set<LatticeValue*> ResultVals = visitNodes(Nodes);

    // Convert the result set to the appropriate lattice type.
    std::set<ConcLatticeVal*> Result;
    while (!ResultVals.empty()) {
      Result.insert(static_cast<ConcLatticeVal*>(*ResultVals.begin()));
      ResultVals.erase(ResultVals.begin());
    }
    return Result;
  }


private:  // Virtual method implementations for the base class.
  virtual LatticeValue* createLatticeValue(DSNode *N,
                                           const std::vector<unsigned> &Idxs,
                                           const Type *FieldTy) {
    return ConcLatticeVal::create(N, Idxs, FieldTy);
  }
};

}  // End Macroscopic namespace
}  // End llvm namespace

#endif