]>
Commit | Line | Data |
---|---|---|
41511585 | 1 | /* Generic SSA value propagation engine. |
fbd26352 | 2 | Copyright (C) 2004-2019 Free Software Foundation, Inc. |
41511585 | 3 | Contributed by Diego Novillo <dnovillo@redhat.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it | |
8 | under the terms of the GNU General Public License as published by the | |
8c4c00c1 | 9 | Free Software Foundation; either version 3, or (at your option) any |
41511585 | 10 | later version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT | |
13 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
41511585 | 20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
9ef16211 | 24 | #include "backend.h" |
41511585 | 25 | #include "tree.h" |
9ef16211 | 26 | #include "gimple.h" |
9ef16211 | 27 | #include "ssa.h" |
7c29e30e | 28 | #include "gimple-pretty-print.h" |
b9ed1410 | 29 | #include "dumpfile.h" |
bc61cadb | 30 | #include "gimple-fold.h" |
31 | #include "tree-eh.h" | |
a8783bee | 32 | #include "gimplify.h" |
dcf1a1ec | 33 | #include "gimple-iterator.h" |
073c1fd5 | 34 | #include "tree-cfg.h" |
69ee5dbb | 35 | #include "tree-ssa.h" |
41511585 | 36 | #include "tree-ssa-propagate.h" |
39b62084 | 37 | #include "domwalk.h" |
bb80be62 | 38 | #include "cfgloop.h" |
25959a39 | 39 | #include "tree-cfgcleanup.h" |
08e33f10 | 40 | #include "cfganal.h" |
41511585 | 41 | |
42 | /* This file implements a generic value propagation engine based on | |
43 | the same propagation used by the SSA-CCP algorithm [1]. | |
44 | ||
45 | Propagation is performed by simulating the execution of every | |
46 | statement that produces the value being propagated. Simulation | |
47 | proceeds as follows: | |
48 | ||
49 | 1- Initially, all edges of the CFG are marked not executable and | |
7b4fe863 | 50 | the CFG worklist is seeded with all the statements in the entry |
41511585 | 51 | basic block (block 0). |
52 | ||
53 | 2- Every statement S is simulated with a call to the call-back | |
54 | function SSA_PROP_VISIT_STMT. This evaluation may produce 3 | |
55 | results: | |
56 | ||
57 | SSA_PROP_NOT_INTERESTING: Statement S produces nothing of | |
58 | interest and does not affect any of the work lists. | |
6517bc96 | 59 | The statement may be simulated again if any of its input |
60 | operands change in future iterations of the simulator. | |
41511585 | 61 | |
62 | SSA_PROP_VARYING: The value produced by S cannot be determined | |
63 | at compile time. Further simulation of S is not required. | |
64 | If S is a conditional jump, all the outgoing edges for the | |
65 | block are considered executable and added to the work | |
66 | list. | |
67 | ||
68 | SSA_PROP_INTERESTING: S produces a value that can be computed | |
69 | at compile time. Its result can be propagated into the | |
91275768 | 70 | statements that feed from S. Furthermore, if S is a |
41511585 | 71 | conditional jump, only the edge known to be taken is added |
72 | to the work list. Edges that are known not to execute are | |
73 | never simulated. | |
74 | ||
75 | 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The | |
76 | return value from SSA_PROP_VISIT_PHI has the same semantics as | |
7b4fe863 | 77 | described in #2. |
41511585 | 78 | |
79 | 4- Three work lists are kept. Statements are only added to these | |
80 | lists if they produce one of SSA_PROP_INTERESTING or | |
81 | SSA_PROP_VARYING. | |
82 | ||
83 | CFG_BLOCKS contains the list of blocks to be simulated. | |
84 | Blocks are added to this list if their incoming edges are | |
85 | found executable. | |
86 | ||
08e33f10 | 87 | SSA_EDGE_WORKLIST contains the list of statements that we |
88 | need to revisit. | |
41511585 | 89 | |
90 | 5- Simulation terminates when all three work lists are drained. | |
91 | ||
92 | Before calling ssa_propagate, it is important to clear | |
75a70cf9 | 93 | prop_simulate_again_p for all the statements in the program that |
41511585 | 94 | should be simulated. This initialization allows an implementation |
95 | to specify which statements should never be simulated. | |
96 | ||
97 | It is also important to compute def-use information before calling | |
98 | ssa_propagate. | |
99 | ||
100 | References: | |
101 | ||
102 | [1] Constant propagation with conditional branches, | |
103 | Wegman and Zadeck, ACM TOPLAS 13(2):181-210. | |
104 | ||
105 | [2] Building an Optimizing Compiler, | |
106 | Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. | |
107 | ||
108 | [3] Advanced Compiler Design and Implementation, | |
109 | Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */ | |
110 | ||
fa31eb45 | 111 | /* Worklists of control flow edge destinations. This contains |
08e33f10 | 112 | the CFG order number of the blocks so we can iterate in CFG |
fa31eb45 | 113 | order by visiting in bit-order. We use two worklists to |
114 | first make forward progress before iterating. */ | |
08e33f10 | 115 | static bitmap cfg_blocks; |
fa31eb45 | 116 | static bitmap cfg_blocks_back; |
08e33f10 | 117 | static int *bb_to_cfg_order; |
118 | static int *cfg_order_to_bb; | |
41511585 | 119 | |
fa31eb45 | 120 | /* Worklists of SSA edges which will need reexamination as their |
41511585 | 121 | definition has changed. SSA edges are def-use edges in the SSA |
122 | web. For each D-U edge, we store the target statement or PHI node | |
fa31eb45 | 123 | UID in a bitmap. UIDs order stmts in execution order. We use |
124 | two worklists to first make forward progress before iterating. */ | |
08e33f10 | 125 | static bitmap ssa_edge_worklist; |
fa31eb45 | 126 | static bitmap ssa_edge_worklist_back; |
08e33f10 | 127 | static vec<gimple *> uid_to_stmt; |
41511585 | 128 | |
fa31eb45 | 129 | /* Current RPO index in the iteration. */ |
130 | static int curr_order; | |
41511585 | 131 | |
132 | ||
133 | /* We have just defined a new value for VAR. If IS_VARYING is true, | |
134 | add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add | |
135 | them to INTERESTING_SSA_EDGES. */ | |
136 | ||
137 | static void | |
08e33f10 | 138 | add_ssa_edge (tree var) |
41511585 | 139 | { |
22aa74c4 | 140 | imm_use_iterator iter; |
141 | use_operand_p use_p; | |
41511585 | 142 | |
22aa74c4 | 143 | FOR_EACH_IMM_USE_FAST (use_p, iter, var) |
41511585 | 144 | { |
42acab1c | 145 | gimple *use_stmt = USE_STMT (use_p); |
c6e99972 | 146 | if (!prop_simulate_again_p (use_stmt)) |
147 | continue; | |
41511585 | 148 | |
08e33f10 | 149 | /* If we did not yet simulate the block wait for this to happen |
150 | and do not add the stmt to the SSA edge worklist. */ | |
c6e99972 | 151 | basic_block use_bb = gimple_bb (use_stmt); |
5c119eea | 152 | if (! (use_bb->flags & BB_VISITED)) |
153 | continue; | |
154 | ||
155 | /* If this is a use on a not yet executable edge do not bother to | |
156 | queue it. */ | |
157 | if (gimple_code (use_stmt) == GIMPLE_PHI | |
158 | && !(EDGE_PRED (use_bb, PHI_ARG_INDEX_FROM_USE (use_p))->flags | |
159 | & EDGE_EXECUTABLE)) | |
08e33f10 | 160 | continue; |
161 | ||
fa31eb45 | 162 | bitmap worklist; |
163 | if (bb_to_cfg_order[gimple_bb (use_stmt)->index] < curr_order) | |
164 | worklist = ssa_edge_worklist_back; | |
165 | else | |
166 | worklist = ssa_edge_worklist; | |
167 | if (bitmap_set_bit (worklist, gimple_uid (use_stmt))) | |
41511585 | 168 | { |
08e33f10 | 169 | uid_to_stmt[gimple_uid (use_stmt)] = use_stmt; |
170 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
8241864b | 171 | { |
08e33f10 | 172 | fprintf (dump_file, "ssa_edge_worklist: adding SSA use in "); |
173 | print_gimple_stmt (dump_file, use_stmt, 0, TDF_SLIM); | |
8241864b | 174 | } |
41511585 | 175 | } |
176 | } | |
177 | } | |
178 | ||
179 | ||
180 | /* Add edge E to the control flow worklist. */ | |
181 | ||
182 | static void | |
183 | add_control_edge (edge e) | |
184 | { | |
185 | basic_block bb = e->dest; | |
34154e27 | 186 | if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
41511585 | 187 | return; |
188 | ||
189 | /* If the edge had already been executed, skip it. */ | |
190 | if (e->flags & EDGE_EXECUTABLE) | |
191 | return; | |
192 | ||
193 | e->flags |= EDGE_EXECUTABLE; | |
194 | ||
fa31eb45 | 195 | int bb_order = bb_to_cfg_order[bb->index]; |
196 | if (bb_order < curr_order) | |
197 | bitmap_set_bit (cfg_blocks_back, bb_order); | |
198 | else | |
199 | bitmap_set_bit (cfg_blocks, bb_order); | |
41511585 | 200 | |
201 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
8241864b | 202 | fprintf (dump_file, "Adding destination of edge (%d -> %d) to worklist\n", |
41511585 | 203 | e->src->index, e->dest->index); |
204 | } | |
205 | ||
206 | ||
207 | /* Simulate the execution of STMT and update the work lists accordingly. */ | |
208 | ||
6bd87d95 | 209 | void |
210 | ssa_propagation_engine::simulate_stmt (gimple *stmt) | |
41511585 | 211 | { |
212 | enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING; | |
213 | edge taken_edge = NULL; | |
214 | tree output_name = NULL_TREE; | |
215 | ||
08e33f10 | 216 | /* Pull the stmt off the SSA edge worklist. */ |
217 | bitmap_clear_bit (ssa_edge_worklist, gimple_uid (stmt)); | |
218 | ||
41511585 | 219 | /* Don't bother visiting statements that are already |
220 | considered varying by the propagator. */ | |
75a70cf9 | 221 | if (!prop_simulate_again_p (stmt)) |
41511585 | 222 | return; |
223 | ||
75a70cf9 | 224 | if (gimple_code (stmt) == GIMPLE_PHI) |
41511585 | 225 | { |
6bd87d95 | 226 | val = visit_phi (as_a <gphi *> (stmt)); |
75a70cf9 | 227 | output_name = gimple_phi_result (stmt); |
41511585 | 228 | } |
229 | else | |
6bd87d95 | 230 | val = visit_stmt (stmt, &taken_edge, &output_name); |
41511585 | 231 | |
232 | if (val == SSA_PROP_VARYING) | |
233 | { | |
75a70cf9 | 234 | prop_set_simulate_again (stmt, false); |
41511585 | 235 | |
236 | /* If the statement produced a new varying value, add the SSA | |
237 | edges coming out of OUTPUT_NAME. */ | |
238 | if (output_name) | |
08e33f10 | 239 | add_ssa_edge (output_name); |
41511585 | 240 | |
241 | /* If STMT transfers control out of its basic block, add | |
242 | all outgoing edges to the work list. */ | |
243 | if (stmt_ends_bb_p (stmt)) | |
244 | { | |
245 | edge e; | |
cd665a06 | 246 | edge_iterator ei; |
75a70cf9 | 247 | basic_block bb = gimple_bb (stmt); |
cd665a06 | 248 | FOR_EACH_EDGE (e, ei, bb->succs) |
41511585 | 249 | add_control_edge (e); |
250 | } | |
a8a0d56e | 251 | return; |
41511585 | 252 | } |
253 | else if (val == SSA_PROP_INTERESTING) | |
254 | { | |
255 | /* If the statement produced new value, add the SSA edges coming | |
256 | out of OUTPUT_NAME. */ | |
257 | if (output_name) | |
08e33f10 | 258 | add_ssa_edge (output_name); |
41511585 | 259 | |
260 | /* If we know which edge is going to be taken out of this block, | |
261 | add it to the CFG work list. */ | |
262 | if (taken_edge) | |
263 | add_control_edge (taken_edge); | |
264 | } | |
a8a0d56e | 265 | |
266 | /* If there are no SSA uses on the stmt whose defs are simulated | |
267 | again then this stmt will be never visited again. */ | |
268 | bool has_simulate_again_uses = false; | |
269 | use_operand_p use_p; | |
270 | ssa_op_iter iter; | |
271 | if (gimple_code (stmt) == GIMPLE_PHI) | |
272 | { | |
273 | edge_iterator ei; | |
274 | edge e; | |
275 | tree arg; | |
276 | FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds) | |
277 | if (!(e->flags & EDGE_EXECUTABLE) | |
278 | || ((arg = PHI_ARG_DEF_FROM_EDGE (stmt, e)) | |
279 | && TREE_CODE (arg) == SSA_NAME | |
280 | && !SSA_NAME_IS_DEFAULT_DEF (arg) | |
281 | && prop_simulate_again_p (SSA_NAME_DEF_STMT (arg)))) | |
282 | { | |
283 | has_simulate_again_uses = true; | |
284 | break; | |
285 | } | |
286 | } | |
287 | else | |
288 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) | |
289 | { | |
42acab1c | 290 | gimple *def_stmt = SSA_NAME_DEF_STMT (USE_FROM_PTR (use_p)); |
a8a0d56e | 291 | if (!gimple_nop_p (def_stmt) |
292 | && prop_simulate_again_p (def_stmt)) | |
293 | { | |
294 | has_simulate_again_uses = true; | |
295 | break; | |
296 | } | |
297 | } | |
298 | if (!has_simulate_again_uses) | |
299 | { | |
300 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
301 | fprintf (dump_file, "marking stmt to be not simulated again\n"); | |
302 | prop_set_simulate_again (stmt, false); | |
303 | } | |
41511585 | 304 | } |
305 | ||
41511585 | 306 | |
307 | /* Simulate the execution of BLOCK. Evaluate the statement associated | |
308 | with each variable reference inside the block. */ | |
309 | ||
6bd87d95 | 310 | void |
311 | ssa_propagation_engine::simulate_block (basic_block block) | |
41511585 | 312 | { |
75a70cf9 | 313 | gimple_stmt_iterator gsi; |
41511585 | 314 | |
315 | /* There is nothing to do for the exit block. */ | |
34154e27 | 316 | if (block == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
41511585 | 317 | return; |
318 | ||
319 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
320 | fprintf (dump_file, "\nSimulating block %d\n", block->index); | |
321 | ||
322 | /* Always simulate PHI nodes, even if we have simulated this block | |
323 | before. */ | |
75a70cf9 | 324 | for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi)) |
325 | simulate_stmt (gsi_stmt (gsi)); | |
41511585 | 326 | |
327 | /* If this is the first time we've simulated this block, then we | |
328 | must simulate each of its statements. */ | |
08e33f10 | 329 | if (! (block->flags & BB_VISITED)) |
41511585 | 330 | { |
75a70cf9 | 331 | gimple_stmt_iterator j; |
41511585 | 332 | unsigned int normal_edge_count; |
333 | edge e, normal_edge; | |
cd665a06 | 334 | edge_iterator ei; |
41511585 | 335 | |
75a70cf9 | 336 | for (j = gsi_start_bb (block); !gsi_end_p (j); gsi_next (&j)) |
08e33f10 | 337 | simulate_stmt (gsi_stmt (j)); |
41511585 | 338 | |
08e33f10 | 339 | /* Note that we have simulated this block. */ |
340 | block->flags |= BB_VISITED; | |
41511585 | 341 | |
f4d3c071 | 342 | /* We cannot predict when abnormal and EH edges will be executed, so |
41511585 | 343 | once a block is considered executable, we consider any |
344 | outgoing abnormal edges as executable. | |
345 | ||
3d1eacdb | 346 | TODO: This is not exactly true. Simplifying statement might |
347 | prove it non-throwing and also computed goto can be handled | |
348 | when destination is known. | |
349 | ||
41511585 | 350 | At the same time, if this block has only one successor that is |
351 | reached by non-abnormal edges, then add that successor to the | |
352 | worklist. */ | |
353 | normal_edge_count = 0; | |
354 | normal_edge = NULL; | |
cd665a06 | 355 | FOR_EACH_EDGE (e, ei, block->succs) |
41511585 | 356 | { |
3d1eacdb | 357 | if (e->flags & (EDGE_ABNORMAL | EDGE_EH)) |
41511585 | 358 | add_control_edge (e); |
359 | else | |
360 | { | |
361 | normal_edge_count++; | |
362 | normal_edge = e; | |
363 | } | |
364 | } | |
365 | ||
366 | if (normal_edge_count == 1) | |
367 | add_control_edge (normal_edge); | |
368 | } | |
369 | } | |
370 | ||
371 | ||
372 | /* Initialize local data structures and work lists. */ | |
373 | ||
374 | static void | |
375 | ssa_prop_init (void) | |
376 | { | |
377 | edge e; | |
cd665a06 | 378 | edge_iterator ei; |
41511585 | 379 | basic_block bb; |
380 | ||
381 | /* Worklists of SSA edges. */ | |
08e33f10 | 382 | ssa_edge_worklist = BITMAP_ALLOC (NULL); |
fa31eb45 | 383 | ssa_edge_worklist_back = BITMAP_ALLOC (NULL); |
e35f850e | 384 | bitmap_tree_view (ssa_edge_worklist); |
385 | bitmap_tree_view (ssa_edge_worklist_back); | |
41511585 | 386 | |
08e33f10 | 387 | /* Worklist of basic-blocks. */ |
388 | bb_to_cfg_order = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1); | |
389 | cfg_order_to_bb = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); | |
b50ad04e | 390 | int n = pre_and_rev_post_order_compute_fn (cfun, NULL, |
391 | cfg_order_to_bb, false); | |
08e33f10 | 392 | for (int i = 0; i < n; ++i) |
393 | bb_to_cfg_order[cfg_order_to_bb[i]] = i; | |
394 | cfg_blocks = BITMAP_ALLOC (NULL); | |
fa31eb45 | 395 | cfg_blocks_back = BITMAP_ALLOC (NULL); |
41511585 | 396 | |
88dbf20f | 397 | /* Initially assume that every edge in the CFG is not executable. |
08e33f10 | 398 | (including the edges coming out of the entry block). Mark blocks |
399 | as not visited, blocks not yet visited will have all their statements | |
400 | simulated once an incoming edge gets executable. */ | |
401 | set_gimple_stmt_max_uid (cfun, 0); | |
402 | for (int i = 0; i < n; ++i) | |
41511585 | 403 | { |
75a70cf9 | 404 | gimple_stmt_iterator si; |
08e33f10 | 405 | bb = BASIC_BLOCK_FOR_FN (cfun, cfg_order_to_bb[i]); |
48e1416a | 406 | |
75a70cf9 | 407 | for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) |
08e33f10 | 408 | { |
409 | gimple *stmt = gsi_stmt (si); | |
410 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
411 | } | |
41511585 | 412 | |
08e33f10 | 413 | for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) |
414 | { | |
415 | gimple *stmt = gsi_stmt (si); | |
416 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
417 | } | |
418 | ||
b50ad04e | 419 | bb->flags &= ~BB_VISITED; |
cd665a06 | 420 | FOR_EACH_EDGE (e, ei, bb->succs) |
41511585 | 421 | e->flags &= ~EDGE_EXECUTABLE; |
422 | } | |
08e33f10 | 423 | uid_to_stmt.safe_grow (gimple_stmt_max_uid (cfun)); |
41511585 | 424 | |
425 | /* Seed the algorithm by adding the successors of the entry block to the | |
426 | edge worklist. */ | |
34154e27 | 427 | FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) |
08e33f10 | 428 | { |
429 | e->flags &= ~EDGE_EXECUTABLE; | |
430 | add_control_edge (e); | |
431 | } | |
41511585 | 432 | } |
433 | ||
434 | ||
435 | /* Free allocated storage. */ | |
436 | ||
437 | static void | |
438 | ssa_prop_fini (void) | |
439 | { | |
08e33f10 | 440 | BITMAP_FREE (cfg_blocks); |
fa31eb45 | 441 | BITMAP_FREE (cfg_blocks_back); |
08e33f10 | 442 | free (bb_to_cfg_order); |
443 | free (cfg_order_to_bb); | |
444 | BITMAP_FREE (ssa_edge_worklist); | |
fa31eb45 | 445 | BITMAP_FREE (ssa_edge_worklist_back); |
08e33f10 | 446 | uid_to_stmt.release (); |
41511585 | 447 | } |
448 | ||
449 | ||
75a70cf9 | 450 | /* Return true if EXPR is an acceptable right-hand-side for a |
451 | GIMPLE assignment. We validate the entire tree, not just | |
452 | the root node, thus catching expressions that embed complex | |
453 | operands that are not permitted in GIMPLE. This function | |
454 | is needed because the folding routines in fold-const.c | |
455 | may return such expressions in some cases, e.g., an array | |
456 | access with an embedded index addition. It may make more | |
457 | sense to have folding routines that are sensitive to the | |
458 | constraints on GIMPLE operands, rather than abandoning any | |
459 | any attempt to fold if the usual folding turns out to be too | |
460 | aggressive. */ | |
41511585 | 461 | |
462 | bool | |
75a70cf9 | 463 | valid_gimple_rhs_p (tree expr) |
41511585 | 464 | { |
41511585 | 465 | enum tree_code code = TREE_CODE (expr); |
41511585 | 466 | |
f2532264 | 467 | switch (TREE_CODE_CLASS (code)) |
41511585 | 468 | { |
f2532264 | 469 | case tcc_declaration: |
1c6d350b | 470 | if (!is_gimple_variable (expr)) |
f2532264 | 471 | return false; |
472 | break; | |
473 | ||
474 | case tcc_constant: | |
75a70cf9 | 475 | /* All constants are ok. */ |
f2532264 | 476 | break; |
477 | ||
f2532264 | 478 | case tcc_comparison: |
bd5e1815 | 479 | /* GENERIC allows comparisons with non-boolean types, reject |
480 | those for GIMPLE. Let vector-typed comparisons pass - rules | |
481 | for GENERIC and GIMPLE are the same here. */ | |
482 | if (!(INTEGRAL_TYPE_P (TREE_TYPE (expr)) | |
483 | && (TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE | |
484 | || TYPE_PRECISION (TREE_TYPE (expr)) == 1)) | |
485 | && ! VECTOR_TYPE_P (TREE_TYPE (expr))) | |
f540a052 | 486 | return false; |
487 | ||
488 | /* Fallthru. */ | |
489 | case tcc_binary: | |
41511585 | 490 | if (!is_gimple_val (TREE_OPERAND (expr, 0)) |
491 | || !is_gimple_val (TREE_OPERAND (expr, 1))) | |
492 | return false; | |
f2532264 | 493 | break; |
494 | ||
495 | case tcc_unary: | |
41511585 | 496 | if (!is_gimple_val (TREE_OPERAND (expr, 0))) |
497 | return false; | |
f2532264 | 498 | break; |
499 | ||
500 | case tcc_expression: | |
501 | switch (code) | |
75a70cf9 | 502 | { |
503 | case ADDR_EXPR: | |
504 | { | |
505 | tree t; | |
506 | if (is_gimple_min_invariant (expr)) | |
507 | return true; | |
508 | t = TREE_OPERAND (expr, 0); | |
509 | while (handled_component_p (t)) | |
510 | { | |
511 | /* ??? More checks needed, see the GIMPLE verifier. */ | |
512 | if ((TREE_CODE (t) == ARRAY_REF | |
513 | || TREE_CODE (t) == ARRAY_RANGE_REF) | |
514 | && !is_gimple_val (TREE_OPERAND (t, 1))) | |
515 | return false; | |
516 | t = TREE_OPERAND (t, 0); | |
517 | } | |
518 | if (!is_gimple_id (t)) | |
519 | return false; | |
520 | } | |
521 | break; | |
f2532264 | 522 | |
f2532264 | 523 | default: |
00161311 | 524 | if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS) |
525 | { | |
526 | if (((code == VEC_COND_EXPR || code == COND_EXPR) | |
527 | ? !is_gimple_condexpr (TREE_OPERAND (expr, 0)) | |
528 | : !is_gimple_val (TREE_OPERAND (expr, 0))) | |
529 | || !is_gimple_val (TREE_OPERAND (expr, 1)) | |
530 | || !is_gimple_val (TREE_OPERAND (expr, 2))) | |
531 | return false; | |
532 | break; | |
533 | } | |
f2532264 | 534 | return false; |
535 | } | |
536 | break; | |
537 | ||
f43a1a60 | 538 | case tcc_vl_exp: |
75a70cf9 | 539 | return false; |
f43a1a60 | 540 | |
f2532264 | 541 | case tcc_exceptional: |
be7b52a2 | 542 | if (code == CONSTRUCTOR) |
543 | { | |
544 | unsigned i; | |
545 | tree elt; | |
546 | FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (expr), i, elt) | |
547 | if (!is_gimple_val (elt)) | |
548 | return false; | |
549 | return true; | |
550 | } | |
75a70cf9 | 551 | if (code != SSA_NAME) |
552 | return false; | |
f2532264 | 553 | break; |
554 | ||
be7b52a2 | 555 | case tcc_reference: |
556 | if (code == BIT_FIELD_REF) | |
557 | return is_gimple_val (TREE_OPERAND (expr, 0)); | |
558 | return false; | |
559 | ||
f2532264 | 560 | default: |
561 | return false; | |
41511585 | 562 | } |
563 | ||
1c6d350b | 564 | return true; |
565 | } | |
566 | ||
567 | ||
75a70cf9 | 568 | /* Return true if EXPR is a CALL_EXPR suitable for representation |
569 | as a single GIMPLE_CALL statement. If the arguments require | |
570 | further gimplification, return false. */ | |
1c6d350b | 571 | |
251e7603 | 572 | static bool |
75a70cf9 | 573 | valid_gimple_call_p (tree expr) |
1c6d350b | 574 | { |
75a70cf9 | 575 | unsigned i, nargs; |
1c6d350b | 576 | |
75a70cf9 | 577 | if (TREE_CODE (expr) != CALL_EXPR) |
1c6d350b | 578 | return false; |
579 | ||
75a70cf9 | 580 | nargs = call_expr_nargs (expr); |
581 | for (i = 0; i < nargs; i++) | |
251e7603 | 582 | { |
583 | tree arg = CALL_EXPR_ARG (expr, i); | |
b7b667b4 | 584 | if (is_gimple_reg_type (TREE_TYPE (arg))) |
251e7603 | 585 | { |
586 | if (!is_gimple_val (arg)) | |
587 | return false; | |
588 | } | |
589 | else | |
590 | if (!is_gimple_lvalue (arg)) | |
591 | return false; | |
592 | } | |
5a7c6119 | 593 | |
75a70cf9 | 594 | return true; |
595 | } | |
41511585 | 596 | |
41511585 | 597 | |
75a70cf9 | 598 | /* Make SSA names defined by OLD_STMT point to NEW_STMT |
599 | as their defining statement. */ | |
41511585 | 600 | |
75a70cf9 | 601 | void |
42acab1c | 602 | move_ssa_defining_stmt_for_defs (gimple *new_stmt, gimple *old_stmt) |
75a70cf9 | 603 | { |
604 | tree var; | |
605 | ssa_op_iter iter; | |
41511585 | 606 | |
75a70cf9 | 607 | if (gimple_in_ssa_p (cfun)) |
608 | { | |
609 | /* Make defined SSA_NAMEs point to the new | |
610 | statement as their definition. */ | |
611 | FOR_EACH_SSA_TREE_OPERAND (var, old_stmt, iter, SSA_OP_ALL_DEFS) | |
612 | { | |
613 | if (TREE_CODE (var) == SSA_NAME) | |
614 | SSA_NAME_DEF_STMT (var) = new_stmt; | |
615 | } | |
41511585 | 616 | } |
75a70cf9 | 617 | } |
41511585 | 618 | |
be7317e9 | 619 | /* Helper function for update_gimple_call and update_call_from_tree. |
620 | A GIMPLE_CALL STMT is being replaced with GIMPLE_CALL NEW_STMT. */ | |
621 | ||
622 | static void | |
42acab1c | 623 | finish_update_gimple_call (gimple_stmt_iterator *si_p, gimple *new_stmt, |
624 | gimple *stmt) | |
be7317e9 | 625 | { |
626 | gimple_call_set_lhs (new_stmt, gimple_call_lhs (stmt)); | |
627 | move_ssa_defining_stmt_for_defs (new_stmt, stmt); | |
1263a9e1 | 628 | gimple_move_vops (new_stmt, stmt); |
be7317e9 | 629 | gimple_set_location (new_stmt, gimple_location (stmt)); |
630 | if (gimple_block (new_stmt) == NULL_TREE) | |
631 | gimple_set_block (new_stmt, gimple_block (stmt)); | |
632 | gsi_replace (si_p, new_stmt, false); | |
633 | } | |
634 | ||
635 | /* Update a GIMPLE_CALL statement at iterator *SI_P to call to FN | |
636 | with number of arguments NARGS, where the arguments in GIMPLE form | |
637 | follow NARGS argument. */ | |
638 | ||
639 | bool | |
640 | update_gimple_call (gimple_stmt_iterator *si_p, tree fn, int nargs, ...) | |
641 | { | |
642 | va_list ap; | |
1a91d914 | 643 | gcall *new_stmt, *stmt = as_a <gcall *> (gsi_stmt (*si_p)); |
be7317e9 | 644 | |
645 | gcc_assert (is_gimple_call (stmt)); | |
646 | va_start (ap, nargs); | |
647 | new_stmt = gimple_build_call_valist (fn, nargs, ap); | |
648 | finish_update_gimple_call (si_p, new_stmt, stmt); | |
649 | va_end (ap); | |
650 | return true; | |
651 | } | |
75a70cf9 | 652 | |
653 | /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the | |
654 | value of EXPR, which is expected to be the result of folding the | |
655 | call. This can only be done if EXPR is a CALL_EXPR with valid | |
656 | GIMPLE operands as arguments, or if it is a suitable RHS expression | |
657 | for a GIMPLE_ASSIGN. More complex expressions will require | |
9d75589a | 658 | gimplification, which will introduce additional statements. In this |
75a70cf9 | 659 | event, no update is performed, and the function returns false. |
660 | Note that we cannot mutate a GIMPLE_CALL in-place, so we always | |
661 | replace the statement at *SI_P with an entirely new statement. | |
662 | The new statement need not be a call, e.g., if the original call | |
663 | folded to a constant. */ | |
664 | ||
665 | bool | |
666 | update_call_from_tree (gimple_stmt_iterator *si_p, tree expr) | |
667 | { | |
42acab1c | 668 | gimple *stmt = gsi_stmt (*si_p); |
75a70cf9 | 669 | |
75a70cf9 | 670 | if (valid_gimple_call_p (expr)) |
671 | { | |
672 | /* The call has simplified to another call. */ | |
673 | tree fn = CALL_EXPR_FN (expr); | |
674 | unsigned i; | |
675 | unsigned nargs = call_expr_nargs (expr); | |
1e094109 | 676 | vec<tree> args = vNULL; |
1a91d914 | 677 | gcall *new_stmt; |
75a70cf9 | 678 | |
679 | if (nargs > 0) | |
680 | { | |
f1f41a6c | 681 | args.create (nargs); |
682 | args.safe_grow_cleared (nargs); | |
48e1416a | 683 | |
75a70cf9 | 684 | for (i = 0; i < nargs; i++) |
f1f41a6c | 685 | args[i] = CALL_EXPR_ARG (expr, i); |
75a70cf9 | 686 | } |
687 | ||
688 | new_stmt = gimple_build_call_vec (fn, args); | |
be7317e9 | 689 | finish_update_gimple_call (si_p, new_stmt, stmt); |
f1f41a6c | 690 | args.release (); |
75a70cf9 | 691 | |
692 | return true; | |
693 | } | |
694 | else if (valid_gimple_rhs_p (expr)) | |
695 | { | |
be7317e9 | 696 | tree lhs = gimple_call_lhs (stmt); |
42acab1c | 697 | gimple *new_stmt; |
75a70cf9 | 698 | |
699 | /* The call has simplified to an expression | |
700 | that cannot be represented as a GIMPLE_CALL. */ | |
701 | if (lhs) | |
702 | { | |
703 | /* A value is expected. | |
704 | Introduce a new GIMPLE_ASSIGN statement. */ | |
705 | STRIP_USELESS_TYPE_CONVERSION (expr); | |
706 | new_stmt = gimple_build_assign (lhs, expr); | |
75a70cf9 | 707 | move_ssa_defining_stmt_for_defs (new_stmt, stmt); |
1263a9e1 | 708 | gimple_move_vops (new_stmt, stmt); |
75a70cf9 | 709 | } |
710 | else if (!TREE_SIDE_EFFECTS (expr)) | |
711 | { | |
712 | /* No value is expected, and EXPR has no effect. | |
713 | Replace it with an empty statement. */ | |
714 | new_stmt = gimple_build_nop (); | |
fa30068d | 715 | if (gimple_in_ssa_p (cfun)) |
716 | { | |
717 | unlink_stmt_vdef (stmt); | |
718 | release_defs (stmt); | |
719 | } | |
75a70cf9 | 720 | } |
721 | else | |
722 | { | |
723 | /* No value is expected, but EXPR has an effect, | |
724 | e.g., it could be a reference to a volatile | |
725 | variable. Create an assignment statement | |
726 | with a dummy (unused) lhs variable. */ | |
727 | STRIP_USELESS_TYPE_CONVERSION (expr); | |
fa30068d | 728 | if (gimple_in_ssa_p (cfun)) |
f9e245b2 | 729 | lhs = make_ssa_name (TREE_TYPE (expr)); |
03d37e4e | 730 | else |
f9e245b2 | 731 | lhs = create_tmp_var (TREE_TYPE (expr)); |
03d37e4e | 732 | new_stmt = gimple_build_assign (lhs, expr); |
1263a9e1 | 733 | gimple_move_vops (new_stmt, stmt); |
75a70cf9 | 734 | move_ssa_defining_stmt_for_defs (new_stmt, stmt); |
735 | } | |
736 | gimple_set_location (new_stmt, gimple_location (stmt)); | |
737 | gsi_replace (si_p, new_stmt, false); | |
738 | return true; | |
739 | } | |
740 | else | |
741 | /* The call simplified to an expression that is | |
742 | not a valid GIMPLE RHS. */ | |
743 | return false; | |
41511585 | 744 | } |
745 | ||
41511585 | 746 | /* Entry point to the propagation engine. |
747 | ||
6bd87d95 | 748 | The VISIT_STMT virtual function is called for every statement |
749 | visited and the VISIT_PHI virtual function is called for every PHI | |
750 | node visited. */ | |
41511585 | 751 | |
752 | void | |
6bd87d95 | 753 | ssa_propagation_engine::ssa_propagate (void) |
41511585 | 754 | { |
41511585 | 755 | ssa_prop_init (); |
756 | ||
fa31eb45 | 757 | curr_order = 0; |
758 | ||
759 | /* Iterate until the worklists are empty. We iterate both blocks | |
760 | and stmts in RPO order, using sets of two worklists to first | |
761 | complete the current iteration before iterating over backedges. */ | |
762 | while (1) | |
41511585 | 763 | { |
fa31eb45 | 764 | int next_block_order = (bitmap_empty_p (cfg_blocks) |
765 | ? -1 : bitmap_first_set_bit (cfg_blocks)); | |
766 | int next_stmt_uid = (bitmap_empty_p (ssa_edge_worklist) | |
767 | ? -1 : bitmap_first_set_bit (ssa_edge_worklist)); | |
768 | if (next_block_order == -1 && next_stmt_uid == -1) | |
41511585 | 769 | { |
fa31eb45 | 770 | if (bitmap_empty_p (cfg_blocks_back) |
771 | && bitmap_empty_p (ssa_edge_worklist_back)) | |
772 | break; | |
773 | ||
774 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
775 | fprintf (dump_file, "Regular worklists empty, now processing " | |
776 | "backedge destinations\n"); | |
777 | std::swap (cfg_blocks, cfg_blocks_back); | |
778 | std::swap (ssa_edge_worklist, ssa_edge_worklist_back); | |
8241864b | 779 | continue; |
41511585 | 780 | } |
781 | ||
fa31eb45 | 782 | int next_stmt_bb_order = -1; |
783 | gimple *next_stmt = NULL; | |
784 | if (next_stmt_uid != -1) | |
785 | { | |
786 | next_stmt = uid_to_stmt[next_stmt_uid]; | |
787 | next_stmt_bb_order = bb_to_cfg_order[gimple_bb (next_stmt)->index]; | |
788 | } | |
789 | ||
790 | /* Pull the next block to simulate off the worklist if it comes first. */ | |
791 | if (next_block_order != -1 | |
792 | && (next_stmt_bb_order == -1 | |
793 | || next_block_order <= next_stmt_bb_order)) | |
794 | { | |
795 | curr_order = next_block_order; | |
796 | bitmap_clear_bit (cfg_blocks, next_block_order); | |
797 | basic_block bb | |
798 | = BASIC_BLOCK_FOR_FN (cfun, cfg_order_to_bb [next_block_order]); | |
799 | simulate_block (bb); | |
800 | } | |
801 | /* Else simulate from the SSA edge worklist. */ | |
802 | else | |
803 | { | |
804 | curr_order = next_stmt_bb_order; | |
fa31eb45 | 805 | if (dump_file && (dump_flags & TDF_DETAILS)) |
806 | { | |
807 | fprintf (dump_file, "\nSimulating statement: "); | |
808 | print_gimple_stmt (dump_file, next_stmt, 0, dump_flags); | |
809 | } | |
810 | simulate_stmt (next_stmt); | |
811 | } | |
41511585 | 812 | } |
813 | ||
814 | ssa_prop_fini (); | |
815 | } | |
816 | ||
88dbf20f | 817 | |
88dbf20f | 818 | /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref' |
819 | is a non-volatile pointer dereference, a structure reference or a | |
820 | reference to a single _DECL. Ignore volatile memory references | |
821 | because they are not interesting for the optimizers. */ | |
822 | ||
823 | bool | |
42acab1c | 824 | stmt_makes_single_store (gimple *stmt) |
88dbf20f | 825 | { |
826 | tree lhs; | |
827 | ||
75a70cf9 | 828 | if (gimple_code (stmt) != GIMPLE_ASSIGN |
829 | && gimple_code (stmt) != GIMPLE_CALL) | |
88dbf20f | 830 | return false; |
831 | ||
dd277d48 | 832 | if (!gimple_vdef (stmt)) |
88dbf20f | 833 | return false; |
834 | ||
75a70cf9 | 835 | lhs = gimple_get_lhs (stmt); |
836 | ||
837 | /* A call statement may have a null LHS. */ | |
838 | if (!lhs) | |
839 | return false; | |
88dbf20f | 840 | |
841 | return (!TREE_THIS_VOLATILE (lhs) | |
842 | && (DECL_P (lhs) | |
a640bb21 | 843 | || REFERENCE_CLASS_P (lhs))); |
88dbf20f | 844 | } |
845 | ||
846 | ||
88dbf20f | 847 | /* Propagation statistics. */ |
848 | struct prop_stats_d | |
849 | { | |
850 | long num_const_prop; | |
851 | long num_copy_prop; | |
07aee51b | 852 | long num_stmts_folded; |
9659d177 | 853 | long num_dce; |
88dbf20f | 854 | }; |
855 | ||
856 | static struct prop_stats_d prop_stats; | |
857 | ||
858 | /* Replace USE references in statement STMT with the values stored in | |
75a70cf9 | 859 | PROP_VALUE. Return true if at least one reference was replaced. */ |
88dbf20f | 860 | |
6e93da1b | 861 | bool |
b08e7364 | 862 | substitute_and_fold_engine::replace_uses_in (gimple *stmt) |
88dbf20f | 863 | { |
864 | bool replaced = false; | |
865 | use_operand_p use; | |
866 | ssa_op_iter iter; | |
867 | ||
868 | FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE) | |
869 | { | |
870 | tree tuse = USE_FROM_PTR (use); | |
b08e7364 | 871 | tree val = get_value (tuse); |
88dbf20f | 872 | |
873 | if (val == tuse || val == NULL_TREE) | |
874 | continue; | |
875 | ||
75a70cf9 | 876 | if (gimple_code (stmt) == GIMPLE_ASM |
88dbf20f | 877 | && !may_propagate_copy_into_asm (tuse)) |
878 | continue; | |
879 | ||
880 | if (!may_propagate_copy (tuse, val)) | |
881 | continue; | |
882 | ||
883 | if (TREE_CODE (val) != SSA_NAME) | |
884 | prop_stats.num_const_prop++; | |
885 | else | |
886 | prop_stats.num_copy_prop++; | |
887 | ||
888 | propagate_value (use, val); | |
889 | ||
890 | replaced = true; | |
88dbf20f | 891 | } |
892 | ||
893 | return replaced; | |
894 | } | |
895 | ||
896 | ||
88dbf20f | 897 | /* Replace propagated values into all the arguments for PHI using the |
898 | values from PROP_VALUE. */ | |
899 | ||
b08e7364 | 900 | bool |
901 | substitute_and_fold_engine::replace_phi_args_in (gphi *phi) | |
88dbf20f | 902 | { |
75a70cf9 | 903 | size_t i; |
eea12c72 | 904 | bool replaced = false; |
eea12c72 | 905 | |
906 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
75a70cf9 | 907 | { |
908 | fprintf (dump_file, "Folding PHI node: "); | |
909 | print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); | |
910 | } | |
88dbf20f | 911 | |
75a70cf9 | 912 | for (i = 0; i < gimple_phi_num_args (phi); i++) |
88dbf20f | 913 | { |
75a70cf9 | 914 | tree arg = gimple_phi_arg_def (phi, i); |
88dbf20f | 915 | |
916 | if (TREE_CODE (arg) == SSA_NAME) | |
917 | { | |
b08e7364 | 918 | tree val = get_value (arg); |
88dbf20f | 919 | |
920 | if (val && val != arg && may_propagate_copy (arg, val)) | |
921 | { | |
bb80be62 | 922 | edge e = gimple_phi_arg_edge (phi, i); |
923 | ||
88dbf20f | 924 | if (TREE_CODE (val) != SSA_NAME) |
925 | prop_stats.num_const_prop++; | |
926 | else | |
927 | prop_stats.num_copy_prop++; | |
928 | ||
929 | propagate_value (PHI_ARG_DEF_PTR (phi, i), val); | |
eea12c72 | 930 | replaced = true; |
88dbf20f | 931 | |
932 | /* If we propagated a copy and this argument flows | |
933 | through an abnormal edge, update the replacement | |
934 | accordingly. */ | |
935 | if (TREE_CODE (val) == SSA_NAME | |
bb80be62 | 936 | && e->flags & EDGE_ABNORMAL |
937 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val)) | |
938 | { | |
939 | /* This can only occur for virtual operands, since | |
940 | for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val)) | |
941 | would prevent replacement. */ | |
942 | gcc_checking_assert (virtual_operand_p (val)); | |
943 | SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1; | |
944 | } | |
88dbf20f | 945 | } |
946 | } | |
947 | } | |
48e1416a | 948 | |
75a70cf9 | 949 | if (dump_file && (dump_flags & TDF_DETAILS)) |
eea12c72 | 950 | { |
75a70cf9 | 951 | if (!replaced) |
952 | fprintf (dump_file, "No folding possible\n"); | |
953 | else | |
954 | { | |
955 | fprintf (dump_file, "Folded into: "); | |
956 | print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); | |
957 | fprintf (dump_file, "\n"); | |
958 | } | |
eea12c72 | 959 | } |
28e7c0f5 | 960 | |
961 | return replaced; | |
eea12c72 | 962 | } |
963 | ||
964 | ||
39b62084 | 965 | class substitute_and_fold_dom_walker : public dom_walker |
88dbf20f | 966 | { |
39b62084 | 967 | public: |
968 | substitute_and_fold_dom_walker (cdi_direction direction, | |
b08e7364 | 969 | class substitute_and_fold_engine *engine) |
970 | : dom_walker (direction), | |
971 | something_changed (false), | |
972 | substitute_and_fold_engine (engine) | |
39b62084 | 973 | { |
974 | stmts_to_remove.create (0); | |
25959a39 | 975 | stmts_to_fixup.create (0); |
42691e36 | 976 | need_eh_cleanup = BITMAP_ALLOC (NULL); |
977 | } | |
978 | ~substitute_and_fold_dom_walker () | |
979 | { | |
980 | stmts_to_remove.release (); | |
25959a39 | 981 | stmts_to_fixup.release (); |
42691e36 | 982 | BITMAP_FREE (need_eh_cleanup); |
39b62084 | 983 | } |
88dbf20f | 984 | |
96752458 | 985 | virtual edge before_dom_children (basic_block); |
39b62084 | 986 | virtual void after_dom_children (basic_block) {} |
eea12c72 | 987 | |
39b62084 | 988 | bool something_changed; |
42acab1c | 989 | vec<gimple *> stmts_to_remove; |
990 | vec<gimple *> stmts_to_fixup; | |
42691e36 | 991 | bitmap need_eh_cleanup; |
b08e7364 | 992 | |
993 | class substitute_and_fold_engine *substitute_and_fold_engine; | |
39b62084 | 994 | }; |
88dbf20f | 995 | |
96752458 | 996 | edge |
39b62084 | 997 | substitute_and_fold_dom_walker::before_dom_children (basic_block bb) |
998 | { | |
39b62084 | 999 | /* Propagate known values into PHI nodes. */ |
1a91d914 | 1000 | for (gphi_iterator i = gsi_start_phis (bb); |
1001 | !gsi_end_p (i); | |
1002 | gsi_next (&i)) | |
39b62084 | 1003 | { |
1a91d914 | 1004 | gphi *phi = i.phi (); |
39b62084 | 1005 | tree res = gimple_phi_result (phi); |
1006 | if (virtual_operand_p (res)) | |
1007 | continue; | |
723c387e | 1008 | if (res && TREE_CODE (res) == SSA_NAME) |
39b62084 | 1009 | { |
b08e7364 | 1010 | tree sprime = substitute_and_fold_engine->get_value (res); |
39b62084 | 1011 | if (sprime |
1012 | && sprime != res | |
1013 | && may_propagate_copy (res, sprime)) | |
1014 | { | |
1015 | stmts_to_remove.safe_push (phi); | |
3064bb7b | 1016 | continue; |
39b62084 | 1017 | } |
1018 | } | |
b08e7364 | 1019 | something_changed |= substitute_and_fold_engine->replace_phi_args_in (phi); |
39b62084 | 1020 | } |
1021 | ||
1022 | /* Propagate known values into stmts. In some case it exposes | |
1023 | more trivially deletable stmts to walk backward. */ | |
1a91d914 | 1024 | for (gimple_stmt_iterator i = gsi_start_bb (bb); |
1025 | !gsi_end_p (i); | |
1026 | gsi_next (&i)) | |
88dbf20f | 1027 | { |
39b62084 | 1028 | bool did_replace; |
42acab1c | 1029 | gimple *stmt = gsi_stmt (i); |
88dbf20f | 1030 | |
39b62084 | 1031 | /* No point propagating into a stmt we have a value for we |
1032 | can propagate into all uses. Mark it for removal instead. */ | |
1033 | tree lhs = gimple_get_lhs (stmt); | |
723c387e | 1034 | if (lhs && TREE_CODE (lhs) == SSA_NAME) |
88dbf20f | 1035 | { |
b08e7364 | 1036 | tree sprime = substitute_and_fold_engine->get_value (lhs); |
39b62084 | 1037 | if (sprime |
1038 | && sprime != lhs | |
1039 | && may_propagate_copy (lhs, sprime) | |
aac19106 | 1040 | && !stmt_could_throw_p (cfun, stmt) |
98e16200 | 1041 | && !gimple_has_side_effects (stmt) |
1042 | /* We have to leave ASSERT_EXPRs around for jump-threading. */ | |
1043 | && (!is_gimple_assign (stmt) | |
1044 | || gimple_assign_rhs_code (stmt) != ASSERT_EXPR)) | |
fc50275a | 1045 | { |
39b62084 | 1046 | stmts_to_remove.safe_push (stmt); |
fc50275a | 1047 | continue; |
1048 | } | |
39b62084 | 1049 | } |
1050 | ||
1051 | /* Replace the statement with its folded version and mark it | |
1052 | folded. */ | |
1053 | did_replace = false; | |
1054 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1055 | { | |
1056 | fprintf (dump_file, "Folding statement: "); | |
1057 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1058 | } | |
1059 | ||
42acab1c | 1060 | gimple *old_stmt = stmt; |
25959a39 | 1061 | bool was_noreturn = (is_gimple_call (stmt) |
1062 | && gimple_call_noreturn_p (stmt)); | |
39b62084 | 1063 | |
39b62084 | 1064 | /* Replace real uses in the statement. */ |
b08e7364 | 1065 | did_replace |= substitute_and_fold_engine->replace_uses_in (stmt); |
39b62084 | 1066 | |
1067 | /* If we made a replacement, fold the statement. */ | |
1068 | if (did_replace) | |
93049066 | 1069 | { |
1070 | fold_stmt (&i, follow_single_use_edges); | |
1071 | stmt = gsi_stmt (i); | |
1941149a | 1072 | gimple_set_modified (stmt, true); |
1073 | } | |
1074 | ||
1075 | /* Some statements may be simplified using propagator | |
1076 | specific information. Do this before propagating | |
1077 | into the stmt to not disturb pass specific information. */ | |
b08e7364 | 1078 | update_stmt_if_modified (stmt); |
1079 | if (substitute_and_fold_engine->fold_stmt(&i)) | |
1941149a | 1080 | { |
b08e7364 | 1081 | did_replace = true; |
1082 | prop_stats.num_stmts_folded++; | |
1083 | stmt = gsi_stmt (i); | |
1084 | gimple_set_modified (stmt, true); | |
93049066 | 1085 | } |
1086 | ||
1087 | /* If this is a control statement the propagator left edges | |
1088 | unexecuted on force the condition in a way consistent with | |
1089 | that. See PR66945 for cases where the propagator can end | |
1090 | up with a different idea of a taken edge than folding | |
1091 | (once undefined behavior is involved). */ | |
1092 | if (gimple_code (stmt) == GIMPLE_COND) | |
1093 | { | |
1094 | if ((EDGE_SUCC (bb, 0)->flags & EDGE_EXECUTABLE) | |
1095 | ^ (EDGE_SUCC (bb, 1)->flags & EDGE_EXECUTABLE)) | |
1096 | { | |
1097 | if (((EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE) != 0) | |
1098 | == ((EDGE_SUCC (bb, 0)->flags & EDGE_EXECUTABLE) != 0)) | |
1099 | gimple_cond_make_true (as_a <gcond *> (stmt)); | |
1100 | else | |
1101 | gimple_cond_make_false (as_a <gcond *> (stmt)); | |
1941149a | 1102 | gimple_set_modified (stmt, true); |
93049066 | 1103 | did_replace = true; |
1104 | } | |
1105 | } | |
eea12c72 | 1106 | |
39b62084 | 1107 | /* Now cleanup. */ |
1108 | if (did_replace) | |
1109 | { | |
39b62084 | 1110 | /* If we cleaned up EH information from the statement, |
1111 | remove EH edges. */ | |
1112 | if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) | |
42691e36 | 1113 | bitmap_set_bit (need_eh_cleanup, bb->index); |
39b62084 | 1114 | |
25959a39 | 1115 | /* If we turned a not noreturn call into a noreturn one |
1116 | schedule it for fixup. */ | |
1117 | if (!was_noreturn | |
1118 | && is_gimple_call (stmt) | |
1119 | && gimple_call_noreturn_p (stmt)) | |
1120 | stmts_to_fixup.safe_push (stmt); | |
1121 | ||
1fa87479 | 1122 | if (gimple_assign_single_p (stmt)) |
75a70cf9 | 1123 | { |
39b62084 | 1124 | tree rhs = gimple_assign_rhs1 (stmt); |
1125 | ||
1126 | if (TREE_CODE (rhs) == ADDR_EXPR) | |
1127 | recompute_tree_invariant_for_addr_expr (rhs); | |
75a70cf9 | 1128 | } |
eea12c72 | 1129 | |
39b62084 | 1130 | /* Determine what needs to be done to update the SSA form. */ |
1941149a | 1131 | update_stmt_if_modified (stmt); |
39b62084 | 1132 | if (!is_gimple_debug (stmt)) |
1133 | something_changed = true; | |
1134 | } | |
07aee51b | 1135 | |
39b62084 | 1136 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1137 | { | |
1138 | if (did_replace) | |
75a70cf9 | 1139 | { |
39b62084 | 1140 | fprintf (dump_file, "Folded into: "); |
1141 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1142 | fprintf (dump_file, "\n"); | |
75a70cf9 | 1143 | } |
39b62084 | 1144 | else |
1145 | fprintf (dump_file, "Not folded\n"); | |
1146 | } | |
1147 | } | |
96752458 | 1148 | return NULL; |
39b62084 | 1149 | } |
eea12c72 | 1150 | |
88dbf20f | 1151 | |
e31161b3 | 1152 | |
39b62084 | 1153 | /* Perform final substitution and folding of propagated values. |
9435b515 | 1154 | Process the whole function if BLOCK is null, otherwise only |
1155 | process the blocks that BLOCK dominates. In the latter case, | |
1156 | it is the caller's responsibility to ensure that dominator | |
1157 | information is available and up-to-date. | |
88dbf20f | 1158 | |
39b62084 | 1159 | PROP_VALUE[I] contains the single value that should be substituted |
1160 | at every use of SSA name N_I. If PROP_VALUE is NULL, no values are | |
1161 | substituted. | |
75a70cf9 | 1162 | |
39b62084 | 1163 | If FOLD_FN is non-NULL the function will be invoked on all statements |
1164 | before propagating values for pass specific simplification. | |
48e1416a | 1165 | |
39b62084 | 1166 | DO_DCE is true if trivially dead stmts can be removed. |
de6ed584 | 1167 | |
39b62084 | 1168 | If DO_DCE is true, the statements within a BB are walked from |
1169 | last to first element. Otherwise we scan from first to last element. | |
75a70cf9 | 1170 | |
39b62084 | 1171 | Return TRUE when something changed. */ |
1172 | ||
1173 | bool | |
9435b515 | 1174 | substitute_and_fold_engine::substitute_and_fold (basic_block block) |
39b62084 | 1175 | { |
39b62084 | 1176 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1177 | fprintf (dump_file, "\nSubstituting values and folding statements\n\n"); | |
1178 | ||
1179 | memset (&prop_stats, 0, sizeof (prop_stats)); | |
1180 | ||
9435b515 | 1181 | /* Don't call calculate_dominance_info when iterating over a subgraph. |
1182 | Callers that are using the interface this way are likely to want to | |
1183 | iterate over several disjoint subgraphs, and it would be expensive | |
1184 | in enable-checking builds to revalidate the whole dominance tree | |
1185 | each time. */ | |
1186 | if (block) | |
1187 | gcc_assert (dom_info_state (CDI_DOMINATORS)); | |
1188 | else | |
1189 | calculate_dominance_info (CDI_DOMINATORS); | |
b08e7364 | 1190 | substitute_and_fold_dom_walker walker (CDI_DOMINATORS, this); |
9435b515 | 1191 | walker.walk (block ? block : ENTRY_BLOCK_PTR_FOR_FN (cfun)); |
39b62084 | 1192 | |
1193 | /* We cannot remove stmts during the BB walk, especially not release | |
1194 | SSA names there as that destroys the lattice of our callers. | |
1195 | Remove stmts in reverse order to make debug stmt creation possible. */ | |
1196 | while (!walker.stmts_to_remove.is_empty ()) | |
1197 | { | |
42acab1c | 1198 | gimple *stmt = walker.stmts_to_remove.pop (); |
39b62084 | 1199 | if (dump_file && dump_flags & TDF_DETAILS) |
1200 | { | |
1201 | fprintf (dump_file, "Removing dead stmt "); | |
1ffa4346 | 1202 | print_gimple_stmt (dump_file, stmt, 0); |
39b62084 | 1203 | fprintf (dump_file, "\n"); |
1204 | } | |
1205 | prop_stats.num_dce++; | |
1206 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
1207 | if (gimple_code (stmt) == GIMPLE_PHI) | |
1208 | remove_phi_node (&gsi, true); | |
1209 | else | |
1210 | { | |
1211 | unlink_stmt_vdef (stmt); | |
1212 | gsi_remove (&gsi, true); | |
1213 | release_defs (stmt); | |
88dbf20f | 1214 | } |
1215 | } | |
1216 | ||
42691e36 | 1217 | if (!bitmap_empty_p (walker.need_eh_cleanup)) |
1218 | gimple_purge_all_dead_eh_edges (walker.need_eh_cleanup); | |
1219 | ||
25959a39 | 1220 | /* Fixup stmts that became noreturn calls. This may require splitting |
1221 | blocks and thus isn't possible during the dominator walk. Do this | |
1222 | in reverse order so we don't inadvertedly remove a stmt we want to | |
1223 | fixup by visiting a dominating now noreturn call first. */ | |
1224 | while (!walker.stmts_to_fixup.is_empty ()) | |
1225 | { | |
42acab1c | 1226 | gimple *stmt = walker.stmts_to_fixup.pop (); |
25959a39 | 1227 | if (dump_file && dump_flags & TDF_DETAILS) |
1228 | { | |
1229 | fprintf (dump_file, "Fixing up noreturn call "); | |
1ffa4346 | 1230 | print_gimple_stmt (dump_file, stmt, 0); |
25959a39 | 1231 | fprintf (dump_file, "\n"); |
1232 | } | |
1233 | fixup_noreturn_call (stmt); | |
1234 | } | |
1235 | ||
9659d177 | 1236 | statistics_counter_event (cfun, "Constants propagated", |
1237 | prop_stats.num_const_prop); | |
1238 | statistics_counter_event (cfun, "Copies propagated", | |
1239 | prop_stats.num_copy_prop); | |
07aee51b | 1240 | statistics_counter_event (cfun, "Statements folded", |
1241 | prop_stats.num_stmts_folded); | |
9659d177 | 1242 | statistics_counter_event (cfun, "Statements deleted", |
1243 | prop_stats.num_dce); | |
39b62084 | 1244 | |
1245 | return walker.something_changed; | |
88dbf20f | 1246 | } |
eea12c72 | 1247 | |
0f4161b1 | 1248 | |
1249 | /* Return true if we may propagate ORIG into DEST, false otherwise. */ | |
1250 | ||
1251 | bool | |
1252 | may_propagate_copy (tree dest, tree orig) | |
1253 | { | |
1254 | tree type_d = TREE_TYPE (dest); | |
1255 | tree type_o = TREE_TYPE (orig); | |
1256 | ||
26ca2f08 | 1257 | /* If ORIG is a default definition which flows in from an abnormal edge |
1258 | then the copy can be propagated. It is important that we do so to avoid | |
1259 | uninitialized copies. */ | |
0f4161b1 | 1260 | if (TREE_CODE (orig) == SSA_NAME |
1261 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig) | |
26ca2f08 | 1262 | && SSA_NAME_IS_DEFAULT_DEF (orig) |
1263 | && (SSA_NAME_VAR (orig) == NULL_TREE | |
1264 | || TREE_CODE (SSA_NAME_VAR (orig)) == VAR_DECL)) | |
1265 | ; | |
1266 | /* Otherwise if ORIG just flows in from an abnormal edge then the copy cannot | |
1267 | be propagated. */ | |
1268 | else if (TREE_CODE (orig) == SSA_NAME | |
1269 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)) | |
0f4161b1 | 1270 | return false; |
26ca2f08 | 1271 | /* Similarly if DEST flows in from an abnormal edge then the copy cannot be |
1272 | propagated. */ | |
1273 | else if (TREE_CODE (dest) == SSA_NAME | |
1274 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest)) | |
0f4161b1 | 1275 | return false; |
1276 | ||
1277 | /* Do not copy between types for which we *do* need a conversion. */ | |
1278 | if (!useless_type_conversion_p (type_d, type_o)) | |
1279 | return false; | |
1280 | ||
1281 | /* Generally propagating virtual operands is not ok as that may | |
1282 | create overlapping life-ranges. */ | |
1283 | if (TREE_CODE (dest) == SSA_NAME && virtual_operand_p (dest)) | |
1284 | return false; | |
1285 | ||
1286 | /* Anything else is OK. */ | |
1287 | return true; | |
1288 | } | |
1289 | ||
1290 | /* Like may_propagate_copy, but use as the destination expression | |
1291 | the principal expression (typically, the RHS) contained in | |
1292 | statement DEST. This is more efficient when working with the | |
1293 | gimple tuples representation. */ | |
1294 | ||
1295 | bool | |
42acab1c | 1296 | may_propagate_copy_into_stmt (gimple *dest, tree orig) |
0f4161b1 | 1297 | { |
1298 | tree type_d; | |
1299 | tree type_o; | |
1300 | ||
1301 | /* If the statement is a switch or a single-rhs assignment, | |
1302 | then the expression to be replaced by the propagation may | |
1303 | be an SSA_NAME. Fortunately, there is an explicit tree | |
1304 | for the expression, so we delegate to may_propagate_copy. */ | |
1305 | ||
1306 | if (gimple_assign_single_p (dest)) | |
1307 | return may_propagate_copy (gimple_assign_rhs1 (dest), orig); | |
1a91d914 | 1308 | else if (gswitch *dest_swtch = dyn_cast <gswitch *> (dest)) |
1309 | return may_propagate_copy (gimple_switch_index (dest_swtch), orig); | |
0f4161b1 | 1310 | |
1311 | /* In other cases, the expression is not materialized, so there | |
1312 | is no destination to pass to may_propagate_copy. On the other | |
1313 | hand, the expression cannot be an SSA_NAME, so the analysis | |
1314 | is much simpler. */ | |
1315 | ||
1316 | if (TREE_CODE (orig) == SSA_NAME | |
1317 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)) | |
1318 | return false; | |
1319 | ||
1320 | if (is_gimple_assign (dest)) | |
1321 | type_d = TREE_TYPE (gimple_assign_lhs (dest)); | |
1322 | else if (gimple_code (dest) == GIMPLE_COND) | |
1323 | type_d = boolean_type_node; | |
1324 | else if (is_gimple_call (dest) | |
1325 | && gimple_call_lhs (dest) != NULL_TREE) | |
1326 | type_d = TREE_TYPE (gimple_call_lhs (dest)); | |
1327 | else | |
1328 | gcc_unreachable (); | |
1329 | ||
1330 | type_o = TREE_TYPE (orig); | |
1331 | ||
1332 | if (!useless_type_conversion_p (type_d, type_o)) | |
1333 | return false; | |
1334 | ||
1335 | return true; | |
1336 | } | |
1337 | ||
1338 | /* Similarly, but we know that we're propagating into an ASM_EXPR. */ | |
1339 | ||
1340 | bool | |
1341 | may_propagate_copy_into_asm (tree dest ATTRIBUTE_UNUSED) | |
1342 | { | |
1343 | return true; | |
1344 | } | |
1345 | ||
1346 | ||
1347 | /* Common code for propagate_value and replace_exp. | |
1348 | ||
1349 | Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the | |
1350 | replacement is done to propagate a value or not. */ | |
1351 | ||
1352 | static void | |
1353 | replace_exp_1 (use_operand_p op_p, tree val, | |
1354 | bool for_propagation ATTRIBUTE_UNUSED) | |
1355 | { | |
382ecba7 | 1356 | if (flag_checking) |
1357 | { | |
1358 | tree op = USE_FROM_PTR (op_p); | |
1359 | gcc_assert (!(for_propagation | |
1360 | && TREE_CODE (op) == SSA_NAME | |
1361 | && TREE_CODE (val) == SSA_NAME | |
1362 | && !may_propagate_copy (op, val))); | |
1363 | } | |
0f4161b1 | 1364 | |
1365 | if (TREE_CODE (val) == SSA_NAME) | |
1366 | SET_USE (op_p, val); | |
1367 | else | |
1368 | SET_USE (op_p, unshare_expr (val)); | |
1369 | } | |
1370 | ||
1371 | ||
1372 | /* Propagate the value VAL (assumed to be a constant or another SSA_NAME) | |
1373 | into the operand pointed to by OP_P. | |
1374 | ||
1375 | Use this version for const/copy propagation as it will perform additional | |
1376 | checks to ensure validity of the const/copy propagation. */ | |
1377 | ||
1378 | void | |
1379 | propagate_value (use_operand_p op_p, tree val) | |
1380 | { | |
1381 | replace_exp_1 (op_p, val, true); | |
1382 | } | |
1383 | ||
1384 | /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME). | |
1385 | ||
1386 | Use this version when not const/copy propagating values. For example, | |
1387 | PRE uses this version when building expressions as they would appear | |
1388 | in specific blocks taking into account actions of PHI nodes. | |
1389 | ||
1390 | The statement in which an expression has been replaced should be | |
1391 | folded using fold_stmt_inplace. */ | |
1392 | ||
1393 | void | |
1394 | replace_exp (use_operand_p op_p, tree val) | |
1395 | { | |
1396 | replace_exp_1 (op_p, val, false); | |
1397 | } | |
1398 | ||
1399 | ||
1400 | /* Propagate the value VAL (assumed to be a constant or another SSA_NAME) | |
1401 | into the tree pointed to by OP_P. | |
1402 | ||
1403 | Use this version for const/copy propagation when SSA operands are not | |
1404 | available. It will perform the additional checks to ensure validity of | |
1405 | the const/copy propagation, but will not update any operand information. | |
1406 | Be sure to mark the stmt as modified. */ | |
1407 | ||
1408 | void | |
1409 | propagate_tree_value (tree *op_p, tree val) | |
1410 | { | |
0f4161b1 | 1411 | if (TREE_CODE (val) == SSA_NAME) |
1412 | *op_p = val; | |
1413 | else | |
1414 | *op_p = unshare_expr (val); | |
1415 | } | |
1416 | ||
1417 | ||
1418 | /* Like propagate_tree_value, but use as the operand to replace | |
1419 | the principal expression (typically, the RHS) contained in the | |
1420 | statement referenced by iterator GSI. Note that it is not | |
1421 | always possible to update the statement in-place, so a new | |
1422 | statement may be created to replace the original. */ | |
1423 | ||
1424 | void | |
1425 | propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val) | |
1426 | { | |
42acab1c | 1427 | gimple *stmt = gsi_stmt (*gsi); |
0f4161b1 | 1428 | |
1429 | if (is_gimple_assign (stmt)) | |
1430 | { | |
1431 | tree expr = NULL_TREE; | |
1432 | if (gimple_assign_single_p (stmt)) | |
1433 | expr = gimple_assign_rhs1 (stmt); | |
1434 | propagate_tree_value (&expr, val); | |
1435 | gimple_assign_set_rhs_from_tree (gsi, expr); | |
1436 | } | |
1a91d914 | 1437 | else if (gcond *cond_stmt = dyn_cast <gcond *> (stmt)) |
0f4161b1 | 1438 | { |
1439 | tree lhs = NULL_TREE; | |
1440 | tree rhs = build_zero_cst (TREE_TYPE (val)); | |
1441 | propagate_tree_value (&lhs, val); | |
1a91d914 | 1442 | gimple_cond_set_code (cond_stmt, NE_EXPR); |
1443 | gimple_cond_set_lhs (cond_stmt, lhs); | |
1444 | gimple_cond_set_rhs (cond_stmt, rhs); | |
0f4161b1 | 1445 | } |
1446 | else if (is_gimple_call (stmt) | |
1447 | && gimple_call_lhs (stmt) != NULL_TREE) | |
1448 | { | |
1449 | tree expr = NULL_TREE; | |
1450 | bool res; | |
1451 | propagate_tree_value (&expr, val); | |
1452 | res = update_call_from_tree (gsi, expr); | |
1453 | gcc_assert (res); | |
1454 | } | |
1a91d914 | 1455 | else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) |
1456 | propagate_tree_value (gimple_switch_index_ptr (swtch_stmt), val); | |
0f4161b1 | 1457 | else |
1458 | gcc_unreachable (); | |
1459 | } |