From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 27066 invoked by alias); 11 Dec 2003 22:31:08 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 26875 invoked from network); 11 Dec 2003 22:30:57 -0000 Received: from unknown (HELO atrey.karlin.mff.cuni.cz) (195.113.31.123) by sources.redhat.com with SMTP; 11 Dec 2003 22:30:57 -0000 Received: by atrey.karlin.mff.cuni.cz (Postfix, from userid 29025) id CA12F4C02FE; Thu, 11 Dec 2003 23:30:56 +0100 (CET) Date: Thu, 11 Dec 2003 22:36:00 -0000 From: Zdenek Dvorak To: law@redhat.com Cc: Diego Novillo , "gcc@gcc.gnu.org" Subject: Re: [tree-ssa] Lazy updating of stmt operands Message-ID: <20031211223056.GA20061@atrey.karlin.mff.cuni.cz> References: <1070818186.7334.30.camel@frodo.toronto.redhat.com> <200312111936.hBBJabGj024859@speedy.slc.redhat.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200312111936.hBBJabGj024859@speedy.slc.redhat.com> User-Agent: Mutt/1.5.4i X-SW-Source: 2003-12/txt/msg00677.txt.bz2 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 *. */