Page MenuHomePhabricator

[DDG] Data Dependence Graph - DOT printer
ClosedPublic

Authored by bmahjour on Oct 26 2020, 8:01 AM.

Details

Summary

This patch implements a DDG printer pass that generates a graph in the DOT description language, providing a more visually appealing representation of the DDG. Similar to the CFG DOT printer, this functionality is provided under an option called -dot-ddg and can be generated in a less verbose mode under -dot-ddg-only option.

Diff Detail

Event Timeline

bmahjour created this revision.Oct 26 2020, 8:01 AM
bmahjour requested review of this revision.Oct 26 2020, 8:01 AM
Meinersbur added inline comments.Nov 3 2020, 10:39 AM
llvm/include/llvm/Analysis/DDG.h
476

[nit] The initializer ("") is useless? std::string default-initializes to an empty string.

481

[suggestion] Instead of count, you can use llvm::enumerate. I think it's nicer to check at for "not the first" at the beginning instead of the last element at the end.

There also is an interleave function in STLExtras.h for uses cases like this.

llvm/include/llvm/Analysis/DDGPrinter.h
22

[style] Space between includes and namespace?

46

Why does a getter set a field value?

llvm/lib/Analysis/DDGPrinter.cpp
110

Does this const_cast exist to add const qualifier?

118

Could you split this up?

if (Count != PNodes.size())
  OS << "\n";
bmahjour updated this revision to Diff 310607.Dec 9 2020, 12:16 PM
bmahjour marked 5 inline comments as done.

Thanks for the review @Meinersbur and sorry for taking so long to address your comments.

bmahjour added inline comments.Dec 9 2020, 12:17 PM
llvm/include/llvm/Analysis/DDG.h
481

Interesting! Thanks for pointing out those utilities! I'll use interleave.

llvm/include/llvm/Analysis/DDGPrinter.h
46

Good question :)

When printing pi-blocks we would like to show the member nodes being enclosed by the pi-node. However, since the member nodes are also part of the graph, they will get visited during the walk and get dumped into the resulting dot file. To solve this, I'm trying to hide the member nodes from the walk (via isNodeHidden()) when they get visited and then print them as part of printing the pi-block node.

The problem I encountered was that, isNodeHidden() only takes a graph node as a parameter, but for me to know whether a node belongs to a pi-block I need to get access to the graph that contains the nodes. To get around this, I'm caching a pointer to the graph when the getGraphName gets called and use it when isNodeHidden is invoked....yikes!

A cleaner solution (and one that may have other uses in the future) is to make isNodeHidden() take a graph object as argument (similar to getNodeLabel(), and getGraphName()). I'll update the patch to include that change.

llvm/lib/Analysis/DDGPrinter.cpp
110

No. The static_cast is used because the getInstructions() is a member function of SimpleDDGNode but not DDGNode.

Meinersbur accepted this revision.Dec 9 2020, 4:24 PM

Thanks, LGTM.

llvm/include/llvm/Analysis/DDG.h
489

llvm::interleaveComma does that without an additional lambda.

This revision is now accepted and ready to land.Dec 9 2020, 4:24 PM
bmahjour updated this revision to Diff 311678.Dec 14 2020, 1:07 PM

fix formatting and use interleaveComma instead of interleave.

Meinersbur accepted this revision.Dec 14 2020, 1:24 PM

Thanks. Still LGTM.

This revision was landed with ongoing or failed builds.Dec 14 2020, 1:41 PM
This revision was automatically updated to reflect the committed changes.

Can I help fixing the Windows build problem?

martong removed a subscriber: martong.Dec 15 2020, 2:48 AM

Can I help fixing the Windows build problem?

I think I have a fix (please see the updated patch), but don't have access to a windows machine to verify. Would you be able to try building with MSVC and let me know if it passes?

bmahjour updated this revision to Diff 311897.Dec 15 2020, 7:17 AM

Can I help fixing the Windows build problem?

I think I have a fix (please see the updated patch), but don't have access to a windows machine to verify. Would you be able to try building with MSVC and let me know if it passes?

I'll try to recommit and watch the windows buildbots.

This revision was landed with ongoing or failed builds.Dec 16 2020, 9:38 AM

Should this have some tests? Even if guarded by REQUIRES: if some feature is needed.

Should this have some tests? Even if guarded by REQUIRES: if some feature is needed.

Test coverage for the DDG functionality has been added under LIT and unittests. I've opened https://reviews.llvm.org/D93949 to add a test and verify the formatting of the dot file produced when using -dot-ddg.