Page MenuHomePhabricator

[JumpThreading] Preserve DT and LVI across the pass.

Authored by brzycki on Oct 4 2017, 12:49 PM.



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 .

Diff Detail

Event Timeline

brzycki created this revision.Oct 4 2017, 12:49 PM
kuhar edited edge metadata.EditedOct 4 2017, 12:52 PM

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

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?


@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 added a subscriber: bmakam.Oct 10 2017, 9:15 AM
bmakam added inline comments.

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 updated this revision to Diff 120077.Oct 24 2017, 8:49 AM

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

brzycki abandoned this revision.Jan 19 2018, 8:24 AM

This code is superceded by D40146.


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.


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


This is the same patch as D38383.