2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
29 /* These RTL headers are needed for basic-block.h. */
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
34 #include "diagnostic.h"
35 #include "tree-inline.h"
36 #include "tree-flow.h"
37 #include "tree-gimple.h"
38 #include "tree-dump.h"
42 #include "tree-iterator.h"
44 #include "alloc-pool.h"
45 #include "tree-pass.h"
51 Some of the algorithms are also based on Open64's SSAPRE implementation.
53 Since the papers are a bit dense to read, take a while to grasp,
54 and have a few bugs, i'll give a quick rundown:
56 Normally, in non-SSA form, one performs PRE on expressions using
57 bit vectors, determining properties for all expressions at once
58 through bitmap operations and iterative dataflow.
60 SSAPRE, like most non-SSA->SSA algorithm conversions, operates one
61 expression at a time, and doesn't use bitvectors or iterative
64 It answers the question "Given a single hypothetical temporary
65 variable, what expressions could we eliminate.
67 To be able to do this, we need an SSA form for expressions.
68 If you are already confused, you likely think an expression, as
69 used here, is something like "b_3 = a_2 + 5". It's not. It's "a +
70 5". "a_2 + 5" is an *occurrence* of the expression "a + 5". Just
71 like PRE, it's lexical equivalence that matters.
72 Compilers generally give you an SSA form for variables, and maybe
73 arrays (and/or conditionals). But not for expressions.
75 GCC doesn't give you one either, so we have to build it.
76 Thus, the first steps of SSAPRE are to do just these things.
78 First we collect lists of occurrences of expressions we are going
81 Unlike the paper, we don't have to ever add newly formed
82 expressions to the list (for normal SSAPRE, anyway), because we
83 don't have expressions with more than two operators, and each
84 operator is either a constant or a variable. Thus, no second
87 Once we have the lists of occurrences, we process one expression
88 at a time, doing the following:
89 1. Using a slightly modified SSA phi placement algorithm, place
90 expression PHI's for expressions.
91 2. Using a two step optimistic SSA renaming algorithm, version the
92 nodes and link phi operands to their real occurrences, if they
93 exist. This creates a factored graph of our expression SSA occurrences.
94 3. Using the factored graph, compute downsafe, avail, and later for
95 EPHIs (which are SSA versions of the same named bitvector PRE
97 4. Using EPHI availability information and versions, compute what
98 occurrences need to have saves, and what occurrences can be
99 reloaded from an already saved value.
100 5. Insert the saves and reloads, and transform EPHIs into regular
101 phis of the temporary we use for insertion/saving.
103 See http://citeseer.nj.nec.com/chow97new.html, and
104 http://citeseer.nj.nec.com/kennedy99partial.html for details of the
107 kennedy99partial is newer, and is what this implementation is based
110 For strength reduction addition, see
111 http://citeseer.nj.nec.com/kennedy98strength.html.
113 There is also a paper on sparse register promotion using PRE that
114 contains the basic algorithm for load PRE. The exact title/url of
115 the paper escapes me.
117 Lastly, there is a code hoisting extension that open64 performs
118 (see opt_ehoist.cxx), but we don't. It's not documented in any
119 papers, but not that difficult to understand of implement. */
123 Do strength reduction on a +-b and -a, not just a * <constant>.
127 static void clear_all_eref_arrays (void);
128 static inline bool expr_lexically_eq (const tree, const tree);
129 static void free_expr_info (struct expr_info *);
130 static bitmap compute_idfs (bitmap *, tree);
131 static void set_var_phis (struct expr_info *, tree);
132 static inline bool names_match_p (const tree, const tree);
133 static bool is_strred_cand (const tree);
134 static int pre_expression (struct expr_info *, void *, bitmap);
135 static bool is_injuring_def (struct expr_info *, tree);
136 static inline bool okay_injuring_def (tree, tree);
137 static bool expr_phi_insertion (bitmap *, struct expr_info *);
138 static tree factor_through_injuries (struct expr_info *, tree, tree, bool *);
139 static inline tree maybe_find_rhs_use_for_var (tree, tree, unsigned int);
140 static inline tree find_rhs_use_for_var (tree, tree);
141 static tree create_ephi_node (basic_block, unsigned int);
142 static inline int opnum_of_phi (tree, int);
143 static inline int opnum_of_ephi (const tree, const edge);
144 static tree subst_phis (struct expr_info *, tree, basic_block, basic_block);
145 static void generate_expr_as_of_bb (tree, basic_block, basic_block);
146 static void generate_vops_as_of_bb (tree, basic_block, basic_block);
147 static void rename_1 (struct expr_info *);
148 static void process_delayed_rename (struct expr_info *, tree, tree);
149 static void assign_new_class (tree, varray_type *, varray_type *);
150 static void create_and_insert_occ_in_preorder_dt_order (struct expr_info *);
151 static void insert_euse_in_preorder_dt_order (struct expr_info *);
152 static bool ephi_has_unsafe_arg (tree);
153 static void reset_down_safe (tree, int);
154 static void compute_down_safety (struct expr_info *);
155 static void compute_will_be_avail (struct expr_info *);
156 static void compute_stops (struct expr_info *);
157 static bool finalize_1 (struct expr_info *);
158 static void finalize_2 (struct expr_info *);
159 static tree occ_identical_to (tree);
160 static void require_phi (struct expr_info *, basic_block);
161 static bool really_available_def (tree node);
163 /* Functions used for an EPHI based depth first search. */
164 struct ephi_df_search
166 /* Return true if the ephi has been seen. */
168 /* Mark the ephi as seen. */
169 void (*set_seen) (tree);
170 /* Note that the search reaches from one ephi to it's use. */
171 void (*reach_from_to) (tree, int, tree);
172 /* Return true if we should start a search from this PHI. */
173 bool (*start_from) (tree);
174 /* Return true if we should continue the search to this use. */
175 bool (*continue_from_to) (tree, int, tree);
177 static bool repl_search_seen (tree);
178 static void repl_search_set_seen (tree);
179 static void repl_search_reach_from_to (tree, int, tree);
180 static bool repl_search_start_from (tree);
181 static bool repl_search_continue_from_to (tree, int, tree);
182 static bool stops_search_seen (tree);
183 static void stops_search_set_seen (tree);
184 static void stops_search_reach_from_to (tree, int, tree);
185 static bool stops_search_start_from (tree);
186 static bool stops_search_continue_from_to (tree, int, tree);
187 static bool cba_search_seen (tree);
188 static void cba_search_set_seen (tree);
189 static bool cba_search_start_from (tree);
190 static bool cba_search_continue_from_to (tree, int, tree);
191 struct ephi_df_search cant_be_avail_search = {
195 cba_search_start_from,
196 cba_search_continue_from_to
199 struct ephi_df_search stops_search = {
201 stops_search_set_seen,
202 stops_search_reach_from_to,
203 stops_search_start_from,
204 stops_search_continue_from_to
208 /* depth-first replacement search used during temp ESSA minimization. */
209 struct ephi_df_search replacing_search = {
211 repl_search_set_seen,
212 repl_search_reach_from_to,
213 repl_search_start_from,
214 repl_search_continue_from_to
217 static void do_ephi_df_search_1 (struct ephi_df_search, tree);
218 static void do_ephi_df_search (struct expr_info *, struct ephi_df_search);
220 static inline bool any_operand_injured (tree);
221 static void code_motion (struct expr_info *);
222 static tree pick_ssa_name (tree stmt);
224 static tree calculate_increment (struct expr_info *, tree);
226 static bool can_insert (tree, int);
227 static void set_save (struct expr_info *, tree);
228 static tree reaching_def (tree, tree, basic_block, tree);
229 static tree do_proper_save (tree , tree, int);
230 static void process_left_occs_and_kills (varray_type, tree);
231 static tree create_expr_ref (struct expr_info *, tree, enum tree_code,
233 static inline bool ephi_will_be_avail (tree);
234 static inline tree ephi_at_block (basic_block);
235 static tree get_default_def (tree, htab_t);
236 static inline bool same_e_version_real_occ_real_occ (struct expr_info *,
239 static inline bool load_modified_phi_result (basic_block, tree);
240 static inline bool same_e_version_phi_result (struct expr_info *,
242 static inline bool load_modified_real_occ_real_occ (tree, tree);
243 static inline bool same_e_version_real_occ_phi_opnd (struct expr_info *,
246 static inline bool injured_real_occ_real_occ (struct expr_info *,
248 static inline bool injured_phi_result_real_occ (struct expr_info *,
249 tree, tree, basic_block);
250 static inline bool injured_real_occ_phi_opnd (struct expr_info *,
251 tree, basic_block, int);
252 static void compute_du_info (struct expr_info *);
253 static void add_ephi_use (tree, tree, int);
254 static void insert_one_operand (struct expr_info *, tree, int, tree, edge,
256 static void collect_expressions (basic_block, varray_type *);
257 static int build_dfn_array (basic_block, int);
258 static int eref_compare (const void *, const void *);
261 /* Bitmap of E-PHI predecessor operands have already been created.
262 We only create one phi-pred per block. */
263 static bitmap created_phi_preds;
265 /* PRE dominance frontiers. */
266 static bitmap *pre_dfs;
268 /* Number of redundancy classes. */
269 static int class_count = 0;
272 /* Iterated dominance frontiers cache. */
273 static bitmap *idfs_cache;
275 /* Partial redundancies statistics. */
276 static struct pre_stats_d
286 } pre_stats = {0, 0, 0, 0, 0, 0, 0, 0};
289 /* USE entry in list of uses of ephi's. */
290 struct ephi_use_entry
296 /* PRE Expression specific info. */
299 /* The actual expression. */
301 /* The occurrences. */
305 /* The left occurrences. */
307 /* An array of real occurrences. */
309 /* True if it's a strength reduction candidate. */
311 /* True if it's a load PRE candidate. */
313 /* The euses/ephis in preorder dt order. */
314 varray_type euses_dt_order;
315 /* The name of the temporary for this expression. */
320 /* Cache of expressions generated for given phi operand, to avoid
321 recomputation and wasting memory. */
322 static tree *phi_pred_cache;
323 static int n_phi_preds;
325 /* Trying to lookup ephi pred operand indexes takes forever on graphs
326 that have high connectivity because it's an O(n) linked list
327 traversal. Thus, we set up a hashtable that tells us the operand
328 index for a given edge. */
330 typedef struct ephi_pred_index_elt
337 /* Hash an (ephi, edge, opnd) tuple. */
340 ephi_pindex_hash (const void *p)
342 const ephi_pindex_t *ep = (const ephi_pindex_t *)p;
343 return htab_hash_pointer (ep->ephi) + htab_hash_pointer (ep->edge);
346 /* Determine equality of an (ephi, edge, opnd) tuple. */
349 ephi_pindex_eq (const void *p1, const void *p2)
351 const ephi_pindex_t *ep1 = (const ephi_pindex_t *)p1;
352 const ephi_pindex_t *ep2 = (const ephi_pindex_t *)p2;
354 return ep1->ephi == ep2->ephi && ep1->edge == ep2->edge;
357 /* The (ephi, edge) => opnd mapping hashtable. */
358 static htab_t ephi_pindex_htab;
360 /* Add an ephi predecessor to a PHI. */
363 add_ephi_pred (tree phi, tree def, edge e)
365 int i = EPHI_NUM_ARGS (phi);
367 ephi_pindex_t ep, *epp;
369 EPHI_ARG_PRED (phi, i) = def;
370 EPHI_ARG_EDGE (phi, i) = e;
374 slot = htab_find_slot (ephi_pindex_htab, (void *)&ep, INSERT);
377 epp = xmalloc (sizeof (*epp));
386 EPHI_NUM_ARGS (phi)++;
390 /* Create a new EPHI node at basic block BB. */
393 create_ephi_node (basic_block bb, unsigned int add)
401 for (len = 0, e = bb->pred; e; e = e->pred_next)
403 size = (sizeof (struct tree_ephi_node)
404 + ((len - 1) * sizeof (struct ephi_arg_d)));
406 phi = xmalloc (size);
407 memset (phi, 0, size);
411 if (ann->ephi_nodes == NULL)
412 ann->ephi_nodes = phi;
414 chainon (ann->ephi_nodes, phi);
416 pre_stats.ephi_allocated += size;
417 pre_stats.ephis_current += 1;
418 TREE_SET_CODE (phi, EPHI_NODE);
419 EPHI_NUM_ARGS (phi) = 0;
420 EPHI_ARG_CAPACITY (phi) = len;
422 /* Associate BB to the PHI node. */
423 set_bb_for_stmt (phi, bb);
428 /* Given DEF (which can be an SSA_NAME or entire statement), and VAR,
429 find a use of VAR on the RHS of DEF, if one exists. Abort if we
433 find_rhs_use_for_var (tree def, tree var)
435 tree ret = maybe_find_rhs_use_for_var (def, var, 0);
441 /* Determine if two trees are referring to the same variable.
442 Handles SSA_NAME vs non SSA_NAME, etc. Uses operand_equal_p for
443 non-trivial cases (INDIRECT_REF and friends). */
446 names_match_p (const tree t1, const tree t2)
453 if (TREE_CODE (t1) == INDIRECT_REF)
454 return names_match_p (TREE_OPERAND (t1, 0), t2);
456 if (TREE_CODE (t2) == INDIRECT_REF)
457 return names_match_p (t1, TREE_OPERAND (t2, 0));
459 if (TREE_CODE (t1) == SSA_NAME)
460 name1 = SSA_NAME_VAR (t1);
461 else if (DECL_P (t1))
466 if (TREE_CODE (t2) == SSA_NAME)
467 name2 = SSA_NAME_VAR (t2);
468 else if (DECL_P (t2))
473 if (name1 == NULL_TREE && name2 != NULL_TREE)
475 if (name2 == NULL_TREE && name1 != NULL_TREE)
477 if (name1 == NULL_TREE && name2 == NULL_TREE)
478 return operand_equal_p (t1, t2, 0);
480 return name1 == name2;
483 /* Given DEF (which can be an SSA_NAME or entire statement), and VAR,
484 find a use of VAR on the RHS of DEF, if one exists. Return NULL if
485 we cannot find one. */
488 maybe_find_rhs_use_for_var (tree def, tree var, unsigned int startpos)
495 if (names_match_p (var, def))
499 get_stmt_operands (def);
500 uses = STMT_USE_OPS (def);
502 for (i = startpos; i < NUM_USES (uses); i++)
504 tree use = USE_OP (uses, i);
505 if (names_match_p (use, var))
511 /* Determine if an injuring def is one which we can repair, and thus,
512 ignore for purposes of determining the version of a variable. */
515 okay_injuring_def (tree inj, tree var)
517 /* Acceptable injuries are those which
518 1. aren't empty statements.
520 3. contain a use of VAR on the RHS. */
521 if (!inj || IS_EMPTY_STMT (inj)
522 || TREE_CODE (inj) == PHI_NODE
523 || !maybe_find_rhs_use_for_var (inj, var, 0))
528 /* Return true if INJ is an injuring definition */
531 is_injuring_def (struct expr_info *ei, tree inj)
533 /* Things that are never injuring definitions. */
534 if (!inj || IS_EMPTY_STMT (inj) || TREE_CODE (inj) == PHI_NODE)
537 /* Things we can't handle. */
538 if (TREE_CODE (TREE_OPERAND (inj, 1)) != PLUS_EXPR
539 && TREE_CODE (TREE_OPERAND (inj, 1)) != MINUS_EXPR)
542 /* given inj: a1 = a2 + 5
550 Or, in English, if either the assigned-to variable in
551 the injury is different from the first variable in the
552 expression, or the incremented variable is different from the
553 first variable in the expression, punt.
555 This makes sure we have something of the form
558 for an expression like "a * 5".
560 This limitation only exists because we don't know how to repair
561 other forms of increments/decrements. */
562 if (!names_match_p (TREE_OPERAND (inj, 0), TREE_OPERAND (ei->expr, 0))
563 || !TREE_OPERAND (TREE_OPERAND (inj, 1), 0)
564 || !names_match_p (TREE_OPERAND (TREE_OPERAND (inj, 1), 0),
565 TREE_OPERAND (ei->expr, 0)))
568 /* If we are strength reducing a multiply, we have the additional
571 2. {expr} and the RHS of the expression are constants. */
572 if (TREE_CODE (ei->expr) == MULT_EXPR)
577 irhs = TREE_OPERAND (inj, 1);
578 irhs1 = TREE_OPERAND (irhs, 0);
579 irhs2 = TREE_OPERAND (irhs, 1);
581 if (TREE_CODE (irhs2) != INTEGER_CST)
583 if (tree_low_cst (irhs2, 0) == 1)
585 if (really_constant_p (irhs2)
586 && really_constant_p (TREE_OPERAND (ei->expr, 1)))
588 /* We don't currently support "the injury is inside a loop,expr is
589 loop-invariant, and b is either loop-invariant or is
590 another induction variable with respect to the loop." */
596 /* Find the statement defining VAR, ignoring injuries we can repair.
597 START is the first potential injuring def. */
600 factor_through_injuries (struct expr_info *ei, tree start, tree var,
605 while (is_injuring_def (ei, SSA_NAME_DEF_STMT (end)))
609 end = find_rhs_use_for_var (SSA_NAME_DEF_STMT (end), var);
610 if (!okay_injuring_def (SSA_NAME_DEF_STMT (end), var))
614 fprintf (dump_file, "Found a real injury:");
615 print_generic_stmt (dump_file, SSA_NAME_DEF_STMT (end), dump_flags);
616 fprintf (dump_file, "\n");
620 end = find_rhs_use_for_var (SSA_NAME_DEF_STMT (end), var);
625 /* Return true if the result of the EPHI, when transformed into a phi,
626 will be available. */
629 ephi_will_be_avail (tree ephi)
631 if (!EPHI_CANT_BE_AVAIL (ephi))
632 if (EPHI_STOPS (ephi))
638 /* EUSE node pool. We allocate EUSE nodes out of this*/
639 static alloc_pool euse_node_pool;
641 /* EREF node pool. We allocate regular EREF nodes (like EEXIT_NODE)
643 static alloc_pool eref_node_pool;
646 /* To order EREF's in a given block, we assign them each an ID based
647 on when we see them. */
648 static int eref_id_counter = 0;
650 /* Creation an expression reference of TYPE. */
653 create_expr_ref (struct expr_info *ei, tree expr, enum tree_code type,
654 basic_block bb, tree parent)
657 if (type == EPHI_NODE)
662 ret = create_ephi_node (bb, 1);
663 for (len = 0, e = bb->pred; e; e = e->pred_next)
666 EREF_TEMP (ret) = make_phi_node (ei->temp, len);
670 if (type == EUSE_NODE)
671 ret = (tree) pool_alloc (euse_node_pool);
673 ret = (tree) pool_alloc (eref_node_pool);
674 TREE_SET_CODE (ret, type);
675 memset (ret, 0, tree_size (ret));
676 TREE_SET_CODE (ret, type);
677 pre_stats.eref_allocated += tree_size (ret);
680 EREF_NAME (ret) = expr;
681 set_bb_for_stmt (ret, bb);
682 EREF_STMT (ret) = parent;
683 EREF_SAVE (ret) = false;
684 EREF_ID (ret) = eref_id_counter++;
690 /* dfphis is a bitmap of where we need to insert ephis due to the
691 iterated dominance frontier of an expression. */
693 static bitmap dfphis;
695 /* varphis is a bitmap of where we need to insert ephis due to the
696 presence of phis for a variable. */
698 static bitmap varphis;
701 /* Function to recursively figure out where EPHI's need to be placed
703 We always place EPHI's where we place PHI's because they are also
704 partially anticipated expression points (because some expression
705 alteration reaches that merge point).
707 We do this recursively, because we have to figure out
708 EPHI's for the variables in the PHI as well. */
711 set_var_phis (struct expr_info *ei, tree phi)
713 basic_block bb = bb_for_stmt (phi);
714 /* If we've already got an EPHI set to be placed in PHI's BB, we
715 don't need to do this again. */
716 if (!bitmap_bit_p (varphis, bb->index)
717 && !bitmap_bit_p (dfphis, bb->index))
720 int curr_phi_operand;
721 bitmap_set_bit (varphis, bb->index);
722 for (curr_phi_operand = 0;
723 curr_phi_operand < PHI_NUM_ARGS (phi);
726 phi_operand = PHI_ARG_DEF (phi, curr_phi_operand);
727 /* For strength reduction, factor through injuries we can
729 if (ei->strred_cand && TREE_CODE (phi_operand) != PHI_NODE)
731 phi_operand = factor_through_injuries (ei, phi_operand,
732 SSA_NAME_VAR (phi_operand),
734 phi_operand = SSA_NAME_DEF_STMT (phi_operand);
737 fprintf (dump_file, "After factoring through injuries:");
738 print_generic_stmt (dump_file, phi_operand, dump_flags);
739 fprintf (dump_file, "\n");
743 /* If our phi operand is defined by a phi, we need to
744 record where the phi operands alter the expression as
745 well, and place EPHI's at each point. */
746 if (TREE_CODE (phi_operand) == PHI_NODE)
747 set_var_phis (ei, phi_operand);
753 /* Clear all the expression reference arrays. */
756 clear_all_eref_arrays (void)
766 free (ann->ephi_nodes);
767 pre_stats.ephis_current -= 1;
769 ann->ephi_nodes = NULL;
773 /* EPHI insertion algorithm. */
776 expr_phi_insertion (bitmap *dfs, struct expr_info *ei)
783 dfphis = BITMAP_XMALLOC ();
784 bitmap_zero (dfphis);
785 varphis = BITMAP_XMALLOC ();
786 bitmap_zero (varphis);
788 /* Compute where we need to place EPHIS. There are two types of
789 places we need EPHI's: Those places we would normally place a
790 PHI for the occurrence (calculated by determining the IDF+ of
791 the statement), and those places we need an EPHI due to partial
793 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->occurs); i++)
795 tree occurp = VARRAY_TREE (ei->occurs, i);
796 tree occur = occurp ? occurp : NULL;
797 tree killp = VARRAY_TREE (ei->kills, i);
798 tree kill = killp ? killp : NULL;
799 tree leftp = VARRAY_TREE (ei->lefts, i);
800 tree left = leftp ? leftp : NULL;
804 #ifdef ENABLE_CHECKING
805 if ((kill && occur) || (left && occur) || (kill && left))
808 occurp = occur ? occurp : kill ? killp : leftp;
809 occur = occur ? occur : kill ? kill : left;
810 temp = compute_idfs (dfs, occur);
811 bitmap_a_or_b (dfphis, dfphis, temp);
814 get_stmt_operands (occurp);
815 ann = stmt_ann (occurp);
816 uses = USE_OPS (ann);
817 for (j = 0; j < NUM_USES (uses); j ++)
819 tree use = USE_OP (uses, j);
821 use = factor_through_injuries (ei, use, SSA_NAME_VAR (use),
823 if (TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE)
825 set_var_phis (ei, SSA_NAME_DEF_STMT (use));
827 if (ei->loadpre_cand && TREE_CODE (ei->expr) == INDIRECT_REF)
829 vuses = VUSE_OPS (ann);
830 for (j = 0; j < NUM_VUSES (vuses); j ++)
832 tree use = VUSE_OP (vuses, j);
834 use = factor_through_injuries (ei, use, SSA_NAME_VAR (use),
836 if (TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE)
838 set_var_phis (ei, SSA_NAME_DEF_STMT (use));
842 /* Union the results of the dfphis and the varphis to get the
843 answer to everywhere we need EPHIS. */
844 bitmap_a_or_b (dfphis, dfphis, varphis);
846 /* Now create the EPHI's in each of these blocks. */
847 EXECUTE_IF_SET_IN_BITMAP(dfphis, 0, i,
849 tree ref = create_expr_ref (ei, ei->expr, EPHI_NODE, BASIC_BLOCK (i),
851 EREF_PROCESSED (ref) = false;
852 EPHI_DOWNSAFE (ref) = true;
853 EPHI_DEAD (ref) = true;
856 /* If there are no phis, we don't have anything to optimize,
857 assuming the dominator optimizer took care of it all. */
858 if (bitmap_first_set_bit (dfphis) == -1)
861 BITMAP_XFREE (dfphis);
862 BITMAP_XFREE (varphis);
867 /* Return the EPHI at block BB, if one exists. */
870 ephi_at_block (basic_block bb)
872 bb_ann_t ann = bb_ann (bb);
874 return ann->ephi_nodes;
879 /* Depth first numbering array. */
882 /* Build a depth first numbering array to be used in sorting in
886 build_dfn_array (basic_block bb, int num)
891 dfn[bb->index] = num;
893 for (son = first_dom_son (CDI_DOMINATORS, bb);
895 son = next_dom_son (CDI_DOMINATORS, son))
896 num = build_dfn_array (son, ++num);
901 /* Compare two EREF's in terms of dominator preorder. Return -1 if
902 ELEM1 goes before ELEM2, 1 if ELEM1 goes after ELEM2, and 0 if they
906 eref_compare (const void *elem1, const void *elem2)
908 tree t1 = *(tree *)elem1;
909 tree t2 = *(tree *)elem2;
910 basic_block bb1, bb2;
913 bb1 = bb_for_stmt (t1);
914 bb2 = bb_for_stmt (t2);
917 if (TREE_CODE (t1) == EEXIT_NODE)
919 if (TREE_CODE (t2) == EEXIT_NODE)
921 if (TREE_CODE (t1) == EPHI_NODE)
923 if (TREE_CODE (t2) == EPHI_NODE)
925 if ((TREE_CODE (t1) == EUSE_NODE && EUSE_PHIOP (t1))
926 && (TREE_CODE (t2) == EUSE_NODE && !EUSE_PHIOP (t2)))
928 if ((TREE_CODE (t1) == EUSE_NODE && !EUSE_PHIOP (t1))
929 && (TREE_CODE (t2) == EUSE_NODE && EUSE_PHIOP (t2)))
931 if (TREE_CODE (t1) == EUSE_NODE && TREE_CODE (t2) == EUSE_NODE)
932 return EREF_ID (t1) - EREF_ID (t2);
933 if (TREE_CODE (t1) == EPHI_NODE && TREE_CODE (t2) == EPHI_NODE)
939 if (dfn[bb1->index] == dfn[bb2->index])
941 if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
947 return (dfn[bb1->index] < dfn[bb2->index]) ? -1 : 1;
953 /* Create expression references for occurrences, kills, phi operands,
954 and the like. At the same time, insert the occurrences into the
955 ei->euses_dt_order array in the proper order. If this function had
956 any use outside of rename_1, you could split it into two
957 functions, one creating, one inserting. */
960 create_and_insert_occ_in_preorder_dt_order (struct expr_info *ei)
964 tree curr_phi_pred = NULL_TREE;
967 /* The ephis references were already created, so just push them into
968 the euses_dt_order list. */
971 tree ephi = ephi_at_block (block);
972 /* The ordering for a given BB is EPHI's, real/left/kill
973 occurrences, phi preds, exit occurrences. */
974 if (ephi != NULL_TREE)
975 VARRAY_PUSH_TREE (ei->euses_dt_order, ephi);
978 /* The non-ephis have to actually be created, so do that, then push
979 them into the list. */
981 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->occurs); i++)
985 current = VARRAY_TREE (ei->occurs, i);
986 current = current ? current : VARRAY_TREE (ei->kills, i);
987 current = current ? current : VARRAY_TREE (ei->lefts, i);
988 block = bb_for_stmt (current);
989 if (VARRAY_TREE (ei->kills, i) != NULL)
991 tree killexpr = VARRAY_TREE (ei->kills, i);
992 tree killname = ei->expr;
993 newref = create_expr_ref (ei, killname, EKILL_NODE, block, killexpr);
994 VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
996 else if (VARRAY_TREE (ei->lefts, i) != NULL)
998 tree occurexpr = VARRAY_TREE (ei->lefts, i);
1000 occurname = ei->expr;
1001 newref = create_expr_ref (ei, occurname, EUSE_NODE, block,
1003 EUSE_DEF (newref) = NULL_TREE;
1004 EUSE_LVAL (newref) = true;
1005 EREF_CLASS (newref) = -1;
1006 EUSE_PHIOP (newref) = false;
1007 EREF_PROCESSED (newref) = false;
1008 VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1012 tree occurexpr = VARRAY_TREE (ei->occurs, i);
1014 occurname = ei->expr;
1015 newref = create_expr_ref (ei, occurname, EUSE_NODE, block,
1017 EUSE_DEF (newref) = NULL_TREE;
1018 EREF_CLASS (newref) = -1;
1019 EUSE_PHIOP (newref) = false;
1020 EREF_PROCESSED (newref) = false;
1021 VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1025 /* Lastly, we need to create and insert the ephi operand occurrences
1029 /* Insert the phi operand occurrences into the list at the
1031 for (succ = block->succ; succ; succ = succ->succ_next)
1033 if (succ->dest != EXIT_BLOCK_PTR)
1035 tree ephi = ephi_at_block (succ->dest);
1037 && !bitmap_bit_p (created_phi_preds, block->index))
1039 tree newref = create_expr_ref (ei, 0, EUSE_NODE, block, NULL);
1040 curr_phi_pred = newref;
1041 VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1042 EUSE_DEF (newref) = NULL_TREE;
1043 EREF_CLASS (newref) = -1;
1044 EUSE_PHIOP (newref) = true;
1045 EREF_SAVE (newref) = false;
1046 EREF_RELOAD (newref) = false;
1047 EUSE_INSERTED (newref) = false;
1048 EREF_PROCESSED (newref) = false;
1049 bitmap_set_bit (created_phi_preds, block->index);
1050 add_ephi_pred (ephi, newref, succ);
1052 else if (ephi != NULL)
1054 #ifdef ENABLE_CHECKING
1055 if (curr_phi_pred == NULL_TREE)
1058 add_ephi_pred (ephi, curr_phi_pred, succ);
1061 else if (succ->dest == EXIT_BLOCK_PTR && !(succ->flags & EDGE_FAKE))
1063 /* No point in inserting exit blocks into heap first, since
1064 they'll never be anything on the stack. */
1066 newref = create_expr_ref (ei, ei->expr, EEXIT_NODE,
1069 VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1073 qsort (ei->euses_dt_order->data.tree,
1074 VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
1080 /* Assign a new redundancy class to the occurrence, and push it on the
1084 assign_new_class (tree occ, varray_type * stack, varray_type * stack2)
1086 /* class(occ) <- count
1090 EREF_CLASS (occ) = class_count;
1091 VARRAY_PUSH_TREE (*stack, occ);
1093 VARRAY_PUSH_TREE (*stack2, occ);
1097 /* Determine if two real occurrences have the same ESSA version.
1098 We do this by hashing the expressions and comparing the hash
1099 values. Even if they don't match, we then see if this is a
1100 strength reduction candidate, and if so, if the use is simply
1104 same_e_version_real_occ_real_occ (struct expr_info *ei,
1105 const tree def, const tree use)
1111 const tree t1 = EREF_STMT (def);
1112 const tree t2 = EREF_STMT (use);
1114 expr1val = iterative_hash_expr (TREE_OPERAND (t1, 1), 0);
1115 expr2val = iterative_hash_expr (TREE_OPERAND (t2, 1), 0);
1117 if (expr1val == expr2val)
1119 vuses = STMT_VUSE_OPS (t1);
1120 for (i = 0; i < NUM_VUSES (vuses); i++)
1121 expr1val = iterative_hash_expr (VUSE_OP (vuses, i), expr1val);
1122 vuses = STMT_VUSE_OPS (t2);
1123 for (i = 0; i < NUM_VUSES (vuses); i++)
1124 expr2val = iterative_hash_expr (VUSE_OP (vuses, i), expr2val);
1125 if (expr1val != expr2val)
1129 /* If the def is injured, and the expressions have the same value,
1130 then the use is injured. */
1131 if (expr1val == expr2val)
1133 if (EREF_INJURED (def))
1134 EREF_INJURED (use) = true;
1138 /* Even if the expressions don't have the same value, it might be
1139 the case that the use is simply injured, in which case, it's
1141 if (expr1val != expr2val && ei->strred_cand)
1143 if (injured_real_occ_real_occ (ei, def, use))
1145 EREF_INJURED (use) = true;
1152 /* Determine if the use occurrence is injured.
1153 TODO: Finish actually implementing this. */
1156 injured_real_occ_real_occ (struct expr_info *ei ATTRIBUTE_UNUSED,
1157 tree def ATTRIBUTE_UNUSED,
1158 tree use ATTRIBUTE_UNUSED)
1163 defstmt = EREF_STMT (def);
1164 if (TREE_CODE (TREE_OPERAND (defstmt, 0)) != SSA_NAME)
1167 defvar = TREE_OPERAND (defstmt, 0);
1168 /* XXX: Implement. */
1173 /* Determine the operand number of edge E in EPHI. */
1176 opnum_of_ephi (const tree ephi, const edge e)
1178 ephi_pindex_t ep, *epp;
1182 epp = htab_find (ephi_pindex_htab, &ep);
1188 /* Determine the phi operand index for J in PHI. */
1191 opnum_of_phi (tree phi, int j)
1194 /* We can't just count predecessors, since tree-ssa.c generates them
1195 when it sees a phi in the successor during it's traversal. So the
1196 order is dependent on the traversal order. */
1197 for (i = 0 ; i < PHI_NUM_ARGS (phi); i++)
1198 if (PHI_ARG_EDGE (phi, i)->src->index == j)
1204 /* Generate EXPR as it would look in basic block PRED (using the phi in
1205 block BB). We do this by replacing the variables with the phi
1206 argument definitions for block J if they are defined by a phi in
1210 generate_expr_as_of_bb (tree expr, basic_block pred, basic_block bb)
1212 use_optype uses = STMT_USE_OPS (expr);
1213 bool replaced_constants = false;
1216 for (k = 0; k < NUM_USES (uses); k++)
1218 tree *vp = USE_OP_PTR (uses, k);
1222 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1224 if (PHI_RESULT (phi) == v)
1226 int opnum = opnum_of_phi (phi, pred->index);
1227 tree p = PHI_ARG_DEF (phi, opnum);
1228 replace_exp (vp, p);
1229 if (!phi_ssa_name_p (p))
1230 replaced_constants = true;
1236 /* If we've substituted in new constants, we must be sure to
1237 simplify the result lest we crash in get_expr_operands. */
1238 if (replaced_constants)
1242 /* Generate VUSE ops as they would look in basic block PRED (using the
1243 phi in block BB). Done the same way as we do generation of regular
1247 generate_vops_as_of_bb (tree expr, basic_block pred, basic_block bb)
1249 vuse_optype vuses = STMT_VUSE_OPS (expr);
1252 for (i = 0; i < NUM_VUSES (vuses); i++)
1254 tree v = VUSE_OP (vuses, i);
1257 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1259 if (PHI_RESULT (phi) == v)
1261 int opnum = opnum_of_phi (phi, pred->index);
1262 tree p = PHI_ARG_DEF (phi, opnum);
1263 replace_exp (VUSE_OP_PTR (vuses, i), p);
1270 /* Make a copy of Z as it would look in basic block PRED, using the PHIs
1274 subst_phis (struct expr_info *ei, tree Z, basic_block pred, basic_block bb)
1279 /* Return the cached version, if we have one. */
1280 if (pred->index < n_phi_preds
1281 && phi_pred_cache[pred->index] != NULL_TREE)
1282 return phi_pred_cache[pred->index];
1284 /* Otherwise, generate a new expression. */
1285 pre_stats.exprs_generated++;
1286 stmt_copy = unshare_expr (Z);
1287 create_stmt_ann (stmt_copy);
1288 modify_stmt (stmt_copy);
1289 get_stmt_operands (stmt_copy);
1290 generate_expr_as_of_bb (stmt_copy, pred, bb);
1291 set_bb_for_stmt (stmt_copy, bb);
1292 modify_stmt (stmt_copy);
1293 get_stmt_operands (stmt_copy);
1295 /* If we have vuses on the original statement, and we still have
1296 use_ops on the generated expr, we need to copy the vuses. */
1298 if (ei->loadpre_cand
1299 && NUM_VUSES (STMT_VUSE_OPS (Z)) != 0
1300 && NUM_USES (STMT_USE_OPS (stmt_copy)) != 0)
1302 vuse_optype vuses = STMT_VUSE_OPS (Z);
1303 remove_vuses (stmt_copy);
1305 start_ssa_stmt_operands (stmt_copy);
1306 for (i = 0; i < NUM_VUSES (vuses); i++)
1307 add_vuse (VUSE_OP (vuses, i), stmt_copy);
1308 finalize_ssa_stmt_operands (stmt_copy);
1310 generate_vops_as_of_bb (stmt_copy, pred, bb);
1314 remove_vuses (stmt_copy);
1315 remove_v_may_defs (stmt_copy);
1316 remove_v_must_defs (stmt_copy);
1319 if (pred->index < n_phi_preds)
1320 phi_pred_cache[pred->index] = stmt_copy;
1324 /* Determine if def and use_tree should have the same e-version. We do
1325 this by simply determining if something modifies the expression
1326 between DEF and USE_TREE. USE_TREE was generated from the OPND_NUM'th
1327 operand of the EPHI in USE_BB. If it is modified, we determine if
1328 it is simply injured, and thus, okay. */
1331 same_e_version_real_occ_phi_opnd (struct expr_info *ei, tree def,
1332 basic_block use_bb, int opnd_num,
1333 tree use_tree, bool *injured)
1335 bool not_mod = true;
1338 if (load_modified_real_occ_real_occ (EREF_STMT (def),
1344 else if (ei->strred_cand)
1346 if (injured_real_occ_phi_opnd (ei, def, use_bb, opnd_num))
1352 /* Determine whether the OPND_NUM'th operand of USE_BB's EPHI is an
1353 injured version of DEF. */
1355 injured_real_occ_phi_opnd (struct expr_info *ei ATTRIBUTE_UNUSED,
1356 tree def ATTRIBUTE_UNUSED,
1357 basic_block use_bb ATTRIBUTE_UNUSED,
1358 int opnd_num ATTRIBUTE_UNUSED)
1360 /* XXX: Implement. */
1364 /* Determine whether the expression is modified between DEF and USE,
1365 by comparing the hash values of the two expressions. */
1367 load_modified_real_occ_real_occ (tree def, tree use)
1374 if (TREE_CODE (def) == VA_ARG_EXPR)
1375 expr1val = iterative_hash_expr (def, 0);
1377 expr1val = iterative_hash_expr (TREE_OPERAND (def, 1), 0);
1379 if (TREE_CODE (use) == VA_ARG_EXPR)
1380 expr2val = iterative_hash_expr (use, 0);
1382 expr2val = iterative_hash_expr (TREE_OPERAND (use, 1), 0);
1384 if (expr1val == expr2val)
1386 vuses = STMT_VUSE_OPS (def);
1387 for (i = 0; i < NUM_VUSES (vuses); i++)
1388 expr1val = iterative_hash_expr (VUSE_OP (vuses, i), expr1val);
1389 vuses = STMT_VUSE_OPS (use);
1390 for (i = 0; i < NUM_VUSES (vuses); i++)
1391 expr2val = iterative_hash_expr (VUSE_OP (vuses, i), expr2val);
1392 if (expr1val != expr2val)
1395 return expr1val != expr2val;
1398 /* Determine if the expression is modified between the start of BB,
1399 and the use at USE, ignoring phis. We do this by simple
1400 domination, because of the properties of SSA. */
1402 load_modified_phi_result (basic_block bb, tree use)
1404 basic_block defbb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
1407 /* This guards against moving around undefined variables.
1408 However, PARM_DECL is special because it *IS* live on entry,
1409 so it's not really undefined. */
1410 if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) != PARM_DECL)
1412 else if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) == PARM_DECL)
1414 if (dominated_by_p (CDI_DOMINATORS, bb, defbb))
1419 if (TREE_CODE (SSA_NAME_DEF_STMT (use)) == PHI_NODE)
1425 /* Determine if the variables in EXP are modified between DEF and
1426 USE. If they are, we have to give a new e-version to the result.
1427 For load PRE, we have to check the vuses too. For strength
1428 reduction, we need to check whether the modification is a simple
1432 same_e_version_phi_result (struct expr_info *ei, tree def, tree exp,
1435 stmt_ann_t ann = stmt_ann (exp);
1436 bool not_mod = true;
1438 use_optype real_expuses = USE_OPS (ann);
1439 vuse_optype expuses;
1442 if (NUM_USES (real_expuses) == 0)
1445 for (i = 0; i < NUM_USES (real_expuses) && not_mod; i++)
1447 tree *use1p = USE_OP_PTR (real_expuses, i);
1452 if (load_modified_phi_result (bb_for_stmt (def), use1))
1456 if (not_mod && ei->loadpre_cand)
1458 expuses = VUSE_OPS (ann);
1460 for (i = 0; i < NUM_VUSES (expuses) && not_mod; i++)
1462 tree use1 = VUSE_OP (expuses, i);
1463 if (load_modified_phi_result (bb_for_stmt (def), use1))
1470 else if (ei->strred_cand)
1472 if (injured_phi_result_real_occ (ei, def, exp, bb_for_stmt (use)))
1474 EREF_INJURED (use) = true;
1482 /* Determine whether USE_TREE is an injured version of DEF. */
1485 injured_phi_result_real_occ (struct expr_info *ei ATTRIBUTE_UNUSED,
1486 tree def ATTRIBUTE_UNUSED,
1487 tree use_tree ATTRIBUTE_UNUSED,
1488 basic_block use_bb ATTRIBUTE_UNUSED)
1490 /* XXX: Implement. */
1494 /* Delayed renaming checks to make sure the optimistic assumptions
1495 about ephi operand versions in rename_1 actually turned out to be
1496 true. This requires generating the expressions for each ephi
1497 operand, and comparing them to the versions of the occurrence it is
1499 Delayed rename handling is done like open64 does it. Basically,
1500 like the delayed renaming is described in the paper, with
1501 extensions for strength reduction. */
1504 process_delayed_rename (struct expr_info *ei, tree use, tree real_occ)
1509 /* We only care about operands we actually have DELAYED_RENAME set
1511 for (opnd_num = 0; opnd_num < EPHI_NUM_ARGS (exp_phi); opnd_num++)
1513 tree opnd = EPHI_ARG_DEF (exp_phi, opnd_num);
1514 if (EPHI_ARG_DELAYED_RENAME (exp_phi, opnd_num))
1519 /* Mark it as being processed, then generate the ephi
1520 operand expression. */
1521 EPHI_ARG_DELAYED_RENAME (exp_phi, opnd_num) = false;
1523 newexp = subst_phis (ei, real_occ,
1524 EPHI_ARG_EDGE (exp_phi, opnd_num)->src,
1525 bb_for_stmt (exp_phi));
1527 /* For operands defined by EPHIs, we need to compare the
1528 generated expression and the phi result.
1529 For operands defined by real occurrences, we simply compare
1530 the phi operand and the real occurrence. */
1531 if (TREE_CODE (def) == EPHI_NODE)
1533 tree tmp_use = EPHI_ARG_PRED (exp_phi, opnd_num);
1534 EREF_STMT (tmp_use) = newexp;
1535 if (same_e_version_phi_result (ei, def, newexp,
1539 if (EREF_INJURED (tmp_use))
1541 EREF_INJURED (tmp_use) = false;
1542 EPHI_ARG_INJURED (exp_phi, opnd_num) = true;
1544 if (EREF_STMT (def) == NULL)
1546 /* If it was injured, we need to make up a new
1547 phi result with the actually injured
1549 if (EPHI_ARG_INJURED (exp_phi, opnd_num))
1551 /* XXX: Allocate phi result with correct version. */
1554 EREF_STMT (def) = newexp;
1555 process_delayed_rename (ei, def, newexp);
1558 /* If it's not the same version, the defining ephi can't
1559 be downsafe, and the operand is not really defined by
1563 EPHI_DOWNSAFE (def) = false;
1564 EPHI_ARG_DEF (exp_phi, opnd_num) = NULL;
1567 else if (TREE_CODE (def) == EUSE_NODE && !EUSE_PHIOP (def))
1569 bool injured = false;
1570 if (same_e_version_real_occ_phi_opnd (ei, def,
1572 opnd_num, newexp, &injured))
1574 tree tmp_use = EPHI_ARG_PRED (exp_phi, opnd_num);
1575 EPHI_ARG_HAS_REAL_USE (exp_phi, opnd_num) = true;
1576 /* EREF_STMT (opnd) = EREF_STMT (def); */
1577 if (injured || EREF_INJURED (def))
1578 EREF_INJURED (def) = true;
1579 if (injured || EREF_INJURED (def))
1580 EREF_INJURED (opnd) = true;
1582 EREF_STMT (tmp_use) = EREF_STMT (def);
1583 if (EUSE_DEF (def) != NULL)
1584 EPHI_ARG_DEF (exp_phi, opnd_num) = EUSE_DEF (def);
1586 EPHI_ARG_DEF (exp_phi, opnd_num) = def;
1590 EPHI_ARG_DEF (exp_phi, opnd_num) = NULL;
1597 /* For the uninitiated, the algorithm is a modified SSA renaming
1598 algorithm (working on expressions rather than variables) . We
1599 attempt to determine which expression occurrences have the same
1600 ESSA version (we call it class, for equivalence/redundancy class,
1601 which is what the papers call it. Open64 calls it e-version), and
1602 which occurrences are actually operands for an EPHI (since this has
1603 to be discovered from the program).
1605 Renaming is done like Open64 does it. Basically as the paper says,
1606 except that we try to use earlier defined occurrences if they are
1607 available in order to keep the number of saves down. */
1610 rename_1 (struct expr_info *ei)
1617 VARRAY_GENERIC_PTR_NOGC_INIT (stack, 1, "Stack for renaming");
1619 /* Start by creating and inserting the occurrences in preorder,
1620 dominator tree into a list. */
1621 create_and_insert_occ_in_preorder_dt_order (ei);
1623 /* Walk the occurrences. */
1624 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1626 occur = VARRAY_TREE (ei->euses_dt_order, i);
1628 /* The current occurrence can't have the same version as
1629 something on the top of the stack unless it is in a basic
1630 block dominated by the basic block of the occurrence on the
1631 top of the stack. */
1632 while (VARRAY_ACTIVE_SIZE (stack) > 0
1633 && !dominated_by_p (CDI_DOMINATORS,
1634 bb_for_stmt (occur),
1635 bb_for_stmt (VARRAY_TOP_TREE (stack))))
1639 /* If the stack is empty, we assign a new version since it isn't
1640 dominated by any other version. */
1641 if (VARRAY_ACTIVE_SIZE (stack) == 0 || VARRAY_TOP_TREE (stack) == NULL)
1643 if (TREE_CODE (occur) == EPHI_NODE)
1644 assign_new_class (occur, &stack, NULL);
1645 else if (TREE_CODE (occur) == EUSE_NODE && !EUSE_PHIOP (occur))
1646 assign_new_class (occur, &stack, NULL);
1650 if (TREE_CODE (occur) == EUSE_NODE && !EUSE_PHIOP (occur))
1652 tree tos = VARRAY_TOP_TREE (stack);
1654 if (TREE_CODE (tos) == EUSE_NODE && !EUSE_PHIOP (tos))
1656 /* If two real occurrences have the same
1657 e-version/class, then this occurrence can be
1658 defined by the prior occurrence (or whatever
1659 the prior occurrence is defined by, if
1661 Otherwise, we have to assign a new version.
1662 lvalue occurrences always need a new version,
1663 since they are definitions. */
1664 if (!EUSE_LVAL (occur)
1665 && same_e_version_real_occ_real_occ (ei, tos, occur))
1670 EREF_CLASS (occur) = EREF_CLASS (tos);
1671 newdef = EUSE_DEF (tos) != NULL ? EUSE_DEF (tos) : tos;
1672 EUSE_DEF (occur) = newdef;
1675 assign_new_class (occur, &stack, NULL);
1677 else if (TREE_CODE (tos) == EPHI_NODE)
1679 /* Here we have an ephi occurrence at the top of the
1680 stack, and the current occurrence is a real
1681 occurrence. So determine if the real occurrence
1682 has the same version as the result of the phi.
1683 If so, then this real occurrence is defined by the
1684 EPHI at the top of the stack.
1685 If not, the EPHI isn't downsafe (because something
1686 must change in between the ephi result and the next
1687 occurrence), and we need a new version for the real
1689 lvalues always need a new version. */
1690 if (!EUSE_LVAL (occur)
1691 && same_e_version_phi_result (ei, tos, EREF_STMT (occur),
1694 EREF_CLASS (occur) = EREF_CLASS (tos);
1695 EUSE_DEF (occur) = tos;
1696 EREF_STMT (tos) = EREF_STMT (occur);
1698 VARRAY_PUSH_TREE (stack, occur);
1702 EPHI_DOWNSAFE (tos) = false;
1703 assign_new_class (occur, &stack, NULL);
1707 /* EPHI occurrences always get new versions. */
1708 else if (TREE_CODE (occur) == EPHI_NODE)
1710 assign_new_class (occur, &stack, NULL);
1712 /* EPHI operands are optimistcally assumed to be whatever is
1713 at the top of the stack at the time we hit the ephi
1714 operand occurrence. The delayed renaming checks this
1715 optimistic assumption for validity. */
1716 else if (TREE_CODE (occur) == EUSE_NODE && EUSE_PHIOP (occur))
1718 basic_block pred_bb = bb_for_stmt (occur);
1720 tree tos = VARRAY_TOP_TREE (stack);
1721 for (e = pred_bb->succ; e; e = e->succ_next)
1723 tree ephi = ephi_at_block (e->dest);
1724 if (ephi != NULL_TREE)
1726 int opnum = opnum_of_ephi (ephi, e);
1728 EPHI_ARG_DELAYED_RENAME (ephi, opnum) = true;
1729 EPHI_ARG_DEF (ephi, opnum) = tos;
1733 /* No EPHI can be downsafe past an exit node. */
1734 else if (TREE_CODE (occur) == EEXIT_NODE)
1736 if (VARRAY_ACTIVE_SIZE (stack) > 0
1737 && TREE_CODE (VARRAY_TOP_TREE (stack)) == EPHI_NODE)
1738 EPHI_DOWNSAFE (VARRAY_TOP_TREE (stack)) = false;
1742 if (dump_file && (dump_flags & TDF_DETAILS))
1745 fprintf (dump_file, "Occurrences for expression ");
1746 print_generic_expr (dump_file, ei->expr, dump_flags);
1747 fprintf (dump_file, " after Rename 1\n");
1748 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1750 print_generic_expr (dump_file,
1751 VARRAY_TREE (ei->euses_dt_order, i), 1);
1752 fprintf (dump_file, "\n");
1756 /* Now process the renames for EPHI's that actually have the result
1757 valid and used. These will be the EPHI's that have the statement
1759 FOR_EACH_BB (phi_bb)
1761 tree ephi = ephi_at_block (phi_bb);
1762 if (ephi != NULL && EREF_STMT (ephi) != NULL)
1763 process_delayed_rename (ei, ephi, EREF_STMT (ephi));
1766 /* If we didn't process the delayed rename for an ephi argument,
1767 but thought we needed to, mark the operand as NULL. Also, if the
1768 operand was defined by an EPHI, we can mark it not downsafe
1769 because there can't have been a real occurrence (or else we would
1770 have processed a rename for it). */
1771 FOR_EACH_BB (phi_bb)
1773 tree ephi = ephi_at_block (phi_bb);
1777 for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1779 if (EPHI_ARG_DELAYED_RENAME (ephi, j))
1781 tree def = EPHI_ARG_DEF (ephi, j);
1782 if (def && TREE_CODE (def) == EPHI_NODE)
1783 EPHI_DOWNSAFE (def) = false;
1784 EPHI_ARG_DEF (ephi, j) = NULL;
1789 VARRAY_FREE (stack);
1792 /* Determine if the EPHI has an argument we could never insert
1793 or extend the lifetime of, such as an argument occurring on
1794 an abnormal edge. */
1797 ephi_has_unsafe_arg (tree ephi)
1800 for (i = 0; i < EPHI_NUM_ARGS (ephi); i++)
1801 if (EPHI_ARG_EDGE (ephi, i)->flags & EDGE_ABNORMAL)
1806 /* Reset down safety flags for non-downsafe ephis. Uses depth first
1810 reset_down_safe (tree currphi, int opnum)
1815 if (EPHI_ARG_HAS_REAL_USE (currphi, opnum))
1817 ephi = EPHI_ARG_DEF (currphi, opnum);
1818 if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
1820 if (!EPHI_DOWNSAFE (ephi))
1822 EPHI_DOWNSAFE (ephi) = false;
1823 for (i = 0; i < EPHI_NUM_ARGS (ephi); i++)
1824 reset_down_safe (ephi, i);
1827 /* Compute down_safety using a depth first search.
1828 This propagates not fully anticipated phi assignments upwards. */
1831 compute_down_safety (struct expr_info *ei)
1837 tree ephi = ephi_at_block (bb);
1838 if (ephi == NULL_TREE)
1840 if (ephi_has_unsafe_arg (ephi))
1841 EPHI_DOWNSAFE (ephi) = false;
1843 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1846 tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
1847 if (TREE_CODE (ephi) != EPHI_NODE)
1850 if (!EPHI_DOWNSAFE (ephi))
1851 for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1852 reset_down_safe (ephi, j);
1857 /* EPHI use node pool. We allocate ephi_use_node's out of this. */
1858 static alloc_pool ephi_use_pool;
1860 /* Add a use of DEF to it's use list. The use is at operand OPND_INDX
1864 add_ephi_use (tree def, tree use, int opnd_indx)
1866 struct ephi_use_entry *entry;
1867 if (EPHI_USES (def) == NULL)
1868 VARRAY_GENERIC_PTR_INIT (EPHI_USES (def), 1, "EPHI uses");
1869 entry = (struct ephi_use_entry *) pool_alloc (ephi_use_pool);
1871 entry->opnd_indx = opnd_indx;
1872 VARRAY_PUSH_GENERIC_PTR (EPHI_USES (def), entry);
1875 /* Compute def-uses of ephis. */
1878 compute_du_info (struct expr_info *ei)
1881 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1884 tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
1885 if (TREE_CODE (ephi) != EPHI_NODE)
1887 for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1889 tree def = EPHI_ARG_DEF (ephi, j);
1890 if (def != NULL_TREE)
1892 if (TREE_CODE (def) == EPHI_NODE)
1893 add_ephi_use (def, ephi, j);
1894 #ifdef ENABLE_CHECKING
1896 if (! (TREE_CODE (def) == EUSE_NODE && !EUSE_PHIOP (def)))
1904 /* STOPS marks what EPHI's/operands stop forward movement. (IE where
1905 we can't insert past). */
1908 compute_stops (struct expr_info *ei)
1912 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1914 tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
1917 if (TREE_CODE (ephi) != EPHI_NODE)
1919 if (EPHI_CANT_BE_AVAIL (ephi))
1920 EPHI_STOPS (ephi) = true;
1921 for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1922 if (EPHI_ARG_HAS_REAL_USE (ephi, j))
1923 EPHI_ARG_STOPS (ephi, j) = true;
1925 do_ephi_df_search (ei, stops_search);
1928 /* Compute will_be_avail property, which consists of cant_be_avail and
1929 stops properties. */
1932 compute_will_be_avail (struct expr_info *ei)
1934 do_ephi_df_search (ei, cant_be_avail_search);
1938 /* Insert the expressions into ei->euses_dt_order in preorder dt order. */
1941 insert_euse_in_preorder_dt_order (struct expr_info *ei)
1943 varray_type new_euses_dt_order;
1945 VARRAY_GENERIC_PTR_NOGC_INIT (new_euses_dt_order, 1, "EUSEs");
1947 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1949 tree ref = VARRAY_TREE (ei->euses_dt_order, i);
1950 if (TREE_CODE (ref) == EUSE_NODE || TREE_CODE (ref) == EPHI_NODE)
1951 VARRAY_PUSH_TREE (new_euses_dt_order, ref);
1953 VARRAY_FREE (ei->euses_dt_order);
1954 ei->euses_dt_order = new_euses_dt_order;
1955 qsort (ei->euses_dt_order->data.tree,
1956 VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
1962 /* Determine if we can insert operand OPND_INDX of EPHI. */
1965 can_insert (tree ephi, int opnd_indx)
1969 if (EPHI_ARG_DEF (ephi, opnd_indx) == NULL_TREE)
1971 def = EPHI_ARG_DEF (ephi, opnd_indx);
1972 if (!EPHI_ARG_HAS_REAL_USE (ephi, opnd_indx))
1973 if (TREE_CODE (def) == EPHI_NODE && !(ephi_will_be_avail (def)))
1978 /* Find the default definition of VAR.
1979 This is incredibly ugly, since we have to walk back through all
1980 the definitions to find the one defined by the empty statement. */
1983 get_default_def (tree var, htab_t seen)
1987 tree defstmt = SSA_NAME_DEF_STMT (var);
1989 if (IS_EMPTY_STMT (defstmt))
1991 *(htab_find_slot (seen, var, INSERT)) = var;
1992 if (TREE_CODE (defstmt) == PHI_NODE)
1995 for (j = 0; j < PHI_NUM_ARGS (defstmt); j++)
1996 if (htab_find (seen, PHI_ARG_DEF (defstmt, j)) == NULL)
1998 if (TREE_CODE (PHI_ARG_DEF (defstmt, j)) == SSA_NAME)
2000 tree temp = get_default_def (PHI_ARG_DEF (defstmt, j), seen);
2001 if (temp != NULL_TREE)
2008 defs = STMT_DEF_OPS (defstmt);
2009 for (i = 0; i < NUM_DEFS (defs); i++)
2011 tree def = DEF_OP (defs, i);
2012 if (SSA_NAME_VAR (def) == SSA_NAME_VAR (var))
2014 if (htab_find (seen, def) != NULL)
2016 return get_default_def (def, seen);
2020 /* We should never get here. */
2024 /* Hunt down the right reaching def for VAR, starting with BB. Ignore
2025 defs in statement IGNORE, and stop if we hit CURRSTMT. */
2028 reaching_def (tree var, tree currstmt, basic_block bb, tree ignore)
2030 tree curruse = NULL_TREE;
2031 block_stmt_iterator bsi;
2035 /* Check phis first. */
2036 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
2038 if (phi == currstmt)
2042 if (names_match_p (var, PHI_RESULT (phi)))
2043 curruse = PHI_RESULT (phi);
2046 /* We can't walk BB's backwards right now, so we have to walk *all*
2047 the statements, and choose the last name we find. */
2048 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2050 tree stmt = bsi_stmt (bsi);
2055 if (stmt == currstmt)
2058 get_stmt_operands (stmt);
2059 defs = STMT_DEF_OPS (stmt);
2060 for (i = 0; i < NUM_DEFS (defs); i++)
2062 def = DEF_OP_PTR (defs, i);
2063 if (def && *def != ignore && names_match_p (var, *def))
2070 if (curruse != NULL_TREE)
2072 dom = get_immediate_dominator (CDI_DOMINATORS, bb);
2073 if (bb == ENTRY_BLOCK_PTR)
2076 temp = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL);
2077 curruse = get_default_def (var, temp);
2082 return reaching_def (var, currstmt, dom, ignore);
2085 /* Insert one ephi operand that doesn't currently exist as a use. */
2088 insert_one_operand (struct expr_info *ei, tree ephi, int opnd_indx,
2089 tree x, edge succ, tree **avdefsp)
2091 /* FIXME. pre_insert_on_edge should probably disappear. */
2092 extern void pre_insert_on_edge (edge, tree);
2094 tree temp = ei->temp;
2097 basic_block bb = bb_for_stmt (x);
2099 /* Insert definition of expr at end of BB containing x. */
2100 copy = TREE_OPERAND (EREF_STMT (ephi), 1);
2101 copy = unshare_expr (copy);
2102 expr = build (MODIFY_EXPR, TREE_TYPE (ei->expr),
2104 expr = subst_phis (ei, expr, bb, bb_for_stmt (ephi));
2105 newtemp = make_ssa_name (temp, expr);
2106 TREE_OPERAND (expr, 0) = newtemp;
2107 copy = TREE_OPERAND (expr, 1);
2110 fprintf (dump_file, "In BB %d, insert save of ", bb->index);
2111 print_generic_expr (dump_file, expr, dump_flags);
2112 fprintf (dump_file, " to ");
2113 print_generic_expr (dump_file, newtemp, dump_flags);
2114 fprintf (dump_file, " after ");
2115 print_generic_stmt (dump_file, last_stmt (bb), dump_flags);
2116 fprintf (dump_file, " (on edge), because of EPHI");
2117 fprintf (dump_file, " in BB %d\n", bb_for_stmt (ephi)->index);
2120 /* Do the insertion. */
2121 /* ??? Previously we did bizarre searching, presumably to get
2122 around bugs elsewhere in the infrastructure. I'm not sure
2123 if we really should be using pre_insert_on_edge
2124 or just bsi_insert_after at the end of BB. */
2125 pre_insert_on_edge (succ, expr);
2127 EPHI_ARG_DEF (ephi, opnd_indx)
2128 = create_expr_ref (ei, ei->expr, EUSE_NODE, bb, 0);
2129 EUSE_DEF (x) = EPHI_ARG_DEF (ephi, opnd_indx);
2130 VARRAY_PUSH_TREE (ei->euses_dt_order, EPHI_ARG_DEF (ephi, opnd_indx));
2131 qsort (ei->euses_dt_order->data.tree,
2132 VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
2135 EREF_TEMP (EUSE_DEF (x)) = newtemp;
2136 EREF_RELOAD (EUSE_DEF (x)) = false;
2137 EREF_SAVE (EUSE_DEF (x)) = false;
2138 EUSE_INSERTED (EUSE_DEF (x)) = true;
2139 EUSE_PHIOP (EUSE_DEF (x)) = false;
2140 EREF_SAVE (x) = false;
2141 EREF_RELOAD (x) = false;
2142 EUSE_INSERTED (x) = true;
2143 EREF_CLASS (x) = class_count++;
2144 EREF_CLASS (EUSE_DEF (x)) = class_count++;
2145 *avdefsp = xrealloc (*avdefsp, sizeof (tree) * (class_count + 1));
2146 (*avdefsp)[class_count - 2] = x;
2147 (*avdefsp)[class_count - 1] = EUSE_DEF (x);
2151 /* First step of finalization. Determine which expressions are being
2152 saved and which are being deleted.
2153 This is done as a simple dominator based availability calculation,
2154 using the e-versions/redundancy classes. */
2157 finalize_1 (struct expr_info *ei)
2161 bool made_a_reload = false;
2165 avdefs = xcalloc (class_count + 1, sizeof (tree));
2167 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2169 x = VARRAY_TREE (ei->euses_dt_order, i);
2170 nx = EREF_CLASS (x);
2172 if (TREE_CODE (x) == EPHI_NODE)
2174 if (ephi_will_be_avail (x))
2177 else if (TREE_CODE (x) == EUSE_NODE && EUSE_LVAL (x))
2181 else if (TREE_CODE (x) == EUSE_NODE && !EUSE_PHIOP (x))
2183 if (avdefs[nx] == NULL
2184 || !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (x),
2185 bb_for_stmt (avdefs[nx])))
2187 EREF_RELOAD (x) = false;
2189 EUSE_DEF (x) = NULL;
2193 EREF_RELOAD (x) = true;
2194 made_a_reload = true;
2195 EUSE_DEF (x) = avdefs[nx];
2196 #ifdef ENABLE_CHECKING
2197 if (EREF_CLASS (x) != EREF_CLASS (avdefs[nx]))
2205 basic_block bb = bb_for_stmt (x);
2206 /* For each ephi in the successor blocks. */
2207 for (succ = bb->succ; succ; succ = succ->succ_next)
2209 tree ephi = ephi_at_block (succ->dest);
2210 if (ephi == NULL_TREE)
2212 if (ephi_will_be_avail (ephi))
2214 int opnd_indx = opnum_of_ephi (ephi, succ);
2215 #ifdef ENABLE_CHECKING
2216 if (EPHI_ARG_PRED (ephi, opnd_indx) != x)
2219 if (can_insert (ephi, opnd_indx))
2221 insert_one_operand (ei, ephi, opnd_indx, x, succ,
2226 nx = EREF_CLASS (EPHI_ARG_DEF (ephi,opnd_indx));
2227 EPHI_ARG_DEF (ephi, opnd_indx) = avdefs[nx];
2234 return made_a_reload;
2237 /* Mark the necessary SAVE bits on X. */
2240 set_save (struct expr_info *ei, tree X)
2242 if (TREE_CODE (X) == EUSE_NODE && !EUSE_PHIOP (X))
2243 EREF_SAVE (X) = true;
2244 else if (TREE_CODE (X) == EPHI_NODE)
2247 for (curr_phiop = 0; curr_phiop < EPHI_NUM_ARGS (X); curr_phiop++)
2249 tree w = EPHI_ARG_DEF (X, curr_phiop);
2250 if (!EPHI_ARG_PROCESSED2 (X, curr_phiop))
2252 EPHI_ARG_PROCESSED2 (X, curr_phiop) = true;
2260 /* DFS Search function: Return true if PHI is can't be available. */
2263 cba_search_seen (tree phi)
2265 return EPHI_CANT_BE_AVAIL (phi);
2268 /* DFS Search function: Mark PHI as can't be available when seen. */
2271 cba_search_set_seen (tree phi)
2273 EPHI_CANT_BE_AVAIL (phi) = true;
2276 /* DFS Search function: Return true if PHI should be marked can't be
2277 available due to a NULL operand. */
2280 cba_search_start_from (tree phi)
2282 if (!EPHI_DOWNSAFE (phi))
2285 for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2286 if (EPHI_ARG_DEF (phi, i) == NULL_TREE
2287 || EPHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL)
2293 /* DFS Search function: Return true if the used PHI is not downsafe,
2294 unless we have a real use for the operand. */
2297 cba_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED,
2301 if (EPHI_ARG_HAS_REAL_USE (use_phi, opnd_indx) &&
2302 !(EPHI_ARG_EDGE (use_phi, opnd_indx)->flags & EDGE_ABNORMAL))
2304 if (!EPHI_DOWNSAFE (use_phi))
2309 /* DFS Search function: Return true if this PHI stops forward
2313 stops_search_seen (tree phi)
2315 return EPHI_STOPS (phi);
2318 /* DFS Search function: Mark the PHI as stopping forward movement. */
2321 stops_search_set_seen (tree phi)
2323 EPHI_STOPS (phi) = true;
2326 /* DFS Search function: Note that the used phi argument stops forward
2330 stops_search_reach_from_to (tree def_phi ATTRIBUTE_UNUSED,
2334 EPHI_ARG_STOPS (use_phi, opnd_indx) = true;
2337 /* DFS Search function: Return true if the PHI has any arguments
2338 stopping forward movement. */
2341 stops_search_start_from (tree phi)
2344 for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2345 if (EPHI_ARG_STOPS (phi, i))
2350 /* DFS Search function: Return true if the PHI has any arguments
2351 stopping forward movement. */
2354 stops_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED,
2355 int opnd_indx ATTRIBUTE_UNUSED,
2358 return stops_search_start_from (use_phi);
2361 /* DFS Search function: Return true if the replacing occurrence is
2365 repl_search_seen (tree phi)
2367 return EPHI_REP_OCCUR_KNOWN (phi);
2370 /* DFS Search function: Set the identical_to field and note the
2371 replacing occurrence is now known. */
2374 repl_search_set_seen (tree phi)
2378 #ifdef ENABLE_CHECKING
2379 if (!ephi_will_be_avail (phi))
2383 if (EPHI_IDENTICAL_TO (phi) == NULL_TREE)
2385 for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2387 tree identical_to = occ_identical_to (EPHI_ARG_DEF (phi, i));
2388 if (identical_to != NULL_TREE)
2390 if (EPHI_IDENTICAL_TO (phi) == NULL)
2391 EPHI_IDENTICAL_TO (phi) = identical_to;
2392 if (EPHI_ARG_INJURED (phi, i))
2393 EPHI_IDENT_INJURED (phi) = true;
2397 EPHI_REP_OCCUR_KNOWN (phi) = true;
2400 /* Helper function. Return true if any argument in the PHI is
2404 any_operand_injured (tree ephi)
2407 for (i = 0; i < EPHI_NUM_ARGS (ephi); i++)
2408 if (EPHI_ARG_INJURED (ephi, i))
2414 /* DFS Search function: Note the identity of the used phi operand is
2415 the same as it's defining phi operand, if that phi will be
2416 available, and it's known. */
2419 repl_search_reach_from_to (tree def_phi, int opnd_indx ATTRIBUTE_UNUSED,
2422 if (ephi_will_be_avail (use_phi)
2423 && EPHI_IDENTITY (use_phi)
2424 && EPHI_IDENTICAL_TO (use_phi) == NULL_TREE)
2426 EPHI_IDENTICAL_TO (use_phi) = EPHI_IDENTICAL_TO (def_phi);
2428 if (EPHI_IDENT_INJURED (def_phi)
2429 || any_operand_injured (use_phi))
2430 EPHI_IDENT_INJURED (use_phi) = true;
2434 /* DFS Search function: Return true if the PHI will be available,
2435 it's an identity PHI, and it's arguments are identical to
2439 repl_search_start_from (tree phi)
2441 if (ephi_will_be_avail (phi) && EPHI_IDENTITY (phi))
2444 for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2445 if (occ_identical_to (EPHI_ARG_DEF (phi, i)) != NULL_TREE)
2451 /* DFS Search function: Return true if the using PHI is will be available,
2455 repl_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED,
2456 int opnd_indx ATTRIBUTE_UNUSED,
2459 return ephi_will_be_avail (use_phi) && EPHI_IDENTITY (use_phi);
2462 /* Mark all will-be-avail ephi's in the dominance frontier of BB as
2466 require_phi (struct expr_info *ei, basic_block bb)
2469 EXECUTE_IF_SET_IN_BITMAP (pre_dfs[bb->index], 0, i,
2472 ephi = ephi_at_block (BASIC_BLOCK (i));
2473 if (ephi != NULL_TREE
2474 && ephi_will_be_avail (ephi)
2475 && EPHI_IDENTITY (ephi))
2477 EPHI_IDENTITY (ephi) = false;
2478 require_phi (ei, BASIC_BLOCK (i));
2483 /* Return the occurrence this occurrence is identical to, if one exists. */
2486 occ_identical_to (tree t)
2488 if (TREE_CODE (t) == EUSE_NODE && !EUSE_PHIOP (t))
2490 else if (TREE_CODE (t) == EUSE_NODE && EUSE_PHIOP (t))
2492 else if (TREE_CODE (t) == EPHI_NODE)
2494 if (EPHI_IDENTITY (t) && EPHI_REP_OCCUR_KNOWN (t))
2495 return EPHI_IDENTICAL_TO (t);
2496 else if (!EPHI_IDENTITY (t))
2502 /* Return true if NODE was or is going to be saved. */
2504 really_available_def (tree node)
2506 if (TREE_CODE (node) == EUSE_NODE
2507 && EUSE_PHIOP (node)
2508 && EUSE_INSERTED (node))
2510 if (TREE_CODE (node) == EUSE_NODE
2511 && EUSE_DEF (node) == NULL_TREE)
2517 /* Second part of the finalize step. Performs save bit setting, and
2518 ESSA minimization. */
2521 finalize_2 (struct expr_info *ei)
2525 insert_euse_in_preorder_dt_order (ei);
2526 /* Note which uses need to be saved to a temporary. */
2527 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2529 tree ref = VARRAY_TREE (ei->euses_dt_order, i);
2530 if (TREE_CODE (ref) == EUSE_NODE
2531 && !EUSE_PHIOP (ref)
2532 && EREF_RELOAD (ref))
2534 set_save (ei, EUSE_DEF (ref));
2538 /* ESSA Minimization. Determines which phis are identical to other
2539 phis, and not strictly necessary. */
2541 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2543 tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
2544 if (TREE_CODE (ephi) != EPHI_NODE)
2546 EPHI_IDENTITY (ephi) = true;
2547 EPHI_IDENTICAL_TO (ephi) = NULL;
2550 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2552 tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
2553 if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
2555 if (ephi_will_be_avail (ephi))
2558 for (k = 0; k < EPHI_NUM_ARGS (ephi); k++)
2560 if (EPHI_ARG_INJURED (ephi, k))
2561 require_phi (ei, EPHI_ARG_EDGE (ephi, k)->src);
2562 else if (EPHI_ARG_DEF (ephi, k)
2563 && TREE_CODE (EPHI_ARG_DEF (ephi, k)) == EUSE_NODE
2564 && really_available_def (EPHI_ARG_DEF (ephi, k)))
2565 require_phi (ei, bb_for_stmt (EPHI_ARG_DEF (ephi, k)));
2569 do_ephi_df_search (ei, replacing_search);
2572 /* Perform a DFS on EPHI using the functions in SEARCH. */
2575 do_ephi_df_search_1 (struct ephi_df_search search, tree ephi)
2579 search.set_seen (ephi);
2581 uses = EPHI_USES (ephi);
2584 for (i = 0; i < VARRAY_ACTIVE_SIZE (uses); i++)
2586 struct ephi_use_entry *use = VARRAY_GENERIC_PTR (uses, i);
2587 if (search.reach_from_to)
2588 search.reach_from_to (ephi, use->opnd_indx, use->phi);
2589 if (!search.seen (use->phi) &&
2590 search.continue_from_to (ephi, use->opnd_indx, use->phi))
2592 do_ephi_df_search_1 (search, use->phi);
2597 /* Perform a DFS on the EPHI's, using the functions in SEARCH. */
2600 do_ephi_df_search (struct expr_info *ei, struct ephi_df_search search)
2603 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2605 tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
2606 if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
2608 if (!search.seen (ephi)
2609 && search.start_from (ephi))
2610 do_ephi_df_search_1 (search, ephi);
2615 /* Calculate the increment necessary due to EXPR for the temporary. */
2617 calculate_increment (struct expr_info *ei, tree expr)
2621 /*XXX: Currently assume it's like a = a + 5, thus, this will give us the 5.
2623 incr = TREE_OPERAND (TREE_OPERAND (expr, 1), 1);
2624 if (TREE_CODE (incr) != INTEGER_CST)
2626 if (TREE_CODE (ei->expr) == MULT_EXPR)
2627 incr = fold (build (MULT_EXPR, TREE_TYPE (ei->expr),
2628 incr, TREE_OPERAND (ei->expr, 1)));
2629 #if DEBUGGING_STRRED
2632 fprintf (dump_file, "Increment calculated to be: ");
2633 print_generic_expr (dump_file, incr, 0);
2634 fprintf (dump_file, "\n");
2642 /* Perform an insertion of EXPR before/after USE, depending on the
2646 do_proper_save (tree use, tree expr, int before)
2648 basic_block bb = bb_for_stmt (use);
2649 block_stmt_iterator bsi;
2651 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2653 if (bsi_stmt (bsi) == use)
2656 bsi_insert_before (&bsi, expr, BSI_SAME_STMT);
2658 bsi_insert_after (&bsi, expr, BSI_SAME_STMT);
2665 /* Get the temporary for ESSA node USE.
2666 Takes into account minimized ESSA. */
2671 if (TREE_CODE (use) == EPHI_NODE && EPHI_IDENTITY (use))
2674 while (TREE_CODE (newuse) == EPHI_NODE
2675 && EPHI_IDENTITY (newuse))
2677 #ifdef ENABLE_CHECKING
2678 if (!EPHI_IDENTICAL_TO (newuse))
2681 newuse = EPHI_IDENTICAL_TO (newuse);
2682 if (TREE_CODE (newuse) != EPHI_NODE)
2685 if (TREE_CODE (EREF_TEMP (newuse)) == PHI_NODE)
2686 newtemp = PHI_RESULT (EREF_TEMP (newuse));
2688 newtemp = EREF_TEMP (newuse);
2692 if (TREE_CODE (EREF_TEMP (use)) == PHI_NODE)
2693 newtemp = PHI_RESULT (EREF_TEMP (use));
2695 newtemp = EREF_TEMP (use);
2700 /* Return the side of the statement that contains an SSA name. */
2703 pick_ssa_name (tree stmt)
2705 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
2706 return TREE_OPERAND (stmt, 0);
2707 else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
2708 return TREE_OPERAND (stmt, 1);
2713 /* Code motion step of SSAPRE. Take the save bits, and reload bits,
2714 and perform the saves and reloads. Also insert new phis where
2718 code_motion (struct expr_info *ei)
2723 tree temp = ei->temp;
2726 /* First, add the phi node temporaries so the reaching defs are
2729 euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
2733 use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
2734 if (TREE_CODE (use) != EPHI_NODE)
2736 if (ephi_will_be_avail (use) && !EPHI_IDENTITY (use))
2738 bb = bb_for_stmt (use);
2739 /* Add the new PHI node to the list of PHI nodes for block BB. */
2740 bb_ann (bb)->phi_nodes = chainon (phi_nodes (bb), EREF_TEMP (use));
2742 else if (EPHI_IDENTITY (use))
2744 if (dump_file && (dump_flags & TDF_DETAILS))
2746 fprintf (dump_file, "Pointless EPHI in block %d\n",
2747 bb_for_stmt (use)->index);
2751 /* Now do the actual saves and reloads, plus repairs. */
2753 euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
2756 use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
2757 #ifdef ENABLE_CHECKING
2758 if (TREE_CODE (use) == EUSE_NODE && EUSE_PHIOP (use)
2759 && (EREF_RELOAD (use) || EREF_SAVE (use)))
2762 if (EREF_SAVE (use) && !EUSE_INSERTED (use))
2767 basic_block usebb = bb_for_stmt (use);
2768 use_stmt = EREF_STMT (use);
2770 copy = TREE_OPERAND (use_stmt, 1);
2771 copy = unshare_expr (copy);
2772 newexpr = build (MODIFY_EXPR, TREE_TYPE (temp), temp, copy);
2773 newtemp = make_ssa_name (temp, newexpr);
2774 EREF_TEMP (use) = newtemp;
2775 TREE_OPERAND (newexpr, 0) = newtemp;
2776 TREE_OPERAND (use_stmt, 1) = newtemp;
2780 fprintf (dump_file, "In BB %d, insert save of ",
2782 print_generic_expr (dump_file, copy, dump_flags);
2783 fprintf (dump_file, " to ");
2784 print_generic_expr (dump_file, newtemp, dump_flags);
2785 fprintf (dump_file, " before statement ");
2786 print_generic_expr (dump_file, use_stmt, dump_flags);
2787 fprintf (dump_file, "\n");
2788 if (EXPR_HAS_LOCATION (use_stmt))
2789 fprintf (dump_file, " on line %d\n",
2790 EXPR_LINENO (use_stmt));
2792 modify_stmt (newexpr);
2793 modify_stmt (use_stmt);
2794 set_bb_for_stmt (newexpr, usebb);
2795 EREF_STMT (use) = do_proper_save (use_stmt, newexpr, true);
2798 else if (EREF_RELOAD (use))
2803 use_stmt = EREF_STMT (use);
2804 bb = bb_for_stmt (use_stmt);
2806 newtemp = get_temp (EUSE_DEF (use));
2811 fprintf (dump_file, "In BB %d, insert reload of ",
2813 print_generic_expr (dump_file,
2814 TREE_OPERAND (use_stmt, 1), 0);
2815 fprintf (dump_file, " from ");
2816 print_generic_expr (dump_file, newtemp, dump_flags);
2817 fprintf (dump_file, " in statement ");
2818 print_generic_stmt (dump_file, use_stmt, dump_flags);
2819 fprintf (dump_file, "\n");
2820 if (EXPR_HAS_LOCATION (use_stmt))
2821 fprintf (dump_file, " on line %d\n",
2822 EXPR_LINENO (use_stmt));
2824 TREE_OPERAND (use_stmt, 1) = newtemp;
2825 EREF_TEMP (use) = newtemp;
2826 modify_stmt (use_stmt);
2827 pre_stats.reloads++;
2831 /* Now do the phi nodes. */
2833 euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
2836 use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
2837 if (TREE_CODE (use) == EPHI_NODE
2838 && ephi_will_be_avail (use)
2839 && !EPHI_IDENTITY (use))
2843 bb = bb_for_stmt (use);
2847 "In BB %d, insert PHI to replace EPHI\n", bb->index);
2849 newtemp = EREF_TEMP (use);
2850 for (i = 0; i < EPHI_NUM_ARGS (use); i++)
2853 argdef = EPHI_ARG_DEF (use, i);
2855 rdef = get_temp (use);
2856 else if (EREF_RELOAD (argdef) || EREF_SAVE (argdef))
2857 rdef = get_temp (argdef);
2858 else if (TREE_CODE (argdef) == EPHI_NODE)
2859 rdef = get_temp (argdef);
2861 && EPHI_ARG_HAS_REAL_USE (use, i)
2862 && EREF_STMT (argdef)
2863 && !EPHI_ARG_INJURED (use, i))
2864 rdef = pick_ssa_name (EREF_STMT (argdef));
2870 add_phi_arg (&newtemp, rdef, EPHI_ARG_EDGE (use, i));
2873 /* Associate BB to the PHI node. */
2874 set_bb_for_stmt (EREF_TEMP (use), bb);
2875 pre_stats.newphis++;
2881 /* Compute the iterated dominance frontier of a statement. */
2884 compute_idfs (bitmap * dfs, tree stmt)
2887 sbitmap inworklist, done;
2892 block = bb_for_stmt (stmt);
2893 if (idfs_cache[block->index] != NULL)
2894 return idfs_cache[block->index];
2896 inworklist = sbitmap_alloc (last_basic_block);
2897 done = sbitmap_alloc (last_basic_block);
2898 worklist = fibheap_new ();
2899 sbitmap_zero (inworklist);
2900 sbitmap_zero (done);
2902 idf = BITMAP_XMALLOC ();
2905 block = bb_for_stmt (stmt);
2906 fibheap_insert (worklist, block->index, (void *)(size_t)block->index);
2907 SET_BIT (inworklist, block->index);
2909 while (!fibheap_empty (worklist))
2911 int a = (size_t) fibheap_extract_min (worklist);
2912 if (TEST_BIT (done, a))
2917 bitmap_a_or_b (idf, idf, idfs_cache[a]);
2918 EXECUTE_IF_SET_IN_BITMAP (idfs_cache[a], 0, i,
2920 SET_BIT (inworklist, i);
2926 bitmap_a_or_b (idf, idf, dfs[a]);
2927 EXECUTE_IF_SET_IN_BITMAP (dfs[a], 0, i,
2929 if (!TEST_BIT (inworklist, i))
2931 SET_BIT (inworklist, i);
2932 fibheap_insert (worklist, i, (void *)i);
2938 fibheap_delete (worklist);
2939 sbitmap_free (inworklist);
2940 sbitmap_free (done);
2941 idfs_cache[block->index] = idf;
2946 /* Return true if EXPR is a strength reduction candidate. */
2948 is_strred_cand (const tree expr ATTRIBUTE_UNUSED)
2951 if (TREE_CODE (TREE_OPERAND (expr, 1)) != MULT_EXPR
2952 && TREE_CODE (TREE_OPERAND (expr, 1)) != MINUS_EXPR
2953 && TREE_CODE (TREE_OPERAND (expr, 1)) != NEGATE_EXPR
2954 && TREE_CODE (TREE_OPERAND (expr, 1)) != PLUS_EXPR)
2963 /* Determine if two expressions are lexically equivalent. */
2966 expr_lexically_eq (const tree v1, const tree v2)
2968 if (TREE_CODE_CLASS (TREE_CODE (v1)) != TREE_CODE_CLASS (TREE_CODE (v2)))
2970 if (TREE_CODE (v1) != TREE_CODE (v2))
2972 switch (TREE_CODE_CLASS (TREE_CODE (v1)))
2976 return names_match_p (TREE_OPERAND (v1, 0), TREE_OPERAND (v2, 0));
2979 return names_match_p (v1, v2);
2983 match = names_match_p (TREE_OPERAND (v1, 0), TREE_OPERAND (v2, 0));
2986 match = names_match_p (TREE_OPERAND (v1, 1), TREE_OPERAND (v2, 1));
2997 /* Free an expression info structure. */
3000 free_expr_info (struct expr_info *v1)
3002 struct expr_info *e1 = (struct expr_info *)v1;
3003 VARRAY_FREE (e1->occurs);
3004 VARRAY_FREE (e1->kills);
3005 VARRAY_FREE (e1->lefts);
3006 VARRAY_FREE (e1->reals);
3007 VARRAY_FREE (e1->euses_dt_order);
3010 /* Process left occurrences and kills due to EXPR.
3011 A left occurrence occurs wherever a variable in an expression we
3012 are PRE'ing is stored to directly in a def, or indirectly because
3013 of a VDEF of an expression that we VUSE. */
3016 process_left_occs_and_kills (varray_type bexprs, tree expr)
3020 v_may_def_optype v_may_defs;
3021 v_must_def_optype v_must_defs;
3024 defs = STMT_DEF_OPS (expr);
3025 v_may_defs = STMT_V_MAY_DEF_OPS (expr);
3026 v_must_defs = STMT_V_MUST_DEF_OPS (expr);
3027 if (NUM_DEFS (defs) == 0
3028 && NUM_V_MAY_DEFS (v_may_defs) == 0
3029 && NUM_V_MUST_DEFS (v_must_defs) == 0)
3032 for (j = 0; j < VARRAY_ACTIVE_SIZE (bexprs); j++)
3034 struct expr_info *ei = VARRAY_GENERIC_PTR (bexprs, j);
3039 if (!ei->loadpre_cand)
3042 /* If we define the variable itself (IE a in *a, or a in a),
3043 it's a left occurrence. */
3044 for (i = 0; i < NUM_DEFS (defs); i++)
3046 if (names_match_p (DEF_OP (defs, i), ei->expr))
3048 if (TREE_CODE (expr) == ASM_EXPR)
3050 ei->loadpre_cand = false;
3053 VARRAY_PUSH_TREE (ei->lefts, expr);
3054 VARRAY_PUSH_TREE (ei->occurs, NULL);
3055 VARRAY_PUSH_TREE (ei->kills, NULL);
3059 /* If we virtually define the variable itself,
3060 it's a left occurrence. */
3061 for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
3063 if (names_match_p (V_MUST_DEF_OP (v_must_defs, i), ei->expr))
3065 if (TREE_CODE (expr) == ASM_EXPR)
3067 ei->loadpre_cand = false;
3070 VARRAY_PUSH_TREE (ei->lefts, expr);
3071 VARRAY_PUSH_TREE (ei->occurs, NULL);
3072 VARRAY_PUSH_TREE (ei->kills, NULL);
3076 /* If we V_MAY_DEF the VUSE of the expression, it's also a left
3078 random_occur = VARRAY_TREE (ei->occurs, 0);
3079 ann = stmt_ann (random_occur);
3080 vuses = VUSE_OPS (ann);
3081 if (NUM_V_MAY_DEFS (v_may_defs) != 0)
3083 for (k = 0; k < NUM_VUSES (vuses); k++)
3085 vuse_name = VUSE_OP (vuses, k);
3086 for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
3088 if (names_match_p (V_MAY_DEF_OP (v_may_defs, i), vuse_name))
3090 VARRAY_PUSH_TREE (ei->lefts, expr);
3091 VARRAY_PUSH_TREE (ei->occurs, NULL);
3092 VARRAY_PUSH_TREE (ei->kills, NULL);
3100 /* Perform SSAPRE on an expression. */
3103 pre_expression (struct expr_info *slot, void *data, bitmap vars_to_rename)
3105 struct expr_info *ei = (struct expr_info *) slot;
3109 eref_id_counter = 0;
3111 /* If we don't have two occurrences along any dominated path, and
3112 it's not load PRE, this is a waste of time. */
3114 if (VARRAY_ACTIVE_SIZE (ei->reals) < 2)
3117 memset (&pre_stats, 0, sizeof (struct pre_stats_d));
3119 ei->temp = create_tmp_var (TREE_TYPE (ei->expr), "pretmp");
3120 add_referenced_tmp_var (ei->temp);
3122 bitmap_clear (created_phi_preds);
3123 ephi_pindex_htab = htab_create (500, ephi_pindex_hash, ephi_pindex_eq, free);
3124 phi_pred_cache = xcalloc (last_basic_block, sizeof (tree));
3125 n_phi_preds = last_basic_block;
3127 if (!expr_phi_insertion ((bitmap *)data, ei))
3130 if (dump_file && (dump_flags & TDF_DETAILS))
3133 fprintf (dump_file, "Occurrences for expression ");
3134 print_generic_expr (dump_file, ei->expr, dump_flags);
3135 fprintf (dump_file, " after Rename 2\n");
3136 for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
3138 print_generic_expr (dump_file,
3139 VARRAY_TREE (ei->euses_dt_order, i), 1);
3140 fprintf (dump_file, "\n");
3143 compute_down_safety (ei);
3144 compute_du_info (ei);
3145 compute_will_be_avail (ei);
3147 if (dump_file && (dump_flags & TDF_DETAILS))
3149 fprintf (dump_file, "EPHI's for expression ");
3150 print_generic_expr (dump_file, ei->expr, dump_flags);
3152 " after down safety and will_be_avail computation\n");
3155 tree ephi = ephi_at_block (bb);
3158 print_generic_expr (dump_file, ephi, 1);
3159 fprintf (dump_file, "\n");
3164 if (finalize_1 (ei))
3168 if (ei->loadpre_cand)
3169 bitmap_set_bit (vars_to_rename, var_ann (ei->temp)->uid);
3172 clear_all_eref_arrays ();
3174 if (dump_flags & TDF_STATS)
3176 fprintf (dump_file, "PRE stats:\n");
3177 fprintf (dump_file, "Reloads:%d\n", pre_stats.reloads);
3178 fprintf (dump_file, "Saves:%d\n", pre_stats.saves);
3179 fprintf (dump_file, "Repairs:%d\n", pre_stats.repairs);
3180 fprintf (dump_file, "New phis:%d\n", pre_stats.newphis);
3181 fprintf (dump_file, "EPHI memory allocated:%d\n",
3182 pre_stats.ephi_allocated);
3183 fprintf (dump_file, "EREF memory allocated:%d\n",
3184 pre_stats.eref_allocated);
3185 fprintf (dump_file, "Expressions generated for rename2:%d\n",
3186 pre_stats.exprs_generated);
3189 free (phi_pred_cache);
3190 if (ephi_pindex_htab)
3192 htab_delete (ephi_pindex_htab);
3193 ephi_pindex_htab = NULL;
3201 /* Step 1 - Collect the expressions to perform PRE on. */
3204 collect_expressions (basic_block block, varray_type *bexprsp)
3207 block_stmt_iterator j;
3210 varray_type bexprs = *bexprsp;
3212 for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
3214 tree stmt = bsi_stmt (j);
3216 tree orig_expr = expr;
3218 struct expr_info *slot = NULL;
3220 get_stmt_operands (expr);
3221 ann = stmt_ann (expr);
3223 if (NUM_USES (USE_OPS (ann)) == 0)
3225 process_left_occs_and_kills (bexprs, expr);
3229 if (TREE_CODE (expr) == MODIFY_EXPR)
3230 expr = TREE_OPERAND (expr, 1);
3231 if ((TREE_CODE_CLASS (TREE_CODE (expr)) == '2'
3232 || TREE_CODE_CLASS (TREE_CODE (expr)) == '<'
3233 /*|| TREE_CODE_CLASS (TREE_CODE (expr)) == '1'*/
3234 || TREE_CODE (expr) == SSA_NAME
3235 || TREE_CODE (expr) == INDIRECT_REF)
3236 && !ann->makes_aliased_stores
3237 && !ann->has_volatile_ops)
3239 bool is_scalar = true;
3240 tree origop0 = TREE_OPERAND (orig_expr, 0);
3242 if (AGGREGATE_TYPE_P (TREE_TYPE (origop0))
3243 || TREE_CODE (TREE_TYPE (origop0)) == COMPLEX_TYPE)
3247 && (TREE_CODE (expr) == SSA_NAME
3248 || (TREE_CODE (expr) == INDIRECT_REF
3249 && !DECL_P (TREE_OPERAND (expr, 0)))
3250 ||(!DECL_P (TREE_OPERAND (expr, 0))
3251 && (!TREE_OPERAND (expr, 1)
3252 || !DECL_P (TREE_OPERAND (expr, 1))))))
3254 for (k = 0; k < VARRAY_ACTIVE_SIZE (bexprs); k++)
3256 slot = VARRAY_GENERIC_PTR (bexprs, k);
3257 if (expr_lexically_eq (slot->expr, expr))
3260 if (k >= VARRAY_ACTIVE_SIZE (bexprs))
3264 VARRAY_PUSH_TREE (slot->occurs, orig_expr);
3265 VARRAY_PUSH_TREE (slot->kills, NULL);
3266 VARRAY_PUSH_TREE (slot->lefts, NULL);
3267 VARRAY_PUSH_TREE (slot->reals, stmt);
3268 slot->strred_cand &= is_strred_cand (orig_expr);
3272 slot = ggc_alloc (sizeof (struct expr_info));
3274 VARRAY_GENERIC_PTR_NOGC_INIT (slot->occurs, 1, "Occurrence");
3275 VARRAY_GENERIC_PTR_NOGC_INIT (slot->kills, 1, "Kills");
3276 VARRAY_GENERIC_PTR_NOGC_INIT (slot->lefts, 1, "Left occurrences");
3277 VARRAY_GENERIC_PTR_NOGC_INIT (slot->reals, 1, "Real occurrences");
3278 VARRAY_GENERIC_PTR_NOGC_INIT (slot->euses_dt_order, 1, "EUSEs");
3280 VARRAY_PUSH_TREE (slot->occurs, orig_expr);
3281 VARRAY_PUSH_TREE (slot->kills, NULL);
3282 VARRAY_PUSH_TREE (slot->lefts, NULL);
3283 VARRAY_PUSH_TREE (slot->reals, stmt);
3284 VARRAY_PUSH_GENERIC_PTR (bexprs, slot);
3285 slot->strred_cand = is_strred_cand (orig_expr);
3286 slot->loadpre_cand = false;
3287 if (TREE_CODE (expr) == SSA_NAME
3288 || TREE_CODE (expr) == INDIRECT_REF)
3289 slot->loadpre_cand = true;
3293 process_left_occs_and_kills (bexprs, orig_expr);
3297 for (son = first_dom_son (CDI_DOMINATORS, block);
3299 son = next_dom_son (CDI_DOMINATORS, son))
3300 collect_expressions (son, bexprsp);
3303 /* Main entry point to the SSA-PRE pass.
3305 PHASE indicates which dump file from the DUMP_FILES array to use when
3306 dumping debugging information. */
3316 if (ENTRY_BLOCK_PTR->succ->dest->pred->pred_next)
3317 if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_ABNORMAL))
3318 split_edge (ENTRY_BLOCK_PTR->succ);
3320 euse_node_pool = create_alloc_pool ("EUSE node pool",
3321 sizeof (struct tree_euse_node), 30);
3322 eref_node_pool = create_alloc_pool ("EREF node pool",
3323 sizeof (struct tree_eref_common), 30);
3324 ephi_use_pool = create_alloc_pool ("EPHI use node pool",
3325 sizeof (struct ephi_use_entry), 30);
3326 VARRAY_GENERIC_PTR_INIT (bexprs, 1, "bexprs");
3327 /* Compute immediate dominators. */
3328 calculate_dominance_info (CDI_DOMINATORS);
3330 /* DCE screws the dom_children up, without bothering to fix it. So fix it. */
3331 currbbs = n_basic_blocks;
3332 dfn = xcalloc (last_basic_block + 1, sizeof (int));
3333 build_dfn_array (ENTRY_BLOCK_PTR, 0);
3335 /* Initialize IDFS cache. */
3336 idfs_cache = xcalloc (currbbs, sizeof (bitmap));
3338 /* Compute dominance frontiers. */
3339 pre_dfs = (bitmap *) xmalloc (sizeof (bitmap) * currbbs);
3340 for (i = 0; i < currbbs; i++)
3341 pre_dfs[i] = BITMAP_XMALLOC ();
3342 compute_dominance_frontiers (pre_dfs);
3344 created_phi_preds = BITMAP_XMALLOC ();
3346 collect_expressions (ENTRY_BLOCK_PTR, &bexprs);
3348 ggc_push_context ();
3350 for (k = 0; k < VARRAY_ACTIVE_SIZE (bexprs); k++)
3352 pre_expression (VARRAY_GENERIC_PTR (bexprs, k), pre_dfs, vars_to_rename);
3353 free_alloc_pool (euse_node_pool);
3354 free_alloc_pool (eref_node_pool);
3355 free_alloc_pool (ephi_use_pool);
3356 euse_node_pool = create_alloc_pool ("EUSE node pool",
3357 sizeof (struct tree_euse_node), 30);
3358 eref_node_pool = create_alloc_pool ("EREF node pool",
3359 sizeof (struct tree_eref_common), 30);
3360 ephi_use_pool = create_alloc_pool ("EPHI use node pool",
3361 sizeof (struct ephi_use_entry), 30);
3362 free_expr_info (VARRAY_GENERIC_PTR (bexprs, k));
3363 #ifdef ENABLE_CHECKING
3364 if (pre_stats.ephis_current != 0)
3372 /* Clean up after PRE. */
3373 memset (&pre_stats, 0, sizeof (struct pre_stats_d));
3374 free_alloc_pool (euse_node_pool);
3375 free_alloc_pool (eref_node_pool);
3376 free_alloc_pool (ephi_use_pool);
3377 VARRAY_CLEAR (bexprs);
3378 for (i = 0; i < currbbs; i++)
3379 BITMAP_XFREE (pre_dfs[i]);
3381 BITMAP_XFREE (created_phi_preds);
3382 for (i = 0; i < currbbs; i++)
3383 if (idfs_cache[i] != NULL)
3384 BITMAP_XFREE (idfs_cache[i]);
3393 return flag_tree_pre != 0;
3396 struct tree_opt_pass pass_pre =
3399 gate_pre, /* gate */
3400 execute_pre, /* execute */
3403 0, /* static_pass_number */
3404 TV_TREE_PRE, /* tv_id */
3405 PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
3406 0, /* properties_provided */
3407 0, /* properties_destroyed */
3408 0, /* todo_flags_start */
3409 TODO_dump_func | TODO_rename_vars
3410 | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */