This is an archive of the discontinued LLVM Phabricator instance.

[Dominators] Add parent and sibling property verification (non-hacky)
ClosedPublic

Authored by kuhar on Jun 21 2017, 3:21 PM.

Details

Summary

This patch adds an additional level of verification - it checks parent and sibling properties of a tree. By definition, every tree with these two properties is a dominator tree.

It is possible to run those check by running llvm with -verify-dom-info=1.

Bootstrapping clang and building the llvm test suite with this option enabled doesn't yield any errors.

Diff Detail

Event Timeline

kuhar created this revision.Jun 21 2017, 3:21 PM
dberlin edited edge metadata.Jun 21 2017, 7:11 PM

You should document what the parent and sibling properties are.

dberlin accepted this revision.Jun 23 2017, 7:22 PM

This is fine once the properties are documented.

This revision is now accepted and ready to land.Jun 23 2017, 7:22 PM
kuhar updated this revision to Diff 104069.Jun 26 2017, 6:52 PM

I added comments explaining the checks.

kuhar updated this revision to Diff 104685.Jun 29 2017, 10:43 AM

Update the diff to apply cleanly.

This revision was automatically updated to reflect the committed changes.

Hi Kuhar,

I unfortunately just saw this new patch (and all your others) as I was traveling for a little while. Thanks for providing verifiers that check some of the invariants you expect from a dominator tree. In my discussion with Daniel pointed out a scientific paper which explicitly discusses the parent and sibling properties you mention here: "Dominator Tree Certification and Independent Spanning Trees". I think it would be great to reference this (or earlier work) in the commit to help people who would like to have more background.

It causes infinite loop in bootstrap. Investigating.

It was not infinite loop but extreme slowness.
https://bugs.llvm.org/show_bug.cgi?id=33656

Tobias,
I added some simple explanation and references in r306912 and wordsmithed it a bit in r306916.
Please let me know if you think they are sufficient :)