diff --git a/llvm/include/llvm/CodeGen/Passes.h
 b/llvm/include/llvm/CodeGen/Passes.h
--- a/llvm/include/llvm/CodeGen/Passes.h
+++ b/llvm/include/llvm/CodeGen/Passes.h
@@ -76,6 +76,11 @@
   /// matching during instruction selection.
   FunctionPass *createCodeGenPreparePass();
 
+  // DFAJumpThreadingPass - When a switch statement inside a loop is used to
+  // implement a deterministic finite automata we can jump thread the switch
+  // statement reducing number of conditional jumps.
+  FunctionPass *createDFAJumpThreadingPass(const TargetMachine *TM = nullptr);
+
   /// AtomicExpandID -- Lowers atomic operations in terms of either cmpxchg
   /// load-linked/store-conditional loops.
   extern char &AtomicExpandID;
diff --git a/llvm/include/llvm/InitializePasses.h
 b/llvm/include/llvm/InitializePasses.h
--- a/llvm/include/llvm/InitializePasses.h
+++ b/llvm/include/llvm/InitializePasses.h
@@ -124,6 +124,7 @@
 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);
 void initializeDCELegacyPassPass(PassRegistry&);
+void initializeDFAJumpThreadingPass(PassRegistry&);
 void initializeDSELegacyPassPass(PassRegistry&);
 void initializeDataFlowSanitizerLegacyPassPass(PassRegistry &);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
diff --git a/llvm/include/llvm/LinkAllPasses.h
 b/llvm/include/llvm/LinkAllPasses.h
--- a/llvm/include/llvm/LinkAllPasses.h
+++ b/llvm/include/llvm/LinkAllPasses.h
@@ -174,6 +174,7 @@
       (void) llvm::createStripDeadPrototypesPass();
       (void) llvm::createTailCallEliminationPass();
       (void) llvm::createJumpThreadingPass();
+      (void) llvm::createDFAJumpThreadingPass();
       (void) llvm::createUnifyFunctionExitNodesPass();
       (void) llvm::createInstCountPass();
       (void) llvm::createConstantHoistingPass();
diff --git a/llvm/lib/CodeGen/CMakeLists.txt
 b/llvm/lib/CodeGen/CMakeLists.txt
--- a/llvm/lib/CodeGen/CMakeLists.txt
+++ b/llvm/lib/CodeGen/CMakeLists.txt
@@ -20,6 +20,7 @@
   CriticalAntiDepBreaker.cpp
   DeadMachineInstructionElim.cpp
   DetectDeadLanes.cpp
+  DFAJumpThreading.cpp
   DFAPacketizer.cpp
   DwarfEHPrepare.cpp
   EarlyIfConversion.cpp
diff --git a/llvm/lib/CodeGen/CodeGen.cpp
 b/llvm/lib/CodeGen/CodeGen.cpp
--- a/llvm/lib/CodeGen/CodeGen.cpp
+++ b/llvm/lib/CodeGen/CodeGen.cpp
@@ -29,6 +29,7 @@
   initializeCodeGenPreparePass(Registry);
   initializeDeadMachineInstructionElimPass(Registry);
   initializeDebugifyMachineModulePass(Registry);
+  initializeDFAJumpThreadingPass(Registry);
   initializeDetectDeadLanesPass(Registry);
   initializeDwarfEHPrepareLegacyPassPass(Registry);
   initializeEarlyIfConverterPass(Registry);
diff --git a/llvm/lib/CodeGen/DFAJumpThreading.cpp b/llvm/lib/CodeGen/DFAJumpThreading.cpp
new file mode 100644
--- /dev/null
+++ b/llvm/lib/CodeGen/DFAJumpThreading.cpp
@@ -0,0 +1,1106 @@
+//===- DFAJumpThreading.cpp - Threads a switch statement inside a loop ----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// When a switch statement inside a loop is used to implement a deterministic
+// finite automaton, we can jump thread the switch statement reducing number of
+// conditional jumps. Currently this does not happen in LLVM jump threading.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/Analysis/LoopIterator.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/SSAUpdaterBulk.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include <list>
+#include <unordered_map>
+#include <unordered_set>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "dfa-jump-threading"
+
+static cl::opt<bool> DisableThis("disable-dfa-jump-thread",
+                                 cl::desc("Disable DFA jump threading."),
+                                 cl::Hidden, cl::init(false));
+
+static cl::opt<bool>
+    IsViewCFG("dfa-jump-view-cfg",
+              cl::desc("View the CFG before DFA Jump Threading"), cl::Hidden,
+              cl::init(false));
+
+static cl::opt<int> MaxPathDepth(
+    "dfa-max-path-length",
+    cl::desc("Max number of blocks searched to find threadable path"),
+    cl::Hidden, cl::init(20));
+
+namespace {
+
+class SelectInstToUnfold {
+  SelectInst *SI;
+  PHINode *SIUse;
+
+public:
+  SelectInstToUnfold(SelectInst *SI, PHINode *SIUse) : SI(SI), SIUse(SIUse) {}
+
+  SelectInst *getInst() { return SI; }
+  PHINode *getUse() { return SIUse; }
+
+  explicit operator bool() const { return SI && SIUse; }
+};
+
+void unfold(DomTreeUpdater *DTU, SelectInstToUnfold SIToUnfold,
+            std::vector<SelectInstToUnfold> *NewSIsToUnfold,
+            std::vector<BasicBlock *> *NewBBs);
+
+class DFAJumpThreading : public FunctionPass {
+public:
+  static char ID; // Pass identification
+  DFAJumpThreading() : FunctionPass(ID) {
+    initializeDFAJumpThreadingPass(*PassRegistry::getPassRegistry());
+  }
+
+  ~DFAJumpThreading() override = default;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<DominatorTreeWrapperPass>();
+  }
+
+  bool runOnFunction(Function &F) override;
+
+private:
+  void unfoldSelectInstrs(DominatorTree *DT,
+                          const std::vector<SelectInstToUnfold> &SelectInsts) {
+    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+    std::list<SelectInstToUnfold> Q;
+    for (SelectInstToUnfold SIToUnfold : SelectInsts) {
+      Q.push_back(SIToUnfold);
+    }
+
+    while (!Q.empty()) {
+      SelectInstToUnfold SIToUnfold = Q.front();
+      Q.pop_front();
+
+      std::vector<SelectInstToUnfold> NewSIsToUnfold;
+      std::vector<BasicBlock *> NewBBs;
+      unfold(&DTU, SIToUnfold, &NewSIsToUnfold, &NewBBs);
+
+      // Put newly discovered select instructions into the work list.
+      for (const SelectInstToUnfold &NewSIToUnfold : NewSIsToUnfold) {
+        Q.push_back(NewSIToUnfold);
+      }
+    }
+  }
+};
+} // end anonymous namespace
+
+char DFAJumpThreading::ID = 0;
+INITIALIZE_PASS_BEGIN(DFAJumpThreading, "dfa-jump-threading",
+                      "DFA Jump Threading", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_END(DFAJumpThreading, "dfa-jump-threading",
+                    "DFA Jump Threading", false, false)
+
+// Public interface to the DFA Jump Threading pass
+FunctionPass *llvm::createDFAJumpThreadingPass(const TargetMachine *TM) {
+  return new DFAJumpThreading();
+}
+
+namespace {
+
+/// Unfold the select instruction held in \p SIToUnfold.
+///
+/// Put newly discovered select instructions into \p NewSIsToUnfold. Put newly
+/// created basic blocks into \p NewBBs.
+///
+/// This routine is inspired by CodeGenPrepare::optimizeSelectInst().
+void unfold(DomTreeUpdater *DTU, SelectInstToUnfold SIToUnfold,
+            std::vector<SelectInstToUnfold> *NewSIsToUnfold,
+            std::vector<BasicBlock *> *NewBBs) {
+  SelectInst *SI = SIToUnfold.getInst();
+  PHINode *SIUse = SIToUnfold.getUse();
+  BasicBlock *StartBlock = SI->getParent();
+  BasicBlock *EndBlock = SIUse->getParent();
+  BranchInst *StartBlockTerm =
+      dyn_cast<BranchInst>(StartBlock->getTerminator());
+
+  assert(StartBlockTerm && StartBlockTerm->isUnconditional());
+  assert(SI->hasOneUse());
+
+  // These are the new basic blocks for the conditional branch.
+  // At least one will become an actual new basic block.
+  BasicBlock *TrueBlock = nullptr;
+  BasicBlock *FalseBlock = nullptr;
+  BranchInst *TrueBranch = nullptr;
+  BranchInst *FalseBranch = nullptr;
+
+  // Sink select instructions to be able to unfold them later.
+  if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getTrueValue())) {
+    assert(SIOp->hasOneUse());
+    TrueBlock = BasicBlock::Create(SI->getContext(), "si.unfold.true",
+                                   EndBlock->getParent(), EndBlock);
+    NewBBs->push_back(TrueBlock);
+    TrueBranch = BranchInst::Create(EndBlock, TrueBlock);
+    SIOp->moveBefore(TrueBranch);
+    NewSIsToUnfold->push_back(SelectInstToUnfold(SIOp, SIUse));
+    DTU->applyUpdates({{DominatorTree::Insert, TrueBlock, EndBlock}});
+  }
+  if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getFalseValue())) {
+    assert(SIOp->hasOneUse());
+    FalseBlock = BasicBlock::Create(SI->getContext(), "si.unfold.false",
+                                    EndBlock->getParent(), EndBlock);
+    NewBBs->push_back(FalseBlock);
+    FalseBranch = BranchInst::Create(EndBlock, FalseBlock);
+    SIOp->moveBefore(FalseBranch);
+    NewSIsToUnfold->push_back(SelectInstToUnfold(SIOp, SIUse));
+    DTU->applyUpdates({{DominatorTree::Insert, FalseBlock, EndBlock}});
+  }
+
+  // If there was nothing to sink, then arbitrarily choose the 'false' side
+  // for a new input value to the PHI.
+  if (!TrueBlock && !FalseBlock) {
+    FalseBlock = BasicBlock::Create(SI->getContext(), "si.unfold.false",
+                                    EndBlock->getParent(), EndBlock);
+    NewBBs->push_back(FalseBlock);
+    BranchInst::Create(EndBlock, FalseBlock);
+    DTU->applyUpdates({{DominatorTree::Insert, FalseBlock, EndBlock}});
+  }
+
+  // Insert the real conditional branch based on the original condition.
+  // If we did not create a new block for one of the 'true' or 'false' paths
+  // of the condition, it means that side of the branch goes to the end block
+  // directly and the path originates from the start block from the point of
+  // view of the new PHI.
+  BasicBlock *TT = nullptr;
+  BasicBlock *FT = nullptr;
+  if (!TrueBlock) {
+    // A triangle pointing right.
+    TT = EndBlock;
+    FT = FalseBlock;
+    TrueBlock = StartBlock;
+
+    // Update the phi node of SI.
+    for (unsigned Idx = 0; Idx < SIUse->getNumIncomingValues(); ++Idx) {
+      if (SIUse->getIncomingBlock(Idx) == StartBlock) {
+        SIUse->setIncomingValue(Idx, SI->getTrueValue());
+      }
+    }
+    SIUse->addIncoming(SI->getFalseValue(), FalseBlock);
+
+    // Update any other PHI nodes in EndBlock.
+    for (auto II = EndBlock->begin(); PHINode *Phi = dyn_cast<PHINode>(II);
+         ++II) {
+      if (Phi != SIUse) {
+        Phi->addIncoming(Phi->getIncomingValueForBlock(StartBlock), FalseBlock);
+      }
+    }
+  } else if (!FalseBlock) {
+    // A triangle pointing left.
+    TT = TrueBlock;
+    FT = EndBlock;
+    FalseBlock = StartBlock;
+
+    // Update the phi node of SI.
+    for (unsigned Idx = 0; Idx < SIUse->getNumIncomingValues(); ++Idx) {
+      if (SIUse->getIncomingBlock(Idx) == StartBlock) {
+        SIUse->setIncomingValue(Idx, SI->getFalseValue());
+      }
+    }
+    SIUse->addIncoming(SI->getTrueValue(), TrueBlock);
+
+    // Update any other PHI nodes in EndBlock.
+    for (auto II = EndBlock->begin(); PHINode *Phi = dyn_cast<PHINode>(II);
+         ++II) {
+      if (Phi != SIUse) {
+        Phi->addIncoming(Phi->getIncomingValueForBlock(StartBlock), TrueBlock);
+      }
+    }
+  } else {
+    // A diamond.
+    TT = TrueBlock;
+    FT = FalseBlock;
+
+    // Update the phi node of SI.
+    SIUse->removeIncomingValue(StartBlock, /* DeletePHIIfEmpty = */ false);
+    SIUse->addIncoming(SI->getTrueValue(), TrueBlock);
+    SIUse->addIncoming(SI->getFalseValue(), FalseBlock);
+
+    // Update any other PHI nodes in EndBlock.
+    for (auto II = EndBlock->begin(); PHINode *Phi = dyn_cast<PHINode>(II);
+         ++II) {
+      if (Phi != SIUse) {
+        Phi->addIncoming(Phi->getIncomingValueForBlock(StartBlock), TrueBlock);
+        Phi->addIncoming(Phi->getIncomingValueForBlock(StartBlock), FalseBlock);
+      }
+    }
+  }
+  StartBlockTerm->eraseFromParent();
+  BranchInst::Create(TT, FT, SI->getCondition(), StartBlock);
+  DTU->applyUpdates({{DominatorTree::Insert, StartBlock, TT},
+                     {DominatorTree::Insert, StartBlock, FT}});
+
+  // The select is now dead.
+  SI->eraseFromParent();
+}
+
+struct ClonedBlock {
+  BasicBlock *BB;
+  uint64_t State;
+};
+
+typedef std::list<BasicBlock *> PathType;
+typedef std::list<PathType> PathsType;
+typedef std::set<const BasicBlock *> VisitedBlocks;
+typedef std::vector<ClonedBlock> CloneList;
+
+// This data structure keeps track of all blocks that have been cloned in the
+// optimization. If two different ThreadingPaths clone the same block for a
+// certain state it should be reused, and it can be looked up in this map.
+typedef std::unordered_map<BasicBlock *, CloneList> DuplicateBlockMap;
+
+// This map keeps track of all the new definitions for an instruction. This
+// information is needed when restoring SSA form after cloning blocks.
+typedef std::unordered_map<Instruction *, std::vector<Instruction *>> DefMap;
+
+inline raw_ostream &operator<<(raw_ostream &OS, const PathType &Path) {
+  OS << "< ";
+  for (const BasicBlock *BB : Path) {
+    OS << BB->getName() << " ";
+  }
+  OS << ">";
+  return OS;
+}
+
+struct ThreadingPath {
+  uint64_t getEntryValue() const { return EntryVal; }
+  void setEntryValue(const ConstantInt *V) {
+    EntryVal = V->getZExtValue();
+    IsEntryValSet = true;
+  }
+  bool isEntryValueSet() const { return IsEntryValSet; }
+
+  uint64_t getExitValue() const { return ExitVal; }
+  void setExitValue(const ConstantInt *V) {
+    ExitVal = V->getZExtValue();
+    IsExitValSet = true;
+  }
+  bool isExitValueSet() const { return IsExitValSet; }
+
+  const BasicBlock *getDeterminatorBB() const { return DBB; }
+  void setDeterminator(const BasicBlock *BB) { DBB = BB; }
+
+  const PathType &getPath() const { return Path; }
+  void setPath(const PathType &NewPath) { Path = NewPath; }
+
+  void print(raw_ostream &OS) const {
+    OS << Path << " [ " << EntryVal << ", " << ExitVal << ", " << DBB->getName()
+       << " ]";
+  }
+
+private:
+  PathType Path;
+  uint64_t EntryVal;
+  uint64_t ExitVal;
+  const BasicBlock *DBB = nullptr;
+  bool IsEntryValSet = false;
+  bool IsExitValSet = false;
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, const ThreadingPath &TPath) {
+  TPath.print(OS);
+  return OS;
+}
+
+struct MainSwitch {
+  MainSwitch(SwitchInst *SI) : SI(SI) {
+    if (isPredictable(SI))
+      Instr = SI;
+  }
+
+  virtual ~MainSwitch() = default;
+
+  SwitchInst *getInstr() const { return Instr; }
+  const std::vector<SelectInstToUnfold> getSelectInsts() { return SelectInsts; }
+
+  /// Returns true if \p BB is a destination of the MainSwitch that is not
+  /// default.
+  bool isNonDefaultDest(const BasicBlock *BB) const {
+    for (auto Case : dyn_cast<SwitchInst>(Instr)->cases()) {
+      if (Case.getCaseSuccessor() == BB) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  const ConstantInt *getValueFor(const BasicBlock *BB) const {
+    for (auto Case : dyn_cast<SwitchInst>(Instr)->cases()) {
+      if (Case.getCaseSuccessor() == BB) {
+        return Case.getCaseValue();
+      }
+    }
+    return nullptr;
+  }
+
+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 jump.
+  bool isPredictable(const SwitchInst *SI) {
+    std::list<Instruction *> Q;
+    SmallSet<Value *, 16> SeenValues;
+    SelectInsts.clear();
+
+    Value *FirstDef = SI->getOperand(0);
+
+    if (!FirstDef->getType()->isIntegerTy())
+      return false;
+
+    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))
+      return false;
+
+    LLVM_DEBUG(dbgs() << "\tisPredictable() FirstDef: " << *Inst << "\n");
+
+    Q.push_back(Inst);
+    SeenValues.insert(FirstDef);
+
+    while (!Q.empty()) {
+      Instruction *Current = Q.front();
+      Q.pop_front();
+
+      if (auto *Phi = dyn_cast<PHINode>(Current)) {
+        for (Value *Incoming : Phi->incoming_values()) {
+          if (!isValidValue(Incoming, SeenValues)) {
+            return false;
+          }
+          addInstToQueue(Incoming, Q, SeenValues);
+        }
+        LLVM_DEBUG(dbgs() << "\tisPredictable() phi: " << *Phi << "\n");
+      } else if (SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
+        if (!isValidSelectInst(SelI)) {
+          return false;
+        }
+        if (!isValidValue(SelI->getTrueValue(), SeenValues) ||
+            !isValidValue(SelI->getFalseValue(), SeenValues)) {
+          return false;
+        }
+        addInstToQueue(SelI->getTrueValue(), Q, SeenValues);
+        addInstToQueue(SelI->getFalseValue(), Q, SeenValues);
+        LLVM_DEBUG(dbgs() << "\tisPredictable() select: " << *SelI << "\n");
+        if (auto SelIUse = dyn_cast<PHINode>(SelI->user_back())) {
+          SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
+        }
+      } else {
+        // If it is neither a phi nor a select, then we give up.
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  bool isValidValue(Value *InpVal, SmallSet<Value *, 16> &SeenValues) {
+    if (SeenValues.find(InpVal) != SeenValues.end())
+      return true;
+
+    if (isa<ConstantInt>(InpVal))
+      return true;
+
+    // If this is a function argument or another non-instruction, then give up.
+    Instruction *I = dyn_cast<Instruction>(InpVal);
+    if (I == nullptr)
+      return false;
+
+    return true;
+  }
+
+  void addInstToQueue(Value *Val, std::list<Instruction *> &Q,
+                      SmallSet<Value *, 16> &SeenValues) {
+    if (SeenValues.find(Val) != SeenValues.end())
+      return;
+    if (Instruction *I = dyn_cast<Instruction>(Val)) {
+      Q.push_back(I);
+    }
+    SeenValues.insert(Val);
+  }
+
+  bool isValidSelectInst(SelectInst *SI) {
+    // Vector select instructions are not supported.
+    if (!SI->getCondition()->getType()->isIntegerTy(1)) {
+      return false;
+    }
+
+    if (!SI->hasOneUse()) {
+      return false;
+    }
+
+    Instruction *SIUse = dyn_cast<Instruction>(SI->user_back());
+    // The use of the select inst should be either a phi or another select.
+    if (!SIUse && !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse))) {
+      return false;
+    }
+
+    BasicBlock *SIBB = SI->getParent();
+
+    // Currently, we can only expand select instructions in basic blocks with
+    // one successor.
+    BranchInst *SITerm = dyn_cast<BranchInst>(SIBB->getTerminator());
+    if (!SITerm || !SITerm->isUnconditional()) {
+      return false;
+    }
+
+    if (isa<PHINode>(SIUse) && SIBB->getSingleSuccessor() !=
+                                   dyn_cast<Instruction>(SIUse)->getParent()) {
+      return false;
+    }
+
+    // If select will not be sunk during unfolding, and it is in the same basic
+    // block as another state defining select, then cannot unfold both.
+    for (SelectInstToUnfold SIToUnfold : SelectInsts) {
+      SelectInst *PrevSI = SIToUnfold.getInst();
+      if (PrevSI->getTrueValue() != SI && PrevSI->getFalseValue() != SI &&
+          PrevSI->getParent() == SI->getParent())
+        return false;
+    }
+
+    return true;
+  }
+
+  SwitchInst *SI;
+  SwitchInst *Instr = nullptr;
+  std::vector<SelectInstToUnfold> SelectInsts;
+};
+
+struct AllSwitchPaths {
+  AllSwitchPaths(const MainSwitch *MSwitch)
+      : Switch(MSwitch->getInstr()), SwitchBlock(Switch->getParent()),
+        MSwitch(MSwitch) {}
+
+  std::list<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();
+
+    for (PathType Path : LoopPaths) {
+      ThreadingPath TPath;
+
+      const BasicBlock *PrevBB = nullptr;
+      for (const BasicBlock *BB : Path) {
+        if (MSwitch->isNonDefaultDest(BB) && !TPath.isEntryValueSet()) {
+          const ConstantInt *Val = MSwitch->getValueFor(BB);
+          TPath.setEntryValue(Val);
+        }
+
+        if (TPath.isEntryValueSet() && StateDef.count(BB) != 0) {
+          const PHINode *Phi = dyn_cast<PHINode>(StateDef[BB]);
+          assert(Phi && "Expected a state-defining instr to be a phi node.");
+
+          const Value *V = Phi->getIncomingValueForBlock(PrevBB);
+          if (const ConstantInt *C = dyn_cast<const ConstantInt>(V)) {
+            TPath.setExitValue(C);
+            TPath.setDeterminator(BB);
+            TPath.setPath(Path);
+          }
+        }
+
+        PrevBB = BB;
+      }
+
+      // The next state may be defined in the switch block itself. If an exit
+      // value was not found, then check if the switch block is the determinator
+      if (!TPath.isExitValueSet() && StateDef.count(SwitchBlock) != 0) {
+        const PHINode *Phi = dyn_cast<PHINode>(StateDef[SwitchBlock]);
+        assert(Phi && "Expected a state-defining instr to be a phi node.");
+
+        if (Phi->getBasicBlockIndex(PrevBB) != -1) {
+          const Value *V = Phi->getIncomingValueForBlock(PrevBB);
+          if (const ConstantInt *C = dyn_cast<const ConstantInt>(V)) {
+            TPath.setExitValue(C);
+            TPath.setDeterminator(SwitchBlock);
+            TPath.setPath(Path);
+          }
+        }
+      }
+
+      if (TPath.isExitValueSet())
+        TPaths.push_back(TPath);
+    }
+
+    for (const ThreadingPath &TPath : TPaths) {
+      LLVM_DEBUG(dbgs() << TPath << "\n");
+    }
+  }
+
+private:
+  // Value: an instruction that defines a switch state;
+  // Key: the parent basic block of that instruction.
+  typedef std::unordered_map<const BasicBlock *, const PHINode *> StateDefMap;
+
+  PathsType paths(BasicBlock *BB, VisitedBlocks &Visited, int PathDepth) const {
+    PathsType Res;
+
+    // Stop exploring paths after visiting MaxPathLength blocks
+    if (PathDepth > MaxPathDepth)
+      return Res;
+
+    Visited.insert(BB);
+
+    // Some blocks have multiple edges to the same successor, and this set
+    // is used to prevent a duplicate path from being generated
+    SmallSet<BasicBlock *, 4> Successors;
+
+    for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
+      BasicBlock *Succ = *SI;
+
+      if (Successors.find(Succ) != Successors.end())
+        continue;
+      Successors.insert(Succ);
+
+      // Found a cycle through the SwitchBlock
+      if (Succ == SwitchBlock) {
+        Res.push_back({BB});
+        continue;
+      }
+
+      // We have encountered a cycle, do not get caught in it
+      if (Visited.find(Succ) != Visited.end())
+        continue;
+
+      PathsType SuccPaths = paths(Succ, Visited, PathDepth + 1);
+      for (PathType Path : SuccPaths) {
+        PathType NewPath(Path);
+        NewPath.push_front(BB);
+        Res.push_back(NewPath);
+      }
+    }
+    // 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 {
+    StateDefMap Res;
+
+    Value *FirstDef = Switch->getOperand(0);
+
+    assert(isa<PHINode>(FirstDef) && "After select unfolding, all state "
+                                     "definitions are expected to be phi "
+                                     "nodes.");
+
+    std::list<PHINode *> Q;
+    Q.push_back(dyn_cast<PHINode>(FirstDef));
+    SmallSet<Value *, 16> SeenValues;
+
+    while (!Q.empty()) {
+      PHINode *CurPhi = Q.front();
+      Q.pop_front();
+
+      Res[CurPhi->getParent()] = CurPhi;
+      SeenValues.insert(CurPhi);
+
+      for (Value *Incoming : CurPhi->incoming_values()) {
+        if (Incoming == FirstDef || isa<ConstantInt>(Incoming) ||
+            SeenValues.find(Incoming) != SeenValues.end()) {
+          continue;
+        }
+
+        assert(isa<PHINode>(Incoming) && "After select unfolding, all state "
+                                         "definitions are expected to be phi "
+                                         "nodes.");
+
+        Q.push_back(dyn_cast<PHINode>(Incoming));
+      }
+    }
+
+    return Res;
+  }
+
+  SwitchInst *Switch;
+  BasicBlock *SwitchBlock;
+  const MainSwitch *MSwitch;
+  std::list<ThreadingPath> TPaths;
+};
+
+struct TransformFSM {
+  TransformFSM(AllSwitchPaths *SwitchPaths, DominatorTree *DT)
+      : SwitchPaths(SwitchPaths), DT(DT) {}
+
+  void run() { createAllExitPaths(); }
+
+private:
+  /// Transform each threading path to effectively jump thread the FSM. For
+  /// example the CFG below could be transformed as follows, where the cloned
+  /// blocks unconditionally branch to the next correct case based on what is
+  /// identified in the analysis.
+  ///          sw.bb                        sw.bb
+  ///        /   |   \                    /   |   \
+  ///   case1  case2  case3          case1  case2  case3
+  ///        \   |   /                 |      |      |
+  ///       determinator            det.2   det.3  det.1
+  ///        br sw.bb                /        |        \
+  ///                          sw.bb.2     sw.bb.3     sw.bb.1
+  ///                           br case2    br case3    br case1
+  void createAllExitPaths() {
+    DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager);
+
+    // Move the switch block to the end of the path, since it will be duplicated
+    BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
+    for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
+      PathType NewPath(TPath.getPath());
+      NewPath.push_back(SwitchBlock);
+      TPath.setPath(NewPath);
+    }
+
+    // Transform the ThreadingPaths and keep track of the cloned values
+    DuplicateBlockMap DuplicateMap;
+    DefMap NewDefs;
+
+    SmallSet<BasicBlock *, 16> BlocksToClean;
+    for (BasicBlock *BB : successors(SwitchBlock)) {
+      BlocksToClean.insert(BB);
+    }
+
+    for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
+      createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU);
+    }
+
+    // After all paths are cloned, now update the last successor of the cloned
+    // path so it skips over the switch statement
+    for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
+      updateLastSuccessor(TPath, DuplicateMap, &DTU);
+    }
+
+    // For each instruction that was cloned and used outside, update its uses
+    updateSSA(NewDefs);
+
+    // Clean PHI Nodes for the newly created blocks
+    for (BasicBlock *BB : BlocksToClean) {
+      cleanPhiNodes(BB);
+    }
+  }
+
+  /// For a specific ThreadingPath, create an exit path starting from the
+  /// determinator block. To remember the correct destination, we have to
+  /// duplicate blocks corresponding to each state. Also update the terminating
+  /// instruction of the predecessors, and phis in the successor blocks.
+  void createExitPath(DefMap &NewDefs, ThreadingPath &Path,
+                      DuplicateBlockMap &DuplicateMap,
+                      SmallSet<BasicBlock *, 16> &BlocksToClean,
+                      DomTreeUpdater *DTU) {
+    uint64_t NextState = Path.getExitValue();
+    const BasicBlock *Determinator = Path.getDeterminatorBB();
+    PathType PathBBs = Path.getPath();
+
+    // Don't select the placeholder block in front
+    if (PathBBs.front() == Determinator)
+      PathBBs.pop_front();
+
+    auto DetIt = std::find(PathBBs.begin(), PathBBs.end(), Determinator);
+    auto Prev = std::prev(DetIt);
+    BasicBlock *PrevBB = *Prev;
+    for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
+      BasicBlock *BB = *BBIt;
+      BlocksToClean.insert(BB);
+
+      // We already cloned BB for this NextState, now just update the branch
+      // and continue.
+      BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
+      if (NextBB) {
+        updatePredecessor(PrevBB, BB, NextBB, DTU);
+        PrevBB = NextBB;
+        continue;
+      }
+
+      // Clone the BB and update the successor of Prev to jump to the new block
+      BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
+          BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
+      DuplicateMap[BB].push_back({NewBB, NextState});
+      BlocksToClean.insert(NewBB);
+      PrevBB = NewBB;
+    }
+  }
+
+  /// Restore SSA form after cloning blocks. Each cloned block creates new defs
+  /// for a variable, and the uses need to be updated to reflect this. The uses
+  /// may be replaced with a cloned value, or some derived phi instruction. Note
+  /// that all uses of a value defined in the same block were already remapped
+  /// when cloning the block.
+  void updateSSA(DefMap &NewDefs) {
+    SSAUpdaterBulk SSAUpdate;
+    SmallVector<Use *, 16> UsesToRename;
+
+    for (auto KV : NewDefs) {
+      Instruction *I = KV.first;
+      BasicBlock *BB = I->getParent();
+      std::vector<Instruction *> Cloned = KV.second;
+
+      // Scan all uses of this instruction to see if it is used outside of its
+      // block, and if so, record them in UsesToRename.
+      for (Use &U : I->uses()) {
+        Instruction *User = cast<Instruction>(U.getUser());
+        if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
+          if (UserPN->getIncomingBlock(U) == BB)
+            continue;
+        } else if (User->getParent() == BB) {
+          continue;
+        }
+
+        UsesToRename.push_back(&U);
+      }
+
+      // If there are no uses outside the block, we're done with this
+      // instruction.
+      if (UsesToRename.empty())
+        continue;
+      LLVM_DEBUG(dbgs() << "DFA-JT: Renaming non-local uses of: " << *I
+                        << "\n");
+
+      // We found a use of I outside of BB.  Rename all uses of I that are
+      // outside its block to be uses of the appropriate PHI node etc.  See
+      // ValuesInBlocks with the values we know.
+      unsigned VarNum = SSAUpdate.AddVariable(I->getName(), I->getType());
+      SSAUpdate.AddAvailableValue(VarNum, BB, I);
+      for (Instruction *New : Cloned)
+        SSAUpdate.AddAvailableValue(VarNum, New->getParent(), New);
+
+      while (!UsesToRename.empty())
+        SSAUpdate.AddUse(VarNum, UsesToRename.pop_back_val());
+
+      LLVM_DEBUG(dbgs() << "\n");
+    }
+    // SSAUpdater handles phi placement and renaming uses with the appropriate
+    // value.
+    SSAUpdate.RewriteAllUses(DT);
+  }
+
+  /// Clones a basic block, and adds it to the CFG. This function also includes
+  /// updating phi nodes in the successors of the BB, and remapping uses that
+  /// were defined locally in the cloned BB.
+  BasicBlock *cloneBlockAndUpdatePredecessor(BasicBlock *BB, BasicBlock *PrevBB,
+                                             uint64_t NextState,
+                                             DuplicateBlockMap &DuplicateMap,
+                                             DefMap &NewDefs,
+                                             DomTreeUpdater *DTU) {
+    ValueToValueMapTy VMap;
+    BasicBlock *NewBB = CloneBasicBlock(
+        BB, VMap, ".jt" + std::to_string(NextState), BB->getParent());
+    NewBB->moveAfter(BB);
+
+    for (Instruction &I : *NewBB) {
+      // Do not remap operands of PHINode in case a definition in BB is an
+      // incoming value to a phi in the same block. This incoming value will
+      // be renamed later while restoring SSA.
+      if (isa<PHINode>(&I))
+        continue;
+      RemapInstruction(&I, VMap,
+                       RF_IgnoreMissingLocals | RF_NoModuleLevelChanges);
+    }
+
+    updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
+    updatePredecessor(PrevBB, BB, NewBB, DTU);
+    updateDefMap(NewDefs, VMap);
+
+    // Add all successors to the DominatorTree
+    SmallPtrSet<BasicBlock *, 4> SuccSet;
+    for (auto *SuccBB : successors(NewBB)) {
+      if (SuccSet.insert(SuccBB).second)
+        DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
+    }
+    SuccSet.clear();
+    return NewBB;
+  }
+
+  /// Update the phi nodes in BB's successors. This means creating a new
+  /// incoming value from NewBB with the new instruction wherever there is
+  /// an incoming value from BB.
+  void updateSuccessorPhis(BasicBlock *BB, BasicBlock *ClonedBB,
+                           uint64_t NextState, ValueToValueMapTy &VMap,
+                           DuplicateBlockMap &DuplicateMap) {
+    std::vector<BasicBlock *> BlocksToUpdate;
+
+    // If BB is the last block in the path, we can simply update the one case
+    // successor that will be reached.
+    if (BB == SwitchPaths->getSwitchBlock()) {
+      SwitchInst *Switch = SwitchPaths->getSwitchInst();
+      BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
+      BlocksToUpdate.push_back(NextCase);
+      BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
+      if (ClonedSucc) {
+        BlocksToUpdate.push_back(ClonedSucc);
+      }
+    }
+    // Otherwise update phis in all successors.
+    else {
+      for (BasicBlock *Succ : successors(BB)) {
+        BlocksToUpdate.push_back(Succ);
+
+        // Check if a successor has already been cloned for the particular exit
+        // value. In this case if a successor was already cloned, the phi nodes
+        // in the cloned block should be updated directly.
+        BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
+        if (ClonedSucc) {
+          BlocksToUpdate.push_back(ClonedSucc);
+        }
+      }
+    }
+
+    // If there is a phi with an incoming value from BB, create a new incoming
+    // value for the new predecessor ClonedBB. The value will either be the same
+    // value from BB or a cloned value.
+    for (BasicBlock *Succ : BlocksToUpdate) {
+      for (auto II = Succ->begin(); PHINode *Phi = dyn_cast<PHINode>(II);
+           ++II) {
+        Value *Incoming = Phi->getIncomingValueForBlock(BB);
+        if (Incoming) {
+          if (isa<Constant>(Incoming)) {
+            Phi->addIncoming(Incoming, ClonedBB);
+            continue;
+          }
+          Value *ClonedVal = VMap[Incoming];
+          if (ClonedVal) {
+            Phi->addIncoming(ClonedVal, ClonedBB);
+          } else {
+            Phi->addIncoming(Incoming, ClonedBB);
+          }
+        }
+      }
+    }
+  }
+
+  /// Sets the successor of PrevBB to be NewBB instead of OldBB. Note that all
+  /// other successors are kept as well.
+  void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB,
+                         BasicBlock *NewBB, DomTreeUpdater *DTU) {
+    // When a path is reused, there is a chance that predecessors were already
+    // updated before. Check if the predecessor needs to be updated first.
+    if (!isPredecessor(OldBB, PrevBB))
+      return;
+
+    Instruction *PrevTerm = PrevBB->getTerminator();
+    for (unsigned i = 0; i < PrevTerm->getNumSuccessors(); i++) {
+      if (PrevTerm->getSuccessor(i) == OldBB) {
+        OldBB->removePredecessor(PrevBB, /* KeepOneInputPHIs = */ true);
+        PrevTerm->setSuccessor(i, NewBB);
+      }
+    }
+    DTU->applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
+                       {DominatorTree::Insert, PrevBB, NewBB}});
+  }
+
+  /// Add new value mappings to the DefMap to keep track of all new definitions
+  /// for a particular instruction. These will be used while updating SSA form.
+  void updateDefMap(DefMap &NewDefs, ValueToValueMapTy &VMap) {
+    for (auto Entry : VMap) {
+      Instruction *Inst =
+          dyn_cast<Instruction>(const_cast<Value *>(Entry.first));
+      if (!Inst || !Entry.second || isa<BranchInst>(Inst) ||
+          isa<SwitchInst>(Inst)) {
+        continue;
+      }
+
+      Instruction *Cloned = dyn_cast<Instruction>(Entry.second);
+      if (!Cloned)
+        continue;
+
+      if (NewDefs.find(Inst) == NewDefs.end())
+        NewDefs[Inst] = {Cloned};
+      else
+        NewDefs[Inst].push_back(Cloned);
+    }
+  }
+
+  /// Update the last branch of a particular cloned path to point to the correct
+  /// case successor. Note that this is an optional step and would have been
+  /// done in later optimizations, but it makes the CFG significantly easier to
+  /// work with.
+  void updateLastSuccessor(ThreadingPath &TPath,
+                           DuplicateBlockMap &DuplicateMap,
+                           DomTreeUpdater *DTU) {
+    uint64_t NextState = TPath.getExitValue();
+    BasicBlock *BB = TPath.getPath().back();
+    BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
+
+    // Note multiple paths can end at the same block so check that it is not
+    // updated yet
+    if (!isa<SwitchInst>(LastBlock->getTerminator()))
+      return;
+    SwitchInst *Switch = cast<SwitchInst>(LastBlock->getTerminator());
+    BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
+
+    std::vector<DominatorTree::UpdateType> DTUpdates;
+    SmallPtrSet<BasicBlock *, 4> SuccSet;
+    for (BasicBlock *Succ : successors(LastBlock)) {
+      if (Succ != NextCase && SuccSet.insert(Succ).second)
+        DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
+    }
+
+    Switch->eraseFromParent();
+    BranchInst::Create(NextCase, LastBlock);
+
+    DTU->applyUpdates(DTUpdates);
+  }
+
+  /// After cloning blocks, some of the phi nodes have extra incoming values
+  /// that are no longer used. This function removes them.
+  void cleanPhiNodes(BasicBlock *BB) {
+    // If BB is no longer reachable, remove any remaining phi nodes
+    if (pred_empty(BB)) {
+      std::vector<PHINode *> PhiToRemove;
+      for (auto II = BB->begin(); PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
+        PhiToRemove.push_back(Phi);
+      }
+      for (PHINode *PN : PhiToRemove) {
+        PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
+        PN->eraseFromParent();
+      }
+      return;
+    }
+
+    // Remove any incoming values that come from an invalid predecessor
+    for (auto II = BB->begin(); PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
+      std::vector<BasicBlock *> BlocksToRemove;
+      for (BasicBlock *IncomingBB : Phi->blocks()) {
+        if (!isPredecessor(BB, IncomingBB))
+          BlocksToRemove.push_back(IncomingBB);
+      }
+      for (BasicBlock *BB : BlocksToRemove) {
+        Phi->removeIncomingValue(BB);
+      }
+    }
+  }
+
+  /// Checks if BB was already cloned for a particular next state value. If it
+  /// was then it returns this cloned block, and otherwise null.
+  BasicBlock *getClonedBB(BasicBlock *BB, uint64_t NextState,
+                          DuplicateBlockMap &DuplicateMap) {
+    CloneList ClonedBBs = DuplicateMap[BB];
+
+    // Find an entry in the CloneList with this NextState. If it exists then
+    // return the corresponding BB
+    auto It = llvm::find_if(ClonedBBs, [NextState](const ClonedBlock &C) {
+      return C.State == NextState;
+    });
+    return It != ClonedBBs.end() ? (*It).BB : nullptr;
+  }
+
+  /// Helper to get the successor corresponding to a particular case value for
+  /// a switch statement.
+  BasicBlock *getNextCaseSuccessor(SwitchInst *Switch, uint64_t NextState) {
+    BasicBlock *NextCase = nullptr;
+    for (auto Case : Switch->cases()) {
+      if (Case.getCaseValue()->getZExtValue() == NextState) {
+        NextCase = Case.getCaseSuccessor();
+        break;
+      }
+    }
+    if (!NextCase) {
+      NextCase = Switch->getDefaultDest();
+    }
+    return NextCase;
+  }
+
+  /// Returns true if IncomingBB is a predecessor of BB.
+  bool isPredecessor(BasicBlock *BB, BasicBlock *IncomingBB) {
+    return llvm::find(predecessors(BB), IncomingBB) != pred_end(BB);
+  }
+
+  AllSwitchPaths *SwitchPaths;
+  DominatorTree *DT;
+  std::list<ThreadingPath> TPaths;
+};
+
+bool DFAJumpThreading::runOnFunction(Function &F) {
+  if (skipFunction(F) || DisableThis)
+    return false;
+
+  LLVM_DEBUG(dbgs() << "\nDFA Jump threading: " << F.getName() << "\n");
+
+  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+  std::list<AllSwitchPaths> ThreadableLoops;
+  bool MadeChanges = false;
+
+  for (Function::iterator B = F.begin(), BE = F.end(); B != BE; B++) {
+    if (auto *SI = dyn_cast<SwitchInst>(B->getTerminator())) {
+
+      LLVM_DEBUG(dbgs() << "\nCheck if SwitchInst in BB " << B->getName()
+                        << " is predictable\n");
+      MainSwitch Switch(SI);
+
+      if (!Switch.getInstr())
+        continue;
+
+      LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << B->getName() << " is a "
+                        << "candidate for jump threading\n");
+      LLVM_DEBUG(SI->dump());
+
+      unfoldSelectInstrs(DT, Switch.getSelectInsts());
+      if (!Switch.getSelectInsts().empty())
+        MadeChanges = true;
+
+      AllSwitchPaths SwitchPaths(&Switch);
+      SwitchPaths.run();
+
+      if (SwitchPaths.getNumThreadingPaths() > 0) {
+        ThreadableLoops.push_back(SwitchPaths);
+
+        // For the time being limit this optimization to occurring once in a
+        // function since it can change the CFG significantly. This is not a
+        // strict requirement but it can cause buggy behavior if there is an
+        // overlap of blocks in different opportunities. There is a lot of room
+        // to experiment with catching more opportunities here.
+        break;
+      }
+    }
+  }
+
+  for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
+    TransformFSM Transform(&SwitchPaths, DT);
+    Transform.run();
+    MadeChanges = true;
+  }
+
+  if (IsViewCFG) {
+    F.viewCFG();
+  }
+
+#ifdef EXPENSIVE_CHECKS
+  assert(DT->verify(DominatorTree::VerificationLevel::Full));
+  verifyFunction(F, &dbgs());
+#endif
+
+  return MadeChanges;
+}
+} // end anonymous namespace
diff --git a/llvm/lib/Target/AArch64/AArch64TargetMachine.cpp
 b/llvm/lib/Target/AArch64/AArch64TargetMachine.cpp
--- a/llvm/lib/Target/AArch64/AArch64TargetMachine.cpp
+++ b/llvm/lib/Target/AArch64/AArch64TargetMachine.cpp
@@ -456,6 +456,9 @@
   // ourselves.
   addPass(createAtomicExpandPass());
 
+  if (TM->getOptLevel() >= CodeGenOpt::Default)
+    addPass(createDFAJumpThreadingPass(TM));
+
   // Expand any SVE vector library calls that we can't code generate directly.
   if (EnableSVEIntrinsicOpts && TM->getOptLevel() == CodeGenOpt::Aggressive)
     addPass(createSVEIntrinsicOptsPass());
diff --git a/llvm/test/CodeGen/AArch64/O3-pipeline.ll
 b/llvm/test/CodeGen/AArch64/O3-pipeline.ll
--- a/llvm/test/CodeGen/AArch64/O3-pipeline.ll
+++ b/llvm/test/CodeGen/AArch64/O3-pipeline.ll
@@ -18,6 +18,8 @@
 ; CHECK-NEXT:     Pre-ISel Intrinsic Lowering
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Expand Atomic instructions
+; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       DFA Jump Threading
 ; CHECK-NEXT:     SVE intrinsics optimizations
 ; CHECK-NEXT:       FunctionPass Manager
 ; CHECK-NEXT:         Dominator Tree Construction
diff --git a/llvm/test/CodeGen/AArch64/dfa-constant-propagation.ll b/llvm/test/CodeGen/AArch64/dfa-constant-propagation.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/AArch64/dfa-constant-propagation.ll
@@ -0,0 +1,31 @@
+; RUN: opt -S -dfa-jump-threading -sccp -simplifycfg %s | FileCheck %s
+
+; CHECK: define i32 @test
+; CHECK-NEXT: entry:
+; CHECK-NEXT: ret i32 3
+
+; This test checks that a constant propagation is applied for a basic loop.
+; Related to bug 44679.
+define i32 @test(i32 %a) {
+entry:
+  br label %while.cond
+
+while.cond:
+  %num = phi i32 [ 0, %entry ], [ %add, %case1 ]
+  %state = phi i32 [ 1, %entry ], [ %state.next, %case1 ]
+  switch i32 %state, label %end [
+    i32 1, label %case1
+    i32 2, label %case2
+  ]
+
+case1:
+  %state.next = phi i32 [ 3, %case2 ], [ 2, %while.cond ]
+  %add = add nsw i32 %num, %state
+  br label %while.cond
+
+case2:
+  br label %case1
+
+end:
+  ret i32 %num
+}
\ No newline at end of file
diff --git a/llvm/test/CodeGen/AArch64/dfa-jump-threading-analysis.ll b/llvm/test/CodeGen/AArch64/dfa-jump-threading-analysis.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/AArch64/dfa-jump-threading-analysis.ll
@@ -0,0 +1,107 @@
+; REQUIRES: asserts
+; RUN: opt -S -dfa-jump-threading -debug-only=dfa-jump-threading -disable-output %s 2>&1 | FileCheck %s
+
+; This test checks that the analysis identifies all threadable paths in a
+; simple CFG. A threadable path includes a list of basic blocks, the entry and
+; exit states, and the block that determines the next state.
+; < path of BBs that form a cycle > [ entry, exit, determinator ]
+define i32 @test1(i32 %num) {
+; CHECK: < for.body case1 for.inc > [ 1, 2, for.inc ]
+; CHECK-NEXT: < for.body case2 for.inc > [ 2, 1, for.inc ]
+; CHECK-NEXT: < for.body case2 si.unfold.false for.inc > [ 2, 2, for.inc ]
+entry:
+  br label %for.body
+
+for.body:
+  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
+  switch i32 %state, label %for.inc [
+    i32 1, label %case1
+    i32 2, label %case2
+  ]
+
+case1:
+  br label %for.inc
+
+case2:
+  %cmp = icmp eq i32 %count, 50
+  %sel = select i1 %cmp, i32 1, i32 2
+  br label %for.inc
+
+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
+}
+
+; This test checks that the analysis finds threadable paths in a more
+; complicated CFG. Here the FSM is represented as a nested loop, with
+; fallthrough cases.
+define i32 @test2(i32 %init) {
+; CHECK: < loop.3 case2 > [ 2, 3, loop.3 ]
+; CHECK-NEXT: < loop.3 case2 loop.1.backedge loop.1 loop.2 > [ 2, 1, loop.1 ]
+; CHECK-NEXT: < loop.3 case2 loop.1.backedge si.unfold.false1 loop.1 loop.2 > [ 2, 4, loop.1.backedge ]
+; CHECK-NEXT: < loop.3 case3 loop.2.backedge loop.2 > [ 3, 0, loop.2.backedge ]
+; CHECK-NEXT: < loop.3 case3 case4 loop.2.backedge loop.2 > [ 3, 3, loop.2.backedge ]
+; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge loop.1 loop.2 > [ 3, 1, loop.1 ]
+; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge si.unfold.false1 loop.1 loop.2 > [ 3, 2, loop.1.backedge ]
+; CHECK-NEXT: < loop.3 case4 loop.2.backedge loop.2 > [ 4, 3, loop.2.backedge ]
+; CHECK-NEXT: < loop.3 case4 loop.1.backedge loop.1 loop.2 > [ 4, 1, loop.1 ]
+; CHECK-NEXT: < loop.3 case4 loop.1.backedge si.unfold.false1 loop.1 loop.2 > [ 4, 2, loop.1.backedge ]
+entry:
+  %cmp = icmp eq i32 %init, 0
+  %sel = select i1 %cmp, i32 0, i32 2
+  br label %loop.1
+
+loop.1:
+  %state.1 = phi i32 [ %sel, %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
+}
diff --git a/llvm/test/CodeGen/AArch64/dfa-jump-threading-transform.ll b/llvm/test/CodeGen/AArch64/dfa-jump-threading-transform.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/AArch64/dfa-jump-threading-transform.ll
@@ -0,0 +1,174 @@
+; RUN: opt -S -dfa-jump-threading %s | FileCheck %s
+
+; These tests check that the DFA jump threading transformation is applied
+; properly to two CFGs. It checks that blocks are cloned, branches are updated,
+; and SSA form is restored.
+define i32 @test1(i32 %num) {
+entry:
+  br label %for.body
+
+for.body:
+  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
+  switch i32 %state, label %for.inc [
+    i32 1, label %case1
+    i32 2, label %case2
+  ]
+
+; CHECK: for.body.jt1:
+; CHECK-NEXT: %count.jt1
+; CHECK-NEXT: %state.jt1
+; CHECK-NEXT: br label %case1
+
+; CHECK: for.body.jt2:
+; CHECK-NEXT: %count.jt2
+; CHECK-NEXT: %state.jt2
+; CHECK-NEXT: br label %case2
+
+case1:
+  br label %for.inc
+
+; CHECK: case1:
+; CHECK-NEXT: %count1 = phi i32 [ %count.jt1, %for.body.jt1 ], [ %count, %for.body ]
+
+case2:
+  %cmp = icmp eq i32 %count, 50
+  %sel = select i1 %cmp, i32 1, i32 2
+  br label %for.inc
+
+; CHECK: case2:
+; CHECK-NEXT: %count2 = phi i32 [ %count.jt2, %for.body.jt2 ], [ %count, %for.body ]
+; CHECK: br i1 %cmp, label %for.inc.jt1, label %si.unfold.false
+
+; CHECK: si.unfold.false:
+; CHECK-NEXT: br label %for.inc.jt2
+
+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
+
+; CHECK: for.inc.jt1:
+; CHECK: br i1 %cmp.exit.jt1, label %for.body.jt1, label %for.end
+
+; CHECK: for.inc.jt2:
+; CHECK-NEXT: %count3 = phi i32 [ %count2, %si.unfold.false ], [ %count1, %case1 ]
+; CHECK: br i1 %cmp.exit.jt2, label %for.body.jt2, label %for.end
+
+for.end:
+  ret i32 0
+}
+
+
+define i32 @test2(i32 %init) {
+entry:
+  %cmp = icmp eq i32 %init, 0
+  %sel = select i1 %cmp, i32 0, i32 2
+  br label %loop.1
+
+; CHECK: si.unfold.false:
+; CHECK-NEXT: br label %loop.1
+; CHECK: si.unfold.false1:
+; CHECK-NEXT: br label %loop.1
+; CHECK: si.unfold.false1.jt2:
+; CHECK-NEXT: br label %loop.1.jt2
+; CHECK: si.unfold.false1.jt4:
+; CHECK-NEXT: br label %loop.1.jt4
+
+loop.1:
+  %state.1 = phi i32 [ %sel, %entry ], [ %state.1.be2, %loop.1.backedge ]
+  br label %loop.2
+
+; CHECK: loop.1.jt2:
+; CHECK :br label %loop.2.jt2
+; CHECK: loop.1.jt4:
+; CHECK: br label %loop.2.jt4
+; CHECK: loop.1.jt1:
+; CHECK: br label %loop.2.jt1
+
+loop.2:
+  %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
+  br label %loop.3
+
+; CHECK: loop.2.jt2:
+; CHECK: br label %loop.3.jt2
+; CHECK: loop.2.jt3:
+; CHECK: br label %loop.3.jt3
+; CHECK: loop.2.jt0:
+; CHECK: br label %loop.3.jt0
+; CHECK: loop.2.jt4:
+; CHECK: br label %loop.3.jt4
+; CHECK: loop.2.jt1:
+; CHECK: br label %loop.3.jt1
+
+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
+  ]
+
+; CHECK: loop.3.jt2:
+; CHECK: br label %case2
+; CHECK: loop.3.jt0:
+; CHECK: br label %case0
+; CHECK: loop.3.jt4:
+; CHECK: br label %case4
+; CHECK: loop.3.jt1:
+; CHECK: br label %case1
+; CHECK: loop.3.jt3:
+; CHECK: br label %case3
+
+case2:
+  br i1 %cmp, label %loop.3, label %loop.1.backedge
+
+; CHECK: case2:
+; CHECK-NEXT: br i1 %cmp, label %loop.3.jt3, label %loop.1.backedge.jt4
+
+case3:
+  br i1 %cmp, label %loop.2.backedge, label %case4
+
+; CHECK: case3:
+; CHECK-NEXT: br i1 %cmp, label %loop.2.backedge.jt0, label %case4
+
+case4:
+  br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge
+
+; CHECK: case4:
+; CHECK-NEXT: br i1 %cmp, label %loop.2.backedge.jt3, label %loop.1.backedge.jt2
+
+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
+
+; CHECK: loop.1.backedge.jt2:
+; CHECK: br i1 %cmp, label %loop.1.jt1, label %si.unfold.false1.jt2
+; CHECK: loop.1.backedge.jt4:
+; CHECK: br i1 %cmp, label %loop.1.jt1, label %si.unfold.false1.jt4
+
+loop.2.backedge:
+  %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
+  br label %loop.2
+
+; CHECK: loop.2.backedge.jt3:
+; CHECK: br label %loop.2.jt3
+; CHECK: loop.2.backedge.jt0:
+; CHECK: br label %loop.2.jt0
+
+case0:
+  br label %exit
+
+case1:
+  br label %exit
+
+infloop.i:
+  br label %infloop.i
+
+exit:
+  ret i32 0
+}
diff --git a/llvm/test/CodeGen/AArch64/dfa-unfold-select.ll b/llvm/test/CodeGen/AArch64/dfa-unfold-select.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/AArch64/dfa-unfold-select.ll
@@ -0,0 +1,151 @@
+; RUN: opt -S -dfa-jump-threading %s | FileCheck %s
+
+; These tests check if selects are unfolded properly for jump threading
+; opportunities. There are three different patterns to consider:
+; 1) Both operands are constant and the false branch is unfolded by default
+; 2) One operand is constant and the other is another select to be unfolded. In
+;    this case a single select is sunk to a new block to unfold.
+; 3) Both operands are a select, and both should be sunk to new blocks.
+define i32 @test1(i32 %num) {
+entry:
+  br label %for.body
+
+for.body:
+  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
+  switch i32 %state, label %for.inc [
+    i32 1, label %case1
+    i32 2, label %case2
+  ]
+
+case1:
+  br label %for.inc
+
+case2:
+; CHECK: %cmp = icmp
+; CHECK-NOT: %sel = select i1 %cmp, i32 1, i32 2
+; CHECK-NEXT: br i1 %cmp, label %for.inc
+; CHECK: si.unfold.false
+  %cmp = icmp slt i32 %count, 50
+  %sel = select i1 %cmp, i32 1, i32 2
+  br label %for.inc
+
+; CHECK: si.unfold.false:
+; CHECK-NEXT: br label %for.inc
+
+for.inc:
+; CHECK: %state.next = phi
+; CHECK-NOT: [ %sel, %case2 ]
+  %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
+}
+
+define i32 @test2(i32 %num) {
+entry:
+  br label %for.body
+
+for.body:
+  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
+  switch i32 %state, label %for.inc [
+    i32 1, label %case1
+    i32 2, label %case2
+  ]
+
+case1:
+; CHECK: %cmp.c1 = icmp
+; CHECK: %cmp2.c1 = icmp
+; CHECK-NOT: select i1
+; CHECK-NEXT: br i1 %cmp2.c1
+  %cmp.c1 = icmp slt i32 %count, 50
+  %cmp2.c1 = icmp slt i32 %count, 100
+  %state1.1 = select i1 %cmp.c1, i32 1, i32 2
+  %state1.2 = select i1 %cmp2.c1, i32 %state1.1, i32 3
+  br label %for.inc
+
+case2:
+; CHECK: %cmp.c2 = icmp
+; CHECK: %cmp2.c2 = icmp
+; CHECK-NOT: select i1
+; CHECK-NEXT: br i1 %cmp2.c2
+  %cmp.c2 = icmp slt i32 %count, 50
+  %cmp2.c2 = icmp sgt i32 %count, 100
+  %state2.1 = select i1 %cmp.c2, i32 1, i32 2
+  %state2.2 = select i1 %cmp2.c2, i32 3, i32 %state2.1
+  br label %for.inc
+
+; CHECK: si.unfold.true:
+; CHECK-NEXT: br i1 %cmp.c1
+; CHECK: si.unfold.false:
+; CHECK-NEXT: br i1 %cmp.c2
+; CHECK: si.unfold.false1:
+; CHECK-NEXT: br label %for.inc
+; CHECK: si.unfold.false2:
+; CHECK-NEXT: br label %for.inc
+
+for.inc:
+; CHECK: %state.next = phi
+; CHECK-NOT: [ %state1.2, %case1 ]
+; CHECK-NOT: [ %state2.2, %case2 ]
+  %state.next = phi i32 [ %state1.2, %case1 ], [ %state2.2, %case2 ], [ 1, %for.body ]
+  %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
+}
+
+define i32 @test3(i32 %num) {
+entry:
+  br label %for.body
+
+for.body:
+  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
+  switch i32 %state, label %for.inc [
+    i32 1, label %case1
+    i32 2, label %case2
+  ]
+
+case1:
+  br label %for.inc
+
+case2:
+; CHECK: %cmp.3 = icmp eq i32 %0, 0
+; CHECK-NOT: select i1
+; CHECK-NEXT: br i1 %cmp.3, label %si.unfold.true, label %si.unfold.false
+  %cmp.1 = icmp slt i32 %count, 50
+  %cmp.2 = icmp slt i32 %count, 100
+  %0 = and i32 %count, 1
+  %cmp.3 = icmp eq i32 %0, 0
+  %sel.1 = select i1 %cmp.1, i32 1, i32 2
+  %sel.2 = select i1 %cmp.2, i32 3, i32 4
+  %sel.3 = select i1 %cmp.3, i32 %sel.1, i32 %sel.2
+  br label %for.inc
+
+; CHECK: si.unfold.true:
+; CHECK-NEXT: br i1 %cmp.1
+; CHECK: si.unfold.false:
+; CHECK-NEXT: br i1 %cmp.2
+; CHECK: si.unfold.false1:
+; CHECK-NEXT: br label %for.inc
+; CHECK: si.unfold.false2:
+; CHECK-NEXT: br label %for.inc
+
+for.inc:
+; CHECK: %state.next = phi
+; CHECK-NOT: %case2
+  %state.next = phi i32 [ %sel.3, %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
+}
diff --git a/llvm/tools/opt/opt.cpp
 b/llvm/tools/opt/opt.cpp
--- a/llvm/tools/opt/opt.cpp
+++ b/llvm/tools/opt/opt.cpp
@@ -521,7 +521,7 @@
       "generic-to-nvvm",      "expandmemcmp",
       "loop-reduce",          "lower-amx-type",
       "lower-amx-intrinsics", "polyhedral-info",
-      "replace-with-veclib"};
+      "replace-with-veclib",  "dfa-jump-threading"};
   for (const auto &P : PassNamePrefix)
     if (Pass.startswith(P))
       return true;
@@ -579,6 +579,7 @@
   initializeAtomicExpandPass(Registry);
   initializeRewriteSymbolsLegacyPassPass(Registry);
   initializeWinEHPreparePass(Registry);
+  initializeDFAJumpThreadingPass(Registry);
   initializeDwarfEHPrepareLegacyPassPass(Registry);
   initializeSafeStackLegacyPassPass(Registry);
   initializeSjLjEHPreparePass(Registry);