HomePhabricator

[DDG] Data Dependence Graph - Graph Simplification

Authored by bmahjour on Feb 18 2020, 1:38 PM.

Description

[DDG] Data Dependence Graph - Graph Simplification

Summary:
This is the last functional patch affecting the representation of DDG.
Here we try to simplify the DDG to reduce the number of nodes and edges by
iteratively merging pairs of nodes that satisfy the following conditions,
until no such pair can be identified. A pair of nodes consisting of a and b
can be merged if:

  1. the only edge from a is a def-use edge to b and
  2. the only edge to b is a def-use edge from a and
  3. there is no cyclic edge from b to a and
  4. all instructions in a and b belong to the same basic block and
  5. both a and b are simple (single or multi instruction) nodes.

These criteria allow us to fold many uninteresting def-use edges that
commonly exist in the graph while avoiding the risk of introducing
dependencies that didn't exist before.

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

Tags: #llvm

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

Details

Committed
bmahjourFeb 19 2020, 10:41 AM
Reviewer
Meinersbur
Differential Revision
D72350: [DDG] Data Dependence Graph - Graph Simplification
Parents
rGfd0e8b4c0ca7: [mlir][NFC] Fix warning for mismatched sign comparison.
Branches
Unknown
Tags
Unknown