Page MenuHomePhabricator

[DDG] Data Dependence Graph - Topological Sort
ClosedPublic

Authored by bmahjour on Nov 22 2019, 11:00 AM.

Details

Summary

In this patch the DDG DAG is sorted topologically to put the nodes in the graph in the order that would satisfy all dependencies. This helps transformations that would like to generate code based on the DDG. Since the DDG is a DAG a reverse-post-order traversal would give us the topological ordering. This patch also sorts the basic blocks passed to the builder based on program order to ensure that the dependencies are computed in the correct direction.

Diff Detail

Event Timeline

bmahjour created this revision.Nov 22 2019, 11:00 AM
Meinersbur accepted this revision.Nov 22 2019, 2:20 PM
Meinersbur added inline comments.
llvm/test/Analysis/DDG/basic-b.ll
50

[design question] def-uses only manifest as flow-dependency, but no anti- or output dependencies. Looking only at the dependencies, a loop distribution pass could conclude that the computation of e.g. %arrayidx2 could be split from the load/store pi-node. However, this is not possible without storing the values in an intermediate array.

My question is how the loop distribution pass should handle the situation? Will anti- and output dependencies for registers added later? Does the pass have to check on its own that no def-use chain would be separated into different loops?

This revision is now accepted and ready to land.Nov 22 2019, 2:20 PM
bmahjour marked 2 inline comments as done.Nov 22 2019, 3:00 PM
bmahjour added inline comments.
llvm/test/Analysis/DDG/basic-b.ll
50

In general, loop distribution would have to consider def-use dependencies the same way it handles scalar dependencies, ie make sure that those edges do not get split. Some def-use dependencies can be ignored if they can be rematerialized (eg if they are just part of the loop structure).

This revision was automatically updated to reflect the committed changes.
bmahjour marked an inline comment as done.
bmahjour updated this revision to Diff 231270.Nov 27 2019, 8:40 AM

One of the sanitizer builds failed due to a memory leak issue. http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/14902
The reason for the leak is that when sorting I did not consider the nodes inside of the pi-block so they got removed from the DirectedGraph's list of nodes, and did not get freed when the DDG destructor got called.
I've updated the patch to fix the leak and reopened this revision for review.

bmahjour reopened this revision.Nov 27 2019, 8:41 AM
This revision is now accepted and ready to land.Nov 27 2019, 8:41 AM
Meinersbur added inline comments.Dec 2 2019, 9:14 AM
llvm/lib/Analysis/DependenceGraphBuilder.cpp
369

[suggestion] Consider adding a comment that pi-nodes are appended to the end of the node list (and why).

374

[serious] This will a emit warning "unused value" in non-assert builds.

376

[style] Use llvm::reverse

for (NodeType *N : reverse(NodesInPO))

[suggestion] Could you add a test case with a reduction (not necessarily in this patch), such as

double sum = 0;
for (int i = 0; i < n; i+=1)
  sum+=A[i];
return sum;

I am interested in what happens in self-recursive phi dependencies that are not induction variables. Note that GVN LoadPRE and LICM register promotion can create those as well. Another interesting case would be a nested reduction:

for (int j = 0; j < m; j+=1) {
  double sum = 0;
  for (int i = 0; i < n; i+=1)
    sum += A[i][j];
  B[j] = sum;
}

The motivation is that reductions usually are optimized differently than flow dependencies.

bmahjour marked 3 inline comments as done.Dec 2 2019, 11:24 AM

[suggestion] Could you add a test case with a reduction (not necessarily in this patch), such as

double sum = 0;
for (int i = 0; i < n; i+=1)
  sum+=A[i];
return sum;

I am interested in what happens in self-recursive phi dependencies that are not induction variables. Note that GVN LoadPRE and LICM register promotion can create those as well. Another interesting case would be a nested reduction:

for (int j = 0; j < m; j+=1) {
  double sum = 0;
  for (int i = 0; i < n; i+=1)
    sum += A[i][j];
  B[j] = sum;
}

The motivation is that reductions usually are optimized differently than flow dependencies.

I'm planning to add more tests later. I have two more patches that would cause reordering in the LIT tests so I'm waiting for us to get those in before adding more maintenance. I've noted the reduction case and will add that to the list of tests.

I'm planning to add more tests later. I have two more patches that would cause reordering in the LIT tests so I'm waiting for us to get those in before adding more maintenance. I've noted the reduction case and will add that to the list of tests.

Thanks

Meinersbur accepted this revision.Dec 2 2019, 11:38 AM

LGTM assuming this fixes the leak (and the unused value warning).

bmahjour updated this revision to Diff 231745.Dec 2 2019, 11:43 AM

Addressed Michael's comments.

This revision was automatically updated to reflect the committed changes.