[JumpThreading] Reverse the order of basic block iteration.

[mnadeem]

Summary

This patch is a fix for a compile time issue I was seeing in
SPEC2017/cam4, reducing the monstrous compile time for
one file from 80+min to under 10sec.

The test changes seem reasonable, although I am not too sure
about the change in LazyValueAnalysis dump as I am not familiar with it.

Essentially the file I was compiling had many lines of fortran code of this
form: arr(:ncol,:) = 0. The 2d array dimensions in this case are statically
known.

When compiling with flang-new this is converted into a nested loop
with a store, and just before Jump Threading is run we have tens of
thousands of branches containing GEP + memsets and memcpys and each
threadable chain is very long as well.

With the current top down approach 90% of the time was spent
in renaming non-local uses of instructions in updateSSA(). Profiling
showed that about half that time was spent in the
SSAUpdater::FindAvailableVals() --> FindExistingPHI() call. This is
because we were accumulating new PHIs as we kept on threading the
successors BBs.

I was not able to reduce a test case showing the high compile time but
the file is cldwat2m_macro.f90 and I compiled with O3.

[mnadeem]

@nikic I dont have the framework to measure more general compile time impact. Could you please help in getting this tested on https://llvm-compile-time-tracker.com/ ?

[efriedma]

I'd prefer to try to prevent compile-time explosions in a more reliable way; messing with iteration order doesn't seem like it will work in all cases.

Even if we do want to mess with the iteration order, just reversing the basic block list isn't really reliable. See llvm/ADT/PostOrderIterator.h

[mnadeem]

In D135125#3834198, @efriedma wrote:

I'd prefer to try to prevent compile-time explosions in a more reliable way; messing with iteration order doesn't seem like it will work in all cases.

I thought about alternate ways to reduce the compile time but could not come up with anything.

Any ideas are appreciated! Here is snippet of relevant IR https://gist.github.com/UsmanNadeem/5543f14020b654f6c1f1d9dc5dc6ab50 .

When JT is called on ._crit_edge2292, %uglygep.13072 is replicated in the threaded block and a PHI node (lets say %phi.1) is inserted into the successor i.e. ._crit_edge2292.1. In the next iteration JT is called on ._crit_edge2292.1 and we now need to build two PHI nodes when rewriting the SSA. One for the new value %uglygep.23073 and one for %phi.1 that we created earlier. The number of new phi nodes we need to build keeps adding up as we go down the chain.

If we iterate from the bottom up then then we do not have this issue by design.

messing with iteration order doesn't seem like it will work in all cases.

I agree, but it would be helpful if we could get compile-time data for other benchmarks so that we have the whole picture.
On another note, I did run a performance experiment and did not see any regression and saw a perf 3% gain in SPEC2017/xz. And look at the test output changes I do see some more threading.

Even if we do want to mess with the iteration order, just reversing the basic block list isn't really reliable. See llvm/ADT/PostOrderIterator.h

A lot of tests are throwing Iterator index out of bound error with the post order iterator. I think that the JT pass modifies the IR in a way that is messing with the PO iterator. I could break the loop on every change to get around this but it would not be efficient, so not sure if just reversing the list could work here...?

Please let me know your thoughts.

[nikic]

CTMark results: http://llvm-compile-time-tracker.com/compare.php?from=8d569e638b9e960b4ab635d780e60e8fa0b049f7&to=5b6c4c8d92da85384942a0dafb232bbc29c82c01&stat=instructions

Worth noting that LVI result quality is unfortunately dependent on query order (when querying without block-local facts, it is preferred to query the loop header before the loop latch -- though probably when querying with block-local results the reverse is true).

[efriedma]

When JT is called on ._crit_edge2292, %uglygep.13072 is replicated in the threaded block and a PHI node (lets say %phi.1) is inserted into the successor i.e. ._crit_edge2292.1. In the next iteration JT is called on ._crit_edge2292.1 and we now need to build two PHI nodes when rewriting the SSA. One for the new value %uglygep.23073 and one for %phi.1 that we created earlier. The number of new phi nodes we need to build keeps adding up as we go down the chain.

I'm not sure I understand the growth aspect here; %uglygep.13072 isn't defined or used in any of the blocks that are getting replicated? Or is the issue that the SSA algorithm spends time trying to rewrite things that don't need to be rewritten? Would using SSAUpdaterBulk in JumpThreadingPass::updateSSA help?

If we iterate from the bottom up then then we do not have this issue by design.

Not this exact issue, no, but trying to fix a local issue by making a global change tends to show other algorithmic weaknesses.

A lot of tests are throwing Iterator index out of bound error with the post order iterator.

I think the post order iterator caches some data; probably if JumpThreading is modifying blocks while you iterate, that won't work. Maybe you could use the iterator to construct a worklist or something like that.

On another note, I did run a performance experiment and did not see any regression and saw a perf 3% gain in SPEC2017/xz. And look at the test output changes I do see some more threading.

That might be an argument for changing the iteration order, if we can explain why it's happening.

[mnadeem]

In D135125#3840548, @efriedma wrote:

When JT is called on ._crit_edge2292, %uglygep.13072 is replicated in the threaded block and a PHI node (lets say %phi.1) is inserted into the successor i.e. ._crit_edge2292.1. In the next iteration JT is called on ._crit_edge2292.1 and we now need to build two PHI nodes when rewriting the SSA. One for the new value %uglygep.23073 and one for %phi.1 that we created earlier. The number of new phi nodes we need to build keeps adding up as we go down the chain.

I'm not sure I understand the growth aspect here; %uglygep.13072 isn't defined or used in any of the blocks that are getting replicated? Or is the issue that the SSA algorithm spends time trying to rewrite things that don't need to be rewritten? Would using SSAUpdaterBulk in JumpThreadingPass::updateSSA help?

The SSA algorithm spends time trying to rewrite things that actually need to be rewritten but we have *more of these things* compared to when we do bottom up threading. I will try to see if SSAUpdaterBulk helps.

I am not sure if I am doing a good job of explaining it, try running opt -jump-threading -debug-only=jump-threading on this test file and you will quickly see what the issue is from the debug dump.
Full .ll file : https://gist.github.com/UsmanNadeem/bfa78d0390d103275792afdd21069d2c

%uglygep.13072 is defined in ._crit_edge2292 and used in .lr.ph2291.1 and .lr.ph2669.1. ._crit_edge2292 gets replicated and a phi node put in its successor ._crit_edge2292.1.
Next time ._crit_edge2292.1 gets replicated with 1 phi node and one gep, after one more iteration ._crit_edge2292.2 gets replicated with 2 phi nodes and one gep, this goes on until we reach ._crit_edge2292.24 when we have 24 phi nodes that need to be replicated.

  Threading edge from '._crit_edge2292.23.thread' to '._crit_edge2292.25, across block:

._crit_edge2292.24:                               ; preds = %._crit_edge2292.23.thread, %.lr.ph2291.24
  %uglygep.243095600 = phi ptr [ %uglygep.243095576, %._crit_edge2292.23.thread ], [ %uglygep.243095, %.lr.ph2291.24 ]
  %uglygep.223093506530599 = phi ptr [ %uglygep.223093484, %._crit_edge2292.23.thread ], [ %uglygep.223093, %.lr.ph2291.24 ]
  %uglygep.203091420442505531598 = phi ptr [ %uglygep.203091400, %._crit_edge2292.23.thread ], [ %uglygep.203091, %.lr.ph2291.24 ]
  %uglygep.183089342362419443504532597 = phi ptr [ %uglygep.183089324, %._crit_edge2292.23.thread ], [ %uglygep.183089, %.lr.ph2291.24 ]
  %uglygep.163087272290341363418444503533596 = phi ptr [ %uglygep.163087256, %._crit_edge2292.23.thread ], [ %uglygep.163087, %.lr.ph2291.24 ]
  %uglygep.143085210226271291340364417445502534595 = phi ptr [ %uglygep.143085196, %._crit_edge2292.23.thread ], [ %uglygep.143085, %.lr.ph2291.24 ]
  %uglygep.123083156170209227270292339365416446501535594 = phi ptr [ %uglygep.123083144, %._crit_edge2292.23.thread ], [ %uglygep.123083, %.lr.ph2291.24 ]
  %uglygep.103081110122155171208228269293338366415447500536593 = phi ptr [ %uglygep.103081100, %._crit_edge2292.23.thread ], [ %uglygep.103081, %.lr.ph2291.24 ]
  %uglygep.830797282109123154172207229268294337367414448499537592 = phi ptr [ %uglygep.8307964, %._crit_edge2292.23.thread ], [ %uglygep.83079, %.lr.ph2291.24 ]
  %uglygep.6307742507183108124153173206230267295336368413449498538591 = phi ptr [ %uglygep.6307736, %._crit_edge2292.23.thread ], [ %uglygep.63077, %.lr.ph2291.24 ]
  %uglygep.43075202641517084107125152174205231266296335369412450497539590 = phi ptr [ %uglygep.4307516, %._crit_edge2292.23.thread ], [ %uglygep.43075, %.lr.ph2291.24 ]
  %uglygep.23073610192740526985106126151175204232265297334370411451496540589 = phi ptr [ %uglygep.230734, %._crit_edge2292.23.thread ], [ %uglygep.23073, %.lr.ph2291.24 ]
  %uglygep.130722511182839536886105127150176203233264298333371410452495541588 = phi ptr [ %uglygep.130721, %._crit_edge2292.23.thread ], [ %uglygep.13072, %.lr.ph2291.24 ]
  %uglygep.3307412172938546787104128149177202234263299332372409453494542587 = phi ptr [ %uglygep.330749, %._crit_edge2292.23.thread ], [ %uglygep.33074, %.lr.ph2291.24 ]
  %uglygep.530763037556688103129148178201235262300331373408454493543586 = phi ptr [ %uglygep.5307625, %._crit_edge2292.23.thread ], [ %uglygep.53076, %.lr.ph2291.24 ]
  %uglygep.73078566589102130147179200236261301330374407455492544585 = phi ptr [ %uglygep.7307849, %._crit_edge2292.23.thread ], [ %uglygep.73078, %.lr.ph2291.24 ]
  %uglygep.9308090101131146180199237260302329375406456491545584 = phi ptr [ %uglygep.9308081, %._crit_edge2292.23.thread ], [ %uglygep.93080, %.lr.ph2291.24 ]
  %uglygep.113082132145181198238259303328376405457490546583 = phi ptr [ %uglygep.113082121, %._crit_edge2292.23.thread ], [ %uglygep.113082, %.lr.ph2291.24 ]
  %uglygep.133084182197239258304327377404458489547582 = phi ptr [ %uglygep.133084169, %._crit_edge2292.23.thread ], [ %uglygep.133084, %.lr.ph2291.24 ]
  %uglygep.153086240257305326378403459488548581 = phi ptr [ %uglygep.153086225, %._crit_edge2292.23.thread ], [ %uglygep.153086, %.lr.ph2291.24 ]
  %uglygep.173088306325379402460487549580 = phi ptr [ %uglygep.173088289, %._crit_edge2292.23.thread ], [ %uglygep.173088, %.lr.ph2291.24 ]
  %uglygep.193090380401461486550579 = phi ptr [ %uglygep.193090361, %._crit_edge2292.23.thread ], [ %uglygep.193090, %.lr.ph2291.24 ]
  %uglygep.213092462485551578 = phi ptr [ %uglygep.213092441, %._crit_edge2292.23.thread ], [ %uglygep.213092, %.lr.ph2291.24 ]
  %uglygep.233094552577 = phi ptr [ %uglygep.233094529, %._crit_edge2292.23.thread ], [ %uglygep.233094, %.lr.ph2291.24 ]
  %uglygep.253096 = getelementptr i8, ptr %40, i64 800, !dbg !127
  br i1 %.not2713, label %._crit_edge2292.25, label %.lr.ph2291.25, !dbg !127


JT: Renaming non-local uses of:   %uglygep.243095600 = phi ptr [ %uglygep.243095, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.223093506530599 = phi ptr [ %uglygep.223093, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.203091420442505531598 = phi ptr [ %uglygep.203091, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.183089342362419443504532597 = phi ptr [ %uglygep.183089, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.163087272290341363418444503533596 = phi ptr [ %uglygep.163087, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.143085210226271291340364417445502534595 = phi ptr [ %uglygep.143085, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.123083156170209227270292339365416446501535594 = phi ptr [ %uglygep.123083, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.103081110122155171208228269293338366415447500536593 = phi ptr [ %uglygep.103081, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.830797282109123154172207229268294337367414448499537592 = phi ptr [ %uglygep.83079, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.6307742507183108124153173206230267295336368413449498538591 = phi ptr [ %uglygep.63077, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.43075202641517084107125152174205231266296335369412450497539590 = phi ptr [ %uglygep.43075, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.23073610192740526985106126151175204232265297334370411451496540589 = phi ptr [ %uglygep.23073, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.130722511182839536886105127150176203233264298333371410452495541588 = phi ptr [ %uglygep.13072, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.3307412172938546787104128149177202234263299332372409453494542587 = phi ptr [ %uglygep.33074, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.530763037556688103129148178201235262300331373408454493543586 = phi ptr [ %uglygep.53076, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.73078566589102130147179200236261301330374407455492544585 = phi ptr [ %uglygep.73078, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.9308090101131146180199237260302329375406456491545584 = phi ptr [ %uglygep.93080, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.113082132145181198238259303328376405457490546583 = phi ptr [ %uglygep.113082, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.133084182197239258304327377404458489547582 = phi ptr [ %uglygep.133084, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.153086240257305326378403459488548581 = phi ptr [ %uglygep.153086, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.173088306325379402460487549580 = phi ptr [ %uglygep.173088, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.193090380401461486550579 = phi ptr [ %uglygep.193090, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.213092462485551578 = phi ptr [ %uglygep.213092, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.233094552577 = phi ptr [ %uglygep.233094, %.lr.ph2291.24 ]
JT: Renaming non-local uses of:   %uglygep.253096 = getelementptr i8, ptr %40, i64 800, !dbg !127

[efriedma]

Oh, I see, the block we choose to thread across continues to get bigger, but the cost model is fine with it because the PHI nodes are "free".

I guess we could just tell the JumpThreading cost model to refuse to clone a block if there are, say, 20 or more PHI nodes in that block. Not ideal, but reduces the chance of runaway growth. (I mean, the growth is still sort of runaway; SSA construction is linear in the size of the function's CFG, so repeatedly doing it is fundamentally quadratic, but we can prevent it from getting worse than that.)

[mnadeem]

In D135125#3854275, @efriedma wrote:

Oh, I see, the block we choose to thread across continues to get bigger, but the cost model is fine with it because the PHI nodes are "free".

I guess we could just tell the JumpThreading cost model to refuse to clone a block if there are, say, 20 or more PHI nodes in that block. Not ideal, but reduces the chance of runaway growth. (I mean, the growth is still sort of runaway; SSA construction is linear in the size of the function's CFG, so repeatedly doing it is fundamentally quadratic, but we can prevent it from getting worse than that.)

Abandoned in favor of D136716 which puts a limit on the number of PHI nodes.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
 
   if (!ThreadAcrossLoopHeaders)
     findLoopHeaders(F);
 
   bool EverChanged = false;
   bool Changed;
   do {
     Changed = false;
-    for (auto &BB : F) {
+    auto BBList = &(F.getBasicBlockList());
+    auto FuncRevIter = make_range(BBList->rbegin(), BBList->rend());
+    for (auto &BB : FuncRevIter) {
       if (Unreachable.count(&BB))
         continue;
       while (processBlock(&BB)) // Thread all of the branches we can over BB.
         Changed = true;
 
       // Jump threading may have introduced redundant debug values into BB
       // which should be removed.
       if (Changed)

llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll

 ; CHECK-LABEL: entry:
 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %a' is: overdefined
 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %length' is: overdefined
   br label %loop
 
 ; CHECK-LABEL: backedge:
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %a' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %length' is: overdefined
-; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, 400>
-; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<399, 400>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, -2147483648>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<399, 2147483647>
 ; CHECK-NEXT:  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
-; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, 401>
-; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, 401>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, -2147483648>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, -2147483648>
 ; CHECK-NEXT:  %iv.next = add nsw i32 %iv, 1
 ; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%exit' is: constantrange<0, -1>
 ; CHECK-NEXT:  %cont = icmp slt i32 %iv.next, 400
 ; CHECK-NOT: loop
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %cnd = icmp sge i32 %iv, 0

llvm/test/Transforms/CallSiteSplitting/callsite-split.ll

 ; RUN: opt < %s -callsite-splitting -inline -instcombine -jump-threading -S | FileCheck %s
 ; RUN: opt < %s  -passes='function(callsite-splitting),cgscc(inline),function(instcombine,jump-threading)' -S | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-linaro-linux-gnueabi"
 
 %struct.bitmap = type { i32, %struct.bitmap* }
 
 ;CHECK-LABEL: @caller
 ;CHECK-LABEL: Top.split:
 ;CHECK: call void @callee(%struct.bitmap* null, %struct.bitmap* null, %struct.bitmap* %b_elt, i1 false)
 ;CHECK-LABEL: NextCond:
-;CHECK: br {{.*}} label %callee.exit
-;CHECK-LABEL: callee.exit:
-;CHECK: call void @dummy2(%struct.bitmap* %a_elt)
+;CHECK: br {{.*}} label %Cond.i
+;CHECK-LABEL: Cond.i:
+;CHECK-NEXT: call void @dummy2(%struct.bitmap* %a_elt)
 
 define void @caller(i1 %c, %struct.bitmap* %a_elt, %struct.bitmap* %b_elt) {
 entry:
   br label %Top
 
 Top:
   %tobool1 = icmp eq %struct.bitmap* %a_elt, null
   br i1 %tobool1, label %CallSiteBB, label %NextCond

llvm/test/Transforms/JumpThreading/PR33357-lvi-recursion.ll

 ; RUN: opt -S -jump-threading -verify -o - %s | FileCheck %s
+; This test checks that we dont infinitely recurse when a
+; binary operator references itself.
 @a = external global i16, align 1
 
 ; CHECK-LABEL: f
-; CHECK: bb6:
-; CHECK: bb2:
-; CHECK: bb3:
-; CHECK-NOT: bb0:
-; CHECK-NOT: bb1:
-; CHECK-NOT: bb4:
-; CHECK-NOT: bb5:
+; CHECK: [[OP:%.*]] = and i1 [[OP]], undef
 define void @f(i32 %p1) {
 bb0:
   %0 = icmp eq i32 %p1, 0
   br i1 undef, label %bb6, label %bb1
 
 bb1:
   br label %bb2
 

llvm/test/Transforms/JumpThreading/implied-cond.ll

right:
   %t = phi i32 [ 1, %left ], [ 2, %entry ], [ 3, %cont ]
   call void @side_effect(i32 %t)
   ret void
 }
 
 ; A s<= B implies A s> B is false.
 ; CHECK-LABEL: @test3(
 ; CHECK: entry:
-; CHECK: br i1 %cmp, label %if.end, label %if.end3
+; CHECK: br i1 %cmp, label %if.then, label %if.end3
 ; CHECK-NOT: br i1 %cmp1, label %if.then2, label %if.end
 ; CHECK-NOT: call void @side_effect(i32 0)
 ; CHECK: br label %if.end3
 ; CHECK: ret void
 
 define void @test3(i32 %a, i32 %b) {
 entry:
   %cmp = icmp sle i32 %a, %b

llvm/test/Transforms/JumpThreading/lvi-tristate.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -jump-threading -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S < %s | FileCheck %s
 declare void @ham()
 
 define void @hoge() {
 ; CHECK-LABEL: @hoge(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP:%.*]] = and i32 undef, 1073741823
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[TMP]], 5
-; CHECK-NEXT:    br i1 [[COND]], label [[BB10:%.*]], label [[BB13:%.*]]
-; CHECK:       bb10:
+; CHECK-NEXT:    br i1 [[COND]], label [[BB7_THREAD:%.*]], label [[BB13:%.*]]
+; CHECK:       bb7.thread:
 ; CHECK-NEXT:    tail call void @ham()
 ; CHECK-NEXT:    br label [[BB13]]
 ; CHECK:       bb13:
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %tmp = and i32 undef, 1073741823
   %tmp1 = icmp eq i32 %tmp, 2

llvm/test/Transforms/JumpThreading/pr22086.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -jump-threading < %s | FileCheck %s
 
 
-; CHECK-LABEL: @f(
-; CHECK-LABEL: entry:
-; CHECK-NEXT:  br label %[[loop:.*]]
-; CHECK:       [[loop]]:
-; CHECK-NEXT:  br label %[[loop]]
-
 define void @f() {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOR_RHS:%.*]]
+; CHECK:       lor.rhs:
+; CHECK-NEXT:    [[G_1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 0, [[LOR_RHS]] ]
+; CHECK-NEXT:    [[SEXT:%.*]] = shl i32 [[G_1]], 16
+; CHECK-NEXT:    [[CONV20:%.*]] = ashr exact i32 [[SEXT]], 16
+; CHECK-NEXT:    br label [[LOR_RHS]]
+;
 entry:
   br label %for.cond1
 
 if.end16:
   %phi1 = phi i32 [ undef, %for.cond1 ]
   %g.3 = phi i32 [ %g.1, %for.cond1 ]
   %sext = shl i32 %g.3, 16
   %conv20 = ashr exact i32 %sext, 16

llvm/test/Transforms/JumpThreading/pr36133.ll

 ; RUN: opt -jump-threading -S < %s | FileCheck %s
 @global = external global i8*, align 8
 
 define i32 @foo(i32 %arg) {
 ; CHECK-LABEL: @foo
 ; CHECK-LABEL: bb:
 ; CHECK: icmp eq
-; CHECK-NEXT: br i1 %tmp1, label %bb7, label %bb7
+; CHECK-NEXT: br i1 %tmp1, label %bb7, label %bb2
 bb:
   %tmp = load i8*, i8** @global, align 8
   %tmp1 = icmp eq i8* %tmp, null
   br i1 %tmp1, label %bb3, label %bb2
 
-; CHECK-NOT: bb2:
+; CHECK: bb2:
+; CHECK-NEXT: br label %bb7
 bb2:
   br label %bb3
 
 ; CHECK-NOT: bb3:
 bb3:
   %tmp4 = phi i8 [ 1, %bb2 ], [ 0, %bb ]
   %tmp5 = icmp eq i8 %tmp4, 0
   br i1 %tmp5, label %bb7, label %bb6

llvm/test/Transforms/JumpThreading/pr40992-indirectbr-folding.ll

 ; RUN: opt -S < %s -jump-threading | FileCheck %s
 
-; PR40992: Do not incorrectly fold %bb5 into an unconditional br to %bb7.
+; PR40992: Do not incorrectly fold %bb5 into an unconditional br to %bb7, bb6 is fine.
 ;          Also verify we correctly thread %bb1 -> %bb7 when %c is false.
 
 define i32 @jtbr(i1 %v1, i1 %v2, i1 %v3) {
 ; CHECK: bb0:
 bb0:
   br label %bb1
 
 ; CHECK: bb1:
 ; CHECK-NEXT: and
 ; CHECK-NEXT: br i1 %c, label %bb2, label %bb7
 bb1:
   %c = and i1 %v1, %v2
   br i1 %c, label %bb2, label %bb5
 
 ; CHECK: bb2:
 ; CHECK-NEXT: select
-; CHECK-NEXT: indirectbr i8* %ba, [label %bb3, label %bb5]
+; CHECK-NEXT: indirectbr i8* %ba, [label %bb3, label %bb6]
 bb2:
   %ba = select i1 %v3, i8* blockaddress(@jtbr, %bb3), i8* blockaddress(@jtbr, %bb4)
   indirectbr i8* %ba, [label %bb3, label %bb4]
 
 ; CHECK: bb3:
 bb3:
   br label %bb1
 
 ; CHECK-NOT: bb4:
 bb4:
   br label %bb5
 
-; CHECK: bb5:
+; CHECK-NOT: bb5:
 bb5:
   br i1 %c, label %bb6, label %bb7
 
 ; CHECK: bb6:
 bb6:
   ret i32 0
 
 ; CHECK: bb7:
 bb7:
   ret i32 1
 }

llvm/test/Transforms/JumpThreading/pr46857-callbr.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -jump-threading -S | FileCheck %s
 
 define i1 @func(i1 %arg, i32 %arg1, i1 %arg2) {
 ; CHECK-LABEL: @func(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br i1 [[ARG:%.*]], label [[BB7:%.*]], label [[BB4:%.*]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    callbr void asm sideeffect "", "!i"()
-; CHECK-NEXT:    to label [[BB7_THR_COMM:%.*]] [label %bb7.thr_comm]
-; CHECK:       bb7.thr_comm:
+; CHECK-NEXT:    to label [[BB6:%.*]] [label %bb6]
+; CHECK:       bb6:
 ; CHECK-NEXT:    [[I91:%.*]] = xor i1 [[ARG2:%.*]], [[ARG]]
 ; CHECK-NEXT:    br i1 [[I91]], label [[BB11:%.*]], label [[BB11]]
 ; CHECK:       bb7:
 ; CHECK-NEXT:    [[I:%.*]] = icmp eq i32 [[ARG1:%.*]], 0
 ; CHECK-NEXT:    [[I9:%.*]] = xor i1 [[I]], [[ARG]]
 ; CHECK-NEXT:    br i1 [[I9]], label [[BB11]], label [[BB11]]
 ; CHECK:       bb11:
-; CHECK-NEXT:    [[I93:%.*]] = phi i1 [ [[I91]], [[BB7_THR_COMM]] ], [ [[I9]], [[BB7]] ], [ [[I91]], [[BB7_THR_COMM]] ], [ [[I9]], [[BB7]] ]
-; CHECK-NEXT:    ret i1 [[I93]]
+; CHECK-NEXT:    [[I92:%.*]] = phi i1 [ [[I91]], [[BB6]] ], [ [[I91]], [[BB6]] ], [ [[I9]], [[BB7]] ], [ [[I9]], [[BB7]] ]
+; CHECK-NEXT:    ret i1 [[I92]]
 ;
 bb:
   br i1 %arg, label %bb3, label %bb4
 
 bb3:
   %i = icmp eq i32 %arg1, 0
   br label %bb7
 

llvm/test/Transforms/JumpThreading/select.ll

 
 }
 
 define i32 @unfold5(i32 %u, i32 %v, i32 %w, i32 %x, i32 %y, i32 %z, i32 %j) nounwind {
 ; CHECK-LABEL: @unfold5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ADD3:%.*]] = add nsw i32 [[J:%.*]], 2
 ; CHECK-NEXT:    [[CMP_I:%.*]] = icmp slt i32 [[U:%.*]], [[V:%.*]]
-; CHECK-NEXT:    br i1 [[CMP_I]], label [[DOTEXIT:%.*]], label [[COND_FALSE_I:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_I]], label [[DOTEXIT_THREAD:%.*]], label [[COND_FALSE_I:%.*]]
 ; CHECK:       cond.false.i:
 ; CHECK-NEXT:    [[CMP4_I:%.*]] = icmp sgt i32 [[U]], [[V]]
-; CHECK-NEXT:    br i1 [[CMP4_I]], label [[DOTEXIT]], label [[COND_FALSE_6_I:%.*]]
+; CHECK-NEXT:    br i1 [[CMP4_I]], label [[DOTEXIT_THREAD]], label [[COND_FALSE_6_I:%.*]]
 ; CHECK:       cond.false.6.i:
 ; CHECK-NEXT:    [[CMP8_I:%.*]] = icmp slt i32 [[W:%.*]], [[X:%.*]]
-; CHECK-NEXT:    br i1 [[CMP8_I]], label [[DOTEXIT]], label [[COND_FALSE_10_I:%.*]]
+; CHECK-NEXT:    br i1 [[CMP8_I]], label [[DOTEXIT_THREAD]], label [[COND_FALSE_10_I:%.*]]
 ; CHECK:       cond.false.10.i:
 ; CHECK-NEXT:    [[CMP13_I:%.*]] = icmp sgt i32 [[W]], [[X]]
-; CHECK-NEXT:    br i1 [[CMP13_I]], label [[DOTEXIT]], label [[COND_FALSE_15_I:%.*]]
+; CHECK-NEXT:    br i1 [[CMP13_I]], label [[DOTEXIT_THREAD]], label [[COND_FALSE_15_I:%.*]]
 ; CHECK:       cond.false.15.i:
 ; CHECK-NEXT:    [[CMP19_I:%.*]] = icmp sge i32 [[Y:%.*]], [[Z:%.*]]
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP19_I]] to i32
-; CHECK-NEXT:    br label [[DOTEXIT]]
-; CHECK:       .exit:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[J]], [[COND_FALSE_10_I]] ], [ [[CONV]], [[COND_FALSE_15_I]] ], [ 1, [[COND_FALSE_6_I]] ], [ 3, [[COND_FALSE_I]] ], [ 2, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br label [[DOTEXIT_THREAD]]
+; CHECK:       .exit.thread:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[CONV]], [[COND_FALSE_15_I]] ], [ 1, [[COND_FALSE_6_I]] ], [ 3, [[COND_FALSE_I]] ], [ 2, [[ENTRY:%.*]] ], [ [[J]], [[COND_FALSE_10_I]] ]
 ; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %add3 = add nsw i32 %j, 2
   %cmp.i = icmp slt i32 %u, %v
   br i1 %cmp.i, label %.exit, label %cond.false.i
 
 cond.false.i:                                     ; preds = %entry

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

check_1:
   %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 edge:
-; CHECK: check_2.thread:
-; CHECK-NEXT: call void @bar()
-; CHECK-NEXT: br label %latch
 
 check_2:
   %cond2 = icmp eq i32 %v, 2
   br i1 %cond2, label %eq_2, label %check_3
+; CHECK: check_2:
 ; No metadata:
-; CHECK: br i1 %cond2, label %eq_2, label %check_3{{$}}
+; CHECK: br i1 %cond2, label %check_3.thread, label %check_3{{$}}
+
+; Verify the new edge:
+; CHECK: check_2.thread:
+; CHECK-NEXT: call void @bar()
+; CHECK-NEXT: br label %latch
 
 eq_2:
   call void @bar()
   br label %check_3
 ; Verify the new edge:
-; CHECK: eq_2:
+; CHECK: check_3.thread:
 ; CHECK-NEXT: call void @bar()
 ; CHECK-NEXT: br label %latch
 
 check_3:
   %condE = icmp eq i32 %v, 3
   br i1 %condE, label %exit, label %latch
 ; No metadata:
 ; CHECK: br i1 %condE, label %exit, label %latch{{$}}

llvm/test/Transforms/JumpThreading/thread-loads.ll

 ; as necessary in the predecessors. This is especially tricky because the same
 ; predecessor ends up with two entries in the PHI node and they must share
 ; a single cast.
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8** [[X:%.*]] to i32**
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32*, i32** [[TMP0]], align 8
 ; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i32* [[TMP1]] to i8*
-; CHECK-NEXT:    br i1 [[F:%.*]], label [[IF_END57:%.*]], label [[IF_END57]]
+; CHECK-NEXT:    br i1 [[F:%.*]], label [[IF_END57:%.*]], label [[IF_THEN56:%.*]]
+; CHECK:       if.then56:
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP1]] to i8*
+; CHECK-NEXT:    br label [[IF_END57]]
 ; CHECK:       if.end57:
-; CHECK-NEXT:    [[TMP3:%.*]] = phi i8* [ [[TMP2]], [[ENTRY:%.*]] ], [ [[TMP2]], [[ENTRY]] ]
-; CHECK-NEXT:    [[TOBOOL59:%.*]] = icmp eq i8* [[TMP3]], null
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i8* [ [[TMP3]], [[IF_THEN56]] ], [ [[TMP2]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TOBOOL59:%.*]] = icmp eq i8* [[TMP4]], null
 ; CHECK-NEXT:    br i1 [[TOBOOL59]], label [[RETURN:%.*]], label [[IF_THEN60:%.*]]
 ; CHECK:       if.then60:
 ; CHECK-NEXT:    ret i32 42
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 13
 ;
 entry:
   %0 = bitcast i8** %x to i32**

 left_x:
   ret i32 20
 
 right_x:
   ret i32 10
 }
 
 
-; CHECK: [[RNG4]] = !{i32 0, i32 1}
 
 !0 = !{!3, !3, i64 0}
 !1 = !{!"omnipotent char", !2}
 !2 = !{!"Simple C/C++ TBAA"}
 !3 = !{!"int", !1}
 !4 = !{ i32 0, i32 1 }
 !5 = !{ i32 8, i32 10 }
 !6 = !{!6}
 !7 = !{!7, !6}
 !8 = !{!8, !6}
 !9 = !{!7}
 !10 = !{!8}

llvm/test/Transforms/JumpThreading/unreachable-loops.ll

 ; This gets into a state that could cause instruction simplify
 ; to hang - an insertelement instruction has itself as an operand.
 
 define void @PR48362() {
 ;
 ; CHECK-LABEL: @PR48362(
 ; CHECK-NEXT:  cleanup.cont1500:
 ; CHECK-NEXT:    unreachable
-; CHECK:       if.end1733:
-; CHECK-NEXT:    [[I82:%.*]] = load i32, i32* undef, align 1
-; CHECK-NEXT:    [[TOBOOL1731_NOT:%.*]] = icmp eq i32 [[I82]], 0
-; CHECK-NEXT:    br label [[IF_END1733:%.*]]
 ;
 cleanup1491:                                      ; preds = %for.body1140
   switch i32 0, label %cleanup2343.loopexit4 [
   i32 0, label %cleanup.cont1500
   i32 128, label %lbl_555.loopexit
   ]
 
 cleanup.cont1500:                                 ; preds = %cleanup1491