Page MenuHomePhabricator

[JumpThreading] Ignore nil destionation when determining whether a block only goes to a single destination
Needs ReviewPublic

Authored by trentxintong on Jun 14 2018, 11:37 AM.

Details

Reviewers
davide
brzycki
Summary

Make sure UNDEF does not cause us to believe a block can have multiple possible destintations.

Diff Detail

Event Timeline

trentxintong created this revision.Jun 14 2018, 11:37 AM

Handle when all destinations are null (i.e. UNDEF value). There is a slight change in pr22086.ll this is due
to we do not run SimplifyInstructionsInBlock after folding (we run after threading).

Hi @trentxintong , I am just starting to review this diff and will get back to you with more meaningful comments soon. While I'm doing that could you tell me if this work is from a bug you discovered or for a new feature you'd like to see implemented. Looking at your .ll changes below makes me believe this is a new feature, but I'd like to be sure to know.

Hi @brzycki. This is a deficiency in a feature we already have. In jump threading, when we can tell all the predecessors of a block go to the same destination. we do not need to thread, we can just fold the terminator of the block. This has less impact on the CFG and also we do not have the problem of not being able to jump threading because the block can not be duplicated.

In case we have a Val being UNDEF, we can ignore it as it can be treated as going to any successor, i.e. we should not go to MultipleDestSentinel state because we see a DestBB==nullptr.

My comments are inline. I'm also curious to know what kind of testing you've done on this (ninja check, ninja check-all, any test-suite runs, etc). I'd like more testing if it's just ninja check: the included tests are a small sampling of real-world code and test-suite is a bit better for this kind of change.

lib/Transforms/Scalar/JumpThreading.cpp
1608

It might be better to add a new counter and increment it here:

if (isa<UndefValue>(Val)) {
  ++PredWithUndefDest;
  continue;
} else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {

I dislike that the logic changes below include PredWithKnownDest for undef (unknown) destinations.

1623

Nit: please convert the . to a , from the end of the previous line or consider re-wording the entire comment.

1655

Instead of changing this core logic it might make more sense to do:

if (PredWithUndefDest && !OnlyDest)
  OnlyDest = BB->getTerminator()->getSuccessor(GetBestDestForJumpOnUndef(BB));
if (OnlyDest && OnlyDest != MultipleDestSentinel) {
  if ((PredWithKnownDest + PredWithUndefDest) == (size_t)pred_size(BB)) {
    ...

I say this because ProcessThreadableEdges() and the multiple calls from ProcessBlock() can create complex and subtle interplay. I try to not change the logic as much as possible between these two.

test/Transforms/JumpThreading/fold-not-thread.ll
332

Is L5 necessary in this functional test? It's connected to nothing.

Added small fix to suggested code.

lib/Transforms/Scalar/JumpThreading.cpp
1608

You also need to add before the continue:

PredToDestList.push_back(std::make_pair(Pred, nullptr));

inside the UndefValue check.

Hi Brian

Thank you very much for the review. I have not taken a look at the
code after integrating what Danny has said. I will take a look at it
in the next few days and see whether this patch is still useful. In
case it is, I will definitely address your suggestions.

-Xin

Hi @trentxintong , did you decide if this patch was useful?