]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* SSA Dominator optimizations for trees |
7cf0dbf3 | 2 | Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 |
62b180e1 | 3 | Free Software Foundation, Inc. |
4ee9c684 | 4 | Contributed by Diego Novillo <dnovillo@redhat.com> |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
8c4c00c1 | 10 | the Free Software Foundation; either version 3, or (at your option) |
4ee9c684 | 11 | any later version. |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
4ee9c684 | 21 | |
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "tree.h" | |
27 | #include "flags.h" | |
4ee9c684 | 28 | #include "tm_p.h" |
4ee9c684 | 29 | #include "basic-block.h" |
388d1fc1 | 30 | #include "cfgloop.h" |
4ee9c684 | 31 | #include "function.h" |
ce084dfc | 32 | #include "tree-pretty-print.h" |
33 | #include "gimple-pretty-print.h" | |
4ee9c684 | 34 | #include "timevar.h" |
35 | #include "tree-dump.h" | |
36 | #include "tree-flow.h" | |
37 | #include "domwalk.h" | |
4ee9c684 | 38 | #include "tree-pass.h" |
7d564439 | 39 | #include "tree-ssa-propagate.h" |
4ee9c684 | 40 | #include "langhooks.h" |
cf024d22 | 41 | #include "params.h" |
4ee9c684 | 42 | |
43 | /* This file implements optimizations on the dominator tree. */ | |
44 | ||
75a70cf9 | 45 | /* Representation of a "naked" right-hand-side expression, to be used |
46 | in recording available expressions in the expression hash table. */ | |
47 | ||
48 | enum expr_kind | |
49 | { | |
50 | EXPR_SINGLE, | |
51 | EXPR_UNARY, | |
52 | EXPR_BINARY, | |
00f4f705 | 53 | EXPR_TERNARY, |
889ef038 | 54 | EXPR_CALL, |
55 | EXPR_PHI | |
75a70cf9 | 56 | }; |
57 | ||
58 | struct hashable_expr | |
59 | { | |
60 | tree type; | |
61 | enum expr_kind kind; | |
62 | union { | |
63 | struct { tree rhs; } single; | |
64 | struct { enum tree_code op; tree opnd; } unary; | |
00f4f705 | 65 | struct { enum tree_code op; tree opnd0, opnd1; } binary; |
66 | struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary; | |
fb049fba | 67 | struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call; |
889ef038 | 68 | struct { size_t nargs; tree *args; } phi; |
75a70cf9 | 69 | } ops; |
70 | }; | |
71 | ||
72 | /* Structure for recording known values of a conditional expression | |
73 | at the exits from its block. */ | |
74 | ||
7aab1427 | 75 | typedef struct cond_equivalence_s |
75a70cf9 | 76 | { |
77 | struct hashable_expr cond; | |
78 | tree value; | |
7aab1427 | 79 | } cond_equivalence; |
80 | ||
81 | DEF_VEC_O(cond_equivalence); | |
82 | DEF_VEC_ALLOC_O(cond_equivalence,heap); | |
2f0993e7 | 83 | |
84 | /* Structure for recording edge equivalences as well as any pending | |
85 | edge redirections during the dominator optimizer. | |
86 | ||
87 | Computing and storing the edge equivalences instead of creating | |
88 | them on-demand can save significant amounts of time, particularly | |
48e1416a | 89 | for pathological cases involving switch statements. |
2f0993e7 | 90 | |
91 | These structures live for a single iteration of the dominator | |
92 | optimizer in the edge's AUX field. At the end of an iteration we | |
93 | free each of these structures and update the AUX field to point | |
94 | to any requested redirection target (the code for updating the | |
95 | CFG and SSA graph for edge redirection expects redirection edge | |
96 | targets to be in the AUX field for each edge. */ | |
97 | ||
98 | struct edge_info | |
99 | { | |
100 | /* If this edge creates a simple equivalence, the LHS and RHS of | |
101 | the equivalence will be stored here. */ | |
102 | tree lhs; | |
103 | tree rhs; | |
104 | ||
105 | /* Traversing an edge may also indicate one or more particular conditions | |
7aab1427 | 106 | are true or false. */ |
107 | VEC(cond_equivalence, heap) *cond_equivalences; | |
2f0993e7 | 108 | }; |
109 | ||
4ee9c684 | 110 | /* Hash table with expressions made available during the renaming process. |
111 | When an assignment of the form X_i = EXPR is found, the statement is | |
112 | stored in this table. If the same expression EXPR is later found on the | |
113 | RHS of another statement, it is replaced with X_i (thus performing | |
114 | global redundancy elimination). Similarly as we pass through conditionals | |
115 | we record the conditional itself as having either a true or false value | |
116 | in this table. */ | |
117 | static htab_t avail_exprs; | |
118 | ||
9c629f0e | 119 | /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any |
120 | expressions it enters into the hash table along with a marker entry | |
73645111 | 121 | (null). When we finish processing the block, we pop off entries and |
9c629f0e | 122 | remove the expressions from the global hash table until we hit the |
123 | marker. */ | |
75a70cf9 | 124 | typedef struct expr_hash_elt * expr_hash_elt_t; |
125 | DEF_VEC_P(expr_hash_elt_t); | |
126 | DEF_VEC_ALLOC_P(expr_hash_elt_t,heap); | |
127 | ||
128 | static VEC(expr_hash_elt_t,heap) *avail_exprs_stack; | |
9c629f0e | 129 | |
75a70cf9 | 130 | /* Structure for entries in the expression hash table. */ |
a8046f60 | 131 | |
4ee9c684 | 132 | struct expr_hash_elt |
133 | { | |
134 | /* The value (lhs) of this expression. */ | |
135 | tree lhs; | |
136 | ||
137 | /* The expression (rhs) we want to record. */ | |
75a70cf9 | 138 | struct hashable_expr expr; |
4ee9c684 | 139 | |
b66731e8 | 140 | /* The stmt pointer if this element corresponds to a statement. */ |
75a70cf9 | 141 | gimple stmt; |
4ee9c684 | 142 | |
75a70cf9 | 143 | /* The hash value for RHS. */ |
4ee9c684 | 144 | hashval_t hash; |
75a70cf9 | 145 | |
146 | /* A unique stamp, typically the address of the hash | |
147 | element itself, used in removing entries from the table. */ | |
148 | struct expr_hash_elt *stamp; | |
4ee9c684 | 149 | }; |
150 | ||
da43203c | 151 | /* Stack of dest,src pairs that need to be restored during finalization. |
152 | ||
153 | A NULL entry is used to mark the end of pairs which need to be | |
154 | restored during finalization of this block. */ | |
046bfc77 | 155 | static VEC(tree,heap) *const_and_copies_stack; |
da43203c | 156 | |
4ee9c684 | 157 | /* Track whether or not we have changed the control flow graph. */ |
158 | static bool cfg_altered; | |
159 | ||
35c15734 | 160 | /* Bitmap of blocks that have had EH statements cleaned. We should |
0870fd6e | 161 | remove their dead edges eventually. */ |
35c15734 | 162 | static bitmap need_eh_cleanup; |
163 | ||
4ee9c684 | 164 | /* Statistics for dominator optimizations. */ |
165 | struct opt_stats_d | |
166 | { | |
167 | long num_stmts; | |
168 | long num_exprs_considered; | |
169 | long num_re; | |
88dbf20f | 170 | long num_const_prop; |
171 | long num_copy_prop; | |
4ee9c684 | 172 | }; |
173 | ||
d0d897b6 | 174 | static struct opt_stats_d opt_stats; |
175 | ||
4ee9c684 | 176 | /* Local functions. */ |
6bf320fb | 177 | static void optimize_stmt (basic_block, gimple_stmt_iterator); |
75a70cf9 | 178 | static tree lookup_avail_expr (gimple, bool); |
4ee9c684 | 179 | static hashval_t avail_expr_hash (const void *); |
23ace16d | 180 | static hashval_t real_avail_expr_hash (const void *); |
4ee9c684 | 181 | static int avail_expr_eq (const void *, const void *); |
182 | static void htab_statistics (FILE *, htab_t); | |
7aab1427 | 183 | static void record_cond (cond_equivalence *); |
da43203c | 184 | static void record_const_or_copy (tree, tree); |
185 | static void record_equality (tree, tree); | |
2f0993e7 | 186 | static void record_equivalences_from_phis (basic_block); |
187 | static void record_equivalences_from_incoming_edge (basic_block); | |
e08ff65a | 188 | static void eliminate_redundant_computations (gimple_stmt_iterator *); |
75a70cf9 | 189 | static void record_equivalences_from_stmt (gimple, int); |
62b180e1 | 190 | static void dom_thread_across_edge (struct dom_walk_data *, edge); |
6bf320fb | 191 | static void dom_opt_leave_block (struct dom_walk_data *, basic_block); |
192 | static void dom_opt_enter_block (struct dom_walk_data *, basic_block); | |
9c629f0e | 193 | static void remove_local_expressions_from_table (void); |
da43203c | 194 | static void restore_vars_to_original_value (void); |
c0735efa | 195 | static edge single_incoming_edge_ignoring_loop_edges (basic_block); |
4ee9c684 | 196 | |
88dbf20f | 197 | |
75a70cf9 | 198 | /* Given a statement STMT, initialize the hash table element pointed to |
199 | by ELEMENT. */ | |
200 | ||
201 | static void | |
202 | initialize_hash_element (gimple stmt, tree lhs, | |
203 | struct expr_hash_elt *element) | |
204 | { | |
205 | enum gimple_code code = gimple_code (stmt); | |
206 | struct hashable_expr *expr = &element->expr; | |
207 | ||
208 | if (code == GIMPLE_ASSIGN) | |
209 | { | |
210 | enum tree_code subcode = gimple_assign_rhs_code (stmt); | |
211 | ||
75a70cf9 | 212 | switch (get_gimple_rhs_class (subcode)) |
213 | { | |
214 | case GIMPLE_SINGLE_RHS: | |
00f4f705 | 215 | expr->kind = EXPR_SINGLE; |
6140195d | 216 | expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt)); |
00f4f705 | 217 | expr->ops.single.rhs = gimple_assign_rhs1 (stmt); |
218 | break; | |
75a70cf9 | 219 | case GIMPLE_UNARY_RHS: |
00f4f705 | 220 | expr->kind = EXPR_UNARY; |
75a70cf9 | 221 | expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); |
00f4f705 | 222 | expr->ops.unary.op = subcode; |
223 | expr->ops.unary.opnd = gimple_assign_rhs1 (stmt); | |
224 | break; | |
75a70cf9 | 225 | case GIMPLE_BINARY_RHS: |
00f4f705 | 226 | expr->kind = EXPR_BINARY; |
75a70cf9 | 227 | expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); |
00f4f705 | 228 | expr->ops.binary.op = subcode; |
229 | expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt); | |
230 | expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt); | |
231 | break; | |
232 | case GIMPLE_TERNARY_RHS: | |
233 | expr->kind = EXPR_TERNARY; | |
234 | expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
235 | expr->ops.ternary.op = subcode; | |
236 | expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt); | |
237 | expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt); | |
238 | expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt); | |
239 | break; | |
75a70cf9 | 240 | default: |
241 | gcc_unreachable (); | |
242 | } | |
243 | } | |
244 | else if (code == GIMPLE_COND) | |
245 | { | |
246 | expr->type = boolean_type_node; | |
247 | expr->kind = EXPR_BINARY; | |
248 | expr->ops.binary.op = gimple_cond_code (stmt); | |
249 | expr->ops.binary.opnd0 = gimple_cond_lhs (stmt); | |
250 | expr->ops.binary.opnd1 = gimple_cond_rhs (stmt); | |
251 | } | |
252 | else if (code == GIMPLE_CALL) | |
253 | { | |
254 | size_t nargs = gimple_call_num_args (stmt); | |
255 | size_t i; | |
256 | ||
257 | gcc_assert (gimple_call_lhs (stmt)); | |
258 | ||
259 | expr->type = TREE_TYPE (gimple_call_lhs (stmt)); | |
260 | expr->kind = EXPR_CALL; | |
fb049fba | 261 | expr->ops.call.fn_from = stmt; |
75a70cf9 | 262 | |
263 | if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)) | |
264 | expr->ops.call.pure = true; | |
48e1416a | 265 | else |
75a70cf9 | 266 | expr->ops.call.pure = false; |
267 | ||
268 | expr->ops.call.nargs = nargs; | |
889ef038 | 269 | expr->ops.call.args = XCNEWVEC (tree, nargs); |
75a70cf9 | 270 | for (i = 0; i < nargs; i++) |
271 | expr->ops.call.args[i] = gimple_call_arg (stmt, i); | |
272 | } | |
273 | else if (code == GIMPLE_SWITCH) | |
274 | { | |
275 | expr->type = TREE_TYPE (gimple_switch_index (stmt)); | |
276 | expr->kind = EXPR_SINGLE; | |
277 | expr->ops.single.rhs = gimple_switch_index (stmt); | |
278 | } | |
279 | else if (code == GIMPLE_GOTO) | |
280 | { | |
281 | expr->type = TREE_TYPE (gimple_goto_dest (stmt)); | |
282 | expr->kind = EXPR_SINGLE; | |
283 | expr->ops.single.rhs = gimple_goto_dest (stmt); | |
284 | } | |
889ef038 | 285 | else if (code == GIMPLE_PHI) |
286 | { | |
287 | size_t nargs = gimple_phi_num_args (stmt); | |
288 | size_t i; | |
289 | ||
290 | expr->type = TREE_TYPE (gimple_phi_result (stmt)); | |
291 | expr->kind = EXPR_PHI; | |
292 | expr->ops.phi.nargs = nargs; | |
293 | expr->ops.phi.args = XCNEWVEC (tree, nargs); | |
294 | ||
295 | for (i = 0; i < nargs; i++) | |
296 | expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i); | |
297 | } | |
75a70cf9 | 298 | else |
299 | gcc_unreachable (); | |
300 | ||
301 | element->lhs = lhs; | |
302 | element->stmt = stmt; | |
303 | element->hash = avail_expr_hash (element); | |
304 | element->stamp = element; | |
305 | } | |
306 | ||
307 | /* Given a conditional expression COND as a tree, initialize | |
308 | a hashable_expr expression EXPR. The conditional must be a | |
309 | comparison or logical negation. A constant or a variable is | |
310 | not permitted. */ | |
311 | ||
312 | static void | |
313 | initialize_expr_from_cond (tree cond, struct hashable_expr *expr) | |
314 | { | |
315 | expr->type = boolean_type_node; | |
48e1416a | 316 | |
75a70cf9 | 317 | if (COMPARISON_CLASS_P (cond)) |
318 | { | |
319 | expr->kind = EXPR_BINARY; | |
320 | expr->ops.binary.op = TREE_CODE (cond); | |
321 | expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0); | |
322 | expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1); | |
323 | } | |
324 | else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) | |
325 | { | |
326 | expr->kind = EXPR_UNARY; | |
327 | expr->ops.unary.op = TRUTH_NOT_EXPR; | |
328 | expr->ops.unary.opnd = TREE_OPERAND (cond, 0); | |
329 | } | |
330 | else | |
331 | gcc_unreachable (); | |
332 | } | |
333 | ||
334 | /* Given a hashable_expr expression EXPR and an LHS, | |
335 | initialize the hash table element pointed to by ELEMENT. */ | |
336 | ||
337 | static void | |
338 | initialize_hash_element_from_expr (struct hashable_expr *expr, | |
339 | tree lhs, | |
340 | struct expr_hash_elt *element) | |
341 | { | |
342 | element->expr = *expr; | |
343 | element->lhs = lhs; | |
344 | element->stmt = NULL; | |
345 | element->hash = avail_expr_hash (element); | |
346 | element->stamp = element; | |
347 | } | |
348 | ||
349 | /* Compare two hashable_expr structures for equivalence. | |
350 | They are considered equivalent when the the expressions | |
351 | they denote must necessarily be equal. The logic is intended | |
352 | to follow that of operand_equal_p in fold-const.c */ | |
353 | ||
354 | static bool | |
355 | hashable_expr_equal_p (const struct hashable_expr *expr0, | |
356 | const struct hashable_expr *expr1) | |
357 | { | |
358 | tree type0 = expr0->type; | |
359 | tree type1 = expr1->type; | |
360 | ||
361 | /* If either type is NULL, there is nothing to check. */ | |
362 | if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE)) | |
363 | return false; | |
364 | ||
365 | /* If both types don't have the same signedness, precision, and mode, | |
366 | then we can't consider them equal. */ | |
367 | if (type0 != type1 | |
368 | && (TREE_CODE (type0) == ERROR_MARK | |
369 | || TREE_CODE (type1) == ERROR_MARK | |
370 | || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1) | |
371 | || TYPE_PRECISION (type0) != TYPE_PRECISION (type1) | |
372 | || TYPE_MODE (type0) != TYPE_MODE (type1))) | |
373 | return false; | |
374 | ||
375 | if (expr0->kind != expr1->kind) | |
376 | return false; | |
377 | ||
378 | switch (expr0->kind) | |
379 | { | |
380 | case EXPR_SINGLE: | |
381 | return operand_equal_p (expr0->ops.single.rhs, | |
382 | expr1->ops.single.rhs, 0); | |
383 | ||
384 | case EXPR_UNARY: | |
385 | if (expr0->ops.unary.op != expr1->ops.unary.op) | |
386 | return false; | |
387 | ||
d9659041 | 388 | if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op) |
75a70cf9 | 389 | || expr0->ops.unary.op == NON_LVALUE_EXPR) |
390 | && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type)) | |
391 | return false; | |
392 | ||
393 | return operand_equal_p (expr0->ops.unary.opnd, | |
394 | expr1->ops.unary.opnd, 0); | |
395 | ||
396 | case EXPR_BINARY: | |
00f4f705 | 397 | if (expr0->ops.binary.op != expr1->ops.binary.op) |
398 | return false; | |
399 | ||
400 | if (operand_equal_p (expr0->ops.binary.opnd0, | |
401 | expr1->ops.binary.opnd0, 0) | |
402 | && operand_equal_p (expr0->ops.binary.opnd1, | |
403 | expr1->ops.binary.opnd1, 0)) | |
404 | return true; | |
405 | ||
406 | /* For commutative ops, allow the other order. */ | |
407 | return (commutative_tree_code (expr0->ops.binary.op) | |
408 | && operand_equal_p (expr0->ops.binary.opnd0, | |
409 | expr1->ops.binary.opnd1, 0) | |
410 | && operand_equal_p (expr0->ops.binary.opnd1, | |
411 | expr1->ops.binary.opnd0, 0)); | |
412 | ||
413 | case EXPR_TERNARY: | |
414 | if (expr0->ops.ternary.op != expr1->ops.ternary.op | |
415 | || !operand_equal_p (expr0->ops.ternary.opnd2, | |
416 | expr1->ops.ternary.opnd2, 0)) | |
417 | return false; | |
418 | ||
419 | if (operand_equal_p (expr0->ops.ternary.opnd0, | |
420 | expr1->ops.ternary.opnd0, 0) | |
421 | && operand_equal_p (expr0->ops.ternary.opnd1, | |
422 | expr1->ops.ternary.opnd1, 0)) | |
423 | return true; | |
424 | ||
425 | /* For commutative ops, allow the other order. */ | |
426 | return (commutative_ternary_tree_code (expr0->ops.ternary.op) | |
427 | && operand_equal_p (expr0->ops.ternary.opnd0, | |
428 | expr1->ops.ternary.opnd1, 0) | |
429 | && operand_equal_p (expr0->ops.ternary.opnd1, | |
430 | expr1->ops.ternary.opnd0, 0)); | |
75a70cf9 | 431 | |
432 | case EXPR_CALL: | |
433 | { | |
434 | size_t i; | |
435 | ||
436 | /* If the calls are to different functions, then they | |
437 | clearly cannot be equal. */ | |
fb049fba | 438 | if (!gimple_call_same_target_p (expr0->ops.call.fn_from, |
439 | expr1->ops.call.fn_from)) | |
75a70cf9 | 440 | return false; |
441 | ||
442 | if (! expr0->ops.call.pure) | |
443 | return false; | |
444 | ||
445 | if (expr0->ops.call.nargs != expr1->ops.call.nargs) | |
446 | return false; | |
447 | ||
448 | for (i = 0; i < expr0->ops.call.nargs; i++) | |
449 | if (! operand_equal_p (expr0->ops.call.args[i], | |
450 | expr1->ops.call.args[i], 0)) | |
451 | return false; | |
452 | ||
453 | return true; | |
454 | } | |
48e1416a | 455 | |
889ef038 | 456 | case EXPR_PHI: |
457 | { | |
458 | size_t i; | |
459 | ||
460 | if (expr0->ops.phi.nargs != expr1->ops.phi.nargs) | |
461 | return false; | |
462 | ||
463 | for (i = 0; i < expr0->ops.phi.nargs; i++) | |
464 | if (! operand_equal_p (expr0->ops.phi.args[i], | |
465 | expr1->ops.phi.args[i], 0)) | |
466 | return false; | |
467 | ||
468 | return true; | |
469 | } | |
470 | ||
75a70cf9 | 471 | default: |
472 | gcc_unreachable (); | |
473 | } | |
474 | } | |
475 | ||
476 | /* Compute a hash value for a hashable_expr value EXPR and a | |
477 | previously accumulated hash value VAL. If two hashable_expr | |
478 | values compare equal with hashable_expr_equal_p, they must | |
479 | hash to the same value, given an identical value of VAL. | |
480 | The logic is intended to follow iterative_hash_expr in tree.c. */ | |
481 | ||
482 | static hashval_t | |
483 | iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val) | |
484 | { | |
485 | switch (expr->kind) | |
486 | { | |
487 | case EXPR_SINGLE: | |
488 | val = iterative_hash_expr (expr->ops.single.rhs, val); | |
489 | break; | |
490 | ||
491 | case EXPR_UNARY: | |
492 | val = iterative_hash_object (expr->ops.unary.op, val); | |
493 | ||
494 | /* Make sure to include signedness in the hash computation. | |
495 | Don't hash the type, that can lead to having nodes which | |
496 | compare equal according to operand_equal_p, but which | |
497 | have different hash codes. */ | |
d9659041 | 498 | if (CONVERT_EXPR_CODE_P (expr->ops.unary.op) |
75a70cf9 | 499 | || expr->ops.unary.op == NON_LVALUE_EXPR) |
500 | val += TYPE_UNSIGNED (expr->type); | |
501 | ||
502 | val = iterative_hash_expr (expr->ops.unary.opnd, val); | |
503 | break; | |
504 | ||
505 | case EXPR_BINARY: | |
506 | val = iterative_hash_object (expr->ops.binary.op, val); | |
507 | if (commutative_tree_code (expr->ops.binary.op)) | |
00f4f705 | 508 | val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0, |
509 | expr->ops.binary.opnd1, val); | |
75a70cf9 | 510 | else |
511 | { | |
512 | val = iterative_hash_expr (expr->ops.binary.opnd0, val); | |
513 | val = iterative_hash_expr (expr->ops.binary.opnd1, val); | |
514 | } | |
515 | break; | |
516 | ||
00f4f705 | 517 | case EXPR_TERNARY: |
518 | val = iterative_hash_object (expr->ops.ternary.op, val); | |
519 | if (commutative_ternary_tree_code (expr->ops.ternary.op)) | |
520 | val = iterative_hash_exprs_commutative (expr->ops.ternary.opnd0, | |
521 | expr->ops.ternary.opnd1, val); | |
522 | else | |
523 | { | |
524 | val = iterative_hash_expr (expr->ops.ternary.opnd0, val); | |
525 | val = iterative_hash_expr (expr->ops.ternary.opnd1, val); | |
526 | } | |
527 | val = iterative_hash_expr (expr->ops.ternary.opnd2, val); | |
528 | break; | |
529 | ||
75a70cf9 | 530 | case EXPR_CALL: |
531 | { | |
532 | size_t i; | |
533 | enum tree_code code = CALL_EXPR; | |
fb049fba | 534 | gimple fn_from; |
75a70cf9 | 535 | |
536 | val = iterative_hash_object (code, val); | |
fb049fba | 537 | fn_from = expr->ops.call.fn_from; |
538 | if (gimple_call_internal_p (fn_from)) | |
539 | val = iterative_hash_hashval_t | |
540 | ((hashval_t) gimple_call_internal_fn (fn_from), val); | |
541 | else | |
542 | val = iterative_hash_expr (gimple_call_fn (fn_from), val); | |
75a70cf9 | 543 | for (i = 0; i < expr->ops.call.nargs; i++) |
544 | val = iterative_hash_expr (expr->ops.call.args[i], val); | |
545 | } | |
546 | break; | |
48e1416a | 547 | |
889ef038 | 548 | case EXPR_PHI: |
549 | { | |
550 | size_t i; | |
551 | ||
552 | for (i = 0; i < expr->ops.phi.nargs; i++) | |
553 | val = iterative_hash_expr (expr->ops.phi.args[i], val); | |
554 | } | |
555 | break; | |
556 | ||
75a70cf9 | 557 | default: |
558 | gcc_unreachable (); | |
559 | } | |
560 | ||
561 | return val; | |
562 | } | |
563 | ||
564 | /* Print a diagnostic dump of an expression hash table entry. */ | |
565 | ||
566 | static void | |
567 | print_expr_hash_elt (FILE * stream, const struct expr_hash_elt *element) | |
568 | { | |
569 | if (element->stmt) | |
570 | fprintf (stream, "STMT "); | |
571 | else | |
572 | fprintf (stream, "COND "); | |
573 | ||
574 | if (element->lhs) | |
575 | { | |
576 | print_generic_expr (stream, element->lhs, 0); | |
577 | fprintf (stream, " = "); | |
578 | } | |
48e1416a | 579 | |
75a70cf9 | 580 | switch (element->expr.kind) |
581 | { | |
582 | case EXPR_SINGLE: | |
583 | print_generic_expr (stream, element->expr.ops.single.rhs, 0); | |
584 | break; | |
585 | ||
586 | case EXPR_UNARY: | |
587 | fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]); | |
588 | print_generic_expr (stream, element->expr.ops.unary.opnd, 0); | |
589 | break; | |
590 | ||
591 | case EXPR_BINARY: | |
592 | print_generic_expr (stream, element->expr.ops.binary.opnd0, 0); | |
593 | fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]); | |
594 | print_generic_expr (stream, element->expr.ops.binary.opnd1, 0); | |
595 | break; | |
596 | ||
00f4f705 | 597 | case EXPR_TERNARY: |
598 | fprintf (stream, " %s <", tree_code_name[element->expr.ops.ternary.op]); | |
599 | print_generic_expr (stream, element->expr.ops.ternary.opnd0, 0); | |
600 | fputs (", ", stream); | |
601 | print_generic_expr (stream, element->expr.ops.ternary.opnd1, 0); | |
602 | fputs (", ", stream); | |
603 | print_generic_expr (stream, element->expr.ops.ternary.opnd2, 0); | |
604 | fputs (">", stream); | |
605 | break; | |
606 | ||
75a70cf9 | 607 | case EXPR_CALL: |
608 | { | |
609 | size_t i; | |
610 | size_t nargs = element->expr.ops.call.nargs; | |
fb049fba | 611 | gimple fn_from; |
612 | ||
613 | fn_from = element->expr.ops.call.fn_from; | |
614 | if (gimple_call_internal_p (fn_from)) | |
615 | fputs (internal_fn_name (gimple_call_internal_fn (fn_from)), | |
616 | stream); | |
617 | else | |
618 | print_generic_expr (stream, gimple_call_fn (fn_from), 0); | |
75a70cf9 | 619 | fprintf (stream, " ("); |
620 | for (i = 0; i < nargs; i++) | |
621 | { | |
622 | print_generic_expr (stream, element->expr.ops.call.args[i], 0); | |
623 | if (i + 1 < nargs) | |
624 | fprintf (stream, ", "); | |
625 | } | |
626 | fprintf (stream, ")"); | |
627 | } | |
628 | break; | |
889ef038 | 629 | |
630 | case EXPR_PHI: | |
631 | { | |
632 | size_t i; | |
633 | size_t nargs = element->expr.ops.phi.nargs; | |
634 | ||
635 | fprintf (stream, "PHI <"); | |
636 | for (i = 0; i < nargs; i++) | |
637 | { | |
638 | print_generic_expr (stream, element->expr.ops.phi.args[i], 0); | |
639 | if (i + 1 < nargs) | |
640 | fprintf (stream, ", "); | |
641 | } | |
642 | fprintf (stream, ">"); | |
643 | } | |
644 | break; | |
75a70cf9 | 645 | } |
646 | fprintf (stream, "\n"); | |
647 | ||
648 | if (element->stmt) | |
649 | { | |
650 | fprintf (stream, " "); | |
651 | print_gimple_stmt (stream, element->stmt, 0, 0); | |
652 | } | |
653 | } | |
654 | ||
655 | /* Delete an expr_hash_elt and reclaim its storage. */ | |
656 | ||
657 | static void | |
658 | free_expr_hash_elt (void *elt) | |
659 | { | |
660 | struct expr_hash_elt *element = ((struct expr_hash_elt *)elt); | |
661 | ||
662 | if (element->expr.kind == EXPR_CALL) | |
663 | free (element->expr.ops.call.args); | |
664 | ||
889ef038 | 665 | if (element->expr.kind == EXPR_PHI) |
666 | free (element->expr.ops.phi.args); | |
667 | ||
75a70cf9 | 668 | free (element); |
669 | } | |
670 | ||
2f0993e7 | 671 | /* Allocate an EDGE_INFO for edge E and attach it to E. |
672 | Return the new EDGE_INFO structure. */ | |
673 | ||
674 | static struct edge_info * | |
675 | allocate_edge_info (edge e) | |
676 | { | |
677 | struct edge_info *edge_info; | |
678 | ||
945865c5 | 679 | edge_info = XCNEW (struct edge_info); |
2f0993e7 | 680 | |
681 | e->aux = edge_info; | |
682 | return edge_info; | |
683 | } | |
684 | ||
685 | /* Free all EDGE_INFO structures associated with edges in the CFG. | |
640e9781 | 686 | If a particular edge can be threaded, copy the redirection |
2f0993e7 | 687 | target from the EDGE_INFO structure into the edge's AUX field |
688 | as required by code to update the CFG and SSA graph for | |
689 | jump threading. */ | |
690 | ||
691 | static void | |
692 | free_all_edge_infos (void) | |
693 | { | |
694 | basic_block bb; | |
695 | edge_iterator ei; | |
696 | edge e; | |
697 | ||
698 | FOR_EACH_BB (bb) | |
699 | { | |
700 | FOR_EACH_EDGE (e, ei, bb->preds) | |
701 | { | |
945865c5 | 702 | struct edge_info *edge_info = (struct edge_info *) e->aux; |
2f0993e7 | 703 | |
704 | if (edge_info) | |
705 | { | |
2f0993e7 | 706 | if (edge_info->cond_equivalences) |
7aab1427 | 707 | VEC_free (cond_equivalence, heap, edge_info->cond_equivalences); |
2f0993e7 | 708 | free (edge_info); |
3cebc9d2 | 709 | e->aux = NULL; |
2f0993e7 | 710 | } |
711 | } | |
712 | } | |
713 | } | |
714 | ||
48e1416a | 715 | /* Jump threading, redundancy elimination and const/copy propagation. |
4ee9c684 | 716 | |
4ee9c684 | 717 | This pass may expose new symbols that need to be renamed into SSA. For |
718 | every new symbol exposed, its corresponding bit will be set in | |
591c2a30 | 719 | VARS_TO_RENAME. */ |
4ee9c684 | 720 | |
2a1990e9 | 721 | static unsigned int |
4ee9c684 | 722 | tree_ssa_dominator_optimize (void) |
723 | { | |
4ee9c684 | 724 | struct dom_walk_data walk_data; |
4ee9c684 | 725 | |
03ec6c0e | 726 | memset (&opt_stats, 0, sizeof (opt_stats)); |
727 | ||
4ee9c684 | 728 | /* Create our hash tables. */ |
75a70cf9 | 729 | avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt); |
730 | avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20); | |
046bfc77 | 731 | const_and_copies_stack = VEC_alloc (tree, heap, 20); |
27335ffd | 732 | need_eh_cleanup = BITMAP_ALLOC (NULL); |
4ee9c684 | 733 | |
734 | /* Setup callbacks for the generic dominator tree walker. */ | |
4ee9c684 | 735 | walk_data.dom_direction = CDI_DOMINATORS; |
180d0339 | 736 | walk_data.initialize_block_local_data = NULL; |
6bf320fb | 737 | walk_data.before_dom_children = dom_opt_enter_block; |
738 | walk_data.after_dom_children = dom_opt_leave_block; | |
4ee9c684 | 739 | /* Right now we only attach a dummy COND_EXPR to the global data pointer. |
740 | When we attach more stuff we'll need to fill this out with a real | |
741 | structure. */ | |
742 | walk_data.global_data = NULL; | |
180d0339 | 743 | walk_data.block_local_data_size = 0; |
4ee9c684 | 744 | |
745 | /* Now initialize the dominator walker. */ | |
746 | init_walk_dominator_tree (&walk_data); | |
747 | ||
4ee9c684 | 748 | calculate_dominance_info (CDI_DOMINATORS); |
9a17dd7d | 749 | cfg_altered = false; |
4ee9c684 | 750 | |
7e0311ae | 751 | /* We need to know loop structures in order to avoid destroying them |
752 | in jump threading. Note that we still can e.g. thread through loop | |
753 | headers to an exit edge, or through loop header to the loop body, assuming | |
754 | that we update the loop info. */ | |
755 | loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES); | |
388d1fc1 | 756 | |
f003f9fd | 757 | /* Initialize the value-handle array. */ |
758 | threadedge_initialize_values (); | |
759 | ||
62b180e1 | 760 | /* We need accurate information regarding back edges in the CFG |
f0b5f617 | 761 | for jump threading; this may include back edges that are not part of |
7e0311ae | 762 | a single loop. */ |
62b180e1 | 763 | mark_dfs_back_edges (); |
48e1416a | 764 | |
62b180e1 | 765 | /* Recursively walk the dominator tree optimizing statements. */ |
766 | walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); | |
4ee9c684 | 767 | |
62b180e1 | 768 | { |
75a70cf9 | 769 | gimple_stmt_iterator gsi; |
62b180e1 | 770 | basic_block bb; |
771 | FOR_EACH_BB (bb) | |
07eeb468 | 772 | { |
773 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
75a70cf9 | 774 | update_stmt_if_modified (gsi_stmt (gsi)); |
22aa74c4 | 775 | } |
62b180e1 | 776 | } |
0638045e | 777 | |
62b180e1 | 778 | /* If we exposed any new variables, go ahead and put them into |
779 | SSA form now, before we handle jump threading. This simplifies | |
780 | interactions between rewriting of _DECL nodes into SSA form | |
781 | and rewriting SSA_NAME nodes into SSA form after block | |
782 | duplication and CFG manipulation. */ | |
783 | update_ssa (TODO_update_ssa); | |
388d1fc1 | 784 | |
62b180e1 | 785 | free_all_edge_infos (); |
388d1fc1 | 786 | |
62b180e1 | 787 | /* Thread jumps, creating duplicate blocks as needed. */ |
7e0311ae | 788 | cfg_altered |= thread_through_all_blocks (first_pass_instance); |
4ee9c684 | 789 | |
9a17dd7d | 790 | if (cfg_altered) |
791 | free_dominance_info (CDI_DOMINATORS); | |
792 | ||
62b180e1 | 793 | /* Removal of statements may make some EH edges dead. Purge |
794 | such edges from the CFG as needed. */ | |
795 | if (!bitmap_empty_p (need_eh_cleanup)) | |
796 | { | |
5ec0139d | 797 | unsigned i; |
798 | bitmap_iterator bi; | |
799 | ||
800 | /* Jump threading may have created forwarder blocks from blocks | |
801 | needing EH cleanup; the new successor of these blocks, which | |
802 | has inherited from the original block, needs the cleanup. */ | |
803 | EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi) | |
804 | { | |
805 | basic_block bb = BASIC_BLOCK (i); | |
07eeb468 | 806 | if (bb |
807 | && single_succ_p (bb) | |
5ec0139d | 808 | && (single_succ_edge (bb)->flags & EDGE_EH) == 0) |
809 | { | |
810 | bitmap_clear_bit (need_eh_cleanup, i); | |
811 | bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index); | |
812 | } | |
813 | } | |
814 | ||
75a70cf9 | 815 | gimple_purge_all_dead_eh_edges (need_eh_cleanup); |
62b180e1 | 816 | bitmap_zero (need_eh_cleanup); |
817 | } | |
4ee9c684 | 818 | |
581f8050 | 819 | statistics_counter_event (cfun, "Redundant expressions eliminated", |
820 | opt_stats.num_re); | |
821 | statistics_counter_event (cfun, "Constants propagated", | |
822 | opt_stats.num_const_prop); | |
823 | statistics_counter_event (cfun, "Copies propagated", | |
824 | opt_stats.num_copy_prop); | |
825 | ||
4ee9c684 | 826 | /* Debugging dumps. */ |
827 | if (dump_file && (dump_flags & TDF_STATS)) | |
828 | dump_dominator_optimization_stats (dump_file); | |
829 | ||
7e0311ae | 830 | loop_optimizer_finalize (); |
831 | ||
62b180e1 | 832 | /* Delete our main hashtable. */ |
4ee9c684 | 833 | htab_delete (avail_exprs); |
4ee9c684 | 834 | |
835 | /* And finalize the dominator walker. */ | |
836 | fini_walk_dominator_tree (&walk_data); | |
a8ddfbad | 837 | |
8dbf774a | 838 | /* Free asserted bitmaps and stacks. */ |
27335ffd | 839 | BITMAP_FREE (need_eh_cleanup); |
48e1416a | 840 | |
75a70cf9 | 841 | VEC_free (expr_hash_elt_t, heap, avail_exprs_stack); |
046bfc77 | 842 | VEC_free (tree, heap, const_and_copies_stack); |
48e1416a | 843 | |
f003f9fd | 844 | /* Free the value-handle array. */ |
845 | threadedge_finalize_values (); | |
846 | ssa_name_values = NULL; | |
847 | ||
2a1990e9 | 848 | return 0; |
4ee9c684 | 849 | } |
850 | ||
851 | static bool | |
852 | gate_dominator (void) | |
853 | { | |
854 | return flag_tree_dom != 0; | |
855 | } | |
856 | ||
48e1416a | 857 | struct gimple_opt_pass pass_dominator = |
4ee9c684 | 858 | { |
20099e35 | 859 | { |
860 | GIMPLE_PASS, | |
4ee9c684 | 861 | "dom", /* name */ |
862 | gate_dominator, /* gate */ | |
863 | tree_ssa_dominator_optimize, /* execute */ | |
864 | NULL, /* sub */ | |
865 | NULL, /* next */ | |
866 | 0, /* static_pass_number */ | |
867 | TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */ | |
2f8eb909 | 868 | PROP_cfg | PROP_ssa, /* properties_required */ |
4ee9c684 | 869 | 0, /* properties_provided */ |
b6246c40 | 870 | 0, /* properties_destroyed */ |
4ee9c684 | 871 | 0, /* todo_flags_start */ |
a2676c4f | 872 | TODO_cleanup_cfg |
88dbf20f | 873 | | TODO_update_ssa |
a2676c4f | 874 | | TODO_verify_ssa |
771e2890 | 875 | | TODO_verify_flow /* todo_flags_finish */ |
20099e35 | 876 | } |
4ee9c684 | 877 | }; |
878 | ||
879 | ||
75a70cf9 | 880 | /* Given a conditional statement CONDSTMT, convert the |
881 | condition to a canonical form. */ | |
54aceb26 | 882 | |
883 | static void | |
75a70cf9 | 884 | canonicalize_comparison (gimple condstmt) |
54aceb26 | 885 | { |
54aceb26 | 886 | tree op0; |
887 | tree op1; | |
75a70cf9 | 888 | enum tree_code code; |
54aceb26 | 889 | |
75a70cf9 | 890 | gcc_assert (gimple_code (condstmt) == GIMPLE_COND); |
54aceb26 | 891 | |
75a70cf9 | 892 | op0 = gimple_cond_lhs (condstmt); |
893 | op1 = gimple_cond_rhs (condstmt); | |
894 | ||
895 | code = gimple_cond_code (condstmt); | |
54aceb26 | 896 | |
897 | /* If it would be profitable to swap the operands, then do so to | |
898 | canonicalize the statement, enabling better optimization. | |
899 | ||
900 | By placing canonicalization of such expressions here we | |
901 | transparently keep statements in canonical form, even | |
902 | when the statement is modified. */ | |
903 | if (tree_swap_operands_p (op0, op1, false)) | |
904 | { | |
905 | /* For relationals we need to swap the operands | |
906 | and change the code. */ | |
907 | if (code == LT_EXPR | |
908 | || code == GT_EXPR | |
909 | || code == LE_EXPR | |
910 | || code == GE_EXPR) | |
911 | { | |
75a70cf9 | 912 | code = swap_tree_comparison (code); |
913 | ||
914 | gimple_cond_set_code (condstmt, code); | |
915 | gimple_cond_set_lhs (condstmt, op1); | |
916 | gimple_cond_set_rhs (condstmt, op0); | |
917 | ||
918 | update_stmt (condstmt); | |
54aceb26 | 919 | } |
920 | } | |
921 | } | |
4ee9c684 | 922 | |
4ee9c684 | 923 | /* Initialize local stacks for this optimizer and record equivalences |
924 | upon entry to BB. Equivalences can come from the edge traversed to | |
925 | reach BB or they may come from PHI nodes at the start of BB. */ | |
926 | ||
4ee9c684 | 927 | /* Remove all the expressions in LOCALS from TABLE, stopping when there are |
928 | LIMIT entries left in LOCALs. */ | |
929 | ||
930 | static void | |
9c629f0e | 931 | remove_local_expressions_from_table (void) |
4ee9c684 | 932 | { |
4ee9c684 | 933 | /* Remove all the expressions made available in this block. */ |
75a70cf9 | 934 | while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0) |
4ee9c684 | 935 | { |
75a70cf9 | 936 | expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack); |
04c3b49f | 937 | void **slot; |
9c629f0e | 938 | |
75a70cf9 | 939 | if (victim == NULL) |
9c629f0e | 940 | break; |
4ee9c684 | 941 | |
75a70cf9 | 942 | /* This must precede the actual removal from the hash table, |
943 | as ELEMENT and the table entry may share a call argument | |
944 | vector which will be freed during removal. */ | |
945 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
946 | { | |
947 | fprintf (dump_file, "<<<< "); | |
04c3b49f | 948 | print_expr_hash_elt (dump_file, victim); |
75a70cf9 | 949 | } |
950 | ||
04c3b49f | 951 | slot = htab_find_slot_with_hash (avail_exprs, |
952 | victim, victim->hash, NO_INSERT); | |
953 | gcc_assert (slot && *slot == (void *) victim); | |
954 | htab_clear_slot (avail_exprs, slot); | |
4ee9c684 | 955 | } |
956 | } | |
957 | ||
da43203c | 958 | /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore |
959 | CONST_AND_COPIES to its original state, stopping when we hit a | |
960 | NULL marker. */ | |
4ee9c684 | 961 | |
962 | static void | |
da43203c | 963 | restore_vars_to_original_value (void) |
4ee9c684 | 964 | { |
046bfc77 | 965 | while (VEC_length (tree, const_and_copies_stack) > 0) |
4ee9c684 | 966 | { |
967 | tree prev_value, dest; | |
968 | ||
046bfc77 | 969 | dest = VEC_pop (tree, const_and_copies_stack); |
4ee9c684 | 970 | |
da43203c | 971 | if (dest == NULL) |
972 | break; | |
973 | ||
75a70cf9 | 974 | if (dump_file && (dump_flags & TDF_DETAILS)) |
975 | { | |
976 | fprintf (dump_file, "<<<< COPY "); | |
977 | print_generic_expr (dump_file, dest, 0); | |
978 | fprintf (dump_file, " = "); | |
979 | print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0); | |
980 | fprintf (dump_file, "\n"); | |
981 | } | |
982 | ||
046bfc77 | 983 | prev_value = VEC_pop (tree, const_and_copies_stack); |
f003f9fd | 984 | set_ssa_name_value (dest, prev_value); |
4ee9c684 | 985 | } |
986 | } | |
987 | ||
62b180e1 | 988 | /* A trivial wrapper so that we can present the generic jump |
989 | threading code with a simple API for simplifying statements. */ | |
990 | static tree | |
75a70cf9 | 991 | simplify_stmt_for_jump_threading (gimple stmt, |
992 | gimple within_stmt ATTRIBUTE_UNUSED) | |
62b180e1 | 993 | { |
994 | return lookup_avail_expr (stmt, false); | |
995 | } | |
996 | ||
997 | /* Wrapper for common code to attempt to thread an edge. For example, | |
998 | it handles lazily building the dummy condition and the bookkeeping | |
999 | when jump threading is successful. */ | |
1000 | ||
1001 | static void | |
1002 | dom_thread_across_edge (struct dom_walk_data *walk_data, edge e) | |
1003 | { | |
62b180e1 | 1004 | if (! walk_data->global_data) |
75a70cf9 | 1005 | { |
1006 | gimple dummy_cond = | |
1007 | gimple_build_cond (NE_EXPR, | |
1008 | integer_zero_node, integer_zero_node, | |
1009 | NULL, NULL); | |
1010 | walk_data->global_data = dummy_cond; | |
1011 | } | |
62b180e1 | 1012 | |
75a70cf9 | 1013 | thread_across_edge ((gimple) walk_data->global_data, e, false, |
62b180e1 | 1014 | &const_and_copies_stack, |
1015 | simplify_stmt_for_jump_threading); | |
1016 | } | |
1017 | ||
4ee9c684 | 1018 | /* PHI nodes can create equivalences too. |
1019 | ||
1020 | Ignoring any alternatives which are the same as the result, if | |
1021 | all the alternatives are equal, then the PHI node creates an | |
8dbf774a | 1022 | equivalence. */ |
6e9a4371 | 1023 | |
4ee9c684 | 1024 | static void |
2f0993e7 | 1025 | record_equivalences_from_phis (basic_block bb) |
4ee9c684 | 1026 | { |
75a70cf9 | 1027 | gimple_stmt_iterator gsi; |
48e1416a | 1028 | |
75a70cf9 | 1029 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
4ee9c684 | 1030 | { |
75a70cf9 | 1031 | gimple phi = gsi_stmt (gsi); |
1032 | ||
1033 | tree lhs = gimple_phi_result (phi); | |
4ee9c684 | 1034 | tree rhs = NULL; |
75a70cf9 | 1035 | size_t i; |
4ee9c684 | 1036 | |
75a70cf9 | 1037 | for (i = 0; i < gimple_phi_num_args (phi); i++) |
4ee9c684 | 1038 | { |
75a70cf9 | 1039 | tree t = gimple_phi_arg_def (phi, i); |
4ee9c684 | 1040 | |
2fb4af30 | 1041 | /* Ignore alternatives which are the same as our LHS. Since |
1042 | LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we | |
1043 | can simply compare pointers. */ | |
fcf57fc2 | 1044 | if (lhs == t) |
92527855 | 1045 | continue; |
1046 | ||
1047 | /* If we have not processed an alternative yet, then set | |
1048 | RHS to this alternative. */ | |
1049 | if (rhs == NULL) | |
1050 | rhs = t; | |
1051 | /* If we have processed an alternative (stored in RHS), then | |
1052 | see if it is equal to this one. If it isn't, then stop | |
1053 | the search. */ | |
1054 | else if (! operand_equal_for_phi_arg_p (rhs, t)) | |
4ee9c684 | 1055 | break; |
1056 | } | |
1057 | ||
1058 | /* If we had no interesting alternatives, then all the RHS alternatives | |
1059 | must have been the same as LHS. */ | |
1060 | if (!rhs) | |
1061 | rhs = lhs; | |
1062 | ||
1063 | /* If we managed to iterate through each PHI alternative without | |
1064 | breaking out of the loop, then we have a PHI which may create | |
1065 | a useful equivalence. We do not need to record unwind data for | |
1066 | this, since this is a true assignment and not an equivalence | |
365db11e | 1067 | inferred from a comparison. All uses of this ssa name are dominated |
4ee9c684 | 1068 | by this assignment, so unwinding just costs time and space. */ |
75a70cf9 | 1069 | if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs)) |
f003f9fd | 1070 | set_ssa_name_value (lhs, rhs); |
4ee9c684 | 1071 | } |
1072 | } | |
1073 | ||
c0735efa | 1074 | /* Ignoring loop backedges, if BB has precisely one incoming edge then |
1075 | return that edge. Otherwise return NULL. */ | |
1076 | static edge | |
1077 | single_incoming_edge_ignoring_loop_edges (basic_block bb) | |
1078 | { | |
1079 | edge retval = NULL; | |
1080 | edge e; | |
cd665a06 | 1081 | edge_iterator ei; |
c0735efa | 1082 | |
cd665a06 | 1083 | FOR_EACH_EDGE (e, ei, bb->preds) |
c0735efa | 1084 | { |
1085 | /* A loop back edge can be identified by the destination of | |
1086 | the edge dominating the source of the edge. */ | |
1087 | if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) | |
1088 | continue; | |
1089 | ||
1090 | /* If we have already seen a non-loop edge, then we must have | |
1091 | multiple incoming non-loop edges and thus we return NULL. */ | |
1092 | if (retval) | |
1093 | return NULL; | |
1094 | ||
1095 | /* This is the first non-loop incoming edge we have found. Record | |
1096 | it. */ | |
1097 | retval = e; | |
1098 | } | |
1099 | ||
1100 | return retval; | |
1101 | } | |
1102 | ||
4ee9c684 | 1103 | /* Record any equivalences created by the incoming edge to BB. If BB |
1104 | has more than one incoming edge, then no equivalence is created. */ | |
1105 | ||
1106 | static void | |
2f0993e7 | 1107 | record_equivalences_from_incoming_edge (basic_block bb) |
4ee9c684 | 1108 | { |
2f0993e7 | 1109 | edge e; |
4ee9c684 | 1110 | basic_block parent; |
2f0993e7 | 1111 | struct edge_info *edge_info; |
4ee9c684 | 1112 | |
0975351b | 1113 | /* If our parent block ended with a control statement, then we may be |
4ee9c684 | 1114 | able to record some equivalences based on which outgoing edge from |
1115 | the parent was followed. */ | |
1116 | parent = get_immediate_dominator (CDI_DOMINATORS, bb); | |
4ee9c684 | 1117 | |
2f0993e7 | 1118 | e = single_incoming_edge_ignoring_loop_edges (bb); |
4ee9c684 | 1119 | |
2f0993e7 | 1120 | /* If we had a single incoming edge from our parent block, then enter |
1121 | any data associated with the edge into our tables. */ | |
1122 | if (e && e->src == parent) | |
4ee9c684 | 1123 | { |
2f0993e7 | 1124 | unsigned int i; |
4ee9c684 | 1125 | |
945865c5 | 1126 | edge_info = (struct edge_info *) e->aux; |
4ee9c684 | 1127 | |
2f0993e7 | 1128 | if (edge_info) |
4ee9c684 | 1129 | { |
2f0993e7 | 1130 | tree lhs = edge_info->lhs; |
1131 | tree rhs = edge_info->rhs; | |
7aab1427 | 1132 | cond_equivalence *eq; |
2f0993e7 | 1133 | |
1134 | if (lhs) | |
1135 | record_equality (lhs, rhs); | |
1136 | ||
7aab1427 | 1137 | for (i = 0; VEC_iterate (cond_equivalence, |
1138 | edge_info->cond_equivalences, i, eq); ++i) | |
1139 | record_cond (eq); | |
4ee9c684 | 1140 | } |
1141 | } | |
4ee9c684 | 1142 | } |
1143 | ||
1144 | /* Dump SSA statistics on FILE. */ | |
1145 | ||
1146 | void | |
1147 | dump_dominator_optimization_stats (FILE *file) | |
1148 | { | |
4ee9c684 | 1149 | fprintf (file, "Total number of statements: %6ld\n\n", |
1150 | opt_stats.num_stmts); | |
1151 | fprintf (file, "Exprs considered for dominator optimizations: %6ld\n", | |
1152 | opt_stats.num_exprs_considered); | |
1153 | ||
4ee9c684 | 1154 | fprintf (file, "\nHash table statistics:\n"); |
1155 | ||
1156 | fprintf (file, " avail_exprs: "); | |
1157 | htab_statistics (file, avail_exprs); | |
1158 | } | |
1159 | ||
1160 | ||
1161 | /* Dump SSA statistics on stderr. */ | |
1162 | ||
4b987fac | 1163 | DEBUG_FUNCTION void |
4ee9c684 | 1164 | debug_dominator_optimization_stats (void) |
1165 | { | |
1166 | dump_dominator_optimization_stats (stderr); | |
1167 | } | |
1168 | ||
1169 | ||
1170 | /* Dump statistics for the hash table HTAB. */ | |
1171 | ||
1172 | static void | |
1173 | htab_statistics (FILE *file, htab_t htab) | |
1174 | { | |
1175 | fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", | |
1176 | (long) htab_size (htab), | |
1177 | (long) htab_elements (htab), | |
1178 | htab_collisions (htab)); | |
1179 | } | |
1180 | ||
75a70cf9 | 1181 | |
1182 | /* Enter condition equivalence into the expression hash table. | |
1183 | This indicates that a conditional expression has a known | |
1184 | boolean value. */ | |
4ee9c684 | 1185 | |
1186 | static void | |
7aab1427 | 1187 | record_cond (cond_equivalence *p) |
4ee9c684 | 1188 | { |
945865c5 | 1189 | struct expr_hash_elt *element = XCNEW (struct expr_hash_elt); |
4ee9c684 | 1190 | void **slot; |
1191 | ||
75a70cf9 | 1192 | initialize_hash_element_from_expr (&p->cond, p->value, element); |
4ee9c684 | 1193 | |
1194 | slot = htab_find_slot_with_hash (avail_exprs, (void *)element, | |
67c4f309 | 1195 | element->hash, INSERT); |
4ee9c684 | 1196 | if (*slot == NULL) |
1197 | { | |
1198 | *slot = (void *) element; | |
75a70cf9 | 1199 | |
1200 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1201 | { | |
1202 | fprintf (dump_file, "1>>> "); | |
1203 | print_expr_hash_elt (dump_file, element); | |
1204 | } | |
1205 | ||
1206 | VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element); | |
4ee9c684 | 1207 | } |
1208 | else | |
1209 | free (element); | |
1210 | } | |
1211 | ||
75a70cf9 | 1212 | /* Build a cond_equivalence record indicating that the comparison |
7aab1427 | 1213 | CODE holds between operands OP0 and OP1 and push it to **P. */ |
48e1416a | 1214 | |
2f0993e7 | 1215 | static void |
75a70cf9 | 1216 | build_and_record_new_cond (enum tree_code code, |
1217 | tree op0, tree op1, | |
7aab1427 | 1218 | VEC(cond_equivalence, heap) **p) |
2f0993e7 | 1219 | { |
7aab1427 | 1220 | cond_equivalence c; |
1221 | struct hashable_expr *cond = &c.cond; | |
75a70cf9 | 1222 | |
1223 | gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison); | |
1224 | ||
1225 | cond->type = boolean_type_node; | |
1226 | cond->kind = EXPR_BINARY; | |
1227 | cond->ops.binary.op = code; | |
1228 | cond->ops.binary.opnd0 = op0; | |
1229 | cond->ops.binary.opnd1 = op1; | |
1230 | ||
7aab1427 | 1231 | c.value = boolean_true_node; |
1232 | VEC_safe_push (cond_equivalence, heap, *p, &c); | |
2f0993e7 | 1233 | } |
1234 | ||
1235 | /* Record that COND is true and INVERTED is false into the edge information | |
1236 | structure. Also record that any conditions dominated by COND are true | |
1237 | as well. | |
043d0665 | 1238 | |
1239 | For example, if a < b is true, then a <= b must also be true. */ | |
1240 | ||
1241 | static void | |
2f0993e7 | 1242 | record_conditions (struct edge_info *edge_info, tree cond, tree inverted) |
043d0665 | 1243 | { |
2f0993e7 | 1244 | tree op0, op1; |
7aab1427 | 1245 | cond_equivalence c; |
2f0993e7 | 1246 | |
1247 | if (!COMPARISON_CLASS_P (cond)) | |
1248 | return; | |
1249 | ||
1250 | op0 = TREE_OPERAND (cond, 0); | |
1251 | op1 = TREE_OPERAND (cond, 1); | |
1252 | ||
043d0665 | 1253 | switch (TREE_CODE (cond)) |
1254 | { | |
1255 | case LT_EXPR: | |
043d0665 | 1256 | case GT_EXPR: |
c4124729 | 1257 | if (FLOAT_TYPE_P (TREE_TYPE (op0))) |
1258 | { | |
c4124729 | 1259 | build_and_record_new_cond (ORDERED_EXPR, op0, op1, |
7aab1427 | 1260 | &edge_info->cond_equivalences); |
c4124729 | 1261 | build_and_record_new_cond (LTGT_EXPR, op0, op1, |
7aab1427 | 1262 | &edge_info->cond_equivalences); |
c4124729 | 1263 | } |
1264 | ||
2f0993e7 | 1265 | build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR |
1266 | ? LE_EXPR : GE_EXPR), | |
7aab1427 | 1267 | op0, op1, &edge_info->cond_equivalences); |
2f0993e7 | 1268 | build_and_record_new_cond (NE_EXPR, op0, op1, |
7aab1427 | 1269 | &edge_info->cond_equivalences); |
043d0665 | 1270 | break; |
1271 | ||
1272 | case GE_EXPR: | |
1273 | case LE_EXPR: | |
c4124729 | 1274 | if (FLOAT_TYPE_P (TREE_TYPE (op0))) |
1275 | { | |
c4124729 | 1276 | build_and_record_new_cond (ORDERED_EXPR, op0, op1, |
7aab1427 | 1277 | &edge_info->cond_equivalences); |
c4124729 | 1278 | } |
043d0665 | 1279 | break; |
1280 | ||
1281 | case EQ_EXPR: | |
c4124729 | 1282 | if (FLOAT_TYPE_P (TREE_TYPE (op0))) |
1283 | { | |
c4124729 | 1284 | build_and_record_new_cond (ORDERED_EXPR, op0, op1, |
7aab1427 | 1285 | &edge_info->cond_equivalences); |
c4124729 | 1286 | } |
2f0993e7 | 1287 | build_and_record_new_cond (LE_EXPR, op0, op1, |
7aab1427 | 1288 | &edge_info->cond_equivalences); |
2f0993e7 | 1289 | build_and_record_new_cond (GE_EXPR, op0, op1, |
7aab1427 | 1290 | &edge_info->cond_equivalences); |
043d0665 | 1291 | break; |
1292 | ||
1293 | case UNORDERED_EXPR: | |
2f0993e7 | 1294 | build_and_record_new_cond (NE_EXPR, op0, op1, |
7aab1427 | 1295 | &edge_info->cond_equivalences); |
2f0993e7 | 1296 | build_and_record_new_cond (UNLE_EXPR, op0, op1, |
7aab1427 | 1297 | &edge_info->cond_equivalences); |
2f0993e7 | 1298 | build_and_record_new_cond (UNGE_EXPR, op0, op1, |
7aab1427 | 1299 | &edge_info->cond_equivalences); |
2f0993e7 | 1300 | build_and_record_new_cond (UNEQ_EXPR, op0, op1, |
7aab1427 | 1301 | &edge_info->cond_equivalences); |
2f0993e7 | 1302 | build_and_record_new_cond (UNLT_EXPR, op0, op1, |
7aab1427 | 1303 | &edge_info->cond_equivalences); |
2f0993e7 | 1304 | build_and_record_new_cond (UNGT_EXPR, op0, op1, |
7aab1427 | 1305 | &edge_info->cond_equivalences); |
043d0665 | 1306 | break; |
1307 | ||
1308 | case UNLT_EXPR: | |
043d0665 | 1309 | case UNGT_EXPR: |
2f0993e7 | 1310 | build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR |
1311 | ? UNLE_EXPR : UNGE_EXPR), | |
7aab1427 | 1312 | op0, op1, &edge_info->cond_equivalences); |
2f0993e7 | 1313 | build_and_record_new_cond (NE_EXPR, op0, op1, |
7aab1427 | 1314 | &edge_info->cond_equivalences); |
043d0665 | 1315 | break; |
1316 | ||
1317 | case UNEQ_EXPR: | |
2f0993e7 | 1318 | build_and_record_new_cond (UNLE_EXPR, op0, op1, |
7aab1427 | 1319 | &edge_info->cond_equivalences); |
2f0993e7 | 1320 | build_and_record_new_cond (UNGE_EXPR, op0, op1, |
7aab1427 | 1321 | &edge_info->cond_equivalences); |
043d0665 | 1322 | break; |
1323 | ||
1324 | case LTGT_EXPR: | |
2f0993e7 | 1325 | build_and_record_new_cond (NE_EXPR, op0, op1, |
7aab1427 | 1326 | &edge_info->cond_equivalences); |
2f0993e7 | 1327 | build_and_record_new_cond (ORDERED_EXPR, op0, op1, |
7aab1427 | 1328 | &edge_info->cond_equivalences); |
2f0993e7 | 1329 | break; |
043d0665 | 1330 | |
1331 | default: | |
1332 | break; | |
1333 | } | |
2f0993e7 | 1334 | |
1335 | /* Now store the original true and false conditions into the first | |
1336 | two slots. */ | |
7aab1427 | 1337 | initialize_expr_from_cond (cond, &c.cond); |
1338 | c.value = boolean_true_node; | |
1339 | VEC_safe_push (cond_equivalence, heap, edge_info->cond_equivalences, &c); | |
75a70cf9 | 1340 | |
1341 | /* It is possible for INVERTED to be the negation of a comparison, | |
1342 | and not a valid RHS or GIMPLE_COND condition. This happens because | |
1343 | invert_truthvalue may return such an expression when asked to invert | |
1344 | a floating-point comparison. These comparisons are not assumed to | |
1345 | obey the trichotomy law. */ | |
7aab1427 | 1346 | initialize_expr_from_cond (inverted, &c.cond); |
1347 | c.value = boolean_false_node; | |
1348 | VEC_safe_push (cond_equivalence, heap, edge_info->cond_equivalences, &c); | |
043d0665 | 1349 | } |
1350 | ||
4ee9c684 | 1351 | /* A helper function for record_const_or_copy and record_equality. |
1352 | Do the work of recording the value and undo info. */ | |
1353 | ||
1354 | static void | |
da43203c | 1355 | record_const_or_copy_1 (tree x, tree y, tree prev_x) |
4ee9c684 | 1356 | { |
f003f9fd | 1357 | set_ssa_name_value (x, y); |
4ee9c684 | 1358 | |
75a70cf9 | 1359 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1360 | { | |
1361 | fprintf (dump_file, "0>>> COPY "); | |
1362 | print_generic_expr (dump_file, x, 0); | |
1363 | fprintf (dump_file, " = "); | |
1364 | print_generic_expr (dump_file, y, 0); | |
1365 | fprintf (dump_file, "\n"); | |
1366 | } | |
1367 | ||
046bfc77 | 1368 | VEC_reserve (tree, heap, const_and_copies_stack, 2); |
1369 | VEC_quick_push (tree, const_and_copies_stack, prev_x); | |
1370 | VEC_quick_push (tree, const_and_copies_stack, x); | |
4ee9c684 | 1371 | } |
1372 | ||
ba4c299c | 1373 | /* Return the loop depth of the basic block of the defining statement of X. |
1374 | This number should not be treated as absolutely correct because the loop | |
1375 | information may not be completely up-to-date when dom runs. However, it | |
1376 | will be relatively correct, and as more passes are taught to keep loop info | |
1377 | up to date, the result will become more and more accurate. */ | |
1378 | ||
88dbf20f | 1379 | int |
ba4c299c | 1380 | loop_depth_of_name (tree x) |
1381 | { | |
75a70cf9 | 1382 | gimple defstmt; |
ba4c299c | 1383 | basic_block defbb; |
1384 | ||
1385 | /* If it's not an SSA_NAME, we have no clue where the definition is. */ | |
1386 | if (TREE_CODE (x) != SSA_NAME) | |
1387 | return 0; | |
1388 | ||
1389 | /* Otherwise return the loop depth of the defining statement's bb. | |
1390 | Note that there may not actually be a bb for this statement, if the | |
1391 | ssa_name is live on entry. */ | |
1392 | defstmt = SSA_NAME_DEF_STMT (x); | |
75a70cf9 | 1393 | defbb = gimple_bb (defstmt); |
ba4c299c | 1394 | if (!defbb) |
1395 | return 0; | |
1396 | ||
1397 | return defbb->loop_depth; | |
1398 | } | |
1399 | ||
4ee9c684 | 1400 | /* Record that X is equal to Y in const_and_copies. Record undo |
f0458177 | 1401 | information in the block-local vector. */ |
4ee9c684 | 1402 | |
1403 | static void | |
da43203c | 1404 | record_const_or_copy (tree x, tree y) |
4ee9c684 | 1405 | { |
4c7a0518 | 1406 | tree prev_x = SSA_NAME_VALUE (x); |
4ee9c684 | 1407 | |
75a70cf9 | 1408 | gcc_assert (TREE_CODE (x) == SSA_NAME); |
1409 | ||
4ee9c684 | 1410 | if (TREE_CODE (y) == SSA_NAME) |
1411 | { | |
4c7a0518 | 1412 | tree tmp = SSA_NAME_VALUE (y); |
4ee9c684 | 1413 | if (tmp) |
1414 | y = tmp; | |
1415 | } | |
1416 | ||
da43203c | 1417 | record_const_or_copy_1 (x, y, prev_x); |
4ee9c684 | 1418 | } |
1419 | ||
1420 | /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR. | |
1421 | This constrains the cases in which we may treat this as assignment. */ | |
1422 | ||
1423 | static void | |
da43203c | 1424 | record_equality (tree x, tree y) |
4ee9c684 | 1425 | { |
1426 | tree prev_x = NULL, prev_y = NULL; | |
1427 | ||
1428 | if (TREE_CODE (x) == SSA_NAME) | |
4c7a0518 | 1429 | prev_x = SSA_NAME_VALUE (x); |
4ee9c684 | 1430 | if (TREE_CODE (y) == SSA_NAME) |
4c7a0518 | 1431 | prev_y = SSA_NAME_VALUE (y); |
4ee9c684 | 1432 | |
ba4c299c | 1433 | /* If one of the previous values is invariant, or invariant in more loops |
1434 | (by depth), then use that. | |
4ee9c684 | 1435 | Otherwise it doesn't matter which value we choose, just so |
1436 | long as we canonicalize on one value. */ | |
71d9af81 | 1437 | if (is_gimple_min_invariant (y)) |
4ee9c684 | 1438 | ; |
71d9af81 | 1439 | else if (is_gimple_min_invariant (x) |
1440 | || (loop_depth_of_name (x) <= loop_depth_of_name (y))) | |
4ee9c684 | 1441 | prev_x = x, x = y, y = prev_x, prev_x = prev_y; |
71d9af81 | 1442 | else if (prev_x && is_gimple_min_invariant (prev_x)) |
4ee9c684 | 1443 | x = y, y = prev_x, prev_x = prev_y; |
f6c33c78 | 1444 | else if (prev_y) |
4ee9c684 | 1445 | y = prev_y; |
1446 | ||
1447 | /* After the swapping, we must have one SSA_NAME. */ | |
1448 | if (TREE_CODE (x) != SSA_NAME) | |
1449 | return; | |
1450 | ||
1451 | /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a | |
1452 | variable compared against zero. If we're honoring signed zeros, | |
1453 | then we cannot record this value unless we know that the value is | |
365db11e | 1454 | nonzero. */ |
4ee9c684 | 1455 | if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x))) |
1456 | && (TREE_CODE (y) != REAL_CST | |
1457 | || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y)))) | |
1458 | return; | |
1459 | ||
da43203c | 1460 | record_const_or_copy_1 (x, y, prev_x); |
4ee9c684 | 1461 | } |
1462 | ||
119a0489 | 1463 | /* Returns true when STMT is a simple iv increment. It detects the |
1464 | following situation: | |
48e1416a | 1465 | |
119a0489 | 1466 | i_1 = phi (..., i_2) |
1467 | i_2 = i_1 +/- ... */ | |
1468 | ||
cd22a796 | 1469 | bool |
75a70cf9 | 1470 | simple_iv_increment_p (gimple stmt) |
119a0489 | 1471 | { |
cd22a796 | 1472 | enum tree_code code; |
75a70cf9 | 1473 | tree lhs, preinc; |
1474 | gimple phi; | |
1475 | size_t i; | |
119a0489 | 1476 | |
75a70cf9 | 1477 | if (gimple_code (stmt) != GIMPLE_ASSIGN) |
119a0489 | 1478 | return false; |
1479 | ||
75a70cf9 | 1480 | lhs = gimple_assign_lhs (stmt); |
119a0489 | 1481 | if (TREE_CODE (lhs) != SSA_NAME) |
1482 | return false; | |
1483 | ||
cd22a796 | 1484 | code = gimple_assign_rhs_code (stmt); |
1485 | if (code != PLUS_EXPR | |
1486 | && code != MINUS_EXPR | |
1487 | && code != POINTER_PLUS_EXPR) | |
119a0489 | 1488 | return false; |
1489 | ||
75a70cf9 | 1490 | preinc = gimple_assign_rhs1 (stmt); |
119a0489 | 1491 | if (TREE_CODE (preinc) != SSA_NAME) |
1492 | return false; | |
1493 | ||
1494 | phi = SSA_NAME_DEF_STMT (preinc); | |
75a70cf9 | 1495 | if (gimple_code (phi) != GIMPLE_PHI) |
119a0489 | 1496 | return false; |
1497 | ||
75a70cf9 | 1498 | for (i = 0; i < gimple_phi_num_args (phi); i++) |
1499 | if (gimple_phi_arg_def (phi, i) == lhs) | |
119a0489 | 1500 | return true; |
1501 | ||
1502 | return false; | |
1503 | } | |
1504 | ||
591c2a30 | 1505 | /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current |
48e1416a | 1506 | known value for that SSA_NAME (or NULL if no value is known). |
591c2a30 | 1507 | |
8dbf774a | 1508 | Propagate values from CONST_AND_COPIES into the PHI nodes of the |
1509 | successors of BB. */ | |
591c2a30 | 1510 | |
1511 | static void | |
8dbf774a | 1512 | cprop_into_successor_phis (basic_block bb) |
591c2a30 | 1513 | { |
1514 | edge e; | |
cd665a06 | 1515 | edge_iterator ei; |
591c2a30 | 1516 | |
cd665a06 | 1517 | FOR_EACH_EDGE (e, ei, bb->succs) |
591c2a30 | 1518 | { |
5f50f9bf | 1519 | int indx; |
75a70cf9 | 1520 | gimple_stmt_iterator gsi; |
591c2a30 | 1521 | |
1522 | /* If this is an abnormal edge, then we do not want to copy propagate | |
1523 | into the PHI alternative associated with this edge. */ | |
1524 | if (e->flags & EDGE_ABNORMAL) | |
1525 | continue; | |
1526 | ||
75a70cf9 | 1527 | gsi = gsi_start_phis (e->dest); |
1528 | if (gsi_end_p (gsi)) | |
591c2a30 | 1529 | continue; |
1530 | ||
5f50f9bf | 1531 | indx = e->dest_idx; |
75a70cf9 | 1532 | for ( ; !gsi_end_p (gsi); gsi_next (&gsi)) |
591c2a30 | 1533 | { |
f0d6e81c | 1534 | tree new_val; |
591c2a30 | 1535 | use_operand_p orig_p; |
f0d6e81c | 1536 | tree orig_val; |
75a70cf9 | 1537 | gimple phi = gsi_stmt (gsi); |
591c2a30 | 1538 | |
591c2a30 | 1539 | /* The alternative may be associated with a constant, so verify |
1540 | it is an SSA_NAME before doing anything with it. */ | |
75a70cf9 | 1541 | orig_p = gimple_phi_arg_imm_use_ptr (phi, indx); |
1542 | orig_val = get_use_from_ptr (orig_p); | |
f0d6e81c | 1543 | if (TREE_CODE (orig_val) != SSA_NAME) |
591c2a30 | 1544 | continue; |
1545 | ||
591c2a30 | 1546 | /* If we have *ORIG_P in our constant/copy table, then replace |
1547 | ORIG_P with its value in our constant/copy table. */ | |
f0d6e81c | 1548 | new_val = SSA_NAME_VALUE (orig_val); |
1549 | if (new_val | |
1550 | && new_val != orig_val | |
1551 | && (TREE_CODE (new_val) == SSA_NAME | |
1552 | || is_gimple_min_invariant (new_val)) | |
1553 | && may_propagate_copy (orig_val, new_val)) | |
1554 | propagate_value (orig_p, new_val); | |
591c2a30 | 1555 | } |
1556 | } | |
1557 | } | |
1558 | ||
2f0993e7 | 1559 | /* We have finished optimizing BB, record any information implied by |
1560 | taking a specific outgoing edge from BB. */ | |
1561 | ||
1562 | static void | |
1563 | record_edge_info (basic_block bb) | |
1564 | { | |
75a70cf9 | 1565 | gimple_stmt_iterator gsi = gsi_last_bb (bb); |
2f0993e7 | 1566 | struct edge_info *edge_info; |
1567 | ||
75a70cf9 | 1568 | if (! gsi_end_p (gsi)) |
2f0993e7 | 1569 | { |
75a70cf9 | 1570 | gimple stmt = gsi_stmt (gsi); |
389dd41b | 1571 | location_t loc = gimple_location (stmt); |
2f0993e7 | 1572 | |
75a70cf9 | 1573 | if (gimple_code (stmt) == GIMPLE_SWITCH) |
2f0993e7 | 1574 | { |
75a70cf9 | 1575 | tree index = gimple_switch_index (stmt); |
2f0993e7 | 1576 | |
75a70cf9 | 1577 | if (TREE_CODE (index) == SSA_NAME) |
2f0993e7 | 1578 | { |
75a70cf9 | 1579 | int i; |
1580 | int n_labels = gimple_switch_num_labels (stmt); | |
945865c5 | 1581 | tree *info = XCNEWVEC (tree, last_basic_block); |
2f0993e7 | 1582 | edge e; |
1583 | edge_iterator ei; | |
1584 | ||
1585 | for (i = 0; i < n_labels; i++) | |
1586 | { | |
75a70cf9 | 1587 | tree label = gimple_switch_label (stmt, i); |
2f0993e7 | 1588 | basic_block target_bb = label_to_block (CASE_LABEL (label)); |
2f0993e7 | 1589 | if (CASE_HIGH (label) |
1590 | || !CASE_LOW (label) | |
1591 | || info[target_bb->index]) | |
1592 | info[target_bb->index] = error_mark_node; | |
1593 | else | |
1594 | info[target_bb->index] = label; | |
1595 | } | |
1596 | ||
1597 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1598 | { | |
1599 | basic_block target_bb = e->dest; | |
75a70cf9 | 1600 | tree label = info[target_bb->index]; |
591c2a30 | 1601 | |
75a70cf9 | 1602 | if (label != NULL && label != error_mark_node) |
2f0993e7 | 1603 | { |
389dd41b | 1604 | tree x = fold_convert_loc (loc, TREE_TYPE (index), |
1605 | CASE_LOW (label)); | |
2f0993e7 | 1606 | edge_info = allocate_edge_info (e); |
75a70cf9 | 1607 | edge_info->lhs = index; |
2f0993e7 | 1608 | edge_info->rhs = x; |
1609 | } | |
1610 | } | |
1611 | free (info); | |
1612 | } | |
1613 | } | |
1614 | ||
1615 | /* A COND_EXPR may create equivalences too. */ | |
75a70cf9 | 1616 | if (gimple_code (stmt) == GIMPLE_COND) |
2f0993e7 | 1617 | { |
2f0993e7 | 1618 | edge true_edge; |
1619 | edge false_edge; | |
1620 | ||
75a70cf9 | 1621 | tree op0 = gimple_cond_lhs (stmt); |
1622 | tree op1 = gimple_cond_rhs (stmt); | |
1623 | enum tree_code code = gimple_cond_code (stmt); | |
2f0993e7 | 1624 | |
75a70cf9 | 1625 | extract_true_false_edges_from_block (bb, &true_edge, &false_edge); |
2f0993e7 | 1626 | |
75a70cf9 | 1627 | /* Special case comparing booleans against a constant as we |
1628 | know the value of OP0 on both arms of the branch. i.e., we | |
1629 | can record an equivalence for OP0 rather than COND. */ | |
1630 | if ((code == EQ_EXPR || code == NE_EXPR) | |
1631 | && TREE_CODE (op0) == SSA_NAME | |
1632 | && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE | |
1633 | && is_gimple_min_invariant (op1)) | |
1634 | { | |
1635 | if (code == EQ_EXPR) | |
1636 | { | |
1637 | edge_info = allocate_edge_info (true_edge); | |
1638 | edge_info->lhs = op0; | |
1639 | edge_info->rhs = (integer_zerop (op1) | |
1640 | ? boolean_false_node | |
1641 | : boolean_true_node); | |
1642 | ||
1643 | edge_info = allocate_edge_info (false_edge); | |
1644 | edge_info->lhs = op0; | |
1645 | edge_info->rhs = (integer_zerop (op1) | |
1646 | ? boolean_true_node | |
1647 | : boolean_false_node); | |
1648 | } | |
1649 | else | |
1650 | { | |
1651 | edge_info = allocate_edge_info (true_edge); | |
1652 | edge_info->lhs = op0; | |
1653 | edge_info->rhs = (integer_zerop (op1) | |
1654 | ? boolean_true_node | |
1655 | : boolean_false_node); | |
1656 | ||
1657 | edge_info = allocate_edge_info (false_edge); | |
1658 | edge_info->lhs = op0; | |
1659 | edge_info->rhs = (integer_zerop (op1) | |
1660 | ? boolean_false_node | |
1661 | : boolean_true_node); | |
1662 | } | |
1663 | } | |
1664 | else if (is_gimple_min_invariant (op0) | |
1665 | && (TREE_CODE (op1) == SSA_NAME | |
1666 | || is_gimple_min_invariant (op1))) | |
1667 | { | |
1668 | tree cond = build2 (code, boolean_type_node, op0, op1); | |
389dd41b | 1669 | tree inverted = invert_truthvalue_loc (loc, cond); |
7b56081a | 1670 | bool can_infer_simple_equiv |
1671 | = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0))) | |
1672 | && real_zerop (op0)); | |
75a70cf9 | 1673 | struct edge_info *edge_info; |
1674 | ||
1675 | edge_info = allocate_edge_info (true_edge); | |
1676 | record_conditions (edge_info, cond, inverted); | |
1677 | ||
7b56081a | 1678 | if (can_infer_simple_equiv && code == EQ_EXPR) |
75a70cf9 | 1679 | { |
1680 | edge_info->lhs = op1; | |
1681 | edge_info->rhs = op0; | |
1682 | } | |
1683 | ||
1684 | edge_info = allocate_edge_info (false_edge); | |
1685 | record_conditions (edge_info, inverted, cond); | |
1686 | ||
7b56081a | 1687 | if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) |
75a70cf9 | 1688 | { |
1689 | edge_info->lhs = op1; | |
1690 | edge_info->rhs = op0; | |
1691 | } | |
1692 | } | |
1693 | ||
1694 | else if (TREE_CODE (op0) == SSA_NAME | |
7b56081a | 1695 | && (TREE_CODE (op1) == SSA_NAME |
1696 | || is_gimple_min_invariant (op1))) | |
75a70cf9 | 1697 | { |
1698 | tree cond = build2 (code, boolean_type_node, op0, op1); | |
389dd41b | 1699 | tree inverted = invert_truthvalue_loc (loc, cond); |
7b56081a | 1700 | bool can_infer_simple_equiv |
1701 | = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op1))) | |
1702 | && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1))); | |
75a70cf9 | 1703 | struct edge_info *edge_info; |
1704 | ||
1705 | edge_info = allocate_edge_info (true_edge); | |
1706 | record_conditions (edge_info, cond, inverted); | |
1707 | ||
7b56081a | 1708 | if (can_infer_simple_equiv && code == EQ_EXPR) |
75a70cf9 | 1709 | { |
1710 | edge_info->lhs = op0; | |
1711 | edge_info->rhs = op1; | |
1712 | } | |
1713 | ||
1714 | edge_info = allocate_edge_info (false_edge); | |
1715 | record_conditions (edge_info, inverted, cond); | |
1716 | ||
7b56081a | 1717 | if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) |
75a70cf9 | 1718 | { |
1719 | edge_info->lhs = op0; | |
1720 | edge_info->rhs = op1; | |
1721 | } | |
1722 | } | |
1723 | } | |
1724 | ||
1725 | /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ | |
2f0993e7 | 1726 | } |
1727 | } | |
1728 | ||
4ee9c684 | 1729 | static void |
6bf320fb | 1730 | dom_opt_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, |
1731 | basic_block bb) | |
4ee9c684 | 1732 | { |
6bf320fb | 1733 | gimple_stmt_iterator gsi; |
1734 | ||
1735 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1736 | fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); | |
1737 | ||
1738 | /* Push a marker on the stacks of local information so that we know how | |
1739 | far to unwind when we finalize this block. */ | |
1740 | VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); | |
1741 | VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
1742 | ||
1743 | record_equivalences_from_incoming_edge (bb); | |
1744 | ||
1745 | /* PHI nodes can create equivalences too. */ | |
1746 | record_equivalences_from_phis (bb); | |
1747 | ||
889ef038 | 1748 | /* Create equivalences from redundant PHIs. PHIs are only truly |
1749 | redundant when they exist in the same block, so push another | |
1750 | marker and unwind right afterwards. */ | |
1751 | VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); | |
1752 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
1753 | eliminate_redundant_computations (&gsi); | |
1754 | remove_local_expressions_from_table (); | |
1755 | ||
6bf320fb | 1756 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
1757 | optimize_stmt (bb, gsi); | |
1758 | ||
1759 | /* Now prepare to process dominated blocks. */ | |
2f0993e7 | 1760 | record_edge_info (bb); |
8dbf774a | 1761 | cprop_into_successor_phis (bb); |
4ee9c684 | 1762 | } |
1763 | ||
6bf320fb | 1764 | /* We have finished processing the dominator children of BB, perform |
1765 | any finalization actions in preparation for leaving this node in | |
1766 | the dominator tree. */ | |
1767 | ||
1768 | static void | |
1769 | dom_opt_leave_block (struct dom_walk_data *walk_data, basic_block bb) | |
1770 | { | |
1771 | gimple last; | |
1772 | ||
1773 | /* If we have an outgoing edge to a block with multiple incoming and | |
1774 | outgoing edges, then we may be able to thread the edge, i.e., we | |
1775 | may be able to statically determine which of the outgoing edges | |
1776 | will be traversed when the incoming edge from BB is traversed. */ | |
1777 | if (single_succ_p (bb) | |
1778 | && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0 | |
1779 | && potentially_threadable_block (single_succ (bb))) | |
1780 | { | |
9f396eaf | 1781 | /* Push a marker on the stack, which thread_across_edge expects |
1782 | and will remove. */ | |
1783 | VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
6bf320fb | 1784 | dom_thread_across_edge (walk_data, single_succ_edge (bb)); |
1785 | } | |
1786 | else if ((last = last_stmt (bb)) | |
1787 | && gimple_code (last) == GIMPLE_COND | |
1788 | && EDGE_COUNT (bb->succs) == 2 | |
1789 | && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0 | |
1790 | && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0) | |
1791 | { | |
1792 | edge true_edge, false_edge; | |
1793 | ||
1794 | extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
1795 | ||
1796 | /* Only try to thread the edge if it reaches a target block with | |
1797 | more than one predecessor and more than one successor. */ | |
1798 | if (potentially_threadable_block (true_edge->dest)) | |
1799 | { | |
1800 | struct edge_info *edge_info; | |
1801 | unsigned int i; | |
1802 | ||
1803 | /* Push a marker onto the available expression stack so that we | |
1804 | unwind any expressions related to the TRUE arm before processing | |
1805 | the false arm below. */ | |
1806 | VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); | |
1807 | VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
1808 | ||
1809 | edge_info = (struct edge_info *) true_edge->aux; | |
1810 | ||
1811 | /* If we have info associated with this edge, record it into | |
1812 | our equivalence tables. */ | |
1813 | if (edge_info) | |
1814 | { | |
7aab1427 | 1815 | cond_equivalence *eq; |
6bf320fb | 1816 | tree lhs = edge_info->lhs; |
1817 | tree rhs = edge_info->rhs; | |
1818 | ||
1819 | /* If we have a simple NAME = VALUE equivalence, record it. */ | |
1820 | if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
1821 | record_const_or_copy (lhs, rhs); | |
1822 | ||
1823 | /* If we have 0 = COND or 1 = COND equivalences, record them | |
1824 | into our expression hash tables. */ | |
7aab1427 | 1825 | for (i = 0; VEC_iterate (cond_equivalence, |
1826 | edge_info->cond_equivalences, i, eq); ++i) | |
1827 | record_cond (eq); | |
6bf320fb | 1828 | } |
1829 | ||
1830 | dom_thread_across_edge (walk_data, true_edge); | |
1831 | ||
1832 | /* And restore the various tables to their state before | |
1833 | we threaded this edge. */ | |
1834 | remove_local_expressions_from_table (); | |
1835 | } | |
1836 | ||
1837 | /* Similarly for the ELSE arm. */ | |
1838 | if (potentially_threadable_block (false_edge->dest)) | |
1839 | { | |
1840 | struct edge_info *edge_info; | |
1841 | unsigned int i; | |
1842 | ||
1843 | VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
1844 | edge_info = (struct edge_info *) false_edge->aux; | |
1845 | ||
1846 | /* If we have info associated with this edge, record it into | |
1847 | our equivalence tables. */ | |
1848 | if (edge_info) | |
1849 | { | |
7aab1427 | 1850 | cond_equivalence *eq; |
6bf320fb | 1851 | tree lhs = edge_info->lhs; |
1852 | tree rhs = edge_info->rhs; | |
1853 | ||
1854 | /* If we have a simple NAME = VALUE equivalence, record it. */ | |
1855 | if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
1856 | record_const_or_copy (lhs, rhs); | |
1857 | ||
1858 | /* If we have 0 = COND or 1 = COND equivalences, record them | |
1859 | into our expression hash tables. */ | |
7aab1427 | 1860 | for (i = 0; VEC_iterate (cond_equivalence, |
1861 | edge_info->cond_equivalences, i, eq); ++i) | |
1862 | record_cond (eq); | |
6bf320fb | 1863 | } |
1864 | ||
1865 | /* Now thread the edge. */ | |
1866 | dom_thread_across_edge (walk_data, false_edge); | |
1867 | ||
1868 | /* No need to remove local expressions from our tables | |
1869 | or restore vars to their original value as that will | |
1870 | be done immediately below. */ | |
1871 | } | |
1872 | } | |
1873 | ||
1874 | remove_local_expressions_from_table (); | |
1875 | restore_vars_to_original_value (); | |
6bf320fb | 1876 | } |
1877 | ||
4ee9c684 | 1878 | /* Search for redundant computations in STMT. If any are found, then |
1879 | replace them with the variable holding the result of the computation. | |
1880 | ||
1881 | If safe, record this expression into the available expression hash | |
1882 | table. */ | |
1883 | ||
e08ff65a | 1884 | static void |
75a70cf9 | 1885 | eliminate_redundant_computations (gimple_stmt_iterator* gsi) |
4ee9c684 | 1886 | { |
75a70cf9 | 1887 | tree expr_type; |
4ee9c684 | 1888 | tree cached_lhs; |
889ef038 | 1889 | tree def; |
75a70cf9 | 1890 | bool insert = true; |
75a70cf9 | 1891 | bool assigns_var_p = false; |
4ee9c684 | 1892 | |
75a70cf9 | 1893 | gimple stmt = gsi_stmt (*gsi); |
1894 | ||
889ef038 | 1895 | if (gimple_code (stmt) == GIMPLE_PHI) |
1896 | def = gimple_phi_result (stmt); | |
1897 | else | |
1898 | def = gimple_get_lhs (stmt); | |
4ee9c684 | 1899 | |
1900 | /* Certain expressions on the RHS can be optimized away, but can not | |
dac49aa5 | 1901 | themselves be entered into the hash tables. */ |
9d637cc5 | 1902 | if (! def |
4ee9c684 | 1903 | || TREE_CODE (def) != SSA_NAME |
1904 | || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) | |
dd277d48 | 1905 | || gimple_vdef (stmt) |
119a0489 | 1906 | /* Do not record equivalences for increments of ivs. This would create |
1907 | overlapping live ranges for a very questionable gain. */ | |
1908 | || simple_iv_increment_p (stmt)) | |
4ee9c684 | 1909 | insert = false; |
1910 | ||
1911 | /* Check if the expression has been computed before. */ | |
9c629f0e | 1912 | cached_lhs = lookup_avail_expr (stmt, insert); |
4ee9c684 | 1913 | |
4ee9c684 | 1914 | opt_stats.num_exprs_considered++; |
1915 | ||
75a70cf9 | 1916 | /* Get the type of the expression we are trying to optimize. */ |
1917 | if (is_gimple_assign (stmt)) | |
f6be5aa5 | 1918 | { |
75a70cf9 | 1919 | expr_type = TREE_TYPE (gimple_assign_lhs (stmt)); |
1920 | assigns_var_p = true; | |
f6be5aa5 | 1921 | } |
75a70cf9 | 1922 | else if (gimple_code (stmt) == GIMPLE_COND) |
1923 | expr_type = boolean_type_node; | |
1924 | else if (is_gimple_call (stmt)) | |
f6be5aa5 | 1925 | { |
75a70cf9 | 1926 | gcc_assert (gimple_call_lhs (stmt)); |
1927 | expr_type = TREE_TYPE (gimple_call_lhs (stmt)); | |
1928 | assigns_var_p = true; | |
f6be5aa5 | 1929 | } |
75a70cf9 | 1930 | else if (gimple_code (stmt) == GIMPLE_SWITCH) |
1931 | expr_type = TREE_TYPE (gimple_switch_index (stmt)); | |
889ef038 | 1932 | else if (gimple_code (stmt) == GIMPLE_PHI) |
1933 | /* We can't propagate into a phi, so the logic below doesn't apply. | |
1934 | Instead record an equivalence between the cached LHS and the | |
1935 | PHI result of this statement, provided they are in the same block. | |
1936 | This should be sufficient to kill the redundant phi. */ | |
1937 | { | |
1938 | if (def && cached_lhs) | |
1939 | record_const_or_copy (def, cached_lhs); | |
1940 | return; | |
1941 | } | |
75a70cf9 | 1942 | else |
1943 | gcc_unreachable (); | |
1944 | ||
1945 | if (!cached_lhs) | |
e08ff65a | 1946 | return; |
4ee9c684 | 1947 | |
1948 | /* It is safe to ignore types here since we have already done | |
1949 | type checking in the hashing and equality routines. In fact | |
1950 | type checking here merely gets in the way of constant | |
1951 | propagation. Also, make sure that it is safe to propagate | |
75a70cf9 | 1952 | CACHED_LHS into the expression in STMT. */ |
1953 | if ((TREE_CODE (cached_lhs) != SSA_NAME | |
1954 | && (assigns_var_p | |
1955 | || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))) | |
1956 | || may_propagate_copy_into_stmt (stmt, cached_lhs)) | |
1957 | { | |
1b4345f7 | 1958 | gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME |
1959 | || is_gimple_min_invariant (cached_lhs)); | |
75a70cf9 | 1960 | |
4ee9c684 | 1961 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1962 | { | |
1963 | fprintf (dump_file, " Replaced redundant expr '"); | |
75a70cf9 | 1964 | print_gimple_expr (dump_file, stmt, 0, dump_flags); |
4ee9c684 | 1965 | fprintf (dump_file, "' with '"); |
1966 | print_generic_expr (dump_file, cached_lhs, dump_flags); | |
75a70cf9 | 1967 | fprintf (dump_file, "'\n"); |
4ee9c684 | 1968 | } |
1969 | ||
1970 | opt_stats.num_re++; | |
48e1416a | 1971 | |
75a70cf9 | 1972 | if (assigns_var_p |
1973 | && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))) | |
1974 | cached_lhs = fold_convert (expr_type, cached_lhs); | |
4ee9c684 | 1975 | |
75a70cf9 | 1976 | propagate_tree_value_into_stmt (gsi, cached_lhs); |
1977 | ||
1978 | /* Since it is always necessary to mark the result as modified, | |
1979 | perhaps we should move this into propagate_tree_value_into_stmt | |
1980 | itself. */ | |
1981 | gimple_set_modified (gsi_stmt (*gsi), true); | |
1982 | } | |
4ee9c684 | 1983 | } |
1984 | ||
75a70cf9 | 1985 | /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either |
4ee9c684 | 1986 | the available expressions table or the const_and_copies table. |
1987 | Detect and record those equivalences. */ | |
75a70cf9 | 1988 | /* We handle only very simple copy equivalences here. The heavy |
1989 | lifing is done by eliminate_redundant_computations. */ | |
4ee9c684 | 1990 | |
1991 | static void | |
75a70cf9 | 1992 | record_equivalences_from_stmt (gimple stmt, int may_optimize_p) |
4ee9c684 | 1993 | { |
75a70cf9 | 1994 | tree lhs; |
1995 | enum tree_code lhs_code; | |
4ee9c684 | 1996 | |
75a70cf9 | 1997 | gcc_assert (is_gimple_assign (stmt)); |
1998 | ||
1999 | lhs = gimple_assign_lhs (stmt); | |
2000 | lhs_code = TREE_CODE (lhs); | |
4ee9c684 | 2001 | |
75a70cf9 | 2002 | if (lhs_code == SSA_NAME |
912886f2 | 2003 | && gimple_assign_single_p (stmt)) |
75a70cf9 | 2004 | { |
2005 | tree rhs = gimple_assign_rhs1 (stmt); | |
48e1416a | 2006 | |
4ee9c684 | 2007 | /* If the RHS of the assignment is a constant or another variable that |
2008 | may be propagated, register it in the CONST_AND_COPIES table. We | |
2009 | do not need to record unwind data for this, since this is a true | |
365db11e | 2010 | assignment and not an equivalence inferred from a comparison. All |
4ee9c684 | 2011 | uses of this ssa name are dominated by this assignment, so unwinding |
2012 | just costs time and space. */ | |
2013 | if (may_optimize_p | |
2014 | && (TREE_CODE (rhs) == SSA_NAME | |
2015 | || is_gimple_min_invariant (rhs))) | |
75a70cf9 | 2016 | { |
2017 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2018 | { | |
2019 | fprintf (dump_file, "==== ASGN "); | |
2020 | print_generic_expr (dump_file, lhs, 0); | |
2021 | fprintf (dump_file, " = "); | |
2022 | print_generic_expr (dump_file, rhs, 0); | |
2023 | fprintf (dump_file, "\n"); | |
2024 | } | |
2025 | ||
f003f9fd | 2026 | set_ssa_name_value (lhs, rhs); |
75a70cf9 | 2027 | } |
4ee9c684 | 2028 | } |
2029 | ||
4ee9c684 | 2030 | /* A memory store, even an aliased store, creates a useful |
2031 | equivalence. By exchanging the LHS and RHS, creating suitable | |
2032 | vops and recording the result in the available expression table, | |
2033 | we may be able to expose more redundant loads. */ | |
75a70cf9 | 2034 | if (!gimple_has_volatile_ops (stmt) |
2035 | && gimple_references_memory_p (stmt) | |
2036 | && gimple_assign_single_p (stmt) | |
2037 | && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
2038 | || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) | |
4ee9c684 | 2039 | && !is_gimple_reg (lhs)) |
2040 | { | |
75a70cf9 | 2041 | tree rhs = gimple_assign_rhs1 (stmt); |
2042 | gimple new_stmt; | |
4ee9c684 | 2043 | |
e607210a | 2044 | /* Build a new statement with the RHS and LHS exchanged. */ |
75a70cf9 | 2045 | if (TREE_CODE (rhs) == SSA_NAME) |
2046 | { | |
2047 | /* NOTE tuples. The call to gimple_build_assign below replaced | |
2048 | a call to build_gimple_modify_stmt, which did not set the | |
2049 | SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so | |
2050 | may cause an SSA validation failure, as the LHS may be a | |
2051 | default-initialized name and should have no definition. I'm | |
2052 | a bit dubious of this, as the artificial statement that we | |
2053 | generate here may in fact be ill-formed, but it is simply | |
2054 | used as an internal device in this pass, and never becomes | |
2055 | part of the CFG. */ | |
2056 | gimple defstmt = SSA_NAME_DEF_STMT (rhs); | |
2057 | new_stmt = gimple_build_assign (rhs, lhs); | |
2058 | SSA_NAME_DEF_STMT (rhs) = defstmt; | |
2059 | } | |
2060 | else | |
2061 | new_stmt = gimple_build_assign (rhs, lhs); | |
2062 | ||
dd277d48 | 2063 | gimple_set_vuse (new_stmt, gimple_vdef (stmt)); |
4ee9c684 | 2064 | |
e607210a | 2065 | /* Finally enter the statement into the available expression |
2066 | table. */ | |
2067 | lookup_avail_expr (new_stmt, true); | |
4ee9c684 | 2068 | } |
2069 | } | |
2070 | ||
591c2a30 | 2071 | /* Replace *OP_P in STMT with any known equivalent value for *OP_P from |
2072 | CONST_AND_COPIES. */ | |
2073 | ||
e08ff65a | 2074 | static void |
75a70cf9 | 2075 | cprop_operand (gimple stmt, use_operand_p op_p) |
591c2a30 | 2076 | { |
591c2a30 | 2077 | tree val; |
2078 | tree op = USE_FROM_PTR (op_p); | |
2079 | ||
2080 | /* If the operand has a known constant value or it is known to be a | |
2081 | copy of some other variable, use the value or copy stored in | |
2082 | CONST_AND_COPIES. */ | |
4c7a0518 | 2083 | val = SSA_NAME_VALUE (op); |
f6c33c78 | 2084 | if (val && val != op) |
591c2a30 | 2085 | { |
93b4f514 | 2086 | /* Do not replace hard register operands in asm statements. */ |
75a70cf9 | 2087 | if (gimple_code (stmt) == GIMPLE_ASM |
93b4f514 | 2088 | && !may_propagate_copy_into_asm (op)) |
e08ff65a | 2089 | return; |
93b4f514 | 2090 | |
591c2a30 | 2091 | /* Certain operands are not allowed to be copy propagated due |
2092 | to their interaction with exception handling and some GCC | |
2093 | extensions. */ | |
93f3673b | 2094 | if (!may_propagate_copy (op, val)) |
e08ff65a | 2095 | return; |
93f3673b | 2096 | |
2097 | /* Do not propagate addresses that point to volatiles into memory | |
2098 | stmts without volatile operands. */ | |
2099 | if (POINTER_TYPE_P (TREE_TYPE (val)) | |
2100 | && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val))) | |
2101 | && gimple_has_mem_ops (stmt) | |
2102 | && !gimple_has_volatile_ops (stmt)) | |
e08ff65a | 2103 | return; |
93f3673b | 2104 | |
652a5bec | 2105 | /* Do not propagate copies if the propagated value is at a deeper loop |
2106 | depth than the propagatee. Otherwise, this may move loop variant | |
2107 | variables outside of their loops and prevent coalescing | |
2108 | opportunities. If the value was loop invariant, it will be hoisted | |
2109 | by LICM and exposed for copy propagation. */ | |
2110 | if (loop_depth_of_name (val) > loop_depth_of_name (op)) | |
e08ff65a | 2111 | return; |
591c2a30 | 2112 | |
09d0041c | 2113 | /* Do not propagate copies into simple IV increment statements. |
2114 | See PR23821 for how this can disturb IV analysis. */ | |
2115 | if (TREE_CODE (val) != INTEGER_CST | |
2116 | && simple_iv_increment_p (stmt)) | |
2117 | return; | |
2118 | ||
591c2a30 | 2119 | /* Dump details. */ |
2120 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2121 | { | |
2122 | fprintf (dump_file, " Replaced '"); | |
2123 | print_generic_expr (dump_file, op, dump_flags); | |
2124 | fprintf (dump_file, "' with %s '", | |
2125 | (TREE_CODE (val) != SSA_NAME ? "constant" : "variable")); | |
2126 | print_generic_expr (dump_file, val, dump_flags); | |
2127 | fprintf (dump_file, "'\n"); | |
2128 | } | |
2129 | ||
88dbf20f | 2130 | if (TREE_CODE (val) != SSA_NAME) |
2131 | opt_stats.num_const_prop++; | |
2132 | else | |
2133 | opt_stats.num_copy_prop++; | |
2134 | ||
591c2a30 | 2135 | propagate_value (op_p, val); |
2136 | ||
2137 | /* And note that we modified this statement. This is now | |
2138 | safe, even if we changed virtual operands since we will | |
2139 | rescan the statement and rewrite its operands again. */ | |
75a70cf9 | 2140 | gimple_set_modified (stmt, true); |
591c2a30 | 2141 | } |
591c2a30 | 2142 | } |
2143 | ||
2144 | /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current | |
48e1416a | 2145 | known value for that SSA_NAME (or NULL if no value is known). |
591c2a30 | 2146 | |
2147 | Propagate values from CONST_AND_COPIES into the uses, vuses and | |
de6ed584 | 2148 | vdef_ops of STMT. */ |
591c2a30 | 2149 | |
e08ff65a | 2150 | static void |
75a70cf9 | 2151 | cprop_into_stmt (gimple stmt) |
591c2a30 | 2152 | { |
43daa21e | 2153 | use_operand_p op_p; |
2154 | ssa_op_iter iter; | |
591c2a30 | 2155 | |
8bf038d5 | 2156 | FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE) |
2157 | cprop_operand (stmt, op_p); | |
591c2a30 | 2158 | } |
2159 | ||
5206b159 | 2160 | /* Optimize the statement pointed to by iterator SI. |
48e1416a | 2161 | |
4ee9c684 | 2162 | We try to perform some simplistic global redundancy elimination and |
2163 | constant propagation: | |
2164 | ||
2165 | 1- To detect global redundancy, we keep track of expressions that have | |
2166 | been computed in this block and its dominators. If we find that the | |
2167 | same expression is computed more than once, we eliminate repeated | |
2168 | computations by using the target of the first one. | |
2169 | ||
2170 | 2- Constant values and copy assignments. This is used to do very | |
2171 | simplistic constant and copy propagation. When a constant or copy | |
2172 | assignment is found, we map the value on the RHS of the assignment to | |
2173 | the variable in the LHS in the CONST_AND_COPIES table. */ | |
2174 | ||
2175 | static void | |
6bf320fb | 2176 | optimize_stmt (basic_block bb, gimple_stmt_iterator si) |
4ee9c684 | 2177 | { |
75a70cf9 | 2178 | gimple stmt, old_stmt; |
4ee9c684 | 2179 | bool may_optimize_p; |
c8c258fe | 2180 | bool modified_p = false; |
4ee9c684 | 2181 | |
75a70cf9 | 2182 | old_stmt = stmt = gsi_stmt (si); |
48e1416a | 2183 | |
4ee9c684 | 2184 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2185 | { | |
2186 | fprintf (dump_file, "Optimizing statement "); | |
75a70cf9 | 2187 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
4ee9c684 | 2188 | } |
2189 | ||
8bf038d5 | 2190 | if (gimple_code (stmt) == GIMPLE_COND) |
2191 | canonicalize_comparison (stmt); | |
2192 | ||
2193 | update_stmt_if_modified (stmt); | |
2194 | opt_stats.num_stmts++; | |
2195 | ||
de6ed584 | 2196 | /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */ |
e08ff65a | 2197 | cprop_into_stmt (stmt); |
4ee9c684 | 2198 | |
2199 | /* If the statement has been modified with constant replacements, | |
2200 | fold its RHS before checking for redundant computations. */ | |
75a70cf9 | 2201 | if (gimple_modified_p (stmt)) |
4ee9c684 | 2202 | { |
75a70cf9 | 2203 | tree rhs = NULL; |
f2fae51f | 2204 | |
4ee9c684 | 2205 | /* Try to fold the statement making sure that STMT is kept |
2206 | up to date. */ | |
75a70cf9 | 2207 | if (fold_stmt (&si)) |
4ee9c684 | 2208 | { |
75a70cf9 | 2209 | stmt = gsi_stmt (si); |
7548e9fe | 2210 | gimple_set_modified (stmt, true); |
4ee9c684 | 2211 | |
2212 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2213 | { | |
2214 | fprintf (dump_file, " Folded to: "); | |
75a70cf9 | 2215 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
4ee9c684 | 2216 | } |
2217 | } | |
2218 | ||
75a70cf9 | 2219 | /* We only need to consider cases that can yield a gimple operand. */ |
2220 | if (gimple_assign_single_p (stmt)) | |
2221 | rhs = gimple_assign_rhs1 (stmt); | |
2222 | else if (gimple_code (stmt) == GIMPLE_GOTO) | |
2223 | rhs = gimple_goto_dest (stmt); | |
2224 | else if (gimple_code (stmt) == GIMPLE_SWITCH) | |
2225 | /* This should never be an ADDR_EXPR. */ | |
2226 | rhs = gimple_switch_index (stmt); | |
2227 | ||
f2fae51f | 2228 | if (rhs && TREE_CODE (rhs) == ADDR_EXPR) |
75a70cf9 | 2229 | recompute_tree_invariant_for_addr_expr (rhs); |
f2fae51f | 2230 | |
c8c258fe | 2231 | /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called, |
2232 | even if fold_stmt updated the stmt already and thus cleared | |
2233 | gimple_modified_p flag on it. */ | |
2234 | modified_p = true; | |
4ee9c684 | 2235 | } |
2236 | ||
2237 | /* Check for redundant computations. Do this optimization only | |
2238 | for assignments that have no volatile ops and conditionals. */ | |
f1960495 | 2239 | may_optimize_p = (!gimple_has_side_effects (stmt) |
2240 | && (is_gimple_assign (stmt) | |
75a70cf9 | 2241 | || (is_gimple_call (stmt) |
f1960495 | 2242 | && gimple_call_lhs (stmt) != NULL_TREE) |
75a70cf9 | 2243 | || gimple_code (stmt) == GIMPLE_COND |
2244 | || gimple_code (stmt) == GIMPLE_SWITCH)); | |
4ee9c684 | 2245 | |
2246 | if (may_optimize_p) | |
75a70cf9 | 2247 | { |
a65c4d64 | 2248 | if (gimple_code (stmt) == GIMPLE_CALL) |
2249 | { | |
2250 | /* Resolve __builtin_constant_p. If it hasn't been | |
2251 | folded to integer_one_node by now, it's fairly | |
2252 | certain that the value simply isn't constant. */ | |
2253 | tree callee = gimple_call_fndecl (stmt); | |
2254 | if (callee | |
2255 | && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL | |
2256 | && DECL_FUNCTION_CODE (callee) == BUILT_IN_CONSTANT_P) | |
2257 | { | |
2258 | propagate_tree_value_into_stmt (&si, integer_zero_node); | |
2259 | stmt = gsi_stmt (si); | |
2260 | } | |
2261 | } | |
04c3b49f | 2262 | |
2263 | update_stmt_if_modified (stmt); | |
2264 | eliminate_redundant_computations (&si); | |
2265 | stmt = gsi_stmt (si); | |
31047158 | 2266 | |
2267 | /* Perform simple redundant store elimination. */ | |
2268 | if (gimple_assign_single_p (stmt) | |
2269 | && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME) | |
2270 | { | |
2271 | tree lhs = gimple_assign_lhs (stmt); | |
2272 | tree rhs = gimple_assign_rhs1 (stmt); | |
2273 | tree cached_lhs; | |
2274 | gimple new_stmt; | |
2275 | if (TREE_CODE (rhs) == SSA_NAME) | |
2276 | { | |
2277 | tree tem = SSA_NAME_VALUE (rhs); | |
2278 | if (tem) | |
2279 | rhs = tem; | |
2280 | } | |
2281 | /* Build a new statement with the RHS and LHS exchanged. */ | |
2282 | if (TREE_CODE (rhs) == SSA_NAME) | |
2283 | { | |
2284 | gimple defstmt = SSA_NAME_DEF_STMT (rhs); | |
2285 | new_stmt = gimple_build_assign (rhs, lhs); | |
2286 | SSA_NAME_DEF_STMT (rhs) = defstmt; | |
2287 | } | |
2288 | else | |
2289 | new_stmt = gimple_build_assign (rhs, lhs); | |
2290 | gimple_set_vuse (new_stmt, gimple_vuse (stmt)); | |
2291 | cached_lhs = lookup_avail_expr (new_stmt, false); | |
2292 | if (cached_lhs | |
2293 | && rhs == cached_lhs) | |
2294 | { | |
2295 | basic_block bb = gimple_bb (stmt); | |
31047158 | 2296 | unlink_stmt_vdef (stmt); |
13ff78a4 | 2297 | if (gsi_remove (&si, true)) |
31047158 | 2298 | { |
2299 | bitmap_set_bit (need_eh_cleanup, bb->index); | |
2300 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2301 | fprintf (dump_file, " Flagged to clear EH edges.\n"); | |
2302 | } | |
bc8a8451 | 2303 | release_defs (stmt); |
31047158 | 2304 | return; |
2305 | } | |
2306 | } | |
75a70cf9 | 2307 | } |
4ee9c684 | 2308 | |
2309 | /* Record any additional equivalences created by this statement. */ | |
75a70cf9 | 2310 | if (is_gimple_assign (stmt)) |
2311 | record_equivalences_from_stmt (stmt, may_optimize_p); | |
4ee9c684 | 2312 | |
4ee9c684 | 2313 | /* If STMT is a COND_EXPR and it was modified, then we may know |
2314 | where it goes. If that is the case, then mark the CFG as altered. | |
2315 | ||
2316 | This will cause us to later call remove_unreachable_blocks and | |
48e1416a | 2317 | cleanup_tree_cfg when it is safe to do so. It is not safe to |
4ee9c684 | 2318 | clean things up here since removal of edges and such can trigger |
2319 | the removal of PHI nodes, which in turn can release SSA_NAMEs to | |
2320 | the manager. | |
2321 | ||
2322 | That's all fine and good, except that once SSA_NAMEs are released | |
2323 | to the manager, we must not call create_ssa_name until all references | |
2324 | to released SSA_NAMEs have been eliminated. | |
2325 | ||
2326 | All references to the deleted SSA_NAMEs can not be eliminated until | |
2327 | we remove unreachable blocks. | |
2328 | ||
2329 | We can not remove unreachable blocks until after we have completed | |
2330 | any queued jump threading. | |
2331 | ||
2332 | We can not complete any queued jump threads until we have taken | |
2333 | appropriate variables out of SSA form. Taking variables out of | |
2334 | SSA form can call create_ssa_name and thus we lose. | |
2335 | ||
2336 | Ultimately I suspect we're going to need to change the interface | |
2337 | into the SSA_NAME manager. */ | |
c8c258fe | 2338 | if (gimple_modified_p (stmt) || modified_p) |
4ee9c684 | 2339 | { |
2340 | tree val = NULL; | |
48e1416a | 2341 | |
04c3b49f | 2342 | update_stmt_if_modified (stmt); |
4ee9c684 | 2343 | |
75a70cf9 | 2344 | if (gimple_code (stmt) == GIMPLE_COND) |
389dd41b | 2345 | val = fold_binary_loc (gimple_location (stmt), |
2346 | gimple_cond_code (stmt), boolean_type_node, | |
75a70cf9 | 2347 | gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); |
2348 | else if (gimple_code (stmt) == GIMPLE_SWITCH) | |
2349 | val = gimple_switch_index (stmt); | |
4ee9c684 | 2350 | |
35c15734 | 2351 | if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val)) |
4ee9c684 | 2352 | cfg_altered = true; |
35c15734 | 2353 | |
2354 | /* If we simplified a statement in such a way as to be shown that it | |
2355 | cannot trap, update the eh information and the cfg to match. */ | |
4c27dd45 | 2356 | if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) |
35c15734 | 2357 | { |
2358 | bitmap_set_bit (need_eh_cleanup, bb->index); | |
2359 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2360 | fprintf (dump_file, " Flagged to clear EH edges.\n"); | |
2361 | } | |
4ee9c684 | 2362 | } |
4ee9c684 | 2363 | } |
2364 | ||
75a70cf9 | 2365 | /* Search for an existing instance of STMT in the AVAIL_EXPRS table. |
2366 | If found, return its LHS. Otherwise insert STMT in the table and | |
2367 | return NULL_TREE. | |
4ee9c684 | 2368 | |
75a70cf9 | 2369 | Also, when an expression is first inserted in the table, it is also |
2370 | is also added to AVAIL_EXPRS_STACK, so that it can be removed when | |
2371 | we finish processing this block and its children. */ | |
4ee9c684 | 2372 | |
2373 | static tree | |
75a70cf9 | 2374 | lookup_avail_expr (gimple stmt, bool insert) |
4ee9c684 | 2375 | { |
2376 | void **slot; | |
2377 | tree lhs; | |
2378 | tree temp; | |
88006128 | 2379 | struct expr_hash_elt element; |
4ee9c684 | 2380 | |
889ef038 | 2381 | /* Get LHS of phi, assignment, or call; else NULL_TREE. */ |
2382 | if (gimple_code (stmt) == GIMPLE_PHI) | |
2383 | lhs = gimple_phi_result (stmt); | |
2384 | else | |
2385 | lhs = gimple_get_lhs (stmt); | |
4ee9c684 | 2386 | |
88006128 | 2387 | initialize_hash_element (stmt, lhs, &element); |
4ee9c684 | 2388 | |
75a70cf9 | 2389 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2390 | { | |
2391 | fprintf (dump_file, "LKUP "); | |
88006128 | 2392 | print_expr_hash_elt (dump_file, &element); |
75a70cf9 | 2393 | } |
2394 | ||
4ee9c684 | 2395 | /* Don't bother remembering constant assignments and copy operations. |
2396 | Constants and copy operations are handled by the constant/copy propagator | |
2397 | in optimize_stmt. */ | |
88006128 | 2398 | if (element.expr.kind == EXPR_SINGLE |
2399 | && (TREE_CODE (element.expr.ops.single.rhs) == SSA_NAME | |
2400 | || is_gimple_min_invariant (element.expr.ops.single.rhs))) | |
2401 | return NULL_TREE; | |
4ee9c684 | 2402 | |
4ee9c684 | 2403 | /* Finally try to find the expression in the main expression hash table. */ |
88006128 | 2404 | slot = htab_find_slot_with_hash (avail_exprs, &element, element.hash, |
4ee9c684 | 2405 | (insert ? INSERT : NO_INSERT)); |
2406 | if (slot == NULL) | |
88006128 | 2407 | return NULL_TREE; |
4ee9c684 | 2408 | |
2409 | if (*slot == NULL) | |
2410 | { | |
88006128 | 2411 | struct expr_hash_elt *element2 = XNEW (struct expr_hash_elt); |
2412 | *element2 = element; | |
2413 | element2->stamp = element2; | |
2414 | *slot = (void *) element2; | |
75a70cf9 | 2415 | |
2416 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2417 | { | |
2418 | fprintf (dump_file, "2>>> "); | |
88006128 | 2419 | print_expr_hash_elt (dump_file, element2); |
75a70cf9 | 2420 | } |
2421 | ||
88006128 | 2422 | VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element2); |
4ee9c684 | 2423 | return NULL_TREE; |
2424 | } | |
2425 | ||
2426 | /* Extract the LHS of the assignment so that it can be used as the current | |
2427 | definition of another variable. */ | |
2428 | lhs = ((struct expr_hash_elt *)*slot)->lhs; | |
2429 | ||
2430 | /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then | |
2431 | use the value from the const_and_copies table. */ | |
2432 | if (TREE_CODE (lhs) == SSA_NAME) | |
2433 | { | |
4c7a0518 | 2434 | temp = SSA_NAME_VALUE (lhs); |
f6c33c78 | 2435 | if (temp) |
4ee9c684 | 2436 | lhs = temp; |
2437 | } | |
2438 | ||
75a70cf9 | 2439 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2440 | { | |
2441 | fprintf (dump_file, "FIND: "); | |
2442 | print_generic_expr (dump_file, lhs, 0); | |
2443 | fprintf (dump_file, "\n"); | |
2444 | } | |
2445 | ||
4ee9c684 | 2446 | return lhs; |
2447 | } | |
2448 | ||
75a70cf9 | 2449 | /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number |
2450 | for expressions using the code of the expression and the SSA numbers of | |
2451 | its operands. */ | |
4ee9c684 | 2452 | |
2453 | static hashval_t | |
2454 | avail_expr_hash (const void *p) | |
2455 | { | |
75a70cf9 | 2456 | gimple stmt = ((const struct expr_hash_elt *)p)->stmt; |
2457 | const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr; | |
b66731e8 | 2458 | tree vuse; |
4ee9c684 | 2459 | hashval_t val = 0; |
4ee9c684 | 2460 | |
75a70cf9 | 2461 | val = iterative_hash_hashable_expr (expr, val); |
4ee9c684 | 2462 | |
2463 | /* If the hash table entry is not associated with a statement, then we | |
2464 | can just hash the expression and not worry about virtual operands | |
2465 | and such. */ | |
75a70cf9 | 2466 | if (!stmt) |
4ee9c684 | 2467 | return val; |
2468 | ||
dd277d48 | 2469 | /* Add the SSA version numbers of the vuse operand. This is important |
4ee9c684 | 2470 | because compound variables like arrays are not renamed in the |
2471 | operands. Rather, the rename is done on the virtual variable | |
2472 | representing all the elements of the array. */ | |
dd277d48 | 2473 | if ((vuse = gimple_vuse (stmt))) |
b66731e8 | 2474 | val = iterative_hash_expr (vuse, val); |
4ee9c684 | 2475 | |
2476 | return val; | |
2477 | } | |
2478 | ||
23ace16d | 2479 | static hashval_t |
2480 | real_avail_expr_hash (const void *p) | |
2481 | { | |
2482 | return ((const struct expr_hash_elt *)p)->hash; | |
2483 | } | |
4ee9c684 | 2484 | |
2485 | static int | |
2486 | avail_expr_eq (const void *p1, const void *p2) | |
2487 | { | |
75a70cf9 | 2488 | gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt; |
2489 | const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr; | |
2490 | const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp; | |
2491 | gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt; | |
2492 | const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr; | |
2493 | const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp; | |
2494 | ||
2495 | /* This case should apply only when removing entries from the table. */ | |
2496 | if (stamp1 == stamp2) | |
4ee9c684 | 2497 | return true; |
2498 | ||
75a70cf9 | 2499 | /* FIXME tuples: |
2500 | We add stmts to a hash table and them modify them. To detect the case | |
2501 | that we modify a stmt and then search for it, we assume that the hash | |
2502 | is always modified by that change. | |
2503 | We have to fully check why this doesn't happen on trunk or rewrite | |
2504 | this in a more reliable (and easier to understand) way. */ | |
2505 | if (((const struct expr_hash_elt *)p1)->hash | |
2506 | != ((const struct expr_hash_elt *)p2)->hash) | |
4ee9c684 | 2507 | return false; |
2508 | ||
2509 | /* In case of a collision, both RHS have to be identical and have the | |
2510 | same VUSE operands. */ | |
75a70cf9 | 2511 | if (hashable_expr_equal_p (expr1, expr2) |
2512 | && types_compatible_p (expr1->type, expr2->type)) | |
4ee9c684 | 2513 | { |
75a70cf9 | 2514 | /* Note that STMT1 and/or STMT2 may be NULL. */ |
dd277d48 | 2515 | return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE) |
2516 | == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE)); | |
4ee9c684 | 2517 | } |
2518 | ||
2519 | return false; | |
2520 | } | |
d1d2af7d | 2521 | |
2522 | /* PHI-ONLY copy and constant propagation. This pass is meant to clean | |
2523 | up degenerate PHIs created by or exposed by jump threading. */ | |
2524 | ||
2525 | /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return | |
2526 | NULL. */ | |
2527 | ||
ac9b13de | 2528 | tree |
75a70cf9 | 2529 | degenerate_phi_result (gimple phi) |
d1d2af7d | 2530 | { |
75a70cf9 | 2531 | tree lhs = gimple_phi_result (phi); |
d1d2af7d | 2532 | tree val = NULL; |
75a70cf9 | 2533 | size_t i; |
d1d2af7d | 2534 | |
2535 | /* Ignoring arguments which are the same as LHS, if all the remaining | |
2536 | arguments are the same, then the PHI is a degenerate and has the | |
2537 | value of that common argument. */ | |
75a70cf9 | 2538 | for (i = 0; i < gimple_phi_num_args (phi); i++) |
d1d2af7d | 2539 | { |
75a70cf9 | 2540 | tree arg = gimple_phi_arg_def (phi, i); |
d1d2af7d | 2541 | |
2542 | if (arg == lhs) | |
2543 | continue; | |
4eb376e3 | 2544 | else if (!arg) |
2545 | break; | |
d1d2af7d | 2546 | else if (!val) |
2547 | val = arg; | |
43e54ec3 | 2548 | else if (arg == val) |
2549 | continue; | |
2550 | /* We bring in some of operand_equal_p not only to speed things | |
2551 | up, but also to avoid crashing when dereferencing the type of | |
2552 | a released SSA name. */ | |
4eb376e3 | 2553 | else if (TREE_CODE (val) != TREE_CODE (arg) |
43e54ec3 | 2554 | || TREE_CODE (val) == SSA_NAME |
2555 | || !operand_equal_p (arg, val, 0)) | |
d1d2af7d | 2556 | break; |
2557 | } | |
75a70cf9 | 2558 | return (i == gimple_phi_num_args (phi) ? val : NULL); |
d1d2af7d | 2559 | } |
2560 | ||
75a70cf9 | 2561 | /* Given a statement STMT, which is either a PHI node or an assignment, |
d1d2af7d | 2562 | remove it from the IL. */ |
2563 | ||
2564 | static void | |
75a70cf9 | 2565 | remove_stmt_or_phi (gimple stmt) |
d1d2af7d | 2566 | { |
75a70cf9 | 2567 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); |
2568 | ||
2569 | if (gimple_code (stmt) == GIMPLE_PHI) | |
2570 | remove_phi_node (&gsi, true); | |
d1d2af7d | 2571 | else |
2572 | { | |
75a70cf9 | 2573 | gsi_remove (&gsi, true); |
2574 | release_defs (stmt); | |
d1d2af7d | 2575 | } |
2576 | } | |
2577 | ||
75a70cf9 | 2578 | /* Given a statement STMT, which is either a PHI node or an assignment, |
d1d2af7d | 2579 | return the "rhs" of the node, in the case of a non-degenerate |
75a70cf9 | 2580 | phi, NULL is returned. */ |
d1d2af7d | 2581 | |
2582 | static tree | |
75a70cf9 | 2583 | get_rhs_or_phi_arg (gimple stmt) |
d1d2af7d | 2584 | { |
75a70cf9 | 2585 | if (gimple_code (stmt) == GIMPLE_PHI) |
2586 | return degenerate_phi_result (stmt); | |
2587 | else if (gimple_assign_single_p (stmt)) | |
2588 | return gimple_assign_rhs1 (stmt); | |
2589 | else | |
2590 | gcc_unreachable (); | |
d1d2af7d | 2591 | } |
2592 | ||
2593 | ||
75a70cf9 | 2594 | /* Given a statement STMT, which is either a PHI node or an assignment, |
d1d2af7d | 2595 | return the "lhs" of the node. */ |
2596 | ||
2597 | static tree | |
75a70cf9 | 2598 | get_lhs_or_phi_result (gimple stmt) |
d1d2af7d | 2599 | { |
75a70cf9 | 2600 | if (gimple_code (stmt) == GIMPLE_PHI) |
2601 | return gimple_phi_result (stmt); | |
2602 | else if (is_gimple_assign (stmt)) | |
2603 | return gimple_assign_lhs (stmt); | |
2604 | else | |
2605 | gcc_unreachable (); | |
d1d2af7d | 2606 | } |
2607 | ||
2608 | /* Propagate RHS into all uses of LHS (when possible). | |
2609 | ||
2610 | RHS and LHS are derived from STMT, which is passed in solely so | |
2611 | that we can remove it if propagation is successful. | |
2612 | ||
2613 | When propagating into a PHI node or into a statement which turns | |
2614 | into a trivial copy or constant initialization, set the | |
2615 | appropriate bit in INTERESTING_NAMEs so that we will visit those | |
2616 | nodes as well in an effort to pick up secondary optimization | |
2617 | opportunities. */ | |
2618 | ||
48e1416a | 2619 | static void |
75a70cf9 | 2620 | propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names) |
d1d2af7d | 2621 | { |
2622 | /* First verify that propagation is valid and isn't going to move a | |
2623 | loop variant variable outside its loop. */ | |
2624 | if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) | |
2625 | && (TREE_CODE (rhs) != SSA_NAME | |
2626 | || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) | |
2627 | && may_propagate_copy (lhs, rhs) | |
2628 | && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs)) | |
2629 | { | |
2630 | use_operand_p use_p; | |
2631 | imm_use_iterator iter; | |
75a70cf9 | 2632 | gimple use_stmt; |
d1d2af7d | 2633 | bool all = true; |
2634 | ||
2635 | /* Dump details. */ | |
2636 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2637 | { | |
2638 | fprintf (dump_file, " Replacing '"); | |
2639 | print_generic_expr (dump_file, lhs, dump_flags); | |
2640 | fprintf (dump_file, "' with %s '", | |
2641 | (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable")); | |
2642 | print_generic_expr (dump_file, rhs, dump_flags); | |
2643 | fprintf (dump_file, "'\n"); | |
2644 | } | |
2645 | ||
48e1416a | 2646 | /* Walk over every use of LHS and try to replace the use with RHS. |
d1d2af7d | 2647 | At this point the only reason why such a propagation would not |
2648 | be successful would be if the use occurs in an ASM_EXPR. */ | |
09aca5bc | 2649 | FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) |
d1d2af7d | 2650 | { |
9845d120 | 2651 | /* Leave debug stmts alone. If we succeed in propagating |
2652 | all non-debug uses, we'll drop the DEF, and propagation | |
2653 | into debug stmts will occur then. */ | |
2654 | if (gimple_debug_bind_p (use_stmt)) | |
2655 | continue; | |
48e1416a | 2656 | |
d1d2af7d | 2657 | /* It's not always safe to propagate into an ASM_EXPR. */ |
75a70cf9 | 2658 | if (gimple_code (use_stmt) == GIMPLE_ASM |
2659 | && ! may_propagate_copy_into_asm (lhs)) | |
d1d2af7d | 2660 | { |
2661 | all = false; | |
2662 | continue; | |
2663 | } | |
2664 | ||
ec396ca3 | 2665 | /* It's not ok to propagate into the definition stmt of RHS. |
2666 | <bb 9>: | |
2667 | # prephitmp.12_36 = PHI <g_67.1_6(9)> | |
2668 | g_67.1_6 = prephitmp.12_36; | |
2669 | goto <bb 9>; | |
2670 | While this is strictly all dead code we do not want to | |
2671 | deal with this here. */ | |
2672 | if (TREE_CODE (rhs) == SSA_NAME | |
2673 | && SSA_NAME_DEF_STMT (rhs) == use_stmt) | |
2674 | { | |
2675 | all = false; | |
2676 | continue; | |
2677 | } | |
2678 | ||
d1d2af7d | 2679 | /* Dump details. */ |
2680 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2681 | { | |
2682 | fprintf (dump_file, " Original statement:"); | |
75a70cf9 | 2683 | print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); |
d1d2af7d | 2684 | } |
2685 | ||
d76551d9 | 2686 | /* Propagate the RHS into this use of the LHS. */ |
09aca5bc | 2687 | FOR_EACH_IMM_USE_ON_STMT (use_p, iter) |
2688 | propagate_value (use_p, rhs); | |
d76551d9 | 2689 | |
2690 | /* Special cases to avoid useless calls into the folding | |
2691 | routines, operand scanning, etc. | |
2692 | ||
2693 | First, propagation into a PHI may cause the PHI to become | |
2694 | a degenerate, so mark the PHI as interesting. No other | |
2695 | actions are necessary. | |
2696 | ||
2697 | Second, if we're propagating a virtual operand and the | |
2698 | propagation does not change the underlying _DECL node for | |
2699 | the virtual operand, then no further actions are necessary. */ | |
75a70cf9 | 2700 | if (gimple_code (use_stmt) == GIMPLE_PHI |
d76551d9 | 2701 | || (! is_gimple_reg (lhs) |
2702 | && TREE_CODE (rhs) == SSA_NAME | |
2703 | && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs))) | |
2704 | { | |
2705 | /* Dump details. */ | |
2706 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2707 | { | |
2708 | fprintf (dump_file, " Updated statement:"); | |
75a70cf9 | 2709 | print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); |
d76551d9 | 2710 | } |
2711 | ||
2712 | /* Propagation into a PHI may expose new degenerate PHIs, | |
2713 | so mark the result of the PHI as interesting. */ | |
75a70cf9 | 2714 | if (gimple_code (use_stmt) == GIMPLE_PHI) |
d76551d9 | 2715 | { |
2716 | tree result = get_lhs_or_phi_result (use_stmt); | |
2717 | bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); | |
2718 | } | |
de6ed584 | 2719 | |
d76551d9 | 2720 | continue; |
2721 | } | |
2722 | ||
48e1416a | 2723 | /* From this point onward we are propagating into a |
d76551d9 | 2724 | real statement. Folding may (or may not) be possible, |
2725 | we may expose new operands, expose dead EH edges, | |
2726 | etc. */ | |
75a70cf9 | 2727 | /* NOTE tuples. In the tuples world, fold_stmt_inplace |
2728 | cannot fold a call that simplifies to a constant, | |
2729 | because the GIMPLE_CALL must be replaced by a | |
2730 | GIMPLE_ASSIGN, and there is no way to effect such a | |
2731 | transformation in-place. We might want to consider | |
2732 | using the more general fold_stmt here. */ | |
50aacf4c | 2733 | { |
2734 | gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); | |
2735 | fold_stmt_inplace (&gsi); | |
2736 | } | |
2f067d14 | 2737 | |
2738 | /* Sometimes propagation can expose new operands to the | |
4c5fd53c | 2739 | renamer. */ |
2740 | update_stmt (use_stmt); | |
d1d2af7d | 2741 | |
2742 | /* Dump details. */ | |
2743 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2744 | { | |
2745 | fprintf (dump_file, " Updated statement:"); | |
75a70cf9 | 2746 | print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); |
d1d2af7d | 2747 | } |
2748 | ||
d1d2af7d | 2749 | /* If we replaced a variable index with a constant, then |
2750 | we would need to update the invariant flag for ADDR_EXPRs. */ | |
75a70cf9 | 2751 | if (gimple_assign_single_p (use_stmt) |
2752 | && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR) | |
35cc02b5 | 2753 | recompute_tree_invariant_for_addr_expr |
75a70cf9 | 2754 | (gimple_assign_rhs1 (use_stmt)); |
d1d2af7d | 2755 | |
2756 | /* If we cleaned up EH information from the statement, | |
d65e4929 | 2757 | mark its containing block as needing EH cleanups. */ |
d1d2af7d | 2758 | if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt)) |
d65e4929 | 2759 | { |
75a70cf9 | 2760 | bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index); |
d65e4929 | 2761 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2762 | fprintf (dump_file, " Flagged to clear EH edges.\n"); | |
2763 | } | |
d1d2af7d | 2764 | |
d76551d9 | 2765 | /* Propagation may expose new trivial copy/constant propagation |
2766 | opportunities. */ | |
75a70cf9 | 2767 | if (gimple_assign_single_p (use_stmt) |
2768 | && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME | |
2769 | && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME | |
2770 | || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt)))) | |
2771 | { | |
d1d2af7d | 2772 | tree result = get_lhs_or_phi_result (use_stmt); |
2773 | bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); | |
2774 | } | |
2775 | ||
2776 | /* Propagation into these nodes may make certain edges in | |
2777 | the CFG unexecutable. We want to identify them as PHI nodes | |
2778 | at the destination of those unexecutable edges may become | |
2779 | degenerates. */ | |
75a70cf9 | 2780 | else if (gimple_code (use_stmt) == GIMPLE_COND |
2781 | || gimple_code (use_stmt) == GIMPLE_SWITCH | |
2782 | || gimple_code (use_stmt) == GIMPLE_GOTO) | |
2783 | { | |
d1d2af7d | 2784 | tree val; |
2785 | ||
75a70cf9 | 2786 | if (gimple_code (use_stmt) == GIMPLE_COND) |
389dd41b | 2787 | val = fold_binary_loc (gimple_location (use_stmt), |
2788 | gimple_cond_code (use_stmt), | |
75a70cf9 | 2789 | boolean_type_node, |
2790 | gimple_cond_lhs (use_stmt), | |
2791 | gimple_cond_rhs (use_stmt)); | |
2792 | else if (gimple_code (use_stmt) == GIMPLE_SWITCH) | |
2793 | val = gimple_switch_index (use_stmt); | |
d1d2af7d | 2794 | else |
75a70cf9 | 2795 | val = gimple_goto_dest (use_stmt); |
d1d2af7d | 2796 | |
75a70cf9 | 2797 | if (val && is_gimple_min_invariant (val)) |
d1d2af7d | 2798 | { |
75a70cf9 | 2799 | basic_block bb = gimple_bb (use_stmt); |
d1d2af7d | 2800 | edge te = find_taken_edge (bb, val); |
2801 | edge_iterator ei; | |
2802 | edge e; | |
75a70cf9 | 2803 | gimple_stmt_iterator gsi, psi; |
d1d2af7d | 2804 | |
2805 | /* Remove all outgoing edges except TE. */ | |
2806 | for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));) | |
2807 | { | |
2808 | if (e != te) | |
2809 | { | |
d1d2af7d | 2810 | /* Mark all the PHI nodes at the destination of |
2811 | the unexecutable edge as interesting. */ | |
75a70cf9 | 2812 | for (psi = gsi_start_phis (e->dest); |
2813 | !gsi_end_p (psi); | |
2814 | gsi_next (&psi)) | |
2815 | { | |
2816 | gimple phi = gsi_stmt (psi); | |
2817 | ||
2818 | tree result = gimple_phi_result (phi); | |
d1d2af7d | 2819 | int version = SSA_NAME_VERSION (result); |
2820 | ||
2821 | bitmap_set_bit (interesting_names, version); | |
2822 | } | |
2823 | ||
2824 | te->probability += e->probability; | |
2825 | ||
2826 | te->count += e->count; | |
2827 | remove_edge (e); | |
9a17dd7d | 2828 | cfg_altered = true; |
d1d2af7d | 2829 | } |
2830 | else | |
2831 | ei_next (&ei); | |
2832 | } | |
2833 | ||
75a70cf9 | 2834 | gsi = gsi_last_bb (gimple_bb (use_stmt)); |
2835 | gsi_remove (&gsi, true); | |
d1d2af7d | 2836 | |
2837 | /* And fixup the flags on the single remaining edge. */ | |
2838 | te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); | |
2839 | te->flags &= ~EDGE_ABNORMAL; | |
2840 | te->flags |= EDGE_FALLTHRU; | |
2841 | if (te->probability > REG_BR_PROB_BASE) | |
2842 | te->probability = REG_BR_PROB_BASE; | |
2843 | } | |
2844 | } | |
2845 | } | |
2846 | ||
48e1416a | 2847 | /* Ensure there is nothing else to do. */ |
76e6653a | 2848 | gcc_assert (!all || has_zero_uses (lhs)); |
ea54ad41 | 2849 | |
d1d2af7d | 2850 | /* If we were able to propagate away all uses of LHS, then |
2851 | we can remove STMT. */ | |
2852 | if (all) | |
2853 | remove_stmt_or_phi (stmt); | |
2854 | } | |
2855 | } | |
2856 | ||
75a70cf9 | 2857 | /* STMT is either a PHI node (potentially a degenerate PHI node) or |
d1d2af7d | 2858 | a statement that is a trivial copy or constant initialization. |
2859 | ||
2860 | Attempt to eliminate T by propagating its RHS into all uses of | |
2861 | its LHS. This may in turn set new bits in INTERESTING_NAMES | |
2862 | for nodes we want to revisit later. | |
2863 | ||
2864 | All exit paths should clear INTERESTING_NAMES for the result | |
75a70cf9 | 2865 | of STMT. */ |
d1d2af7d | 2866 | |
2867 | static void | |
75a70cf9 | 2868 | eliminate_const_or_copy (gimple stmt, bitmap interesting_names) |
d1d2af7d | 2869 | { |
75a70cf9 | 2870 | tree lhs = get_lhs_or_phi_result (stmt); |
d1d2af7d | 2871 | tree rhs; |
2872 | int version = SSA_NAME_VERSION (lhs); | |
2873 | ||
2874 | /* If the LHS of this statement or PHI has no uses, then we can | |
2875 | just eliminate it. This can occur if, for example, the PHI | |
2876 | was created by block duplication due to threading and its only | |
2877 | use was in the conditional at the end of the block which was | |
2878 | deleted. */ | |
2879 | if (has_zero_uses (lhs)) | |
2880 | { | |
2881 | bitmap_clear_bit (interesting_names, version); | |
75a70cf9 | 2882 | remove_stmt_or_phi (stmt); |
d1d2af7d | 2883 | return; |
2884 | } | |
2885 | ||
2886 | /* Get the RHS of the assignment or PHI node if the PHI is a | |
2887 | degenerate. */ | |
75a70cf9 | 2888 | rhs = get_rhs_or_phi_arg (stmt); |
d1d2af7d | 2889 | if (!rhs) |
2890 | { | |
2891 | bitmap_clear_bit (interesting_names, version); | |
2892 | return; | |
2893 | } | |
2894 | ||
75a70cf9 | 2895 | propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names); |
d1d2af7d | 2896 | |
75a70cf9 | 2897 | /* Note that STMT may well have been deleted by now, so do |
d1d2af7d | 2898 | not access it, instead use the saved version # to clear |
2899 | T's entry in the worklist. */ | |
2900 | bitmap_clear_bit (interesting_names, version); | |
2901 | } | |
2902 | ||
2903 | /* The first phase in degenerate PHI elimination. | |
2904 | ||
2905 | Eliminate the degenerate PHIs in BB, then recurse on the | |
2906 | dominator children of BB. */ | |
2907 | ||
2908 | static void | |
2909 | eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names) | |
2910 | { | |
75a70cf9 | 2911 | gimple_stmt_iterator gsi; |
d1d2af7d | 2912 | basic_block son; |
2913 | ||
75a70cf9 | 2914 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
d1d2af7d | 2915 | { |
75a70cf9 | 2916 | gimple phi = gsi_stmt (gsi); |
2917 | ||
d1d2af7d | 2918 | eliminate_const_or_copy (phi, interesting_names); |
2919 | } | |
2920 | ||
2921 | /* Recurse into the dominator children of BB. */ | |
2922 | for (son = first_dom_son (CDI_DOMINATORS, bb); | |
2923 | son; | |
2924 | son = next_dom_son (CDI_DOMINATORS, son)) | |
2925 | eliminate_degenerate_phis_1 (son, interesting_names); | |
2926 | } | |
2927 | ||
2928 | ||
2929 | /* A very simple pass to eliminate degenerate PHI nodes from the | |
2930 | IL. This is meant to be fast enough to be able to be run several | |
2931 | times in the optimization pipeline. | |
2932 | ||
2933 | Certain optimizations, particularly those which duplicate blocks | |
2934 | or remove edges from the CFG can create or expose PHIs which are | |
2935 | trivial copies or constant initializations. | |
2936 | ||
2937 | While we could pick up these optimizations in DOM or with the | |
2938 | combination of copy-prop and CCP, those solutions are far too | |
2939 | heavy-weight for our needs. | |
2940 | ||
2941 | This implementation has two phases so that we can efficiently | |
2942 | eliminate the first order degenerate PHIs and second order | |
2943 | degenerate PHIs. | |
2944 | ||
2945 | The first phase performs a dominator walk to identify and eliminate | |
2946 | the vast majority of the degenerate PHIs. When a degenerate PHI | |
2947 | is identified and eliminated any affected statements or PHIs | |
2948 | are put on a worklist. | |
2949 | ||
2950 | The second phase eliminates degenerate PHIs and trivial copies | |
2951 | or constant initializations using the worklist. This is how we | |
2952 | pick up the secondary optimization opportunities with minimal | |
2953 | cost. */ | |
2954 | ||
2955 | static unsigned int | |
2956 | eliminate_degenerate_phis (void) | |
2957 | { | |
2958 | bitmap interesting_names; | |
76af66a6 | 2959 | bitmap interesting_names1; |
d1d2af7d | 2960 | |
d65e4929 | 2961 | /* Bitmap of blocks which need EH information updated. We can not |
2962 | update it on-the-fly as doing so invalidates the dominator tree. */ | |
2963 | need_eh_cleanup = BITMAP_ALLOC (NULL); | |
2964 | ||
d1d2af7d | 2965 | /* INTERESTING_NAMES is effectively our worklist, indexed by |
2966 | SSA_NAME_VERSION. | |
2967 | ||
2968 | A set bit indicates that the statement or PHI node which | |
2969 | defines the SSA_NAME should be (re)examined to determine if | |
4562961a | 2970 | it has become a degenerate PHI or trivial const/copy propagation |
48e1416a | 2971 | opportunity. |
d1d2af7d | 2972 | |
2973 | Experiments have show we generally get better compilation | |
2974 | time behavior with bitmaps rather than sbitmaps. */ | |
2975 | interesting_names = BITMAP_ALLOC (NULL); | |
76af66a6 | 2976 | interesting_names1 = BITMAP_ALLOC (NULL); |
d1d2af7d | 2977 | |
9a17dd7d | 2978 | calculate_dominance_info (CDI_DOMINATORS); |
2979 | cfg_altered = false; | |
2980 | ||
9ca2c29a | 2981 | /* First phase. Eliminate degenerate PHIs via a dominator |
d1d2af7d | 2982 | walk of the CFG. |
2983 | ||
2984 | Experiments have indicated that we generally get better | |
2985 | compile-time behavior by visiting blocks in the first | |
2986 | phase in dominator order. Presumably this is because walking | |
2987 | in dominator order leaves fewer PHIs for later examination | |
2988 | by the worklist phase. */ | |
d1d2af7d | 2989 | eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names); |
2990 | ||
9ca2c29a | 2991 | /* Second phase. Eliminate second order degenerate PHIs as well |
d1d2af7d | 2992 | as trivial copies or constant initializations identified by |
2993 | the first phase or this phase. Basically we keep iterating | |
2994 | until our set of INTERESTING_NAMEs is empty. */ | |
2995 | while (!bitmap_empty_p (interesting_names)) | |
2996 | { | |
2997 | unsigned int i; | |
2998 | bitmap_iterator bi; | |
2999 | ||
76af66a6 | 3000 | /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap |
3001 | changed during the loop. Copy it to another bitmap and | |
3002 | use that. */ | |
3003 | bitmap_copy (interesting_names1, interesting_names); | |
3004 | ||
3005 | EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi) | |
d1d2af7d | 3006 | { |
3007 | tree name = ssa_name (i); | |
3008 | ||
3009 | /* Ignore SSA_NAMEs that have been released because | |
3010 | their defining statement was deleted (unreachable). */ | |
3011 | if (name) | |
3012 | eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)), | |
3013 | interesting_names); | |
3014 | } | |
3015 | } | |
d65e4929 | 3016 | |
9a17dd7d | 3017 | if (cfg_altered) |
3018 | free_dominance_info (CDI_DOMINATORS); | |
3019 | ||
d65e4929 | 3020 | /* Propagation of const and copies may make some EH edges dead. Purge |
3021 | such edges from the CFG as needed. */ | |
3022 | if (!bitmap_empty_p (need_eh_cleanup)) | |
3023 | { | |
75a70cf9 | 3024 | gimple_purge_all_dead_eh_edges (need_eh_cleanup); |
d65e4929 | 3025 | BITMAP_FREE (need_eh_cleanup); |
3026 | } | |
d1d2af7d | 3027 | |
3028 | BITMAP_FREE (interesting_names); | |
76af66a6 | 3029 | BITMAP_FREE (interesting_names1); |
d1d2af7d | 3030 | return 0; |
3031 | } | |
3032 | ||
20099e35 | 3033 | struct gimple_opt_pass pass_phi_only_cprop = |
d1d2af7d | 3034 | { |
20099e35 | 3035 | { |
3036 | GIMPLE_PASS, | |
d1d2af7d | 3037 | "phicprop", /* name */ |
3038 | gate_dominator, /* gate */ | |
3039 | eliminate_degenerate_phis, /* execute */ | |
3040 | NULL, /* sub */ | |
3041 | NULL, /* next */ | |
3042 | 0, /* static_pass_number */ | |
1ef27f86 | 3043 | TV_TREE_PHI_CPROP, /* tv_id */ |
2f8eb909 | 3044 | PROP_cfg | PROP_ssa, /* properties_required */ |
d1d2af7d | 3045 | 0, /* properties_provided */ |
b6246c40 | 3046 | 0, /* properties_destroyed */ |
d1d2af7d | 3047 | 0, /* todo_flags_start */ |
eb9161e7 | 3048 | TODO_cleanup_cfg |
eb9161e7 | 3049 | | TODO_ggc_collect |
3050 | | TODO_verify_ssa | |
3051 | | TODO_verify_stmts | |
20099e35 | 3052 | | TODO_update_ssa /* todo_flags_finish */ |
3053 | } | |
d1d2af7d | 3054 | }; |