HomePhabricator

[DDG] DirectedGraph as a base class for various dependence graphs such as DDG…

Authored by Whitney on Jul 25 2019, 11:23 AM.

Description

[DDG] DirectedGraph as a base class for various dependence graphs such as DDG and PDG. Summary: This is an implementation of a directed graph base class with explicit representation of both nodes and edges. This implementation makes the edges explicit because we expect to assign various attributes (such as dependence type, distribution interference weight, etc) to the edges in the derived classes such as DDG and DIG. The DirectedGraph consists of a list of DGNode's. Each node consists of a (possibly empty) list of outgoing edges to other nodes in the graph. A DGEdge contains a reference to a single target node. Note that nodes do not know about their incoming edges so the DirectedGraph class provides a function to find all incoming edges to a given node.

This is the first patch in a series of patches that we are planning to
contribute upstream in order to implement Data Dependence Graph and
Program Dependence Graph.

More information about the proposed design can be found here:
https://ibm.ent.box.com/v/directed-graph-and-ddg
Authored By: bmahjour
Reviewer: Meinersbur, myhsum hfinkel, fhahn, jdoerfert, kbarton
Reviewed By: Meinersbur
Subscribers: mgorny, wuzish, jsji, lebedev.ri, dexonsmith, kristina,
llvm-commits, Whitney, etiotto
Tag: LLVM
Differential Revision: https://reviews.llvm.org/D64088

llvm-svn: 367043