HomePhabricator

[DDG] Data Dependence Graph - Root Node

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

Details

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