[DFAJumpThreading] Relax analysis to handle unpredictable initial values

[alexey.zhikhar]

Summary

Responding to a feature request from the Rust community:

https://github.com/rust-lang/rust/issues/80630

void foo(X) {
  for (...)
    switch (X)
      case A
        X = B
      case B
        X = C
}

Even though the initial switch value is non-constant, the switch statement can still be threaded:
the initial value will hit the switch statement but the rest of the state changes will proceed by
jumping unconditionally.

The early predictability check is relaxed to allow unpredictable values anywhere, but later,
after the paths through the switch statement have been enumerated, no non-constant state
values are allowed along the paths. Any state value not along a path will be an initial switch value,
which can be safely ignored.

[alexey.zhikhar]

Code size increase is very small.

Tests: 3887
Metric: size..text

Program                                        results-base results-init diff

test-suite...TimberWolfMC/timberwolfmc.test   215116.00    216284.00     0.5%
test-suite...lications/ClamAV/clamscan.test   485520.00    485968.00     0.1%
test-suite...marks/7zip/7zip-benchmark.test   895972.00    896396.00     0.0%
test-suite...lications/sqlite3/sqlite3.test   464044.00    464052.00     0.0%
test-suite...te/GCC-C-execute-920618-1.test   420.00       420.00        0.0%
test-suite...te/GCC-C-execute-920501-5.test   508.00       508.00        0.0%
test-suite...te/GCC-C-execute-920501-6.test   972.00       972.00        0.0%
test-suite...te/GCC-C-execute-920501-8.test   1484.00      1484.00       0.0%
test-suite...te/GCC-C-execute-920501-9.test   836.00       836.00        0.0%
test-suite...te/GCC-C-execute-920506-1.test   436.00       436.00        0.0%
test-suite...te/GCC-C-execute-920520-1.test   436.00       436.00        0.0%
test-suite...te/GCC-C-execute-920603-1.test   444.00       444.00        0.0%
test-suite...te/GCC-C-execute-920604-1.test   428.00       428.00        0.0%
test-suite...te/GCC-C-execute-920612-1.test   436.00       436.00        0.0%
test-suite...simd_ops_test_op_abs_1026.test   27548.00     27548.00      0.0%
Geomean difference                                                       nan%
       results-base  results-init          diff
count  3.412000e+03  3.412000e+03  3.412000e+03
mean   1.749191e+04  1.749155e+04  3.031513e-08
std    4.639147e+04  4.638708e+04  1.444742e-04
min    4.120000e+02  4.120000e+02 -6.363928e-03
25%    4.840000e+02  4.840000e+02  0.000000e+00
50%    2.012000e+03  2.012000e+03  0.000000e+00
75%    2.768600e+04  2.768600e+04  0.000000e+00
max    1.029404e+06  1.029404e+06  5.429629e-03

[alexey.zhikhar]

I'm getting compile time numbers, will submit them soon. We're also planning on adding more test cases before the patch is merged.

[alexey.zhikhar]

Limit the number of paths explored to contain compile time.

[alexey.zhikhar]

Compare the number of switches threaded before and after this patch.

BM	Before	After
MultiSource/Applications/ClamAV/CMakeFiles/clamscan.dir/libclamav\_htmlnorm.stats	0	1
MultiSource/Applications/ClamAV/CMakeFiles/clamscan.dir/libclamav\_message.stats	3	3
MultiSource/Applications/ClamAV/CMakeFiles/clamscan.dir/libclamav\_nsis\_LZMADecode.stats	0	1
MultiSource/Applications/ClamAV/CMakeFiles/clamscan.dir/libclamav\_nsis\_bzlib.stats	0	1
MultiSource/Applications/ClamAV/CMakeFiles/clamscan.dir/libclamav\_untar.stats	1	1
MultiSource/Applications/SPASS/CMakeFiles/SPASS.dir/dfgscanner.stats	1	1
MultiSource/Applications/SPASS/CMakeFiles/SPASS.dir/iascanner.stats	1	1
MultiSource/Applications/kimwitu++/CMakeFiles/kc.dir/kimwl.stats	1	1
MultiSource/Applications/kimwitu++/CMakeFiles/kc.dir/kimwy.stats	0	1
MultiSource/Applications/lua/CMakeFiles/lua.dir/lvm.stats	1	1
MultiSource/Applications/obsequi/CMakeFiles/Obsequi.dir/does\_x\_win.stats	1	1
MultiSource/Applications/sqlite3/CMakeFiles/sqlite3.dir/sqlite3.stats	7	7
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/C/BwtSort.stats	1	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/C/Lzma2Dec.stats	0	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/C/LzmaEnc.stats	1	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/C/XzDec.stats	1	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/Archive/7z/7zUpdate.stats	2	2
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/Archive/Cab/CabHandler.stats	3	3
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/Archive/GzHandler.stats	1	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/Archive/Tar/TarHandler.stats	1	2
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/Archive/Zip/ZipHandler.stats	0	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/Archive/Zip/ZipHandlerOut.stats	1	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/Archive/Zip/ZipIn.stats	1	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/Archive/Zip/ZipUpdate.stats	2	2
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/Compress/ShrinkDecoder.stats	1	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/UI/Common/EnumDirItems.stats	0	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/UI/Common/Extract.stats	1	2
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/UI/Common/OpenArchive.stats	1	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/UI/Common/Update.stats	1	1
MultiSource/Benchmarks/7zip/CMakeFiles/7zip-benchmark.dir/CPP/7zip/UI/Console/List.stats	1	1
MultiSource/Benchmarks/DOE-ProxyApps-C++/CLAMR/CMakeFiles/CLAMR.dir/Cmd.stats	1	1
MultiSource/Benchmarks/MallocBench/gs/CMakeFiles/gs.dir/interp.stats	1	1
MultiSource/Benchmarks/McCat/01-qbsort/CMakeFiles/qbsort.dir/readlist.stats	0	1
MultiSource/Benchmarks/MiBench/consumer-jpeg/CMakeFiles/consumer-jpeg.dir/jddctmgr.stats	1	1
MultiSource/Benchmarks/MiBench/consumer-typeset/CMakeFiles/consumer-typeset.dir/z12.stats	0	1
MultiSource/Benchmarks/MiBench/consumer-typeset/CMakeFiles/consumer-typeset.dir/z14.stats	0	1
MultiSource/Benchmarks/MiBench/consumer-typeset/CMakeFiles/consumer-typeset.dir/z36.stats	1	1
MultiSource/Benchmarks/MiBench/consumer-typeset/CMakeFiles/consumer-typeset.dir/z38.stats	1	1
MultiSource/Benchmarks/MiBench/consumer-typeset/CMakeFiles/consumer-typeset.dir/z49.stats	1	1
MultiSource/Benchmarks/Prolangs-C/TimberWolfMC/CMakeFiles/timberwolfmc.dir/genorient.stats	0	1
MultiSource/Benchmarks/Prolangs-C/TimberWolfMC/CMakeFiles/timberwolfmc.dir/parser.stats	0	1
MultiSource/Benchmarks/Prolangs-C/TimberWolfMC/CMakeFiles/timberwolfmc.dir/unbust.stats	1	1
MultiSource/Benchmarks/Prolangs-C/football/CMakeFiles/football.dir/sort.stats	1	1
MultiSource/Benchmarks/Ptrdist/bc/CMakeFiles/bc.dir/scan.stats	1	1
MultiSource/Benchmarks/mediabench/jpeg/jpeg-6a/CMakeFiles/cjpeg.dir/jddctmgr.stats	1	1
	45	59
		+14

[alexey.zhikhar]

No noticeable compile time impact.

Tests: 10
Metric: compile_time

Program                                        compile_time
                                              base-ct      limit200-ct diff
kimwitu++/kc                                   25.65        25.83       0.7%
sqlite3/sqlite3                                29.09        29.21       0.4%
SPASS/SPASS                                    26.73        26.82       0.4%
ClamAV/clamscan                                29.22        29.21      -0.0%
Bullet/bullet                                  51.96        51.91      -0.1%
consumer-typeset/consumer-typeset              19.90        19.86      -0.2%
lencod/lencod                                  36.56        36.41      -0.4%
mafft/pairlocalalign                           19.60        19.47      -0.7%
7zip/7zip-benchmark                            79.28        78.62      -0.8%
tramp3d-v4/tramp3d-v4                          58.38        56.99      -2.4%
Geomean difference                               nan          nan      -0.3%
      compile_time
run        base-ct limit200-ct       diff
count  10.000000    10.000000   10.000000
mean   37.636450    37.432840  -0.003150
std    19.486189    19.158558   0.008754
min    19.604300    19.467300  -0.023786
25%    25.916200    26.077900  -0.006306
50%    29.154400    29.212200  -0.001405
75%    48.110275    48.032550   0.002560
max    79.283200    78.622400   0.007186

[alexey.zhikhar]

@SjoerdMeijer @jaykang10

Hi Sjoerd and JinGu, I remember from your comments on the initial DFAJumpThreading patch, that you guys are interested in the opportunities in SPEC2017 perlbench. I wanted to let you know that this patch introduces a limit on the number of threaded paths per switch. The limit is 200 paths, that means that if a switch has 1,000 potential path candidates, only 200 of them will get threaded, the rest of them will circle back to the switch instruction the usual way. The thing is that perlbench has several switches optimized by DFAJumpThreading, and a couple of them have the number of paths above the limit (in the thousands). Due to the limit, these switches are threaded partially, which might lead to performance regressions.

Initially I wanted to check whether this patch leads to a regression in perlbench myself but I don't see any performance gains from DFAJumpThreading on perlbench even before introducing the limit, so I don't know which switches you guys are interested in. To be sure that this patch doesn't slow down perlbench for you, please experiment with it on your end, thanks.

[amehsan]

LGTM. I have looked at the code here, but before that we have discussed the approach here and also alternatives with Alex. Since we haven't received any comments from other reviewers, I suggest we merge it.

llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp

ClViewCfgBefore("dfa-jump-view-cfg-before",
                     cl::desc("View the CFG before DFA Jump Threading"),
                     cl::Hidden, cl::init(false));
 
 static cl::opt<unsigned> MaxPathLength(
     "dfa-max-path-length",
     cl::desc("Max number of blocks searched to find a threading path"),
     cl::Hidden, cl::init(20));
 
+static cl::opt<unsigned> MaxNumPaths(
+    "dfa-max-num-paths",
+    cl::desc("Max number of paths enumerated around a switch"),
+    cl::Hidden, cl::init(200));
+
 static cl::opt<unsigned>
     CostThreshold("dfa-cost-threshold",
                   cl::desc("Maximum cost accepted for the transformation"),
                   cl::Hidden, cl::init(50));
 
 namespace {
 
 class SelectInstToUnfold {

 inline raw_ostream &operator<<(raw_ostream &OS, const ThreadingPath &TPath) {
   TPath.print(OS);
   return OS;
 }
 #endif
 
 struct MainSwitch {
   MainSwitch(SwitchInst *SI, OptimizationRemarkEmitter *ORE) {
-    if (isPredictable(SI)) {
+    if (isCandidate(SI)) {
       Instr = SI;
     } else {
       ORE->emit([&]() {
         return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable", SI)
                << "Switch instruction is not predictable.";
       });
     }
   }
 
   virtual ~MainSwitch() = default;
 
   SwitchInst *getInstr() const { return Instr; }
   const SmallVector<SelectInstToUnfold, 4> getSelectInsts() {
     return SelectInsts;
   }
 
 private:
-  /// Do a use-def chain traversal. Make sure the value of the switch variable
-  /// is always a known constant. This means that all conditional jumps based on
-  /// switch variable can be converted to unconditional jumps.
-  bool isPredictable(const SwitchInst *SI) {
-    std::deque<Instruction *> Q;
+  /// Do a use-def chain traversal starting from the switch condition to see if
+  /// \p SI is a potential condidate.
+  ///
+  /// Also, collect select instructions to unfold.
+  bool isCandidate(const SwitchInst *SI) {
+    std::deque<Value *> Q;
     SmallSet<Value *, 16> SeenValues;
     SelectInsts.clear();
 
-    Value *FirstDef = SI->getOperand(0);
-    auto *Inst = dyn_cast<Instruction>(FirstDef);
-
-    // If this is a function argument or another non-instruction, then give up.
-    // We are interested in loop local variables.
-    if (!Inst)
-      return false;
-
-    // Require the first definition to be a PHINode
-    if (!isa<PHINode>(Inst))
+    Value *SICond = SI->getCondition();
+    LLVM_DEBUG(dbgs() << "\tSICond: " << *SICond << "\n");
+    if (!isa<PHINode>(SICond))
       return false;
 
-    LLVM_DEBUG(dbgs() << "\tisPredictable() FirstDef: " << *Inst << "\n");
-
-    Q.push_back(Inst);
-    SeenValues.insert(FirstDef);
+    addToQueue(SICond, Q, SeenValues);
 
     while (!Q.empty()) {
-      Instruction *Current = Q.front();
+      Value *Current = Q.front();
       Q.pop_front();
 
       if (auto *Phi = dyn_cast<PHINode>(Current)) {
         for (Value *Incoming : Phi->incoming_values()) {
-          if (!isPredictableValue(Incoming, SeenValues))
-            return false;
-          addInstToQueue(Incoming, Q, SeenValues);
+          addToQueue(Incoming, Q, SeenValues);
         }
-        LLVM_DEBUG(dbgs() << "\tisPredictable() phi: " << *Phi << "\n");
+        LLVM_DEBUG(dbgs() << "\tphi: " << *Phi << "\n");
       } else if (SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
         if (!isValidSelectInst(SelI))
           return false;
-        if (!isPredictableValue(SelI->getTrueValue(), SeenValues) ||
-            !isPredictableValue(SelI->getFalseValue(), SeenValues)) {
-          return false;
-        }
-        addInstToQueue(SelI->getTrueValue(), Q, SeenValues);
-        addInstToQueue(SelI->getFalseValue(), Q, SeenValues);
-        LLVM_DEBUG(dbgs() << "\tisPredictable() select: " << *SelI << "\n");
+        addToQueue(SelI->getTrueValue(), Q, SeenValues);
+        addToQueue(SelI->getFalseValue(), Q, SeenValues);
+        LLVM_DEBUG(dbgs() << "\tselect: " << *SelI << "\n");
         if (auto *SelIUse = dyn_cast<PHINode>(SelI->user_back()))
           SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
+      } else if (isa<Constant>(Current)) {
+        LLVM_DEBUG(dbgs() << "\tconst: " << *Current << "\n");
+        continue;
       } else {
-        // If it is neither a phi nor a select, then we give up.
-        return false;
+        LLVM_DEBUG(dbgs() << "\tother: " << *Current << "\n");
+        // Allow unpredictable values. The hope is that those will be the
+        // initial switch values that can be ignored (they will hit the
+        // unthreaded switch) but this assumption will get checked later after
+        // paths have been enumerated (in function getStateDefMap).
+        continue;
       }
     }
 
     return true;
   }
 
-  bool isPredictableValue(Value *InpVal, SmallSet<Value *, 16> &SeenValues) {
-    if (SeenValues.contains(InpVal))
-      return true;
-
-    if (isa<ConstantInt>(InpVal))
-      return true;
-
-    // If this is a function argument or another non-instruction, then give up.
-    if (!isa<Instruction>(InpVal))
-      return false;
-
-    return true;
-  }
-
-  void addInstToQueue(Value *Val, std::deque<Instruction *> &Q,
-                      SmallSet<Value *, 16> &SeenValues) {
+  void addToQueue(Value *Val, std::deque<Value *> &Q,
     if (SeenValues.contains(Val))
       return;
-    if (Instruction *I = dyn_cast<Instruction>(Val))
-      Q.push_back(I);
+    Q.push_back(Val);
     SeenValues.insert(Val);
   }
 
   bool isValidSelectInst(SelectInst *SI) {
     if (!SI->hasOneUse())
       return false;
 
     Instruction *SIUse = dyn_cast<Instruction>(SI->user_back());
struct AllSwitchPaths {
   std::vector<ThreadingPath> &getThreadingPaths() { return TPaths; }
   unsigned getNumThreadingPaths() { return TPaths.size(); }
   SwitchInst *getSwitchInst() { return Switch; }
   BasicBlock *getSwitchBlock() { return SwitchBlock; }
 
   void run() {
     VisitedBlocks Visited;
     PathsType LoopPaths = paths(SwitchBlock, Visited, /* PathDepth = */ 1);
-    StateDefMap StateDef = getStateDefMap();
+    StateDefMap StateDef = getStateDefMap(LoopPaths);
+
+    if (StateDef.empty()) {
+      ORE->emit([&]() {
+        return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable",
+                                        Switch)
+               << "Switch instruction is not predictable.";
+      });
+      return;
+    }
 
     for (PathType Path : LoopPaths) {
       ThreadingPath TPath;
 
       const BasicBlock *PrevBB = Path.back();
       for (const BasicBlock *BB : Path) {
         if (StateDef.count(BB) != 0) {
           const PHINode *Phi = dyn_cast<PHINode>(StateDef[BB]);
for (BasicBlock *Succ : successors(BB)) {
       if (Visited.contains(Succ))
         continue;
 
       PathsType SuccPaths = paths(Succ, Visited, PathDepth + 1);
       for (PathType Path : SuccPaths) {
         PathType NewPath(Path);
         NewPath.push_front(BB);
         Res.push_back(NewPath);
+        if (Res.size() >= MaxNumPaths) {
+          return Res;
+        }
       }
     }
     // This block could now be visited again from a different predecessor. Note
     // that this will result in exponential runtime. Subpaths could possibly be
     // cached but it takes a lot of memory to store them.
     Visited.erase(BB);
     return Res;
   }
 
   /// Walk the use-def chain and collect all the state-defining instructions.
-  StateDefMap getStateDefMap() const {
+  ///
+  /// Return an empty map if unpredictable values encountered inside the basic
+  /// blocks of \p LoopPaths.
+  StateDefMap getStateDefMap(const PathsType &LoopPaths) const {
     StateDefMap Res;
 
+    // Basic blocks belonging to any of the loops around the switch statement.
+    SmallPtrSet<BasicBlock *, 16> LoopBBs;
+    for (const PathType &Path : LoopPaths) {
+      for (BasicBlock *BB : Path)
+        LoopBBs.insert(BB);
+    }
+
     Value *FirstDef = Switch->getOperand(0);
 
-    assert(isa<PHINode>(FirstDef) && "After select unfolding, all state "
-                                     "definitions are expected to be phi "
-                                     "nodes.");
+    assert(isa<PHINode>(FirstDef) && "The first definition must be a phi.");
 
     SmallVector<PHINode *, 8> Stack;
     Stack.push_back(dyn_cast<PHINode>(FirstDef));
     SmallSet<Value *, 16> SeenValues;
 
     while (!Stack.empty()) {
       PHINode *CurPhi = Stack.pop_back_val();
 
       Res[CurPhi->getParent()] = CurPhi;
       SeenValues.insert(CurPhi);
 
-      for (Value *Incoming : CurPhi->incoming_values()) {
+      for (BasicBlock *IncomingBB : CurPhi->blocks()) {
+        Value *Incoming = CurPhi->getIncomingValueForBlock(IncomingBB);
+        bool IsOutsideLoops = LoopBBs.count(IncomingBB) == 0;
         if (Incoming == FirstDef || isa<ConstantInt>(Incoming) ||
-            SeenValues.contains(Incoming)) {
+            SeenValues.contains(Incoming) || IsOutsideLoops) {
           continue;
         }
 
-        assert(isa<PHINode>(Incoming) && "After select unfolding, all state "
-                                         "definitions are expected to be phi "
-                                         "nodes.");
+        // Any unpredictable value inside the loops means we must bail out.
+        if (!isa<PHINode>(Incoming))
+          return StateDefMap();
 
         Stack.push_back(cast<PHINode>(Incoming));
       }
     }
 
     return Res;
   }
 
bool DFAJumpThreading::run(Function &F) {
   bool MadeChanges = false;
 
   for (BasicBlock &BB : F) {
     auto *SI = dyn_cast<SwitchInst>(BB.getTerminator());
     if (!SI)
       continue;
 
     LLVM_DEBUG(dbgs() << "\nCheck if SwitchInst in BB " << BB.getName()
-                      << " is predictable\n");
+                      << " is a candidate\n");
     MainSwitch Switch(SI, ORE);
 
     if (!Switch.getInstr())
       continue;
 
     LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is a "
                       << "candidate for jump threading\n");
     LLVM_DEBUG(SI->dump());

llvm/test/Transforms/DFAJumpThreading/dfa-jump-threading-analysis.ll

 
 bb49:                                             ; preds = %bb43, %bb43
   tail call void @baz()
   br label %bb59
 
 bb66:                                             ; preds = %bb59
   ret i32 0
 }
+
+; Value %init is not predictable but it's okay since it is the value initial to the switch.
+define i32 @initial.value.positive1(i32 %init) {
+; CHECK: < loop.3 case2 > [ 3, loop.3 ]
+; CHECK-NEXT: < loop.3 case2 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
+; CHECK-NEXT: < loop.3 case2 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 4, loop.1.backedge ]
+; CHECK-NEXT: < loop.3 case3 loop.2.backedge loop.2 > [ 0, loop.2.backedge ]
+; CHECK-NEXT: < loop.3 case3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
+; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
+; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
+; CHECK-NEXT: < loop.3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
+; CHECK-NEXT: < loop.3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
+; CHECK-NEXT: < loop.3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
+entry:
+  %cmp = icmp eq i32 %init, 0
+  br label %loop.1
+
+loop.1:
+  %state.1 = phi i32 [ %init, %entry ], [ %state.1.be2, %loop.1.backedge ]
+  br label %loop.2
+
+loop.2:
+  %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
+  br label %loop.3
+
+loop.3:
+  %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
+  switch i32 %state, label %infloop.i [
+    i32 2, label %case2
+    i32 3, label %case3
+    i32 4, label %case4
+    i32 0, label %case0
+    i32 1, label %case1
+  ]
+
+case2:
+  br i1 %cmp, label %loop.3, label %loop.1.backedge
+
+case3:
+  br i1 %cmp, label %loop.2.backedge, label %case4
+
+case4:
+  br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge
+
+loop.1.backedge:
+  %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
+  %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
+  br label %loop.1
+
+loop.2.backedge:
+  %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
+  br label %loop.2
+
+case0:
+  br label %exit
+
+case1:
+  br label %exit
+
+infloop.i:
+  br label %infloop.i
+
+exit:
+  ret i32 0
+}

llvm/test/Transforms/DFAJumpThreading/negative.ll

for.inc:
   %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ]
   %inc = add nsw i32 %count, 1
   %cmp.exit = icmp slt i32 %inc, %num
   br i1 %cmp.exit, label %for.body, label %for.end
 
 for.end:
   ret i32 0
 }
+
+declare i32 @arbitrary_function()
+
+; Don't confuse %state.2 for the initial switch value.
+define i32 @negative6(i32 %init) {
+; REMARK: SwitchNotPredictable
+; REMARK-NEXT: negative6
+entry:
+  %cmp = icmp eq i32 %init, 0
+  br label %loop.2
+
+loop.2:
+  %state.2 = call i32 @arbitrary_function()
+  br label %loop.3
+
+loop.3:
+  %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
+  switch i32 %state, label %infloop.i [
+    i32 2, label %case2
+    i32 3, label %case3
+    i32 4, label %case4
+    i32 0, label %case0
+    i32 1, label %case1
+  ]
+
+case2:
+  br label %loop.3
+
+case3:
+  br i1 %cmp, label %loop.2.backedge, label %case4
+
+case4:
+  br label %loop.2.backedge
+
+loop.2.backedge:
+  br label %loop.2
+
+case0:
+  br label %exit
+
+case1:
+  br label %exit
+
+infloop.i:
+  br label %infloop.i
+
+exit:
+  ret i32 0
+}