This is an archive of the discontinued LLVM Phabricator instance.

[JumpThreading] Replace MergeBasicBlockIntoOnlyPred() with MergeBlockIntoPredecessor()
AbandonedPublic

Authored by brzycki on Feb 26 2019, 3:27 PM.

Details

Summary

In D48202 the helper function MergeBasicBlockIntoOnlyPred() was removed from llvm with the exception of JumpThreading. @asbirlea asked me to look at it for this final case. This patch replaces the last remaining usage of MergeBasicBlockIntoOnlyPred() with MergeBlockIntoPredecessor(). (I didn't fully remove the function and its test cases. I consider that work for a separate patch.)

This is a bit more complex than a simple function replacement for the following reasons:

  1. MergeBlockIntoPredecessor() may return false and not perform the merge while MergeBasicBlockIntoOnlyPred() always performed the action.
  2. The checks in MergeBlockIntoPredecessor() are slightly different.
  3. MergeBlockIntoPredecessor() does block hoisting. This was by far the biggest change and caused several re-labeling of blocks in test cases.
  4. In a few test cases the hoisting prevented existing checks from detecting trivially dead code from the existing logic in ProcessBlock.
  5. A bug in MergeBlockIntoPredecessor() causing DTU asserts, fixed with D58444.

Passes make-check on x86_64, test-suite on x86_64. I see nominal gains of a few percent overall on compile_time in test-suite and test-suite with CTmark. The benchmark execution times are on par, indicating this change (should be) a no-op for emitted IR.

Note: This diff relies on D58444 being comitted first. Without it test-suite benchmarks cause compiler asserts.

Finally, there is one instance in the test cases, lvi-after-jumpthreading.ll where hoisting causes the loss of valuable LVI information. There is no API to inform LVI two blocks have been merged other than deleting the merged block and (potentially) deleting the block that was merged into. It would be nice to have an LVI API similar to LVI->threadEdge(...) to prevent such metadata loss. Ideally it'd be a parameter to MergeBlockIntoPredecessor().

Diff Detail

Event Timeline

brzycki created this revision.Feb 26 2019, 3:27 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 26 2019, 3:27 PM
brzycki edited the summary of this revision. (Show Details)Feb 26 2019, 3:29 PM

Thank you for working on this!
I can only comment on the changes in the testcases which looks exactly as expected considering the blocks now being merge in the other direction.

I will default the approval to someone familiar with JumpThreading.

dmgreen added a subscriber: dmgreen.Mar 1 2019, 9:13 AM

Bump. Reviews or feedback would be appreciated.

brzycki updated this revision to Diff 191747.Mar 21 2019, 11:12 AM

Rebase patchset to tip.

brzycki updated this revision to Diff 195468.Apr 16 2019, 3:00 PM

Rebase to tip. Reviews or comments are very much appreciated.

asbirlea accepted this revision.May 31 2019, 1:50 PM

LGTM.

This revision is now accepted and ready to land.May 31 2019, 1:50 PM

Thank you @asbirlea for the review. I'll rebase, verify everything looks ok, and commit. Hopefully in the next 7-10 days based on my current work load.

brzycki abandoned this revision.Feb 12 2020, 11:55 AM

I must abandon this revision as my current employer has not authorized me to contribute to LLVM.