This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Lazy updating of stmt operands
Hello,
> >> > tree-dfa.c:compute_immediate_uses()
> >>
> >> Which needs to pass through every single statement in the program. Not
> >> really terribly efficient.
> >>
> >*shrug*, it's used by SSA-CCP. Since def-use edges are only needed by
> >some passes, I don't think it would be worth our while trying to
> >maintain them in get_stmt_operands.
> >
> >But I'm ready to be convinced otherwise. Say, with an implementation
> >comparing both approaches with timings over a reasonable code base (a
> >typical GCC bootstrap or one of the compile-time related PRs).
> IMHO, when we have the need, then we'll expand on the immediate uses
> interface -- either by having a way to incrementally update it, or
> rebuild it.
>
> While it's nice to think about a world where you always have immediate uses,
> you end up with FUD chains if you do that -- with ultimately a tangled nest
> of pointers that is bloody impossible to work with in the real world.
here is the patch. It increases time for compiling preprocessed gcc
sources from 3m43.734s to 3m47.967s. It does not use interface of
immediate uses, since that is not well suited for updating; instead it
just keeps lists of uses for each ssa name. The old interface and ccp
that uses it are not changed by the patch, so in fact the cost would
be a bit smaller.
It turned out to be simpler not to require the immediate uses to be
updated all the time; just to keep the list of statements that were
modified and to update it when get_stmt_operands is called.
The cost is not insignificant, so we probably don't want to do this
unless I am able to cut it down or we really need it.
Zdenek
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.153
diff -c -3 -p -r1.903.2.153 Makefile.in
*** Makefile.in 8 Dec 2003 13:52:58 -0000 1.903.2.153
--- Makefile.in 11 Dec 2003 09:00:59 -0000
*************** tree-ssa-dom.o : tree-ssa-dom.c $(TREE_F
*** 1558,1564 ****
errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
$(BASIC_BLOCK_H) domwalk.h
tree-ssanames.o : tree-ssanames.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
! $(TM_H) $(TREE_H) varray.h $(GGC_H) gt-tree-ssanames.h
tree-phinodes.o : tree-phinodes.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(TM_H) $(TREE_H) varray.h $(GGC_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
gt-tree-phinodes.h $(RTL_H)
--- 1558,1564 ----
errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
$(BASIC_BLOCK_H) domwalk.h
tree-ssanames.o : tree-ssanames.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
! $(TM_H) $(TREE_H) varray.h $(GGC_H) gt-tree-ssanames.h tree-flow.h
tree-phinodes.o : tree-phinodes.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(TM_H) $(TREE_H) varray.h $(GGC_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
gt-tree-phinodes.h $(RTL_H)
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.235
diff -c -3 -p -r1.1.4.235 tree-cfg.c
*** tree-cfg.c 11 Dec 2003 01:29:50 -0000 1.1.4.235
--- tree-cfg.c 11 Dec 2003 09:00:59 -0000
*************** void
*** 2446,2452 ****
bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
! modify_stmt (t);
tsi_link_before (&i->tsi, t, m);
}
--- 2446,2452 ----
bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
! stmt_added (t);
tsi_link_before (&i->tsi, t, m);
}
*************** void
*** 2456,2462 ****
bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
! modify_stmt (t);
tsi_link_after (&i->tsi, t, m);
}
--- 2456,2462 ----
bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
! stmt_added (t);
tsi_link_after (&i->tsi, t, m);
}
*************** bsi_remove (block_stmt_iterator *i)
*** 2468,2474 ****
{
tree t = bsi_stmt (*i);
set_bb_for_stmt (t, NULL);
! modify_stmt (t);
tsi_delink (&i->tsi);
}
--- 2468,2474 ----
{
tree t = bsi_stmt (*i);
set_bb_for_stmt (t, NULL);
! stmt_removed (t);
tsi_delink (&i->tsi);
}
*************** bsi_replace (const block_stmt_iterator *
*** 2527,2533 ****
}
*bsi_stmt_ptr (*bsi) = stmt;
! modify_stmt (stmt);
}
/* This routine locates a place to insert a statement on an edge. Every
--- 2527,2533 ----
}
*bsi_stmt_ptr (*bsi) = stmt;
! stmt_added (stmt);
}
/* This routine locates a place to insert a statement on an edge. Every
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.200
diff -c -3 -p -r1.1.4.200 tree-dfa.c
*** tree-dfa.c 11 Dec 2003 01:27:02 -0000 1.1.4.200
--- tree-dfa.c 11 Dec 2003 09:00:59 -0000
*************** static int dump_flags;
*** 124,129 ****
--- 124,131 ----
/* Data and functions shared with tree-ssa.c. */
struct dfa_stats_d dfa_stats;
+ /* A list of statements to rescan. */
+ varray_type statements_to_rescan;
/* Local functions. */
static void note_addressable (tree, stmt_ann_t);
*************** add_use (tree *use_p, tree stmt)
*** 721,726 ****
--- 723,730 ----
abort ();
#endif
+ add_name_use (*use_p, stmt);
+
if (ann->ops == NULL)
{
ann->ops = ggc_alloc (sizeof (struct operands_d));
*************** add_vdef (tree var, tree stmt, voperands
*** 787,792 ****
--- 791,798 ----
source = var;
}
+ add_name_use (source, stmt);
+
if (ann->vops == NULL)
{
ann->vops = ggc_alloc (sizeof (struct voperands_d));
*************** add_vuse (tree var, tree stmt, voperands
*** 849,854 ****
--- 855,862 ----
if (found)
var = vuse;
+ add_name_use (var, stmt);
+
if (ann->vops == NULL)
{
ann->vops = ggc_alloc (sizeof (struct voperands_d));
*************** mark_new_vars_to_rename (tree stmt, bitm
*** 2780,2785 ****
--- 2834,2877 ----
bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
BITMAP_XFREE (vars_in_vops_to_rename);
+ }
+
+ /* Record the statement STMT to a list of statements to rescan. */
+
+ void
+ record_modified_stmt (tree stmt)
+ {
+ if (!statements_to_rescan)
+ VARRAY_TREE_INIT (statements_to_rescan, 1000, "statements_to_rescan");
+
+ VARRAY_PUSH_TREE (statements_to_rescan, stmt);
+ }
+
+ /* Rescan operands of all the modified statements. */
+
+ void
+ rescan_modified_stmts (void)
+ {
+ unsigned i;
+ tree stmt;
+ stmt_ann_t ann;
+
+ if (!statements_to_rescan)
+ return;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (statements_to_rescan); i++)
+ {
+ stmt = VARRAY_TREE (statements_to_rescan, i);
+ VARRAY_TREE (statements_to_rescan, i) = NULL_TREE;
+
+ ann = stmt_ann (stmt);
+ if (ann && ann->removed)
+ continue;
+
+ get_stmt_operands (stmt);
+ }
+
+ VARRAY_POP_ALL (statements_to_rescan);
}
#include "gt-tree-dfa.h"
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.61
diff -c -3 -p -r1.1.2.61 tree-flow-inline.h
*** tree-flow-inline.h 8 Dec 2003 12:58:22 -0000 1.1.2.61
--- tree-flow-inline.h 11 Dec 2003 09:00:59 -0000
*************** get_filename (tree expr)
*** 170,181 ****
--- 170,208 ----
}
static inline void
+ stmt_removed (tree t)
+ {
+ stmt_ann_t ann = stmt_ann (t);
+ if (ann)
+ {
+ ann->modified = 1;
+ ann->removed = 1;
+ if (ann->name_uses)
+ remove_stmt_uses (t);
+ }
+ }
+
+ static inline void
modify_stmt (tree t)
{
stmt_ann_t ann = stmt_ann (t);
if (ann == NULL)
ann = create_stmt_ann (t);
+ if (!ann->modified)
+ record_modified_stmt (t);
ann->modified = 1;
+ if (ann->name_uses)
+ remove_stmt_uses (t);
+ }
+
+ static inline void
+ stmt_added (tree t)
+ {
+ stmt_ann_t ann;
+ modify_stmt (t);
+
+ ann = stmt_ann (t);
+ ann->removed = 0;
}
static inline void
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.167
diff -c -3 -p -r1.1.4.167 tree-flow.h
*** tree-flow.h 8 Dec 2003 12:58:22 -0000 1.1.4.167
--- tree-flow.h 11 Dec 2003 09:00:59 -0000
*************** struct stmt_ann_d GTY(())
*** 221,226 ****
--- 221,229 ----
need to be scanned again). */
unsigned modified : 1;
+ /* Nonzero if the statement has been removed. */
+ unsigned removed : 1;
+
/* Nonzero if the statement is in the CCP worklist and has not been
"cancelled". If we ever need to use this bit outside CCP, then
it should be renamed. */
*************** struct stmt_ann_d GTY(())
*** 248,253 ****
--- 251,259 ----
/* Virtual operands (VDEF and VUSE). */
voperands_t vops;
+ /* A list of ssa names uses in the statement. */
+ struct ssa_name_use *name_uses;
+
/* Dataflow information. */
dataflow_t df;
*************** static inline enum tree_ann_type ann_typ
*** 275,280 ****
--- 281,288 ----
static inline basic_block bb_for_stmt (tree);
extern void set_bb_for_stmt (tree, basic_block);
static inline void modify_stmt (tree);
+ static inline void stmt_removed (tree);
+ static inline void stmt_added (tree);
static inline void unmodify_stmt (tree);
static inline bool stmt_modified_p (tree);
static inline varray_type may_aliases (tree);
*************** extern GTY(()) varray_type call_clobbere
*** 362,367 ****
--- 370,377 ----
#define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
+ /* A list of statements to rescan. */
+ extern GTY(()) varray_type statements_to_rescan;
/*---------------------------------------------------------------------------
Block iterators
*************** extern stmt_ann_t create_stmt_ann (tree)
*** 461,466 ****
--- 471,477 ----
extern tree create_phi_node (tree, basic_block);
extern void add_phi_arg (tree *, tree, edge);
extern void remove_phi_arg (tree, basic_block);
+ extern void replace_phi_arg_num (tree, int, tree);
extern void remove_phi_arg_num (tree, int);
extern void remove_phi_node (tree, tree, basic_block);
extern void remove_all_phi_nodes_for (bitmap);
*************** extern void add_vuse (tree, tree, vopera
*** 489,494 ****
--- 501,508 ----
extern void create_global_var (void);
extern void add_referenced_tmp_var (tree var);
extern void mark_new_vars_to_rename (tree, bitmap);
+ extern void record_modified_stmt (tree);
+ extern void rescan_modified_stmts (void);
/* Flags used when computing reaching definitions and reached uses. */
#define TDFA_USE_OPS 1 << 0
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.92
diff -c -3 -p -r1.1.4.92 tree-optimize.c
*** tree-optimize.c 9 Dec 2003 15:39:11 -0000 1.1.4.92
--- tree-optimize.c 11 Dec 2003 09:00:59 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 122,127 ****
--- 122,129 ----
if (bitmap_first_set_bit (vars_to_rename) >= 0)
rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
+ rescan_modified_stmts ();
+
#ifdef ENABLE_CHECKING
verify_ssa ();
#endif
*************** optimize_function_tree (tree fndecl, tre
*** 157,162 ****
--- 159,166 ----
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_3);
+
+ rescan_modified_stmts ();
ggc_collect ();
#ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 166,171 ****
--- 170,176 ----
/* Eliminate tail recursion calls. */
tree_optimize_tail_calls ();
+ rescan_modified_stmts ();
#ifdef ENABLE_CHECKING
verify_ssa ();
*************** optimize_function_tree (tree fndecl, tre
*** 180,185 ****
--- 185,192 ----
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_4);
+
+ rescan_modified_stmts ();
ggc_collect ();
#ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 196,201 ****
--- 203,209 ----
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_5);
+ rescan_modified_stmts ();
ggc_collect ();
#ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 207,212 ****
--- 215,221 ----
if (flag_tree_pre)
{
tree_perform_ssapre (fndecl, TDI_pre);
+ rescan_modified_stmts ();
ggc_collect ();
#ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 224,229 ****
--- 233,239 ----
if (bitmap_first_set_bit (vars_to_rename) >= 0)
rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_6);
+ rescan_modified_stmts ();
#ifdef ENABLE_CHECKING
verify_ssa ();
#endif
*************** optimize_function_tree (tree fndecl, tre
*** 245,250 ****
--- 255,261 ----
tree_optimize_tail_calls (true, TDI_tail2);
#endif
+ rescan_modified_stmts ();
#ifdef ENABLE_CHECKING
verify_flow_info ();
verify_stmts ();
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-phinodes.c,v
retrieving revision 1.1.2.8
diff -c -3 -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 11 Dec 2003 09:00:59 -0000
*************** release_phi_node (tree phi)
*** 218,223 ****
--- 218,224 ----
int bucket;
int len = PHI_ARG_CAPACITY (phi);
+ remove_stmt_uses (phi);
bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
bucket -= 2;
TREE_CHAIN (phi) = free_phinodes[bucket];
*************** resize_phi_node (tree *phi, int len)
*** 234,245 ****
int size, old_size;
tree new_phi;
int i, old_len, bucket = NUM_BUCKETS - 2;
!
#ifdef ENABLE_CHECKING
if (len < PHI_ARG_CAPACITY (*phi))
abort ();
#endif
!
size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
if (free_phinode_count)
--- 235,246 ----
int size, old_size;
tree new_phi;
int i, old_len, bucket = NUM_BUCKETS - 2;
!
#ifdef ENABLE_CHECKING
if (len < PHI_ARG_CAPACITY (*phi))
abort ();
#endif
!
size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
if (free_phinode_count)
*************** resize_phi_node (tree *phi, int len)
*** 273,285 ****
old_len = PHI_ARG_CAPACITY (new_phi);
PHI_ARG_CAPACITY (new_phi) = len;
!
! for (i = old_len; i < len; i++)
{
PHI_ARG_DEF (new_phi, i) = NULL_TREE;
PHI_ARG_EDGE (new_phi, i) = NULL;
}
!
*phi = new_phi;
}
--- 274,294 ----
old_len = PHI_ARG_CAPACITY (new_phi);
PHI_ARG_CAPACITY (new_phi) = len;
!
! for (i = 0; i < old_len; i++)
! if (PHI_ARG_USE (new_phi, i))
! {
! PHI_ARG_USE (new_phi, i)->stmt = new_phi;
! PHI_ARG_USE (*phi, i) = NULL;
! }
!
! for (; i < len; i++)
{
PHI_ARG_DEF (new_phi, i) = NULL_TREE;
PHI_ARG_EDGE (new_phi, i) = NULL;
+ PHI_ARG_USE (new_phi, i) = NULL;
}
!
*phi = new_phi;
}
*************** add_phi_arg (tree *phi, tree def, edge e
*** 362,367 ****
--- 371,378 ----
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (*phi)) = 1;
}
+ PHI_ARG_USE (*phi, i) = add_name_use (def, *phi);
+
PHI_ARG_DEF (*phi, i) = def;
PHI_ARG_EDGE (*phi, i) = e;
PHI_NUM_ARGS (*phi)++;
*************** remove_phi_arg (tree phi, basic_block bl
*** 389,394 ****
--- 400,418 ----
}
}
+ /* Replace the Ith arg of PHI by VAL. */
+
+ void
+ replace_phi_arg_num (tree phi, int i, tree val)
+ {
+ remove_phi_arg_use (phi, i);
+ PHI_ARG_USE (phi, i) = add_name_use (val, phi);
+ if (TREE_CODE (val) == SSA_NAME
+ && TREE_CODE (PHI_ARG_DEF (phi, i)) == SSA_NAME)
+ propagate_copy (&PHI_ARG_DEF (phi, i), val);
+ else
+ PHI_ARG_DEF (phi, i) = val;
+ }
/* Remove the Ith argument from PHI's argument list. This routine assumes
ordering of alternatives in the vector is not important and implements
*************** remove_phi_arg_num (tree phi, int i)
*** 400,416 ****
--- 424,444 ----
{
int num_elem = PHI_NUM_ARGS (phi);
+ remove_phi_arg_use (phi, i);
+
/* If we are not at the last element, switch the last element
with the element we want to delete. */
if (i != num_elem - 1)
{
PHI_ARG_DEF (phi, i) = PHI_ARG_DEF (phi, num_elem - 1);
PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1);
+ PHI_ARG_USE (phi, i) = PHI_ARG_USE (phi, num_elem - 1);
}
/* Shrink the vector and return. */
PHI_ARG_DEF (phi, num_elem - 1) = NULL_TREE;
PHI_ARG_EDGE (phi, num_elem - 1) = NULL;
+ PHI_ARG_USE (phi, num_elem - 1) = NULL;
PHI_NUM_ARGS (phi)--;
/* If we removed the last PHI argument, then go ahead and
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.123
diff -c -3 -p -r1.1.2.123 tree-ssa-ccp.c
*** tree-ssa-ccp.c 10 Dec 2003 21:43:52 -0000 1.1.2.123
--- tree-ssa-ccp.c 11 Dec 2003 09:00:59 -0000
*************** substitute_and_fold (bitmap vars_to_rena
*** 344,358 ****
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
value *new_val;
! tree *orig_p = &PHI_ARG_DEF (phi, i);
! if (! SSA_VAR_P (*orig_p))
break;
! new_val = get_value (*orig_p);
if (new_val->lattice_val == CONSTANT
! && may_propagate_copy (*orig_p, new_val->const_val))
! *orig_p = new_val->const_val;
}
}
--- 344,358 ----
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
value *new_val;
! tree orig = PHI_ARG_DEF (phi, i);
! if (! SSA_VAR_P (orig))
break;
! new_val = get_value (orig);
if (new_val->lattice_val == CONSTANT
! && may_propagate_copy (orig, new_val->const_val))
! replace_phi_arg_num (phi, i, new_val->const_val);
}
}
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.93
diff -c -3 -p -r1.1.2.93 tree-ssa-dom.c
*** tree-ssa-dom.c 11 Dec 2003 01:29:50 -0000 1.1.2.93
--- tree-ssa-dom.c 11 Dec 2003 09:00:59 -0000
*************** cprop_into_phis (struct dom_walk_data *w
*** 1989,1995 ****
{
int i;
tree new;
! tree *orig_p;
/* If the hint is valid (!= phi_num_args), see if it points
us to the desired phi alternative. */
--- 1989,1995 ----
{
int i;
tree new;
! tree orig;
/* If the hint is valid (!= phi_num_args), see if it points
us to the desired phi alternative. */
*************** cprop_into_phis (struct dom_walk_data *w
*** 2015,2032 ****
/* The alternative may be associated with a constant, so verify
it is an SSA_NAME before doing anything with it. */
! orig_p = &PHI_ARG_DEF (phi, hint);
! if (TREE_CODE (*orig_p) != SSA_NAME)
continue;
/* If we have *ORIG_P in our constant/copy table, then replace
ORIG_P with its value in our constant/copy table. */
! new = get_value_for (*orig_p, const_and_copies);
if (new
&& (TREE_CODE (new) == SSA_NAME
|| is_gimple_min_invariant (new))
! && may_propagate_copy (*orig_p, new))
! propagate_value (orig_p, new);
}
}
}
--- 2015,2032 ----
/* The alternative may be associated with a constant, so verify
it is an SSA_NAME before doing anything with it. */
! orig = PHI_ARG_DEF (phi, hint);
! if (TREE_CODE (orig) != SSA_NAME)
continue;
/* If we have *ORIG_P in our constant/copy table, then replace
ORIG_P with its value in our constant/copy table. */
! new = get_value_for (orig, const_and_copies);
if (new
&& (TREE_CODE (new) == SSA_NAME
|| is_gimple_min_invariant (new))
! && may_propagate_copy (orig, new))
! replace_phi_arg_num (phi, hint, new);
}
}
}
*************** record_equivalences_from_stmt (tree stmt
*** 2248,2253 ****
--- 2248,2257 ----
tree op = VDEF_RESULT (vdefs, j);
add_vuse (op, new, NULL);
}
+
+ /* Forget the statement uses; if we ever use it anywhere, they will
+ be rescanned anyway. */
+ remove_stmt_uses (new);
/* Finally enter the statement into the available expression
table. */
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.174
diff -c -3 -p -r1.1.4.174 tree-ssa.c
*** tree-ssa.c 5 Dec 2003 23:02:24 -0000 1.1.4.174
--- tree-ssa.c 11 Dec 2003 09:01:00 -0000
*************** static void set_livein_block (tree, basi
*** 187,193 ****
static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
static void insert_phi_nodes (bitmap *);
static void rewrite_stmt (block_stmt_iterator, varray_type *);
! static inline void rewrite_operand (tree *);
static void register_new_def (tree, tree, varray_type *);
static void insert_phi_nodes_for (tree, bitmap *);
static tree get_reaching_def (tree);
--- 187,193 ----
static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
static void insert_phi_nodes (bitmap *);
static void rewrite_stmt (block_stmt_iterator, varray_type *);
! static inline void rewrite_operand (tree *, tree);
static void register_new_def (tree, tree, varray_type *);
static void insert_phi_nodes_for (tree, bitmap *);
static tree get_reaching_def (tree);
*************** rewrite_stmt (block_stmt_iterator si, va
*** 3194,3204 ****
/* Step 1. Rewrite USES and VUSES in the statement. */
for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
! rewrite_operand (VARRAY_TREE_PTR (uses, i));
/* Rewrite virtual uses in the statement. */
for (i = 0; vuses && i < VARRAY_ACTIVE_SIZE (vuses); i++)
! rewrite_operand (&VARRAY_TREE (vuses, i));
/* Step 2. Register the statement's DEF and VDEF operands. */
for (i = 0; defs && i < VARRAY_ACTIVE_SIZE (defs); i++)
--- 3194,3204 ----
/* Step 1. Rewrite USES and VUSES in the statement. */
for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
! rewrite_operand (VARRAY_TREE_PTR (uses, i), stmt);
/* Rewrite virtual uses in the statement. */
for (i = 0; vuses && i < VARRAY_ACTIVE_SIZE (vuses); i++)
! rewrite_operand (&VARRAY_TREE (vuses, i), stmt);
/* Step 2. Register the statement's DEF and VDEF operands. */
for (i = 0; defs && i < VARRAY_ACTIVE_SIZE (defs); i++)
*************** rewrite_stmt (block_stmt_iterator si, va
*** 3216,3222 ****
/* Register new virtual definitions made by the statement. */
for (i = 0; vdefs && i < NUM_VDEFS (vdefs); i++)
{
! rewrite_operand (&(VDEF_OP (vdefs, i)));
if (TREE_CODE (VDEF_RESULT (vdefs, i)) != SSA_NAME)
VDEF_RESULT (vdefs, i) = make_ssa_name (VDEF_RESULT (vdefs, i), stmt);
--- 3216,3222 ----
/* Register new virtual definitions made by the statement. */
for (i = 0; vdefs && i < NUM_VDEFS (vdefs); i++)
{
! rewrite_operand (&(VDEF_OP (vdefs, i)), stmt);
if (TREE_CODE (VDEF_RESULT (vdefs, i)) != SSA_NAME)
VDEF_RESULT (vdefs, i) = make_ssa_name (VDEF_RESULT (vdefs, i), stmt);
*************** set_is_used (tree t)
*** 3240,3252 ****
/* Replace the operand pointed by OP_P with its immediate reaching
! definition. */
static inline void
! rewrite_operand (tree *op_p)
{
if (TREE_CODE (*op_p) != SSA_NAME)
! *op_p = get_reaching_def (*op_p);
}
--- 3240,3255 ----
/* Replace the operand pointed by OP_P with its immediate reaching
! definition in STMT. */
static inline void
! rewrite_operand (tree *op_p, tree stmt)
{
if (TREE_CODE (*op_p) != SSA_NAME)
! {
! *op_p = get_reaching_def (*op_p);
! add_name_use (*op_p, stmt);
! }
}
*************** delete_tree_ssa (void)
*** 3314,3319 ****
--- 3317,3324 ----
referenced_var (i)->common.ann = NULL;
referenced_vars = NULL;
}
+
+ statements_to_rescan = NULL;
fini_ssanames ();
fini_phinodes ();
Index: tree-ssanames.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssanames.c,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 tree-ssanames.c
*** tree-ssanames.c 1 Dec 2003 22:15:15 -0000 1.1.2.6
--- tree-ssanames.c 11 Dec 2003 09:01:00 -0000
*************** Boston, MA 02111-1307, USA. */
*** 24,29 ****
--- 24,30 ----
#include "tm.h"
#include "tree.h"
#include "varray.h"
+ #include "tree-flow.h"
#include "ggc.h"
/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
*************** unsigned int highest_ssa_version;
*** 64,69 ****
--- 65,74 ----
after we leave SSA form. */
static GTY (()) tree free_ssanames;
+ /* Free list of SSA_NAME use occurences. Linked through next_stmt_use
+ field. */
+ static GTY(()) struct ssa_name_use *free_name_uses;
+
/* Version numbers with special meanings. We start allocating new version
numbers after the special ones. */
#define UNUSED_NAME_VERSION 0
*************** init_ssanames (void)
*** 80,85 ****
--- 85,91 ----
{
highest_ssa_version = UNUSED_NAME_VERSION + 1;
free_ssanames = NULL;
+ free_name_uses = NULL;
}
/* Finalize management of SSA_NAMEs. */
*************** void
*** 88,93 ****
--- 94,100 ----
fini_ssanames (void)
{
free_ssanames = NULL;
+ free_name_uses = NULL;
}
/* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */
*************** make_ssa_name (tree var, tree stmt)
*** 151,156 ****
--- 158,165 ----
TREE_TYPE (t) = TREE_TYPE (var);
SSA_NAME_VAR (t) = var;
SSA_NAME_DEF_STMT (t) = stmt;
+ SSA_NAME_USES (t)->next_name_use = SSA_NAME_USES (t);
+ SSA_NAME_USES (t)->prev_name_use = SSA_NAME_USES (t);
return t;
}
*************** release_ssa_name (tree var)
*** 179,184 ****
--- 188,286 ----
TREE_CHAIN (var) = free_ssanames;
free_ssanames = var;
}
+ }
+
+ /* Add a record of using the ssa name NAME in the statement STMT. */
+
+ struct ssa_name_use *
+ add_name_use (tree name, tree stmt)
+ {
+ struct ssa_name_use *use;
+ stmt_ann_t ann;
+
+ if (TREE_CODE (name) != SSA_NAME)
+ return NULL;
+
+ if (free_name_uses)
+ {
+ use = free_name_uses;
+ free_name_uses = free_name_uses->next_name_use;
+ }
+ else
+ use = ggc_alloc (sizeof (struct ssa_name_use));
+
+ use->stmt = stmt;
+ use->next_name_use = SSA_NAME_USES (name)->next_name_use;
+ use->prev_name_use = SSA_NAME_USES (name);
+ use->next_name_use->prev_name_use = use;
+ use->prev_name_use->next_name_use = use;
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ use->next_stmt_use = NULL;
+ else
+ {
+ ann = stmt_ann (stmt);
+ use->next_stmt_use = ann->name_uses;
+ ann->name_uses = use;
+ }
+
+ return use;
+ }
+
+ /* Remove the USE from the list of uses of the variable. */
+ static void
+ remove_stmt_use (struct ssa_name_use *use)
+ {
+ struct ssa_name_use *next = use->next_name_use, *prev = use->prev_name_use;
+
+ next->prev_name_use = prev;
+ prev->next_name_use = next;
+ use->stmt = NULL_TREE;
+ use->prev_name_use = use->next_name_use = NULL;
+ }
+
+ /* Remove records of use of the i-th arg of the PHI node. */
+
+ void
+ remove_phi_arg_use (tree phi, int i)
+ {
+ struct ssa_name_use *use = PHI_ARG_USE (phi, i);
+
+ if (!use)
+ return;
+
+ remove_stmt_use (use);
+ use->next_stmt_use = free_name_uses;
+ free_name_uses = use;
+ PHI_ARG_USE (phi, i) = NULL;
+ }
+
+ /* Remove records of uses in the statement STMT. */
+
+ void
+ remove_stmt_uses (tree stmt)
+ {
+ struct ssa_name_use **use, **w;
+ stmt_ann_t ann;
+ int i;
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ {
+ for (i = 0; i < PHI_NUM_ARGS (stmt); i++)
+ remove_phi_arg_use (stmt, i);
+
+ return;
+ }
+
+ ann = stmt_ann (stmt);
+ w = &ann->name_uses;
+
+ for (use = w; *use; use = &(*use)->next_stmt_use)
+ remove_stmt_use (*use);
+
+ *use = free_name_uses;
+ free_name_uses = *w;
+ *w = NULL;
}
#include "gt-tree-ssanames.h"
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.150
diff -c -3 -p -r1.342.2.150 tree.h
*** tree.h 8 Dec 2003 20:29:26 -0000 1.342.2.150
--- tree.h 11 Dec 2003 09:01:00 -0000
*************** struct tree_exp GTY(())
*** 1021,1027 ****
/* Returns the variable being referenced. Once released, this is the
only field that can be relied upon. */
! #define SSA_NAME_VAR(NODE) SSA_NAME_CHECK (NODE)->ssa_name.var
/* Returns the statement which defines this reference. Note that
we use the same field when chaining SSA_NAME nodes together on
--- 1021,1027 ----
/* Returns the variable being referenced. Once released, this is the
only field that can be relied upon. */
! #define SSA_NAME_VAR(NODE) SSA_NAME_CHECK (NODE)->ssa_name.uses.stmt
/* Returns the statement which defines this reference. Note that
we use the same field when chaining SSA_NAME nodes together on
*************** struct tree_exp GTY(())
*** 1032,1037 ****
--- 1032,1040 ----
tree SSA, version numbers are not per variable and may be recycled. */
#define SSA_NAME_VERSION(NODE) SSA_NAME_CHECK (NODE)->ssa_name.version
+ /* Returns the list of uses of the SSA name. */
+ #define SSA_NAME_USES(NODE) (&SSA_NAME_CHECK (NODE)->ssa_name.uses)
+
/* Nonzero if this SSA name occurs in an abnormal PHI. SSA_NAMES are
never output, so we can safely use the ASM_WRITTEN_FLAG for this
status bit. */
*************** struct tree_exp GTY(())
*** 1044,1058 ****
#define SSA_NAME_IN_FREE_LIST(NODE) \
SSA_NAME_CHECK (NODE)->common.nothrow_flag
struct tree_ssa_name GTY(())
{
struct tree_common common;
- /* _DECL wrapped by this SSA name. */
- tree var;
-
/* SSA version number. */
unsigned int version;
};
/* In a PHI_NODE node. */
--- 1047,1082 ----
#define SSA_NAME_IN_FREE_LIST(NODE) \
SSA_NAME_CHECK (NODE)->common.nothrow_flag
+ /* The instance of the use of the SSA name. They are linked in two list;
+ one of them is a list of uses in the same statement, the second one
+ is the list of uses of the SSA name. The second list is double cyclic
+ list with a head. To conserve a few bytes of memory, the head has STMT set
+ to the _DECL the SSA name is based on. */
+ struct ssa_name_use GTY(())
+ {
+ /* Statement in that the SSA name is used. */
+ tree stmt;
+
+ /* Next and previous use of the same SSA name in the linked list of all
+ uses. The `skip' here is so that we may let it point to a non-ggc
+ allocated head; next_stmt_use list is sufficient to keep the reference
+ alive as long as we need it. */
+ struct ssa_name_use * GTY((skip (""))) next_name_use;
+ struct ssa_name_use * GTY((skip (""))) prev_name_use;
+
+ /* Entry for a next SSA name used in the STMT. */
+ struct ssa_name_use *next_stmt_use;
+ };
+
struct tree_ssa_name GTY(())
{
struct tree_common common;
/* SSA version number. */
unsigned int version;
+
+ /* A list of SSA name uses. */
+ struct ssa_name_use uses;
};
/* In a PHI_NODE node. */
*************** struct tree_ssa_name GTY(())
*** 1066,1071 ****
--- 1090,1096 ----
#define PHI_ARG_ELT(NODE, I) PHI_NODE_ELT_CHECK (NODE, I)
#define PHI_ARG_EDGE(NODE, I) PHI_NODE_ELT_CHECK (NODE, I).e
#define PHI_ARG_DEF(NODE, I) PHI_NODE_ELT_CHECK (NODE, I).def
+ #define PHI_ARG_USE(NODE, I) PHI_NODE_ELT_CHECK (NODE, I).use
struct edge_def;
*************** struct phi_arg_d GTY(())
*** 1073,1078 ****
--- 1098,1106 ----
{
tree def;
struct edge_def * GTY((skip (""))) e;
+
+ /* SSA name use. */
+ struct ssa_name_use *use;
};
struct tree_phi_node GTY(())
*************** extern void release_ssa_name (tree);
*** 2564,2569 ****
--- 2592,2601 ----
#ifdef GATHER_STATISTICS
extern void ssanames_print_statistics (void);
#endif
+
+ extern struct ssa_name_use *add_name_use (tree, tree);
+ extern void remove_stmt_uses (tree);
+ extern void remove_phi_arg_use (tree, int);
/* Return the (unique) IDENTIFIER_NODE node for a given name.
The name is supplied as a char *. */