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_vdefs (stmt_copy
);
1318 if (pred
->index
< n_phi_preds
)
1319 phi_pred_cache
[pred
->index
] = stmt_copy
;
1323 /* Determine if def and use_tree should have the same e-version. We do
1324 this by simply determining if something modifies the expression
1325 between DEF and USE_TREE. USE_TREE was generated from the OPND_NUM'th
1326 operand of the EPHI in USE_BB. If it is modified, we determine if
1327 it is simply injured, and thus, okay. */
1330 same_e_version_real_occ_phi_opnd (struct expr_info
*ei
, tree def
,
1331 basic_block use_bb
, int opnd_num
,
1332 tree use_tree
, bool *injured
)
1334 bool not_mod
= true;
1337 if (load_modified_real_occ_real_occ (EREF_STMT (def
),
1343 else if (ei
->strred_cand
)
1345 if (injured_real_occ_phi_opnd (ei
, def
, use_bb
, opnd_num
))
1351 /* Determine whether the OPND_NUM'th operand of USE_BB's EPHI is an
1352 injured version of DEF. */
1354 injured_real_occ_phi_opnd (struct expr_info
*ei ATTRIBUTE_UNUSED
,
1355 tree def ATTRIBUTE_UNUSED
,
1356 basic_block use_bb ATTRIBUTE_UNUSED
,
1357 int opnd_num ATTRIBUTE_UNUSED
)
1359 /* XXX: Implement. */
1363 /* Determine whether the expression is modified between DEF and USE,
1364 by comparing the hash values of the two expressions. */
1366 load_modified_real_occ_real_occ (tree def
, tree use
)
1373 if (TREE_CODE (def
) == VA_ARG_EXPR
)
1374 expr1val
= iterative_hash_expr (def
, 0);
1376 expr1val
= iterative_hash_expr (TREE_OPERAND (def
, 1), 0);
1378 if (TREE_CODE (use
) == VA_ARG_EXPR
)
1379 expr2val
= iterative_hash_expr (use
, 0);
1381 expr2val
= iterative_hash_expr (TREE_OPERAND (use
, 1), 0);
1383 if (expr1val
== expr2val
)
1385 vuses
= STMT_VUSE_OPS (def
);
1386 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
1387 expr1val
= iterative_hash_expr (VUSE_OP (vuses
, i
), expr1val
);
1388 vuses
= STMT_VUSE_OPS (use
);
1389 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
1390 expr2val
= iterative_hash_expr (VUSE_OP (vuses
, i
), expr2val
);
1391 if (expr1val
!= expr2val
)
1394 return expr1val
!= expr2val
;
1397 /* Determine if the expression is modified between the start of BB,
1398 and the use at USE, ignoring phis. We do this by simple
1399 domination, because of the properties of SSA. */
1401 load_modified_phi_result (basic_block bb
, tree use
)
1403 basic_block defbb
= bb_for_stmt (SSA_NAME_DEF_STMT (use
));
1406 /* This guards against moving around undefined variables.
1407 However, PARM_DECL is special because it *IS* live on entry,
1408 so it's not really undefined. */
1409 if (!defbb
&& TREE_CODE (SSA_NAME_VAR (use
)) != PARM_DECL
)
1411 else if (!defbb
&& TREE_CODE (SSA_NAME_VAR (use
)) == PARM_DECL
)
1413 if (dominated_by_p (CDI_DOMINATORS
, bb
, defbb
))
1418 if (TREE_CODE (SSA_NAME_DEF_STMT (use
)) == PHI_NODE
)
1424 /* Determine if the variables in EXP are modified between DEF and
1425 USE. If they are, we have to give a new e-version to the result.
1426 For load PRE, we have to check the vuses too. For strength
1427 reduction, we need to check whether the modification is a simple
1431 same_e_version_phi_result (struct expr_info
*ei
, tree def
, tree exp
,
1434 stmt_ann_t ann
= stmt_ann (exp
);
1435 bool not_mod
= true;
1437 use_optype real_expuses
= USE_OPS (ann
);
1438 vuse_optype expuses
;
1441 if (NUM_USES (real_expuses
) == 0)
1444 for (i
= 0; i
< NUM_USES (real_expuses
) && not_mod
; i
++)
1446 tree
*use1p
= USE_OP_PTR (real_expuses
, i
);
1451 if (load_modified_phi_result (bb_for_stmt (def
), use1
))
1455 if (not_mod
&& ei
->loadpre_cand
)
1457 expuses
= VUSE_OPS (ann
);
1459 for (i
= 0; i
< NUM_VUSES (expuses
) && not_mod
; i
++)
1461 tree use1
= VUSE_OP (expuses
, i
);
1462 if (load_modified_phi_result (bb_for_stmt (def
), use1
))
1469 else if (ei
->strred_cand
)
1471 if (injured_phi_result_real_occ (ei
, def
, exp
, bb_for_stmt (use
)))
1473 EREF_INJURED (use
) = true;
1481 /* Determine whether USE_TREE is an injured version of DEF. */
1484 injured_phi_result_real_occ (struct expr_info
*ei ATTRIBUTE_UNUSED
,
1485 tree def ATTRIBUTE_UNUSED
,
1486 tree use_tree ATTRIBUTE_UNUSED
,
1487 basic_block use_bb ATTRIBUTE_UNUSED
)
1489 /* XXX: Implement. */
1493 /* Delayed renaming checks to make sure the optimistic assumptions
1494 about ephi operand versions in rename_1 actually turned out to be
1495 true. This requires generating the expressions for each ephi
1496 operand, and comparing them to the versions of the occurrence it is
1498 Delayed rename handling is done like open64 does it. Basically,
1499 like the delayed renaming is described in the paper, with
1500 extensions for strength reduction. */
1503 process_delayed_rename (struct expr_info
*ei
, tree use
, tree real_occ
)
1508 /* We only care about operands we actually have DELAYED_RENAME set
1510 for (opnd_num
= 0; opnd_num
< EPHI_NUM_ARGS (exp_phi
); opnd_num
++)
1512 tree opnd
= EPHI_ARG_DEF (exp_phi
, opnd_num
);
1513 if (EPHI_ARG_DELAYED_RENAME (exp_phi
, opnd_num
))
1518 /* Mark it as being processed, then generate the ephi
1519 operand expression. */
1520 EPHI_ARG_DELAYED_RENAME (exp_phi
, opnd_num
) = false;
1522 newexp
= subst_phis (ei
, real_occ
,
1523 EPHI_ARG_EDGE (exp_phi
, opnd_num
)->src
,
1524 bb_for_stmt (exp_phi
));
1526 /* For operands defined by EPHIs, we need to compare the
1527 generated expression and the phi result.
1528 For operands defined by real occurrences, we simply compare
1529 the phi operand and the real occurrence. */
1530 if (TREE_CODE (def
) == EPHI_NODE
)
1532 tree tmp_use
= EPHI_ARG_PRED (exp_phi
, opnd_num
);
1533 EREF_STMT (tmp_use
) = newexp
;
1534 if (same_e_version_phi_result (ei
, def
, newexp
,
1538 if (EREF_INJURED (tmp_use
))
1540 EREF_INJURED (tmp_use
) = false;
1541 EPHI_ARG_INJURED (exp_phi
, opnd_num
) = true;
1543 if (EREF_STMT (def
) == NULL
)
1545 /* If it was injured, we need to make up a new
1546 phi result with the actually injured
1548 if (EPHI_ARG_INJURED (exp_phi
, opnd_num
))
1550 /* XXX: Allocate phi result with correct version. */
1553 EREF_STMT (def
) = newexp
;
1554 process_delayed_rename (ei
, def
, newexp
);
1557 /* If it's not the same version, the defining ephi can't
1558 be downsafe, and the operand is not really defined by
1562 EPHI_DOWNSAFE (def
) = false;
1563 EPHI_ARG_DEF (exp_phi
, opnd_num
) = NULL
;
1566 else if (TREE_CODE (def
) == EUSE_NODE
&& !EUSE_PHIOP (def
))
1568 bool injured
= false;
1569 if (same_e_version_real_occ_phi_opnd (ei
, def
,
1571 opnd_num
, newexp
, &injured
))
1573 tree tmp_use
= EPHI_ARG_PRED (exp_phi
, opnd_num
);
1574 EPHI_ARG_HAS_REAL_USE (exp_phi
, opnd_num
) = true;
1575 /* EREF_STMT (opnd) = EREF_STMT (def); */
1576 if (injured
|| EREF_INJURED (def
))
1577 EREF_INJURED (def
) = true;
1578 if (injured
|| EREF_INJURED (def
))
1579 EREF_INJURED (opnd
) = true;
1581 EREF_STMT (tmp_use
) = EREF_STMT (def
);
1582 if (EUSE_DEF (def
) != NULL
)
1583 EPHI_ARG_DEF (exp_phi
, opnd_num
) = EUSE_DEF (def
);
1585 EPHI_ARG_DEF (exp_phi
, opnd_num
) = def
;
1589 EPHI_ARG_DEF (exp_phi
, opnd_num
) = NULL
;
1596 /* For the uninitiated, the algorithm is a modified SSA renaming
1597 algorithm (working on expressions rather than variables) . We
1598 attempt to determine which expression occurrences have the same
1599 ESSA version (we call it class, for equivalence/redunancy class,
1600 which is what the papers call it. Open64 calls it e-version), and
1601 which occurrences are actually operands for an EPHI (since this has
1602 to be discovered from the program).
1604 Renaming is done like Open64 does it. Basically as the paper says,
1605 except that we try to use earlier defined occurrences if they are
1606 available in order to keep the number of saves down. */
1609 rename_1 (struct expr_info
*ei
)
1616 VARRAY_GENERIC_PTR_NOGC_INIT (stack
, 1, "Stack for renaming");
1618 /* Start by creating and inserting the occurrences in preorder,
1619 dominator tree into a list. */
1620 create_and_insert_occ_in_preorder_dt_order (ei
);
1622 /* Walk the occurrences. */
1623 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
1625 occur
= VARRAY_TREE (ei
->euses_dt_order
, i
);
1627 /* The current occurrence can't have the same version as
1628 something on the top of the stack unless it is in a basic
1629 block dominated by the basic block of the occurrence on the
1630 top of the stack. */
1631 while (VARRAY_ACTIVE_SIZE (stack
) > 0
1632 && !dominated_by_p (CDI_DOMINATORS
,
1633 bb_for_stmt (occur
),
1634 bb_for_stmt (VARRAY_TOP_TREE (stack
))))
1638 /* If the stack is empty, we assign a new version since it isn't
1639 dominated by any other version. */
1640 if (VARRAY_ACTIVE_SIZE (stack
) == 0 || VARRAY_TOP_TREE (stack
) == NULL
)
1642 if (TREE_CODE (occur
) == EPHI_NODE
)
1643 assign_new_class (occur
, &stack
, NULL
);
1644 else if (TREE_CODE (occur
) == EUSE_NODE
&& !EUSE_PHIOP (occur
))
1645 assign_new_class (occur
, &stack
, NULL
);
1649 if (TREE_CODE (occur
) == EUSE_NODE
&& !EUSE_PHIOP (occur
))
1651 tree tos
= VARRAY_TOP_TREE (stack
);
1653 if (TREE_CODE (tos
) == EUSE_NODE
&& !EUSE_PHIOP (tos
))
1655 /* If two real occurrences have the same
1656 e-version/class, then this occurrence can be
1657 defined by the prior occurrence (or whatever
1658 the prior occurrence is defined by, if
1660 Otherwise, we have to assign a new version.
1661 lvalue occurrences always need a new version,
1662 since they are definitions. */
1663 if (!EUSE_LVAL (occur
)
1664 && same_e_version_real_occ_real_occ (ei
, tos
, occur
))
1669 EREF_CLASS (occur
) = EREF_CLASS (tos
);
1670 newdef
= EUSE_DEF (tos
) != NULL
? EUSE_DEF (tos
) : tos
;
1671 EUSE_DEF (occur
) = newdef
;
1674 assign_new_class (occur
, &stack
, NULL
);
1676 else if (TREE_CODE (tos
) == EPHI_NODE
)
1678 /* Here we have an ephi occurrence at the top of the
1679 stack, and the current occurrence is a real
1680 occurrence. So determine if the real occurrence
1681 has the same version as the result of the phi.
1682 If so, then this real occurrence is defined by the
1683 EPHI at the top of the stack.
1684 If not, the EPHI isn't downsafe (because something
1685 must change in between the ephi result and the next
1686 occurrence), and we need a new version for the real
1688 lvalues always need a new version. */
1689 if (!EUSE_LVAL (occur
)
1690 && same_e_version_phi_result (ei
, tos
, EREF_STMT (occur
),
1693 EREF_CLASS (occur
) = EREF_CLASS (tos
);
1694 EUSE_DEF (occur
) = tos
;
1695 EREF_STMT (tos
) = EREF_STMT (occur
);
1697 VARRAY_PUSH_TREE (stack
, occur
);
1701 EPHI_DOWNSAFE (tos
) = false;
1702 assign_new_class (occur
, &stack
, NULL
);
1706 /* EPHI occurrences always get new versions. */
1707 else if (TREE_CODE (occur
) == EPHI_NODE
)
1709 assign_new_class (occur
, &stack
, NULL
);
1711 /* EPHI operands are optimistcally assumed to be whatever is
1712 at the top of the stack at the time we hit the ephi
1713 operand occurrence. The delayed renaming checks this
1714 optimistic assumption for validity. */
1715 else if (TREE_CODE (occur
) == EUSE_NODE
&& EUSE_PHIOP (occur
))
1717 basic_block pred_bb
= bb_for_stmt (occur
);
1719 tree tos
= VARRAY_TOP_TREE (stack
);
1720 for (e
= pred_bb
->succ
; e
; e
= e
->succ_next
)
1722 tree ephi
= ephi_at_block (e
->dest
);
1723 if (ephi
!= NULL_TREE
)
1725 int opnum
= opnum_of_ephi (ephi
, e
);
1727 EPHI_ARG_DELAYED_RENAME (ephi
, opnum
) = true;
1728 EPHI_ARG_DEF (ephi
, opnum
) = tos
;
1732 /* No EPHI can be downsafe past an exit node. */
1733 else if (TREE_CODE (occur
) == EEXIT_NODE
)
1735 if (VARRAY_ACTIVE_SIZE (stack
) > 0
1736 && TREE_CODE (VARRAY_TOP_TREE (stack
)) == EPHI_NODE
)
1737 EPHI_DOWNSAFE (VARRAY_TOP_TREE (stack
)) = false;
1741 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1744 fprintf (dump_file
, "Occurrences for expression ");
1745 print_generic_expr (dump_file
, ei
->expr
, dump_flags
);
1746 fprintf (dump_file
, " after Rename 1\n");
1747 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
1749 print_generic_expr (dump_file
,
1750 VARRAY_TREE (ei
->euses_dt_order
, i
), 1);
1751 fprintf (dump_file
, "\n");
1755 /* Now process the renames for EPHI's that actually have the result
1756 valid and used. These will be the EPHI's that have the statement
1758 FOR_EACH_BB (phi_bb
)
1760 tree ephi
= ephi_at_block (phi_bb
);
1761 if (ephi
!= NULL
&& EREF_STMT (ephi
) != NULL
)
1762 process_delayed_rename (ei
, ephi
, EREF_STMT (ephi
));
1765 /* If we didn't process the delayed rename for an ephi argument,
1766 but thought we needed to, mark the operand as NULL. Also, if the
1767 operand was defined by an EPHI, we can mark it not downsafe
1768 because there can't have been a real occurrence (or else we would
1769 have processed a rename for it). */
1770 FOR_EACH_BB (phi_bb
)
1772 tree ephi
= ephi_at_block (phi_bb
);
1776 for (j
= 0; j
< EPHI_NUM_ARGS (ephi
); j
++)
1778 if (EPHI_ARG_DELAYED_RENAME (ephi
, j
))
1780 tree def
= EPHI_ARG_DEF (ephi
, j
);
1781 if (def
&& TREE_CODE (def
) == EPHI_NODE
)
1782 EPHI_DOWNSAFE (def
) = false;
1783 EPHI_ARG_DEF (ephi
, j
) = NULL
;
1788 VARRAY_FREE (stack
);
1791 /* Determine if the EPHI has an argument we could never insert
1792 or extend the lifetime of, such as an argument occurring on
1793 an abnormal edge. */
1796 ephi_has_unsafe_arg (tree ephi
)
1799 for (i
= 0; i
< EPHI_NUM_ARGS (ephi
); i
++)
1800 if (EPHI_ARG_EDGE (ephi
, i
)->flags
& EDGE_ABNORMAL
)
1805 /* Reset down safety flags for non-downsafe ephis. Uses depth first
1809 reset_down_safe (tree currphi
, int opnum
)
1814 if (EPHI_ARG_HAS_REAL_USE (currphi
, opnum
))
1816 ephi
= EPHI_ARG_DEF (currphi
, opnum
);
1817 if (!ephi
|| TREE_CODE (ephi
) != EPHI_NODE
)
1819 if (!EPHI_DOWNSAFE (ephi
))
1821 EPHI_DOWNSAFE (ephi
) = false;
1822 for (i
= 0; i
< EPHI_NUM_ARGS (ephi
); i
++)
1823 reset_down_safe (ephi
, i
);
1826 /* Compute down_safety using a depth first search.
1827 This propagates not fully anticipated phi assignments upwards. */
1830 compute_down_safety (struct expr_info
*ei
)
1836 tree ephi
= ephi_at_block (bb
);
1837 if (ephi
== NULL_TREE
)
1839 if (ephi_has_unsafe_arg (ephi
))
1840 EPHI_DOWNSAFE (ephi
) = false;
1842 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
1845 tree ephi
= VARRAY_TREE (ei
->euses_dt_order
, i
);
1846 if (TREE_CODE (ephi
) != EPHI_NODE
)
1849 if (!EPHI_DOWNSAFE (ephi
))
1850 for (j
= 0; j
< EPHI_NUM_ARGS (ephi
); j
++)
1851 reset_down_safe (ephi
, j
);
1856 /* EPHI use node pool. We allocate ephi_use_node's out of this. */
1857 static alloc_pool ephi_use_pool
;
1859 /* Add a use of DEF to it's use list. The use is at operand OPND_INDX
1863 add_ephi_use (tree def
, tree use
, int opnd_indx
)
1865 struct ephi_use_entry
*entry
;
1866 if (EPHI_USES (def
) == NULL
)
1867 VARRAY_GENERIC_PTR_INIT (EPHI_USES (def
), 1, "EPHI uses");
1868 entry
= (struct ephi_use_entry
*) pool_alloc (ephi_use_pool
);
1870 entry
->opnd_indx
= opnd_indx
;
1871 VARRAY_PUSH_GENERIC_PTR (EPHI_USES (def
), entry
);
1874 /* Compute def-uses of ephis. */
1877 compute_du_info (struct expr_info
*ei
)
1880 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
1883 tree ephi
= VARRAY_TREE (ei
->euses_dt_order
, i
);
1884 if (TREE_CODE (ephi
) != EPHI_NODE
)
1886 for (j
= 0; j
< EPHI_NUM_ARGS (ephi
); j
++)
1888 tree def
= EPHI_ARG_DEF (ephi
, j
);
1889 if (def
!= NULL_TREE
)
1891 if (TREE_CODE (def
) == EPHI_NODE
)
1892 add_ephi_use (def
, ephi
, j
);
1893 #ifdef ENABLE_CHECKING
1895 if (! (TREE_CODE (def
) == EUSE_NODE
&& !EUSE_PHIOP (def
)))
1903 /* STOPS marks what EPHI's/operands stop forward movement. (IE where
1904 we can't insert past). */
1907 compute_stops (struct expr_info
*ei
)
1911 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
1913 tree ephi
= VARRAY_TREE (ei
->euses_dt_order
, i
);
1916 if (TREE_CODE (ephi
) != EPHI_NODE
)
1918 if (EPHI_CANT_BE_AVAIL (ephi
))
1919 EPHI_STOPS (ephi
) = true;
1920 for (j
= 0; j
< EPHI_NUM_ARGS (ephi
); j
++)
1921 if (EPHI_ARG_HAS_REAL_USE (ephi
, j
))
1922 EPHI_ARG_STOPS (ephi
, j
) = true;
1924 do_ephi_df_search (ei
, stops_search
);
1927 /* Compute will_be_avail property, which consists of cant_be_avail and
1928 stops properties. */
1931 compute_will_be_avail (struct expr_info
*ei
)
1933 do_ephi_df_search (ei
, cant_be_avail_search
);
1937 /* Insert the expressions into ei->euses_dt_order in preorder dt order. */
1940 insert_euse_in_preorder_dt_order (struct expr_info
*ei
)
1942 varray_type new_euses_dt_order
;
1944 VARRAY_GENERIC_PTR_NOGC_INIT (new_euses_dt_order
, 1, "EUSEs");
1946 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
1948 tree ref
= VARRAY_TREE (ei
->euses_dt_order
, i
);
1949 if (TREE_CODE (ref
) == EUSE_NODE
|| TREE_CODE (ref
) == EPHI_NODE
)
1950 VARRAY_PUSH_TREE (new_euses_dt_order
, ref
);
1952 VARRAY_FREE (ei
->euses_dt_order
);
1953 ei
->euses_dt_order
= new_euses_dt_order
;
1954 qsort (ei
->euses_dt_order
->data
.tree
,
1955 VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
),
1961 /* Determine if we can insert operand OPND_INDX of EPHI. */
1964 can_insert (tree ephi
, int opnd_indx
)
1968 if (EPHI_ARG_DEF (ephi
, opnd_indx
) == NULL_TREE
)
1970 def
= EPHI_ARG_DEF (ephi
, opnd_indx
);
1971 if (!EPHI_ARG_HAS_REAL_USE (ephi
, opnd_indx
))
1972 if (TREE_CODE (def
) == EPHI_NODE
&& !(ephi_will_be_avail (def
)))
1977 /* Find the default definition of VAR.
1978 This is incredibly ugly, since we have to walk back through all
1979 the definitions to find the one defined by the empty statement. */
1982 get_default_def (tree var
, htab_t seen
)
1986 tree defstmt
= SSA_NAME_DEF_STMT (var
);
1988 if (IS_EMPTY_STMT (defstmt
))
1990 *(htab_find_slot (seen
, var
, INSERT
)) = var
;
1991 if (TREE_CODE (defstmt
) == PHI_NODE
)
1994 for (j
= 0; j
< PHI_NUM_ARGS (defstmt
); j
++)
1995 if (htab_find (seen
, PHI_ARG_DEF (defstmt
, j
)) == NULL
)
1997 if (TREE_CODE (PHI_ARG_DEF (defstmt
, j
)) == SSA_NAME
)
1999 tree temp
= get_default_def (PHI_ARG_DEF (defstmt
, j
), seen
);
2000 if (temp
!= NULL_TREE
)
2007 defs
= STMT_DEF_OPS (defstmt
);
2008 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
2010 tree def
= DEF_OP (defs
, i
);
2011 if (SSA_NAME_VAR (def
) == SSA_NAME_VAR (var
))
2013 if (htab_find (seen
, def
) != NULL
)
2015 return get_default_def (def
, seen
);
2019 /* We should never get here. */
2023 /* Hunt down the right reaching def for VAR, starting with BB. Ignore
2024 defs in statement IGNORE, and stop if we hit CURRSTMT. */
2027 reaching_def (tree var
, tree currstmt
, basic_block bb
, tree ignore
)
2029 tree curruse
= NULL_TREE
;
2030 block_stmt_iterator bsi
;
2034 /* Check phis first. */
2035 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
2037 if (phi
== currstmt
)
2041 if (names_match_p (var
, PHI_RESULT (phi
)))
2042 curruse
= PHI_RESULT (phi
);
2045 /* We can't walk BB's backwards right now, so we have to walk *all*
2046 the statements, and choose the last name we find. */
2047 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2049 tree stmt
= bsi_stmt (bsi
);
2054 if (stmt
== currstmt
)
2057 get_stmt_operands (stmt
);
2058 defs
= STMT_DEF_OPS (stmt
);
2059 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
2061 def
= DEF_OP_PTR (defs
, i
);
2062 if (def
&& *def
!= ignore
&& names_match_p (var
, *def
))
2069 if (curruse
!= NULL_TREE
)
2071 dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
2072 if (bb
== ENTRY_BLOCK_PTR
)
2075 temp
= htab_create (7, htab_hash_pointer
, htab_eq_pointer
, NULL
);
2076 curruse
= get_default_def (var
, temp
);
2081 return reaching_def (var
, currstmt
, dom
, ignore
);
2084 /* Insert one ephi operand that doesn't currently exist as a use. */
2087 insert_one_operand (struct expr_info
*ei
, tree ephi
, int opnd_indx
,
2088 tree x
, edge succ
, tree
**avdefsp
)
2090 /* FIXME. pre_insert_on_edge should probably disappear. */
2091 extern void pre_insert_on_edge (edge
, tree
);
2093 tree temp
= ei
->temp
;
2096 basic_block bb
= bb_for_stmt (x
);
2098 /* Insert definition of expr at end of BB containing x. */
2099 copy
= TREE_OPERAND (EREF_STMT (ephi
), 1);
2100 copy
= unshare_expr (copy
);
2101 expr
= build (MODIFY_EXPR
, TREE_TYPE (ei
->expr
),
2103 expr
= subst_phis (ei
, expr
, bb
, bb_for_stmt (ephi
));
2104 newtemp
= make_ssa_name (temp
, expr
);
2105 TREE_OPERAND (expr
, 0) = newtemp
;
2106 copy
= TREE_OPERAND (expr
, 1);
2109 fprintf (dump_file
, "In BB %d, insert save of ", bb
->index
);
2110 print_generic_expr (dump_file
, expr
, dump_flags
);
2111 fprintf (dump_file
, " to ");
2112 print_generic_expr (dump_file
, newtemp
, dump_flags
);
2113 fprintf (dump_file
, " after ");
2114 print_generic_stmt (dump_file
, last_stmt (bb
), dump_flags
);
2115 fprintf (dump_file
, " (on edge), because of EPHI");
2116 fprintf (dump_file
, " in BB %d\n", bb_for_stmt (ephi
)->index
);
2119 /* Do the insertion. */
2120 /* ??? Previously we did bizarre searching, presumably to get
2121 around bugs elsewhere in the infrastructure. I'm not sure
2122 if we really should be using pre_insert_on_edge
2123 or just bsi_insert_after at the end of BB. */
2124 pre_insert_on_edge (succ
, expr
);
2126 EPHI_ARG_DEF (ephi
, opnd_indx
)
2127 = create_expr_ref (ei
, ei
->expr
, EUSE_NODE
, bb
, 0);
2128 EUSE_DEF (x
) = EPHI_ARG_DEF (ephi
, opnd_indx
);
2129 VARRAY_PUSH_TREE (ei
->euses_dt_order
, EPHI_ARG_DEF (ephi
, opnd_indx
));
2130 qsort (ei
->euses_dt_order
->data
.tree
,
2131 VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
),
2134 EREF_TEMP (EUSE_DEF (x
)) = newtemp
;
2135 EREF_RELOAD (EUSE_DEF (x
)) = false;
2136 EREF_SAVE (EUSE_DEF (x
)) = false;
2137 EUSE_INSERTED (EUSE_DEF (x
)) = true;
2138 EUSE_PHIOP (EUSE_DEF (x
)) = false;
2139 EREF_SAVE (x
) = false;
2140 EREF_RELOAD (x
) = false;
2141 EUSE_INSERTED (x
) = true;
2142 EREF_CLASS (x
) = class_count
++;
2143 EREF_CLASS (EUSE_DEF (x
)) = class_count
++;
2144 *avdefsp
= xrealloc (*avdefsp
, sizeof (tree
) * (class_count
+ 1));
2145 (*avdefsp
)[class_count
- 2] = x
;
2146 (*avdefsp
)[class_count
- 1] = EUSE_DEF (x
);
2150 /* First step of finalization. Determine which expressions are being
2151 saved and which are being deleted.
2152 This is done as a simple dominator based availabilty calculation,
2153 using the e-versions/redundancy classes. */
2156 finalize_1 (struct expr_info
*ei
)
2160 bool made_a_reload
= false;
2164 avdefs
= xcalloc (class_count
+ 1, sizeof (tree
));
2166 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
2168 x
= VARRAY_TREE (ei
->euses_dt_order
, i
);
2169 nx
= EREF_CLASS (x
);
2171 if (TREE_CODE (x
) == EPHI_NODE
)
2173 if (ephi_will_be_avail (x
))
2176 else if (TREE_CODE (x
) == EUSE_NODE
&& EUSE_LVAL (x
))
2180 else if (TREE_CODE (x
) == EUSE_NODE
&& !EUSE_PHIOP (x
))
2182 if (avdefs
[nx
] == NULL
2183 || !dominated_by_p (CDI_DOMINATORS
, bb_for_stmt (x
),
2184 bb_for_stmt (avdefs
[nx
])))
2186 EREF_RELOAD (x
) = false;
2188 EUSE_DEF (x
) = NULL
;
2192 EREF_RELOAD (x
) = true;
2193 made_a_reload
= true;
2194 EUSE_DEF (x
) = avdefs
[nx
];
2195 #ifdef ENABLE_CHECKING
2196 if (EREF_CLASS (x
) != EREF_CLASS (avdefs
[nx
]))
2204 basic_block bb
= bb_for_stmt (x
);
2205 /* For each ephi in the successor blocks. */
2206 for (succ
= bb
->succ
; succ
; succ
= succ
->succ_next
)
2208 tree ephi
= ephi_at_block (succ
->dest
);
2209 if (ephi
== NULL_TREE
)
2211 if (ephi_will_be_avail (ephi
))
2213 int opnd_indx
= opnum_of_ephi (ephi
, succ
);
2214 #ifdef ENABLE_CHECKING
2215 if (EPHI_ARG_PRED (ephi
, opnd_indx
) != x
)
2218 if (can_insert (ephi
, opnd_indx
))
2220 insert_one_operand (ei
, ephi
, opnd_indx
, x
, succ
,
2225 nx
= EREF_CLASS (EPHI_ARG_DEF (ephi
,opnd_indx
));
2226 EPHI_ARG_DEF (ephi
, opnd_indx
) = avdefs
[nx
];
2233 return made_a_reload
;
2236 /* Mark the necessary SAVE bits on X. */
2239 set_save (struct expr_info
*ei
, tree X
)
2241 if (TREE_CODE (X
) == EUSE_NODE
&& !EUSE_PHIOP (X
))
2242 EREF_SAVE (X
) = true;
2243 else if (TREE_CODE (X
) == EPHI_NODE
)
2246 for (curr_phiop
= 0; curr_phiop
< EPHI_NUM_ARGS (X
); curr_phiop
++)
2248 tree w
= EPHI_ARG_DEF (X
, curr_phiop
);
2249 if (!EPHI_ARG_PROCESSED2 (X
, curr_phiop
))
2251 EPHI_ARG_PROCESSED2 (X
, curr_phiop
) = true;
2259 /* DFS Search function: Return true if PHI is can't be available. */
2262 cba_search_seen (tree phi
)
2264 return EPHI_CANT_BE_AVAIL (phi
);
2267 /* DFS Search function: Mark PHI as can't be available when seen. */
2270 cba_search_set_seen (tree phi
)
2272 EPHI_CANT_BE_AVAIL (phi
) = true;
2275 /* DFS Search function: Return true if PHI should be marked can't be
2276 available due to a NULL operand. */
2279 cba_search_start_from (tree phi
)
2281 if (!EPHI_DOWNSAFE (phi
))
2284 for (i
= 0; i
< EPHI_NUM_ARGS (phi
); i
++)
2285 if (EPHI_ARG_DEF (phi
, i
) == NULL_TREE
2286 || EPHI_ARG_EDGE (phi
, i
)->flags
& EDGE_ABNORMAL
)
2292 /* DFS Search function: Return true if the used PHI is not downsafe,
2293 unless we have a real use for the operand. */
2296 cba_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED
,
2300 if (EPHI_ARG_HAS_REAL_USE (use_phi
, opnd_indx
) &&
2301 !(EPHI_ARG_EDGE (use_phi
, opnd_indx
)->flags
& EDGE_ABNORMAL
))
2303 if (!EPHI_DOWNSAFE (use_phi
))
2308 /* DFS Search function: Return true if this PHI stops forward
2312 stops_search_seen (tree phi
)
2314 return EPHI_STOPS (phi
);
2317 /* DFS Search function: Mark the PHI as stopping forward movement. */
2320 stops_search_set_seen (tree phi
)
2322 EPHI_STOPS (phi
) = true;
2325 /* DFS Search function: Note that the used phi argument stops forward
2329 stops_search_reach_from_to (tree def_phi ATTRIBUTE_UNUSED
,
2333 EPHI_ARG_STOPS (use_phi
, opnd_indx
) = true;
2336 /* DFS Search function: Return true if the PHI has any arguments
2337 stopping forward movement. */
2340 stops_search_start_from (tree phi
)
2343 for (i
= 0; i
< EPHI_NUM_ARGS (phi
); i
++)
2344 if (EPHI_ARG_STOPS (phi
, i
))
2349 /* DFS Search function: Return true if the PHI has any arguments
2350 stopping forward movement. */
2353 stops_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED
,
2354 int opnd_indx ATTRIBUTE_UNUSED
,
2357 return stops_search_start_from (use_phi
);
2360 /* DFS Search function: Return true if the replacing occurrence is
2364 repl_search_seen (tree phi
)
2366 return EPHI_REP_OCCUR_KNOWN (phi
);
2369 /* DFS Search function: Set the identical_to field and note the
2370 replacing occurrence is now known. */
2373 repl_search_set_seen (tree phi
)
2377 #ifdef ENABLE_CHECKING
2378 if (!ephi_will_be_avail (phi
))
2382 if (EPHI_IDENTICAL_TO (phi
) == NULL_TREE
)
2384 for (i
= 0; i
< EPHI_NUM_ARGS (phi
); i
++)
2386 tree identical_to
= occ_identical_to (EPHI_ARG_DEF (phi
, i
));
2387 if (identical_to
!= NULL_TREE
)
2389 if (EPHI_IDENTICAL_TO (phi
) == NULL
)
2390 EPHI_IDENTICAL_TO (phi
) = identical_to
;
2391 if (EPHI_ARG_INJURED (phi
, i
))
2392 EPHI_IDENT_INJURED (phi
) = true;
2396 EPHI_REP_OCCUR_KNOWN (phi
) = true;
2399 /* Helper function. Return true if any argument in the PHI is
2403 any_operand_injured (tree ephi
)
2406 for (i
= 0; i
< EPHI_NUM_ARGS (ephi
); i
++)
2407 if (EPHI_ARG_INJURED (ephi
, i
))
2413 /* DFS Search function: Note the identity of the used phi operand is
2414 the same as it's defining phi operand, if that phi will be
2415 available, and it's known. */
2418 repl_search_reach_from_to (tree def_phi
, int opnd_indx ATTRIBUTE_UNUSED
,
2421 if (ephi_will_be_avail (use_phi
)
2422 && EPHI_IDENTITY (use_phi
)
2423 && EPHI_IDENTICAL_TO (use_phi
) == NULL_TREE
)
2425 EPHI_IDENTICAL_TO (use_phi
) = EPHI_IDENTICAL_TO (def_phi
);
2427 if (EPHI_IDENT_INJURED (def_phi
)
2428 || any_operand_injured (use_phi
))
2429 EPHI_IDENT_INJURED (use_phi
) = true;
2433 /* DFS Search function: Return true if the PHI will be available,
2434 it's an identity PHI, and it's arguments are identical to
2438 repl_search_start_from (tree phi
)
2440 if (ephi_will_be_avail (phi
) && EPHI_IDENTITY (phi
))
2443 for (i
= 0; i
< EPHI_NUM_ARGS (phi
); i
++)
2444 if (occ_identical_to (EPHI_ARG_DEF (phi
, i
)) != NULL_TREE
)
2450 /* DFS Search function: Return true if the using PHI is will be available,
2454 repl_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED
,
2455 int opnd_indx ATTRIBUTE_UNUSED
,
2458 return ephi_will_be_avail (use_phi
) && EPHI_IDENTITY (use_phi
);
2461 /* Mark all will-be-avail ephi's in the dominance frontier of BB as
2465 require_phi (struct expr_info
*ei
, basic_block bb
)
2468 EXECUTE_IF_SET_IN_BITMAP (pre_dfs
[bb
->index
], 0, i
,
2471 ephi
= ephi_at_block (BASIC_BLOCK (i
));
2472 if (ephi
!= NULL_TREE
2473 && ephi_will_be_avail (ephi
)
2474 && EPHI_IDENTITY (ephi
))
2476 EPHI_IDENTITY (ephi
) = false;
2477 require_phi (ei
, BASIC_BLOCK (i
));
2482 /* Return the occurrence this occurrence is identical to, if one exists. */
2485 occ_identical_to (tree t
)
2487 if (TREE_CODE (t
) == EUSE_NODE
&& !EUSE_PHIOP (t
))
2489 else if (TREE_CODE (t
) == EUSE_NODE
&& EUSE_PHIOP (t
))
2491 else if (TREE_CODE (t
) == EPHI_NODE
)
2493 if (EPHI_IDENTITY (t
) && EPHI_REP_OCCUR_KNOWN (t
))
2494 return EPHI_IDENTICAL_TO (t
);
2495 else if (!EPHI_IDENTITY (t
))
2501 /* Return true if NODE was or is going to be saved. */
2503 really_available_def (tree node
)
2505 if (TREE_CODE (node
) == EUSE_NODE
2506 && EUSE_PHIOP (node
)
2507 && EUSE_INSERTED (node
))
2509 if (TREE_CODE (node
) == EUSE_NODE
2510 && EUSE_DEF (node
) == NULL_TREE
)
2516 /* Second part of the finalize step. Performs save bit setting, and
2517 ESSA minimization. */
2520 finalize_2 (struct expr_info
*ei
)
2524 insert_euse_in_preorder_dt_order (ei
);
2525 /* Note which uses need to be saved to a temporary. */
2526 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
2528 tree ref
= VARRAY_TREE (ei
->euses_dt_order
, i
);
2529 if (TREE_CODE (ref
) == EUSE_NODE
2530 && !EUSE_PHIOP (ref
)
2531 && EREF_RELOAD (ref
))
2533 set_save (ei
, EUSE_DEF (ref
));
2537 /* ESSA Minimization. Determines which phis are identical to other
2538 phis, and not strictly necessary. */
2540 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
2542 tree ephi
= VARRAY_TREE (ei
->euses_dt_order
, i
);
2543 if (TREE_CODE (ephi
) != EPHI_NODE
)
2545 EPHI_IDENTITY (ephi
) = true;
2546 EPHI_IDENTICAL_TO (ephi
) = NULL
;
2549 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
2551 tree ephi
= VARRAY_TREE (ei
->euses_dt_order
, i
);
2552 if (!ephi
|| TREE_CODE (ephi
) != EPHI_NODE
)
2554 if (ephi_will_be_avail (ephi
))
2557 for (k
= 0; k
< EPHI_NUM_ARGS (ephi
); k
++)
2559 if (EPHI_ARG_INJURED (ephi
, k
))
2560 require_phi (ei
, EPHI_ARG_EDGE (ephi
, k
)->src
);
2561 else if (EPHI_ARG_DEF (ephi
, k
)
2562 && TREE_CODE (EPHI_ARG_DEF (ephi
, k
)) == EUSE_NODE
2563 && really_available_def (EPHI_ARG_DEF (ephi
, k
)))
2564 require_phi (ei
, bb_for_stmt (EPHI_ARG_DEF (ephi
, k
)));
2568 do_ephi_df_search (ei
, replacing_search
);
2571 /* Perform a DFS on EPHI using the functions in SEARCH. */
2574 do_ephi_df_search_1 (struct ephi_df_search search
, tree ephi
)
2578 search
.set_seen (ephi
);
2580 uses
= EPHI_USES (ephi
);
2583 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (uses
); i
++)
2585 struct ephi_use_entry
*use
= VARRAY_GENERIC_PTR (uses
, i
);
2586 if (search
.reach_from_to
)
2587 search
.reach_from_to (ephi
, use
->opnd_indx
, use
->phi
);
2588 if (!search
.seen (use
->phi
) &&
2589 search
.continue_from_to (ephi
, use
->opnd_indx
, use
->phi
))
2591 do_ephi_df_search_1 (search
, use
->phi
);
2596 /* Perform a DFS on the EPHI's, using the functions in SEARCH. */
2599 do_ephi_df_search (struct expr_info
*ei
, struct ephi_df_search search
)
2602 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
2604 tree ephi
= VARRAY_TREE (ei
->euses_dt_order
, i
);
2605 if (!ephi
|| TREE_CODE (ephi
) != EPHI_NODE
)
2607 if (!search
.seen (ephi
)
2608 && search
.start_from (ephi
))
2609 do_ephi_df_search_1 (search
, ephi
);
2614 /* Calculate the increment necessary due to EXPR for the temporary. */
2616 calculate_increment (struct expr_info
*ei
, tree expr
)
2620 /*XXX: Currently assume it's like a = a + 5, thus, this will give us the 5.
2622 incr
= TREE_OPERAND (TREE_OPERAND (expr
, 1), 1);
2623 if (TREE_CODE (incr
) != INTEGER_CST
)
2625 if (TREE_CODE (ei
->expr
) == MULT_EXPR
)
2626 incr
= fold (build (MULT_EXPR
, TREE_TYPE (ei
->expr
),
2627 incr
, TREE_OPERAND (ei
->expr
, 1)));
2628 #if DEBUGGING_STRRED
2631 fprintf (dump_file
, "Increment calculated to be: ");
2632 print_generic_expr (dump_file
, incr
, 0);
2633 fprintf (dump_file
, "\n");
2641 /* Perform an insertion of EXPR before/after USE, depending on the
2645 do_proper_save (tree use
, tree expr
, int before
)
2647 basic_block bb
= bb_for_stmt (use
);
2648 block_stmt_iterator bsi
;
2650 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2652 if (bsi_stmt (bsi
) == use
)
2655 bsi_insert_before (&bsi
, expr
, BSI_SAME_STMT
);
2657 bsi_insert_after (&bsi
, expr
, BSI_SAME_STMT
);
2664 /* Get the temporary for ESSA node USE.
2665 Takes into account minimized ESSA. */
2670 if (TREE_CODE (use
) == EPHI_NODE
&& EPHI_IDENTITY (use
))
2673 while (TREE_CODE (newuse
) == EPHI_NODE
2674 && EPHI_IDENTITY (newuse
))
2676 #ifdef ENABLE_CHECKING
2677 if (!EPHI_IDENTICAL_TO (newuse
))
2680 newuse
= EPHI_IDENTICAL_TO (newuse
);
2681 if (TREE_CODE (newuse
) != EPHI_NODE
)
2684 if (TREE_CODE (EREF_TEMP (newuse
)) == PHI_NODE
)
2685 newtemp
= PHI_RESULT (EREF_TEMP (newuse
));
2687 newtemp
= EREF_TEMP (newuse
);
2691 if (TREE_CODE (EREF_TEMP (use
)) == PHI_NODE
)
2692 newtemp
= PHI_RESULT (EREF_TEMP (use
));
2694 newtemp
= EREF_TEMP (use
);
2699 /* Return the side of the statement that contains an SSA name. */
2702 pick_ssa_name (tree stmt
)
2704 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
)
2705 return TREE_OPERAND (stmt
, 0);
2706 else if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
)
2707 return TREE_OPERAND (stmt
, 1);
2712 /* Code motion step of SSAPRE. Take the save bits, and reload bits,
2713 and perform the saves and reloads. Also insert new phis where
2717 code_motion (struct expr_info
*ei
)
2722 tree temp
= ei
->temp
;
2725 /* First, add the phi node temporaries so the reaching defs are
2728 euse_iter
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
);
2732 use
= VARRAY_TREE (ei
->euses_dt_order
, euse_iter
);
2733 if (TREE_CODE (use
) != EPHI_NODE
)
2735 if (ephi_will_be_avail (use
) && !EPHI_IDENTITY (use
))
2737 bb
= bb_for_stmt (use
);
2738 /* Add the new PHI node to the list of PHI nodes for block BB. */
2739 bb_ann (bb
)->phi_nodes
= chainon (phi_nodes (bb
), EREF_TEMP (use
));
2741 else if (EPHI_IDENTITY (use
))
2743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2745 fprintf (dump_file
, "Pointless EPHI in block %d\n",
2746 bb_for_stmt (use
)->index
);
2750 /* Now do the actual saves and reloads, plus repairs. */
2752 euse_iter
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
);
2755 use
= VARRAY_TREE (ei
->euses_dt_order
, euse_iter
);
2756 #ifdef ENABLE_CHECKING
2757 if (TREE_CODE (use
) == EUSE_NODE
&& EUSE_PHIOP (use
)
2758 && (EREF_RELOAD (use
) || EREF_SAVE (use
)))
2761 if (EREF_SAVE (use
) && !EUSE_INSERTED (use
))
2766 basic_block usebb
= bb_for_stmt (use
);
2767 use_stmt
= EREF_STMT (use
);
2769 copy
= TREE_OPERAND (use_stmt
, 1);
2770 copy
= unshare_expr (copy
);
2771 newexpr
= build (MODIFY_EXPR
, TREE_TYPE (temp
), temp
, copy
);
2772 newtemp
= make_ssa_name (temp
, newexpr
);
2773 EREF_TEMP (use
) = newtemp
;
2774 TREE_OPERAND (newexpr
, 0) = newtemp
;
2775 TREE_OPERAND (use_stmt
, 1) = newtemp
;
2779 fprintf (dump_file
, "In BB %d, insert save of ",
2781 print_generic_expr (dump_file
, copy
, dump_flags
);
2782 fprintf (dump_file
, " to ");
2783 print_generic_expr (dump_file
, newtemp
, dump_flags
);
2784 fprintf (dump_file
, " before statement ");
2785 print_generic_expr (dump_file
, use_stmt
, dump_flags
);
2786 fprintf (dump_file
, "\n");
2787 if (EXPR_HAS_LOCATION (use_stmt
))
2788 fprintf (dump_file
, " on line %d\n",
2789 EXPR_LINENO (use_stmt
));
2791 modify_stmt (newexpr
);
2792 modify_stmt (use_stmt
);
2793 set_bb_for_stmt (newexpr
, usebb
);
2794 EREF_STMT (use
) = do_proper_save (use_stmt
, newexpr
, true);
2797 else if (EREF_RELOAD (use
))
2802 use_stmt
= EREF_STMT (use
);
2803 bb
= bb_for_stmt (use_stmt
);
2805 newtemp
= get_temp (EUSE_DEF (use
));
2810 fprintf (dump_file
, "In BB %d, insert reload of ",
2812 print_generic_expr (dump_file
,
2813 TREE_OPERAND (use_stmt
, 1), 0);
2814 fprintf (dump_file
, " from ");
2815 print_generic_expr (dump_file
, newtemp
, dump_flags
);
2816 fprintf (dump_file
, " in statement ");
2817 print_generic_stmt (dump_file
, use_stmt
, dump_flags
);
2818 fprintf (dump_file
, "\n");
2819 if (EXPR_HAS_LOCATION (use_stmt
))
2820 fprintf (dump_file
, " on line %d\n",
2821 EXPR_LINENO (use_stmt
));
2823 TREE_OPERAND (use_stmt
, 1) = newtemp
;
2824 EREF_TEMP (use
) = newtemp
;
2825 modify_stmt (use_stmt
);
2826 pre_stats
.reloads
++;
2830 /* Now do the phi nodes. */
2832 euse_iter
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
);
2835 use
= VARRAY_TREE (ei
->euses_dt_order
, euse_iter
);
2836 if (TREE_CODE (use
) == EPHI_NODE
2837 && ephi_will_be_avail (use
)
2838 && !EPHI_IDENTITY (use
))
2842 bb
= bb_for_stmt (use
);
2846 "In BB %d, insert PHI to replace EPHI\n", bb
->index
);
2848 newtemp
= EREF_TEMP (use
);
2849 for (i
= 0; i
< EPHI_NUM_ARGS (use
); i
++)
2852 argdef
= EPHI_ARG_DEF (use
, i
);
2854 rdef
= get_temp (use
);
2855 else if (EREF_RELOAD (argdef
) || EREF_SAVE (argdef
))
2856 rdef
= get_temp (argdef
);
2857 else if (TREE_CODE (argdef
) == EPHI_NODE
)
2858 rdef
= get_temp (argdef
);
2860 && EPHI_ARG_HAS_REAL_USE (use
, i
)
2861 && EREF_STMT (argdef
)
2862 && !EPHI_ARG_INJURED (use
, i
))
2863 rdef
= pick_ssa_name (EREF_STMT (argdef
));
2869 add_phi_arg (&newtemp
, rdef
, EPHI_ARG_EDGE (use
, i
));
2872 /* Associate BB to the PHI node. */
2873 set_bb_for_stmt (EREF_TEMP (use
), bb
);
2874 pre_stats
.newphis
++;
2880 /* Compute the iterated dominance frontier of a statement. */
2883 compute_idfs (bitmap
* dfs
, tree stmt
)
2886 sbitmap inworklist
, done
;
2891 block
= bb_for_stmt (stmt
);
2892 if (idfs_cache
[block
->index
] != NULL
)
2893 return idfs_cache
[block
->index
];
2895 inworklist
= sbitmap_alloc (last_basic_block
);
2896 done
= sbitmap_alloc (last_basic_block
);
2897 worklist
= fibheap_new ();
2898 sbitmap_zero (inworklist
);
2899 sbitmap_zero (done
);
2901 idf
= BITMAP_XMALLOC ();
2904 block
= bb_for_stmt (stmt
);
2905 fibheap_insert (worklist
, block
->index
, (void *)(size_t)block
->index
);
2906 SET_BIT (inworklist
, block
->index
);
2908 while (!fibheap_empty (worklist
))
2910 int a
= (size_t) fibheap_extract_min (worklist
);
2911 if (TEST_BIT (done
, a
))
2916 bitmap_a_or_b (idf
, idf
, idfs_cache
[a
]);
2917 EXECUTE_IF_SET_IN_BITMAP (idfs_cache
[a
], 0, i
,
2919 SET_BIT (inworklist
, i
);
2925 bitmap_a_or_b (idf
, idf
, dfs
[a
]);
2926 EXECUTE_IF_SET_IN_BITMAP (dfs
[a
], 0, i
,
2928 if (!TEST_BIT (inworklist
, i
))
2930 SET_BIT (inworklist
, i
);
2931 fibheap_insert (worklist
, i
, (void *)i
);
2937 fibheap_delete (worklist
);
2938 sbitmap_free (inworklist
);
2939 sbitmap_free (done
);
2940 idfs_cache
[block
->index
] = idf
;
2945 /* Return true if EXPR is a strength reduction candidate. */
2947 is_strred_cand (const tree expr ATTRIBUTE_UNUSED
)
2950 if (TREE_CODE (TREE_OPERAND (expr
, 1)) != MULT_EXPR
2951 && TREE_CODE (TREE_OPERAND (expr
, 1)) != MINUS_EXPR
2952 && TREE_CODE (TREE_OPERAND (expr
, 1)) != NEGATE_EXPR
2953 && TREE_CODE (TREE_OPERAND (expr
, 1)) != PLUS_EXPR
)
2962 /* Determine if two expressions are lexically equivalent. */
2965 expr_lexically_eq (const tree v1
, const tree v2
)
2967 if (TREE_CODE_CLASS (TREE_CODE (v1
)) != TREE_CODE_CLASS (TREE_CODE (v2
)))
2969 if (TREE_CODE (v1
) != TREE_CODE (v2
))
2971 switch (TREE_CODE_CLASS (TREE_CODE (v1
)))
2975 return names_match_p (TREE_OPERAND (v1
, 0), TREE_OPERAND (v2
, 0));
2978 return names_match_p (v1
, v2
);
2982 match
= names_match_p (TREE_OPERAND (v1
, 0), TREE_OPERAND (v2
, 0));
2985 match
= names_match_p (TREE_OPERAND (v1
, 1), TREE_OPERAND (v2
, 1));
2996 /* Free an expression info structure. */
2999 free_expr_info (struct expr_info
*v1
)
3001 struct expr_info
*e1
= (struct expr_info
*)v1
;
3002 VARRAY_FREE (e1
->occurs
);
3003 VARRAY_FREE (e1
->kills
);
3004 VARRAY_FREE (e1
->lefts
);
3005 VARRAY_FREE (e1
->reals
);
3006 VARRAY_FREE (e1
->euses_dt_order
);
3009 /* Process left occurrences and kills due to EXPR.
3010 A left occurrence occurs wherever a variable in an expression we
3011 are PRE'ing is stored to directly in a def, or indirectly because
3012 of a VDEF of an expression that we VUSE. */
3015 process_left_occs_and_kills (varray_type bexprs
, tree expr
)
3019 stmt_ann_t ann
= stmt_ann (expr
);
3023 defs
= DEF_OPS (ann
);
3024 vdefs
= VDEF_OPS (ann
);
3025 if (NUM_DEFS (defs
) == 0 && NUM_VDEFS (vdefs
) == 0)
3028 for (j
= 0; j
< VARRAY_ACTIVE_SIZE (bexprs
); j
++)
3030 struct expr_info
*ei
= VARRAY_GENERIC_PTR (bexprs
, j
);
3035 if (!ei
->loadpre_cand
)
3038 /* If we define the variable itself (IE a in *a, or a in a),
3039 it's a left occurrence. */
3040 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
3042 if (names_match_p (DEF_OP (defs
, i
), ei
->expr
))
3044 if (TREE_CODE (expr
) == ASM_EXPR
)
3046 ei
->loadpre_cand
= false;
3049 VARRAY_PUSH_TREE (ei
->lefts
, expr
);
3050 VARRAY_PUSH_TREE (ei
->occurs
, NULL
);
3051 VARRAY_PUSH_TREE (ei
->kills
, NULL
);
3055 /* If we VDEF the VUSE of the expression, it's also a left
3057 random_occur
= VARRAY_TREE (ei
->occurs
, 0);
3058 ann
= stmt_ann (random_occur
);
3059 vuses
= VUSE_OPS (ann
);
3060 if (NUM_VDEFS (vdefs
) != 0)
3062 for (k
= 0; k
< NUM_VUSES (vuses
); k
++)
3064 vuse_name
= VUSE_OP (vuses
, k
);
3065 for (i
= 0; i
< NUM_VDEFS (vdefs
); i
++)
3067 if (names_match_p (VDEF_OP (vdefs
, i
), vuse_name
))
3069 VARRAY_PUSH_TREE (ei
->lefts
, expr
);
3070 VARRAY_PUSH_TREE (ei
->occurs
, NULL
);
3071 VARRAY_PUSH_TREE (ei
->kills
, NULL
);
3079 /* Perform SSAPRE on an expression. */
3082 pre_expression (struct expr_info
*slot
, void *data
, bitmap vars_to_rename
)
3084 struct expr_info
*ei
= (struct expr_info
*) slot
;
3088 eref_id_counter
= 0;
3090 /* If we don't have two occurrences along any dominated path, and
3091 it's not load PRE, this is a waste of time. */
3093 if (VARRAY_ACTIVE_SIZE (ei
->reals
) < 2)
3096 memset (&pre_stats
, 0, sizeof (struct pre_stats_d
));
3098 ei
->temp
= create_tmp_var (TREE_TYPE (ei
->expr
), "pretmp");
3099 add_referenced_tmp_var (ei
->temp
);
3101 bitmap_clear (created_phi_preds
);
3102 ephi_pindex_htab
= htab_create (500, ephi_pindex_hash
, ephi_pindex_eq
, free
);
3103 phi_pred_cache
= xcalloc (last_basic_block
, sizeof (tree
));
3104 n_phi_preds
= last_basic_block
;
3106 if (!expr_phi_insertion ((bitmap
*)data
, ei
))
3109 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3112 fprintf (dump_file
, "Occurrences for expression ");
3113 print_generic_expr (dump_file
, ei
->expr
, dump_flags
);
3114 fprintf (dump_file
, " after Rename 2\n");
3115 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ei
->euses_dt_order
); i
++)
3117 print_generic_expr (dump_file
,
3118 VARRAY_TREE (ei
->euses_dt_order
, i
), 1);
3119 fprintf (dump_file
, "\n");
3122 compute_down_safety (ei
);
3123 compute_du_info (ei
);
3124 compute_will_be_avail (ei
);
3126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3128 fprintf (dump_file
, "EPHI's for expression ");
3129 print_generic_expr (dump_file
, ei
->expr
, dump_flags
);
3131 " after down safety and will_be_avail computation\n");
3134 tree ephi
= ephi_at_block (bb
);
3137 print_generic_expr (dump_file
, ephi
, 1);
3138 fprintf (dump_file
, "\n");
3143 if (finalize_1 (ei
))
3147 if (ei
->loadpre_cand
)
3148 bitmap_set_bit (vars_to_rename
, var_ann (ei
->temp
)->uid
);
3151 clear_all_eref_arrays ();
3153 if (dump_flags
& TDF_STATS
)
3155 fprintf (dump_file
, "PRE stats:\n");
3156 fprintf (dump_file
, "Reloads:%d\n", pre_stats
.reloads
);
3157 fprintf (dump_file
, "Saves:%d\n", pre_stats
.saves
);
3158 fprintf (dump_file
, "Repairs:%d\n", pre_stats
.repairs
);
3159 fprintf (dump_file
, "New phis:%d\n", pre_stats
.newphis
);
3160 fprintf (dump_file
, "EPHI memory allocated:%d\n",
3161 pre_stats
.ephi_allocated
);
3162 fprintf (dump_file
, "EREF memory allocated:%d\n",
3163 pre_stats
.eref_allocated
);
3164 fprintf (dump_file
, "Expressions generated for rename2:%d\n",
3165 pre_stats
.exprs_generated
);
3168 free (phi_pred_cache
);
3169 if (ephi_pindex_htab
)
3171 htab_delete (ephi_pindex_htab
);
3172 ephi_pindex_htab
= NULL
;
3180 /* Step 1 - Collect the expressions to perform PRE on. */
3183 collect_expressions (basic_block block
, varray_type
*bexprsp
)
3186 block_stmt_iterator j
;
3189 varray_type bexprs
= *bexprsp
;
3191 for (j
= bsi_start (block
); !bsi_end_p (j
); bsi_next (&j
))
3193 tree stmt
= bsi_stmt (j
);
3195 tree orig_expr
= expr
;
3197 struct expr_info
*slot
= NULL
;
3199 get_stmt_operands (expr
);
3200 ann
= stmt_ann (expr
);
3202 if (NUM_USES (USE_OPS (ann
)) == 0)
3204 process_left_occs_and_kills (bexprs
, expr
);
3208 if (TREE_CODE (expr
) == MODIFY_EXPR
)
3209 expr
= TREE_OPERAND (expr
, 1);
3210 if ((TREE_CODE_CLASS (TREE_CODE (expr
)) == '2'
3211 || TREE_CODE_CLASS (TREE_CODE (expr
)) == '<'
3212 /*|| TREE_CODE_CLASS (TREE_CODE (expr)) == '1'*/
3213 || TREE_CODE (expr
) == SSA_NAME
3214 || TREE_CODE (expr
) == INDIRECT_REF
)
3215 && !ann
->makes_aliased_stores
3216 && !ann
->has_volatile_ops
)
3218 bool is_scalar
= true;
3219 tree origop0
= TREE_OPERAND (orig_expr
, 0);
3221 if (AGGREGATE_TYPE_P (TREE_TYPE (origop0
))
3222 || TREE_CODE (TREE_TYPE (origop0
)) == COMPLEX_TYPE
)
3226 && (TREE_CODE (expr
) == SSA_NAME
3227 || (TREE_CODE (expr
) == INDIRECT_REF
3228 && !DECL_P (TREE_OPERAND (expr
, 0)))
3229 ||(!DECL_P (TREE_OPERAND (expr
, 0))
3230 && (!TREE_OPERAND (expr
, 1)
3231 || !DECL_P (TREE_OPERAND (expr
, 1))))))
3233 for (k
= 0; k
< VARRAY_ACTIVE_SIZE (bexprs
); k
++)
3235 slot
= VARRAY_GENERIC_PTR (bexprs
, k
);
3236 if (expr_lexically_eq (slot
->expr
, expr
))
3239 if (k
>= VARRAY_ACTIVE_SIZE (bexprs
))
3243 VARRAY_PUSH_TREE (slot
->occurs
, orig_expr
);
3244 VARRAY_PUSH_TREE (slot
->kills
, NULL
);
3245 VARRAY_PUSH_TREE (slot
->lefts
, NULL
);
3246 VARRAY_PUSH_TREE (slot
->reals
, stmt
);
3247 slot
->strred_cand
&= is_strred_cand (orig_expr
);
3251 slot
= ggc_alloc (sizeof (struct expr_info
));
3253 VARRAY_GENERIC_PTR_NOGC_INIT (slot
->occurs
, 1, "Occurrence");
3254 VARRAY_GENERIC_PTR_NOGC_INIT (slot
->kills
, 1, "Kills");
3255 VARRAY_GENERIC_PTR_NOGC_INIT (slot
->lefts
, 1, "Left occurrences");
3256 VARRAY_GENERIC_PTR_NOGC_INIT (slot
->reals
, 1, "Real occurrences");
3257 VARRAY_GENERIC_PTR_NOGC_INIT (slot
->euses_dt_order
, 1, "EUSEs");
3259 VARRAY_PUSH_TREE (slot
->occurs
, orig_expr
);
3260 VARRAY_PUSH_TREE (slot
->kills
, NULL
);
3261 VARRAY_PUSH_TREE (slot
->lefts
, NULL
);
3262 VARRAY_PUSH_TREE (slot
->reals
, stmt
);
3263 VARRAY_PUSH_GENERIC_PTR (bexprs
, slot
);
3264 slot
->strred_cand
= is_strred_cand (orig_expr
);
3265 slot
->loadpre_cand
= false;
3266 if (TREE_CODE (expr
) == SSA_NAME
3267 || TREE_CODE (expr
) == INDIRECT_REF
)
3268 slot
->loadpre_cand
= true;
3272 process_left_occs_and_kills (bexprs
, orig_expr
);
3276 for (son
= first_dom_son (CDI_DOMINATORS
, block
);
3278 son
= next_dom_son (CDI_DOMINATORS
, son
))
3279 collect_expressions (son
, bexprsp
);
3282 /* Main entry point to the SSA-PRE pass.
3284 PHASE indicates which dump file from the DUMP_FILES array to use when
3285 dumping debugging information. */
3295 if (ENTRY_BLOCK_PTR
->succ
->dest
->pred
->pred_next
)
3296 if (!(ENTRY_BLOCK_PTR
->succ
->flags
& EDGE_ABNORMAL
))
3297 split_edge (ENTRY_BLOCK_PTR
->succ
);
3299 euse_node_pool
= create_alloc_pool ("EUSE node pool",
3300 sizeof (struct tree_euse_node
), 30);
3301 eref_node_pool
= create_alloc_pool ("EREF node pool",
3302 sizeof (struct tree_eref_common
), 30);
3303 ephi_use_pool
= create_alloc_pool ("EPHI use node pool",
3304 sizeof (struct ephi_use_entry
), 30);
3305 VARRAY_GENERIC_PTR_INIT (bexprs
, 1, "bexprs");
3306 /* Compute immediate dominators. */
3307 calculate_dominance_info (CDI_DOMINATORS
);
3309 /* DCE screws the dom_children up, without bothering to fix it. So fix it. */
3310 currbbs
= n_basic_blocks
;
3311 dfn
= xcalloc (last_basic_block
+ 1, sizeof (int));
3312 build_dfn_array (ENTRY_BLOCK_PTR
, 0);
3314 /* Initialize IDFS cache. */
3315 idfs_cache
= xcalloc (currbbs
, sizeof (bitmap
));
3317 /* Compute dominance frontiers. */
3318 pre_dfs
= (bitmap
*) xmalloc (sizeof (bitmap
) * currbbs
);
3319 for (i
= 0; i
< currbbs
; i
++)
3320 pre_dfs
[i
] = BITMAP_XMALLOC ();
3321 compute_dominance_frontiers (pre_dfs
);
3323 created_phi_preds
= BITMAP_XMALLOC ();
3325 collect_expressions (ENTRY_BLOCK_PTR
, &bexprs
);
3327 ggc_push_context ();
3329 for (k
= 0; k
< VARRAY_ACTIVE_SIZE (bexprs
); k
++)
3331 pre_expression (VARRAY_GENERIC_PTR (bexprs
, k
), pre_dfs
, vars_to_rename
);
3332 free_alloc_pool (euse_node_pool
);
3333 free_alloc_pool (eref_node_pool
);
3334 free_alloc_pool (ephi_use_pool
);
3335 euse_node_pool
= create_alloc_pool ("EUSE node pool",
3336 sizeof (struct tree_euse_node
), 30);
3337 eref_node_pool
= create_alloc_pool ("EREF node pool",
3338 sizeof (struct tree_eref_common
), 30);
3339 ephi_use_pool
= create_alloc_pool ("EPHI use node pool",
3340 sizeof (struct ephi_use_entry
), 30);
3341 free_expr_info (VARRAY_GENERIC_PTR (bexprs
, k
));
3342 #ifdef ENABLE_CHECKING
3343 if (pre_stats
.ephis_current
!= 0)
3351 /* Clean up after PRE. */
3352 memset (&pre_stats
, 0, sizeof (struct pre_stats_d
));
3353 free_alloc_pool (euse_node_pool
);
3354 free_alloc_pool (eref_node_pool
);
3355 free_alloc_pool (ephi_use_pool
);
3356 VARRAY_CLEAR (bexprs
);
3357 for (i
= 0; i
< currbbs
; i
++)
3358 BITMAP_XFREE (pre_dfs
[i
]);
3360 BITMAP_XFREE (created_phi_preds
);
3361 for (i
= 0; i
< currbbs
; i
++)
3362 if (idfs_cache
[i
] != NULL
)
3363 BITMAP_XFREE (idfs_cache
[i
]);
3372 return flag_tree_pre
!= 0;
3375 struct tree_opt_pass pass_pre
=
3378 gate_pre
, /* gate */
3379 execute_pre
, /* execute */
3382 0, /* static_pass_number */
3383 TV_TREE_PRE
, /* tv_id */
3384 PROP_no_crit_edges
| PROP_cfg
| PROP_ssa
,/* properties_required */
3385 0, /* properties_provided */
3386 0, /* properties_destroyed */
3387 0, /* todo_flags_start */
3388 TODO_dump_func
| TODO_rename_vars
3389 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */