poolalloc/lib/PoolAllocate/EquivClassGraphs.h

//===-- EquivClassGraphs.h - Merge equiv-class graphs & inline bottom-up --===//
// 
//                     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 pass is the same as the complete bottom-up graphs, but
// with functions partitioned into equivalence classes and a single merged
// DS graph for all functions in an equivalence class.  After this merging,
// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph.
//
//===----------------------------------------------------------------------===//


#include "llvm/Analysis/DataStructure/DataStructure.h"
#include "llvm/Analysis/DataStructure/DSGraph.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/STLExtras.h"
#include <vector>
#include <map>
#include <ext/hash_map>

namespace llvm {

class Module;
class Function;

namespace PA {

  /// EquivClassGraphArgsInfo - Information about the set of argument nodes 
  /// in a DS graph (the number of argument nodes is the max of argument nodes
  /// for all functions folded into the graph).
  /// FIXME: This class is only used temporarily and could be eliminated.
  ///  
  struct EquivClassGraphArgsInfo {
    const DSGraph* ECGraph;
    std::vector<DSNodeHandle> argNodes;
    EquivClassGraphArgsInfo() : ECGraph(NULL) {}
  };

  /// EquivClassGraphs - This is the same as the complete bottom-up graphs, but
  /// with functions partitioned into equivalence classes and a single merged
  /// DS graph for all functions in an equivalence class.  After this merging,
  /// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph.
  ///
  struct EquivClassGraphs : public ModulePass {
    CompleteBUDataStructures *CBU;

    // FoldedGraphsMap, one graph for each function
    hash_map<const Function*, DSGraph*> FoldedGraphsMap;
  
    // Equivalence class where functions that can potentially be called via the
    // same function pointer are in the same class.
    EquivalenceClasses<Function*> FuncECs;

    // Each equivalence class graph contains several functions.
    // Remember their argument nodes (and return nodes?)
    std::map<const DSGraph*, EquivClassGraphArgsInfo> ECGraphInfo;
    
    /// OneCalledFunction - For each indirect call, we keep track of one
    /// target of the call.  This is used to find equivalence class called by
    /// a call site.
    std::map<DSNode*, Function *> OneCalledFunction;

  public:
    /// EquivClassGraphs - Computes the equivalence classes and then the
    /// folded DS graphs for each class.
    /// 
    virtual bool runOnModule(Module &M) { computeFoldedGraphs(M); return true; }

    /// getCBUDataStructures - Get the CompleteBUDataStructures object
    /// 
    CompleteBUDataStructures *getCBUDataStructures() { return CBU; }

    /// getDSGraph - Return the data structure graph for the specified function.
    /// This returns the folded graph.  The folded graph is the same as the CBU
    /// graph iff the function is in a singleton equivalence class AND all its 
    /// callees also have the same folded graph as the CBU graph.
    /// 
    DSGraph &getDSGraph(const Function &F) const {
      hash_map<const Function*, DSGraph*>::const_iterator I =
        FoldedGraphsMap.find(const_cast<Function*>(&F));
      assert(I != FoldedGraphsMap.end() && "No folded graph for function!");
      return *I->second;
    }

    /// getSomeCalleeForCallSite - Return any one callee function at
    /// a call site.
    /// 
    Function *getSomeCalleeForCallSite(const CallSite &CS) const;

    /// getDSGraphForCallSite - Return the common data structure graph for
    /// callees at the specified call site.
    /// 
    DSGraph &getDSGraphForCallSite(const CallSite &CS) const {
      return this->getDSGraph(*getSomeCalleeForCallSite(CS));
    }

    /// getEquivClassForCallSite - Get the set of functions in the equivalence
    /// class for a given call site.
    /// 
    const std::set<Function*>& getEquivClassForCallSite(const CallSite& CS) {
      Function* leaderF = FuncECs.findClass(getSomeCalleeForCallSite(CS));
      return FuncECs.getEqClass(leaderF);
    }

    /// getECGraphInfo - Get the graph info object with arg nodes info
    /// 
    EquivClassGraphArgsInfo &getECGraphInfo(const DSGraph* G) {
      assert(G != NULL && "getECGraphInfo: Null graph!");
      EquivClassGraphArgsInfo& GraphInfo = ECGraphInfo[G];
      if (GraphInfo.ECGraph == NULL)
        GraphInfo.ECGraph = G;
      return GraphInfo;
    }

    /// sameAsCBUGraph - Check if the folded graph for this function is
    /// the same as the CBU graph.
    bool sameAsCBUGraph(const Function &F) const {
      DSGraph& foldedGraph = getDSGraph(F);
      return (&foldedGraph == &CBU->getDSGraph(F));
    }

    DSGraph &getGlobalsGraph() const {
      return CBU->getGlobalsGraph();
    }
    
    typedef llvm::BUDataStructures::ActualCalleesTy ActualCalleesTy;
    const ActualCalleesTy &getActualCallees() const {
      return CBU->getActualCallees();
    }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesAll();
      AU.addRequired<CompleteBUDataStructures>();
    }

    /// print - Print out the analysis results...
    ///
    void print(std::ostream &O, const Module *M) const { CBU->print(O, M); }

  private:
    void computeFoldedGraphs(Module &M);

    void buildIndirectFunctionSets(Module &M);

    unsigned processSCC(DSGraph &FG, Function &F, std::vector<Function*> &Stack,
                        unsigned &NextID, 
                        hash_map<Function*, unsigned> &ValMap);

    void processGraph(DSGraph &FG, Function &F);

    DSGraph &getOrCreateGraph(Function &F);

    DSGraph* cloneGraph(Function &F);

    bool hasFoldedGraph(const Function& F) const {
      hash_map<const Function*, DSGraph*>::const_iterator I =
        FoldedGraphsMap.find(const_cast<Function*>(&F));
      return (I != FoldedGraphsMap.end());
    }

    DSGraph* getOrCreateLeaderGraph(const Function& leader) {
      DSGraph*& leaderGraph = FoldedGraphsMap[&leader];
      if (leaderGraph == NULL)
        leaderGraph = new DSGraph(CBU->getGlobalsGraph().getTargetData());
      return leaderGraph;
    }
  };

}; // end PA namespace

}; // end llvm namespace