TDDataStructures

// TDDataStructures
//  - Analysis that computes new data structure graphs for each function using the closed graphs for the callers computed by the bottom-up pass.

class TDDataStructures : public DataStructures {
  svset<const Function*> ExternallyCallable;

  /// CallerCallEdges - For a particular graph, we keep a list of these records
  /// which indicates which graphs call this function and from where.
  struct CallerCallEdge {
    DSGraph *CallerGraph;        // The graph of the caller function.
    const DSCallSite *CS;        // The actual call site.
    const Function *CalledFunction;    // The actual function being called.

    CallerCallEdge(DSGraph *G, const DSCallSite *cs, const Function *CF)
      : CallerGraph(G), CS(cs), CalledFunction(CF) {}

    bool operator<(const CallerCallEdge &RHS) const {
      return CallerGraph < RHS.CallerGraph ||
            (CallerGraph == RHS.CallerGraph && CS < RHS.CS);
    }
  };

  std::map<DSGraph*, std::vector<CallerCallEdge> > CallerEdges;


  // IndCallMap - We memoize the results of indirect call inlining operations that have multiple targets here to avoid N*M inlining.  The key to the map is a sorted set of callee functions, the value is the DSGraph that holds all of the caller graphs merged together, and the DSCallSite to merge with the arguments for each function.

  std::map<std::vector<const Function*>, DSGraph*> IndCallMap;

  bool useEQBU;

public:
  static char ID;
  TDDataStructures(char & CID = ID, const char* printname = "td.", bool useEQ = false)
    : DataStructures(CID, printname), useEQBU(useEQ) {}
  ~TDDataStructures();

  virtual bool runOnModule(Module &M);

  /// getAnalysisUsage - This obviously provides a data structure graph.

  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
    if (useEQBU) {
      AU.addRequired<EquivBUDataStructures>();
    } else {
      AU.addRequired<BUDataStructures>();
      AU.addPreserved<BUDataStructures>();
    }
    AU.setPreservesAll();
  }

private:
  void markReachableFunctionsExternallyAccessible(DSNode *N,
                                                  DenseSet<DSNode*> &Visited);

  void InlineCallersIntoGraph(DSGraph* G);
  void ComputePostOrder(const Function &F, DenseSet<DSGraph*> &Visited,
                        std::vector<DSGraph*> &PostOrder);
};