diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 92f7aaead74..f01696696bf 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -14754,6 +14754,13 @@ optimizing.
 Maximum number of statements allowed in a block that needs to be
 duplicated when threading jumps.
 
+@item max-jump-thread-paths
+The maximum number of paths to consider when searching for jump threading
+opportunities.  When arriving at a block incoming edges are only considered
+if the number of paths to be searched sofar multiplied by the incoming
+edge degree does not exhaust the specified maximum number of paths to
+consider.
+
 @item max-fields-for-field-sensitive
 Maximum number of fields in a structure treated in
 a field sensitive manner during pointer analysis.
diff --git a/gcc/params.opt b/gcc/params.opt
index 2f9c9cf27dd..132987343c6 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -582,6 +582,10 @@ Bound on the number of iterations the brute force # of iterations analysis algor
 Common Joined UInteger Var(param_max_jump_thread_duplication_stmts) Init(15) Param Optimization
 Maximum number of statements allowed in a block that needs to be duplicated when threading jumps.
 
+-param=max-jump-thread-paths=
+Common Joined UInteger Var(param_max_jump_thread_paths) Init(64) IntegerRange(1, 65536) Param Optimization
+Search space limit for the backwards jump threader.
+
 -param=max-last-value-rtl=
 Common Joined UInteger Var(param_max_last_value_rtl) Init(10000) Param Optimization
 The maximum number of RTL nodes that can be recorded as combiner's last value.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
index aa06db5e223..47b8fdfa29a 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
@@ -11,7 +11,7 @@
    to change decisions in switch expansion which in turn can expose new
    jump threading opportunities.  Skip the later tests on aarch64.  */
 /* { dg-final { scan-tree-dump-not "Jumps threaded"  "dom3" { target { ! aarch64*-*-* } } } } */
-/* { dg-final { scan-tree-dump "Jumps threaded: 8"  "thread2" { target { ! aarch64*-*-* } } } } */
+/* { dg-final { scan-tree-dump "Jumps threaded: 9"  "thread2" { target { ! aarch64*-*-* } } } } */
 /* { dg-final { scan-tree-dump "Jumps threaded: 18"  "thread2" { target { aarch64*-*-* } } } } */
 
 enum STATE {
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c
new file mode 100644
index 00000000000..f96170b073d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-threadfull1-details" } */
+
+int res;
+void foo (int a, int b, int c, int d, int e)
+{
+  if (a > 100)
+    res = 3;
+  if (b != 5)
+    res = 5;
+  if (c == 29)
+    res = 7;
+  if (d < 2)
+    res = 9;
+  /* Accounting whoes makes this not catched.  */
+#if 0
+  if (e != 37)
+    res = 11;
+#endif
+  if (a < 10)
+    res = 13;
+}
+
+/* { dg-final { scan-tree-dump "SUCCESS" "threadfull1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c
new file mode 100644
index 00000000000..94ee6666788
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c
@@ -0,0 +1,7 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-threadfull1-details --param max-jump-thread-paths=15" } */
+
+#include "ssa-thread-16.c"
+
+/* With limiting the search space we should no longer consider this path.  */
+/* { dg-final { scan-tree-dump-not "SUCCESS" "threadfull1" } } */
diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index 0acbfb0624c..bb1ef514abf 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -90,7 +90,7 @@ private:
   bool debug_counter ();
   edge maybe_register_path ();
   void maybe_register_path_dump (edge taken_edge);
-  void find_paths_to_names (basic_block bb, bitmap imports);
+  void find_paths_to_names (basic_block bb, bitmap imports, unsigned);
   edge find_taken_edge (const vec<basic_block> &path);
   edge find_taken_edge_cond (const vec<basic_block> &path, gcond *);
   edge find_taken_edge_switch (const vec<basic_block> &path, gswitch *);
@@ -337,9 +337,12 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path,
 // INTERESTING bitmap, and register any such paths.
 //
 // BB is the current path being processed.
+//
+// OVERALL_PATHS is the search space up to this block
 
 void
-back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
+back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
+				    unsigned overall_paths)
 {
   if (m_visited_bbs.add (bb))
     return;
@@ -352,8 +355,10 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
 	  || maybe_register_path ()))
     ;
 
-  // Continue looking for ways to extend the path
-  else
+  // Continue looking for ways to extend the path but limit the
+  // search space along a branch
+  else if ((overall_paths = overall_paths * EDGE_COUNT (bb->preds))
+	   <= (unsigned)param_max_jump_thread_paths)
     {
       // For further greedy searching we want to remove interesting
       // names defined in BB but add ones on the PHI edges for the
@@ -407,7 +412,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
 			unwind.quick_push (def);
 		      }
 		}
-	      find_paths_to_names (e->src, new_interesting);
+	      find_paths_to_names (e->src, new_interesting, overall_paths);
 	      // Restore new_interesting.  We leave m_imports alone since
 	      // we do not prune defs in BB from it and separately keeping
 	      // track of which bits to unwind isn't worth the trouble.
@@ -417,6 +422,9 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
 	    }
 	}
     }
+  else if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "  FAIL: Search space limit %d reached.\n",
+	     param_max_jump_thread_paths);
 
   // Reset things to their original state.
   m_path.pop ();
@@ -447,7 +455,7 @@ back_threader::find_paths (basic_block bb, tree name)
 
       auto_bitmap interesting;
       bitmap_copy (interesting, m_imports);
-      find_paths_to_names (bb, interesting);
+      find_paths_to_names (bb, interesting, 1);
     }
 }
 
