@@ -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.
@@ -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.
@@ -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 {
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */
@@ -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);
}
}