@@ -49,5 +49,5 @@ L23:
/* We should thread the backedge to the top of the loop; ie we only
execute the if (expr->common.code != 142) test once per loop
iteration. */
-/* { dg-final { scan-tree-dump-times "FSM jump thread" 1 "thread4" } } */
+/* { dg-final { scan-tree-dump-times "jump thread" 1 "thread4" } } */
@@ -32,9 +32,9 @@ foo (int N, int c, int b, int *a)
pt--;
}
-/* There are 4 FSM jump threading opportunities, all of which will be
+/* There are 4 jump threading opportunities, all of which will be
realized, which will eliminate testing of FLAG, completely. */
-/* { dg-final { scan-tree-dump-times "Registering FSM" 4 "thread1"} } */
+/* { dg-final { scan-tree-dump-times "Registering jump" 4 "thread1"} } */
/* There should be no assignments or references to FLAG, verify they're
eliminated as early as possible. */
@@ -37,5 +37,5 @@ c_finish_omp_clauses (tree clauses)
}
}
-/* There are 3 FSM jump threading opportunities. */
-/* { dg-final { scan-tree-dump-times "Registering FSM" 3 "thread1"} } */
+/* There are 3 jump threading opportunities. */
+/* { dg-final { scan-tree-dump-times "Registering jump" 3 "thread1"} } */
@@ -1,7 +1,7 @@
/* { dg-do compile { target sparc*-*-* i?86-*-* x86_64-*-* } } */
/* { dg-options "-O2 -fdump-tree-thread1-details -fdisable-tree-ethread" } */
-/* { dg-final { scan-tree-dump "FSM did not thread around loop and would copy too many statements" "thread1" } } */
+/* { dg-final { scan-tree-dump "Did not thread around loop and would copy too many statements" "thread1" } } */
typedef __builtin_va_list __gnuc_va_list;
@@ -1,12 +1,12 @@
/* { dg-do compile } */
/* { dg-options "-O2 -w -fdump-tree-vrp1-details -fdump-tree-vrp2-details -fdump-tree-dom2-details -fdump-tree-dom3-details" } */
-/* All the threads found by the FSM threader should have too
- many statements to be profitable. */
-/* { dg-final { scan-tree-dump-not "Registering FSM " "dom2"} } */
-/* { dg-final { scan-tree-dump-not "Registering FSM " "dom3"} } */
-/* { dg-final { scan-tree-dump-not "Registering FSM " "vrp1"} } */
-/* { dg-final { scan-tree-dump-not "Registering FSM " "vrp2"} } */
+/* All the threads found by the threader should have too many
+ statements to be profitable. */
+/* { dg-final { scan-tree-dump-not "Registering jump " "dom2"} } */
+/* { dg-final { scan-tree-dump-not "Registering jump " "dom3"} } */
+/* { dg-final { scan-tree-dump-not "Registering jump " "vrp1"} } */
+/* { dg-final { scan-tree-dump-not "Registering jump " "vrp2"} } */
typedef _Bool bool;
typedef unsigned char uint8_t;
@@ -25,5 +25,5 @@ main (int argc)
if (b)
test2 ();
}
-/* { dg-final { scan-tree-dump-times "Registering FSM jump thread" 2 "thread3" } } */
+/* { dg-final { scan-tree-dump-times "Registering jump thread" 2 "thread3" } } */
/* { dg-final { scan-tree-dump-not "Invalid sum" "thread3" } } */
@@ -1,6 +1,6 @@
/* { dg-do compile } */
/* { dg-additional-options "-O2 -fdump-tree-vrp-details -fdump-tree-thread1-details --param logical-op-non-short-circuit=1" } */
-/* { dg-final { scan-tree-dump-times "Registering FSM jump" 8 "thread1" } } */
+/* { dg-final { scan-tree-dump-times "Registering jump" 8 "thread1" } } */
/* Copied from ssa-thread-14. */
@@ -21,5 +21,5 @@
condition.
All the cases are picked up by VRP1 as jump threads. */
-/* { dg-final { scan-tree-dump-times "Registering FSM jump" 6 "thread1" } } */
+/* { dg-final { scan-tree-dump-times "Registering jump" 6 "thread1" } } */
/* { dg-final { scan-tree-dump-times "Threaded" 2 "vrp1" } } */
@@ -1,8 +1,8 @@
/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-thread1-details -fdump-tree-thread3-details" } */
-/* { dg-final { scan-tree-dump-times "Registering FSM jump" 6 "thread1" } } */
-/* { dg-final { scan-tree-dump-times "Registering FSM jump" 1 "thread3" } } */
+/* { dg-final { scan-tree-dump-times "Registering jump" 6 "thread1" } } */
+/* { dg-final { scan-tree-dump-times "Registering jump" 1 "thread3" } } */
int sum0, sum1, sum2, sum3;
int foo (char *s, char **ret)
@@ -1,8 +1,7 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-thread2-details -fdump-tree-thread3-details -fdump-tree-thread4-details -fno-finite-loops --param early-inlining-insns=14 -fno-inline-functions" } */
-/* { dg-final { scan-tree-dump "FSM" "thread2" } } */
-/* { dg-final { scan-tree-dump "FSM" "thread3" } } */
-/* { dg-final { scan-tree-dump "FSM" "thread4" } } */
+/* { dg-options "-O2 -fdump-tree-thread3-details -fdump-tree-thread4-details -fno-finite-loops --param early-inlining-insns=14 -fno-inline-functions" } */
+/* { dg-final { scan-tree-dump "Registering jump thread" "thread3" } } */
+/* { dg-final { scan-tree-dump "Registering jump thread" "thread4" } } */
typedef struct bitmap_head_def *bitmap;
typedef const struct bitmap_head_def *const_bitmap;
@@ -1,6 +1,6 @@
/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-ethread-details" } */
-/* { dg-final { scan-tree-dump "FSM" "ethread" } } */
+/* { dg-final { scan-tree-dump "Registering jump thread" "ethread" } } */
typedef struct rtx_def *rtx;
typedef const struct rtx_def *const_rtx;
@@ -593,7 +593,7 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
if (m_path.length () > (unsigned) param_max_fsm_thread_length)
{
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " FAIL: FSM jump-thread path not considered: "
+ fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"the number of basic blocks on the path "
"exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
return false;
@@ -768,7 +768,7 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
if (path_crosses_loops)
{
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " FAIL: FSM jump-thread path not considered: "
+ fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"the path crosses loops.\n");
return false;
}
@@ -784,7 +784,7 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
if (n_insns >= param_max_fsm_thread_path_insns)
{
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " FAIL: FSM jump-thread path not considered: "
+ fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"the number of instructions on the path "
"exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
return false;
@@ -793,7 +793,7 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
else if (!m_speed_p && n_insns > 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " FAIL: FSM jump-thread path not considered: "
+ fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"duplication of %i insns is needed and optimizing for size.\n",
n_insns);
return false;
@@ -818,25 +818,22 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
- " FAIL: FSM would create irreducible loop without threading "
+ " FAIL: Would create irreducible loop without threading "
"multiway branch.\n");
return false;
}
- /* If this path does not thread through the loop latch, then we are
- using the FSM threader to find old style jump threads. This
- is good, except the FSM threader does not re-use an existing
- threading path to reduce code duplication.
-
- So for that case, drastically reduce the number of statements
- we are allowed to copy. */
+ /* The generic copier used by the backthreader does not re-use an
+ existing threading path to reduce code duplication. So for that
+ case, drastically reduce the number of statements we are allowed
+ to copy. */
if (!(threaded_through_latch && threaded_multiway_branch)
&& (n_insns * param_fsm_scale_path_stmts
>= param_max_jump_thread_duplication_stmts))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
- " FAIL: FSM did not thread around loop and would copy too "
+ " FAIL: Did not thread around loop and would copy too "
"many statements.\n");
return false;
}
@@ -849,7 +846,7 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
- " FAIL: FSM Thread through multiway branch without threading "
+ " FAIL: Thread through multiway branch without threading "
"a multiway branch.\n");
return false;
}
@@ -865,7 +862,7 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
- " FAIL: FSM Thread through latch before loop opts would create non-empty latch\n");
+ " FAIL: Thread through latch before loop opts would create non-empty latch\n");
return false;
}
@@ -887,8 +884,8 @@ back_threader_registry::register_path (const vec<basic_block> &m_path,
if (m_threaded_paths > m_max_allowable_paths)
{
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " FAIL: FSM jump-thread path not considered: "
- "the number of previously recorded FSM paths to "
+ fprintf (dump_file, " FAIL: Jump-thread path not considered: "
+ "the number of previously recorded paths to "
"thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
return false;
}
@@ -896,7 +893,8 @@ back_threader_registry::register_path (const vec<basic_block> &m_path,
vec<jump_thread_edge *> *jump_thread_path
= m_lowlevel_registry.allocate_thread_path ();
- /* Record the edges between the blocks in PATH. */
+ // The generic copier ignores the edge type. We can build the
+ // thread edges with any type.
for (unsigned int j = 0; j + 1 < m_path.length (); j++)
{
basic_block bb1 = m_path[m_path.length () - j - 1];
@@ -905,11 +903,10 @@ back_threader_registry::register_path (const vec<basic_block> &m_path,
edge e = find_edge (bb1, bb2);
gcc_assert (e);
jump_thread_edge *x
- = m_lowlevel_registry.allocate_thread_edge (e, EDGE_FSM_THREAD);
+ = m_lowlevel_registry.allocate_thread_edge (e, EDGE_COPY_SRC_BLOCK);
jump_thread_path->safe_push (x);
}
- /* Add the edge taken when the control variable has value ARG. */
jump_thread_edge *x
= m_lowlevel_registry.allocate_thread_edge (taken_edge,
EDGE_NO_COPY_SRC_BLOCK);
@@ -456,17 +456,17 @@ jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
= simplify_control_stmt_condition_1 (e, stmt, op0, cond_code, op1,
recursion_limit);
- /* If we were testing an integer/pointer against a constant, then
- we can use the FSM code to trace the value of the SSA_NAME. If
- a value is found, then the condition will collapse to a constant.
+ /* If we were testing an integer/pointer against a constant,
+ then we can trace the value of the SSA_NAME. If a value is
+ found, then the condition will collapse to a constant.
Return the SSA_NAME we want to trace back rather than the full
- expression and give the FSM threader a chance to find its value. */
+ expression and give the threader a chance to find its value. */
if (cached_lhs == NULL)
{
/* Recover the original operands. They may have been simplified
using context sensitive equivalences. Those context sensitive
- equivalences may not be valid on paths found by the FSM optimizer. */
+ equivalences may not be valid on paths. */
tree op0 = gimple_cond_lhs (stmt);
tree op1 = gimple_cond_rhs (stmt);
@@ -167,10 +167,11 @@ jump_thread_path_allocator::allocate_thread_path ()
return new (r) vec<jump_thread_edge *> ();
}
-jt_path_registry::jt_path_registry ()
+jt_path_registry::jt_path_registry (bool backedge_threads)
{
m_paths.create (5);
m_num_threaded_edges = 0;
+ m_backedge_threads = backedge_threads;
}
jt_path_registry::~jt_path_registry ()
@@ -179,6 +180,7 @@ jt_path_registry::~jt_path_registry ()
}
fwd_jt_path_registry::fwd_jt_path_registry ()
+ : jt_path_registry (/*backedge_threads=*/false)
{
m_removed_edges = new hash_table<struct removed_edges> (17);
m_redirection_data = NULL;
@@ -189,6 +191,11 @@ fwd_jt_path_registry::~fwd_jt_path_registry ()
delete m_removed_edges;
}
+back_jt_path_registry::back_jt_path_registry ()
+ : jt_path_registry (/*backedge_threads=*/true)
+{
+}
+
jump_thread_edge *
jt_path_registry::allocate_thread_edge (edge e, jump_thread_edge_type t)
{
@@ -210,9 +217,8 @@ dump_jump_thread_path (FILE *dump_file,
bool registering)
{
fprintf (dump_file,
- " %s%s jump thread: (%d, %d) incoming edge; ",
+ " %s jump thread: (%d, %d) incoming edge; ",
(registering ? "Registering" : "Cancelling"),
- (path[0]->type == EDGE_FSM_THREAD ? " FSM": ""),
path[0]->e->src->index, path[0]->e->dest->index);
for (unsigned int i = 1; i < path.length (); i++)
@@ -224,20 +230,24 @@ dump_jump_thread_path (FILE *dump_file,
if (path[i]->e == NULL)
continue;
- if (path[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
- fprintf (dump_file, " (%d, %d) joiner; ",
- path[i]->e->src->index, path[i]->e->dest->index);
- if (path[i]->type == EDGE_COPY_SRC_BLOCK)
- fprintf (dump_file, " (%d, %d) normal;",
- path[i]->e->src->index, path[i]->e->dest->index);
- if (path[i]->type == EDGE_NO_COPY_SRC_BLOCK)
- fprintf (dump_file, " (%d, %d) nocopy;",
- path[i]->e->src->index, path[i]->e->dest->index);
- if (path[0]->type == EDGE_FSM_THREAD)
- fprintf (dump_file, " (%d, %d) ",
- path[i]->e->src->index, path[i]->e->dest->index);
+ fprintf (dump_file, " (%d, %d) ",
+ path[i]->e->src->index, path[i]->e->dest->index);
+ switch (path[i]->type)
+ {
+ case EDGE_COPY_SRC_JOINER_BLOCK:
+ fprintf (dump_file, "joiner");
+ break;
+ case EDGE_COPY_SRC_BLOCK:
+ fprintf (dump_file, "normal");
+ break;
+ case EDGE_NO_COPY_SRC_BLOCK:
+ fprintf (dump_file, "nocopy");
+ break;
+ default:
+ gcc_unreachable ();
+ }
}
- fputc ('\n', dump_file);
+ fprintf (dump_file, "; \n");
}
DEBUG_FUNCTION void
@@ -2256,8 +2266,8 @@ back_jt_path_registry::rewire_first_differing_edge (unsigned path_num,
return true;
}
-/* After an FSM path has been jump threaded, adjust the remaining FSM
- paths that are subsets of this path, so these paths can be safely
+/* After a path has been jump threaded, adjust the remaining paths
+ that are subsets of this path, so these paths can be safely
threaded within the context of the new threaded path.
For example, suppose we have just threaded:
@@ -2293,10 +2303,9 @@ back_jt_path_registry::adjust_paths_after_duplication (unsigned curr_path_num)
continue;
}
/* Make sure the candidate to adjust starts with the same path
- as the recently threaded path and is an FSM thread. */
+ as the recently threaded path. */
vec<jump_thread_edge *> *cand_path = m_paths[cand_path_num];
- if ((*cand_path)[0]->type != EDGE_FSM_THREAD
- || (*cand_path)[0]->e != (*curr_path)[0]->e)
+ if ((*cand_path)[0]->e != (*curr_path)[0]->e)
{
++cand_path_num;
continue;
@@ -2350,16 +2359,11 @@ back_jt_path_registry::adjust_paths_after_duplication (unsigned curr_path_num)
m_paths.unordered_remove (cand_path_num);
continue;
}
- if ((*cand_path)[j]->type != EDGE_FSM_THREAD)
- {
- /* If all the EDGE_FSM_THREADs are common, all that's
- left is the final EDGE_NO_COPY_SRC_BLOCK. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Dropping illformed candidate.\n");
- }
- else
- /* Otherwise, just remove the redundant sub-path. */
+ /* Otherwise, just remove the redundant sub-path. */
+ if (cand_path->length () - j > 1)
cand_path->block_remove (0, j);
+ else if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Dropping illformed candidate.\n");
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -2616,8 +2620,6 @@ back_jt_path_registry::update_cfg (bool /*peel_loop_headers*/)
vec<jump_thread_edge *> *path = m_paths[0];
edge entry = (*path)[0]->e;
- gcc_checking_assert ((*path)[0]->type == EDGE_FSM_THREAD);
-
/* Do not jump-thread twice from the same starting edge.
Previously we only checked that we weren't threading twice
@@ -2631,7 +2633,7 @@ back_jt_path_registry::update_cfg (bool /*peel_loop_headers*/)
various reasons. So check it first. */
|| !valid_jump_thread_path (path))
{
- /* Remove invalid FSM jump-thread paths. */
+ /* Remove invalid jump-thread paths. */
cancel_thread (path, "Avoiding threading twice from same edge");
m_paths.unordered_remove (0);
continue;
@@ -2782,10 +2784,7 @@ jt_path_registry::register_jump_thread (vec<jump_thread_edge *> *path)
return false;
}
- /* Only the FSM threader is allowed to thread across
- backedges in the CFG. */
- if (flag_checking
- && (*path)[0]->type != EDGE_FSM_THREAD)
+ if (flag_checking && !m_backedge_threads)
gcc_assert (((*path)[i]->e->flags & EDGE_DFS_BACK) == 0);
}
@@ -24,7 +24,6 @@ along with GCC; see the file COPYING3. If not see
enum jump_thread_edge_type
{
EDGE_START_JUMP_THREAD,
- EDGE_FSM_THREAD,
EDGE_COPY_SRC_BLOCK,
EDGE_COPY_SRC_JOINER_BLOCK,
EDGE_NO_COPY_SRC_BLOCK
@@ -63,7 +62,7 @@ private:
class jt_path_registry
{
public:
- jt_path_registry ();
+ jt_path_registry (bool backedge_threads);
virtual ~jt_path_registry ();
bool register_jump_thread (vec<jump_thread_edge *> *);
bool thread_through_all_blocks (bool peel_loop_headers);
@@ -77,6 +76,9 @@ protected:
private:
virtual bool update_cfg (bool peel_loop_headers) = 0;
jump_thread_path_allocator m_allocator;
+ // True if threading through back edges is allowed. This is only
+ // allowed in the generic copier in the backward threader.
+ bool m_backedge_threads;
DISABLE_COPY_AND_ASSIGN (jt_path_registry);
};
@@ -107,6 +109,8 @@ private:
class back_jt_path_registry : public jt_path_registry
{
+public:
+ back_jt_path_registry ();
private:
bool update_cfg (bool peel_loop_headers) override;
void adjust_paths_after_duplication (unsigned curr_path_num);