HomePhabricator

[DDG] Data Dependence Graph - Root Node

Authored by bmahjour on Oct 1 2019, 12:32 PM.

Description

[DDG] Data Dependence Graph - Root Node

Summary:
This patch adds Root Node to the DDG. The purpose of the root node is to create a single entry node that allows graph walk iterators to iterate through all nodes of the graph, making sure that no node is left unvisited during a graph walk (eg. SCC or DFS). Once the DDG is fully constructed it will have exactly one root node. Every node in the graph is reachable from the root. The algorithm for connecting the root node is based on depth-first-search that keeps track of visited nodes to try to avoid creating unnecessary edges.

Authored By: bmahjour

Reviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfert

Reviewed By: Meinersbur

Subscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slack

Tag: #llvm

Differential Revision: https://reviews.llvm.org/D67970

llvm-svn: 373386

Details

Committed
bmahjourOct 1 2019, 12:32 PM
Reviewer
Meinersbur
Differential Revision
D67970: [DDG] Data Dependence Graph - Root Node
Parents
rGbcab95182b37: [libc++] Re-apply workaround for D63883
Branches
Unknown
Tags
Unknown