This is an archive of the discontinued LLVM Phabricator instance.

[Dominators] Introduce DomTree verification levels
ClosedPublic

Authored by kuhar on Jan 20 2018, 1:30 PM.

Details

Summary

Currently, there are 2 ways to verify a DomTree:

  • DT.verify() -- runs full tree verification and checks all the properties and gives a reason why the tree is incorrect. This is run by when EXPENSIVE_CHECKS are enabled or when -verify-dom-info flag is set.
  • DT.verifyDominatorTree() -- constructs a fresh tree and compares it against the old one. This does not check any other tree properties (DFS number, levels), nor ensures that the construction algorithm is correct. Used by some passes inside assertions.

This patch introduces DomTree verification levels, that try to close the gape between the two ways of checking trees by introducing 3 verification levels:

  • Full -- checks all properties, but can be slow (O(N^3)). Used when manually requested (e.g. assert(DT.verify())) or when -verify-dom-info is set.
  • Basic -- checks all properties except the sibling property, and compares the current tree with a freshly constructed one instead. This should catch almost all errors, but does not guarantee that the construction algorithm is correct. Used when EXPENSIVE checks are enabled.
  • Fast -- checks only basic properties (reachablility, dfs numbers, levels, roots), and compares with a fresh tree. This is meant to replace the legacy DT.verifyDominatorTree() and in my tests doesn't cause any noticeable performance impact even in the most pessimistic examples.

When used to verify dom tree wrapper pass analysis on sqlite3, the 3 new levels make opt -O3 take the following amount of time on my machine:

  • no verification: 8.3s
  • DT.verify(VerificationLevel::Fast): 10.1s
  • DT.verify(VerificationLevel::Basic): 44.8s
  • DT.verify(VerificationLevel::Full): 1m 46.2s

(and the previous DT.verifyDominatorTree() is within the noise of the Fast level)

This patch makes DT.verifyDominatorTree() pick between the 3 verification levels depending on EXPENSIVE_CHECKS and -verify-dom-info.

Diff Detail

Repository
rL LLVM

Event Timeline

kuhar created this revision.Jan 20 2018, 1:30 PM
kuhar added a comment.Jan 20 2018, 1:50 PM

@dberlin:

I assume if we ever bothered to make the verification O(N) again using better algorithms, we'd go back to one level of verification?

I think it's very unlikely that someone will implement this in the foreseeable future. As far as I understand, this would disallow to perform any manual updates and require extra data to be sorted in the tree and the tree nodes.
But if someone implements this, it would be best to go back one verification level. And if it tells us the tree is incorrect, we could run the current full verification to get a descriptive error message telling us what exactly went wrong.

kuhar edited the summary of this revision. (Show Details)Jan 20 2018, 4:17 PM
kuhar added a subscriber: MatzeB.Jan 20 2018, 7:12 PM

LGTM. I just have one question about the patch, see inline.

include/llvm/Support/GenericDomTree.h
775

Is the Full level the same as what verify did before this patch? I'm curious how the default level was chosen.

kuhar added inline comments.Jan 22 2018, 7:59 AM
include/llvm/Support/GenericDomTree.h
775

Yes. This is to preserve behavior of the existing code.
I also expect DT.verify() to be used for debugging, where you don't really care how long it takes. And then if it becomes a performance issue for someone, they can explicitly request a faster (but imprecise) level.

dberlin accepted this revision.Jan 22 2018, 10:58 AM

@dberlin:

I assume if we ever bothered to make the verification O(N) again using better algorithms, we'd go back to one level of verification?

I think it's very unlikely that someone will implement this in the foreseeable future.

Sure, i was just asking

As far as I understand, this would disallow to perform any manual updates and require extra data to be sorted in the tree and the tree nodes.

That's just the current state. These things always improve :)

But if someone implements this, it would be best to go back one verification level. And if it tells us the tree is incorrect, we could run the current full verification to get a descriptive error message telling us what exactly went wrong.

SGTM

This revision is now accepted and ready to land.Jan 22 2018, 10:58 AM
brzycki accepted this revision.Jan 22 2018, 11:32 AM

LGTM.

This revision was automatically updated to reflect the committed changes.