HomePhabricator

[DDG] Data Dependence Graph - Pi Block

Authored by bmahjour on Nov 8 2019, 12:05 PM.

Description

[DDG] Data Dependence Graph - Pi Block

Summary:
This patch adds Pi Blocks to the DDG. A pi-block represents a group of DDG
nodes that are part of a strongly-connected component of the graph.
Replacing all the SCCs with pi-blocks results in an acyclic representation
of the DDG. For example if we have:
   {a -> b}, {b -> c, d}, {c -> a}
the cycle a -> b -> c -> a is abstracted into a pi-block "p" as follows:
   {p -> d} with "p" containing: {a -> b}, {b -> c}, {c -> a}
In this implementation the edges between nodes that are part of the pi-block
are preserved. The crossing edges (edges where one end of the edge is in the
set of nodes belonging to an SCC and the other end is outside that set) are
replaced with corresponding edges to/from the pi-block node instead.

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/D68827

Details

Committed
bmahjourNov 8 2019, 12:46 PM
Differential Revision
D68827: [DDG] Data Dependence Graph - Pi Block
Parents
rG5df3a87224ef: [AArch64][X86] Don't assume __powidf2 is available on Windows.
Branches
Unknown
Tags
Unknown