1 | /* Convert a program in SSA form into Normal form. |
2 | Copyright (C) 2004-2023 Free Software Foundation, Inc. |
3 | Contributed by Andrew Macleod <amacleod@redhat.com> |
4 | |
5 | This file is part of GCC. |
6 | |
7 | GCC is free software; you can redistribute it and/or modify |
8 | it under the terms of the GNU General Public License as published by |
9 | the Free Software Foundation; either version 3, or (at your option) |
10 | any later version. |
11 | |
12 | GCC is distributed in the hope that it will be useful, |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
15 | GNU General Public License for more details. |
16 | |
17 | You should have received a copy of the GNU General Public License |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ |
20 | |
21 | #include "config.h" |
22 | #include "system.h" |
23 | #include "coretypes.h" |
24 | #include "backend.h" |
25 | #include "rtl.h" |
26 | #include "tree.h" |
27 | #include "gimple.h" |
28 | #include "cfghooks.h" |
29 | #include "ssa.h" |
30 | #include "tree-ssa.h" |
31 | #include "memmodel.h" |
32 | #include "emit-rtl.h" |
33 | #include "gimple-pretty-print.h" |
34 | #include "diagnostic-core.h" |
35 | #include "tree-dfa.h" |
36 | #include "stor-layout.h" |
37 | #include "cfgrtl.h" |
38 | #include "cfganal.h" |
39 | #include "tree-eh.h" |
40 | #include "gimple-iterator.h" |
41 | #include "tree-cfg.h" |
42 | #include "dumpfile.h" |
43 | #include "tree-ssa-live.h" |
44 | #include "tree-ssa-ter.h" |
45 | #include "tree-ssa-coalesce.h" |
46 | #include "tree-outof-ssa.h" |
47 | #include "dojump.h" |
48 | |
49 | /* FIXME: A lot of code here deals with expanding to RTL. All that code |
50 | should be in cfgexpand.cc. */ |
51 | #include "explow.h" |
52 | #include "expr.h" |
53 | |
54 | /* Return TRUE if expression STMT is suitable for replacement. */ |
55 | |
56 | bool |
57 | ssa_is_replaceable_p (gimple *stmt) |
58 | { |
59 | use_operand_p use_p; |
60 | tree def; |
61 | gimple *use_stmt; |
62 | |
63 | /* Only consider modify stmts. */ |
64 | if (!is_gimple_assign (gs: stmt)) |
65 | return false; |
66 | |
67 | /* If the statement may throw an exception, it cannot be replaced. */ |
68 | if (stmt_could_throw_p (cfun, stmt)) |
69 | return false; |
70 | |
71 | /* Punt if there is more than 1 def. */ |
72 | def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); |
73 | if (!def) |
74 | return false; |
75 | |
76 | /* Only consider definitions which have a single use. */ |
77 | if (!single_imm_use (var: def, use_p: &use_p, stmt: &use_stmt)) |
78 | return false; |
79 | |
80 | /* Used in this block, but at the TOP of the block, not the end. */ |
81 | if (gimple_code (g: use_stmt) == GIMPLE_PHI) |
82 | return false; |
83 | |
84 | /* There must be no VDEFs. */ |
85 | if (gimple_vdef (g: stmt)) |
86 | return false; |
87 | |
88 | /* Float expressions must go through memory if float-store is on. */ |
89 | if (flag_float_store |
90 | && FLOAT_TYPE_P (TREE_TYPE (def))) |
91 | return false; |
92 | |
93 | /* An assignment with a register variable on the RHS is not |
94 | replaceable. */ |
95 | if (gimple_assign_rhs_code (gs: stmt) == VAR_DECL |
96 | && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt))) |
97 | return false; |
98 | |
99 | /* No function calls can be replaced. */ |
100 | if (is_gimple_call (gs: stmt)) |
101 | return false; |
102 | |
103 | /* Leave any stmt with volatile operands alone as well. */ |
104 | if (gimple_has_volatile_ops (stmt)) |
105 | return false; |
106 | |
107 | return true; |
108 | } |
109 | |
110 | |
111 | /* Used to hold all the components required to do SSA PHI elimination. |
112 | The node and pred/succ list is a simple linear list of nodes and |
113 | edges represented as pairs of nodes. |
114 | |
115 | The predecessor and successor list: Nodes are entered in pairs, where |
116 | [0] ->PRED, [1]->SUCC. All the even indexes in the array represent |
117 | predecessors, all the odd elements are successors. |
118 | |
119 | Rationale: |
120 | When implemented as bitmaps, very large programs SSA->Normal times were |
121 | being dominated by clearing the interference graph. |
122 | |
123 | Typically this list of edges is extremely small since it only includes |
124 | PHI results and uses from a single edge which have not coalesced with |
125 | each other. This means that no virtual PHI nodes are included, and |
126 | empirical evidence suggests that the number of edges rarely exceed |
127 | 3, and in a bootstrap of GCC, the maximum size encountered was 7. |
128 | This also limits the number of possible nodes that are involved to |
129 | rarely more than 6, and in the bootstrap of gcc, the maximum number |
130 | of nodes encountered was 12. */ |
131 | |
132 | class elim_graph |
133 | { |
134 | public: |
135 | elim_graph (var_map map); |
136 | |
137 | /* Size of the elimination vectors. */ |
138 | int size; |
139 | |
140 | /* List of nodes in the elimination graph. */ |
141 | auto_vec<int> nodes; |
142 | |
143 | /* The predecessor and successor edge list. */ |
144 | auto_vec<int> edge_list; |
145 | |
146 | /* Source locus on each edge */ |
147 | auto_vec<location_t> edge_locus; |
148 | |
149 | /* Visited vector. */ |
150 | auto_sbitmap visited; |
151 | |
152 | /* Stack for visited nodes. */ |
153 | auto_vec<int> stack; |
154 | |
155 | /* The variable partition map. */ |
156 | var_map map; |
157 | |
158 | /* Edge being eliminated by this graph. */ |
159 | edge e; |
160 | |
161 | /* List of constant copies to emit. These are pushed on in pairs. */ |
162 | auto_vec<int> const_dests; |
163 | auto_vec<tree> const_copies; |
164 | |
165 | /* Source locations for any constant copies. */ |
166 | auto_vec<location_t> copy_locus; |
167 | }; |
168 | |
169 | |
170 | /* For an edge E find out a good source location to associate with |
171 | instructions inserted on edge E. If E has an implicit goto set, |
172 | use its location. Otherwise search instructions in predecessors |
173 | of E for a location, and use that one. That makes sense because |
174 | we insert on edges for PHI nodes, and effects of PHIs happen on |
175 | the end of the predecessor conceptually. An exception is made |
176 | for EH edges because we don't want to drag the source location |
177 | of unrelated statements at the beginning of handlers; they would |
178 | be further reused for various EH constructs, which would damage |
179 | the coverage information. */ |
180 | |
181 | static void |
182 | set_location_for_edge (edge e) |
183 | { |
184 | if (e->goto_locus) |
185 | set_curr_insn_location (e->goto_locus); |
186 | else if (e->flags & EDGE_EH) |
187 | { |
188 | basic_block bb = e->dest; |
189 | gimple_stmt_iterator gsi; |
190 | |
191 | do |
192 | { |
193 | for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
194 | { |
195 | gimple *stmt = gsi_stmt (i: gsi); |
196 | if (is_gimple_debug (gs: stmt)) |
197 | continue; |
198 | if (gimple_has_location (g: stmt) || gimple_block (g: stmt)) |
199 | { |
200 | set_curr_insn_location (gimple_location (g: stmt)); |
201 | return; |
202 | } |
203 | } |
204 | /* Nothing found in this basic block. Make a half-assed attempt |
205 | to continue with another block. */ |
206 | if (single_succ_p (bb)) |
207 | bb = single_succ (bb); |
208 | else |
209 | bb = e->dest; |
210 | } |
211 | while (bb != e->dest); |
212 | } |
213 | else |
214 | { |
215 | basic_block bb = e->src; |
216 | gimple_stmt_iterator gsi; |
217 | |
218 | do |
219 | { |
220 | for (gsi = gsi_last_bb (bb); !gsi_end_p (i: gsi); gsi_prev (i: &gsi)) |
221 | { |
222 | gimple *stmt = gsi_stmt (i: gsi); |
223 | if (is_gimple_debug (gs: stmt)) |
224 | continue; |
225 | if (gimple_has_location (g: stmt) || gimple_block (g: stmt)) |
226 | { |
227 | set_curr_insn_location (gimple_location (g: stmt)); |
228 | return; |
229 | } |
230 | } |
231 | /* Nothing found in this basic block. Make a half-assed attempt |
232 | to continue with another block. */ |
233 | if (single_pred_p (bb)) |
234 | bb = single_pred (bb); |
235 | else |
236 | bb = e->src; |
237 | } |
238 | while (bb != e->src); |
239 | } |
240 | } |
241 | |
242 | /* Emit insns to copy SRC into DEST converting SRC if necessary. As |
243 | SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from |
244 | which we deduce the size to copy in that case. */ |
245 | |
246 | static inline rtx_insn * |
247 | emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp) |
248 | { |
249 | start_sequence (); |
250 | |
251 | if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest)) |
252 | src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp); |
253 | if (GET_MODE (src) == BLKmode) |
254 | { |
255 | gcc_assert (GET_MODE (dest) == BLKmode); |
256 | emit_block_move (dest, src, expr_size (sizeexp), BLOCK_OP_NORMAL); |
257 | } |
258 | else |
259 | emit_move_insn (dest, src); |
260 | do_pending_stack_adjust (); |
261 | |
262 | rtx_insn *seq = get_insns (); |
263 | end_sequence (); |
264 | |
265 | return seq; |
266 | } |
267 | |
268 | /* Insert a copy instruction from partition SRC to DEST onto edge E. */ |
269 | |
270 | static void |
271 | insert_partition_copy_on_edge (edge e, int dest, int src, location_t locus) |
272 | { |
273 | tree var; |
274 | if (dump_file && (dump_flags & TDF_DETAILS)) |
275 | { |
276 | fprintf (stream: dump_file, |
277 | format: "Inserting a partition copy on edge BB%d->BB%d : " |
278 | "PART.%d = PART.%d" , |
279 | e->src->index, |
280 | e->dest->index, dest, src); |
281 | fprintf (stream: dump_file, format: "\n" ); |
282 | } |
283 | |
284 | gcc_assert (SA.partition_to_pseudo[dest]); |
285 | gcc_assert (SA.partition_to_pseudo[src]); |
286 | |
287 | set_location_for_edge (e); |
288 | /* If a locus is provided, override the default. */ |
289 | if (locus) |
290 | set_curr_insn_location (locus); |
291 | |
292 | var = partition_to_var (map: SA.map, i: src); |
293 | rtx_insn *seq = emit_partition_copy (dest: copy_rtx (SA.partition_to_pseudo[dest]), |
294 | src: copy_rtx (SA.partition_to_pseudo[src]), |
295 | TYPE_UNSIGNED (TREE_TYPE (var)), |
296 | sizeexp: var); |
297 | |
298 | insert_insn_on_edge (seq, e); |
299 | } |
300 | |
301 | /* Insert a copy instruction from expression SRC to partition DEST |
302 | onto edge E. */ |
303 | |
304 | static void |
305 | insert_value_copy_on_edge (edge e, int dest, tree src, location_t locus) |
306 | { |
307 | rtx dest_rtx, seq, x; |
308 | machine_mode dest_mode, src_mode; |
309 | int unsignedp; |
310 | |
311 | if (dump_file && (dump_flags & TDF_DETAILS)) |
312 | { |
313 | fprintf (stream: dump_file, |
314 | format: "Inserting a value copy on edge BB%d->BB%d : PART.%d = " , |
315 | e->src->index, |
316 | e->dest->index, dest); |
317 | print_generic_expr (dump_file, src, TDF_SLIM); |
318 | fprintf (stream: dump_file, format: "\n" ); |
319 | } |
320 | |
321 | dest_rtx = copy_rtx (SA.partition_to_pseudo[dest]); |
322 | gcc_assert (dest_rtx); |
323 | |
324 | set_location_for_edge (e); |
325 | /* If a locus is provided, override the default. */ |
326 | if (locus) |
327 | set_curr_insn_location (locus); |
328 | |
329 | start_sequence (); |
330 | |
331 | tree name = partition_to_var (map: SA.map, i: dest); |
332 | src_mode = TYPE_MODE (TREE_TYPE (src)); |
333 | dest_mode = GET_MODE (dest_rtx); |
334 | gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (name))); |
335 | gcc_assert (!REG_P (dest_rtx) |
336 | || dest_mode == promote_ssa_mode (name, &unsignedp)); |
337 | |
338 | if (src_mode != dest_mode) |
339 | { |
340 | x = expand_expr (exp: src, NULL, mode: src_mode, modifier: EXPAND_NORMAL); |
341 | x = convert_modes (mode: dest_mode, oldmode: src_mode, x, unsignedp); |
342 | } |
343 | else if (src_mode == BLKmode) |
344 | { |
345 | x = dest_rtx; |
346 | store_expr (src, x, 0, false, false); |
347 | } |
348 | else |
349 | x = expand_expr (exp: src, target: dest_rtx, mode: dest_mode, modifier: EXPAND_NORMAL); |
350 | |
351 | if (x != dest_rtx) |
352 | emit_move_insn (dest_rtx, x); |
353 | do_pending_stack_adjust (); |
354 | |
355 | seq = get_insns (); |
356 | end_sequence (); |
357 | |
358 | insert_insn_on_edge (seq, e); |
359 | } |
360 | |
361 | /* Insert a copy instruction from RTL expression SRC to partition DEST |
362 | onto edge E. */ |
363 | |
364 | static void |
365 | insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp, |
366 | location_t locus) |
367 | { |
368 | if (dump_file && (dump_flags & TDF_DETAILS)) |
369 | { |
370 | fprintf (stream: dump_file, |
371 | format: "Inserting a temp copy on edge BB%d->BB%d : PART.%d = " , |
372 | e->src->index, |
373 | e->dest->index, dest); |
374 | print_simple_rtl (dump_file, src); |
375 | fprintf (stream: dump_file, format: "\n" ); |
376 | } |
377 | |
378 | gcc_assert (SA.partition_to_pseudo[dest]); |
379 | |
380 | set_location_for_edge (e); |
381 | /* If a locus is provided, override the default. */ |
382 | if (locus) |
383 | set_curr_insn_location (locus); |
384 | |
385 | /* We give the destination as sizeexp in case src/dest are BLKmode |
386 | mems. Usually we give the source. As we result from SSA names |
387 | the left and right size should be the same (and no WITH_SIZE_EXPR |
388 | involved), so it doesn't matter. */ |
389 | rtx_insn *seq = emit_partition_copy (dest: copy_rtx (SA.partition_to_pseudo[dest]), |
390 | src, unsignedsrcp, |
391 | sizeexp: partition_to_var (map: SA.map, i: dest)); |
392 | |
393 | insert_insn_on_edge (seq, e); |
394 | } |
395 | |
396 | /* Insert a copy instruction from partition SRC to RTL lvalue DEST |
397 | onto edge E. */ |
398 | |
399 | static void |
400 | insert_part_to_rtx_on_edge (edge e, rtx dest, int src, location_t locus) |
401 | { |
402 | tree var; |
403 | if (dump_file && (dump_flags & TDF_DETAILS)) |
404 | { |
405 | fprintf (stream: dump_file, |
406 | format: "Inserting a temp copy on edge BB%d->BB%d : " , |
407 | e->src->index, |
408 | e->dest->index); |
409 | print_simple_rtl (dump_file, dest); |
410 | fprintf (stream: dump_file, format: "= PART.%d\n" , src); |
411 | } |
412 | |
413 | gcc_assert (SA.partition_to_pseudo[src]); |
414 | |
415 | set_location_for_edge (e); |
416 | /* If a locus is provided, override the default. */ |
417 | if (locus) |
418 | set_curr_insn_location (locus); |
419 | |
420 | var = partition_to_var (map: SA.map, i: src); |
421 | rtx_insn *seq = emit_partition_copy (dest, |
422 | src: copy_rtx (SA.partition_to_pseudo[src]), |
423 | TYPE_UNSIGNED (TREE_TYPE (var)), |
424 | sizeexp: var); |
425 | |
426 | insert_insn_on_edge (seq, e); |
427 | } |
428 | |
429 | |
430 | /* Create an elimination graph for map. */ |
431 | |
432 | elim_graph::elim_graph (var_map map) : |
433 | nodes (30), edge_list (20), edge_locus (10), visited (map->num_partitions), |
434 | stack (30), map (map), const_dests (20), const_copies (20), copy_locus (10) |
435 | { |
436 | } |
437 | |
438 | |
439 | /* Empty elimination graph G. */ |
440 | |
441 | static inline void |
442 | clear_elim_graph (elim_graph *g) |
443 | { |
444 | g->nodes.truncate (size: 0); |
445 | g->edge_list.truncate (size: 0); |
446 | g->edge_locus.truncate (size: 0); |
447 | } |
448 | |
449 | |
450 | /* Return the number of nodes in graph G. */ |
451 | |
452 | static inline int |
453 | elim_graph_size (elim_graph *g) |
454 | { |
455 | return g->nodes.length (); |
456 | } |
457 | |
458 | |
459 | /* Add NODE to graph G, if it doesn't exist already. */ |
460 | |
461 | static inline void |
462 | elim_graph_add_node (elim_graph *g, int node) |
463 | { |
464 | int x; |
465 | int t; |
466 | |
467 | FOR_EACH_VEC_ELT (g->nodes, x, t) |
468 | if (t == node) |
469 | return; |
470 | g->nodes.safe_push (obj: node); |
471 | } |
472 | |
473 | |
474 | /* Add the edge PRED->SUCC to graph G. */ |
475 | |
476 | static inline void |
477 | elim_graph_add_edge (elim_graph *g, int pred, int succ, location_t locus) |
478 | { |
479 | g->edge_list.safe_push (obj: pred); |
480 | g->edge_list.safe_push (obj: succ); |
481 | g->edge_locus.safe_push (obj: locus); |
482 | } |
483 | |
484 | |
485 | /* Remove an edge from graph G for which NODE is the predecessor, and |
486 | return the successor node. -1 is returned if there is no such edge. */ |
487 | |
488 | static inline int |
489 | elim_graph_remove_succ_edge (elim_graph *g, int node, location_t *locus) |
490 | { |
491 | int y; |
492 | unsigned x; |
493 | for (x = 0; x < g->edge_list.length (); x += 2) |
494 | if (g->edge_list[x] == node) |
495 | { |
496 | g->edge_list[x] = -1; |
497 | y = g->edge_list[x + 1]; |
498 | g->edge_list[x + 1] = -1; |
499 | *locus = g->edge_locus[x / 2]; |
500 | g->edge_locus[x / 2] = UNKNOWN_LOCATION; |
501 | return y; |
502 | } |
503 | *locus = UNKNOWN_LOCATION; |
504 | return -1; |
505 | } |
506 | |
507 | |
508 | /* Find all the nodes in GRAPH which are successors to NODE in the |
509 | edge list. VAR will hold the partition number found. CODE is the |
510 | code fragment executed for every node found. */ |
511 | |
512 | #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \ |
513 | do { \ |
514 | unsigned x_; \ |
515 | int y_; \ |
516 | for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \ |
517 | { \ |
518 | y_ = (GRAPH)->edge_list[x_]; \ |
519 | if (y_ != (NODE)) \ |
520 | continue; \ |
521 | (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \ |
522 | (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \ |
523 | CODE; \ |
524 | } \ |
525 | } while (0) |
526 | |
527 | |
528 | /* Find all the nodes which are predecessors of NODE in the edge list for |
529 | GRAPH. VAR will hold the partition number found. CODE is the |
530 | code fragment executed for every node found. */ |
531 | |
532 | #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \ |
533 | do { \ |
534 | unsigned x_; \ |
535 | int y_; \ |
536 | for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \ |
537 | { \ |
538 | y_ = (GRAPH)->edge_list[x_ + 1]; \ |
539 | if (y_ != (NODE)) \ |
540 | continue; \ |
541 | (void) ((VAR) = (GRAPH)->edge_list[x_]); \ |
542 | (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \ |
543 | CODE; \ |
544 | } \ |
545 | } while (0) |
546 | |
547 | |
548 | /* Add T to elimination graph G. */ |
549 | |
550 | static inline void |
551 | eliminate_name (elim_graph *g, int T) |
552 | { |
553 | elim_graph_add_node (g, node: T); |
554 | } |
555 | |
556 | /* Return true if this phi argument T should have a copy queued when using |
557 | var_map MAP. PHI nodes should contain only ssa_names and invariants. A |
558 | test for ssa_name is definitely simpler, but don't let invalid contents |
559 | slip through in the meantime. */ |
560 | |
561 | static inline bool |
562 | queue_phi_copy_p (var_map map, tree t) |
563 | { |
564 | if (TREE_CODE (t) == SSA_NAME) |
565 | { |
566 | if (var_to_partition (map, var: t) == NO_PARTITION) |
567 | return true; |
568 | return false; |
569 | } |
570 | gcc_checking_assert (is_gimple_min_invariant (t)); |
571 | return true; |
572 | } |
573 | |
574 | /* Build elimination graph G for basic block BB on incoming PHI edge |
575 | G->e. */ |
576 | |
577 | static void |
578 | eliminate_build (elim_graph *g) |
579 | { |
580 | tree Ti; |
581 | int p0, pi; |
582 | gphi_iterator gsi; |
583 | |
584 | clear_elim_graph (g); |
585 | |
586 | for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
587 | { |
588 | gphi *phi = gsi.phi (); |
589 | location_t locus; |
590 | |
591 | p0 = var_to_partition (map: g->map, var: gimple_phi_result (gs: phi)); |
592 | /* Ignore results which are not in partitions. */ |
593 | if (p0 == NO_PARTITION) |
594 | continue; |
595 | |
596 | Ti = PHI_ARG_DEF (phi, g->e->dest_idx); |
597 | /* See set_location_for_edge for the rationale. */ |
598 | if (g->e->flags & EDGE_EH) |
599 | locus = UNKNOWN_LOCATION; |
600 | else |
601 | locus = gimple_phi_arg_location_from_edge (phi, e: g->e); |
602 | |
603 | /* If this argument is a constant, or a SSA_NAME which is being |
604 | left in SSA form, just queue a copy to be emitted on this |
605 | edge. */ |
606 | if (queue_phi_copy_p (map: g->map, t: Ti)) |
607 | { |
608 | /* Save constant copies until all other copies have been emitted |
609 | on this edge. */ |
610 | g->const_dests.safe_push (obj: p0); |
611 | g->const_copies.safe_push (obj: Ti); |
612 | g->copy_locus.safe_push (obj: locus); |
613 | } |
614 | else |
615 | { |
616 | pi = var_to_partition (map: g->map, var: Ti); |
617 | if (p0 != pi) |
618 | { |
619 | eliminate_name (g, T: p0); |
620 | eliminate_name (g, T: pi); |
621 | elim_graph_add_edge (g, pred: p0, succ: pi, locus); |
622 | } |
623 | } |
624 | } |
625 | } |
626 | |
627 | |
628 | /* Push successors of T onto the elimination stack for G. */ |
629 | |
630 | static void |
631 | elim_forward (elim_graph *g, int T) |
632 | { |
633 | int S; |
634 | location_t locus; |
635 | |
636 | bitmap_set_bit (map: g->visited, bitno: T); |
637 | FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus, |
638 | { |
639 | if (!bitmap_bit_p (g->visited, S)) |
640 | elim_forward (g, S); |
641 | }); |
642 | g->stack.safe_push (obj: T); |
643 | } |
644 | |
645 | |
646 | /* Return 1 if there unvisited predecessors of T in graph G. */ |
647 | |
648 | static int |
649 | elim_unvisited_predecessor (elim_graph *g, int T) |
650 | { |
651 | int P; |
652 | location_t locus; |
653 | |
654 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, |
655 | { |
656 | if (!bitmap_bit_p (g->visited, P)) |
657 | return 1; |
658 | }); |
659 | return 0; |
660 | } |
661 | |
662 | /* Process predecessors first, and insert a copy. */ |
663 | |
664 | static void |
665 | elim_backward (elim_graph *g, int T) |
666 | { |
667 | int P; |
668 | location_t locus; |
669 | |
670 | bitmap_set_bit (map: g->visited, bitno: T); |
671 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, |
672 | { |
673 | if (!bitmap_bit_p (g->visited, P)) |
674 | { |
675 | elim_backward (g, P); |
676 | insert_partition_copy_on_edge (g->e, P, T, locus); |
677 | } |
678 | }); |
679 | } |
680 | |
681 | /* Allocate a new pseudo register usable for storing values sitting |
682 | in NAME (a decl or SSA name), i.e. with matching mode and attributes. */ |
683 | |
684 | static rtx |
685 | get_temp_reg (tree name) |
686 | { |
687 | tree type = TREE_TYPE (name); |
688 | int unsignedp; |
689 | machine_mode reg_mode = promote_ssa_mode (name, &unsignedp); |
690 | if (reg_mode == BLKmode) |
691 | return assign_temp (type, 0, 0); |
692 | rtx x = gen_reg_rtx (reg_mode); |
693 | if (POINTER_TYPE_P (type)) |
694 | mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (type))); |
695 | return x; |
696 | } |
697 | |
698 | /* Insert required copies for T in graph G. Check for a strongly connected |
699 | region, and create a temporary to break the cycle if one is found. */ |
700 | |
701 | static void |
702 | elim_create (elim_graph *g, int T) |
703 | { |
704 | int P, S; |
705 | location_t locus; |
706 | |
707 | if (elim_unvisited_predecessor (g, T)) |
708 | { |
709 | tree var = partition_to_var (map: g->map, i: T); |
710 | rtx U = get_temp_reg (name: var); |
711 | int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var)); |
712 | |
713 | insert_part_to_rtx_on_edge (e: g->e, dest: U, src: T, UNKNOWN_LOCATION); |
714 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, |
715 | { |
716 | if (!bitmap_bit_p (g->visited, P)) |
717 | { |
718 | elim_backward (g, P); |
719 | insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus); |
720 | } |
721 | }); |
722 | } |
723 | else |
724 | { |
725 | S = elim_graph_remove_succ_edge (g, node: T, locus: &locus); |
726 | if (S != -1) |
727 | { |
728 | bitmap_set_bit (map: g->visited, bitno: T); |
729 | insert_partition_copy_on_edge (e: g->e, dest: T, src: S, locus); |
730 | } |
731 | } |
732 | } |
733 | |
734 | |
735 | /* Eliminate all the phi nodes on edge E in graph G. */ |
736 | |
737 | static void |
738 | eliminate_phi (edge e, elim_graph *g) |
739 | { |
740 | int x; |
741 | |
742 | gcc_assert (g->const_copies.length () == 0); |
743 | gcc_assert (g->copy_locus.length () == 0); |
744 | |
745 | /* Abnormal edges already have everything coalesced. */ |
746 | if (e->flags & EDGE_ABNORMAL) |
747 | return; |
748 | |
749 | g->e = e; |
750 | |
751 | eliminate_build (g); |
752 | |
753 | if (elim_graph_size (g) != 0) |
754 | { |
755 | int part; |
756 | |
757 | bitmap_clear (g->visited); |
758 | g->stack.truncate (size: 0); |
759 | |
760 | FOR_EACH_VEC_ELT (g->nodes, x, part) |
761 | { |
762 | if (!bitmap_bit_p (map: g->visited, bitno: part)) |
763 | elim_forward (g, T: part); |
764 | } |
765 | |
766 | bitmap_clear (g->visited); |
767 | while (g->stack.length () > 0) |
768 | { |
769 | x = g->stack.pop (); |
770 | if (!bitmap_bit_p (map: g->visited, bitno: x)) |
771 | elim_create (g, T: x); |
772 | } |
773 | } |
774 | |
775 | /* If there are any pending constant copies, issue them now. */ |
776 | while (g->const_copies.length () > 0) |
777 | { |
778 | int dest; |
779 | tree src; |
780 | location_t locus; |
781 | |
782 | src = g->const_copies.pop (); |
783 | dest = g->const_dests.pop (); |
784 | locus = g->copy_locus.pop (); |
785 | insert_value_copy_on_edge (e, dest, src, locus); |
786 | } |
787 | } |
788 | |
789 | |
790 | /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME, |
791 | check to see if this allows another PHI node to be removed. */ |
792 | |
793 | static void |
794 | remove_gimple_phi_args (gphi *phi) |
795 | { |
796 | use_operand_p arg_p; |
797 | ssa_op_iter iter; |
798 | |
799 | if (dump_file && (dump_flags & TDF_DETAILS)) |
800 | { |
801 | fprintf (stream: dump_file, format: "Removing Dead PHI definition: " ); |
802 | print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); |
803 | } |
804 | |
805 | FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE) |
806 | { |
807 | tree arg = USE_FROM_PTR (arg_p); |
808 | if (TREE_CODE (arg) == SSA_NAME) |
809 | { |
810 | /* Remove the reference to the existing argument. */ |
811 | SET_USE (arg_p, NULL_TREE); |
812 | if (has_zero_uses (var: arg)) |
813 | { |
814 | gimple *stmt; |
815 | gimple_stmt_iterator gsi; |
816 | |
817 | stmt = SSA_NAME_DEF_STMT (arg); |
818 | |
819 | /* Also remove the def if it is a PHI node. */ |
820 | if (gimple_code (g: stmt) == GIMPLE_PHI) |
821 | { |
822 | remove_gimple_phi_args (phi: as_a <gphi *> (p: stmt)); |
823 | gsi = gsi_for_stmt (stmt); |
824 | remove_phi_node (&gsi, true); |
825 | } |
826 | |
827 | } |
828 | } |
829 | } |
830 | } |
831 | |
832 | /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */ |
833 | |
834 | static void |
835 | eliminate_useless_phis (void) |
836 | { |
837 | basic_block bb; |
838 | gphi_iterator gsi; |
839 | tree result; |
840 | |
841 | FOR_EACH_BB_FN (bb, cfun) |
842 | { |
843 | for (gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi); ) |
844 | { |
845 | gphi *phi = gsi.phi (); |
846 | result = gimple_phi_result (gs: phi); |
847 | if (virtual_operand_p (op: result)) |
848 | remove_phi_node (&gsi, true); |
849 | else |
850 | { |
851 | /* Also remove real PHIs with no uses. */ |
852 | if (has_zero_uses (var: result)) |
853 | { |
854 | remove_gimple_phi_args (phi); |
855 | remove_phi_node (&gsi, true); |
856 | } |
857 | else |
858 | gsi_next (i: &gsi); |
859 | } |
860 | } |
861 | } |
862 | } |
863 | |
864 | |
865 | /* This function will rewrite the current program using the variable mapping |
866 | found in MAP. If the replacement vector VALUES is provided, any |
867 | occurrences of partitions with non-null entries in the vector will be |
868 | replaced with the expression in the vector instead of its mapped |
869 | variable. */ |
870 | |
871 | static void |
872 | rewrite_trees (var_map map) |
873 | { |
874 | if (!flag_checking) |
875 | return; |
876 | |
877 | basic_block bb; |
878 | /* Search for PHIs where the destination has no partition, but one |
879 | or more arguments has a partition. This should not happen and can |
880 | create incorrect code. */ |
881 | FOR_EACH_BB_FN (bb, cfun) |
882 | { |
883 | gphi_iterator gsi; |
884 | for (gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
885 | { |
886 | gphi *phi = gsi.phi (); |
887 | tree T0 = var_to_partition_to_var (map, var: gimple_phi_result (gs: phi)); |
888 | if (T0 == NULL_TREE) |
889 | { |
890 | size_t i; |
891 | for (i = 0; i < gimple_phi_num_args (gs: phi); i++) |
892 | { |
893 | tree arg = PHI_ARG_DEF (phi, i); |
894 | |
895 | if (TREE_CODE (arg) == SSA_NAME |
896 | && var_to_partition (map, var: arg) != NO_PARTITION) |
897 | { |
898 | fprintf (stderr, format: "Argument of PHI is in a partition :(" ); |
899 | print_generic_expr (stderr, arg, TDF_SLIM); |
900 | fprintf (stderr, format: "), but the result is not :" ); |
901 | print_gimple_stmt (stderr, phi, 0, TDF_SLIM); |
902 | internal_error ("SSA corruption" ); |
903 | } |
904 | } |
905 | } |
906 | } |
907 | } |
908 | } |
909 | |
910 | /* Create a default def for VAR. */ |
911 | |
912 | static void |
913 | create_default_def (tree var, void *arg ATTRIBUTE_UNUSED) |
914 | { |
915 | if (!is_gimple_reg (var)) |
916 | return; |
917 | |
918 | tree ssa = get_or_create_ssa_default_def (cfun, var); |
919 | gcc_assert (ssa); |
920 | } |
921 | |
922 | /* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which |
923 | assign_parms may ask for a default partition. */ |
924 | |
925 | static void |
926 | for_all_parms (void (*callback)(tree var, void *arg), void *arg) |
927 | { |
928 | for (tree var = DECL_ARGUMENTS (current_function_decl); var; |
929 | var = DECL_CHAIN (var)) |
930 | callback (var, arg); |
931 | if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) |
932 | callback (DECL_RESULT (current_function_decl), arg); |
933 | if (cfun->static_chain_decl) |
934 | callback (cfun->static_chain_decl, arg); |
935 | } |
936 | |
937 | /* We need to pass two arguments to set_parm_default_def_partition, |
938 | but for_all_parms only supports one. Use a pair. */ |
939 | |
940 | typedef std::pair<var_map, bitmap> parm_default_def_partition_arg; |
941 | |
942 | /* Set in ARG's PARTS bitmap the bit corresponding to the partition in |
943 | ARG's MAP containing VAR's default def. */ |
944 | |
945 | static void |
946 | set_parm_default_def_partition (tree var, void *arg_) |
947 | { |
948 | parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_; |
949 | var_map map = arg->first; |
950 | bitmap parts = arg->second; |
951 | |
952 | if (!is_gimple_reg (var)) |
953 | return; |
954 | |
955 | tree ssa = ssa_default_def (cfun, var); |
956 | gcc_assert (ssa); |
957 | |
958 | int version = var_to_partition (map, var: ssa); |
959 | gcc_assert (version != NO_PARTITION); |
960 | |
961 | bool changed = bitmap_set_bit (parts, version); |
962 | gcc_assert (changed); |
963 | } |
964 | |
965 | /* Allocate and return a bitmap that has a bit set for each partition |
966 | that contains a default def for a parameter. */ |
967 | |
968 | static bitmap |
969 | get_parm_default_def_partitions (var_map map) |
970 | { |
971 | bitmap parm_default_def_parts = BITMAP_ALLOC (NULL); |
972 | |
973 | parm_default_def_partition_arg |
974 | arg = std::make_pair (x&: map, y&: parm_default_def_parts); |
975 | |
976 | for_all_parms (callback: set_parm_default_def_partition, arg: &arg); |
977 | |
978 | return parm_default_def_parts; |
979 | } |
980 | |
981 | /* Allocate and return a bitmap that has a bit set for each partition |
982 | that contains an undefined value. */ |
983 | |
984 | static bitmap |
985 | get_undefined_value_partitions (var_map map) |
986 | { |
987 | bitmap undefined_value_parts = BITMAP_ALLOC (NULL); |
988 | |
989 | for (unsigned int i = 1; i < num_ssa_names; i++) |
990 | { |
991 | tree var = ssa_name (i); |
992 | if (var |
993 | && !virtual_operand_p (op: var) |
994 | && !has_zero_uses (var) |
995 | && ssa_undefined_value_p (var)) |
996 | { |
997 | const int p = var_to_partition (map, var); |
998 | if (p != NO_PARTITION) |
999 | bitmap_set_bit (undefined_value_parts, p); |
1000 | } |
1001 | } |
1002 | |
1003 | return undefined_value_parts; |
1004 | } |
1005 | |
1006 | /* Given the out-of-ssa info object SA (with prepared partitions) |
1007 | eliminate all phi nodes in all basic blocks. Afterwards no |
1008 | basic block will have phi nodes anymore and there are possibly |
1009 | some RTL instructions inserted on edges. */ |
1010 | |
1011 | void |
1012 | expand_phi_nodes (struct ssaexpand *sa) |
1013 | { |
1014 | basic_block bb; |
1015 | elim_graph g (sa->map); |
1016 | |
1017 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, |
1018 | EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) |
1019 | if (!gimple_seq_empty_p (s: phi_nodes (bb))) |
1020 | { |
1021 | edge e; |
1022 | edge_iterator ei; |
1023 | FOR_EACH_EDGE (e, ei, bb->preds) |
1024 | eliminate_phi (e, g: &g); |
1025 | set_phi_nodes (bb, NULL); |
1026 | /* We can't redirect EH edges in RTL land, so we need to do this |
1027 | here. Redirection happens only when splitting is necessary, |
1028 | which it is only for critical edges, normally. For EH edges |
1029 | it might also be necessary when the successor has more than |
1030 | one predecessor. In that case the edge is either required to |
1031 | be fallthru (which EH edges aren't), or the predecessor needs |
1032 | to end with a jump (which again, isn't the case with EH edges). |
1033 | Hence, split all EH edges on which we inserted instructions |
1034 | and whose successor has multiple predecessors. */ |
1035 | for (ei = ei_start (bb->preds); (e = ei_safe_edge (i: ei)); ) |
1036 | { |
1037 | if (e->insns.r && (e->flags & EDGE_EH) |
1038 | && !single_pred_p (bb: e->dest)) |
1039 | { |
1040 | rtx_insn *insns = e->insns.r; |
1041 | basic_block bb; |
1042 | e->insns.r = NULL; |
1043 | bb = split_edge (e); |
1044 | single_pred_edge (bb)->insns.r = insns; |
1045 | } |
1046 | else |
1047 | ei_next (i: &ei); |
1048 | } |
1049 | } |
1050 | } |
1051 | |
1052 | |
1053 | /* Remove the ssa-names in the current function and translate them into normal |
1054 | compiler variables. PERFORM_TER is true if Temporary Expression Replacement |
1055 | should also be used. */ |
1056 | |
1057 | static void |
1058 | remove_ssa_form (bool perform_ter, struct ssaexpand *sa) |
1059 | { |
1060 | bitmap values = NULL; |
1061 | var_map map; |
1062 | |
1063 | for_all_parms (callback: create_default_def, NULL); |
1064 | map = init_var_map (num_ssa_names); |
1065 | coalesce_ssa_name (map); |
1066 | |
1067 | /* Return to viewing the variable list as just all reference variables after |
1068 | coalescing has been performed. */ |
1069 | partition_view_normal (map); |
1070 | |
1071 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1072 | { |
1073 | fprintf (stream: dump_file, format: "After Coalescing:\n" ); |
1074 | dump_var_map (dump_file, map); |
1075 | } |
1076 | |
1077 | if (perform_ter) |
1078 | { |
1079 | values = find_replaceable_exprs (map); |
1080 | if (values && dump_file && (dump_flags & TDF_DETAILS)) |
1081 | dump_replaceable_exprs (dump_file, values); |
1082 | } |
1083 | |
1084 | rewrite_trees (map); |
1085 | |
1086 | sa->map = map; |
1087 | sa->values = values; |
1088 | sa->partitions_for_parm_default_defs = get_parm_default_def_partitions (map); |
1089 | sa->partitions_for_undefined_values = get_undefined_value_partitions (map); |
1090 | } |
1091 | |
1092 | |
1093 | /* If not already done so for basic block BB, assign increasing uids |
1094 | to each of its instructions. */ |
1095 | |
1096 | static void |
1097 | maybe_renumber_stmts_bb (basic_block bb) |
1098 | { |
1099 | unsigned i = 0; |
1100 | gimple_stmt_iterator gsi; |
1101 | |
1102 | if (!bb->aux) |
1103 | return; |
1104 | bb->aux = NULL; |
1105 | for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
1106 | { |
1107 | gimple *stmt = gsi_stmt (i: gsi); |
1108 | gimple_set_uid (g: stmt, uid: i); |
1109 | i++; |
1110 | } |
1111 | } |
1112 | |
1113 | |
1114 | /* Return true if we can determine that the SSA_NAMEs RESULT (a result |
1115 | of a PHI node) and ARG (one of its arguments) conflict. Return false |
1116 | otherwise, also when we simply aren't sure. */ |
1117 | |
1118 | static bool |
1119 | trivially_conflicts_p (basic_block bb, tree result, tree arg) |
1120 | { |
1121 | use_operand_p use; |
1122 | imm_use_iterator imm_iter; |
1123 | gimple *defa = SSA_NAME_DEF_STMT (arg); |
1124 | |
1125 | /* If ARG isn't defined in the same block it's too complicated for |
1126 | our little mind. */ |
1127 | if (gimple_bb (g: defa) != bb) |
1128 | return false; |
1129 | |
1130 | FOR_EACH_IMM_USE_FAST (use, imm_iter, result) |
1131 | { |
1132 | gimple *use_stmt = USE_STMT (use); |
1133 | if (is_gimple_debug (gs: use_stmt)) |
1134 | continue; |
1135 | /* Now, if there's a use of RESULT that lies outside this basic block, |
1136 | then there surely is a conflict with ARG. */ |
1137 | if (gimple_bb (g: use_stmt) != bb) |
1138 | return true; |
1139 | if (gimple_code (g: use_stmt) == GIMPLE_PHI) |
1140 | continue; |
1141 | /* The use now is in a real stmt of BB, so if ARG was defined |
1142 | in a PHI node (like RESULT) both conflict. */ |
1143 | if (gimple_code (g: defa) == GIMPLE_PHI) |
1144 | return true; |
1145 | maybe_renumber_stmts_bb (bb); |
1146 | /* If the use of RESULT occurs after the definition of ARG, |
1147 | the two conflict too. */ |
1148 | if (gimple_uid (g: defa) < gimple_uid (g: use_stmt)) |
1149 | return true; |
1150 | } |
1151 | |
1152 | return false; |
1153 | } |
1154 | |
1155 | |
1156 | /* Search every PHI node for arguments associated with backedges which |
1157 | we can trivially determine will need a copy (the argument is either |
1158 | not an SSA_NAME or the argument has a different underlying variable |
1159 | than the PHI result). |
1160 | |
1161 | Insert a copy from the PHI argument to a new destination at the |
1162 | end of the block with the backedge to the top of the loop. Update |
1163 | the PHI argument to reference this new destination. */ |
1164 | |
1165 | static void |
1166 | insert_backedge_copies (void) |
1167 | { |
1168 | basic_block bb; |
1169 | gphi_iterator gsi; |
1170 | |
1171 | mark_dfs_back_edges (); |
1172 | |
1173 | FOR_EACH_BB_FN (bb, cfun) |
1174 | { |
1175 | /* Mark block as possibly needing calculation of UIDs. */ |
1176 | bb->aux = &bb->aux; |
1177 | |
1178 | for (gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
1179 | { |
1180 | gphi *phi = gsi.phi (); |
1181 | tree result = gimple_phi_result (gs: phi); |
1182 | size_t i; |
1183 | |
1184 | if (virtual_operand_p (op: result)) |
1185 | continue; |
1186 | |
1187 | for (i = 0; i < gimple_phi_num_args (gs: phi); i++) |
1188 | { |
1189 | tree arg = gimple_phi_arg_def (gs: phi, index: i); |
1190 | edge e = gimple_phi_arg_edge (phi, i); |
1191 | /* We are only interested in copies emitted on critical |
1192 | backedges. */ |
1193 | if (!(e->flags & EDGE_DFS_BACK) |
1194 | || !EDGE_CRITICAL_P (e)) |
1195 | continue; |
1196 | |
1197 | /* If the argument is not an SSA_NAME, then we will need a |
1198 | constant initialization. If the argument is an SSA_NAME then |
1199 | a copy statement may be needed. First handle the case |
1200 | where we cannot insert before the argument definition. */ |
1201 | if (TREE_CODE (arg) != SSA_NAME |
1202 | || (gimple_code (SSA_NAME_DEF_STMT (arg)) == GIMPLE_PHI |
1203 | && trivially_conflicts_p (bb, result, arg))) |
1204 | { |
1205 | tree name; |
1206 | gassign *stmt; |
1207 | gimple *last = NULL; |
1208 | gimple_stmt_iterator gsi2; |
1209 | |
1210 | gsi2 = gsi_last_bb (bb: gimple_phi_arg_edge (phi, i)->src); |
1211 | if (!gsi_end_p (i: gsi2)) |
1212 | last = gsi_stmt (i: gsi2); |
1213 | |
1214 | /* In theory the only way we ought to get back to the |
1215 | start of a loop should be with a COND_EXPR or GOTO_EXPR. |
1216 | However, better safe than sorry. |
1217 | If the block ends with a control statement or |
1218 | something that might throw, then we have to |
1219 | insert this assignment before the last |
1220 | statement. Else insert it after the last statement. */ |
1221 | if (last && stmt_ends_bb_p (last)) |
1222 | { |
1223 | /* If the last statement in the block is the definition |
1224 | site of the PHI argument, then we can't insert |
1225 | anything after it. */ |
1226 | if (TREE_CODE (arg) == SSA_NAME |
1227 | && SSA_NAME_DEF_STMT (arg) == last) |
1228 | continue; |
1229 | } |
1230 | |
1231 | /* Create a new instance of the underlying variable of the |
1232 | PHI result. */ |
1233 | name = copy_ssa_name (var: result); |
1234 | stmt = gimple_build_assign (name, |
1235 | gimple_phi_arg_def (gs: phi, index: i)); |
1236 | |
1237 | /* copy location if present. */ |
1238 | if (gimple_phi_arg_has_location (phi, i)) |
1239 | gimple_set_location (g: stmt, |
1240 | location: gimple_phi_arg_location (phi, i)); |
1241 | |
1242 | /* Insert the new statement into the block and update |
1243 | the PHI node. */ |
1244 | if (last && stmt_ends_bb_p (last)) |
1245 | gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT); |
1246 | else |
1247 | gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT); |
1248 | SET_PHI_ARG_DEF (phi, i, name); |
1249 | } |
1250 | /* Insert a copy before the definition of the backedge value |
1251 | and adjust all conflicting uses. */ |
1252 | else if (trivially_conflicts_p (bb, result, arg)) |
1253 | { |
1254 | gimple *def = SSA_NAME_DEF_STMT (arg); |
1255 | if (gimple_nop_p (g: def) |
1256 | || gimple_code (g: def) == GIMPLE_PHI) |
1257 | continue; |
1258 | tree name = copy_ssa_name (var: result); |
1259 | gimple *stmt = gimple_build_assign (name, result); |
1260 | imm_use_iterator imm_iter; |
1261 | gimple *use_stmt; |
1262 | /* The following matches trivially_conflicts_p. */ |
1263 | FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, result) |
1264 | { |
1265 | if (gimple_bb (g: use_stmt) != bb |
1266 | || (gimple_code (g: use_stmt) != GIMPLE_PHI |
1267 | && (maybe_renumber_stmts_bb (bb), true) |
1268 | && gimple_uid (g: use_stmt) > gimple_uid (g: def))) |
1269 | { |
1270 | use_operand_p use; |
1271 | FOR_EACH_IMM_USE_ON_STMT (use, imm_iter) |
1272 | SET_USE (use, name); |
1273 | } |
1274 | } |
1275 | gimple_stmt_iterator gsi = gsi_for_stmt (def); |
1276 | gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); |
1277 | } |
1278 | } |
1279 | } |
1280 | |
1281 | /* Unmark this block again. */ |
1282 | bb->aux = NULL; |
1283 | } |
1284 | } |
1285 | |
1286 | /* Remove indirect clobbers. */ |
1287 | |
1288 | static void |
1289 | remove_indirect_clobbers (void) |
1290 | { |
1291 | basic_block bb; |
1292 | |
1293 | FOR_EACH_BB_FN (bb, cfun) |
1294 | for (auto gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi);) |
1295 | { |
1296 | gimple *stmt = gsi_stmt (i: gsi); |
1297 | if (gimple_clobber_p (s: stmt)) |
1298 | { |
1299 | tree lhs = gimple_assign_lhs (gs: stmt); |
1300 | if (TREE_CODE (lhs) == MEM_REF |
1301 | && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME) |
1302 | { |
1303 | unlink_stmt_vdef (stmt); |
1304 | gsi_remove (&gsi, true); |
1305 | release_defs (stmt); |
1306 | continue; |
1307 | } |
1308 | } |
1309 | gsi_next (i: &gsi); |
1310 | } |
1311 | } |
1312 | |
1313 | /* Free all memory associated with going out of SSA form. SA is |
1314 | the outof-SSA info object. */ |
1315 | |
1316 | void |
1317 | finish_out_of_ssa (struct ssaexpand *sa) |
1318 | { |
1319 | free (ptr: sa->partition_to_pseudo); |
1320 | if (sa->values) |
1321 | BITMAP_FREE (sa->values); |
1322 | delete_var_map (sa->map); |
1323 | BITMAP_FREE (sa->partitions_for_parm_default_defs); |
1324 | BITMAP_FREE (sa->partitions_for_undefined_values); |
1325 | memset (s: sa, c: 0, n: sizeof *sa); |
1326 | } |
1327 | |
1328 | /* Take the current function out of SSA form, translating PHIs as described in |
1329 | R. Morgan, ``Building an Optimizing Compiler'', |
1330 | Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */ |
1331 | |
1332 | unsigned int |
1333 | rewrite_out_of_ssa (struct ssaexpand *sa) |
1334 | { |
1335 | /* Remove remaining indirect clobbers as we do not need those anymore. |
1336 | Those might extend SSA lifetime and restrict coalescing. */ |
1337 | remove_indirect_clobbers (); |
1338 | |
1339 | /* If elimination of a PHI requires inserting a copy on a backedge, |
1340 | then we will have to split the backedge which has numerous |
1341 | undesirable performance effects. |
1342 | |
1343 | A significant number of such cases can be handled here by inserting |
1344 | copies into the loop itself. */ |
1345 | insert_backedge_copies (); |
1346 | |
1347 | /* Eliminate PHIs which are of no use, such as virtual or dead phis. */ |
1348 | eliminate_useless_phis (); |
1349 | |
1350 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1351 | gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); |
1352 | |
1353 | remove_ssa_form (flag_tree_ter, sa); |
1354 | |
1355 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1356 | gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); |
1357 | |
1358 | return 0; |
1359 | } |
1360 | |