This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa-lno] Remove O(n) walking of visited nodes
- From: Pop Sébastian <pop at gauvain dot u-strasbg dot fr>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 31 Dec 2003 17:37:27 +0100
- Subject: [tree-ssa-lno] Remove O(n) walking of visited nodes
Hi,
Dan has proposed to flag the phi nodes instead of using the O(n)
search of the visited nodes. The following patch implements this
idea.
2003-12-31 Sebastian Pop <s.pop@laposte.net>
Daniel Berlin <dberlin@dberlin.org>
* tree-phinodes.c (create_phi_node): Initialise PHI_MARKED to 0.
* tree-scalar-evolution.c (already_visited,
node_already_visited_by_ssa_path): Removed.
(analyze_evolution): Remove initialisation of already_visited.
(construct_schedule): idem.
(monev_follow_ssa_edge): use PHI_MARKED for deciding whether
to analyze the phi-node.
(follow_ssa_edge_and_record_dependences_rec): idem.
* tree.h (PHI_MARKED): New macro.
(tree_phi_node): Add a field marked.
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-phinodes.c,v
retrieving revision 1.1.2.8
diff -d -u -p -r1.1.2.8 tree-phinodes.c
--- tree-phinodes.c 8 Dec 2003 12:58:22 -0000 1.1.2.8
+++ tree-phinodes.c 31 Dec 2003 14:11:30 -0000
@@ -295,6 +295,7 @@ create_phi_node (tree var, basic_block b
/* This is a new phi node, so note that is has not yet been
rewritten. */
PHI_REWRITTEN (phi) = 0;
+ PHI_MARKED (phi) = 0;
/* Add the new PHI node to the list of PHI nodes for block BB. */
TREE_CHAIN (phi) = phi_nodes (bb);
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.1
diff -d -u -p -r1.1.2.1 tree-scalar-evolution.c
--- tree-scalar-evolution.c 27 Dec 2003 05:42:48 -0000 1.1.2.1
+++ tree-scalar-evolution.c 31 Dec 2003 14:11:31 -0000
@@ -386,30 +386,6 @@ insert_ssa_name_in_imperative_list (tree
-/* A quick hack for avoiding infinite recursion. For example, in
- gcc/gcc/calls.c:expand_call, we have the following phi nodes:
-
- "normal_call_insns_8 = PHI <0B(380), normal_call_insns_9(782)>;
- normal_call_insns_9 = PHI <normal_call_insns_8(773), T.1529_2087(777), T.1529_2087(778)>;"
-
- This results in a loop in the PHI walking. By the way, is this
- normally allowed in the SSA representation? */
-
-static varray_type already_visited;
-static bool node_already_visited_by_ssa_path (tree node);
-
-static bool
-node_already_visited_by_ssa_path (tree node)
-{
- if (tree_is_in_varray_tree_p (node, already_visited))
- return true;
- else
- {
- VARRAY_PUSH_TREE (already_visited, node);
- return false;
- }
-}
-
/* Analyze the evolution of a SSA_NAME in the LOOP_NEST. */
static void
@@ -435,8 +411,6 @@ analyze_evolution (tree ssa_name_to_anal
fprintf (stderr, " ssa_name_to_analyze = ");
debug_generic_expr (ssa_name_to_analyze));
- VARRAY_TREE_INIT (already_visited, 5, "already_visited");
-
/* The variable has a phi node in this loop: the variable is thus
"updated" at every iteration of this loop. */
if (loop_phi_node)
@@ -455,7 +429,6 @@ analyze_evolution (tree ssa_name_to_anal
determine_whether_ssa_name_is_symbolic_parameter
(ssa_name_to_analyze, loop_nest);
- varray_clear (already_visited);
DBG_S (fprintf (stderr, ")\n"));
}
@@ -926,9 +899,7 @@ monev_follow_ssa_edge (tree rdef,
if (rdef == NULL_TREE
|| TREE_CODE (rdef) == NOP_EXPR
/* End the recursion when the halting_phi node is reached. */
- || rdef == halting_phi
- /* Avoid infinite recursion on bizarre cases. */
- || node_already_visited_by_ssa_path (rdef))
+ || rdef == halting_phi)
return;
/* DBG_S (debug_generic_expr (rdef)); */
@@ -946,6 +917,21 @@ monev_follow_ssa_edge (tree rdef,
switch (TREE_CODE (rdef))
{
case PHI_NODE:
+
+ /* Avoid recursion when the phi-nodes contain SCCs. For
+ example, in gcc/gcc/calls.c:expand_call, we have the
+ following phi nodes:
+
+ "normal_call_insns_8 = PHI <0B(380), normal_call_insns_9(782)>;
+ normal_call_insns_9 = PHI <normal_call_insns_8(773), T.1529_2087(777),
+ T.1529_2087(778)>;"
+ */
+ if (PHI_MARKED (rdef) == 1)
+ return;
+
+ else
+ PHI_MARKED (rdef) = 1;
+
/* Determine whether the PHI_NODE is a loop phi or a conditional
phi. */
if (rdef_depth > halting_depth)
@@ -1003,8 +989,8 @@ monev_follow_ssa_edge (tree rdef,
}
analyze_evolution_in_loop (rdef, halting_num);
- break;
}
+
else
/* RDEF is a CONDITION-phi-node.
@@ -1018,6 +1004,9 @@ monev_follow_ssa_edge (tree rdef,
of paths that differ, ie. do not analyze n times outside
the if-body. */
merge_branches_of_condition_phi_node_in_loop (rdef, halting_phi);
+
+ /* Reset the marker after the analysis. */
+ PHI_MARKED (rdef) = 0;
break;
case MODIFY_EXPR:
@@ -2503,12 +2492,10 @@ construct_schedule (varray_type imperati
VARRAY_GENERIC_PTR (imperative_vars, i);
DBG_SCHEDULE_S (dump_schedule_elt (stderr, sched_elt));
- VARRAY_TREE_INIT (already_visited, 37, "already_visited");
record_dependences_for_ssa_name (SCHED_LOOP_NEST (sched_elt),
VARRAY_TREE (SCHED_SCC (sched_elt), 0),
sdd_graph,
complete_imperative_list);
- varray_clear (already_visited);
}
DBG_SCHEDULE_S (debug_schedule (complete_imperative_list));
@@ -2949,9 +2936,7 @@ follow_ssa_edge_and_record_dependences_r
|| halting_phi == NULL_TREE
|| TREE_CODE (rdef) == NOP_EXPR
/* End the recursion when the halting_phi node is reached. */
- || rdef == halting_phi
- /* Avoid infinite recursion on bizarre cases. */
- || node_already_visited_by_ssa_path (rdef))
+ || rdef == halting_phi)
return;
DBG_SDD_S (debug_generic_expr (rdef));
@@ -2962,6 +2947,14 @@ follow_ssa_edge_and_record_dependences_r
switch (TREE_CODE (rdef))
{
case PHI_NODE:
+
+ /* Avoid recursion when the phi-nodes contain SCCs. */
+ if (PHI_MARKED (rdef) == 1)
+ return;
+
+ else
+ PHI_MARKED (rdef) = 1;
+
if (rdef_depth > halting_depth)
{
/* This is an inner loop phi. */
@@ -3017,6 +3010,9 @@ follow_ssa_edge_and_record_dependences_r
}
}
}
+
+ /* Reset the marker after the analysis. */
+ PHI_MARKED (rdef) = 0;
break;
case MODIFY_EXPR:
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.154.2.1
diff -d -u -p -r1.342.2.154.2.1 tree.h
--- tree.h 27 Dec 2003 05:42:48 -0000 1.342.2.154.2.1
+++ tree.h 31 Dec 2003 14:11:34 -0000
@@ -1059,6 +1059,7 @@ struct tree_ssa_name GTY(())
/* Nonzero if the PHI node was rewritten by a previous pass through the
SSA renamer. */
#define PHI_REWRITTEN(NODE) PHI_NODE_CHECK (NODE)->phi.rewritten
+#define PHI_MARKED(NODE) PHI_NODE_CHECK (NODE)->phi.marked
#define PHI_NUM_ARGS(NODE) PHI_NODE_CHECK (NODE)->phi.num_args
#define PHI_ARG_CAPACITY(NODE) PHI_NODE_CHECK (NODE)->phi.capacity
#define PHI_ARG_ELT(NODE, I) PHI_NODE_ELT_CHECK (NODE, I)
@@ -1082,7 +1083,11 @@ struct tree_phi_node GTY(())
/* Nonzero if the PHI node was rewritten by a previous pass through the
SSA renamer. */
- int rewritten;
+ unsigned int rewritten:1;
+
+ /* Nonzero if the PHI node has already been walked by the scalar
+ evolution analyzer. */
+ unsigned int marked:1;
struct phi_arg_d GTY ((length ("((tree)&%h)->phi.capacity"))) a[1];
};