[JumpThreading] Preserve DT and LVI across the pass.

[brzycki]

Summary

JumpThreading now preserves dominance and lazy value information across the entire pass. The pass manager is also informed of this preservation with the goal of DT and LVI being recalculated fewer times overall during compilation.

This change prepares JumpThreading for enhanced opportunities; particularly those across loop boundaries.

Patch by Brian Rzycki and Sebastian Pop.

This is the second attempt at the patch, the first one can be found at D37528. This also includes the fix from D38383 and a fix to an assert reported by @eli.friedman .

[kuhar]

Have you tried profiling it on some non-trivial module, like sqlite3? I'm wondering where the reported slowdown comes from exactly.

[brzycki]

In D38558#888638, @kuhar wrote:

Have you tried profiling it on some non-trivial module, like sqlite3? I'm wondering where the reported slowdown comes from exactly.

Not yet. I've focused on correctness and bug fixing. I was planning on spending some time tomorrow to analyze compile time deltas. Do you have any recommended tools to help?

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1112

@eli.friedman This is the fix for your assert. In this context BB had a terminator instruction that looked like:

br i8 cmp eq 0, %BB_A, %BB_A

In this corner-case we don't actually remove the edge in the dominance graph because we're converting to:

br %BB_A

And the edge between these two blocks still exists.

[bmakam]

llvm/lib/Transforms/Utils/Local.cpp

720

I am trying to understand why we need to recalculate DT here. Can't we just delete the edge before nuking BB instead of recalculating?

[brzycki]

Rebase patch to tip as of 10/24/2017.

[brzycki]

This code is superceded by D40146.

llvm/lib/Transforms/Utils/Local.cpp

720

Hello @bmakam , unfortunately no. In this corner case we've removed the entry block of the function. This is treated as the root node of the new DT data structure @kuhar implemented. If we continue as you propose the next insertEdge() or deleteEdge() returns an assert about the root node of the DT being invalid.

I had a private e-mail thread discussion with @kuhar and @dberlin last August and we decided on this compromise in this corner-case event.

720

I collected some statistics on this event: of the times we enter MergeBasicBlockIntoOnlyPred() this case is encountered somewhere around 5% of the time:

4.49% of calls remove the entry block for ninja check
913 calls into MergeBasicBlockIntoOnlyPred
41 entry block removals

5.09% of calls remove the entry block for test-suite build
30335 calls into MergeBasicBlockIntoOnlyPred
1545 entry block removals

980

This is the same patch as D38383.