ping

@Meinersbur this update should address your concern regarding time complexity. I've also tried to limit the additional memory usage by only keeping track of incoming edge counts for nodes that are targets of candidate source nodes.

ping

Address review comments.

In D70986#1790336, @Meinersbur wrote:

In D70986#1790305, @bmahjour wrote:

The order is at the mercy of SCCIterator. For example if you look at the first pi-block node in basic-a.ll, you'll notice that prior to this change the %inc = add i64 %i.02, 1 was placed ahead of %i.02 = phi .

I see. Could you add that as a comment to either computeInstructionOrdinals and/or the invocation of llvm::sort.

In D71492#1784331, @Meinersbur wrote:

[suggestion] The scope of the lcssa PHI node and the definition of its value are in different loops, hence calling getSCEVAtScope at the lcssa's scope may simplify the expression. This might even be mandatory since SCEV should be canonical.

If by "lcssa`s scope" you mean the scope at which the lcssa phi instruction appears, then it's not going to help in this case. The scope is the function (outside of any loop). If you pass nullptr to getSCEVAtScope it continues to produce SCEVUnknown.

[serious] createAddRecFromPHI might be directly called be called getSCEV such that %indvars.iv.next isn't in the cache yet. Therefore the result changes depending on the order in which getSCEV is called.

Yes, I was originally concerned that calling getSCEV could cause an infinite loop for cyclic phis, but I gave it more thought and I couldn't come up with a valid IR that can cause the infinite loop. I've changed it to use getSCEV and documented my reasoning for why I don't think a cycle is possible.

Address Michael's comments.

What would cause the order of nodes in a pi-node to change? As it's not topologically sorted, wouldn't the order stay the order in which they were added to NodeList?

ping

Thank you @dmgreen and @fhahn for the quick review.

Addressed review comments.

Check the complete da print output in the LIT test as per Florian's comment.

In D70986#1771141, @Meinersbur wrote:

I do not understand why the ordinals are necessary. For deterministic behavior, the deterministic iteration order over blocks and instructions should already ensure that (unless you are iterating over DenseMaps, which does not seem the case and is easily fixed). If for correctness, do you have an illustrative example when this would be critical?

The deleteDeadLoop function when called on the outer loop will effectively remove the subloops from the CFG too (make them unreachable). Maybe we should change deleteDeadLoop to also take the subloops into account when updating the analysis passed to it. Then we shouldn't need a separate function to delete loop nests.

Addressed Michael's comments.

In D70609#1765480, @Meinersbur wrote:

[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.

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.

LGTM.

In D68789#1753777, @Meinersbur wrote:

[suggestion] Add a methods that returns/fills a vector with all the Loop*s that are part of the perfect loop nest.

Changed the enum array to use "Last" instead of "Count"

Created EnumeratedArray ADT (with unit tests), added Count to the edge enums and changed EdgeAlreadyCreated matrix to use EnumeratedArray.

In D68827#1726300, @Meinersbur wrote:

I am still unconvinced over the boilerplate createPiBlocks.

Addressed all comments.

typo in title: [LoopNext] -> [LoopNest]

The motivation for this patch was discussed at the latest meeting of the LLVM loop group (https://ibm.box.com/s/xn1sfd80jkpfssiqhal6t88yvzxebcex).

LGTM, but I'll let another reviewer give the green light :)

Do I understand it correctly, that this node is added to avoid having to deal with forests?

Kind of. The graph prior to creation of pi-blocks is not a DAG and may have disjoint components. The root node is needed to turn it into a "rooted digraph" making it easier to compute all the strongly connected components. Prior to creating the root, the graph is similar to a forest, but technically speaking it's not a forest because the components may not be trees.

ping

Addressed latest round of review comments.

In D65350#1659816, @Meinersbur wrote:

Thanks for the docs! Could you clarify the difference between paper and implementation? The implementations looks fine, apart a few nits.

In D65350#1652123, @fhahn wrote:

In D65350#1639499, @bmahjour wrote:

In D65350#1636205, @fhahn wrote:

This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges. The idea behind the DependenceGraphBuilder and why we need it are summarized in https://ibm.ent.box.com/v/directed-graph-and-ddg.

I think it would be good to summarize the information in-tree as well, to ensure the information is accessible later on as well. Some of the docs fit in the headers, for some of it a new documentation page might be worth adding. Ideally it would include some info about design decisions, the intended/example uses cases and how the DDG helps and the benefits over the existing infrastructure.

Sure I can create a page or two of documentation, however I'm not very familiar with the doc infrastructure in LLVM. Could you point me to some examples to follow? Would an rts file under llvm/docs/DDG be sufficient? Are they rendered by any tool and if so how can I test it?

Great thanks! Yep adding a .rts should be sufficient. I think you need sphinx installed to build the docs and set LLVM_BUILD_DOCS.

No Problem. Thank you for bringing it up. The latest uploaded patch contains the .rst and the relevant images.

Created a documentation in tree with diagrams and words describing the high level design.

In D65350#1636205, @fhahn wrote:

This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges. The idea behind the DependenceGraphBuilder and why we need it are summarized in https://ibm.ent.box.com/v/directed-graph-and-ddg.

I think it would be good to summarize the information in-tree as well, to ensure the information is accessible later on as well. Some of the docs fit in the headers, for some of it a new documentation page might be worth adding. Ideally it would include some info about design decisions, the intended/example uses cases and how the DDG helps and the benefits over the existing infrastructure.

Addressed the latest round of review comments.

A friendly reminder to kindly review and provide comments/approval. Thank you!