From 9ca441aa442dd8c33b7a580447ede231b8f02ea7 Mon Sep 17 00:00:00 2001
From: Krzysztof Parzyszek <kparzysz@codeaurora.org>
Date: Wed, 6 Sep 2017 19:36:58 +0000
Subject: [PATCH] Disable jump threading into loop headers

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.

Differential Revision: https://reviews.llvm.org/D36404


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@312664 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/JumpThreading.cpp       | 13 +++++--
 .../JumpThreading/static-profile.ll           | 37 ++++++++++++-------
 2 files changed, 32 insertions(+), 18 deletions(-)

diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp
index 9befd05e767..930ae328ad7 100644
--- a/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/lib/Transforms/Scalar/JumpThreading.cpp
@@ -1791,10 +1791,15 @@ bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
 
   // 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;
   }
 
diff --git a/test/Transforms/JumpThreading/static-profile.ll b/test/Transforms/JumpThreading/static-profile.ll
index 505e849f480..2b2e1cb89cc 100644
--- a/test/Transforms/JumpThreading/static-profile.ll
+++ b/test/Transforms/JumpThreading/static-profile.ll
@@ -23,6 +23,8 @@
 ;             (1) /  |
 ;        (loop exit) | (15)
 ;                    |
+;                  latch
+;                    |
 ;               (back edge)
 ;
 ; First we thread eq_1->check_2 to check_3.  Frequencies are updated to remove
@@ -41,12 +43,14 @@
 ;             (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) /  |
@@ -55,10 +59,12 @@
 ;           /     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)
 ;
@@ -83,10 +89,10 @@ check_1:
 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
@@ -97,16 +103,19 @@ check_2:
 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
-- 
2.50.1