[Jump Threading] Convert conditional branches into unconditional branches using GVN results

[masakiarai]

Summary

processBBWithCommonDomCondition converts a conditional branch of BB
into an unconditional branch if possible, when the basic block BBa
dominates BB and both basic blocks have conditional branches under the
same condition.

BBa:

%cmp = ...
br i1 %cmp, label %LA1, label %LA2

...

BB:

...
br i1 %cmp, label %LD1, label %LD2

The condition to apply this optimization is that the predecessors of
BB is divided into the set S1 coming from LA1 and the set S2 coming
from LA2.
If S1(or S2) is empty, it rewrites the conditional branch to an
unconditional branch to LD2(or LD1).
If both S1 and S2 are not empty and BB can be copied, BB is copied for
S2, and each conditional branches in BB and the copied BB are
converted into unconditional branches for LD1 and LD2, respectively.

[rengolin]

Adding llvm-commits for wider audience

[brzycki]

Hello @masakiarai, my comments are inline.

I am also curious: have you run test-suite and make-check-llvm on this code? For test-suite I am curious about the SingleSource, MultiSource, and CTMark directories. The first two can help identify miscompiles or compiler crashes while last one can help identify compile-time performance regressions.

lib/Transforms/Scalar/JumpThreading.cpp

374–379

Running processBBWithCommonDomCondition at this location means the code can only ever catch this pattern once when the initial IR passed to JumpThreading contains it. If the pattern ever emerges in the IR from changes within the do { ... } while(); loop below it will not be detected.

376

This is expensive for large block counts of F. It would be better to update Unreachable as you alter the state of BBs within the new logic.

567

I think you can get the Level from DT using the getLevel() method without generating it recursively yourself.

595

This should probably return an enum similar to enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 }; Magic numbers make maintainability more difficult.

697

Why instantiate another instance of DT? The location where you call this code has DTU which you can pass in. For large F generating the DT is expensive. It's also a unique instance of DT that knows nothing about DTU->DT.

703

This feels like the code here is more of a function-level-pass-within-a-pass than an extension of JumpThreading. I have concerns the number of loops and recursive calls over the BBs of F will add to the overall compile time.

730

This code makes me nervous. On line 727 you call findBBWithCommonDomCondition(DT, ... but here you call conditionalToUnconditional(DTU, .... The JumpThreadingPass creates DTU with UpdateStrategy::Lazy. This means the calls to DTU->deleteEdgeRelaxed(...) in conditionalToUnconditional() and the calls to DT.dominates() in findBBWithCommonDomCondition() may lead to an inconsistent state.

744

Please explain the reasoning behind increasing BBDupThreshold

[masakiarai]

Thank you very much for your quick and detailed review.

I'm sorry that I incorrectly uploaded halfway differences.
The correct patch file, which includes 2 bug fixes, reflects some of your comments, but it does not reflect everything.
So, I reply to your comments before uploading it.

About test-suite, I run them using 'test-suite/cmake/caches/*'.

[masakiarai]

lib/Transforms/Scalar/JumpThreading.cpp

374–379

It is possible to place processBBWithCommonDomCondition call in the loop, but in reality, there was little effect.
In theory, I can create situations that are effective.
JumpThreading is executed multiple times, but since the first time is before GVN, the execution of processBBWithCommonDomCondition at that time has no meaning.

567

You are right.
visitBB is unnecessary.

595

You are right.
I will fix this.

697

The correct patch uses only DTU.

703

I do not think that I should create a new pass in the following reasons:
(1) The essential effect of this optimization is about branches.
(2) The most complicated process of my modification depends on JumpThreadingPass::ThreadEdge.

730

I understand your concerns.
The correct patch uses only DTU.

744

It is unnecessary to change BBDupThreshold here.
I have confirmed that increasing BBDupThreshold here increases the opportunity for some optimization about HPC applications.
However, to generate CFG like GCC(that is my immediate goal), I do not need to change the value.

[masakiarai]

I uploaded my patch with some fixes.

[brzycki]

In D57953#1395870, @masakiarai wrote:

I uploaded my patch with some fixes.

Thank you for the comments and re-upload @masakiarai. I will review the patch again either today or tomorrow.

[brzycki]

Hello @masakiarai, the new patch looks better, thank you. My updated comments are inline.

lib/Transforms/Scalar/JumpThreading.cpp

374–379

Understood. I'm still thinking there are cases your testing didn't encounter that emerge from other JT optimizations. I suppose real-world usage will discover them, if at all.

Also, I'd really prefer if processBBWithCommonDomCondition() marked BBs unreachable as it changed F instead of coming back and doing yet-another loop over all the BBs. For large F these multiple iterations over all the blocks adds non-trivial deltas of compile-time.

680

Does this need to be deleteEdgeRelaxed()? If at all possible please don't use this variant of the DTU method. There's actually work underway to try and deprecate/remove it. (See D58170 and D57881 if you're interested)

703

Understood. I made the comment because most of the optimizations in JT rely on analysis at the BB level but this new enhancement works at the F level. It's a bit of a departure for JT and I'm not sure if the community as a whole is interested in going this direction. I don't think I alone can make that decision...

720

Please no magic numbers.

724

Please no magic numbers.

729

This function is fairly complex. I know I'd appreciate a few more comments describing the logic and why certain checks are happening.

[sebpop]

This seems to be a useful transform that is not yet covered by the current implementation of jump-threading.
I think GCC calls it control dependence DCE.
Please run and report performance numbers on the testsuite and other benchmarks that you have access to.

lib/Transforms/Scalar/JumpThreading.cpp

374

You are missing a flag to enable/disable this transform.

599

Please remove the else after an if-then that returns. Here and everywhere else in your patch.
https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return
Please review all the coding rules and apply to your patch.

703

I am also inclined to say that this does not belong to jump-threading: the analysis relies on gvn to have executed and replaced all equivalent %cmp values. Moving this code to a new pass would allow more flexibility to schedule the pass after gvn.

718

Please use continue; that tells the reader that there are no more statements to be executed in this loop body.

719

no else needed after a continue;

722

same here: continue and remove else

724

You could replace the arguments of conditionalToUnconditional(..., 0, 1) with a single param enum {KeepThen, KeepElse};

732

As the code generation relies on threadEdge, you could factor it out from this file and make it usable from other passes.

test/Transforms/JumpThreading/gvn-dom-cb.ll

16

Please add a comment that explains what this test is checking for. Here and for all the CHECK/CHECK-NOT below.

For this particular case the comment could be:
"Check that jump-threading is able to infer the value of %cmp used at the end of basic block if.end and thus that the IR after jump-threading contains only one conditional branch based on %cmp in basic block entry."

Maybe you can also CHECK-NOT: label if.else4 and mention in the comment that the basic block becomes unreachable and is eliminated.

58

You could mention in the comment that explains what this testcase checks for that "This testcase only differs from check1 by one annotation noduplicate on the call to show3, this prevents jump-threading because ... such and such."

[brzycki]

lib/Transforms/Scalar/JumpThreading.cpp

732

+1. A suitable location for this would be llvm/lib/Transforms/Utils/Local.cpp.

[xbolva00]

Re-ping

[masakiarai]

I'm sorry to stagnate this for a very long time.
According to the reviewer's comments, I am preparing this as a new optimization pass as 'Control Dependent DCE'.
With enhancements and additional test programs, I will submit a new review request.

[fhahn]

In D57953#1796475, @masakiarai wrote:

I'm sorry to stagnate this for a very long time.
According to the reviewer's comments, I am preparing this as a new optimization pass as 'Control Dependent DCE'.
With enhancements and additional test programs, I will submit a new review request.

I’ll take a closer look in a bit, but I think there might be a different approach using predicate info to solve this problem relatively easily. I’ll see if I can put something together. In general it should be enough to just simplify the condition to true and let other passes do the cCFG cleanup

[fhahn]

(marking as changes requested to indicate that there's an outstanding comment)

[masakiarai]

I'm sorry for the long suspension due to various changes in my working environment(my job description, email address, etc).
I implemented this as a new optimization pass, so I will upload it.
I'm thinking of getting a new Phabricator review number and linking it from this comment section.
Is this a reasonable procedure?

[rengolin]

In D57953#2289359, @masakiarai wrote:

I implemented this as a new optimization pass, so I will upload it.
I'm thinking of getting a new Phabricator review number and linking it from this comment section.
Is this a reasonable procedure?

If the implementation is completely different, they I guess it would make sense to start fresh. If you do, please close this one with a comment, pointing to the new review.

You should also refer back to this review, in the new one, in case people want to read the previous context.

Also, copy all people that interacted with this review and mention it's a rework, so they continue reviewing the "same" work.

[masakiarai]

Thank you very much for your advice.

Since the files to be added and modified in the new version are
significantly different, I got the following new Differential Revision.

[ControlDependentDCE] Add Control Dependent DCE pass
https://reviews.llvm.org/D88293

If there are no problems, I will close this Differential Revision.

[rengolin]

No problems, feel free to close, thanks!

[masakiarai]

I closed this revision as the following revision will reconstruct this anew.

[ControlDependentDCE] Add Control Dependent DCE pass
https://reviews.llvm.org/D88293

include/llvm/Transforms/Scalar/JumpThreading.h

public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   void releaseMemory() {
     BFI.reset();
     BPI.reset();
   }
 
   void FindLoopHeaders(Function &F);
+  bool processBBWithCommonDomCondition(Function &F,
+                                       SmallPtrSetImpl<BasicBlock *> &Unreachable);
   bool ProcessBlock(BasicBlock *BB);
   bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
                   BasicBlock *SuccBB);
   bool DuplicateCondBranchOnPHIIntoPred(
       BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
 
   bool ComputeValueKnownInPredecessorsImpl(
       Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,

lib/Transforms/Scalar/JumpThreading.cpp

 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Jump Threading pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/JumpThreading.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
   assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed.");
   DominatorTree &DT = DTU->getDomTree();
   for (auto &BB : F)
     if (!DT.isReachableFromEntry(&BB))
       Unreachable.insert(&BB);
 
   FindLoopHeaders(F);
 
-  bool EverChanged = false;
+  bool EverChanged = processBBWithCommonDomCondition(F, Unreachable);
+  DTU->getDomTree();
+  for (auto &BB : F)
+    if (!Unreachable.count(&BB) && !DT.isReachableFromEntry(&BB))
+      Unreachable.insert(&BB);
+
   bool Changed;
   do {
     Changed = false;
     for (auto &BB : F) {
       if (Unreachable.count(&BB))
         continue;
       while (ProcessBlock(&BB)) // Thread all of the branches we can over BB.
         Changed = true;

 void JumpThreadingPass::FindLoopHeaders(Function &F) {
   SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges;
   FindFunctionBackedges(F, Edges);
 
   for (const auto &Edge : Edges)
     LoopHeaders.insert(Edge.second);
 }
 
+/// collectReachableBBSet - Create a set of reachable basic blocks from BB in
+/// the reverse direction of the control flow as TouchBBSet.
+/// When reaching BBa, search is stopped there.
+static void collectReachableBBSet(BasicBlock *BB, BasicBlock *BBa,
+                                  DenseSet<const BasicBlock*>& TouchBBSet) {
+  if (TouchBBSet.count(BB))
+    return;
+  TouchBBSet.insert(BB);
+  for (BasicBlock *Pred : predecessors(BB)) {
+    if (Pred != BBa) {
+      collectReachableBBSet(Pred, BBa, TouchBBSet);
+    }
+  }
+}
+
+/// findPredSourceEdge - Classify the predecessor Pred of BB into the following
+/// categories:
+enum PredOrigin : unsigned {
+  PredFromSuccBB0, // from SuccBB0
+  PredFromSuccBB1, // from SuccBB1
+  PredFromBothSuccBB0AndSuccBB1, // from both SuccBB0 and SuccBB1
+  PredUnreachable, // unreachable
+};
+/// BBa is the basic block which dominates BB.
+/// Both SuccBB0 and SuccBB1 are the successors of BBa.
+static enum PredOrigin findPredSourceEdge(BasicBlock *BBa, BasicBlock *BB,
+                                          BasicBlock *Pred, BasicBlock *SuccBB0,
+                                          BasicBlock *SuccBB1) {
+  if (Pred == BBa) {
+    if (BB == SuccBB0)
+      return PredFromSuccBB0;
+    else if (BB == SuccBB1)
+      return PredFromSuccBB1;
+    else
+      llvm_unreachable("This cannot happen!");
+  }
+  DenseSet<const BasicBlock*> TouchBBSet;
+  collectReachableBBSet(Pred, BBa, TouchBBSet);
+  bool ReachSuccBB0 = TouchBBSet.count(SuccBB0);
+  bool ReachSuccBB1 = TouchBBSet.count(SuccBB1);
+  if (ReachSuccBB0 && ReachSuccBB1)
+    return PredFromBothSuccBB0AndSuccBB1;
+  else if (ReachSuccBB0)
+    return PredFromSuccBB0;
+  else if (ReachSuccBB1)
+    return PredFromSuccBB1;
+  else
+    return PredUnreachable;
+}
+
+/// findBBWithCommonDomCondition - Detect BBa that dominates BB and has the same
+/// condition code C as BB. BBList is sorted in descending order of levels on
+/// the dominating tree with the condition code C. The position of BB in BBList
+/// is StartIdx - 1.
+/// If there was BBa, then return it and also the set of predecessor of BB is
+/// divided into Preds0 and Preds1.
+static BasicBlock*
+findBBWithCommonDomCondition(DominatorTree &DT,
+                             SmallVectorImpl<BasicBlock *> &BBList,
+                             BasicBlock *BB, unsigned StartIdx,
+                             SmallVectorImpl<BasicBlock *>& Preds0,
+                             SmallVectorImpl<BasicBlock *>& Preds1) {
+  size_t Size = BBList.size();
+  for (unsigned Idx = StartIdx; Idx < Size; Idx++) {
+    BasicBlock *BBa = BBList[Idx];
+    if (DT.dominates(BBa, BB)) {
+      BranchInst *CondBr = dyn_cast<BranchInst>(BBa->getTerminator());
+      BasicBlock *SuccBB0 = CondBr->getSuccessor(0);
+      BasicBlock *SuccBB1 = CondBr->getSuccessor(1);
+      if (SuccBB0 != SuccBB1 && BBa != SuccBB0 && BBa != SuccBB1) {
+        SmallVector<BasicBlock *, 2> Preds(predecessors(BB));
+        SmallVector<BasicBlock *, 4> PredsBoth;
+        for (auto Pred : Preds) {
+          unsigned Src = PredFromBothSuccBB0AndSuccBB1;
+          if (Pred == BBa) {
+            if (BB == SuccBB0)
+              Src = PredFromSuccBB0;
+            else if (BB == SuccBB1)
+              Src = PredFromSuccBB1;
+            else
+              llvm_unreachable("This cannot happen!");
+          } else if (Pred == BB)
+            Src = PredFromBothSuccBB0AndSuccBB1;
+          else
+            Src = findPredSourceEdge(BBa, BB, Pred, SuccBB0, SuccBB1);
+          switch (Src) {
+          case PredFromSuccBB0:
+            Preds0.push_back(Pred);
+            break;
+          case PredFromSuccBB1:
+            Preds1.push_back(Pred);
+            break;
+          case PredFromBothSuccBB0AndSuccBB1:
+            PredsBoth.push_back(Pred);
+            break;
+          case PredUnreachable:
+            break;
+          default:
+            llvm_unreachable("This cannot happen!");
+          }
+        }
+        if (PredsBoth.empty()) {
+          return BBa;
+        } else {
+          return nullptr;
+        }
+      }
+    }
+  }
+  return nullptr;
+}
+
+/// conditionalToUnconditional - Change BBd to the basic block of unconditional
+/// branching to ToKeep.
+static void conditionalToUnconditional(DomTreeUpdater *DTU, BasicBlock *BBd,
+                                       unsigned ToKeep, unsigned ToRemove) {
+  BranchInst *CondBr = dyn_cast<BranchInst>(BBd->getTerminator());
+  BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove);
+  BasicBlock *ToKeepSucc = CondBr->getSuccessor(ToKeep);
+  ToRemoveSucc->removePredecessor(BBd);
+  BranchInst *NewBI = BranchInst::Create(ToKeepSucc, CondBr);
+  NewBI->setDebugLoc(ToKeepSucc->getTerminator()->getDebugLoc());
+  CondBr->eraseFromParent();
+  DTU->deleteEdgeRelaxed(BBd, ToRemoveSucc);
+}
+
+/// processBBWithCommonDomCondition - Convert conditional branches into
+/// unconditional branches using common dominator conditions.
+bool JumpThreadingPass::processBBWithCommonDomCondition(
+    Function &F, SmallPtrSetImpl<BasicBlock *> &Unreachable) {
+  DominatorTree &DT = DTU->getDomTree();
+  MapVector<Value *, SmallVector<BasicBlock *, 4>> CtoBBList;
+  for (auto &BB : F) {
+    if (Unreachable.count(&BB))
+      continue;
+    Instruction *Terminator = BB.getTerminator();
+    if (BranchInst *BI = dyn_cast<BranchInst>(Terminator)) {
+      if (BI->isConditional()) {
+        Value *Condition = BI->getCondition();
+        CtoBBList[Condition].push_back(&BB);
+      }
+    }
+  }
+
+  unsigned UB = 0;
+  unsigned DUP = 0;
+  bool Changed = false;
+  for (auto &Pair : CtoBBList) {
+    SmallVectorImpl<BasicBlock *> &BBList = Pair.second;
+    if (BBList.size() > 1) {
+      std::stable_sort(BBList.begin(), BBList.end(),
+                       [&DT](BasicBlock* X, BasicBlock* Y) {
+                         return DT.getNode(X)->getLevel() > DT.getNode(Y)->getLevel();
+                       });
+      unsigned Idx = 0;
+      for (auto *BB : BBList) {
+        SmallVector<BasicBlock *, 4> Preds0;
+        SmallVector<BasicBlock *, 4> Preds1;
+        if (findBBWithCommonDomCondition(DT, BBList, BB, Idx + 1,
+                                         Preds0, Preds1)) {
+          if (Preds0.size() == 0 && Preds1.size() == 0)
+            ;
+          else if (Preds0.size() == 0) {
+            conditionalToUnconditional(DTU, BB, 1, 0);
+            UB++;
+            Changed = true;
+          } else if (Preds1.size() == 0) {
+            conditionalToUnconditional(DTU, BB, 0, 1);
+            UB++;
+            Changed = true;
+          } else if (!LoopHeaders.count(BB)) {
+            BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
+            BasicBlock *SuccBB0 = CondBr->getSuccessor(0);
+            BasicBlock *SuccBB1 = CondBr->getSuccessor(1);
+            if (SuccBB0 != SuccBB1 && SuccBB0 != BB && SuccBB1 != BB) {
+              if (ThreadEdge(BB, Preds1, SuccBB1)) {
+                SuccBB1->removePredecessor(BB);
+                BranchInst *NewBI = BranchInst::Create(SuccBB0, CondBr);
+                NewBI->setDebugLoc(SuccBB0->getTerminator()->getDebugLoc());
+                CondBr->eraseFromParent();
+                DTU->deleteEdgeRelaxed(BB, SuccBB1);
+                DUP++;
+                Changed = true;
+              }
+            }
+          }
+        }
+        Idx++;
+      }
+    }
+  }
+  LLVM_DEBUG(dbgs() << "JT: Processing BB with common dominator condition: #UB="
+                    << UB << " #DUP=" << DUP << "\n");
+  return Changed;
+}
+
 /// getKnownConstant - Helper method to determine if we can thread over a
 /// terminator with the given value as its condition, and if so what value to
 /// use for that. What kind of value this is depends on whether we want an
 /// integer or a block address, but an undef is always accepted.
 /// Returns null if Val is null or not an appropriate constant.
 static Constant *getKnownConstant(Value *Val, ConstantPreference Preference) {
   if (!Val)
     return nullptr;

test/Transforms/JumpThreading/gvn-dom-cb.ll

+; RUN: opt -jump-threading -S < %s | FileCheck %s
+
+declare void @show1()
+declare void @show2()
+declare void @show3()
+declare void @show4()
+declare void @show5()
+declare void @show6()
+declare void @show7()
+
+@E = external global i32, align 4
+
+define void @check1(i32 %x, i32 %y) {
+; CHECK-LABEL: @check1(
+; CHECK: br i1 %cmp,
+; CHECK-NOT: br i1 %cmp,
+entry:
+  %cmp = icmp slt i32 %x, %y
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %if.then
+  %i.0 = phi i32 [ 0, %if.then ], [ %inc, %do.body ]
+  call void () @show1()
+  %inc = add nsw i32 %i.0, 1
+  %0 = load i32, i32* @E, align 4
+  %cmp1 = icmp slt i32 %inc, %0
+  br i1 %cmp1, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.body
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  call void () @show2()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %do.end
+  call void () @show3()
+  br i1 %cmp, label %if.then3, label %if.else4
+
+if.then3:                                         ; preds = %if.end
+  call void () @show4()
+  br label %if.end5
+
+if.else4:                                         ; preds = %if.end
+  call void () @show5()
+  br label %if.end5
+
+if.end5:                                          ; preds = %if.else4, %if.then3
+  ret void
+}
+
+define void @check2(i32 %x, i32 %y) {
+; CHECK-LABEL: @check2(
+; CHECK: br i1 %cmp,
+; CHECK: br i1 %cmp,
+entry:
+  %cmp = icmp slt i32 %x, %y
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %if.then
+  %i.0 = phi i32 [ 0, %if.then ], [ %inc, %do.body ]
+  call void () @show1()
+  %inc = add nsw i32 %i.0, 1
+  %0 = load i32, i32* @E, align 4
+  %cmp1 = icmp slt i32 %inc, %0
+  br i1 %cmp1, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.body
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  call void () @show2()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %do.end
+  call void () @show3() noduplicate
+  br i1 %cmp, label %if.then3, label %if.else4
+
+if.then3:                                         ; preds = %if.end
+  call void () @show4()
+  br label %if.end5
+
+if.else4:                                         ; preds = %if.end
+  call void () @show5()
+  br label %if.end5
+
+if.end5:                                          ; preds = %if.else4, %if.then3
+  ret void
+}
+
+define void @check3(i32 %x, i32 %y) {
+; CHECK-LABEL: @check3(
+; CHECK: br i1 %cmp,
+; CHECK-NOT: br i1 %cmp,
+entry:
+  %cmp = icmp slt i32 %x, %y
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %if.then
+  %i.0 = phi i32 [ 0, %if.then ], [ %inc, %do.body ]
+  call void () @show1()
+  %inc = add nsw i32 %i.0, 1
+  %0 = load i32, i32* @E, align 4
+  %cmp1 = icmp slt i32 %inc, %0
+  br i1 %cmp1, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.body
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  call void () @show2()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %do.end
+  call void () @show3()
+  br i1 %cmp, label %if.then3, label %if.else10
+
+if.then3:                                         ; preds = %if.end
+  br label %do.body5
+
+do.body5:                                         ; preds = %do.body5, %if.then3
+  %i4.0 = phi i32 [ 0, %if.then3 ], [ %inc6, %do.body5 ]
+  call void () @show4()
+  %inc6 = add nsw i32 %i4.0, 1
+  %1 = load i32, i32* @E, align 4
+  %cmp8 = icmp slt i32 %inc6, %1
+  br i1 %cmp8, label %do.body5, label %do.end9
+
+do.end9:                                          ; preds = %do.body5
+  br label %if.end11
+
+if.else10:                                        ; preds = %if.end
+  call void () @show5()
+  br label %if.end11
+
+if.end11:                                         ; preds = %if.else10, %do.end9
+  br i1 %cmp, label %if.then13, label %if.else14
+
+if.then13:                                        ; preds = %if.end11
+  call void () @show6()
+  br label %if.end15
+
+if.else14:                                        ; preds = %if.end11
+  call void () @show7()
+  br label %if.end15
+
+if.end15:                                         ; preds = %if.else14, %if.then13
+  ret void
+}
+
+define void @check4(i32 %x, i32 %y) {
+; CHECK-LABEL: @check4(
+; CHECK: br i1 %cmp,
+; CHECK: br i1 %cmp,
+; CHECK-NOT: br i1 %cmp,
+entry:
+  %cmp = icmp slt i32 %x, %y
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %if.then
+  %i.0 = phi i32 [ 0, %if.then ], [ %inc, %do.body ]
+  call void () @show1()
+  %inc = add nsw i32 %i.0, 1
+  %0 = load i32, i32* @E, align 4
+  %cmp1 = icmp slt i32 %inc, %0
+  br i1 %cmp1, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.body
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  call void () @show2()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %do.end
+  call void () @show3() noduplicate
+  br i1 %cmp, label %if.then3, label %if.else10
+
+if.then3:                                         ; preds = %if.end
+  br label %do.body5
+
+do.body5:                                         ; preds = %do.body5, %if.then3
+  %i4.0 = phi i32 [ 0, %if.then3 ], [ %inc6, %do.body5 ]
+  call void () @show4()
+  %inc6 = add nsw i32 %i4.0, 1
+  %1 = load i32, i32* @E, align 4
+  %cmp8 = icmp slt i32 %inc6, %1
+  br i1 %cmp8, label %do.body5, label %do.end9
+
+do.end9:                                          ; preds = %do.body5
+  br label %if.end11
+
+if.else10:                                        ; preds = %if.end
+  call void () @show5()
+  br label %if.end11
+
+if.end11:                                         ; preds = %if.else10, %do.end9
+  br i1 %cmp, label %if.then13, label %if.else14
+
+if.then13:                                        ; preds = %if.end11
+  call void () @show6()
+  br label %if.end15
+
+if.else14:                                        ; preds = %if.end11
+  call void () @show7()
+  br label %if.end15
+
+if.end15:                                         ; preds = %if.else14, %if.then13
+  ret void
+}

test/Transforms/JumpThreading/gvn-dom-ub.ll

+; RUN: opt -jump-threading -S < %s | FileCheck %s
+
+declare void @show1()
+declare void @show2()
+declare void @show3()
+declare void @show4()
+
+@c = external global i32, align 4
+
+define void @check1(i32 %x, i32 %y) {
+; CHECK-LABEL: @check1(
+; CHECK: br i1 %cmp,
+; CHECK-NOT: br i1 %cmp,
+entry:
+  %cmp = icmp slt i32 %x, %y
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:                                          ; preds = %entry
+  call void () @show1()
+  br i1 %cmp, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %if.then
+  call void () @show2()
+  br label %if.end
+
+if.else:                                          ; preds = %if.then
+  call void () @show3()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then2
+  br label %if.end3
+
+if.end3:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+define void @check2(i32 %x, i32 %y) {
+; CHECK-LABEL: @check2(
+; CHECK: br i1 %cmp,
+; CHECK-NOT: br i1 %cmp,
+entry:
+  %cmp = icmp slt i32 %x, %y
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:                                          ; preds = %entry
+  call void () @show1()
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %if.then
+  call void () @show2()
+  br i1 %cmp, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %do.body
+  call void () @show3()
+  br label %if.end
+
+if.else:                                          ; preds = %do.body
+  call void () @show4()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then2
+  %0 = load i32, i32* @c, align 4
+  %dec = add nsw i32 %0, -1
+  store i32 %dec, i32* @c, align 4
+  br label %do.cond
+
+do.cond:                                          ; preds = %if.end
+  %1 = load i32, i32* @c, align 4
+  %tobool = icmp ne i32 %1, 0
+  br i1 %tobool, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.cond
+  br label %if.end3
+
+if.end3:                                          ; preds = %do.end, %entry
+  ret void
+}
+
+define void @check3(i32 %x, i32 %y) {
+; CHECK-LABEL: @check3(
+; CHECK: br i1 %cmp,
+; CHECK-NOT: br i1 %cmp,
+entry:
+  %cmp = icmp slt i32 %x, %y
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:                                          ; preds = %entry
+  call void () @show1()
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %if.then
+  br i1 %cmp, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %do.body
+  call void () @show2()
+  br label %if.end
+
+if.else:                                          ; preds = %do.body
+  call void () @show3()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then2
+  %0 = load i32, i32* @c, align 4
+  %dec = add nsw i32 %0, -1
+  store i32 %dec, i32* @c, align 4
+  br label %do.cond
+
+do.cond:                                          ; preds = %if.end
+  %1 = load i32, i32* @c, align 4
+  %tobool = icmp ne i32 %1, 0
+  br i1 %tobool, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.cond
+  br label %if.end3
+
+if.end3:                                          ; preds = %do.end, %entry
+  ret void
+}