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