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