This is an archive of the discontinued LLVM Phabricator instance.

Differential D3991

[Jump-Threading] Fixed jump threading hang issues (PR15386, PR15851)
ClosedPublic

Authored by dinesh.d on Jun 2 2014, 7:45 AM.

Details

Reviewers
nadav
nicholas
• rafael
bkramer
Commits
rG4737e892def6: AMDGPU/SI: Add d16 support for image intrinsics.
rG657105e582ed: Fixed jump threading going to infinite loop.
rL322903: AMDGPU/SI: Add d16 support for image intrinsics.
rL211103: Fixed jump threading going to infinite loop.
Summary

For specific IR patterns, jump threading pass goes in to infinite loop transforming one pattern to other and then back to previous one.
For these kind of pattern just checking if BB changed is not enough. I have added a set of BBs to maintain how many BBs are updated
and code to terminate pass if count is not increased to previous iteration.

If required, we can tweak this to check if last few iterations have not updated any new BB to terminate pass.

I am not very familiar with Jump Threading pass so this patch might not correct. Please let me know if I should look in any other direction
to fix these issues.

Diff Detail

Event Timeline

dinesh.d updated this revision to Diff 10017.Jun 2 2014, 7:45 AM
dinesh.d retitled this revision from to [Jump-Threading] Fixed jump threading hang issues (PR15386, PR15851).
dinesh.d updated this object.
dinesh.d edited the test plan for this revision. (Show Details)
dinesh.d added reviewers: • rafael, bkramer, nicholas, nadav.
dinesh.d added a subscriber: Unknown Object (MLST).
dinesh.d updated this revision to Diff 10018.Jun 2 2014, 7:50 AM

Forgot to add RUN line in test case

dinesh.d added a comment.Jun 9 2014, 11:14 AM

gentle ping

• rafael edited edge metadata.Jun 9 2014, 6:24 PM

It is not clear why this check is the correct one.One issue is

  • If in the first pass we update 3 BBs, and in the second pass we update 2, this will stop, right? How do you know that there is no further changes to be done?

The more important one is that it doesn't address the root of the problem. From the description it looks like two parts of the pass disagree as to what the canonical form is. Shouldn't we change one of them avoid the transformation?

What are the two forms that cause us to bounce back and forth?

The testcase should also use FileCheck to see that the output is in the canonical form (whatever we decide that to be).

dinesh.d added a comment.Jun 9 2014, 10:53 PM

Each pass iterates over all BBs of the functions and all updated BBs are added to
'UpdatedBB' so if first pass adds 3 BBs and second pass adds 2, there will be
5 BBs in the list and we will still continue with next pass.

Every change in BBs actually adds atleast one new block XXX.thread and till it finds
some new block added or updated, it will do next iteration on all BBs of the function.
and the condition, that will break this is when we are not adding any new block or not
updatind any new BB.

In attached test case, jump threading stuck between 'for.cond1' and 'for.body' block.
Here is sample output for few iterations.
After first iteration:

for.cond1:                                        ; preds = %for.body.thread, %for.body, %land.rhs
  %div5 = phi i32 [ 0, %for.body.thread ], [ %div, %for.body ], [ %div, %land.rhs ]
  %inc = add nsw i32 %div5, 1
  %cmp = icmp slt i32 %inc, 2
  br i1 %cmp, label %for.body, label %for.cond1.thread

for.cond1.thread:                                 ; preds = %for.cond1
  br label %for.body.thread

for.body.thread:                                  ; preds = %for.cond1.thread
  br label %for.cond1

for.body:                                         ; preds = %for.cond1
  %i.02 = phi i32 [ %inc, %for.cond1 ]
  %div = sdiv i32 %i.02, 2
  %i.0.off = add i32 %i.02, 1
  %0 = icmp ugt i32 %i.0.off, 2
  br i1 %0, label %land.rhs, label %for.cond1

2nd:

for.cond1:                                        ; preds = %for.body.thread, %for.body, %land.rhs
  %div5 = phi i32 [ %div, %for.body ], [ %div, %land.rhs ], [ 0, %for.body.thread ]
  %inc = add nsw i32 %div5, 1
  %cmp = icmp slt i32 %inc, 2
  br i1 %cmp, label %for.body, label %for.cond1.thread6

for.cond1.thread6:                                ; preds = %for.cond1
  br label %for.body.thread

for.body.thread:                                  ; preds = %for.cond1.thread6
  br label %for.cond1

for.body:                                         ; preds = %for.cond1
  %i.02 = phi i32 [ %inc, %for.cond1 ]
  %div = sdiv i32 %i.02, 2
  %i.0.off = add i32 %i.02, 1
  %0 = icmp ugt i32 %i.0.off, 2
  br i1 %0, label %land.rhs, label %for.cond1

and 3rd:

for.cond1:                                        ; preds = %for.body.thread, %for.body, %land.rhs
  %div5 = phi i32 [ %div, %for.body ], [ %div, %land.rhs ], [ 0, %for.body.thread ]
  %inc = add nsw i32 %div5, 1
  %cmp = icmp slt i32 %inc, 2
  br i1 %cmp, label %for.body, label %for.cond1.thread

for.cond1.thread:                                 ; preds = %for.cond1
  br label %for.body.thread

for.body.thread:                                  ; preds = %for.cond1.thread
  br label %for.cond1

for.body:                                         ; preds = %for.cond1
  %i.02 = phi i32 [ %inc, %for.cond1 ]
  %div = sdiv i32 %i.02, 2
  %i.0.off = add i32 %i.02, 1
  %0 = icmp ugt i32 %i.0.off, 2
  br i1 %0, label %land.rhs, label %for.cond1

I will update test cases as you suggested. Actually I am not sure about test as
it hangs with trunk and check-all never completes.

dinesh.d added a comment.Jun 10 2014, 4:53 AM

Here are few observations I came across during debugging:
If any of the existing BB in the function is updated, it will be added in UpdatedBB,
if not already exist. For this new XXX.thread blocks are not considered for this
iteration.

For next iteration, all existing BB and new XXX.thread blocks are considered and if
any of the block is updated, it will get added to UpdatedBB.

Condition I have added to break, will be true if none of the existing BBs are updated,
which were not updated in previous passes.

So until, passes are threading some new path, iterations will go on and will break only
if already threaded paths are re-threaded and no new threading is introduced.

dinesh.d updated this revision to Diff 10272.Jun 10 2014, 5:57 AM
dinesh.d edited edge metadata.

updated test case

• rafael added a comment.Jun 10 2014, 6:56 AM

I looked a bit in a debugger and the issue is not the Changed or EverChanged variables. That part of the logic is correct. It is simply "while we found something profitable to do, do it".

What is wrong is that we can find two conflicting actions and we think they are both profitable. The testcase can be reduced to just

define void @f() {
entry:
ret void

for.cond1:
%i.025 = phi i32 [ %inc, %for.body ], [ %inc, %for.body ], [ 1, %for.cond1 ]
%cmp = icmp slt i32 %i.025, 2
br i1 %cmp, label %for.body, label %for.cond1

for.body:
%inc = add nsw i32 %i.025, 0
%a = icmp ugt i32 %inc, 2
br i1 %a, label %for.cond1, label %for.cond1
}

What happens is that we jump thread the jump from for.cond1 to itself, since we can see that the result is just a jump to for.body:

define void @f() {
entry:
ret void

for.cond1:
%i.025 = phi i32 [ %inc, %for.body ], [ %inc, %for.body ]
%cmp = icmp slt i32 %i.025, 2
br i1 %cmp, label %for.body, label %for.cond1.thread

for.cond1.thread:
br label %for.body

for.body:
%i.0252 = phi i32 [ 1, %for.cond1.thread ], [ %i.025, %for.cond1 ]
%inc = add nsw i32 %i.0252, 0
%a = icmp ugt i32 %inc, 2
br i1 %a, label %for.cond1, label %for.cond1
}

We then jump thread the jump from for.cond1.thread to for.body:

define void @f() {
entry:
ret void

for.cond1:
%i.025 = phi i32 [ %inc, %for.body ], [ %inc, %for.body ], [ 1, %for.body.thread ]
%cmp = icmp slt i32 %i.025, 2
br i1 %cmp, label %for.body, label %for.cond1.thread

for.cond1.thread:
br label %for.body.thread

for.body.thread:
br label %for.cond1

for.body:
%i.0252 = phi i32 [ %i.025, %for.cond1 ]
%inc = add nsw i32 %i.0252, 0
%a = icmp ugt i32 %inc, 2
br i1 %a, label %for.cond1, label %for.cond1
}

And we are back to a situation where for.cond1 can be jump threaded. This will loop forever, with for.cond1 and for.body alternating at giving each other another phi edge.

Now, why doesn't this happen all the time? The answer is that we don't jump thread over destinations of back edges. For example, a small modification to the test:

define void @f() {
entry:
br label %for.cond1

for.cond1:
%i.025 = phi i32 [ %inc, %for.body ], [ %inc, %for.body ], [ 1, %for.cond1 ], [ 1, %entry ]
%cmp = icmp slt i32 %i.025, 2
br i1 %cmp, label %for.body, label %for.cond1

for.body:
%inc = add nsw i32 %i.025, 0
%a = icmp ugt i32 %inc, 2
br i1 %a, label %for.cond1, label %for.cond1
}

will prevent it from going in an infinite loop since now for.cond1 is a destination of a back edge.

The logic is sound for reachable code: If we are going over the basic blocks in a loop, at some point we get to one that is pointed by a back edge and stop.

The problem is that in unreachable code there can be cycles with no back edges and we loop forever.

It seems that the best solution is to just delete dead code upfront, or at least don't try to jump thread it.

Cheers,
Rafael

dinesh.d updated this revision to Diff 10316.Jun 10 2014, 11:10 PM

Wow, I couldn't have come up with that. I have updated code to remove
unreachable blocks at the start of pass.

I had to update one test case in select.ll where

switch i32 %0, label %L2 [
  i32 5061, label %L1
  i32 0, label %L2
]

is now getting converted to

%cond = icmp eq i32 %0, 5061
br i1 %cond, label %L2.thread, label %L2
dinesh.d added a comment.Jun 16 2014, 5:00 AM

gentle ping

• rafael accepted this revision.Jun 16 2014, 1:10 PM
• rafael edited edge metadata.

LGTM with two nits.

lib/Transforms/Scalar/JumpThreading.cpp
161

Please include a comment saying why this is not just an optimization.

test/Transforms/JumpThreading/pr15851_hang.ll
2

I don't think timeout is portable. Just run opt directly.

This revision is now accepted and ready to land.Jun 16 2014, 1:10 PM
dinesh.d updated this revision to Diff 10501.Jun 17 2014, 7:37 AM
dinesh.d edited edge metadata.

Thanks. Updated patch as per comments.

dinesh.d closed this revision.Jun 17 2014, 7:42 AM
dinesh.d updated this revision to Diff 10502.

Closed by commit rL211103 (authored by dinesh).

brzycki mentioned this in D44177: [JumpThreading] use UnreachableBlocks to avoid unreachable regions.Mar 6 2018, 3:55 PM
brzycki mentioned this in rL327713: [JumpThreading] Track unreachable BBs to avoid processing.Mar 16 2018, 8:16 AM

Revision Contents

PathSize
lib/
Transforms/
Scalar/
15 lines
test/
Transforms/
JumpThreading/
27 lines

Diff 10017

lib/Transforms/Scalar/JumpThreading.cpp

Show First 20 Lines • Show All 152 Lines • ▼ Show 20 Lines if (skipOptnoneFunction(F))
return false; return false;
DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n"); DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
DL = DLP ? &DLP->getDataLayout() : nullptr; DL = DLP ? &DLP->getDataLayout() : nullptr;
TLI = &getAnalysis<TargetLibraryInfo>(); TLI = &getAnalysis<TargetLibraryInfo>();
LVI = &getAnalysis<LazyValueInfo>(); LVI = &getAnalysis<LazyValueInfo>();
FindLoopHeaders(F); FindLoopHeaders(F);
rafaelUnsubmitted
Not Done
ReplyInline Actions

Please include a comment saying why this is not just an optimization.

rafael: Please include a comment saying why this is not just an optimization.
bool Changed, EverChanged = false; unsigned UpdatedBBCount;
SmallPtrSet<BasicBlock *, 16> UpdatedBB;
do { do {
Changed = false; UpdatedBBCount = UpdatedBB.size();
for (Function::iterator I = F.begin(), E = F.end(); I != E;) { for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
bool Changed = false;
BasicBlock *BB = I; BasicBlock *BB = I;
// Thread all of the branches we can over this block. // Thread all of the branches we can over this block.
while (ProcessBlock(BB)) while (ProcessBlock(BB))
Changed = true; Changed = true;
++I; ++I;
// If the block is trivially dead, zap it. This eliminates the successor // If the block is trivially dead, zap it. This eliminates the successor
// edges which simplifies the CFG. // edges which simplifies the CFG.
if (pred_begin(BB) == pred_end(BB) && if (pred_begin(BB) == pred_end(BB) &&
BB != &BB->getParent()->getEntryBlock()) { BB != &BB->getParent()->getEntryBlock()) {
DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName() DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName()
<< "' with terminator: " << *BB->getTerminator() << '\n'); << "' with terminator: " << *BB->getTerminator() << '\n');
LoopHeaders.erase(BB); LoopHeaders.erase(BB);
LVI->eraseBlock(BB); LVI->eraseBlock(BB);
DeleteDeadBlock(BB); DeleteDeadBlock(BB);
Changed = true; UpdatedBB.insert(BB);
continue; continue;
} }
BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
// Can't thread an unconditional jump, but if the block is "almost // Can't thread an unconditional jump, but if the block is "almost
// empty", we can replace uses of it with uses of the successor and make // empty", we can replace uses of it with uses of the successor and make
// this dead. // this dead.
Show All 17 Lines for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
// If we deleted BB and BB was the header of a loop, then the // If we deleted BB and BB was the header of a loop, then the
// successor is now the header of the loop. // successor is now the header of the loop.
BB = Succ; BB = Succ;
} }
if (ErasedFromLoopHeaders) if (ErasedFromLoopHeaders)
LoopHeaders.insert(BB); LoopHeaders.insert(BB);
} }
if (Changed)
UpdatedBB.insert(BB);
} }
EverChanged |= Changed; } while (UpdatedBBCount < UpdatedBB.size());
} while (Changed);
LoopHeaders.clear(); LoopHeaders.clear();
return EverChanged; return UpdatedBBCount > 0;
} }
/// getJumpThreadDuplicationCost - Return the cost of duplicating this block to /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
/// thread across it. Stop scanning the block when passing the threshold. /// thread across it. Stop scanning the block when passing the threshold.
static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB, static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB,
unsigned Threshold) { unsigned Threshold) {
/// Ignore PHI nodes, these will be flattened when duplication happens. /// Ignore PHI nodes, these will be flattened when duplication happens.
BasicBlock::const_iterator I = BB->getFirstNonPHI(); BasicBlock::const_iterator I = BB->getFirstNonPHI();
▲ Show 20 Lines • Show All 1,478 Lines • Show Last 20 Lines

test/Transforms/JumpThreading/pr15851_hang.ll

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
rafaelUnsubmitted
Not Done
ReplyInline Actions

I don't think timeout is portable. Just run opt directly.

rafael: I don't think timeout is portable. Just run opt directly.
define void @f() {
entry:
call void @f()
unreachable
for.cond1: ; preds = %for.cond1, %for.inc
%i.0 = phi i32 [ %inc, %for.inc ], [ 0, %for.cond1 ]
%cmp = icmp slt i32 %i.0, 2
br i1 %cmp, label %for.body, label %for.cond1
for.body: ; preds = %for.cond1
%div = sdiv i32 %i.0, 2
%i.0.off = add i32 %i.0, 1
%0 = icmp ugt i32 %i.0.off, 2
br i1 %0, label %land.rhs, label %for.inc
land.rhs: ; preds = %for.body
store i32 0, i32* undef, align 4
br label %for.inc
for.inc: ; preds = %for.body
%inc = add nsw i32 %div, 1
br label %for.cond1
}