diff options
| author | Daniel Berlin <dberlin@gcc.gnu.org> | 2004-06-12 00:18:35 +0000 |
|---|---|---|
| committer | Daniel Berlin <dberlin@gcc.gnu.org> | 2004-06-12 00:18:35 +0000 |
| commit | 7e6eb623f948dcaacab5e1251c99ebadc270c3d5 (patch) | |
| tree | ca99eaea2a64c9280cab7d983086bb2ab6db10a1 /gcc | |
| parent | e4602cf33b4359a1a92ffff5749eaf3422600993 (diff) | |
| download | gcc-7e6eb623f948dcaacab5e1251c99ebadc270c3d5.zip gcc-7e6eb623f948dcaacab5e1251c99ebadc270c3d5.tar.gz gcc-7e6eb623f948dcaacab5e1251c99ebadc270c3d5.tar.bz2 | |
[multiple changes]
2004-06-11 Steven Bosscher <stevenb@suse.de>
* tree-ssa-dce.c (mark_control_dependent_edges_necessary):
Don't try to mark anything control dependent on the entry or
exit blocks.
2004-06-11 Daniel Berlin <dberlin@dberlin.org>
Fix Bug 15899
Fix Bug 15460
* tree.h (SSA_NAME_VALUE): New macro.
(struct tree_ssa_name): Add value_handle member.
* tree-ssa-pre.c: Replaced.
* tree-flow.h (tree_ann_type): Add CST_ANN, EXPR_ANN.
(struct cst_ann_d): New.
(struct expr_ann_d): New.
(union tree_ann_d): Add cst_ann, expr_ann.
* tree-dfa.c (create_cst_ann): New function.
(create_expr_ann): Ditto.
* tree-flow-inline.h (cst_ann): New function.
(expr_ann): Ditto.
(get_cst_ann): Ditto.
(get_expr_ann): Ditto..
From-SVN: r83010
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/ChangeLog | 24 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.c-torture/compile/20040611-1.c | 8 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-1.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-2.c | 2 | ||||
| -rw-r--r-- | gcc/tree-dfa.c | 46 | ||||
| -rw-r--r-- | gcc/tree-flow-inline.h | 41 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 39 | ||||
| -rw-r--r-- | gcc/tree-ssa-dce.c | 8 | ||||
| -rw-r--r-- | gcc/tree-ssa-pre.c | 4419 | ||||
| -rw-r--r-- | gcc/tree.h | 7 |
10 files changed, 1625 insertions, 2971 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 39fe01a..3c8371a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,27 @@ +2004-06-11 Steven Bosscher <stevenb@suse.de> + + * tree-ssa-dce.c (mark_control_dependent_edges_necessary): + Don't try to mark anything control dependent on the entry or + exit blocks. + +2004-06-11 Daniel Berlin <dberlin@dberlin.org> + + Fix Bug 15899 + Fix Bug 15460 + * tree.h (SSA_NAME_VALUE): New macro. + (struct tree_ssa_name): Add value_handle member. + * tree-ssa-pre.c: Replaced. + * tree-flow.h (tree_ann_type): Add CST_ANN, EXPR_ANN. + (struct cst_ann_d): New. + (struct expr_ann_d): New. + (union tree_ann_d): Add cst_ann, expr_ann. + * tree-dfa.c (create_cst_ann): New function. + (create_expr_ann): Ditto. + * tree-flow-inline.h (cst_ann): New function. + (expr_ann): Ditto. + (get_cst_ann): Ditto. + (get_expr_ann): Ditto.. + 2004-06-11 John David Anglin <dave.anglin@nrc-cnrc.gc.ca> * pa.c (pa_hpux_init_libfunc): Add support for unord_optab. diff --git a/gcc/testsuite/gcc.c-torture/compile/20040611-1.c b/gcc/testsuite/gcc.c-torture/compile/20040611-1.c new file mode 100644 index 0000000..8a5528b --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/compile/20040611-1.c @@ -0,0 +1,8 @@ +/* This would cause PRE load motion to generate invalid code and ICE */ +void foo (char *name) +{ + if (*name) + name ++; + while (name[0]); + asm ("" : "=r" (name)); +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-1.c index 43eb6e0..d3c9d421 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-1.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-1.c @@ -16,4 +16,4 @@ int main(int argc, char **argv) } /* We should eliminate one evaluation of b + c along the main path, causing one reload. */ -/* { dg-final { scan-tree-dump-times "Reloads:1" 1 "pre"} } */ +/* { dg-final { scan-tree-dump-times "Eliminated:1" 1 "pre"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-2.c index e264c50..8326009 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-2.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-2.c @@ -17,4 +17,4 @@ int motion_test1(int data, int data_0, int data_3, int v) } /* We should eliminate one computation of data_0 + data_3 along the main path, causing one reload. */ -/* { dg-final { scan-tree-dump-times "Reloads:1" 1 "pre"} } */ +/* { dg-final { scan-tree-dump-times "Eliminated:1" 1 "pre"} } */ diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c index 3bcf1d5..869f6da 100644 --- a/gcc/tree-dfa.c +++ b/gcc/tree-dfa.c @@ -463,6 +463,52 @@ create_stmt_ann (tree t) } +/* Create a new annotation for a constant T. */ + +cst_ann_t +create_cst_ann (tree t) +{ + cst_ann_t ann; + +#if defined ENABLE_CHECKING + if (t == NULL_TREE + || (t->common.ann + && t->common.ann->common.type != CST_ANN)) + abort (); +#endif + + ann = ggc_alloc (sizeof (*ann)); + memset ((void *) ann, 0, sizeof (*ann)); + + ann->common.type = CST_ANN; + t->common.ann = (tree_ann) ann; + + return ann; +} + +/* Create a new annotation for an expression T. */ + +expr_ann_t +create_expr_ann (tree t) +{ + expr_ann_t ann; + +#if defined ENABLE_CHECKING + if (t == NULL_TREE + || (t->common.ann + && t->common.ann->common.type != EXPR_ANN)) + abort (); +#endif + + ann = ggc_alloc (sizeof (*ann)); + memset ((void *) ann, 0, sizeof (*ann)); + + ann->common.type = EXPR_ANN; + t->common.ann = (tree_ann) ann; + + return ann; +} + /* Build a temporary. Make sure and register it to be renamed. */ tree diff --git a/gcc/tree-flow-inline.h b/gcc/tree-flow-inline.h index 4bb5e41..c8cf12c1 100644 --- a/gcc/tree-flow-inline.h +++ b/gcc/tree-flow-inline.h @@ -46,6 +46,47 @@ get_var_ann (tree var) return (ann) ? ann : create_var_ann (var); } + +static inline cst_ann_t +cst_ann (tree t) +{ +#if defined ENABLE_CHECKING + if (TREE_CODE_CLASS (TREE_CODE (t)) != 'c' + || (t->common.ann + && t->common.ann->common.type != CST_ANN)) + abort (); +#endif + + return (cst_ann_t) t->common.ann; +} + +static inline cst_ann_t +get_cst_ann (tree var) +{ + cst_ann_t ann = cst_ann (var); + return (ann) ? ann : create_cst_ann (var); +} + +static inline expr_ann_t +expr_ann (tree t) +{ +#if defined ENABLE_CHECKING + if (!EXPR_P (t) + || (t->common.ann + && t->common.ann->common.type != EXPR_ANN)) + abort (); +#endif + + return (expr_ann_t) t->common.ann; +} + +static inline expr_ann_t +get_expr_ann (tree var) +{ + expr_ann_t ann = expr_ann (var); + return (ann) ? ann : create_expr_ann (var); +} + static inline stmt_ann_t stmt_ann (tree t) { diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index d9827e1..4f3a4a6 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -40,12 +40,15 @@ typedef struct basic_block_def *basic_block; /*--------------------------------------------------------------------------- Tree annotations stored in tree_common.ann ---------------------------------------------------------------------------*/ -enum tree_ann_type { TREE_ANN_COMMON, VAR_ANN, STMT_ANN }; +enum tree_ann_type { TREE_ANN_COMMON, VAR_ANN, CST_ANN, EXPR_ANN, STMT_ANN }; struct tree_ann_common_d GTY(()) { /* Annotation type. */ enum tree_ann_type type; + + /* The value handle for this expression. Used by GVN-PRE. */ + tree GTY((skip)) value_handle; }; /* It is advantageous to avoid things like life analysis for variables which @@ -164,6 +167,11 @@ struct var_ann_d GTY(()) live at the same time and this can happen for each call to the dominator optimizer. */ tree current_def; + + /* The set of expressions represented by this variable if it is a + value handle. This is used by GVN-PRE. */ + PTR GTY ((skip)) expr_set; + }; @@ -256,17 +264,38 @@ struct stmt_ann_d GTY(()) }; +struct cst_ann_d GTY (()) +{ + struct tree_ann_common_d common; + +}; + +struct expr_ann_d GTY(()) +{ + struct tree_ann_common_d common; + +}; + + union tree_ann_d GTY((desc ("ann_type ((tree_ann)&%h)"))) { struct tree_ann_common_d GTY((tag ("TREE_ANN_COMMON"))) common; struct var_ann_d GTY((tag ("VAR_ANN"))) decl; + struct expr_ann_d GTY((tag ("EXPR_ANN"))) expr; + struct cst_ann_d GTY((tag ("CST_ANN"))) cst; struct stmt_ann_d GTY((tag ("STMT_ANN"))) stmt; }; typedef union tree_ann_d *tree_ann; typedef struct var_ann_d *var_ann_t; typedef struct stmt_ann_d *stmt_ann_t; +typedef struct expr_ann_d *expr_ann_t; +typedef struct cst_ann_d *cst_ann_t; +static inline cst_ann_t cst_ann (tree); +static inline cst_ann_t get_cst_ann (tree); +static inline expr_ann_t expr_ann (tree); +static inline expr_ann_t get_expr_ann (tree); static inline var_ann_t var_ann (tree); static inline var_ann_t get_var_ann (tree); static inline stmt_ann_t stmt_ann (tree); @@ -464,6 +493,8 @@ extern void dump_generic_bb (FILE *, basic_block, int, int); /* In tree-dfa.c */ extern var_ann_t create_var_ann (tree); +extern cst_ann_t create_cst_ann (tree); +extern expr_ann_t create_expr_ann (tree); extern stmt_ann_t create_stmt_ann (tree); extern tree create_phi_node (tree, basic_block); extern void add_phi_arg (tree *, tree, edge); @@ -567,6 +598,12 @@ extern bool tree_can_throw_internal (tree); extern bool tree_can_throw_external (tree); extern void add_stmt_to_eh_region (tree, int); +/* In tree-ssa-pre.c */ +tree get_value_handle (tree); +void set_value_handle (tree, tree); +void debug_value_expressions (tree); +void print_value_expressions (FILE *, tree); + #include "tree-flow-inline.h" #endif /* _TREE_FLOW_H */ diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c index 5380e01..36007a4 100644 --- a/gcc/tree-ssa-dce.c +++ b/gcc/tree-ssa-dce.c @@ -482,6 +482,14 @@ mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) { int edge_number; +#ifdef ENABLE_CHECKING + if (bb == EXIT_BLOCK_PTR) + abort (); +#endif + + if (bb == ENTRY_BLOCK_PTR) + return; + EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number, { tree t; diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index aa45e10..a1f33ad 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -1,6 +1,7 @@ /* SSA-PRE for trees. Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. - Contributed by Daniel Berlin <dan@dberlin.org> + Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher + <stevenb@suse.de> This file is part of GCC. @@ -44,3260 +45,1741 @@ Boston, MA 02111-1307, USA. */ #include "alloc-pool.h" #include "tree-pass.h" #include "flags.h" - - -/* - - Some of the algorithms are also based on Open64's SSAPRE implementation. - - Since the papers are a bit dense to read, take a while to grasp, - and have a few bugs, i'll give a quick rundown: - - Normally, in non-SSA form, one performs PRE on expressions using - bit vectors, determining properties for all expressions at once - through bitmap operations and iterative dataflow. - - SSAPRE, like most non-SSA->SSA algorithm conversions, operates one - expression at a time, and doesn't use bitvectors or iterative - dataflow. - - It answers the question "Given a single hypothetical temporary - variable, what expressions could we eliminate. - - To be able to do this, we need an SSA form for expressions. - If you are already confused, you likely think an expression, as - used here, is something like "b_3 = a_2 + 5". It's not. It's "a + - 5". "a_2 + 5" is an *occurrence* of the expression "a + 5". Just - like PRE, it's lexical equivalence that matters. - Compilers generally give you an SSA form for variables, and maybe - arrays (and/or conditionals). But not for expressions. - - GCC doesn't give you one either, so we have to build it. - Thus, the first steps of SSAPRE are to do just these things. - - First we collect lists of occurrences of expressions we are going - to operate on. - Note that: - Unlike the paper, we don't have to ever add newly formed - expressions to the list (for normal SSAPRE, anyway), because we - don't have expressions with more than two operators, and each - operator is either a constant or a variable. Thus, no second - order effects. - - Once we have the lists of occurrences, we process one expression - at a time, doing the following: - 1. Using a slightly modified SSA phi placement algorithm, place - expression PHI's for expressions. - 2. Using a two step optimistic SSA renaming algorithm, version the - nodes and link phi operands to their real occurrences, if they - exist. This creates a factored graph of our expression SSA occurrences. - 3. Using the factored graph, compute downsafe, avail, and later for - EPHIs (which are SSA versions of the same named bitvector PRE - problems) - 4. Using EPHI availability information and versions, compute what - occurrences need to have saves, and what occurrences can be - reloaded from an already saved value. - 5. Insert the saves and reloads, and transform EPHIs into regular - phis of the temporary we use for insertion/saving. +#include "splay-tree.h" +#include "bitmap.h" +#include "langhooks.h" +/* TODO: - See http://citeseer.nj.nec.com/chow97new.html, and - http://citeseer.nj.nec.com/kennedy99partial.html for details of the - algorithm. + 1. Implement load value numbering. + 2. Speed up insert_aux so that we can use it all the time. It + spends most of it's time in quadratic value replacement. + 3. Avail sets can be shared by making an avail_find_leader that + walks up the dominator tree and looks in those avail sets. + This might affect code optimality, it's unclear right now. + 4. Load motion can be performed by value numbering the loads the + same as we do other expressions. This requires iterative + hashing the vuses into the values. Right now we simply assign + a new value every time we see a statement with a vuse. + 5. Strength reduction can be performed by anticipating expressions + we can repair later on. +*/ + +/* For ease of terminology, "expression node" in the below refers to + every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent + the actual statement containing the expressions we care about, and + we cache the value number by putting it in the expression. */ + +/* Basic algorithm - kennedy99partial is newer, and is what this implementation is based - on. + First we walk the statements to generate the AVAIL sets, the EXP_GEN + sets, and the tmp_gen sets. AVAIL is a forward dataflow + problem. EXP_GEN sets represent the generation of + values/expressions by a given block. We use them when computing + the ANTIC sets. The AVAIL sets consist of SSA_NAME's that + represent values, so we know what values are available in what + blocks. In SSA, values are never killed, so we don't need a kill + set, or a fixpoint iteration, in order to calculate the AVAIL sets. + In traditional parlance, AVAIL sets tell us the downsafety of the + expressions/values. - For strength reduction addition, see - http://citeseer.nj.nec.com/kennedy98strength.html. - - There is also a paper on sparse register promotion using PRE that - contains the basic algorithm for load PRE. The exact title/url of - the paper escapes me. - - Lastly, there is a code hoisting extension that open64 performs - (see opt_ehoist.cxx), but we don't. It's not documented in any - papers, but not that difficult to understand of implement. */ - - -/* TODOS: - Do strength reduction on a +-b and -a, not just a * <constant>. - */ - -struct expr_info; -static void clear_all_eref_arrays (void); -static inline bool expr_lexically_eq (const tree, const tree); -static void free_expr_info (struct expr_info *); -static bitmap compute_idfs (bitmap *, tree); -static void set_var_phis (struct expr_info *, tree); -static inline bool names_match_p (const tree, const tree); -static bool is_strred_cand (const tree); -static int pre_expression (struct expr_info *, void *, bitmap); -static bool is_injuring_def (struct expr_info *, tree); -static inline bool okay_injuring_def (tree, tree); -static bool expr_phi_insertion (bitmap *, struct expr_info *); -static tree factor_through_injuries (struct expr_info *, tree, tree, bool *); -static inline tree maybe_find_rhs_use_for_var (tree, tree, unsigned int); -static inline tree find_rhs_use_for_var (tree, tree); -static tree create_ephi_node (basic_block, unsigned int); -static inline int opnum_of_phi (tree, int); -static inline int opnum_of_ephi (const tree, const edge); -static tree subst_phis (struct expr_info *, tree, basic_block, basic_block); -static void generate_expr_as_of_bb (tree, basic_block, basic_block); -static void generate_vops_as_of_bb (tree, basic_block, basic_block); -static void rename_1 (struct expr_info *); -static void process_delayed_rename (struct expr_info *, tree, tree); -static void assign_new_class (tree, varray_type *, varray_type *); -static void create_and_insert_occ_in_preorder_dt_order (struct expr_info *); -static void insert_euse_in_preorder_dt_order (struct expr_info *); -static bool ephi_has_unsafe_arg (tree); -static void reset_down_safe (tree, int); -static void compute_down_safety (struct expr_info *); -static void compute_will_be_avail (struct expr_info *); -static void compute_stops (struct expr_info *); -static bool finalize_1 (struct expr_info *); -static void finalize_2 (struct expr_info *); -static tree occ_identical_to (tree); -static void require_phi (struct expr_info *, basic_block); -static bool really_available_def (tree node); - -/* Functions used for an EPHI based depth first search. */ -struct ephi_df_search -{ - /* Return true if the ephi has been seen. */ - bool (*seen) (tree); - /* Mark the ephi as seen. */ - void (*set_seen) (tree); - /* Note that the search reaches from one ephi to it's use. */ - void (*reach_from_to) (tree, int, tree); - /* Return true if we should start a search from this PHI. */ - bool (*start_from) (tree); - /* Return true if we should continue the search to this use. */ - bool (*continue_from_to) (tree, int, tree); -}; -static bool repl_search_seen (tree); -static void repl_search_set_seen (tree); -static void repl_search_reach_from_to (tree, int, tree); -static bool repl_search_start_from (tree); -static bool repl_search_continue_from_to (tree, int, tree); -static bool stops_search_seen (tree); -static void stops_search_set_seen (tree); -static void stops_search_reach_from_to (tree, int, tree); -static bool stops_search_start_from (tree); -static bool stops_search_continue_from_to (tree, int, tree); -static bool cba_search_seen (tree); -static void cba_search_set_seen (tree); -static bool cba_search_start_from (tree); -static bool cba_search_continue_from_to (tree, int, tree); -struct ephi_df_search cant_be_avail_search = { - cba_search_seen, - cba_search_set_seen, - NULL, - cba_search_start_from, - cba_search_continue_from_to -}; - -struct ephi_df_search stops_search = { - stops_search_seen, - stops_search_set_seen, - stops_search_reach_from_to, - stops_search_start_from, - stops_search_continue_from_to -}; - - -/* depth-first replacement search used during temp ESSA minimization. */ -struct ephi_df_search replacing_search = { - repl_search_seen, - repl_search_set_seen, - repl_search_reach_from_to, - repl_search_start_from, - repl_search_continue_from_to -}; - -static void do_ephi_df_search_1 (struct ephi_df_search, tree); -static void do_ephi_df_search (struct expr_info *, struct ephi_df_search); - -static inline bool any_operand_injured (tree); -static void code_motion (struct expr_info *); -static tree pick_ssa_name (tree stmt); -#if 0 -static tree calculate_increment (struct expr_info *, tree); -#endif -static bool can_insert (tree, int); -static void set_save (struct expr_info *, tree); -static tree reaching_def (tree, tree, basic_block, tree); -static tree do_proper_save (tree , tree, int); -static void process_left_occs_and_kills (varray_type, tree); -static tree create_expr_ref (struct expr_info *, tree, enum tree_code, - basic_block, tree); -static inline bool ephi_will_be_avail (tree); -static inline tree ephi_at_block (basic_block); -static tree get_default_def (tree, htab_t); -static inline bool same_e_version_real_occ_real_occ (struct expr_info *, - const tree, - const tree); -static inline bool load_modified_phi_result (basic_block, tree); -static inline bool same_e_version_phi_result (struct expr_info *, - tree, tree, tree); -static inline bool load_modified_real_occ_real_occ (tree, tree); -static inline bool same_e_version_real_occ_phi_opnd (struct expr_info *, - tree, basic_block, - int, tree, bool *); -static inline bool injured_real_occ_real_occ (struct expr_info *, - tree, tree); -static inline bool injured_phi_result_real_occ (struct expr_info *, - tree, tree, basic_block); -static inline bool injured_real_occ_phi_opnd (struct expr_info *, - tree, basic_block, int); -static void compute_du_info (struct expr_info *); -static void add_ephi_use (tree, tree, int); -static void insert_one_operand (struct expr_info *, tree, int, tree, edge, - tree **); -static void collect_expressions (basic_block, varray_type *); -static int build_dfn_array (basic_block, int); -static int eref_compare (const void *, const void *); - - -/* Bitmap of E-PHI predecessor operands have already been created. - We only create one phi-pred per block. */ -static bitmap created_phi_preds; - -/* PRE dominance frontiers. */ -static bitmap *pre_dfs; - -/* Number of redundancy classes. */ -static int class_count = 0; - - -/* Iterated dominance frontiers cache. */ -static bitmap *idfs_cache; - -/* Partial redundancies statistics. */ -static struct pre_stats_d -{ - int reloads; - int saves; - int repairs; - int newphis; - int ephi_allocated; - int ephis_current; - int eref_allocated; - int exprs_generated; -} pre_stats = {0, 0, 0, 0, 0, 0, 0, 0}; - - -/* USE entry in list of uses of ephi's. */ -struct ephi_use_entry + Next, we generate the ANTIC sets. ANTIC is a backwards dataflow + problem. These sets represent the anticipatable expressions. An + expression is anticipatable in a given block if it could be + generated in that block. This means that if we had to perform an + insertion in that block, of the value of that expression, we could. + Calculating the ANTIC sets requires phi translation of expressions, + because the flow goes backwards through phis. We must iterate to a + fixpoint of the ANTIC sets, because we have a kill set. + Even in SSA form, values are not live over the entire function, + only from their definition point onwards. So we have to remove + values from the ANTIC set once we go past the definition point of + the leaders that make them up. compute_antic/compute_antic_aux + performs this computation. + + Third, we perform insertions to make partially redundant + expressions fully redundant. + + An expression is partially redundant (excluding partial + anticipation) if: + + 1. It is AVAIL in some, but not all, of the predecessors of a + given block. + 2. It is ANTIC in all the predecessors. + + In order to make it fully redundant, we insert the expression into + the predecessors where it is not available, but is ANTIC. + insert/insert_aux performs this insertion. + + Fourth, we eliminate fully redundant expressions. + This is a simple statement walk that replaces redundant + calculations with the now available values. */ + +/* Representations of value numbers: + + Value numbers are represented using the "value handle" approach. + This means that each SSA_NAME (and for other reasons to be + disclosed in a moment, expression nodes and constant nodes) has a + value handle that can be retrieved through get_value_handle. This + value handle, *is* the value number of the SSA_NAME. You can + pointer compare the value handles for equivalence purposes. + + For debugging reasons, the value handle is internally more than + just a number, it is a VAR_DECL named "value.x", where x is a + unique number for each value number in use. This allows + expressions with SSA_NAMES replaced by value handles to still be + pretty printed in a sane way. They simply print as "value.3 * + value.5", etc. + + Expression nodes have value handles associated with them as a + cache. Otherwise, we'd have to look them up again in the hash + table This makes significant difference (factor of two or more) on + some test cases. They can be thrown away after the Constants have + value handles associated with them so that they aren't special + cased everywhere, and for consistency sake. This may be changed + depending on memory usage vs code maintenance tradeoff. */ + +/* Representation of expressions on value numbers: + + In some portions of this code, you will notice we allocate "fake" + analogues to the expression we are value numbering, and replace the + operands with the values of the expression. Since we work on + values, and not just names, we canonicalize expressions to value + expressions for use in the ANTIC sets, the EXP_GEN set, etc. + + This is theoretically unnecessary, it just saves a bunch of + repeated get_value_handle and find_leader calls in the remainder of + the code, trading off temporary memory usage for speed. The tree + nodes aren't actually creating more garbage, since they are + allocated in a special pools which are thrown away at the end of + this pass. + + All of this also means that if you print the EXP_GEN or ANTIC sets, + you will see "value.5 + value.7" in the set, instead of "a_55 + + b_66" or something. The only thing that actually cares about + seeing the value leaders is phi translation, and it needs to be + able to find the leader for a value in an arbitrary block, so this + "value expression" form is perfect for it (otherwise you'd do + get_value_handle->find_leader->translate->get_value_handle->find_leader).*/ + + +/* Representation of sets: + + Sets are represented as doubly linked lists kept in topological + order, with an optional supporting bitmap of values present in the + set. The sets represent values, and the elements can be constants, + values, or expressions. The elements can appear in different sets, + but each element can only appear once in each set. + + Since each node in the set represents a value, we also want to be + able to map expression, set pairs to something that tells us + whether the value is present is a set. We use a per-set bitmap for + that. The value handles also point to a linked list of the + expressions they represent via a tree annotation. This is mainly + useful only for debugging, since we don't do identity lookups. */ + + +/* A value set element. Basically a single linked list of + expressions/constants/values. */ +typedef struct value_set_node { - tree phi; - int opnd_indx; -}; - -/* PRE Expression specific info. */ -struct expr_info -{ - /* The actual expression. */ tree expr; - /* The occurrences. */ - varray_type occurs; - /* The kills. */ - varray_type kills; - /* The left occurrences. */ - varray_type lefts; - /* An array of real occurrences. */ - varray_type reals; - /* True if it's a strength reduction candidate. */ - bool strred_cand; - /* True if it's a load PRE candidate. */ - bool loadpre_cand; - /* The euses/ephis in preorder dt order. */ - varray_type euses_dt_order; - /* The name of the temporary for this expression. */ - tree temp; -}; - - -/* Cache of expressions generated for given phi operand, to avoid - recomputation and wasting memory. */ -static tree *phi_pred_cache; -static int n_phi_preds; + struct value_set_node *next; +} *value_set_node_t; -/* Trying to lookup ephi pred operand indexes takes forever on graphs - that have high connectivity because it's an O(n) linked list - traversal. Thus, we set up a hashtable that tells us the operand - index for a given edge. */ -typedef struct ephi_pred_index_elt +/* A value set, which is the head of the linked list, and we also keep + the tail because we have to append for the topolofical sort. */ +typedef struct value_set { - tree ephi; - edge edge; - int opnd; -} ephi_pindex_t; - -/* Hash an (ephi, edge, opnd) tuple. */ + value_set_node_t head; + value_set_node_t tail; + size_t length; + bool indexed; + bitmap values; + +} *value_set_t; -static hashval_t -ephi_pindex_hash (const void *p) +/* All of the following sets, except for TMP_GEN, are indexed. + TMP_GEN is only ever iterated over, we never check what values + exist in it. */ +typedef struct bb_value_sets { - const ephi_pindex_t *ep = (const ephi_pindex_t *)p; - return htab_hash_pointer (ep->ephi) + htab_hash_pointer (ep->edge); -} + value_set_t exp_gen; + value_set_t phi_gen; + value_set_t tmp_gen; + value_set_t avail_out; + value_set_t antic_in; + value_set_t new_sets; +} *bb_value_sets_t; -/* Determine equality of an (ephi, edge, opnd) tuple. */ +#define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen +#define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen +#define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen +#define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out +#define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in +#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets -static int -ephi_pindex_eq (const void *p1, const void *p2) +static struct { - const ephi_pindex_t *ep1 = (const ephi_pindex_t *)p1; - const ephi_pindex_t *ep2 = (const ephi_pindex_t *)p2; - - return ep1->ephi == ep2->ephi && ep1->edge == ep2->edge; -} + int eliminations; + int insertions; + int phis; +} pre_stats; -/* The (ephi, edge) => opnd mapping hashtable. */ -static htab_t ephi_pindex_htab; +static tree find_leader (value_set_t, tree); +static void value_insert_into_set (value_set_t, tree); +static void insert_into_set (value_set_t, tree); +static void add_to_value (tree, tree); +static value_set_t set_new (bool); +static bool is_undefined_value (tree); -/* Add an ephi predecessor to a PHI. */ +/* We can add and remove elements and entries to and from sets + and hash tables, so we use alloc pools for them. */ -static int -add_ephi_pred (tree phi, tree def, edge e) -{ - int i = EPHI_NUM_ARGS (phi); - void **slot; - ephi_pindex_t ep, *epp; - - EPHI_ARG_PRED (phi, i) = def; - EPHI_ARG_EDGE (phi, i) = e; +static alloc_pool value_set_pool; +static alloc_pool value_set_node_pool; +static alloc_pool binary_node_pool; +static alloc_pool unary_node_pool; - ep.ephi = phi; - ep.edge = e; - slot = htab_find_slot (ephi_pindex_htab, (void *)&ep, INSERT); - if (*slot == NULL) - { - epp = xmalloc (sizeof (*epp)); - epp->ephi = phi; - epp->edge = e; - epp->opnd = i; - *slot = (void *)epp; - } - else - abort (); - - EPHI_NUM_ARGS (phi)++; - return i; -} +/* The value table that maps expressions to values. */ +static htab_t value_table; -/* Create a new EPHI node at basic block BB. */ +/* The phi_translate_table caches phi translations for a given + expression and predecessor. */ +static htab_t phi_translate_table; -static tree -create_ephi_node (basic_block bb, unsigned int add) -{ - tree phi; - int len; - edge e; - size_t size; - bb_ann_t ann; - - for (len = 0, e = bb->pred; e; e = e->pred_next) - len++; - size = (sizeof (struct tree_ephi_node) - + ((len - 1) * sizeof (struct ephi_arg_d))); - phi = xmalloc (size); - memset (phi, 0, size); - if (add) - { - ann = bb_ann (bb); - if (ann->ephi_nodes == NULL) - ann->ephi_nodes = phi; - else - chainon (ann->ephi_nodes, phi); - } - pre_stats.ephi_allocated += size; - pre_stats.ephis_current += 1; - TREE_SET_CODE (phi, EPHI_NODE); - EPHI_NUM_ARGS (phi) = 0; - EPHI_ARG_CAPACITY (phi) = len; +/* Map expressions to values. These are simple pairs of expressions + and the values they represent. To find the value represented by + an expression, we use a hash table where the elements are {e,v} + pairs, and the expression is the key. */ - /* Associate BB to the PHI node. */ - set_bb_for_stmt (phi, bb); +typedef struct val_expr_pair_d +{ + tree v, e; + hashval_t hashcode; +} *val_expr_pair_t; - return phi; -} -/* Given DEF (which can be an SSA_NAME or entire statement), and VAR, - find a use of VAR on the RHS of DEF, if one exists. Abort if we - can't find one. */ +/* Hash a {v,e} pair. We really only hash the expression. */ -static inline tree -find_rhs_use_for_var (tree def, tree var) +static hashval_t +val_expr_pair_hash (const void *p) { - tree ret = maybe_find_rhs_use_for_var (def, var, 0); - if (!ret) - abort (); - return ret; + const val_expr_pair_t ve = (val_expr_pair_t) p; + return ve->hashcode; } -/* Determine if two trees are referring to the same variable. - Handles SSA_NAME vs non SSA_NAME, etc. Uses operand_equal_p for - non-trivial cases (INDIRECT_REF and friends). */ -static inline bool -names_match_p (const tree t1, const tree t2) -{ - tree name1, name2; +/* Are {e2,v2} and {e1,v1} the same? Again, only the expression + matters. */ - if (t1 == t2) +static int +val_expr_pair_expr_eq (const void *p1, const void *p2) +{ + const val_expr_pair_t ve1 = (val_expr_pair_t) p1; + const val_expr_pair_t ve2 = (val_expr_pair_t) p2; + tree e1 = ve1->e; + tree e2 = ve2->e; + tree te1; + tree te2; + if (e1 == e2) return true; - - if (TREE_CODE (t1) == INDIRECT_REF) - return names_match_p (TREE_OPERAND (t1, 0), t2); - - if (TREE_CODE (t2) == INDIRECT_REF) - return names_match_p (t1, TREE_OPERAND (t2, 0)); - - if (TREE_CODE (t1) == SSA_NAME) - name1 = SSA_NAME_VAR (t1); - else if (DECL_P (t1)) - name1 = t1; - else - name1 = NULL_TREE; - - if (TREE_CODE (t2) == SSA_NAME) - name2 = SSA_NAME_VAR (t2); - else if (DECL_P (t2)) - name2 = t2; - else - name2 = NULL_TREE; - if (name1 == NULL_TREE && name2 != NULL_TREE) - return false; - if (name2 == NULL_TREE && name1 != NULL_TREE) - return false; - if (name1 == NULL_TREE && name2 == NULL_TREE) - return operand_equal_p (t1, t2, 0); + te1 = TREE_TYPE (e1); + te2 = TREE_TYPE (e2); + if (TREE_CODE (e1) == TREE_CODE (e2) + && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) + && operand_equal_p (e1, e2, 0)) + return true; - return name1 == name2; + return false; } -/* Given DEF (which can be an SSA_NAME or entire statement), and VAR, - find a use of VAR on the RHS of DEF, if one exists. Return NULL if - we cannot find one. */ -static inline tree -maybe_find_rhs_use_for_var (tree def, tree var, unsigned int startpos) -{ - use_optype uses; - size_t i; +/* Get the value handle of EXPR. This is the only correct way to get + the value handle for a "thing". */ - if (SSA_VAR_P (def)) - { - if (names_match_p (var, def)) - return def; - return NULL_TREE; - } - get_stmt_operands (def); - uses = STMT_USE_OPS (def); - - for (i = startpos; i < NUM_USES (uses); i++) +tree +get_value_handle (tree expr) +{ + /* We should never see these. */ + if (DECL_P (expr)) + abort (); + else if (TREE_CODE (expr) == SSA_NAME) { - tree use = USE_OP (uses, i); - if (names_match_p (use, var)) - return use; + return SSA_NAME_VALUE (expr); } - return NULL_TREE; -} - -/* Determine if an injuring def is one which we can repair, and thus, - ignore for purposes of determining the version of a variable. */ - -static inline bool -okay_injuring_def (tree inj, tree var) -{ - /* Acceptable injuries are those which - 1. aren't empty statements. - 2. aren't phi nodes. - 3. contain a use of VAR on the RHS. */ - if (!inj || IS_EMPTY_STMT (inj) - || TREE_CODE (inj) == PHI_NODE - || !maybe_find_rhs_use_for_var (inj, var, 0)) - return false; - return true; -} - -/* Return true if INJ is an injuring definition */ - -static bool -is_injuring_def (struct expr_info *ei, tree inj) -{ - /* Things that are never injuring definitions. */ - if (!inj || IS_EMPTY_STMT (inj) || TREE_CODE (inj) == PHI_NODE) - return false; - - /* Things we can't handle. */ - if (TREE_CODE (TREE_OPERAND (inj, 1)) != PLUS_EXPR - && TREE_CODE (TREE_OPERAND (inj, 1)) != MINUS_EXPR) - return false; - - /* given inj: a1 = a2 + 5 - expr: a3 * c - we are testing: - if (a1 != a3 - || ! (a2 exists) - || a2 != a3) - return false - - Or, in English, if either the assigned-to variable in - the injury is different from the first variable in the - expression, or the incremented variable is different from the - first variable in the expression, punt. - - This makes sure we have something of the form - - a = a {+,-} {expr} - for an expression like "a * 5". - - This limitation only exists because we don't know how to repair - other forms of increments/decrements. */ - if (!names_match_p (TREE_OPERAND (inj, 0), TREE_OPERAND (ei->expr, 0)) - || !TREE_OPERAND (TREE_OPERAND (inj, 1), 0) - || !names_match_p (TREE_OPERAND (TREE_OPERAND (inj, 1), 0), - TREE_OPERAND (ei->expr, 0))) - return false; - - /* If we are strength reducing a multiply, we have the additional - constraints that - 1. {expr} is 1 - 2. {expr} and the RHS of the expression are constants. */ - if (TREE_CODE (ei->expr) == MULT_EXPR) + else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c') { - tree irhs1; - tree irhs2; - tree irhs; - irhs = TREE_OPERAND (inj, 1); - irhs1 = TREE_OPERAND (irhs, 0); - irhs2 = TREE_OPERAND (irhs, 1); - - if (TREE_CODE (irhs2) != INTEGER_CST) - return false; - if (tree_low_cst (irhs2, 0) == 1) - return true; - if (really_constant_p (irhs2) - && really_constant_p (TREE_OPERAND (ei->expr, 1))) - return true; - /* We don't currently support "the injury is inside a loop,expr is - loop-invariant, and b is either loop-invariant or is - another induction variable with respect to the loop." */ - return false; + cst_ann_t ann = cst_ann (expr); + if (ann) + return ann->common.value_handle; + return NULL; } - return true; -} - -/* Find the statement defining VAR, ignoring injuries we can repair. - START is the first potential injuring def. */ - -static tree -factor_through_injuries (struct expr_info *ei, tree start, tree var, - bool *injured) -{ - tree end = start; - - while (is_injuring_def (ei, SSA_NAME_DEF_STMT (end))) + else if (EXPR_P (expr)) { - if (injured) - *injured = true; - end = find_rhs_use_for_var (SSA_NAME_DEF_STMT (end), var); - if (!okay_injuring_def (SSA_NAME_DEF_STMT (end), var)) - break; - if (dump_file) - { - fprintf (dump_file, "Found a real injury:"); - print_generic_stmt (dump_file, SSA_NAME_DEF_STMT (end), dump_flags); - fprintf (dump_file, "\n"); - } - if (injured) - *injured = true; - end = find_rhs_use_for_var (SSA_NAME_DEF_STMT (end), var); + expr_ann_t ann = expr_ann (expr); + if (ann) + return ann->common.value_handle; + return NULL; } - return end; + abort (); } -/* Return true if the result of the EPHI, when transformed into a phi, - will be available. */ -static inline bool -ephi_will_be_avail (tree ephi) +/* Set the value handle for E to V */ + +void +set_value_handle (tree e, tree v) { - if (!EPHI_CANT_BE_AVAIL (ephi)) - if (EPHI_STOPS (ephi)) - return true; - - return false; + if (DECL_P (e)) + abort (); + else if (TREE_CODE (e) == SSA_NAME) + SSA_NAME_VALUE (e) = v; + else if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c') + get_cst_ann (e)->common.value_handle = v; + else if (EXPR_P (e)) + get_expr_ann (e)->common.value_handle = v; } -/* EUSE node pool. We allocate EUSE nodes out of this*/ -static alloc_pool euse_node_pool; - -/* EREF node pool. We allocate regular EREF nodes (like EEXIT_NODE) - out of this. */ -static alloc_pool eref_node_pool; - - -/* To order EREF's in a given block, we assign them each an ID based - on when we see them. */ -static int eref_id_counter = 0; +/* A three tuple {e, pred, v} used to cache phi translations in the + phi_translate_table. */ -/* Creation an expression reference of TYPE. */ - -static tree -create_expr_ref (struct expr_info *ei, tree expr, enum tree_code type, - basic_block bb, tree parent) +typedef struct expr_pred_trans_d { - tree ret; - if (type == EPHI_NODE) - { - int len; - edge e; - - ret = create_ephi_node (bb, 1); - for (len = 0, e = bb->pred; e; e = e->pred_next) - len++; - - EREF_TEMP (ret) = make_phi_node (ei->temp, len); - } - else - { - if (type == EUSE_NODE) - ret = (tree) pool_alloc (euse_node_pool); - else - ret = (tree) pool_alloc (eref_node_pool); - TREE_SET_CODE (ret, type); - memset (ret, 0, tree_size (ret)); - TREE_SET_CODE (ret, type); - pre_stats.eref_allocated += tree_size (ret); - } - - EREF_NAME (ret) = expr; - set_bb_for_stmt (ret, bb); - EREF_STMT (ret) = parent; - EREF_SAVE (ret) = false; - EREF_ID (ret) = eref_id_counter++; - - return ret; -} - - -/* dfphis is a bitmap of where we need to insert ephis due to the - iterated dominance frontier of an expression. */ - -static bitmap dfphis; - -/* varphis is a bitmap of where we need to insert ephis due to the - presence of phis for a variable. */ + tree e; + basic_block pred; + tree v; + hashval_t hashcode; +} *expr_pred_trans_t; -static bitmap varphis; +/* Return the hash value for a phi translation table entry. */ - -/* Function to recursively figure out where EPHI's need to be placed - because of PHI's. - We always place EPHI's where we place PHI's because they are also - partially anticipated expression points (because some expression - alteration reaches that merge point). - - We do this recursively, because we have to figure out - EPHI's for the variables in the PHI as well. */ - -static void -set_var_phis (struct expr_info *ei, tree phi) +static hashval_t +expr_pred_trans_hash (const void *p) { - basic_block bb = bb_for_stmt (phi); - /* If we've already got an EPHI set to be placed in PHI's BB, we - don't need to do this again. */ - if (!bitmap_bit_p (varphis, bb->index) - && !bitmap_bit_p (dfphis, bb->index)) - { - tree phi_operand; - int curr_phi_operand; - bitmap_set_bit (varphis, bb->index); - for (curr_phi_operand = 0; - curr_phi_operand < PHI_NUM_ARGS (phi); - curr_phi_operand++) - { - phi_operand = PHI_ARG_DEF (phi, curr_phi_operand); - /* For strength reduction, factor through injuries we can - repair. */ - if (ei->strred_cand && TREE_CODE (phi_operand) != PHI_NODE) - { - phi_operand = factor_through_injuries (ei, phi_operand, - SSA_NAME_VAR (phi_operand), - NULL); - phi_operand = SSA_NAME_DEF_STMT (phi_operand); - if (dump_file) - { - fprintf (dump_file, "After factoring through injuries:"); - print_generic_stmt (dump_file, phi_operand, dump_flags); - fprintf (dump_file, "\n"); - } - } - - /* If our phi operand is defined by a phi, we need to - record where the phi operands alter the expression as - well, and place EPHI's at each point. */ - if (TREE_CODE (phi_operand) == PHI_NODE) - set_var_phis (ei, phi_operand); - } - } + const expr_pred_trans_t ve = (expr_pred_trans_t) p; + return ve->hashcode; } +/* Return true if two phi translation table entries are the same. */ -/* Clear all the expression reference arrays. */ +static int +expr_pred_trans_eq (const void *p1, const void *p2) +{ + const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1; + const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2; + tree e1 = ve1->e; + tree e2 = ve2->e; + basic_block b1 = ve1->pred; + basic_block b2 = ve2->pred; + tree te1; + tree te2; + + if (b1 != b2) + return false; -static void -clear_all_eref_arrays (void) -{ - basic_block bb; - bb_ann_t ann; + if (e1 == e2) + return true; - FOR_ALL_BB (bb) - { - ann = bb_ann (bb); - if (ann->ephi_nodes) - { - free (ann->ephi_nodes); - pre_stats.ephis_current -= 1; - } - ann->ephi_nodes = NULL; - } -} - -/* EPHI insertion algorithm. */ + te1 = TREE_TYPE (e1); + te2 = TREE_TYPE (e2); -static bool -expr_phi_insertion (bitmap *dfs, struct expr_info *ei) -{ - size_t i, j; - vuse_optype vuses; - use_optype uses; - bool retval = true; - - dfphis = BITMAP_XMALLOC (); - bitmap_zero (dfphis); - varphis = BITMAP_XMALLOC (); - bitmap_zero (varphis); + if (TREE_CODE (e1) == TREE_CODE (e2) + && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) + && operand_equal_p (e1, e2, 0)) + return true; - /* Compute where we need to place EPHIS. There are two types of - places we need EPHI's: Those places we would normally place a - PHI for the occurrence (calculated by determining the IDF+ of - the statement), and those places we need an EPHI due to partial - anticipation. */ - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->occurs); i++) - { - tree occurp = VARRAY_TREE (ei->occurs, i); - tree occur = occurp ? occurp : NULL; - tree killp = VARRAY_TREE (ei->kills, i); - tree kill = killp ? killp : NULL; - tree leftp = VARRAY_TREE (ei->lefts, i); - tree left = leftp ? leftp : NULL; - bitmap temp; - stmt_ann_t ann; - -#ifdef ENABLE_CHECKING - if ((kill && occur) || (left && occur) || (kill && left)) - abort(); -#endif - occurp = occur ? occurp : kill ? killp : leftp; - occur = occur ? occur : kill ? kill : left; - temp = compute_idfs (dfs, occur); - bitmap_a_or_b (dfphis, dfphis, temp); - if (kill != NULL) - continue; - get_stmt_operands (occurp); - ann = stmt_ann (occurp); - uses = USE_OPS (ann); - for (j = 0; j < NUM_USES (uses); j ++) - { - tree use = USE_OP (uses, j); - if (ei->strred_cand) - use = factor_through_injuries (ei, use, SSA_NAME_VAR (use), - NULL); - if (TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE) - continue; - set_var_phis (ei, SSA_NAME_DEF_STMT (use)); - } - if (ei->loadpre_cand && TREE_CODE (ei->expr) == INDIRECT_REF) - { - vuses = VUSE_OPS (ann); - for (j = 0; j < NUM_VUSES (vuses); j ++) - { - tree use = VUSE_OP (vuses, j); - if (ei->strred_cand) - use = factor_through_injuries (ei, use, SSA_NAME_VAR (use), - NULL); - if (TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE) - continue; - set_var_phis (ei, SSA_NAME_DEF_STMT (use)); - } - } - } - /* Union the results of the dfphis and the varphis to get the - answer to everywhere we need EPHIS. */ - bitmap_a_or_b (dfphis, dfphis, varphis); - - /* Now create the EPHI's in each of these blocks. */ - EXECUTE_IF_SET_IN_BITMAP(dfphis, 0, i, - { - tree ref = create_expr_ref (ei, ei->expr, EPHI_NODE, BASIC_BLOCK (i), - NULL); - EREF_PROCESSED (ref) = false; - EPHI_DOWNSAFE (ref) = true; - EPHI_DEAD (ref) = true; - }); -#if 0 - /* If there are no phis, we don't have anything to optimize, - assuming the dominator optimizer took care of it all. */ - if (bitmap_first_set_bit (dfphis) == -1) - retval = false; -#endif - BITMAP_XFREE (dfphis); - BITMAP_XFREE (varphis); - return retval; - + return false; } -/* Return the EPHI at block BB, if one exists. */ +/* Search in the phi translation table for the translation of E in + PRED. Return the translated value, if found, NULL otherwise. */ static inline tree -ephi_at_block (basic_block bb) +phi_trans_lookup (tree e, basic_block pred) { - bb_ann_t ann = bb_ann (bb); - if (ann->ephi_nodes) - return ann->ephi_nodes; + void **slot; + struct expr_pred_trans_d ugly; + ugly.e = e; + ugly.pred = pred; + ugly.hashcode = iterative_hash_expr (e, (unsigned long) pred); + slot = htab_find_slot_with_hash (phi_translate_table, &ugly, ugly.hashcode, + NO_INSERT); + if (!slot) + return NULL; else - return NULL_TREE; + return ((expr_pred_trans_t) *slot)->v; } -/* Depth first numbering array. */ -static int *dfn; -/* Build a depth first numbering array to be used in sorting in - dominator order. */ +/* Add the tuple mapping {e, pred}->v to the phi translation table. */ -static int -build_dfn_array (basic_block bb, int num) +static inline void +phi_trans_add (tree e, tree v, basic_block pred) { - basic_block son; - - if (bb->index >= 0) - dfn[bb->index] = num; - - for (son = first_dom_son (CDI_DOMINATORS, bb); - son; - son = next_dom_son (CDI_DOMINATORS, son)) - num = build_dfn_array (son, ++num); - return num; + void **slot; + expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair)); + new_pair->e = e; + new_pair->pred = pred; + new_pair->v = v; + new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred); + slot = htab_find_slot_with_hash (phi_translate_table, new_pair, + new_pair->hashcode, INSERT); + if (*slot) + free (*slot); + *slot = (void *) new_pair; } +/* Search in TABLE for an existing instance of expression E, + and return its value, or NULL if none has been set. */ -/* Compare two EREF's in terms of dominator preorder. Return -1 if - ELEM1 goes before ELEM2, 1 if ELEM1 goes after ELEM2, and 0 if they - are equal. */ - -static int -eref_compare (const void *elem1, const void *elem2) +static inline tree +lookup (htab_t table, tree e) { - tree t1 = *(tree *)elem1; - tree t2 = *(tree *)elem2; - basic_block bb1, bb2; - if (t1 == t2) - return 0; - bb1 = bb_for_stmt (t1); - bb2 = bb_for_stmt (t2); - if (bb1 == bb2) - { - if (TREE_CODE (t1) == EEXIT_NODE) - return 1; - if (TREE_CODE (t2) == EEXIT_NODE) - return -1; - if (TREE_CODE (t1) == EPHI_NODE) - return -1; - if (TREE_CODE (t2) == EPHI_NODE) - return 1; - if ((TREE_CODE (t1) == EUSE_NODE && EUSE_PHIOP (t1)) - && (TREE_CODE (t2) == EUSE_NODE && !EUSE_PHIOP (t2))) - return 1; - if ((TREE_CODE (t1) == EUSE_NODE && !EUSE_PHIOP (t1)) - && (TREE_CODE (t2) == EUSE_NODE && EUSE_PHIOP (t2))) - return -1; - if (TREE_CODE (t1) == EUSE_NODE && TREE_CODE (t2) == EUSE_NODE) - return EREF_ID (t1) - EREF_ID (t2); - if (TREE_CODE (t1) == EPHI_NODE && TREE_CODE (t2) == EPHI_NODE) - abort (); - - } + void **slot; + struct val_expr_pair_d ugly = {NULL, NULL, 0}; + ugly.e = e; + ugly.hashcode = iterative_hash_expr (e,0); + slot = htab_find_slot_with_hash (table, &ugly, ugly.hashcode, NO_INSERT); + if (!slot) + return NULL_TREE; else - { - if (dfn[bb1->index] == dfn[bb2->index]) - { - if (dominated_by_p (CDI_DOMINATORS, bb1, bb2)) - return 1; - else - return -1; - } - else - return (dfn[bb1->index] < dfn[bb2->index]) ? -1 : 1; - } - - abort (); + return ((val_expr_pair_t) *slot)->v; } -/* Create expression references for occurrences, kills, phi operands, - and the like. At the same time, insert the occurrences into the - ei->euses_dt_order array in the proper order. If this function had - any use outside of rename_1, you could split it into two - functions, one creating, one inserting. */ +/* Add E to the expression set of V. */ -static void -create_and_insert_occ_in_preorder_dt_order (struct expr_info *ei) +static inline void +add_to_value (tree v, tree e) { - size_t i; - edge succ; - tree curr_phi_pred = NULL_TREE; - basic_block block; - - /* The ephis references were already created, so just push them into - the euses_dt_order list. */ - FOR_EACH_BB (block) - { - tree ephi = ephi_at_block (block); - /* The ordering for a given BB is EPHI's, real/left/kill - occurrences, phi preds, exit occurrences. */ - if (ephi != NULL_TREE) - VARRAY_PUSH_TREE (ei->euses_dt_order, ephi); - } - - /* The non-ephis have to actually be created, so do that, then push - them into the list. */ - - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->occurs); i++) - { - tree newref; - tree current; - current = VARRAY_TREE (ei->occurs, i); - current = current ? current : VARRAY_TREE (ei->kills, i); - current = current ? current : VARRAY_TREE (ei->lefts, i); - block = bb_for_stmt (current); - if (VARRAY_TREE (ei->kills, i) != NULL) - { - tree killexpr = VARRAY_TREE (ei->kills, i); - tree killname = ei->expr; - newref = create_expr_ref (ei, killname, EKILL_NODE, block, killexpr); - VARRAY_PUSH_TREE (ei->euses_dt_order, newref); - } - else if (VARRAY_TREE (ei->lefts, i) != NULL) - { - tree occurexpr = VARRAY_TREE (ei->lefts, i); - tree occurname; - occurname = ei->expr; - newref = create_expr_ref (ei, occurname, EUSE_NODE, block, - occurexpr); - EUSE_DEF (newref) = NULL_TREE; - EUSE_LVAL (newref) = true; - EREF_CLASS (newref) = -1; - EUSE_PHIOP (newref) = false; - EREF_PROCESSED (newref) = false; - VARRAY_PUSH_TREE (ei->euses_dt_order, newref); - } - else - { - tree occurexpr = VARRAY_TREE (ei->occurs, i); - tree occurname; - occurname = ei->expr; - newref = create_expr_ref (ei, occurname, EUSE_NODE, block, - occurexpr); - EUSE_DEF (newref) = NULL_TREE; - EREF_CLASS (newref) = -1; - EUSE_PHIOP (newref) = false; - EREF_PROCESSED (newref) = false; - VARRAY_PUSH_TREE (ei->euses_dt_order, newref); - } - } - - /* Lastly, we need to create and insert the ephi operand occurrences - into the list. */ - FOR_ALL_BB (block) - { - /* Insert the phi operand occurrences into the list at the - successors.*/ - for (succ = block->succ; succ; succ = succ->succ_next) - { - if (succ->dest != EXIT_BLOCK_PTR) - { - tree ephi = ephi_at_block (succ->dest); - if (ephi != NULL - && !bitmap_bit_p (created_phi_preds, block->index)) - { - tree newref = create_expr_ref (ei, 0, EUSE_NODE, block, NULL); - curr_phi_pred = newref; - VARRAY_PUSH_TREE (ei->euses_dt_order, newref); - EUSE_DEF (newref) = NULL_TREE; - EREF_CLASS (newref) = -1; - EUSE_PHIOP (newref) = true; - EREF_SAVE (newref) = false; - EREF_RELOAD (newref) = false; - EUSE_INSERTED (newref) = false; - EREF_PROCESSED (newref) = false; - bitmap_set_bit (created_phi_preds, block->index); - add_ephi_pred (ephi, newref, succ); - } - else if (ephi != NULL) - { -#ifdef ENABLE_CHECKING - if (curr_phi_pred == NULL_TREE) - abort(); +#if DEBUG_VALUE_EXPRESSIONS + var_ann_t va = var_ann (v); +#endif + /* For values representing numerical constants, we mark + TREE_CONSTANT as true and set the tree chain to the actual + constant. This is because unlike values involving expressions, + which are only available to use where the expressions are live, a + constant can be remade anywhere, and thus, is available + everywhere. */ + if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c') + { + TREE_CONSTANT (v) = true; + TREE_CHAIN (v) = e; + } +#if DEBUG_VALUE_EXPRESSIONS + if (va->expr_set == NULL) + va->expr_set = set_new (false); + insert_into_set (va->expr_set, e); #endif - add_ephi_pred (ephi, curr_phi_pred, succ); - } - } - else if (succ->dest == EXIT_BLOCK_PTR && !(succ->flags & EDGE_FAKE)) - { - /* No point in inserting exit blocks into heap first, since - they'll never be anything on the stack. */ - tree newref; - newref = create_expr_ref (ei, ei->expr, EEXIT_NODE, - block, - NULL); - VARRAY_PUSH_TREE (ei->euses_dt_order, newref); - } - } - } - qsort (ei->euses_dt_order->data.tree, - VARRAY_ACTIVE_SIZE (ei->euses_dt_order), - sizeof (tree), - eref_compare); } - -/* Assign a new redundancy class to the occurrence, and push it on the - renaming stack. */ +/* Insert E into TABLE with value V, and add E to the value set for V. */ -static void -assign_new_class (tree occ, varray_type * stack, varray_type * stack2) +static inline void +add (htab_t table, tree e, tree v) { - /* class(occ) <- count - Push(occ, stack) - count <- count + 1 - */ - EREF_CLASS (occ) = class_count; - VARRAY_PUSH_TREE (*stack, occ); - if (stack2) - VARRAY_PUSH_TREE (*stack2, occ); - class_count++; + + void **slot; + val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d)); + new_pair->e = e; + new_pair->v = v; + new_pair->hashcode = iterative_hash_expr (e, 0); + slot = htab_find_slot_with_hash (table, new_pair, new_pair->hashcode, + INSERT); + if (*slot) + free (*slot); + *slot = (void *) new_pair; + set_value_handle (e, v); + + add_to_value (v, e); + } -/* Determine if two real occurrences have the same ESSA version. - We do this by hashing the expressions and comparing the hash - values. Even if they don't match, we then see if this is a - strength reduction candidate, and if so, if the use is simply - injured. */ +static int pre_uid; -static inline bool -same_e_version_real_occ_real_occ (struct expr_info *ei, - const tree def, const tree use) +/* Create a new value handle for EXPR. */ +static tree +create_new_value (tree expr) { - hashval_t expr1val; - hashval_t expr2val; - vuse_optype vuses; - size_t i; - const tree t1 = EREF_STMT (def); - const tree t2 = EREF_STMT (use); - - expr1val = iterative_hash_expr (TREE_OPERAND (t1, 1), 0); - expr2val = iterative_hash_expr (TREE_OPERAND (t2, 1), 0); - - if (expr1val == expr2val) - { - vuses = STMT_VUSE_OPS (t1); - for (i = 0; i < NUM_VUSES (vuses); i++) - expr1val = iterative_hash_expr (VUSE_OP (vuses, i), expr1val); - vuses = STMT_VUSE_OPS (t2); - for (i = 0; i < NUM_VUSES (vuses); i++) - expr2val = iterative_hash_expr (VUSE_OP (vuses, i), expr2val); - if (expr1val != expr2val) - return false; - } + tree a = create_tmp_var_raw (TREE_TYPE (expr), "value"); + create_var_ann (a); + var_ann (a)->uid = pre_uid++; - /* If the def is injured, and the expressions have the same value, - then the use is injured. */ - if (expr1val == expr2val) - { - if (EREF_INJURED (def)) - EREF_INJURED (use) = true; - return true; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Created value "); + print_generic_expr (dump_file, a, dump_flags); + fprintf (dump_file, " for "); + print_generic_expr (dump_file, expr, dump_flags); + fprintf (dump_file, "\n"); } + return a; +} - /* Even if the expressions don't have the same value, it might be - the case that the use is simply injured, in which case, it's - still okay. */ - if (expr1val != expr2val && ei->strred_cand) +/* Like lookup, but adds V as the value for E if E does not have a value. */ +static inline tree +lookup_or_add (htab_t table, tree e) +{ + tree x = lookup (table, e); + if (x == NULL_TREE) { - if (injured_real_occ_real_occ (ei, def, use)) - { - EREF_INJURED (use) = true; - return true; - } + tree v; + v = create_new_value (e); + add (table, e, v); + x = v; } - return false; -} - -/* Determine if the use occurrence is injured. - TODO: Finish actually implementing this. */ - -static inline bool -injured_real_occ_real_occ (struct expr_info *ei ATTRIBUTE_UNUSED, - tree def ATTRIBUTE_UNUSED, - tree use ATTRIBUTE_UNUSED) -{ - tree defstmt; - tree defvar; - - defstmt = EREF_STMT (def); - if (TREE_CODE (TREE_OPERAND (defstmt, 0)) != SSA_NAME) - return false; - - defvar = TREE_OPERAND (defstmt, 0); - /* XXX: Implement. */ - return false; - + set_value_handle (e, x); + return x; } -/* Determine the operand number of edge E in EPHI. */ + +/* Search in the bitmap for SET to see if E exists. */ -static inline int -opnum_of_ephi (const tree ephi, const edge e) +static inline bool +value_exists_in_set_bitmap (value_set_t set, tree e) { - ephi_pindex_t ep, *epp; - - ep.ephi = ephi; - ep.edge = e; - epp = htab_find (ephi_pindex_htab, &ep); - if (epp == NULL) + if (TREE_CODE (e) != VAR_DECL) abort (); - return epp->opnd; -} -/* Determine the phi operand index for J in PHI. */ - -static inline int -opnum_of_phi (tree phi, int j) -{ - int i; - /* We can't just count predecessors, since tree-ssa.c generates them - when it sees a phi in the successor during it's traversal. So the - order is dependent on the traversal order. */ - for (i = 0 ; i < PHI_NUM_ARGS (phi); i++) - if (PHI_ARG_EDGE (phi, i)->src->index == j) - return i; - - abort(); + if (!set->values) + return false; + return bitmap_bit_p (set->values, get_var_ann (e)->uid); } -/* Generate EXPR as it would look in basic block PRED (using the phi in - block BB). We do this by replacing the variables with the phi - argument definitions for block J if they are defined by a phi in - block BB. */ +/* Remove E from the bitmap for SET. */ static void -generate_expr_as_of_bb (tree expr, basic_block pred, basic_block bb) +value_remove_from_set_bitmap (value_set_t set, tree e) { - use_optype uses = STMT_USE_OPS (expr); - bool replaced_constants = false; - size_t k; - - for (k = 0; k < NUM_USES (uses); k++) - { - tree *vp = USE_OP_PTR (uses, k); - tree v = *vp; - tree phi; - - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) - { - if (PHI_RESULT (phi) == v) - { - int opnum = opnum_of_phi (phi, pred->index); - tree p = PHI_ARG_DEF (phi, opnum); - replace_exp (vp, p); - if (!phi_ssa_name_p (p)) - replaced_constants = true; - break; - } - } - } - - /* If we've substituted in new constants, we must be sure to - simplify the result lest we crash in get_expr_operands. */ - if (replaced_constants) - fold_stmt (&expr); + if (TREE_CODE (e) != VAR_DECL) + abort (); +#ifdef ENABLE_CHECKING + if (!set->indexed) + abort (); +#endif + if (!set->values) + return; + bitmap_clear_bit (set->values, get_var_ann (e)->uid); } -/* Generate VUSE ops as they would look in basic block PRED (using the - phi in block BB). Done the same way as we do generation of regular - ops for the bb. */ -static void -generate_vops_as_of_bb (tree expr, basic_block pred, basic_block bb) -{ - vuse_optype vuses = STMT_VUSE_OPS (expr); - size_t i; - - for (i = 0; i < NUM_VUSES (vuses); i++) - { - tree v = VUSE_OP (vuses, i); - tree phi; +/* Insert the value number E into the bitmap of values existing in + SET. */ - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) - { - if (PHI_RESULT (phi) == v) - { - int opnum = opnum_of_phi (phi, pred->index); - tree p = PHI_ARG_DEF (phi, opnum); - replace_exp (VUSE_OP_PTR (vuses, i), p); - break; - } - } - } -} - -/* Make a copy of Z as it would look in basic block PRED, using the PHIs - in BB. */ - -static tree -subst_phis (struct expr_info *ei, tree Z, basic_block pred, basic_block bb) +static inline void +value_insert_into_set_bitmap (value_set_t set, tree e) { - tree stmt_copy; - size_t i; - - /* Return the cached version, if we have one. */ - if (pred->index < n_phi_preds - && phi_pred_cache[pred->index] != NULL_TREE) - return phi_pred_cache[pred->index]; - - /* Otherwise, generate a new expression. */ - pre_stats.exprs_generated++; - stmt_copy = unshare_expr (Z); - create_stmt_ann (stmt_copy); - modify_stmt (stmt_copy); - get_stmt_operands (stmt_copy); - generate_expr_as_of_bb (stmt_copy, pred, bb); - set_bb_for_stmt (stmt_copy, bb); - modify_stmt (stmt_copy); - get_stmt_operands (stmt_copy); - - /* If we have vuses on the original statement, and we still have - use_ops on the generated expr, we need to copy the vuses. */ - - if (ei->loadpre_cand - && NUM_VUSES (STMT_VUSE_OPS (Z)) != 0 - && NUM_USES (STMT_USE_OPS (stmt_copy)) != 0) - { - vuse_optype vuses = STMT_VUSE_OPS (Z); - remove_vuses (stmt_copy); - - start_ssa_stmt_operands (stmt_copy); - for (i = 0; i < NUM_VUSES (vuses); i++) - add_vuse (VUSE_OP (vuses, i), stmt_copy); - finalize_ssa_stmt_operands (stmt_copy); - - generate_vops_as_of_bb (stmt_copy, pred, bb); - } - else + if (TREE_CODE (e) != VAR_DECL) + abort (); +#ifdef ENABLE_CHECKING + if (!set->indexed) + abort (); +#endif + if (set->values == NULL) { - remove_vuses (stmt_copy); - remove_v_may_defs (stmt_copy); - remove_v_must_defs (stmt_copy); + set->values = BITMAP_GGC_ALLOC (); + bitmap_clear (set->values); } - - if (pred->index < n_phi_preds) - phi_pred_cache[pred->index] = stmt_copy; - return stmt_copy; + bitmap_set_bit (set->values, get_var_ann (e)->uid); } -/* Determine if def and use_tree should have the same e-version. We do - this by simply determining if something modifies the expression - between DEF and USE_TREE. USE_TREE was generated from the OPND_NUM'th - operand of the EPHI in USE_BB. If it is modified, we determine if - it is simply injured, and thus, okay. */ +/* Create a new set. */ -static inline bool -same_e_version_real_occ_phi_opnd (struct expr_info *ei, tree def, - basic_block use_bb, int opnd_num, - tree use_tree, bool *injured) +static value_set_t +set_new (bool indexed) { - bool not_mod = true; - *injured = false; - - if (load_modified_real_occ_real_occ (EREF_STMT (def), - use_tree)) - not_mod = false; - - if (not_mod) - return true; - else if (ei->strred_cand) - { - if (injured_real_occ_phi_opnd (ei, def, use_bb, opnd_num)) - return true; - } - return false; + value_set_t ret; + ret = pool_alloc (value_set_pool); + ret->head = ret->tail = NULL; + ret->length = 0; + ret->indexed = indexed; + ret->values = NULL; + return ret; } -/* Determine whether the OPND_NUM'th operand of USE_BB's EPHI is an - injured version of DEF. */ -static inline bool -injured_real_occ_phi_opnd (struct expr_info *ei ATTRIBUTE_UNUSED, - tree def ATTRIBUTE_UNUSED, - basic_block use_bb ATTRIBUTE_UNUSED, - int opnd_num ATTRIBUTE_UNUSED) -{ - /* XXX: Implement. */ - return false; -} -/* Determine whether the expression is modified between DEF and USE, - by comparing the hash values of the two expressions. */ -static inline bool -load_modified_real_occ_real_occ (tree def, tree use) +/* Insert EXPR into SET. */ + +static void +insert_into_set (value_set_t set, tree expr) { - hashval_t expr1val; - hashval_t expr2val; - vuse_optype vuses; - size_t i; + value_set_node_t newnode = pool_alloc (value_set_node_pool); + tree val = get_value_handle (expr); + if (DECL_P (expr)) + abort (); - if (TREE_CODE (def) == VA_ARG_EXPR) - expr1val = iterative_hash_expr (def, 0); - else - expr1val = iterative_hash_expr (TREE_OPERAND (def, 1), 0); + if (val == NULL) + abort (); - if (TREE_CODE (use) == VA_ARG_EXPR) - expr2val = iterative_hash_expr (use, 0); - else - expr2val = iterative_hash_expr (TREE_OPERAND (use, 1), 0); - - if (expr1val == expr2val) - { - vuses = STMT_VUSE_OPS (def); - for (i = 0; i < NUM_VUSES (vuses); i++) - expr1val = iterative_hash_expr (VUSE_OP (vuses, i), expr1val); - vuses = STMT_VUSE_OPS (use); - for (i = 0; i < NUM_VUSES (vuses); i++) - expr2val = iterative_hash_expr (VUSE_OP (vuses, i), expr2val); - if (expr1val != expr2val) - return false; - } - return expr1val != expr2val; -} + /* For indexed sets, insert the value into the set value bitmap. + For all sets, add it to the linked list and increment the list + length. */ + if (set->indexed) + value_insert_into_set_bitmap (set, val); -/* Determine if the expression is modified between the start of BB, - and the use at USE, ignoring phis. We do this by simple - domination, because of the properties of SSA. */ -static bool -load_modified_phi_result (basic_block bb, tree use) -{ - basic_block defbb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); - if (defbb != bb) + newnode->next = NULL; + newnode->expr = expr; + set->length ++; + if (set->head == NULL) { - /* This guards against moving around undefined variables. - However, PARM_DECL is special because it *IS* live on entry, - so it's not really undefined. */ - if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) != PARM_DECL) - return true; - else if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) == PARM_DECL) - return false; - if (dominated_by_p (CDI_DOMINATORS, bb, defbb)) - return false; + set->head = set->tail = newnode; } else { - if (TREE_CODE (SSA_NAME_DEF_STMT (use)) == PHI_NODE) - return false; - } - return true; -} - -/* Determine if the variables in EXP are modified between DEF and - USE. If they are, we have to give a new e-version to the result. - For load PRE, we have to check the vuses too. For strength - reduction, we need to check whether the modification is a simple - injury. */ - -static bool -same_e_version_phi_result (struct expr_info *ei, tree def, tree exp, - tree use) -{ - stmt_ann_t ann = stmt_ann (exp); - bool not_mod = true; - size_t i; - use_optype real_expuses = USE_OPS (ann); - vuse_optype expuses; - - - if (NUM_USES (real_expuses) == 0) - return false; - - for (i = 0; i < NUM_USES (real_expuses) && not_mod; i++) - { - tree *use1p = USE_OP_PTR (real_expuses, i); - tree use1; - if (!use1p) - continue; - use1 = *use1p; - if (load_modified_phi_result (bb_for_stmt (def), use1)) - not_mod = false; - } - - if (not_mod && ei->loadpre_cand) - { - expuses = VUSE_OPS (ann); - - for (i = 0; i < NUM_VUSES (expuses) && not_mod; i++) - { - tree use1 = VUSE_OP (expuses, i); - if (load_modified_phi_result (bb_for_stmt (def), use1)) - not_mod = false; - } + set->tail->next = newnode; + set->tail = newnode; } - - if (not_mod) - return true; - else if (ei->strred_cand) - { - if (injured_phi_result_real_occ (ei, def, exp, bb_for_stmt (use))) - { - EREF_INJURED (use) = true; - return true; - } - } - - return false; } -/* Determine whether USE_TREE is an injured version of DEF. */ - -static inline bool -injured_phi_result_real_occ (struct expr_info *ei ATTRIBUTE_UNUSED, - tree def ATTRIBUTE_UNUSED, - tree use_tree ATTRIBUTE_UNUSED, - basic_block use_bb ATTRIBUTE_UNUSED) -{ - /* XXX: Implement. */ - return false; -} - -/* Delayed renaming checks to make sure the optimistic assumptions - about ephi operand versions in rename_1 actually turned out to be - true. This requires generating the expressions for each ephi - operand, and comparing them to the versions of the occurrence it is - defined by. - Delayed rename handling is done like open64 does it. Basically, - like the delayed renaming is described in the paper, with - extensions for strength reduction. */ +/* Copy the set ORIG to the set DEST. */ static void -process_delayed_rename (struct expr_info *ei, tree use, tree real_occ) +set_copy (value_set_t dest, value_set_t orig) { - tree exp_phi = use; - int opnd_num = 0; + value_set_node_t node; + + if (!orig || !orig->head) + return; - /* We only care about operands we actually have DELAYED_RENAME set - on. */ - for (opnd_num = 0; opnd_num < EPHI_NUM_ARGS (exp_phi); opnd_num++) + for (node = orig->head; + node; + node = node->next) { - tree opnd = EPHI_ARG_DEF (exp_phi, opnd_num); - if (EPHI_ARG_DELAYED_RENAME (exp_phi, opnd_num)) - { - tree def; - tree newexp; - - /* Mark it as being processed, then generate the ephi - operand expression. */ - EPHI_ARG_DELAYED_RENAME (exp_phi, opnd_num) = false; - def = opnd; - newexp = subst_phis (ei, real_occ, - EPHI_ARG_EDGE (exp_phi, opnd_num)->src, - bb_for_stmt (exp_phi)); - - /* For operands defined by EPHIs, we need to compare the - generated expression and the phi result. - For operands defined by real occurrences, we simply compare - the phi operand and the real occurrence. */ - if (TREE_CODE (def) == EPHI_NODE) - { - tree tmp_use = EPHI_ARG_PRED (exp_phi, opnd_num); - EREF_STMT (tmp_use) = newexp; - if (same_e_version_phi_result (ei, def, newexp, - tmp_use)) - { - - if (EREF_INJURED (tmp_use)) - { - EREF_INJURED (tmp_use) = false; - EPHI_ARG_INJURED (exp_phi, opnd_num) = true; - } - if (EREF_STMT (def) == NULL) - { - /* If it was injured, we need to make up a new - phi result with the actually injured - version. */ - if (EPHI_ARG_INJURED (exp_phi, opnd_num)) - { - /* XXX: Allocate phi result with correct version. */ - - } - EREF_STMT (def) = newexp; - process_delayed_rename (ei, def, newexp); - } - } - /* If it's not the same version, the defining ephi can't - be downsafe, and the operand is not really defined by - anything. */ - else - { - EPHI_DOWNSAFE (def) = false; - EPHI_ARG_DEF (exp_phi, opnd_num) = NULL; - } - } - else if (TREE_CODE (def) == EUSE_NODE && !EUSE_PHIOP (def)) - { - bool injured = false; - if (same_e_version_real_occ_phi_opnd (ei, def, - bb_for_stmt (use), - opnd_num, newexp, &injured)) - { - tree tmp_use = EPHI_ARG_PRED (exp_phi, opnd_num); - EPHI_ARG_HAS_REAL_USE (exp_phi, opnd_num) = true; - /* EREF_STMT (opnd) = EREF_STMT (def); */ - if (injured || EREF_INJURED (def)) - EREF_INJURED (def) = true; - if (injured || EREF_INJURED (def)) - EREF_INJURED (opnd) = true; - else - EREF_STMT (tmp_use) = EREF_STMT (def); - if (EUSE_DEF (def) != NULL) - EPHI_ARG_DEF (exp_phi, opnd_num) = EUSE_DEF (def); - else - EPHI_ARG_DEF (exp_phi, opnd_num) = def; - } - else - { - EPHI_ARG_DEF (exp_phi, opnd_num) = NULL; - } - } - } + insert_into_set (dest, node->expr); } } -/* For the uninitiated, the algorithm is a modified SSA renaming - algorithm (working on expressions rather than variables) . We - attempt to determine which expression occurrences have the same - ESSA version (we call it class, for equivalence/redundancy class, - which is what the papers call it. Open64 calls it e-version), and - which occurrences are actually operands for an EPHI (since this has - to be discovered from the program). - - Renaming is done like Open64 does it. Basically as the paper says, - except that we try to use earlier defined occurrences if they are - available in order to keep the number of saves down. */ +/* Remove EXPR from SET. */ static void -rename_1 (struct expr_info *ei) +set_remove (value_set_t set, tree expr) { - tree occur; - basic_block phi_bb; - size_t i; - varray_type stack; - - VARRAY_GENERIC_PTR_NOGC_INIT (stack, 1, "Stack for renaming"); - - /* Start by creating and inserting the occurrences in preorder, - dominator tree into a list. */ - create_and_insert_occ_in_preorder_dt_order (ei); - - /* Walk the occurrences. */ - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) - { - occur = VARRAY_TREE (ei->euses_dt_order, i); - - /* The current occurrence can't have the same version as - something on the top of the stack unless it is in a basic - block dominated by the basic block of the occurrence on the - top of the stack. */ - while (VARRAY_ACTIVE_SIZE (stack) > 0 - && !dominated_by_p (CDI_DOMINATORS, - bb_for_stmt (occur), - bb_for_stmt (VARRAY_TOP_TREE (stack)))) - - VARRAY_POP (stack); + value_set_node_t node, prev; - /* If the stack is empty, we assign a new version since it isn't - dominated by any other version. */ - if (VARRAY_ACTIVE_SIZE (stack) == 0 || VARRAY_TOP_TREE (stack) == NULL) - { - if (TREE_CODE (occur) == EPHI_NODE) - assign_new_class (occur, &stack, NULL); - else if (TREE_CODE (occur) == EUSE_NODE && !EUSE_PHIOP (occur)) - assign_new_class (occur, &stack, NULL); - } - else - { - if (TREE_CODE (occur) == EUSE_NODE && !EUSE_PHIOP (occur)) - { - tree tos = VARRAY_TOP_TREE (stack); - - if (TREE_CODE (tos) == EUSE_NODE && !EUSE_PHIOP (tos)) - { - /* If two real occurrences have the same - e-version/class, then this occurrence can be - defined by the prior occurrence (or whatever - the prior occurrence is defined by, if - anything). - Otherwise, we have to assign a new version. - lvalue occurrences always need a new version, - since they are definitions. */ - if (!EUSE_LVAL (occur) - && same_e_version_real_occ_real_occ (ei, tos, occur)) - { - - - tree newdef; - EREF_CLASS (occur) = EREF_CLASS (tos); - newdef = EUSE_DEF (tos) != NULL ? EUSE_DEF (tos) : tos; - EUSE_DEF (occur) = newdef; - } - else - assign_new_class (occur, &stack, NULL); - } - else if (TREE_CODE (tos) == EPHI_NODE) - { - /* Here we have an ephi occurrence at the top of the - stack, and the current occurrence is a real - occurrence. So determine if the real occurrence - has the same version as the result of the phi. - If so, then this real occurrence is defined by the - EPHI at the top of the stack. - If not, the EPHI isn't downsafe (because something - must change in between the ephi result and the next - occurrence), and we need a new version for the real - occurrence. - lvalues always need a new version. */ - if (!EUSE_LVAL (occur) - && same_e_version_phi_result (ei, tos, EREF_STMT (occur), - occur)) - { - EREF_CLASS (occur) = EREF_CLASS (tos); - EUSE_DEF (occur) = tos; - EREF_STMT (tos) = EREF_STMT (occur); - - VARRAY_PUSH_TREE (stack, occur); - } - else - { - EPHI_DOWNSAFE (tos) = false; - assign_new_class (occur, &stack, NULL); - } - } - } - /* EPHI occurrences always get new versions. */ - else if (TREE_CODE (occur) == EPHI_NODE) - { - assign_new_class (occur, &stack, NULL); - } - /* EPHI operands are optimistcally assumed to be whatever is - at the top of the stack at the time we hit the ephi - operand occurrence. The delayed renaming checks this - optimistic assumption for validity. */ - else if (TREE_CODE (occur) == EUSE_NODE && EUSE_PHIOP (occur)) - { - basic_block pred_bb = bb_for_stmt (occur); - edge e; - tree tos = VARRAY_TOP_TREE (stack); - for (e = pred_bb->succ; e; e = e->succ_next) - { - tree ephi = ephi_at_block (e->dest); - if (ephi != NULL_TREE) - { - int opnum = opnum_of_ephi (ephi, e); - - EPHI_ARG_DELAYED_RENAME (ephi, opnum) = true; - EPHI_ARG_DEF (ephi, opnum) = tos; - } - } - } - /* No EPHI can be downsafe past an exit node. */ - else if (TREE_CODE (occur) == EEXIT_NODE) - { - if (VARRAY_ACTIVE_SIZE (stack) > 0 - && TREE_CODE (VARRAY_TOP_TREE (stack)) == EPHI_NODE) - EPHI_DOWNSAFE (VARRAY_TOP_TREE (stack)) = false; - } - } - } - if (dump_file && (dump_flags & TDF_DETAILS)) + /* Remove the value of EXPR from the bitmap, decrement the set + length, and remove it from the actual double linked list. */ + value_remove_from_set_bitmap (set, get_value_handle (expr)); + set->length--; + prev = NULL; + for (node = set->head; + node != NULL; + prev = node, node = node->next) { - size_t i; - fprintf (dump_file, "Occurrences for expression "); - print_generic_expr (dump_file, ei->expr, dump_flags); - fprintf (dump_file, " after Rename 1\n"); - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) + if (node->expr == expr) { - print_generic_expr (dump_file, - VARRAY_TREE (ei->euses_dt_order, i), 1); - fprintf (dump_file, "\n"); + if (prev == NULL) + set->head = node->next; + else + prev->next= node->next; + + if (node == set->tail) + set->tail = prev; + pool_free (value_set_node_pool, node); + return; } } - - /* Now process the renames for EPHI's that actually have the result - valid and used. These will be the EPHI's that have the statement - set above. */ - FOR_EACH_BB (phi_bb) - { - tree ephi = ephi_at_block (phi_bb); - if (ephi != NULL && EREF_STMT (ephi) != NULL) - process_delayed_rename (ei, ephi, EREF_STMT (ephi)); - } - - /* If we didn't process the delayed rename for an ephi argument, - but thought we needed to, mark the operand as NULL. Also, if the - operand was defined by an EPHI, we can mark it not downsafe - because there can't have been a real occurrence (or else we would - have processed a rename for it). */ - FOR_EACH_BB (phi_bb) - { - tree ephi = ephi_at_block (phi_bb); - if (ephi != NULL) - { - int j; - for (j = 0; j < EPHI_NUM_ARGS (ephi); j++) - { - if (EPHI_ARG_DELAYED_RENAME (ephi, j)) - { - tree def = EPHI_ARG_DEF (ephi, j); - if (def && TREE_CODE (def) == EPHI_NODE) - EPHI_DOWNSAFE (def) = false; - EPHI_ARG_DEF (ephi, j) = NULL; - } - } - } - } - VARRAY_FREE (stack); } -/* Determine if the EPHI has an argument we could never insert - or extend the lifetime of, such as an argument occurring on - an abnormal edge. */ +/* Return true if SET contains the value VAL. */ static bool -ephi_has_unsafe_arg (tree ephi) +set_contains_value (value_set_t set, tree val) { - int i; - for (i = 0; i < EPHI_NUM_ARGS (ephi); i++) - if (EPHI_ARG_EDGE (ephi, i)->flags & EDGE_ABNORMAL) - return true; - return false; + /* This is only referring to the flag above that we set on + values referring to numerical constants, because we know that we + are dealing with one of the value handles we created. */ + if (TREE_CONSTANT (val)) + return true; + + if (set->length == 0) + return false; + + return value_exists_in_set_bitmap (set, val); } -/* Reset down safety flags for non-downsafe ephis. Uses depth first - search. */ +/* Replace the leader for the value LOOKFOR in SET with EXPR. */ static void -reset_down_safe (tree currphi, int opnum) +set_replace_value (value_set_t set, tree lookfor, tree expr) { - tree ephi; - int i; + value_set_node_t node = set->head; - if (EPHI_ARG_HAS_REAL_USE (currphi, opnum)) + /* The lookup is probably more expensive than walking the linked + list when we have only a small number of nodes. */ + if (!set_contains_value (set, lookfor)) return; - ephi = EPHI_ARG_DEF (currphi, opnum); - if (!ephi || TREE_CODE (ephi) != EPHI_NODE) - return; - if (!EPHI_DOWNSAFE (ephi)) - return; - EPHI_DOWNSAFE (ephi) = false; - for (i = 0; i < EPHI_NUM_ARGS (ephi); i++) - reset_down_safe (ephi, i); -} - -/* Compute down_safety using a depth first search. - This propagates not fully anticipated phi assignments upwards. */ - -static void -compute_down_safety (struct expr_info *ei) -{ - size_t i; - basic_block bb; - FOR_EACH_BB (bb) - { - tree ephi = ephi_at_block (bb); - if (ephi == NULL_TREE) - continue; - if (ephi_has_unsafe_arg (ephi)) - EPHI_DOWNSAFE (ephi) = false; - } - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) - { - int j; - tree ephi = VARRAY_TREE (ei->euses_dt_order, i); - if (TREE_CODE (ephi) != EPHI_NODE) - continue; - - if (!EPHI_DOWNSAFE (ephi)) - for (j = 0; j < EPHI_NUM_ARGS (ephi); j++) - reset_down_safe (ephi, j); - - } -} - -/* EPHI use node pool. We allocate ephi_use_node's out of this. */ -static alloc_pool ephi_use_pool; - -/* Add a use of DEF to it's use list. The use is at operand OPND_INDX - of USE. */ - -static void -add_ephi_use (tree def, tree use, int opnd_indx) -{ - struct ephi_use_entry *entry; - if (EPHI_USES (def) == NULL) - VARRAY_GENERIC_PTR_INIT (EPHI_USES (def), 1, "EPHI uses"); - entry = (struct ephi_use_entry *) pool_alloc (ephi_use_pool); - entry->phi = use; - entry->opnd_indx = opnd_indx; - VARRAY_PUSH_GENERIC_PTR (EPHI_USES (def), entry); -} - -/* Compute def-uses of ephis. */ -static void -compute_du_info (struct expr_info *ei) -{ - size_t i; - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) + for (node = set->head; + node; + node = node->next) { - int j; - tree ephi = VARRAY_TREE (ei->euses_dt_order, i); - if (TREE_CODE (ephi) != EPHI_NODE) - continue; - for (j = 0; j < EPHI_NUM_ARGS (ephi); j++) + if (get_value_handle (node->expr) == lookfor) { - tree def = EPHI_ARG_DEF (ephi, j); - if (def != NULL_TREE) - { - if (TREE_CODE (def) == EPHI_NODE) - add_ephi_use (def, ephi, j); -#ifdef ENABLE_CHECKING - else - if (! (TREE_CODE (def) == EUSE_NODE && !EUSE_PHIOP (def))) - abort(); -#endif - } + node->expr = expr; + return; } } } -/* STOPS marks what EPHI's/operands stop forward movement. (IE where - we can't insert past). */ +/* Return true if the set contains expression (not value) EXPR. */ -static void -compute_stops (struct expr_info *ei) +static bool +set_contains (value_set_t set, tree expr) { - size_t i; + value_set_node_t node; - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) + for (node = set->head; + node; + node = node->next) { - tree ephi = VARRAY_TREE (ei->euses_dt_order, i); - int j; - - if (TREE_CODE (ephi) != EPHI_NODE) - continue; - if (EPHI_CANT_BE_AVAIL (ephi)) - EPHI_STOPS (ephi) = true; - for (j = 0; j < EPHI_NUM_ARGS (ephi); j++) - if (EPHI_ARG_HAS_REAL_USE (ephi, j)) - EPHI_ARG_STOPS (ephi, j) = true; - } - do_ephi_df_search (ei, stops_search); -} - -/* Compute will_be_avail property, which consists of cant_be_avail and - stops properties. */ - -static void -compute_will_be_avail (struct expr_info *ei) -{ - do_ephi_df_search (ei, cant_be_avail_search); - compute_stops (ei); -} - -/* Insert the expressions into ei->euses_dt_order in preorder dt order. */ - -static void -insert_euse_in_preorder_dt_order (struct expr_info *ei) -{ - varray_type new_euses_dt_order; - size_t i; - VARRAY_GENERIC_PTR_NOGC_INIT (new_euses_dt_order, 1, "EUSEs"); - - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) - { - tree ref = VARRAY_TREE (ei->euses_dt_order, i); - if (TREE_CODE (ref) == EUSE_NODE || TREE_CODE (ref) == EPHI_NODE) - VARRAY_PUSH_TREE (new_euses_dt_order, ref); + if (operand_equal_p (node->expr, expr, 0)) + return true; } - VARRAY_FREE (ei->euses_dt_order); - ei->euses_dt_order = new_euses_dt_order; - qsort (ei->euses_dt_order->data.tree, - VARRAY_ACTIVE_SIZE (ei->euses_dt_order), - sizeof (tree), - eref_compare); - -} - -/* Determine if we can insert operand OPND_INDX of EPHI. */ - -static bool -can_insert (tree ephi, int opnd_indx) -{ - tree def; - - if (EPHI_ARG_DEF (ephi, opnd_indx) == NULL_TREE) - return true; - def = EPHI_ARG_DEF (ephi, opnd_indx); - if (!EPHI_ARG_HAS_REAL_USE (ephi, opnd_indx)) - if (TREE_CODE (def) == EPHI_NODE && !(ephi_will_be_avail (def))) - return true; return false; } -/* Find the default definition of VAR. - This is incredibly ugly, since we have to walk back through all - the definitions to find the one defined by the empty statement. */ +/* Subtract set B from set A, and return the new set. */ -static tree -get_default_def (tree var, htab_t seen) +static value_set_t +set_subtract (value_set_t a, value_set_t b, bool indexed) { - def_optype defs; - size_t i; - tree defstmt = SSA_NAME_DEF_STMT (var); - - if (IS_EMPTY_STMT (defstmt)) - return var; - *(htab_find_slot (seen, var, INSERT)) = var; - if (TREE_CODE (defstmt) == PHI_NODE) + value_set_t ret = set_new (indexed); + value_set_node_t node; + for (node = a->head; + node; + node = node->next) { - int j; - for (j = 0; j < PHI_NUM_ARGS (defstmt); j++) - if (htab_find (seen, PHI_ARG_DEF (defstmt, j)) == NULL) - { - if (TREE_CODE (PHI_ARG_DEF (defstmt, j)) == SSA_NAME) - { - tree temp = get_default_def (PHI_ARG_DEF (defstmt, j), seen); - if (temp != NULL_TREE) - return temp; - } - } + if (!set_contains (b, node->expr)) + insert_into_set (ret, node->expr); } - - - defs = STMT_DEF_OPS (defstmt); - for (i = 0; i < NUM_DEFS (defs); i++) - { - tree def = DEF_OP (defs, i); - if (SSA_NAME_VAR (def) == SSA_NAME_VAR (var)) - { - if (htab_find (seen, def) != NULL) - return NULL; - return get_default_def (def, seen); - } - } - - /* We should never get here. */ - abort (); + return ret; } -/* Hunt down the right reaching def for VAR, starting with BB. Ignore - defs in statement IGNORE, and stop if we hit CURRSTMT. */ +/* Return true if two sets are equal. */ -static tree -reaching_def (tree var, tree currstmt, basic_block bb, tree ignore) +static bool +set_equal (value_set_t a, value_set_t b) { - tree curruse = NULL_TREE; - block_stmt_iterator bsi; - basic_block dom; - tree phi; - - /* Check phis first. */ - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) - { - if (phi == currstmt) - break; - if (phi == ignore) - continue; - if (names_match_p (var, PHI_RESULT (phi))) - curruse = PHI_RESULT (phi); - } + value_set_node_t node; - /* We can't walk BB's backwards right now, so we have to walk *all* - the statements, and choose the last name we find. */ - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - tree stmt = bsi_stmt (bsi); - tree *def; - def_optype defs; - size_t i; - - if (stmt == currstmt) - break; - - get_stmt_operands (stmt); - defs = STMT_DEF_OPS (stmt); - for (i = 0; i < NUM_DEFS (defs); i++) - { - def = DEF_OP_PTR (defs, i); - if (def && *def != ignore && names_match_p (var, *def)) - { - curruse = *def; - break; - } - } - } - if (curruse != NULL_TREE) - return curruse; - dom = get_immediate_dominator (CDI_DOMINATORS, bb); - if (bb == ENTRY_BLOCK_PTR) + if (a->length != b->length) + return false; + for (node = a->head; + node; + node = node->next) { - htab_t temp; - temp = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL); - curruse = get_default_def (var, temp); - htab_delete (temp); + if (!set_contains_value (b, get_value_handle (node->expr))) + return false; } - if (!dom) - return curruse; - return reaching_def (var, currstmt, dom, ignore); + return true; } -/* Insert one ephi operand that doesn't currently exist as a use. */ - +/* Replace the value for EXPR in SET with EXPR. */ static void -insert_one_operand (struct expr_info *ei, tree ephi, int opnd_indx, - tree x, edge succ, tree **avdefsp) +value_replace_in_set (value_set_t set, tree expr) { - /* FIXME. pre_insert_on_edge should probably disappear. */ - extern void pre_insert_on_edge (edge, tree); - tree expr; - tree temp = ei->temp; - tree copy; - tree newtemp; - basic_block bb = bb_for_stmt (x); - - /* Insert definition of expr at end of BB containing x. */ - copy = TREE_OPERAND (EREF_STMT (ephi), 1); - copy = unshare_expr (copy); - expr = build (MODIFY_EXPR, TREE_TYPE (ei->expr), - temp, copy); - expr = subst_phis (ei, expr, bb, bb_for_stmt (ephi)); - newtemp = make_ssa_name (temp, expr); - TREE_OPERAND (expr, 0) = newtemp; - copy = TREE_OPERAND (expr, 1); - if (dump_file) - { - fprintf (dump_file, "In BB %d, insert save of ", bb->index); - print_generic_expr (dump_file, expr, dump_flags); - fprintf (dump_file, " to "); - print_generic_expr (dump_file, newtemp, dump_flags); - fprintf (dump_file, " after "); - print_generic_stmt (dump_file, last_stmt (bb), dump_flags); - fprintf (dump_file, " (on edge), because of EPHI"); - fprintf (dump_file, " in BB %d\n", bb_for_stmt (ephi)->index); - } - - /* Do the insertion. */ - /* ??? Previously we did bizarre searching, presumably to get - around bugs elsewhere in the infrastructure. I'm not sure - if we really should be using pre_insert_on_edge - or just bsi_insert_after at the end of BB. */ - pre_insert_on_edge (succ, expr); - - EPHI_ARG_DEF (ephi, opnd_indx) - = create_expr_ref (ei, ei->expr, EUSE_NODE, bb, 0); - EUSE_DEF (x) = EPHI_ARG_DEF (ephi, opnd_indx); - VARRAY_PUSH_TREE (ei->euses_dt_order, EPHI_ARG_DEF (ephi, opnd_indx)); - qsort (ei->euses_dt_order->data.tree, - VARRAY_ACTIVE_SIZE (ei->euses_dt_order), - sizeof (tree), - eref_compare); - EREF_TEMP (EUSE_DEF (x)) = newtemp; - EREF_RELOAD (EUSE_DEF (x)) = false; - EREF_SAVE (EUSE_DEF (x)) = false; - EUSE_INSERTED (EUSE_DEF (x)) = true; - EUSE_PHIOP (EUSE_DEF (x)) = false; - EREF_SAVE (x) = false; - EREF_RELOAD (x) = false; - EUSE_INSERTED (x) = true; - EREF_CLASS (x) = class_count++; - EREF_CLASS (EUSE_DEF (x)) = class_count++; - *avdefsp = xrealloc (*avdefsp, sizeof (tree) * (class_count + 1)); - (*avdefsp)[class_count - 2] = x; - (*avdefsp)[class_count - 1] = EUSE_DEF (x); - pre_stats.saves++; -} - -/* First step of finalization. Determine which expressions are being - saved and which are being deleted. - This is done as a simple dominator based availability calculation, - using the e-versions/redundancy classes. */ + tree val = get_value_handle (expr); -static bool -finalize_1 (struct expr_info *ei) -{ - tree x; - int nx; - bool made_a_reload = false; - size_t i; - tree *avdefs; + if (set->length == 0) + return; - avdefs = xcalloc (class_count + 1, sizeof (tree)); - - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) - { - x = VARRAY_TREE (ei->euses_dt_order, i); - nx = EREF_CLASS (x); - - if (TREE_CODE (x) == EPHI_NODE) - { - if (ephi_will_be_avail (x)) - avdefs[nx] = x; - } - else if (TREE_CODE (x) == EUSE_NODE && EUSE_LVAL (x)) - { - avdefs[nx] = x; - } - else if (TREE_CODE (x) == EUSE_NODE && !EUSE_PHIOP (x)) - { - if (avdefs[nx] == NULL - || !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (x), - bb_for_stmt (avdefs[nx]))) - { - EREF_RELOAD (x) = false; - avdefs[nx] = x; - EUSE_DEF (x) = NULL; - } - else - { - EREF_RELOAD (x) = true; - made_a_reload = true; - EUSE_DEF (x) = avdefs[nx]; -#ifdef ENABLE_CHECKING - if (EREF_CLASS (x) != EREF_CLASS (avdefs[nx])) - abort (); -#endif - } - } - else - { - edge succ; - basic_block bb = bb_for_stmt (x); - /* For each ephi in the successor blocks. */ - for (succ = bb->succ; succ; succ = succ->succ_next) - { - tree ephi = ephi_at_block (succ->dest); - if (ephi == NULL_TREE) - continue; - if (ephi_will_be_avail (ephi)) - { - int opnd_indx = opnum_of_ephi (ephi, succ); -#ifdef ENABLE_CHECKING - if (EPHI_ARG_PRED (ephi, opnd_indx) != x) - abort (); -#endif - if (can_insert (ephi, opnd_indx)) - { - insert_one_operand (ei, ephi, opnd_indx, x, succ, - &avdefs); - } - else - { - nx = EREF_CLASS (EPHI_ARG_DEF (ephi,opnd_indx)); - EPHI_ARG_DEF (ephi, opnd_indx) = avdefs[nx]; - } - } - } - } - } - free (avdefs); - return made_a_reload; + set_replace_value (set, val, expr); } -/* Mark the necessary SAVE bits on X. */ +/* Insert the value for EXPR into SET, if it doesn't exist already. */ static void -set_save (struct expr_info *ei, tree X) +value_insert_into_set (value_set_t set, tree expr) { - if (TREE_CODE (X) == EUSE_NODE && !EUSE_PHIOP (X)) - EREF_SAVE (X) = true; - else if (TREE_CODE (X) == EPHI_NODE) - { - int curr_phiop; - for (curr_phiop = 0; curr_phiop < EPHI_NUM_ARGS (X); curr_phiop++) - { - tree w = EPHI_ARG_DEF (X, curr_phiop); - if (!EPHI_ARG_PROCESSED2 (X, curr_phiop)) - { - EPHI_ARG_PROCESSED2 (X, curr_phiop) = true; - if (w) - set_save (ei, w); - } - } - } -} + tree val = get_value_handle (expr); -/* DFS Search function: Return true if PHI is can't be available. */ + /* Constant values exist everywhere. */ + if (TREE_CONSTANT (val)) + return; -static bool -cba_search_seen (tree phi) -{ - return EPHI_CANT_BE_AVAIL (phi); + if (!set_contains_value (set, val)) + insert_into_set (set, expr); } -/* DFS Search function: Mark PHI as can't be available when seen. */ -static void -cba_search_set_seen (tree phi) -{ - EPHI_CANT_BE_AVAIL (phi) = true; -} +/* Print out the value_set SET to OUTFILE. */ -/* DFS Search function: Return true if PHI should be marked can't be - available due to a NULL operand. */ - -static bool -cba_search_start_from (tree phi) +static void +print_value_set (FILE *outfile, value_set_t set, + const char *setname, int blockindex) { - if (!EPHI_DOWNSAFE (phi)) + value_set_node_t node; + fprintf (outfile, "%s[%d] := { ", setname, blockindex); + if (set) { - int i; - for (i = 0; i < EPHI_NUM_ARGS (phi); i++) - if (EPHI_ARG_DEF (phi, i) == NULL_TREE - || EPHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL) - return true; + for (node = set->head; + node; + node = node->next) + { + print_generic_expr (outfile, node->expr, 0); + if (node->next) + fprintf (outfile, ", "); + } } - return false; -} -/* DFS Search function: Return true if the used PHI is not downsafe, - unless we have a real use for the operand. */ - -static bool -cba_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED, - int opnd_indx, - tree use_phi) -{ - if (EPHI_ARG_HAS_REAL_USE (use_phi, opnd_indx) && - !(EPHI_ARG_EDGE (use_phi, opnd_indx)->flags & EDGE_ABNORMAL)) - return false; - if (!EPHI_DOWNSAFE (use_phi)) - return true; - return false; + fprintf (outfile, " }\n"); } - -/* DFS Search function: Return true if this PHI stops forward - movement. */ -static bool -stops_search_seen (tree phi) +/* Print out the expressions that have VAL to OUTFILE. */ +void +print_value_expressions (FILE *outfile, tree val) { - return EPHI_STOPS (phi); + var_ann_t va = var_ann (val); + if (va && va->expr_set) + print_value_set (outfile, va->expr_set, + IDENTIFIER_POINTER (DECL_NAME (val)), 0); } -/* DFS Search function: Mark the PHI as stopping forward movement. */ -static void -stops_search_set_seen (tree phi) +void +debug_value_expressions (tree val) { - EPHI_STOPS (phi) = true; + print_value_expressions (stderr, val); } -/* DFS Search function: Note that the used phi argument stops forward - movement. */ - -static void -stops_search_reach_from_to (tree def_phi ATTRIBUTE_UNUSED, - int opnd_indx, - tree use_phi) -{ - EPHI_ARG_STOPS (use_phi, opnd_indx) = true; -} - -/* DFS Search function: Return true if the PHI has any arguments - stopping forward movement. */ - -static bool -stops_search_start_from (tree phi) -{ - int i; - for (i = 0; i < EPHI_NUM_ARGS (phi); i++) - if (EPHI_ARG_STOPS (phi, i)) - return true; - return false; -} - -/* DFS Search function: Return true if the PHI has any arguments - stopping forward movement. */ + +void debug_value_set (value_set_t, const char *, int); -static bool -stops_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED, - int opnd_indx ATTRIBUTE_UNUSED, - tree use_phi) +void +debug_value_set (value_set_t set, const char *setname, int blockindex) { - return stops_search_start_from (use_phi); + print_value_set (stderr, set, setname, blockindex); } -/* DFS Search function: Return true if the replacing occurrence is - known. */ +/* Translate EXPR using phis in PHIBLOCK, so that it has the values of + the phis in PRED. Return NULL if we can't find a leader for each + part of the translated expression. */ -static bool -repl_search_seen (tree phi) +static tree +phi_translate (tree expr, value_set_t set, basic_block pred, + basic_block phiblock) { - return EPHI_REP_OCCUR_KNOWN (phi); -} - -/* DFS Search function: Set the identical_to field and note the - replacing occurrence is now known. */ + tree phitrans = NULL; + tree oldexpr = expr; + + if (expr == NULL) + return NULL; -static void -repl_search_set_seen (tree phi) -{ - int i; + /* Phi translations of a given expression don't change, */ + phitrans = phi_trans_lookup (expr, pred); + if (phitrans) + return phitrans; -#ifdef ENABLE_CHECKING - if (!ephi_will_be_avail (phi)) - abort (); -#endif - if (EPHI_IDENTICAL_TO (phi) == NULL_TREE) + switch (TREE_CODE_CLASS (TREE_CODE (expr))) { - for (i = 0; i < EPHI_NUM_ARGS (phi); i++) - { - tree identical_to = occ_identical_to (EPHI_ARG_DEF (phi, i)); - if (identical_to != NULL_TREE) + case '2': + { + tree oldop1 = TREE_OPERAND (expr, 0); + tree oldop2 = TREE_OPERAND (expr, 1); + tree newop1; + tree newop2; + tree newexpr; + + newop1 = phi_translate (find_leader (set, oldop1), + set, pred, phiblock); + if (newop1 == NULL) + return NULL; + newop2 = phi_translate (find_leader (set, oldop2), + set, pred, phiblock); + if (newop2 == NULL) + return NULL; + if (newop1 != oldop1 || newop2 != oldop2) + { + newexpr = pool_alloc (binary_node_pool); + memcpy (newexpr, expr, tree_size (expr)); + create_expr_ann (newexpr); + TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1); + TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2); + lookup_or_add (value_table, newexpr); + expr = newexpr; + phi_trans_add (oldexpr, newexpr, pred); + } + } + break; + case '1': + { + tree oldop1 = TREE_OPERAND (expr, 0); + tree newop1; + tree newexpr; + + newop1 = phi_translate (find_leader (set, oldop1), + set, pred, phiblock); + if (newop1 == NULL) + return NULL; + if (newop1 != oldop1) + { + newexpr = pool_alloc (unary_node_pool); + memcpy (newexpr, expr, tree_size (expr)); + create_expr_ann (newexpr); + TREE_OPERAND (newexpr, 0) = get_value_handle (newop1); + lookup_or_add (value_table, newexpr); + expr = newexpr; + phi_trans_add (oldexpr, newexpr, pred); + } + } + break; + case 'd': + abort (); + case 'x': + { + tree phi = NULL; + int i; + if (TREE_CODE (expr) != SSA_NAME) + abort (); + if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE) + phi = SSA_NAME_DEF_STMT (expr); + else + return expr; + + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + if (PHI_ARG_EDGE (phi, i)->src == pred) { - if (EPHI_IDENTICAL_TO (phi) == NULL) - EPHI_IDENTICAL_TO (phi) = identical_to; - if (EPHI_ARG_INJURED (phi, i)) - EPHI_IDENT_INJURED (phi) = true; + tree val; + if (is_undefined_value (PHI_ARG_DEF (phi, i))) + return NULL; + val = lookup_or_add (value_table, PHI_ARG_DEF (phi, i)); + return PHI_ARG_DEF (phi, i); } - } + } + break; } - EPHI_REP_OCCUR_KNOWN (phi) = true; -} - -/* Helper function. Return true if any argument in the PHI is - injured. */ - -static inline bool -any_operand_injured (tree ephi) -{ - int i; - for (i = 0; i < EPHI_NUM_ARGS (ephi); i++) - if (EPHI_ARG_INJURED (ephi, i)) - return true; - return false; - + return expr; } -/* DFS Search function: Note the identity of the used phi operand is - the same as it's defining phi operand, if that phi will be - available, and it's known. */ - static void -repl_search_reach_from_to (tree def_phi, int opnd_indx ATTRIBUTE_UNUSED, - tree use_phi) +phi_translate_set (value_set_t dest, value_set_t set, basic_block pred, + basic_block phiblock) { - if (ephi_will_be_avail (use_phi) - && EPHI_IDENTITY (use_phi) - && EPHI_IDENTICAL_TO (use_phi) == NULL_TREE) + value_set_node_t node; + for (node = set->head; + node; + node = node->next) { - EPHI_IDENTICAL_TO (use_phi) = EPHI_IDENTICAL_TO (def_phi); + tree translated; + translated = phi_translate (node->expr, set, pred, phiblock); + phi_trans_add (node->expr, translated, pred); - if (EPHI_IDENT_INJURED (def_phi) - || any_operand_injured (use_phi)) - EPHI_IDENT_INJURED (use_phi) = true; - } + if (translated != NULL) + value_insert_into_set (dest, translated); + } } -/* DFS Search function: Return true if the PHI will be available, - it's an identity PHI, and it's arguments are identical to - something. */ - -static bool -repl_search_start_from (tree phi) -{ - if (ephi_will_be_avail (phi) && EPHI_IDENTITY (phi)) - { - int i; - for (i = 0; i < EPHI_NUM_ARGS (phi); i++) - if (occ_identical_to (EPHI_ARG_DEF (phi, i)) != NULL_TREE) - return true; - } - return false; -} - -/* DFS Search function: Return true if the using PHI is will be available, - and identity. */ - -static bool -repl_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED, - int opnd_indx ATTRIBUTE_UNUSED, - tree use_phi) -{ - return ephi_will_be_avail (use_phi) && EPHI_IDENTITY (use_phi); -} - -/* Mark all will-be-avail ephi's in the dominance frontier of BB as - required. */ - -static void -require_phi (struct expr_info *ei, basic_block bb) -{ - size_t i; - EXECUTE_IF_SET_IN_BITMAP (pre_dfs[bb->index], 0, i, - { - tree ephi; - ephi = ephi_at_block (BASIC_BLOCK (i)); - if (ephi != NULL_TREE - && ephi_will_be_avail (ephi) - && EPHI_IDENTITY (ephi)) - { - EPHI_IDENTITY (ephi) = false; - require_phi (ei, BASIC_BLOCK (i)); - } - }); -} - -/* Return the occurrence this occurrence is identical to, if one exists. */ +/* Find the leader for a value (IE the name representing that + value) in a given set, and return it. Return NULL if no leader is + found. */ static tree -occ_identical_to (tree t) -{ - if (TREE_CODE (t) == EUSE_NODE && !EUSE_PHIOP (t)) - return t; - else if (TREE_CODE (t) == EUSE_NODE && EUSE_PHIOP (t)) - return t; - else if (TREE_CODE (t) == EPHI_NODE) - { - if (EPHI_IDENTITY (t) && EPHI_REP_OCCUR_KNOWN (t)) - return EPHI_IDENTICAL_TO (t); - else if (!EPHI_IDENTITY (t)) - return t; - } - return NULL_TREE; -} - -/* Return true if NODE was or is going to be saved. */ -static bool -really_available_def (tree node) -{ - if (TREE_CODE (node) == EUSE_NODE - && EUSE_PHIOP (node) - && EUSE_INSERTED (node)) - return true; - if (TREE_CODE (node) == EUSE_NODE - && EUSE_DEF (node) == NULL_TREE) - return true; - return false; -} - - -/* Second part of the finalize step. Performs save bit setting, and - ESSA minimization. */ - -static void -finalize_2 (struct expr_info *ei) +find_leader (value_set_t set, tree val) { - size_t i; + value_set_node_t node; - insert_euse_in_preorder_dt_order (ei); - /* Note which uses need to be saved to a temporary. */ - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) - { - tree ref = VARRAY_TREE (ei->euses_dt_order, i); - if (TREE_CODE (ref) == EUSE_NODE - && !EUSE_PHIOP (ref) - && EREF_RELOAD (ref)) - { - set_save (ei, EUSE_DEF (ref)); - } - } + if (val == NULL) + return NULL; - /* ESSA Minimization. Determines which phis are identical to other - phis, and not strictly necessary. */ + if (TREE_CONSTANT (val)) + return TREE_CHAIN (val); - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) - { - tree ephi = VARRAY_TREE (ei->euses_dt_order, i); - if (TREE_CODE (ephi) != EPHI_NODE) - continue; - EPHI_IDENTITY (ephi) = true; - EPHI_IDENTICAL_TO (ephi) = NULL; - } + if (set->length == 0) + return NULL; - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) + if (value_exists_in_set_bitmap (set, val)) { - tree ephi = VARRAY_TREE (ei->euses_dt_order, i); - if (!ephi || TREE_CODE (ephi) != EPHI_NODE) - continue; - if (ephi_will_be_avail (ephi)) + for (node = set->head; + node; + node = node->next) { - int k; - for (k = 0; k < EPHI_NUM_ARGS (ephi); k++) - { - if (EPHI_ARG_INJURED (ephi, k)) - require_phi (ei, EPHI_ARG_EDGE (ephi, k)->src); - else if (EPHI_ARG_DEF (ephi, k) - && TREE_CODE (EPHI_ARG_DEF (ephi, k)) == EUSE_NODE - && really_available_def (EPHI_ARG_DEF (ephi, k))) - require_phi (ei, bb_for_stmt (EPHI_ARG_DEF (ephi, k))); - } + if (get_value_handle (node->expr) == val) + return node->expr; } } - do_ephi_df_search (ei, replacing_search); + return NULL; } -/* Perform a DFS on EPHI using the functions in SEARCH. */ +/* Determine if the expression EXPR is valid in SET. This means that + we have a leader for each part of the expression (if it consists of + values), or the expression is an SSA_NAME. -static void -do_ephi_df_search_1 (struct ephi_df_search search, tree ephi) + NB: We never should run into a case where we have SSA_NAME + + SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on, + the ANTIC sets, will only ever have SSA_NAME's or binary value + expression (IE VALUE1 + VALUE2) */ + +static bool +valid_in_set (value_set_t set, tree expr) { - varray_type uses; - size_t i; - search.set_seen (ephi); - - uses = EPHI_USES (ephi); - if (!uses) - return; - for (i = 0; i < VARRAY_ACTIVE_SIZE (uses); i++) + switch (TREE_CODE_CLASS (TREE_CODE (expr))) { - struct ephi_use_entry *use = VARRAY_GENERIC_PTR (uses, i); - if (search.reach_from_to) - search.reach_from_to (ephi, use->opnd_indx, use->phi); - if (!search.seen (use->phi) && - search.continue_from_to (ephi, use->opnd_indx, use->phi)) - { - do_ephi_df_search_1 (search, use->phi); - } + case '2': + { + tree op1 = TREE_OPERAND (expr, 0); + tree op2 = TREE_OPERAND (expr, 1); + return set_contains_value (set, op1) && set_contains_value (set, op2); + } + break; + case '1': + { + tree op1 = TREE_OPERAND (expr, 0); + return set_contains_value (set, op1); + } + break; + case 'x': + { + if (TREE_CODE (expr) == SSA_NAME) + return true; + abort (); + } + case 'c': + abort (); } + return false; } -/* Perform a DFS on the EPHI's, using the functions in SEARCH. */ +/* Clean the set of expressions that are no longer valid in the + specified set. This means expressions that are made up of values + we have no leaders for in the current set, etc. */ static void -do_ephi_df_search (struct expr_info *ei, struct ephi_df_search search) +clean (value_set_t set) { - size_t i; - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) + value_set_node_t node; + value_set_node_t next; + node = set->head; + while (node) { - tree ephi = VARRAY_TREE (ei->euses_dt_order, i); - if (!ephi || TREE_CODE (ephi) != EPHI_NODE) - continue; - if (!search.seen (ephi) - && search.start_from (ephi)) - do_ephi_df_search_1 (search, ephi); + next = node->next; + if (!valid_in_set (set, node->expr)) + set_remove (set, node->expr); + node = next; } } -#if 0 -/* Calculate the increment necessary due to EXPR for the temporary. */ -static tree -calculate_increment (struct expr_info *ei, tree expr) -{ - tree incr; - - /*XXX: Currently assume it's like a = a + 5, thus, this will give us the 5. - */ - incr = TREE_OPERAND (TREE_OPERAND (expr, 1), 1); - if (TREE_CODE (incr) != INTEGER_CST) - abort(); - if (TREE_CODE (ei->expr) == MULT_EXPR) - incr = fold (build (MULT_EXPR, TREE_TYPE (ei->expr), - incr, TREE_OPERAND (ei->expr, 1))); -#if DEBUGGING_STRRED - if (dump_file) - { - fprintf (dump_file, "Increment calculated to be: "); - print_generic_expr (dump_file, incr, 0); - fprintf (dump_file, "\n"); - } -#endif - return incr; -} -#endif +/* Compute the ANTIC set for BLOCK. +ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if +succs(BLOCK) > 1 +ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if +succs(BLOCK) == 1 -/* Perform an insertion of EXPR before/after USE, depending on the - value of BEFORE. */ +ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - +TMP_GEN[BLOCK]) -static tree -do_proper_save (tree use, tree expr, int before) -{ - basic_block bb = bb_for_stmt (use); - block_stmt_iterator bsi; +Iterate until fixpointed. - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - if (bsi_stmt (bsi) == use) - { - if (before) - bsi_insert_before (&bsi, expr, BSI_SAME_STMT); - else - bsi_insert_after (&bsi, expr, BSI_SAME_STMT); - return use; - } - } - abort (); -} +XXX: It would be nice to either write a set_clear, and use it for +antic_out, or to mark the antic_out set as deleted at the end +of this routine, so that the pool can hand the same memory back out +again for the next antic_out. */ -/* Get the temporary for ESSA node USE. - Takes into account minimized ESSA. */ -static tree -get_temp (tree use) + +static bool +compute_antic_aux (basic_block block) { - tree newtemp; - if (TREE_CODE (use) == EPHI_NODE && EPHI_IDENTITY (use)) + basic_block son; + edge e; + bool changed = false; + value_set_t S, old, ANTIC_OUT; + value_set_node_t node; + + ANTIC_OUT = S = NULL; + /* If any edges from predecessors are abnormal, antic_in is empty, so + punt. Remember that the block has an incoming abnormal edge by + setting the BB_VISITED flag. */ + if (! (block->flags & BB_VISITED)) { - tree newuse = use; - while (TREE_CODE (newuse) == EPHI_NODE - && EPHI_IDENTITY (newuse)) - { -#ifdef ENABLE_CHECKING - if (!EPHI_IDENTICAL_TO (newuse)) - abort (); -#endif - newuse = EPHI_IDENTICAL_TO (newuse); - if (TREE_CODE (newuse) != EPHI_NODE) - break; - } - if (TREE_CODE (EREF_TEMP (newuse)) == PHI_NODE) - newtemp = PHI_RESULT (EREF_TEMP (newuse)); - else - newtemp = EREF_TEMP (newuse); + for (e = block->pred; e; e = e->pred_next) + if (e->flags & EDGE_ABNORMAL) + { + block->flags |= BB_VISITED; + break; + } } - else + if (block->flags & BB_VISITED) { - if (TREE_CODE (EREF_TEMP (use)) == PHI_NODE) - newtemp = PHI_RESULT (EREF_TEMP (use)); - else - newtemp = EREF_TEMP (use); + S = NULL; + goto visit_sons; } - return newtemp; -} - -/* Return the side of the statement that contains an SSA name. */ - -static tree -pick_ssa_name (tree stmt) -{ - if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME) - return TREE_OPERAND (stmt, 0); - else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME) - return TREE_OPERAND (stmt, 1); - else - abort (); -} + -/* Code motion step of SSAPRE. Take the save bits, and reload bits, - and perform the saves and reloads. Also insert new phis where - necessary. */ + old = set_new (false); + set_copy (old, ANTIC_IN (block)); + ANTIC_OUT = set_new (true); -static void -code_motion (struct expr_info *ei) -{ - tree use; - tree newtemp; - size_t euse_iter; - tree temp = ei->temp; - basic_block bb; + /* If the block has no successors, ANTIC_OUT is empty, because it is + the exit block. */ + if (block->succ == NULL); - /* First, add the phi node temporaries so the reaching defs are - always right. */ - for (euse_iter = 0; - euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); - euse_iter++) + /* If we have one successor, we could have some phi nodes to + translate through. */ + else if (block->succ->succ_next == NULL) { - - use = VARRAY_TREE (ei->euses_dt_order, euse_iter); - if (TREE_CODE (use) != EPHI_NODE) - continue; - if (ephi_will_be_avail (use) && !EPHI_IDENTITY (use)) - { - bb = bb_for_stmt (use); - /* Add the new PHI node to the list of PHI nodes for block BB. */ - bb_ann (bb)->phi_nodes = chainon (phi_nodes (bb), EREF_TEMP (use)); - } - else if (EPHI_IDENTITY (use)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Pointless EPHI in block %d\n", - bb_for_stmt (use)->index); - } - } + phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest), + block, block->succ->dest); } - /* Now do the actual saves and reloads, plus repairs. */ - for (euse_iter = 0; - euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); - euse_iter++) + /* If we have multiple successors, we take the intersection of all of + them. */ + else { - use = VARRAY_TREE (ei->euses_dt_order, euse_iter); -#ifdef ENABLE_CHECKING - if (TREE_CODE (use) == EUSE_NODE && EUSE_PHIOP (use) - && (EREF_RELOAD (use) || EREF_SAVE (use))) - abort (); -#endif - if (EREF_SAVE (use) && !EUSE_INSERTED (use)) + varray_type worklist; + edge e; + size_t i; + basic_block bprime, first; + + VARRAY_BB_INIT (worklist, 1, "succ"); + e = block->succ; + while (e) { - tree newexpr; - tree use_stmt; - tree copy; - basic_block usebb = bb_for_stmt (use); - use_stmt = EREF_STMT (use); - - copy = TREE_OPERAND (use_stmt, 1); - copy = unshare_expr (copy); - newexpr = build (MODIFY_EXPR, TREE_TYPE (temp), temp, copy); - newtemp = make_ssa_name (temp, newexpr); - EREF_TEMP (use) = newtemp; - TREE_OPERAND (newexpr, 0) = newtemp; - TREE_OPERAND (use_stmt, 1) = newtemp; - - if (dump_file) - { - fprintf (dump_file, "In BB %d, insert save of ", - usebb->index); - print_generic_expr (dump_file, copy, dump_flags); - fprintf (dump_file, " to "); - print_generic_expr (dump_file, newtemp, dump_flags); - fprintf (dump_file, " before statement "); - print_generic_expr (dump_file, use_stmt, dump_flags); - fprintf (dump_file, "\n"); - if (EXPR_HAS_LOCATION (use_stmt)) - fprintf (dump_file, " on line %d\n", - EXPR_LINENO (use_stmt)); - } - modify_stmt (newexpr); - modify_stmt (use_stmt); - set_bb_for_stmt (newexpr, usebb); - EREF_STMT (use) = do_proper_save (use_stmt, newexpr, true); - pre_stats.saves++; + VARRAY_PUSH_BB (worklist, e->dest); + e = e->succ_next; } - else if (EREF_RELOAD (use)) - { - tree use_stmt; - tree newtemp; + first = VARRAY_BB (worklist, 0); + set_copy (ANTIC_OUT, ANTIC_IN (first)); - use_stmt = EREF_STMT (use); - bb = bb_for_stmt (use_stmt); - - newtemp = get_temp (EUSE_DEF (use)); - if (!newtemp) - abort (); - if (dump_file) - { - fprintf (dump_file, "In BB %d, insert reload of ", - bb->index); - print_generic_expr (dump_file, - TREE_OPERAND (use_stmt, 1), 0); - fprintf (dump_file, " from "); - print_generic_expr (dump_file, newtemp, dump_flags); - fprintf (dump_file, " in statement "); - print_generic_stmt (dump_file, use_stmt, dump_flags); - fprintf (dump_file, "\n"); - if (EXPR_HAS_LOCATION (use_stmt)) - fprintf (dump_file, " on line %d\n", - EXPR_LINENO (use_stmt)); - } - TREE_OPERAND (use_stmt, 1) = newtemp; - EREF_TEMP (use) = newtemp; - modify_stmt (use_stmt); - pre_stats.reloads++; - } - } - - /* Now do the phi nodes. */ - for (euse_iter = 0; - euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); - euse_iter++) - { - use = VARRAY_TREE (ei->euses_dt_order, euse_iter); - if (TREE_CODE (use) == EPHI_NODE - && ephi_will_be_avail (use) - && !EPHI_IDENTITY (use)) + for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++) { - int i; - tree argdef; - bb = bb_for_stmt (use); - if (dump_file) + bprime = VARRAY_BB (worklist, i); + node = ANTIC_OUT->head; + while (node) { - fprintf (dump_file, - "In BB %d, insert PHI to replace EPHI\n", bb->index); + tree val; + value_set_node_t next = node->next; + val = get_value_handle (node->expr); + if (!set_contains_value (ANTIC_IN (bprime), val)) + set_remove (ANTIC_OUT, node->expr); + node = next; } - newtemp = EREF_TEMP (use); - for (i = 0; i < EPHI_NUM_ARGS (use); i++) - { - tree rdef; - argdef = EPHI_ARG_DEF (use, i); - if (argdef == use) - rdef = get_temp (use); - else if (EREF_RELOAD (argdef) || EREF_SAVE (argdef)) - rdef = get_temp (argdef); - else if (TREE_CODE (argdef) == EPHI_NODE) - rdef = get_temp (argdef); - else if (argdef - && EPHI_ARG_HAS_REAL_USE (use, i) - && EREF_STMT (argdef) - && !EPHI_ARG_INJURED (use, i)) - rdef = pick_ssa_name (EREF_STMT (argdef)); - else - abort (); - - if (!rdef) - abort(); - add_phi_arg (&newtemp, rdef, EPHI_ARG_EDGE (use, i)); - } - - /* Associate BB to the PHI node. */ - set_bb_for_stmt (EREF_TEMP (use), bb); - pre_stats.newphis++; - } + VARRAY_CLEAR (worklist); } -} -/* Compute the iterated dominance frontier of a statement. */ + /* Generate ANTIC_OUT - TMP_GEN */ + S = set_subtract (ANTIC_OUT, TMP_GEN (block), false); -static bitmap -compute_idfs (bitmap * dfs, tree stmt) -{ - fibheap_t worklist; - sbitmap inworklist, done; - bitmap idf; - size_t i; - basic_block block; + /* Start ANTIC_IN with EXP_GEN - TMP_GEN */ + ANTIC_IN (block) = set_subtract (EXP_GEN (block),TMP_GEN (block), true); - block = bb_for_stmt (stmt); - if (idfs_cache[block->index] != NULL) - return idfs_cache[block->index]; - - inworklist = sbitmap_alloc (last_basic_block); - done = sbitmap_alloc (last_basic_block); - worklist = fibheap_new (); - sbitmap_zero (inworklist); - sbitmap_zero (done); - - idf = BITMAP_XMALLOC (); - bitmap_zero (idf); - - block = bb_for_stmt (stmt); - fibheap_insert (worklist, block->index, (void *)(size_t)block->index); - SET_BIT (inworklist, block->index); - - while (!fibheap_empty (worklist)) + /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U + EXP_GEN - TMP_GEN */ + for (node = S->head; + node; + node = node->next) { - int a = (size_t) fibheap_extract_min (worklist); - if (TEST_BIT (done, a)) - continue; - SET_BIT (done, a); - if (idfs_cache[a]) - { - bitmap_a_or_b (idf, idf, idfs_cache[a]); - EXECUTE_IF_SET_IN_BITMAP (idfs_cache[a], 0, i, - { - SET_BIT (inworklist, i); - SET_BIT (done, i); - }); - } - else - { - bitmap_a_or_b (idf, idf, dfs[a]); - EXECUTE_IF_SET_IN_BITMAP (dfs[a], 0, i, - { - if (!TEST_BIT (inworklist, i)) - { - SET_BIT (inworklist, i); - fibheap_insert (worklist, i, (void *)i); - } - }); - } - + value_insert_into_set (ANTIC_IN (block), node->expr); } - fibheap_delete (worklist); - sbitmap_free (inworklist); - sbitmap_free (done); - idfs_cache[block->index] = idf; - return idf; - -} - -/* Return true if EXPR is a strength reduction candidate. */ -static bool -is_strred_cand (const tree expr ATTRIBUTE_UNUSED) -{ -#if 0 - if (TREE_CODE (TREE_OPERAND (expr, 1)) != MULT_EXPR - && TREE_CODE (TREE_OPERAND (expr, 1)) != MINUS_EXPR - && TREE_CODE (TREE_OPERAND (expr, 1)) != NEGATE_EXPR - && TREE_CODE (TREE_OPERAND (expr, 1)) != PLUS_EXPR) - return false; - return true; -#endif - return false; -} + clean (ANTIC_IN (block)); + if (!set_equal (old, ANTIC_IN (block))) + changed = true; + visit_sons: + if (dump_file && (dump_flags & TDF_DETAILS)) + { + if (ANTIC_OUT) + print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index); + print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index); + if (S) + print_value_set (dump_file, S, "S", block->index); -/* Determine if two expressions are lexically equivalent. */ + } -static inline bool -expr_lexically_eq (const tree v1, const tree v2) -{ - if (TREE_CODE_CLASS (TREE_CODE (v1)) != TREE_CODE_CLASS (TREE_CODE (v2))) - return false; - if (TREE_CODE (v1) != TREE_CODE (v2)) - return false; - switch (TREE_CODE_CLASS (TREE_CODE (v1))) + for (son = first_dom_son (CDI_POST_DOMINATORS, block); + son; + son = next_dom_son (CDI_POST_DOMINATORS, son)) { - case 'r': - case '1': - return names_match_p (TREE_OPERAND (v1, 0), TREE_OPERAND (v2, 0)); - case 'x': - case 'd': - return names_match_p (v1, v2); - case '2': - { - bool match; - match = names_match_p (TREE_OPERAND (v1, 0), TREE_OPERAND (v2, 0)); - if (!match) - return false; - match = names_match_p (TREE_OPERAND (v1, 1), TREE_OPERAND (v2, 1)); - if (!match) - return false; - return true; - } - default: - return false; + changed |= compute_antic_aux (son); } - + return changed; } -/* Free an expression info structure. */ +/* Compute ANTIC sets. */ static void -free_expr_info (struct expr_info *v1) +compute_antic (void) { - struct expr_info *e1 = (struct expr_info *)v1; - VARRAY_FREE (e1->occurs); - VARRAY_FREE (e1->kills); - VARRAY_FREE (e1->lefts); - VARRAY_FREE (e1->reals); - VARRAY_FREE (e1->euses_dt_order); + bool changed = true; + basic_block bb; + int num_iterations = 0; + FOR_ALL_BB (bb) + { + ANTIC_IN (bb) = set_new (true); + bb->flags &= ~BB_VISITED; + } + + while (changed) + { + num_iterations++; + changed = false; + changed = compute_antic_aux (EXIT_BLOCK_PTR); + } + if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations); } -/* Process left occurrences and kills due to EXPR. - A left occurrence occurs wherever a variable in an expression we - are PRE'ing is stored to directly in a def, or indirectly because - of a VDEF of an expression that we VUSE. */ +/* Perform insertion of partially redundant values. + For BLOCK, do the following: + 1. Propagate the NEW_SETS of the dominator into the current block. + If the block has multiple predecessors, + 2a. Iterate over the ANTIC expressions for the block to see if + any of them are partially redundant. + 2b. If so, insert them into the necessary predecessors to make + the expression fully redundant. + 2c. Insert a new PHI merging the values of the predecessors. + 2d. Insert the new PHI, and the new expressions, into the + NEW_SETS set. + 3. Recursively call ourselves on the dominator children of BLOCK. -static void -process_left_occs_and_kills (varray_type bexprs, tree expr) +*/ +static bool +insert_aux (basic_block block) { - size_t i, j, k; - - v_may_def_optype v_may_defs; - v_must_def_optype v_must_defs; - vuse_optype vuses; - def_optype defs; - defs = STMT_DEF_OPS (expr); - v_may_defs = STMT_V_MAY_DEF_OPS (expr); - v_must_defs = STMT_V_MUST_DEF_OPS (expr); - if (NUM_DEFS (defs) == 0 - && NUM_V_MAY_DEFS (v_may_defs) == 0 - && NUM_V_MUST_DEFS (v_must_defs) == 0) - return; + basic_block son; + bool new_stuff = false; - for (j = 0; j < VARRAY_ACTIVE_SIZE (bexprs); j++) + if (block) { - struct expr_info *ei = VARRAY_GENERIC_PTR (bexprs, j); - tree vuse_name; - tree random_occur; - stmt_ann_t ann; - - if (!ei->loadpre_cand) - continue; - - /* If we define the variable itself (IE a in *a, or a in a), - it's a left occurrence. */ - for (i = 0; i < NUM_DEFS (defs); i++) + value_set_node_t e; + basic_block dom; + dom = get_immediate_dominator (CDI_DOMINATORS, block); + if (dom) { - if (names_match_p (DEF_OP (defs, i), ei->expr)) + e = NEW_SETS (dom)->head; + while (e) { - if (TREE_CODE (expr) == ASM_EXPR) - { - ei->loadpre_cand = false; - continue; - } - VARRAY_PUSH_TREE (ei->lefts, expr); - VARRAY_PUSH_TREE (ei->occurs, NULL); - VARRAY_PUSH_TREE (ei->kills, NULL); + insert_into_set (NEW_SETS (block), e->expr); + value_replace_in_set (AVAIL_OUT (block), e->expr); + e = e->next; } - } - - /* If we virtually define the variable itself, - it's a left occurrence. */ - for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++) - { - if (names_match_p (V_MUST_DEF_OP (v_must_defs, i), ei->expr)) + if (block->pred->pred_next) { - if (TREE_CODE (expr) == ASM_EXPR) + value_set_node_t node; + for (node = ANTIC_IN (block)->head; + node; + node = node->next) { - ei->loadpre_cand = false; - continue; - } - VARRAY_PUSH_TREE (ei->lefts, expr); - VARRAY_PUSH_TREE (ei->occurs, NULL); - VARRAY_PUSH_TREE (ei->kills, NULL); - } - } - - /* If we V_MAY_DEF the VUSE of the expression, it's also a left - occurrence. */ - random_occur = VARRAY_TREE (ei->occurs, 0); - ann = stmt_ann (random_occur); - vuses = VUSE_OPS (ann); - if (NUM_V_MAY_DEFS (v_may_defs) != 0) - { - for (k = 0; k < NUM_VUSES (vuses); k++) - { - vuse_name = VUSE_OP (vuses, k); - for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) - { - if (names_match_p (V_MAY_DEF_OP (v_may_defs, i), vuse_name)) + if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2' + || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1') { - VARRAY_PUSH_TREE (ei->lefts, expr); - VARRAY_PUSH_TREE (ei->occurs, NULL); - VARRAY_PUSH_TREE (ei->kills, NULL); + tree *avail; + tree val; + bool by_some = false; + bool all_same = true; + tree first_s = NULL; + edge pred; + basic_block bprime; + tree eprime; + val = get_value_handle (node->expr); + if (set_contains_value (PHI_GEN (block), val)) + continue; + if (set_contains_value (AVAIL_OUT (dom), val)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Found fully redundant value\n"); + continue; + } + + + avail = xcalloc (last_basic_block, sizeof (tree)); + for (pred = block->pred; + pred; + pred = pred->pred_next) + { + tree vprime; + tree edoubleprime; + bprime = pred->src; + eprime = phi_translate (node->expr, + ANTIC_IN (block), + bprime, block); + if (eprime == NULL) + continue; + + vprime = get_value_handle (eprime); + if (!vprime) + abort (); + edoubleprime = find_leader (AVAIL_OUT (bprime), + vprime); + if (edoubleprime == NULL) + { + avail[bprime->index] = eprime; + all_same = false; + } + else + { + avail[bprime->index] = edoubleprime; + by_some = true; + if (first_s == NULL) + first_s = edoubleprime; + else if (first_s != edoubleprime) + all_same = false; + if (first_s != edoubleprime + && operand_equal_p (first_s, edoubleprime, 0)) + abort (); + } + } + + if (!all_same && by_some) + { + tree temp; + tree type = TREE_TYPE (avail[block->pred->src->index]); + tree v; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Found partial redundancy for expression "); + print_generic_expr (dump_file, node->expr, 0); + fprintf (dump_file, "\n"); + } + + /* Make the necessary insertions. */ + for (pred = block->pred; + pred; + pred = pred->pred_next) + { + bprime = pred->src; + eprime = avail[bprime->index]; + if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2') + { + tree s1, s2; + tree newexpr; + s1 = find_leader (AVAIL_OUT (bprime), + TREE_OPERAND (eprime, 0)); + /* Depending on the order we process + DOM branches in, the value may + not have propagated to all the + dom children yet during this + iteration. In this case, the + value will always be in the + NEW_SETS for *our* dominator */ + if (!s1) + s1 = find_leader (NEW_SETS (dom), + TREE_OPERAND (eprime, 0)); + if (!s1) + abort (); + + s2 = find_leader (AVAIL_OUT (bprime), + TREE_OPERAND (eprime, 1)); + if (!s2) + s2 = find_leader (NEW_SETS (dom), + TREE_OPERAND (eprime, 1)); + if (!s2) + abort (); + + temp = create_tmp_var (TREE_TYPE (eprime), + "pretmp"); + add_referenced_tmp_var (temp); + newexpr = build (TREE_CODE (eprime), + TREE_TYPE (eprime), + s1, s2); + newexpr = build (MODIFY_EXPR, + TREE_TYPE (eprime), + temp, newexpr); + temp = make_ssa_name (temp, newexpr); + TREE_OPERAND (newexpr, 0) = temp; + bsi_insert_on_edge (pred, newexpr); + bsi_commit_edge_inserts (NULL); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Inserted "); + print_generic_expr (dump_file, newexpr, 0); + fprintf (dump_file, " in predecessor %d\n", pred->src->index); + } + pre_stats.insertions++; + v = lookup_or_add (value_table, eprime); + add (value_table, temp, v); + insert_into_set (NEW_SETS (bprime), temp); + value_insert_into_set (AVAIL_OUT (bprime), + temp); + avail[bprime->index] = temp; + } + else if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '1') + { + tree s1; + tree newexpr; + s1 = find_leader (AVAIL_OUT (bprime), + TREE_OPERAND (eprime, 0)); + /* Depending on the order we process + DOM branches in, the value may not have + propagated to all the dom + children yet in the current + iteration, but it will be in + NEW_SETS if it is not yet + propagated. */ + + if (!s1) + s1 = find_leader (NEW_SETS (dom), + TREE_OPERAND (eprime, 0)); + if (!s1) + abort (); + + temp = create_tmp_var (TREE_TYPE (eprime), + "pretmp"); + add_referenced_tmp_var (temp); + newexpr = build (TREE_CODE (eprime), + TREE_TYPE (eprime), + s1); + newexpr = build (MODIFY_EXPR, + TREE_TYPE (eprime), + temp, newexpr); + temp = make_ssa_name (temp, newexpr); + TREE_OPERAND (newexpr, 0) = temp; + bsi_insert_on_edge (pred, newexpr); + bsi_commit_edge_inserts (NULL); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Inserted "); + print_generic_expr (dump_file, newexpr, 0); + fprintf (dump_file, " in predecessor %d\n", pred->src->index); + } + pre_stats.insertions++; + v = lookup_or_add (value_table, eprime); + add (value_table, temp, v); + insert_into_set (NEW_SETS (bprime), temp); + value_insert_into_set (AVAIL_OUT (bprime), + temp); + avail[bprime->index] = temp; + } + } + /* Now build a phi for the new variable. */ + temp = create_tmp_var (type, "prephitmp"); + add_referenced_tmp_var (temp); + temp = create_phi_node (temp, block); + add (value_table, PHI_RESULT (temp), val); + +#if 0 + if (!set_contains_value (AVAIL_OUT (block), val)) + insert_into_set (AVAIL_OUT (block), + PHI_RESULT (temp)); + else +#endif + value_replace_in_set (AVAIL_OUT (block), + PHI_RESULT (temp)); + for (pred = block->pred; + pred; + pred = pred->pred_next) + { + add_phi_arg (&temp, avail[pred->src->index], + pred); + } + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Created phi "); + print_generic_expr (dump_file, temp, 0); + fprintf (dump_file, " in block %d\n", block->index); + } + pre_stats.phis++; + new_stuff = true; + insert_into_set (NEW_SETS (block), + PHI_RESULT (temp)); + insert_into_set (PHI_GEN (block), + PHI_RESULT (temp)); + } + + free (avail); } } } } } + for (son = first_dom_son (CDI_DOMINATORS, block); + son; + son = next_dom_son (CDI_DOMINATORS, son)) + { + new_stuff |= insert_aux (son); + } + + return new_stuff; } -/* Perform SSAPRE on an expression. */ +/* Perform insertion of partially redundant values. */ -static int -pre_expression (struct expr_info *slot, void *data, bitmap vars_to_rename) +static void +insert (void) { - struct expr_info *ei = (struct expr_info *) slot; + bool new_stuff = true; basic_block bb; + int num_iterations = 0; - class_count = 0; - eref_id_counter = 0; - - /* If we don't have two occurrences along any dominated path, and - it's not load PRE, this is a waste of time. */ - - if (VARRAY_ACTIVE_SIZE (ei->reals) < 2) - return 1; - - memset (&pre_stats, 0, sizeof (struct pre_stats_d)); + FOR_ALL_BB (bb) + NEW_SETS (bb) = set_new (true); - ei->temp = create_tmp_var (TREE_TYPE (ei->expr), "pretmp"); - add_referenced_tmp_var (ei->temp); - - bitmap_clear (created_phi_preds); - ephi_pindex_htab = htab_create (500, ephi_pindex_hash, ephi_pindex_eq, free); - phi_pred_cache = xcalloc (last_basic_block, sizeof (tree)); - n_phi_preds = last_basic_block; - - if (!expr_phi_insertion ((bitmap *)data, ei)) - goto cleanup; - rename_1 (ei); - if (dump_file && (dump_flags & TDF_DETAILS)) + while (new_stuff) { - size_t i; - fprintf (dump_file, "Occurrences for expression "); - print_generic_expr (dump_file, ei->expr, dump_flags); - fprintf (dump_file, " after Rename 2\n"); - for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++) - { - print_generic_expr (dump_file, - VARRAY_TREE (ei->euses_dt_order, i), 1); - fprintf (dump_file, "\n"); - } - } - compute_down_safety (ei); - compute_du_info (ei); - compute_will_be_avail (ei); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "EPHI's for expression "); - print_generic_expr (dump_file, ei->expr, dump_flags); - fprintf (dump_file, - " after down safety and will_be_avail computation\n"); - FOR_EACH_BB (bb) - { - tree ephi = ephi_at_block (bb); - if (ephi != NULL) - { - print_generic_expr (dump_file, ephi, 1); - fprintf (dump_file, "\n"); - } - } - } - - if (finalize_1 (ei)) - { - finalize_2 (ei); - code_motion (ei); - if (ei->loadpre_cand) - bitmap_set_bit (vars_to_rename, var_ann (ei->temp)->uid); + num_iterations++; + new_stuff = false; + new_stuff = insert_aux (ENTRY_BLOCK_PTR); } + if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, "insert required %d iterations\n", num_iterations); +} - clear_all_eref_arrays (); - if (dump_file) - if (dump_flags & TDF_STATS) - { - fprintf (dump_file, "PRE stats:\n"); - fprintf (dump_file, "Reloads:%d\n", pre_stats.reloads); - fprintf (dump_file, "Saves:%d\n", pre_stats.saves); - fprintf (dump_file, "Repairs:%d\n", pre_stats.repairs); - fprintf (dump_file, "New phis:%d\n", pre_stats.newphis); - fprintf (dump_file, "EPHI memory allocated:%d\n", - pre_stats.ephi_allocated); - fprintf (dump_file, "EREF memory allocated:%d\n", - pre_stats.eref_allocated); - fprintf (dump_file, "Expressions generated for rename2:%d\n", - pre_stats.exprs_generated); - } - cleanup: - free (phi_pred_cache); - if (ephi_pindex_htab) +/* Return true if EXPR has no defining statement in this procedure, + *AND* isn't a live-on-entry parameter. */ +static bool +is_undefined_value (tree expr) +{ + +#ifdef ENABLE_CHECKING + /* We should never be handed DECL's */ + if (DECL_P (expr)) + abort (); +#endif + if (TREE_CODE (expr) == SSA_NAME) { - htab_delete (ephi_pindex_htab); - ephi_pindex_htab = NULL; + /* XXX: Is this the correct test? */ + if (TREE_CODE (SSA_NAME_VAR (expr)) == PARM_DECL) + return false; + if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))) + return true; } - - - return 0; + return false; } +/* Compute the AVAIL set for BLOCK. + This function performs value numbering of the statements in BLOCK. + The AVAIL sets are built from information we glean while doing this + value numbering, since the AVAIL sets contain only entry per + value. -/* Step 1 - Collect the expressions to perform PRE on. */ + + AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)]. + AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U + TMP_GEN[BLOCK]. +*/ -static void -collect_expressions (basic_block block, varray_type *bexprsp) +static void +compute_avail (basic_block block) { - size_t k; - block_stmt_iterator j; basic_block son; - - varray_type bexprs = *bexprsp; - for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j)) + /* For arguments with default definitions, we pretend they are + defined in the entry block. */ + if (block == ENTRY_BLOCK_PTR) + { + tree param; + for (param = DECL_ARGUMENTS (current_function_decl); + param; + param = TREE_CHAIN (param)) + { + if (default_def (param) != NULL) + { + tree val; + tree def = default_def (param); + val = lookup_or_add (value_table, def); + insert_into_set (TMP_GEN (block), def); + value_insert_into_set (AVAIL_OUT (block), def); + } + } + } + else if (block) { - tree stmt = bsi_stmt (j); - tree expr = stmt; - tree orig_expr = expr; - stmt_ann_t ann; - struct expr_info *slot = NULL; - - get_stmt_operands (expr); - ann = stmt_ann (expr); - - if (NUM_USES (USE_OPS (ann)) == 0) + block_stmt_iterator bsi; + tree stmt, phi; + basic_block dom; + + dom = get_immediate_dominator (CDI_DOMINATORS, block); + if (dom) + set_copy (AVAIL_OUT (block), AVAIL_OUT (dom)); + for (phi = phi_nodes (block); phi; phi = TREE_CHAIN (phi)) { - process_left_occs_and_kills (bexprs, expr); - continue; + /* Ignore virtual PHIs until we can do PRE on expressions + with virtual operands. */ + if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) + continue; + + lookup_or_add (value_table, PHI_RESULT (phi)); + value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi)); + insert_into_set (PHI_GEN (block), PHI_RESULT (phi)); } - - if (TREE_CODE (expr) == MODIFY_EXPR) - expr = TREE_OPERAND (expr, 1); - if ((TREE_CODE_CLASS (TREE_CODE (expr)) == '2' - || TREE_CODE_CLASS (TREE_CODE (expr)) == '<' - /*|| TREE_CODE_CLASS (TREE_CODE (expr)) == '1'*/ - || TREE_CODE (expr) == SSA_NAME - || TREE_CODE (expr) == INDIRECT_REF) - && !ann->makes_aliased_stores - && !ann->has_volatile_ops) + + for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi)) { - bool is_scalar = true; - tree origop0 = TREE_OPERAND (orig_expr, 0); + tree op0, op1; + stmt = bsi_stmt (bsi); + get_stmt_operands (stmt); - if (AGGREGATE_TYPE_P (TREE_TYPE (origop0)) - || TREE_CODE (TREE_TYPE (origop0)) == COMPLEX_TYPE) - is_scalar = false; + if (NUM_VUSES (STMT_VUSE_OPS (stmt)) + || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) + || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) + || stmt_ann (stmt)->has_volatile_ops) + { + size_t j; + for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++) + { + tree def = DEF_OP (STMT_DEF_OPS (stmt), j); + lookup_or_add (value_table, def); + insert_into_set (TMP_GEN (block), def); + value_insert_into_set (AVAIL_OUT (block), def); + } + continue; + } + else if (TREE_CODE (stmt) == RETURN_EXPR + && TREE_OPERAND (stmt, 0) + && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) + stmt = TREE_OPERAND (stmt, 0); - if (is_scalar - && (TREE_CODE (expr) == SSA_NAME - || (TREE_CODE (expr) == INDIRECT_REF - && !DECL_P (TREE_OPERAND (expr, 0))) - ||(!DECL_P (TREE_OPERAND (expr, 0)) - && (!TREE_OPERAND (expr, 1) - || !DECL_P (TREE_OPERAND (expr, 1)))))) + if (TREE_CODE (stmt) == MODIFY_EXPR) { - for (k = 0; k < VARRAY_ACTIVE_SIZE (bexprs); k++) + op0 = TREE_OPERAND (stmt, 0); + if (TREE_CODE (op0) != SSA_NAME) + continue; + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)) + continue; + op1 = TREE_OPERAND (stmt, 1); + if (TREE_CODE_CLASS (TREE_CODE (op1)) == 'c') { - slot = VARRAY_GENERIC_PTR (bexprs, k); - if (expr_lexically_eq (slot->expr, expr)) - break; + add (value_table, op0, lookup_or_add (value_table, op1)); + insert_into_set (TMP_GEN (block), op0); + value_insert_into_set (AVAIL_OUT (block), op0); } - if (k >= VARRAY_ACTIVE_SIZE (bexprs)) - slot = NULL; - if (slot) + else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '2') { - VARRAY_PUSH_TREE (slot->occurs, orig_expr); - VARRAY_PUSH_TREE (slot->kills, NULL); - VARRAY_PUSH_TREE (slot->lefts, NULL); - VARRAY_PUSH_TREE (slot->reals, stmt); - slot->strred_cand &= is_strred_cand (orig_expr); + tree bop1, bop2; + tree val, val1, val2; + tree newt; + bop1 = TREE_OPERAND (op1, 0); + bop2 = TREE_OPERAND (op1, 1); + val1 = lookup_or_add (value_table, bop1); + val2 = lookup_or_add (value_table, bop2); + + newt = pool_alloc (binary_node_pool); + memcpy (newt, op1, tree_size (op1)); + TREE_OPERAND (newt, 0) = val1; + TREE_OPERAND (newt, 1) = val2; + val = lookup_or_add (value_table, newt); + add (value_table, op0, val); + if (!is_undefined_value (bop1)) + value_insert_into_set (EXP_GEN (block), bop1); + if (!is_undefined_value (bop2)) + value_insert_into_set (EXP_GEN (block), bop2); + value_insert_into_set (EXP_GEN (block), newt); + insert_into_set (TMP_GEN (block), op0); + value_insert_into_set (AVAIL_OUT (block), op0); + } + else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '1') + { + tree uop; + tree val, val1; + tree newt; + uop = TREE_OPERAND (op1, 0); + val1 = lookup_or_add (value_table, uop); + newt = pool_alloc (unary_node_pool); + memcpy (newt, op1, tree_size (op1)); + TREE_OPERAND (newt, 0) = val1; + val = lookup_or_add (value_table, newt); + add (value_table, op0, val); + if (!is_undefined_value (uop)) + value_insert_into_set (EXP_GEN (block), uop); + value_insert_into_set (EXP_GEN (block), newt); + insert_into_set (TMP_GEN (block), op0); + value_insert_into_set (AVAIL_OUT (block), op0); + } + else if (TREE_CODE (op1) == SSA_NAME) + { + tree val = lookup_or_add (value_table, op1); + add (value_table, op0, val); + if (!is_undefined_value (op1)) + value_insert_into_set (EXP_GEN (block), op1); + insert_into_set (TMP_GEN (block), op0); + value_insert_into_set (AVAIL_OUT (block), op0); } else { - slot = ggc_alloc (sizeof (struct expr_info)); - slot->expr = expr; - VARRAY_GENERIC_PTR_NOGC_INIT (slot->occurs, 1, "Occurrence"); - VARRAY_GENERIC_PTR_NOGC_INIT (slot->kills, 1, "Kills"); - VARRAY_GENERIC_PTR_NOGC_INIT (slot->lefts, 1, "Left occurrences"); - VARRAY_GENERIC_PTR_NOGC_INIT (slot->reals, 1, "Real occurrences"); - VARRAY_GENERIC_PTR_NOGC_INIT (slot->euses_dt_order, 1, "EUSEs"); - - VARRAY_PUSH_TREE (slot->occurs, orig_expr); - VARRAY_PUSH_TREE (slot->kills, NULL); - VARRAY_PUSH_TREE (slot->lefts, NULL); - VARRAY_PUSH_TREE (slot->reals, stmt); - VARRAY_PUSH_GENERIC_PTR (bexprs, slot); - slot->strred_cand = is_strred_cand (orig_expr); - slot->loadpre_cand = false; - if (TREE_CODE (expr) == SSA_NAME - || TREE_CODE (expr) == INDIRECT_REF) - slot->loadpre_cand = true; + size_t j; + for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++) + { + tree def = DEF_OP (STMT_DEF_OPS (stmt), j); + lookup_or_add (value_table, def); + insert_into_set (TMP_GEN (block), def); + value_insert_into_set (AVAIL_OUT (block), def); + value_insert_into_set (AVAIL_OUT (block), op0); + } + } + } + else + { + size_t j; + for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++) + { + tree def = DEF_OP (STMT_DEF_OPS (stmt), j); + lookup_or_add (value_table, def); + insert_into_set (TMP_GEN (block), def); + value_insert_into_set (AVAIL_OUT (block), def); } } } - process_left_occs_and_kills (bexprs, orig_expr); } - *bexprsp = bexprs; - for (son = first_dom_son (CDI_DOMINATORS, block); son; son = next_dom_son (CDI_DOMINATORS, son)) - collect_expressions (son, bexprsp); + compute_avail (son); + +} + +/* Eliminate fully redundant computations. */ + +static void +eliminate (void) +{ + basic_block b; + + FOR_EACH_BB (b) + { + block_stmt_iterator i; + + for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i)) + { + tree stmt = bsi_stmt (i); + + if (NUM_VUSES (STMT_VUSE_OPS (stmt)) + || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) + || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) + || stmt_ann (stmt)->has_volatile_ops) + continue; + /* Lookup the RHS of the expression, see if we have an + available computation for it. If so, replace the RHS with + the available computation. */ + if (TREE_CODE (stmt) == MODIFY_EXPR) + { + tree t = TREE_OPERAND (stmt, 0); + tree expr = TREE_OPERAND (stmt, 1); + tree sprime; + /* There is no point in eliminating NOP_EXPR, it isn't + supposed to generate any code. */ + if (TREE_CODE (expr) == NOP_EXPR + || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2' + && TREE_CODE_CLASS (TREE_CODE (expr)) != '1')) + continue; + sprime = find_leader (AVAIL_OUT (b), + lookup (value_table, t)); + if (sprime + && sprime != t + && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1))) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Replaced "); + print_generic_expr (dump_file, expr, 0); + fprintf (dump_file, " with "); + print_generic_expr (dump_file, sprime, 0); + fprintf (dump_file, " in "); + print_generic_stmt (dump_file, stmt, 0); + } + pre_stats.eliminations++; + propagate_value (&TREE_OPERAND (stmt, 1), sprime); + modify_stmt (stmt); + } + } + + } + } } /* Main entry point to the SSA-PRE pass. @@ -3308,83 +1790,85 @@ collect_expressions (basic_block block, varray_type *bexprsp) static void execute_pre (void) { - int currbbs; - varray_type bexprs; - size_t k; - int i; - - if (ENTRY_BLOCK_PTR->succ->dest->pred->pred_next) - if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_ABNORMAL)) - split_edge (ENTRY_BLOCK_PTR->succ); - - euse_node_pool = create_alloc_pool ("EUSE node pool", - sizeof (struct tree_euse_node), 30); - eref_node_pool = create_alloc_pool ("EREF node pool", - sizeof (struct tree_eref_common), 30); - ephi_use_pool = create_alloc_pool ("EPHI use node pool", - sizeof (struct ephi_use_entry), 30); - VARRAY_GENERIC_PTR_INIT (bexprs, 1, "bexprs"); - /* Compute immediate dominators. */ + size_t tsize; + basic_block bb; + pre_uid = num_referenced_vars; + memset (&pre_stats, 0, sizeof (pre_stats)); + FOR_ALL_BB (bb) + { + bb->aux = xcalloc (1, sizeof (struct bb_value_sets)); + } + phi_translate_table = htab_create (511, expr_pred_trans_hash, + expr_pred_trans_eq, + free); + value_table = htab_create (511, val_expr_pair_hash, + val_expr_pair_expr_eq, free); + value_set_pool = create_alloc_pool ("Value sets", + sizeof (struct value_set), 30); + value_set_node_pool = create_alloc_pool ("Value set nodes", + sizeof (struct value_set_node), 30); + calculate_dominance_info (CDI_POST_DOMINATORS); calculate_dominance_info (CDI_DOMINATORS); + tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE, + NULL_TREE)); + binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30); + tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE)); + unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30); - /* DCE screws the dom_children up, without bothering to fix it. So fix it. */ - currbbs = n_basic_blocks; - dfn = xcalloc (last_basic_block + 1, sizeof (int)); - build_dfn_array (ENTRY_BLOCK_PTR, 0); - - /* Initialize IDFS cache. */ - idfs_cache = xcalloc (currbbs, sizeof (bitmap)); + FOR_ALL_BB (bb) + { + EXP_GEN (bb) = set_new (true); + PHI_GEN (bb) = set_new (true); + TMP_GEN (bb) = set_new (false); + AVAIL_OUT (bb) = set_new (true); + } - /* Compute dominance frontiers. */ - pre_dfs = (bitmap *) xmalloc (sizeof (bitmap) * currbbs); - for (i = 0; i < currbbs; i++) - pre_dfs[i] = BITMAP_XMALLOC (); - compute_dominance_frontiers (pre_dfs); + compute_avail (ENTRY_BLOCK_PTR); - created_phi_preds = BITMAP_XMALLOC (); - - collect_expressions (ENTRY_BLOCK_PTR, &bexprs); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + FOR_ALL_BB (bb) + { + print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index); + print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index); + print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index); + } + } - ggc_push_context (); + /* Insert can get quite slow on an incredibly large number of basic + blocks due to some quadratic behavior. Until this behavior is + fixed, don't run it when he have an incredibly large number of + bb's. If we aren't going to run insert, there is no point in + computing ANTIC, either, even though it's plenty fast. */ - for (k = 0; k < VARRAY_ACTIVE_SIZE (bexprs); k++) + if (n_basic_blocks < 4000) { - pre_expression (VARRAY_GENERIC_PTR (bexprs, k), pre_dfs, vars_to_rename); - free_alloc_pool (euse_node_pool); - free_alloc_pool (eref_node_pool); - free_alloc_pool (ephi_use_pool); - euse_node_pool = create_alloc_pool ("EUSE node pool", - sizeof (struct tree_euse_node), 30); - eref_node_pool = create_alloc_pool ("EREF node pool", - sizeof (struct tree_eref_common), 30); - ephi_use_pool = create_alloc_pool ("EPHI use node pool", - sizeof (struct ephi_use_entry), 30); - free_expr_info (VARRAY_GENERIC_PTR (bexprs, k)); -#ifdef ENABLE_CHECKING - if (pre_stats.ephis_current != 0) - abort (); -#endif - ggc_collect (); + compute_antic (); + + insert (); + } + eliminate (); + + if (dump_file && (dump_flags & TDF_STATS)) + { + fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions); + fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis); + fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations); } - ggc_pop_context (); - - /* Clean up after PRE. */ - memset (&pre_stats, 0, sizeof (struct pre_stats_d)); - free_alloc_pool (euse_node_pool); - free_alloc_pool (eref_node_pool); - free_alloc_pool (ephi_use_pool); - VARRAY_CLEAR (bexprs); - for (i = 0; i < currbbs; i++) - BITMAP_XFREE (pre_dfs[i]); - free (pre_dfs); - BITMAP_XFREE (created_phi_preds); - for (i = 0; i < currbbs; i++) - if (idfs_cache[i] != NULL) - BITMAP_XFREE (idfs_cache[i]); + free_alloc_pool (value_set_pool); + free_alloc_pool (value_set_node_pool); + free_alloc_pool (binary_node_pool); + free_alloc_pool (unary_node_pool); + htab_delete (value_table); + htab_delete (phi_translate_table); - free (dfn); - free (idfs_cache); + FOR_ALL_BB (bb) + { + free (bb->aux); + bb->aux = NULL; + } + free_dominance_info (CDI_POST_DOMINATORS); } static bool @@ -3393,7 +1877,7 @@ gate_pre (void) return flag_tree_pre != 0; } -struct tree_opt_pass pass_pre = +struct tree_opt_pass pass_pre = { "pre", /* name */ gate_pre, /* gate */ @@ -3406,6 +1890,5 @@ struct tree_opt_pass pass_pre = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func | TODO_rename_vars - | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ + TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ }; @@ -1184,6 +1184,10 @@ struct tree_exp GTY(()) #define SSA_NAME_PTR_INFO(N) \ SSA_NAME_CHECK (N)->ssa_name.ptr_info +/* Get the value of this SSA_NAME, if available. */ +#define SSA_NAME_VALUE(N) \ + SSA_NAME_CHECK (N)->ssa_name.value_handle + #ifndef GCC_BITMAP_H struct bitmap_head_def; #endif @@ -1223,6 +1227,9 @@ struct tree_ssa_name GTY(()) /* Pointer attributes used for alias analysis. */ struct ptr_info_def *ptr_info; + + /* Value for SSA name used by GVN. */ + tree GTY((skip)) value_handle; }; /* In a PHI_NODE node. */ |