Disable jump threading into loop headers

[kparzysz]

Summary

Consider this type of a loop:

for (...) {
  ...
  if (...) continue;
  ...
}

Normally, the "continue" would branch to the loop control code that checks whether the loop should continue iterating and which contains the (often) unique loop latch branch. In certain cases jump threading can "thread" the inner branch directly to the loop header, creating a second loop latch. Loop canonicalization would then transform this loop into a loop nest. The problem with this is that in such a loop nest neither loop is countable even if the original loop was. This may inhibit subsequent loop optimizations and be detrimental to performance.

[mcrosier]

@bmakam: Isn't this very similar to some of your recent work?

[bmakam]

In D36404#834053, @mcrosier wrote:

@bmakam: Isn't this very similar to some of your recent work?

This is similar to r308422, but it was only limited to threading unconditional jumps in almost empty blocks. It seems like there are more places in jumpthreading that can turn a loop into non-canonical forms. We also saw in D29572 that jumpthreading can turn a loop into irreducible loop but it was performance neutral.

[davide]

Do you have numbers/examples of performance delta(s) with this patch applied?

[kparzysz]

On our internal benchmarks it's mostly neutral, but the benchmark that motivated it improved by 5.3%. We have some extra code, though, that is supposed to deal with similar cases, so some of the impact may be reduced. By default it keeps the behavior unchanged, so for all other architectures it should have no effect.

[kparzysz]

Ping.

[kparzysz]

Any thoughts on this?

[hfinkel]

In D36404#852556, @kparzysz wrote:

Any thoughts on this?

I think that we should just disable this for all targets. JumpThreading is run early in the pipeline where we are supposed to be simplifying the IR, but importantly, canonicalizing it. Our canonical form must be chosen to enable subsequent optimizations, and if it's not, then we should fix that. The whole reason that LoopHeaders exists in the first place is to avoid this kind of thing. The comment above FindLoopHeaders reads:

/// FindLoopHeaders - We do not want jump threading to turn proper loop
/// structures into irreducible loops.  Doing this breaks up the loop nesting
/// hierarchy and pessimizes later transformations.  To prevent this from
/// happening, we first have to find the loop headers. ...

If this optimization is a good thing to do, then we should have a special run of JumpThreading late in the pipeline where we allow it to put loops into efficient-but-hard-to-analyze forms. That can certainly be follow-up work if it is found to be helpful.

[kparzysz]

Changed the code to simply disable jump threading into loop headers.

[hfinkel]

In D36404#862414, @kparzysz wrote:

Changed the code to simply disable jump threading into loop headers.

LGTM.

[bmakam]

In D36404#835401, @kparzysz wrote:

On our internal benchmarks it's mostly neutral, but the benchmark that motivated it improved by 5.3%. We have some extra code, though, that is supposed to deal with similar cases, so some of the impact may be reduced. By default it keeps the behavior unchanged, so for all other architectures it should have no effect.

@kparzysz, This change regressed spec2017/perlbench by 3% on Falkor. Perhaps we need a late jump-threading pass like Hal suggested?

[kparzysz]

Have you tried it? Changing jump threading to have early/late versions is trivial, the question is when should the late one run, and if that would help in the first place.

[bmakam]

In D36404#869657, @kparzysz wrote:

Have you tried it? Changing jump threading to have early/late versions is trivial, the question is when should the late one run, and if that would help in the first place.

I reverted this change and it recovered the regression. I was going to try to re-run the whole jumpthreading pass after latesimplifycfg to see if it would help, but I don't know if it is a good place because LSR that runs after, will not have the loop in canonical form and loopsimplify will again turn it into irreducible loop. Another place I was thinking was to try before CGP.

[kparzysz]

I'll come up with a late jump threading pass that you can try plugging in, in addition to having the existing one.

[kparzysz]

Late jump threading is in D37816.

[hfinkel]

In D36404#869695, @bmakam wrote:

In D36404#869657, @kparzysz wrote:

Have you tried it? Changing jump threading to have early/late versions is trivial, the question is when should the late one run, and if that would help in the first place.

I reverted this change and it recovered the regression. I was going to try to re-run the whole jumpthreading pass after latesimplifycfg to see if it would help, but I don't know if it is a good place because LSR that runs after, will not have the loop in canonical form and loopsimplify will again turn it into irreducible loop. Another place I was thinking was to try before CGP.

If it'll work right before CGP, that's probably best. That way targets can run IR-level passes that want to look at loops before that.

[bmakam]

In D36404#870092, @hfinkel wrote:

In D36404#869695, @bmakam wrote:

In D36404#869657, @kparzysz wrote:

Have you tried it? Changing jump threading to have early/late versions is trivial, the question is when should the late one run, and if that would help in the first place.

I reverted this change and it recovered the regression. I was going to try to re-run the whole jumpthreading pass after latesimplifycfg to see if it would help, but I don't know if it is a good place because LSR that runs after, will not have the loop in canonical form and loopsimplify will again turn it into irreducible loop. Another place I was thinking was to try before CGP.

If it'll work right before CGP, that's probably best. That way targets can run IR-level passes that want to look at loops before that.

I tried right after latesimplifycfg and it almost recovers the regression. However, running it right before CGP made it even worse for performance of spec2017/perlbench. It seems to be due to some kind of bad interaction with LSR, I haven't digged deeper. Would running right before LSR be reasonable?

[hfinkel]

In D36404#870132, @bmakam wrote:

In D36404#870092, @hfinkel wrote:

In D36404#869695, @bmakam wrote:

In D36404#869657, @kparzysz wrote:

Have you tried it? Changing jump threading to have early/late versions is trivial, the question is when should the late one run, and if that would help in the first place.

I reverted this change and it recovered the regression. I was going to try to re-run the whole jumpthreading pass after latesimplifycfg to see if it would help, but I don't know if it is a good place because LSR that runs after, will not have the loop in canonical form and loopsimplify will again turn it into irreducible loop. Another place I was thinking was to try before CGP.

If it'll work right before CGP, that's probably best. That way targets can run IR-level passes that want to look at loops before that.

I tried right after latesimplifycfg and it almost recovers the regression. However, running it right before CGP made it even worse for performance of spec2017/perlbench. It seems to be due to some kind of bad interaction with LSR, I haven't digged deeper. Would running right before LSR be reasonable?

We need to figure out if LSR is doing something reasonable. It's possible that LSR is actually causing the regression, and old jumpthreading is just serving to obscure the loop structure (thus preventing LSR from doing whatever bad thing it's doing).

[kparzysz]

On another note, this patch was meant to prevent adding extra branches to the header from within the loop. Branches to the header that come from outside of the loop should be fine. In other words, it should be ok to refine the check to only disable jump threading when any of the PredBBs is dominated by the header (SuccBB).

[bmakam]

We need to figure out if LSR is doing something reasonable. It's possible that LSR is actually causing the regression, and old jumpthreading is just serving to obscure the loop structure (thus preventing LSR from doing whatever bad thing it's doing).

It seems like LSR is doing the right thing, the difference in codegen is due to loopsimplify that is required in LSR. If LoopSimplify is required in CGP, then running LateJumpThreading right before CGP (D37866) completely recovers the regression.

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   if (SuccBB == BB) {
     DEBUG(dbgs() << "  Not threading across BB '" << BB->getName()
           << "' - would thread to self!\n");
     return false;
   }
 
   // If threading this would thread across a loop header, don't thread the edge.
   // See the comments above FindLoopHeaders for justifications and caveats.
-  if (LoopHeaders.count(BB)) {
-    DEBUG(dbgs() << "  Not threading across loop header BB '" << BB->getName()
-          << "' to dest BB '" << SuccBB->getName()
-          << "' - it might create an irreducible loop!\n");
+  if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
+    DEBUG({
+      bool BBIsHeader = LoopHeaders.count(BB);
+      bool SuccIsHeader = LoopHeaders.count(SuccBB);
+      dbgs() << "  Not threading across "
+          << (BBIsHeader ? "loop header BB '" : "block BB '") << BB->getName()
+          << "' to dest " << (SuccIsHeader ? "loop header BB '" : "block BB '")
+          << SuccBB->getName() << "' - it might create an irreducible loop!\n";
+    });
     return false;
   }
 
   unsigned JumpThreadCost =
       getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
   if (JumpThreadCost > BBDupThreshold) {
     DEBUG(dbgs() << "  Not threading BB '" << BB->getName()
           << "' - Cost is too high: " << JumpThreadCost << "\n");

llvm/trunk/test/Transforms/JumpThreading/static-profile.ll

 ;                 check_2 (16)
 ;             (8) /  |
 ;             eq_2   | (8)
 ;                 \  |
 ;                 check_3 (16)
 ;             (1) /  |
 ;        (loop exit) | (15)
 ;                    |
+;                  latch
+;                    |
 ;               (back edge)
 ;
 ; First we thread eq_1->check_2 to check_3.  Frequencies are updated to remove
 ; the frequency of eq_1 from check_2 and then the false edge leaving check_2
 ; (changed frequencies are highlighted with * *):
 ;
 ;                 check_1 (16)
 ;             (8) /  |
 ;            eq_1~   | (8)
 ;            /       |
 ;           /     check_2 (*8*)
 ;          /  (8) /  |
 ;          \  eq_2   | (*0*)
 ;           \     \  |
 ;            ` --- check_3 (16)
 ;             (1) /  |
 ;        (loop exit) | (15)
 ;                    |
+;                  latch
+;                    |
 ;               (back edge)
 ;
-; Next we thread eq_1->check_3 and eq_2->check_3 to check_1 as new back edges.
-; Frequencies are updated to remove the frequency of eq_1 and eq_3 from
-; check_3 and then the false edge leaving check_3 (changed frequencies are
-; highlighted with * *):
+; Next we thread eq_1->check_3 and eq_2->check_3 to check_1 as new edges to
+; the loop latch.  Frequencies are updated to remove the frequency of eq_1
+; and eq_3 from check_3 and then the false edge leaving check_3 (changed
+; frequencies are highlighted with * *):
 ;
 ;                 check_1 (16)
 ;             (8) /  |
 ;            eq_1~   | (8)
 ;            /       |
 ;           /     check_2 (*8*)
 ;          /  (8) /  |
 ;         /-- eq_2~  | (*0*)
-; (back edge)        |
-;                 check_3 (*0*)
-;           (*0*) /  |
-;        (loop exit) | (*0*)
+;        /           |
+;       /         check_3 (*0*)
+;      /    (*0*) /  |
+;     |  (loop exit) | (*0*)
+;      \             |
+;       `--------- latch
 ;                    |
 ;               (back edge)
 ;
 ; As a result, the loop exit edge ends up with 0 frequency which in turn makes
 ; the loop header to have maximum frequency.
 
 declare void @bar()
 
 define void @foo(i32 *%p, i32 %n) !prof !0 {
 entry:
   %enter_loop = icmp eq i32 %n, 0
   br i1 %enter_loop, label %exit, label %check_1, !prof !1
 ; CHECK: br i1 %enter_loop, label %exit, label %check_1, !prof !1
 
 check_1:
   %v = load i32, i32* %p
   %cond1 = icmp eq i32 %v, 1
   br i1 %cond1, label %eq_1, label %check_2
 ; No metadata:
 ; CHECK:   br i1 %cond1, label %check_2.thread, label %check_2{{$}}
 
 eq_1:
   call void @bar()
   br label %check_2
-; Verify the new backedge:
+; Verify the new edge:
 ; CHECK: check_2.thread:
 ; CHECK-NEXT: call void @bar()
-; CHECK-NEXT: br label %check_3.thread
+; CHECK-NEXT: br label %latch
 
 check_2:
   %cond2 = icmp eq i32 %v, 2
   br i1 %cond2, label %eq_2, label %check_3
 ; No metadata:
 ; CHECK: br i1 %cond2, label %eq_2, label %check_3{{$}}
 
 eq_2:
   call void @bar()
   br label %check_3
-; Verify the new backedge:
+; Verify the new edge:
 ; CHECK: eq_2:
 ; CHECK-NEXT: call void @bar()
-; CHECK-NEXT: br label %check_3.thread
+; CHECK-NEXT: br label %latch
 
 check_3:
   %condE = icmp eq i32 %v, 3
-  br i1 %condE, label %exit, label %check_1
+  br i1 %condE, label %exit, label %latch
 ; No metadata:
-; CHECK: br i1 %condE, label %exit, label %check_1{{$}}
+; CHECK: br i1 %condE, label %exit, label %latch{{$}}
+
+latch:
+  br label %check_1
 
 exit:
   ret void
 }
 
 !0 = !{!"function_entry_count", i64 120}
 ; CHECK-NOT: branch_weights
 !1 = !{!"branch_weights", i32 119, i32 1}
 ; CHECK: !1 = !{!"branch_weights", i32 119, i32 1}
 ; CHECK-NOT: branch_weights