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!

Addressed comments from Michael and Min-Yih.

Addressed comments from Michael and Min-Yih.

Address comments on the unit test.

In D64088#1579497, @fhahn wrote:

In D64088#1579463, @Meinersbur wrote:

To not to be stuck in details and not block the dependence graph patches, we maybe should land the patch and work on it in-tree when its users materialize?

Sounds good, but I think to land it, it would be good if we have some unit tests for the current implementation, to make sure it builds, we don’t regress and have sanitizer coverage.

Address more review comments.

Address second round of comments from Michael and Florian.

In D64088#1577250, @Meinersbur wrote:

In D64088#1577050, @bmahjour wrote:

In D64088#1574555, @Meinersbur wrote:

To reduce the number of allocations, have you thought about making EdgeList contain the edges objects instead of pointers? The edges would have to be copied/moved into the list and edges could not be compared by identity. Is this semantic needed/are edge objects large?

Since the edge class does not contain the source node, the same edge object could be put into multiple outgoing edges lists. Is this supported?

I think we would be better off using pointers in this case, because of the following reasons:

1. Using pointers gives the clients freedom to use polymorphic behavior.

I don't see why you would go the way implementing compile-time template polymorphism, but introduce vtables in derived classes.

I actually just realized that we cannot have a container of objects due to the CRTP idiom, because the edge type is not a complete type yet. If we don't use static polymorphism, then we need to use dynamic polymorphism and that requires a container of pointers. Either way we need to store pointers, it seems.

In D64088#1574555, @Meinersbur wrote:

To reduce the number of allocations, have you thought about making EdgeList contain the edges objects instead of pointers? The edges would have to be copied/moved into the list and edges could not be compared by identity. Is this semantic needed/are edge objects large?

Since the edge class does not contain the source node, the same edge object could be put into multiple outgoing edges lists. Is this supported?

Address Michael's review comments.

In D64088#1568644, @lebedev.ri wrote:

Tests missing.

In D64088#1570392, @myhsu wrote:

Is there any plan on supporting GraphTraits in this patch?

formatting change to reduce the number of new lines in the options description.

Renamed the option to -da-disable-delinearization-checks and set the default value to "false". Updated LIT tests accordingly.

In D62610#1526365, @jdoerfert wrote:

I would have liked to invert the option though. Most similar options are set up such that they allow to opt-out of the sound behavior.

In D62610#1523995, @dmgreen wrote:

As a debugging tool, this sounds fine. Not so sure about the tests, but I guess they are not hurting anyone :) And show good room for improvement.

Do you have any ideas how we might get the llvm form of them we have here (not the c form) to give good DA results without the miscompiles that the new option would produce? I was wondering if it was worth trying to get DA to return a dependency that is conditional on a set of predicates. Clients (we only have 3 at the moment) could treat predicated dependencies as "confused", or version the loop based on them.