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