Page MenuHomePhabricator

[JumpThreading] Don't select an edge that we know we can't thread
ClosedPublic

Authored by haicheng on Jan 18 2018, 12:38 PM.

Details

Summary

In r312664 (D36404), JumpThreading stopped threading edges into
loop headers. Unfortunately, I observed a significant performance
regression as a result of this change. Upon further investigation,
the problematic pattern looked something like this (after
many high level optimizations):

while (true) {
    bool cond = ...;
    if (!cond) {
        <body>
    }
    if (cond)
        break;
}

Now, naturally we want jump threading to essentially eliminate the
second if check and hook up the edges appropriately. However, the
above mentioned change, prevented it from doing this because it would
have to thread an edge into the loop header.

Upon further investigation, what is happening is that since both branches
are threadable, JumpThreading picks one of them at arbitrarily. In my
case, because of the way that the IR ended up, it tended to pick
the one to the loop header, bailing out immediately after. However,
if it had picked the one to the exit block, everything would have
worked out fine (because the only remaining branch would then be folded,
not thraded which is acceptable).

Thus, to fix this problem, we can simply eliminate loop headers from
consideration as possible threading targets earlier, to make sure that
if there are multiple eligible branches, we can still thread one of
the ones that don't target a loop header.

Diff Detail

Repository
rL LLVM

Event Timeline

loladiro created this revision.Jan 18 2018, 12:38 PM
haicheng added inline comments.Jan 31 2018, 2:16 PM
test/Transforms/JumpThreading/header-succ.ll
40 ↗(On Diff #130477)

It seems to me that two test cases are identical. Did you forget flip the branch condition or destinations?

loladiro added inline comments.Jan 31 2018, 2:21 PM
test/Transforms/JumpThreading/header-succ.ll
40 ↗(On Diff #130477)

Argh, yes I think I meant to flip the order of the entries in the switch. Thanks for the catch. I'll fix it up for the committed version.

haicheng added inline comments.Feb 1 2018, 11:52 AM
lib/Transforms/Scalar/JumpThreading.cpp
1670 ↗(On Diff #130477)

What about other cases that ThreadEdge() does not support, e.g. SuccBB == BB?

The idea to remove loop headers from destination list when selecting a threadable destination looks reasonable to me. This also fixes the regression we saw in spec2017/perlbench due to D36404.

kparzysz accepted this revision.Mar 22 2018, 11:03 AM
This revision is now accepted and ready to land.Mar 22 2018, 11:03 AM
haicheng added inline comments.Mar 27 2018, 11:12 AM
lib/Transforms/Scalar/JumpThreading.cpp
1485 ↗(On Diff #130477)

I think we need something like

if (DestPopularity.empty())
  return nullptr;

before this line.

This patch removes some destinations. If the remaining destinations' conditions are undef, DestPopularity would be empty and we would get a segment fault here. Without this patch, I don't think the segment fault could happen.

haicheng commandeered this revision.Mar 28 2018, 12:24 PM
haicheng edited reviewers, added: loladiro; removed: haicheng.
haicheng updated this revision to Diff 140123.Mar 28 2018, 12:26 PM

Fixed a segment fault bug with a new test case, fixed an existing test case, and fixed the format.

mcrosier accepted this revision.Mar 29 2018, 6:49 AM

Still LGTM. Thanks for the fix, Haicheng.

This revision was automatically updated to reflect the committed changes.