path: root/include/llvm/Analysis/DataStructure/DSGraph.h

//===- DSGraph.h - Represent a collection of data structures ----*- 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 header defines the data structure graph (DSGraph) and the
// ReachabilityCloner class.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DSGRAPH_H
#define LLVM_ANALYSIS_DSGRAPH_H

#include "llvm/Analysis/DataStructure/DSNode.h"
#include "llvm/ADT/hash_map"
#include "llvm/ADT/EquivalenceClasses.h"
#include <list>

namespace llvm {

class GlobalValue;

//===----------------------------------------------------------------------===//
/// DSScalarMap - An instance of this class is used to keep track of all of 
/// which DSNode each scalar in a function points to.  This is specialized to
/// keep track of globals with nodes in the function, and to keep track of the 
/// unique DSNodeHandle being used by the scalar map.
///
/// This class is crucial to the efficiency of DSA with some large SCC's.  In 
/// these cases, the cost of iterating over the scalar map dominates the cost
/// of DSA.  In all of these cases, the DSA phase is really trying to identify 
/// globals or unique node handles active in the function.
///
class DSScalarMap {
  typedef hash_map<Value*, DSNodeHandle> ValueMapTy;
  ValueMapTy ValueMap;

  typedef hash_set<GlobalValue*> GlobalSetTy;
  GlobalSetTy GlobalSet;

  EquivalenceClasses<GlobalValue*> &GlobalECs;
public:
  DSScalarMap(EquivalenceClasses<GlobalValue*> &ECs) : GlobalECs(ECs) {}

  EquivalenceClasses<GlobalValue*> &getGlobalECs() const { return GlobalECs; }

  // Compatibility methods: provide an interface compatible with a map of 
  // Value* to DSNodeHandle's.
  typedef ValueMapTy::const_iterator const_iterator;
  typedef ValueMapTy::iterator iterator;
  iterator begin() { return ValueMap.begin(); }
  iterator end()   { return ValueMap.end(); }
  const_iterator begin() const { return ValueMap.begin(); }
  const_iterator end() const { return ValueMap.end(); }

  GlobalValue *getLeaderForGlobal(GlobalValue *GV) const {
    EquivalenceClasses<GlobalValue*>::iterator ECI = GlobalECs.findValue(GV);
    if (ECI == GlobalECs.end()) return GV;
    return *GlobalECs.findLeader(ECI);
  }


  iterator find(Value *V) {
    iterator I = ValueMap.find(V);
    if (I != ValueMap.end()) return I;

    if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
      // If this is a global, check to see if it is equivalenced to something
      // in the map.
      GlobalValue *Leader = getLeaderForGlobal(GV);
      if (Leader != GV)
        I = ValueMap.find((Value*)Leader);
    }
    return I;
  }
  const_iterator find(Value *V) const {
    const_iterator I = ValueMap.find(V);
    if (I != ValueMap.end()) return I;

    if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
      // If this is a global, check to see if it is equivalenced to something
      // in the map.
      GlobalValue *Leader = getLeaderForGlobal(GV);
      if (Leader != GV)
        I = ValueMap.find((Value*)Leader);
    }
    return I;
  }

  /// getRawEntryRef - This method can be used by clients that are aware of the
  /// global value equivalence class in effect.
  DSNodeHandle &getRawEntryRef(Value *V) {
    std::pair<iterator,bool> IP =
      ValueMap.insert(std::make_pair(V, DSNodeHandle()));
     if (IP.second)   // Inserted the new entry into the map.
       if (GlobalValue *GV = dyn_cast<GlobalValue>(V))
         GlobalSet.insert(GV);
     return IP.first->second;
  }

  unsigned count(Value *V) const { return ValueMap.find(V) != ValueMap.end(); }

  void erase(Value *V) { erase(ValueMap.find(V)); }

  void eraseIfExists(Value *V) {
    iterator I = find(V);
    if (I != end()) erase(I);
  }

  /// replaceScalar - When an instruction needs to be modified, this method can
  /// be used to update the scalar map to remove the old and insert the new.
  ///
  void replaceScalar(Value *Old, Value *New) {
    iterator I = find(Old);
    assert(I != end() && "Old value is not in the map!");
    ValueMap.insert(std::make_pair(New, I->second));
    erase(I);
  }

  /// copyScalarIfExists - If Old exists in the scalar map, make New point to
  /// whatever Old did.
  void copyScalarIfExists(Value *Old, Value *New) {
    iterator I = find(Old);
    if (I != end())
      ValueMap.insert(std::make_pair(New, I->second));
  }

  /// operator[] - Return the DSNodeHandle for the specified value, creating a
  /// new null handle if there is no entry yet.
  DSNodeHandle &operator[](Value *V) {
    iterator I = ValueMap.find(V);
    if (I != ValueMap.end())
      return I->second;   // Return value if already exists.

    if (GlobalValue *GV = dyn_cast<GlobalValue>(V))
      return AddGlobal(GV);

    return ValueMap.insert(std::make_pair(V, DSNodeHandle())).first->second;
  }

  void erase(iterator I) { 
    assert(I != ValueMap.end() && "Cannot erase end!");
    if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first))
      GlobalSet.erase(GV);
    ValueMap.erase(I); 
  }

  void clear() {
    ValueMap.clear();
    GlobalSet.clear();
  }

  /// spliceFrom - Copy all entries from RHS, then clear RHS.
  ///
  void spliceFrom(DSScalarMap &RHS);

  // Access to the global set: the set of all globals currently in the
  // scalar map.
  typedef GlobalSetTy::const_iterator global_iterator;
  global_iterator global_begin() const { return GlobalSet.begin(); }
  global_iterator global_end() const { return GlobalSet.end(); }
  unsigned global_size() const { return GlobalSet.size(); }
  unsigned global_count(GlobalValue *GV) const { return GlobalSet.count(GV); }
private:
  DSNodeHandle &AddGlobal(GlobalValue *GV);
};


//===----------------------------------------------------------------------===//
/// DSGraph - The graph that represents a function.
///
class DSGraph {
public:
  // Public data-type declarations...
  typedef DSScalarMap ScalarMapTy;
  typedef hash_map<Function*, DSNodeHandle> ReturnNodesTy;
  typedef ilist<DSNode> NodeListTy;

  /// NodeMapTy - This data type is used when cloning one graph into another to
  /// keep track of the correspondence between the nodes in the old and new
  /// graphs.
  typedef hash_map<const DSNode*, DSNodeHandle> NodeMapTy;

  // InvNodeMapTy - This data type is used to represent the inverse of a node
  // map.
  typedef hash_multimap<DSNodeHandle, const DSNode*> InvNodeMapTy;
private:
  DSGraph *GlobalsGraph;   // Pointer to the common graph of global objects
  bool PrintAuxCalls;      // Should this graph print the Aux calls vector?

  NodeListTy Nodes;
  ScalarMapTy ScalarMap;

  // ReturnNodes - A return value for every function merged into this graph.
  // Each DSGraph may have multiple functions merged into it at any time, which
  // is used for representing SCCs.
  //
  ReturnNodesTy ReturnNodes;

  // FunctionCalls - This list maintains a single entry for each call
  // instruction in the current graph.  The first entry in the vector is the
  // scalar that holds the return value for the call, the second is the function
  // scalar being invoked, and the rest are pointer arguments to the function.
  // This vector is built by the Local graph and is never modified after that.
  //
  std