]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Convert a program in SSA form into Normal form. |
23a5b65a | 2 | Copyright (C) 2004-2014 Free Software Foundation, Inc. |
6de9cd9a DN |
3 | Contributed by Andrew Macleod <amacleod@redhat.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
10 | any later version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
d8a2d370 | 26 | #include "stor-layout.h" |
60393bbc AM |
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" | |
6de9cd9a | 39 | #include "basic-block.h" |
cf835838 | 40 | #include "gimple-pretty-print.h" |
6de9cd9a | 41 | #include "bitmap.h" |
4484a35a | 42 | #include "sbitmap.h" |
2fb9a547 AM |
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" | |
442b4905 | 48 | #include "gimple.h" |
5be5c238 | 49 | #include "gimple-iterator.h" |
442b4905 AM |
50 | #include "gimple-ssa.h" |
51 | #include "tree-cfg.h" | |
52 | #include "tree-phinodes.h" | |
53 | #include "ssa-iterators.h" | |
d8a2d370 | 54 | #include "stringpool.h" |
442b4905 | 55 | #include "tree-ssanames.h" |
7ee2468b | 56 | #include "dumpfile.h" |
718f9c0f | 57 | #include "diagnostic-core.h" |
8e9055ae AM |
58 | #include "tree-ssa-live.h" |
59 | #include "tree-ssa-ter.h" | |
60 | #include "tree-ssa-coalesce.h" | |
78bca40d | 61 | #include "tree-outof-ssa.h" |
6de9cd9a | 62 | |
2eb79bbb SB |
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 | ||
78bca40d AM |
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 | } | |
56b043c8 | 122 | |
f5045c96 | 123 | |
6de9cd9a DN |
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 | |
b8698a0f L |
129 | [0] ->PRED, [1]->SUCC. All the even indexes in the array represent |
130 | predecessors, all the odd elements are successors. | |
131 | ||
6de9cd9a | 132 | Rationale: |
b8698a0f | 133 | When implemented as bitmaps, very large programs SSA->Normal times were |
6de9cd9a DN |
134 | being dominated by clearing the interference graph. |
135 | ||
b8698a0f L |
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 | |
6de9cd9a DN |
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. */ | |
b8698a0f | 144 | |
6de9cd9a DN |
145 | typedef struct _elim_graph { |
146 | /* Size of the elimination vectors. */ | |
147 | int size; | |
148 | ||
149 | /* List of nodes in the elimination graph. */ | |
9771b263 | 150 | vec<int> nodes; |
6de9cd9a | 151 | |
9cf737f8 | 152 | /* The predecessor and successor edge list. */ |
9771b263 | 153 | vec<int> edge_list; |
6de9cd9a | 154 | |
f5045c96 | 155 | /* Source locus on each edge */ |
9771b263 | 156 | vec<source_location> edge_locus; |
f5045c96 | 157 | |
6de9cd9a DN |
158 | /* Visited vector. */ |
159 | sbitmap visited; | |
160 | ||
161 | /* Stack for visited nodes. */ | |
9771b263 | 162 | vec<int> stack; |
b8698a0f | 163 | |
6de9cd9a DN |
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. */ | |
9771b263 DN |
171 | vec<int> const_dests; |
172 | vec<tree> const_copies; | |
f5045c96 AM |
173 | |
174 | /* Source locations for any constant copies. */ | |
9771b263 | 175 | vec<source_location> copy_locus; |
6de9cd9a DN |
176 | } *elim_graph; |
177 | ||
178 | ||
4e3825db MM |
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. */ | |
6de9cd9a | 185 | |
4e3825db MM |
186 | static void |
187 | set_location_for_edge (edge e) | |
6de9cd9a | 188 | { |
4e3825db MM |
189 | if (e->goto_locus) |
190 | { | |
5368224f | 191 | set_curr_insn_location (e->goto_locus); |
4e3825db MM |
192 | } |
193 | else | |
194 | { | |
195 | basic_block bb = e->src; | |
196 | gimple_stmt_iterator gsi; | |
6de9cd9a | 197 | |
4e3825db MM |
198 | do |
199 | { | |
200 | for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) | |
201 | { | |
202 | gimple stmt = gsi_stmt (gsi); | |
b5b8b0ac AO |
203 | if (is_gimple_debug (stmt)) |
204 | continue; | |
4e3825db MM |
205 | if (gimple_has_location (stmt) || gimple_block (stmt)) |
206 | { | |
5368224f | 207 | set_curr_insn_location (gimple_location (stmt)); |
4e3825db MM |
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 | } | |
6de9cd9a | 221 | |
c2172338 MM |
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. */ | |
8e001680 AK |
225 | |
226 | static inline rtx | |
c2172338 | 227 | emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp) |
8e001680 AK |
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); | |
c2172338 MM |
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); | |
8e001680 AK |
242 | |
243 | seq = get_insns (); | |
244 | end_sequence (); | |
245 | ||
246 | return seq; | |
247 | } | |
248 | ||
4e3825db | 249 | /* Insert a copy instruction from partition SRC to DEST onto edge E. */ |
ac3bfd86 | 250 | |
4e3825db | 251 | static void |
9e227d60 | 252 | insert_partition_copy_on_edge (edge e, int dest, int src, source_location locus) |
4e3825db | 253 | { |
c2172338 | 254 | tree var; |
4e3825db MM |
255 | rtx seq; |
256 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
dad2a933 | 257 | { |
4e3825db MM |
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"); | |
dad2a933 | 264 | } |
4e3825db MM |
265 | |
266 | gcc_assert (SA.partition_to_pseudo[dest]); | |
267 | gcc_assert (SA.partition_to_pseudo[src]); | |
268 | ||
269 | set_location_for_edge (e); | |
f5045c96 AM |
270 | /* If a locus is provided, override the default. */ |
271 | if (locus) | |
5368224f | 272 | set_curr_insn_location (locus); |
4e3825db | 273 | |
c2172338 | 274 | var = partition_to_var (SA.map, src); |
02b278a8 RS |
275 | seq = emit_partition_copy (copy_rtx (SA.partition_to_pseudo[dest]), |
276 | copy_rtx (SA.partition_to_pseudo[src]), | |
c2172338 MM |
277 | TYPE_UNSIGNED (TREE_TYPE (var)), |
278 | var); | |
4e3825db MM |
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 | |
9e227d60 | 287 | insert_value_copy_on_edge (edge e, int dest, tree src, source_location locus) |
4e3825db | 288 | { |
02b278a8 | 289 | rtx dest_rtx, seq, x; |
ef4bddc2 | 290 | machine_mode dest_mode, src_mode; |
8f048d2f | 291 | int unsignedp; |
b2a58473 | 292 | tree var; |
8f048d2f | 293 | |
4e3825db | 294 | if (dump_file && (dump_flags & TDF_DETAILS)) |
dad2a933 | 295 | { |
4e3825db MM |
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"); | |
dad2a933 | 302 | } |
6de9cd9a | 303 | |
02b278a8 RS |
304 | dest_rtx = copy_rtx (SA.partition_to_pseudo[dest]); |
305 | gcc_assert (dest_rtx); | |
6de9cd9a | 306 | |
4e3825db | 307 | set_location_for_edge (e); |
f5045c96 AM |
308 | /* If a locus is provided, override the default. */ |
309 | if (locus) | |
5368224f | 310 | set_curr_insn_location (locus); |
4e3825db MM |
311 | |
312 | start_sequence (); | |
8f048d2f | 313 | |
b2a58473 | 314 | var = SSA_NAME_VAR (partition_to_var (SA.map, dest)); |
8f048d2f | 315 | src_mode = TYPE_MODE (TREE_TYPE (src)); |
02b278a8 | 316 | dest_mode = GET_MODE (dest_rtx); |
b2a58473 | 317 | gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (var))); |
02b278a8 | 318 | gcc_assert (!REG_P (dest_rtx) |
b200cc3f | 319 | || dest_mode == promote_decl_mode (var, &unsignedp)); |
8f048d2f RS |
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 | } | |
c2172338 MM |
326 | else if (src_mode == BLKmode) |
327 | { | |
02b278a8 | 328 | x = dest_rtx; |
c2172338 MM |
329 | store_expr (src, x, 0, false); |
330 | } | |
8f048d2f | 331 | else |
02b278a8 | 332 | x = expand_expr (src, dest_rtx, dest_mode, EXPAND_NORMAL); |
8f048d2f | 333 | |
02b278a8 RS |
334 | if (x != dest_rtx) |
335 | emit_move_insn (dest_rtx, x); | |
4e3825db MM |
336 | seq = get_insns (); |
337 | end_sequence (); | |
6de9cd9a | 338 | |
4e3825db MM |
339 | insert_insn_on_edge (seq, e); |
340 | } | |
6de9cd9a | 341 | |
4e3825db MM |
342 | /* Insert a copy instruction from RTL expression SRC to partition DEST |
343 | onto edge E. */ | |
6de9cd9a DN |
344 | |
345 | static void | |
f5045c96 | 346 | insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp, |
9e227d60 | 347 | source_location locus) |
6de9cd9a | 348 | { |
4e3825db MM |
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 | } | |
6de9cd9a | 359 | |
4e3825db | 360 | gcc_assert (SA.partition_to_pseudo[dest]); |
f5045c96 | 361 | |
4e3825db | 362 | set_location_for_edge (e); |
f5045c96 AM |
363 | /* If a locus is provided, override the default. */ |
364 | if (locus) | |
5368224f | 365 | set_curr_insn_location (locus); |
6de9cd9a | 366 | |
c2172338 MM |
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. */ | |
02b278a8 | 371 | seq = emit_partition_copy (copy_rtx (SA.partition_to_pseudo[dest]), |
c2172338 MM |
372 | src, unsignedsrcp, |
373 | partition_to_var (SA.map, dest)); | |
6de9cd9a | 374 | |
4e3825db MM |
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 | |
9e227d60 | 382 | insert_part_to_rtx_on_edge (edge e, rtx dest, int src, source_location locus) |
4e3825db | 383 | { |
c2172338 | 384 | tree var; |
4e3825db | 385 | rtx seq; |
6de9cd9a DN |
386 | if (dump_file && (dump_flags & TDF_DETAILS)) |
387 | { | |
388 | fprintf (dump_file, | |
4e3825db | 389 | "Inserting a temp copy on edge BB%d->BB%d : ", |
6de9cd9a DN |
390 | e->src->index, |
391 | e->dest->index); | |
4e3825db MM |
392 | print_simple_rtl (dump_file, dest); |
393 | fprintf (dump_file, "= PART.%d\n", src); | |
6de9cd9a DN |
394 | } |
395 | ||
4e3825db | 396 | gcc_assert (SA.partition_to_pseudo[src]); |
f5045c96 | 397 | |
4e3825db | 398 | set_location_for_edge (e); |
f5045c96 AM |
399 | /* If a locus is provided, override the default. */ |
400 | if (locus) | |
5368224f | 401 | set_curr_insn_location (locus); |
4e3825db | 402 | |
c2172338 | 403 | var = partition_to_var (SA.map, src); |
8e001680 | 404 | seq = emit_partition_copy (dest, |
02b278a8 | 405 | copy_rtx (SA.partition_to_pseudo[src]), |
c2172338 MM |
406 | TYPE_UNSIGNED (TREE_TYPE (var)), |
407 | var); | |
4e3825db MM |
408 | |
409 | insert_insn_on_edge (seq, e); | |
6de9cd9a DN |
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 | ||
9771b263 DN |
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); | |
b8698a0f | 428 | |
6de9cd9a DN |
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 | { | |
9771b263 DN |
440 | g->nodes.truncate (0); |
441 | g->edge_list.truncate (0); | |
442 | g->edge_locus.truncate (0); | |
6de9cd9a DN |
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); | |
9771b263 DN |
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 (); | |
f5045c96 | 459 | |
6de9cd9a DN |
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 | { | |
9771b263 | 469 | return g->nodes.length (); |
6de9cd9a DN |
470 | } |
471 | ||
472 | ||
473 | /* Add NODE to graph G, if it doesn't exist already. */ | |
474 | ||
b8698a0f | 475 | static inline void |
4e3825db | 476 | elim_graph_add_node (elim_graph g, int node) |
6de9cd9a DN |
477 | { |
478 | int x; | |
4e3825db | 479 | int t; |
bf645d6f | 480 | |
9771b263 | 481 | FOR_EACH_VEC_ELT (g->nodes, x, t) |
bf645d6f | 482 | if (t == node) |
6de9cd9a | 483 | return; |
9771b263 | 484 | g->nodes.safe_push (node); |
6de9cd9a DN |
485 | } |
486 | ||
487 | ||
488 | /* Add the edge PRED->SUCC to graph G. */ | |
489 | ||
490 | static inline void | |
9e227d60 | 491 | elim_graph_add_edge (elim_graph g, int pred, int succ, source_location locus) |
6de9cd9a | 492 | { |
9771b263 DN |
493 | g->edge_list.safe_push (pred); |
494 | g->edge_list.safe_push (succ); | |
495 | g->edge_locus.safe_push (locus); | |
6de9cd9a DN |
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 | |
9e227d60 | 503 | elim_graph_remove_succ_edge (elim_graph g, int node, source_location *locus) |
6de9cd9a DN |
504 | { |
505 | int y; | |
506 | unsigned x; | |
9771b263 DN |
507 | for (x = 0; x < g->edge_list.length (); x += 2) |
508 | if (g->edge_list[x] == node) | |
6de9cd9a | 509 | { |
9771b263 DN |
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; | |
6de9cd9a DN |
515 | return y; |
516 | } | |
f5045c96 | 517 | *locus = UNKNOWN_LOCATION; |
6de9cd9a DN |
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 | ||
9e227d60 | 526 | #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \ |
6de9cd9a DN |
527 | do { \ |
528 | unsigned x_; \ | |
529 | int y_; \ | |
9771b263 | 530 | for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \ |
6de9cd9a | 531 | { \ |
9771b263 | 532 | y_ = (GRAPH)->edge_list[x_]; \ |
6de9cd9a DN |
533 | if (y_ != (NODE)) \ |
534 | continue; \ | |
9771b263 DN |
535 | (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \ |
536 | (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \ | |
6de9cd9a DN |
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 | ||
9e227d60 | 546 | #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \ |
6de9cd9a DN |
547 | do { \ |
548 | unsigned x_; \ | |
549 | int y_; \ | |
9771b263 | 550 | for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \ |
6de9cd9a | 551 | { \ |
9771b263 | 552 | y_ = (GRAPH)->edge_list[x_ + 1]; \ |
6de9cd9a DN |
553 | if (y_ != (NODE)) \ |
554 | continue; \ | |
9771b263 DN |
555 | (void) ((VAR) = (GRAPH)->edge_list[x_]); \ |
556 | (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \ | |
6de9cd9a DN |
557 | CODE; \ |
558 | } \ | |
559 | } while (0) | |
560 | ||
561 | ||
562 | /* Add T to elimination graph G. */ | |
563 | ||
564 | static inline void | |
4e3825db | 565 | eliminate_name (elim_graph g, int T) |
6de9cd9a DN |
566 | { |
567 | elim_graph_add_node (g, T); | |
568 | } | |
569 | ||
c8d97db2 AM |
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 | } | |
6de9cd9a | 587 | |
41f683ef KH |
588 | /* Build elimination graph G for basic block BB on incoming PHI edge |
589 | G->e. */ | |
6de9cd9a DN |
590 | |
591 | static void | |
4e3825db | 592 | eliminate_build (elim_graph g) |
6de9cd9a | 593 | { |
4e3825db | 594 | tree Ti; |
6de9cd9a | 595 | int p0, pi; |
726a989a | 596 | gimple_stmt_iterator gsi; |
6de9cd9a DN |
597 | |
598 | clear_elim_graph (g); | |
b8698a0f | 599 | |
4e3825db | 600 | for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
6de9cd9a | 601 | { |
726a989a | 602 | gimple phi = gsi_stmt (gsi); |
f5045c96 | 603 | source_location locus; |
726a989a | 604 | |
4e3825db | 605 | p0 = var_to_partition (g->map, gimple_phi_result (phi)); |
6de9cd9a | 606 | /* Ignore results which are not in partitions. */ |
4e3825db | 607 | if (p0 == NO_PARTITION) |
6de9cd9a DN |
608 | continue; |
609 | ||
41f683ef | 610 | Ti = PHI_ARG_DEF (phi, g->e->dest_idx); |
f5045c96 | 611 | locus = gimple_phi_arg_location_from_edge (phi, g->e); |
6de9cd9a DN |
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. */ | |
c8d97db2 | 616 | if (queue_phi_copy_p (g->map, Ti)) |
6de9cd9a DN |
617 | { |
618 | /* Save constant copies until all other copies have been emitted | |
619 | on this edge. */ | |
9771b263 DN |
620 | g->const_dests.safe_push (p0); |
621 | g->const_copies.safe_push (Ti); | |
622 | g->copy_locus.safe_push (locus); | |
6de9cd9a DN |
623 | } |
624 | else | |
625 | { | |
4e3825db MM |
626 | pi = var_to_partition (g->map, Ti); |
627 | if (p0 != pi) | |
6de9cd9a | 628 | { |
4e3825db MM |
629 | eliminate_name (g, p0); |
630 | eliminate_name (g, pi); | |
9e227d60 | 631 | elim_graph_add_edge (g, p0, pi, locus); |
6de9cd9a DN |
632 | } |
633 | } | |
634 | } | |
635 | } | |
636 | ||
637 | ||
638 | /* Push successors of T onto the elimination stack for G. */ | |
639 | ||
b8698a0f | 640 | static void |
6de9cd9a DN |
641 | elim_forward (elim_graph g, int T) |
642 | { | |
643 | int S; | |
f5045c96 AM |
644 | source_location locus; |
645 | ||
d7c028c0 | 646 | bitmap_set_bit (g->visited, T); |
9e227d60 | 647 | FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus, |
6de9cd9a | 648 | { |
d7c028c0 | 649 | if (!bitmap_bit_p (g->visited, S)) |
6de9cd9a DN |
650 | elim_forward (g, S); |
651 | }); | |
9771b263 | 652 | g->stack.safe_push (T); |
6de9cd9a DN |
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; | |
f5045c96 AM |
662 | source_location locus; |
663 | ||
9e227d60 | 664 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, |
6de9cd9a | 665 | { |
d7c028c0 | 666 | if (!bitmap_bit_p (g->visited, P)) |
6de9cd9a DN |
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; | |
f5045c96 AM |
678 | source_location locus; |
679 | ||
d7c028c0 | 680 | bitmap_set_bit (g->visited, T); |
9e227d60 | 681 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, |
6de9cd9a | 682 | { |
d7c028c0 | 683 | if (!bitmap_bit_p (g->visited, P)) |
6de9cd9a DN |
684 | { |
685 | elim_backward (g, P); | |
9e227d60 | 686 | insert_partition_copy_on_edge (g->e, P, T, locus); |
6de9cd9a DN |
687 | } |
688 | }); | |
689 | } | |
690 | ||
4e3825db MM |
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); | |
cde0f3fd | 699 | int unsignedp; |
ef4bddc2 | 700 | machine_mode reg_mode = promote_decl_mode (var, &unsignedp); |
4e3825db MM |
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 | ||
b8698a0f | 707 | /* Insert required copies for T in graph G. Check for a strongly connected |
6de9cd9a DN |
708 | region, and create a temporary to break the cycle if one is found. */ |
709 | ||
b8698a0f | 710 | static void |
6de9cd9a DN |
711 | elim_create (elim_graph g, int T) |
712 | { | |
6de9cd9a | 713 | int P, S; |
f5045c96 | 714 | source_location locus; |
6de9cd9a DN |
715 | |
716 | if (elim_unvisited_predecessor (g, T)) | |
717 | { | |
8e001680 AK |
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 | ||
9e227d60 DC |
722 | insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION); |
723 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, | |
6de9cd9a | 724 | { |
d7c028c0 | 725 | if (!bitmap_bit_p (g->visited, P)) |
6de9cd9a DN |
726 | { |
727 | elim_backward (g, P); | |
9e227d60 | 728 | insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus); |
6de9cd9a DN |
729 | } |
730 | }); | |
731 | } | |
732 | else | |
733 | { | |
9e227d60 | 734 | S = elim_graph_remove_succ_edge (g, T, &locus); |
6de9cd9a DN |
735 | if (S != -1) |
736 | { | |
d7c028c0 | 737 | bitmap_set_bit (g->visited, T); |
9e227d60 | 738 | insert_partition_copy_on_edge (g->e, T, S, locus); |
6de9cd9a DN |
739 | } |
740 | } | |
6de9cd9a DN |
741 | } |
742 | ||
7290d709 | 743 | |
41f683ef | 744 | /* Eliminate all the phi nodes on edge E in graph G. */ |
6de9cd9a DN |
745 | |
746 | static void | |
41f683ef | 747 | eliminate_phi (edge e, elim_graph g) |
6de9cd9a | 748 | { |
6de9cd9a | 749 | int x; |
6de9cd9a | 750 | |
9771b263 DN |
751 | gcc_assert (g->const_copies.length () == 0); |
752 | gcc_assert (g->copy_locus.length () == 0); | |
6de9cd9a | 753 | |
0e61db61 | 754 | /* Abnormal edges already have everything coalesced. */ |
6de9cd9a DN |
755 | if (e->flags & EDGE_ABNORMAL) |
756 | return; | |
757 | ||
6de9cd9a DN |
758 | g->e = e; |
759 | ||
4e3825db | 760 | eliminate_build (g); |
6de9cd9a DN |
761 | |
762 | if (elim_graph_size (g) != 0) | |
763 | { | |
4e3825db | 764 | int part; |
bf645d6f | 765 | |
f61e445a | 766 | bitmap_clear (g->visited); |
9771b263 | 767 | g->stack.truncate (0); |
6de9cd9a | 768 | |
9771b263 | 769 | FOR_EACH_VEC_ELT (g->nodes, x, part) |
6de9cd9a | 770 | { |
d7c028c0 | 771 | if (!bitmap_bit_p (g->visited, part)) |
4e3825db | 772 | elim_forward (g, part); |
6de9cd9a | 773 | } |
b8698a0f | 774 | |
f61e445a | 775 | bitmap_clear (g->visited); |
9771b263 | 776 | while (g->stack.length () > 0) |
6de9cd9a | 777 | { |
9771b263 | 778 | x = g->stack.pop (); |
d7c028c0 | 779 | if (!bitmap_bit_p (g->visited, x)) |
6de9cd9a DN |
780 | elim_create (g, x); |
781 | } | |
782 | } | |
783 | ||
784 | /* If there are any pending constant copies, issue them now. */ | |
9771b263 | 785 | while (g->const_copies.length () > 0) |
6de9cd9a | 786 | { |
4e3825db MM |
787 | int dest; |
788 | tree src; | |
f5045c96 AM |
789 | source_location locus; |
790 | ||
9771b263 DN |
791 | src = g->const_copies.pop (); |
792 | dest = g->const_dests.pop (); | |
793 | locus = g->copy_locus.pop (); | |
9e227d60 | 794 | insert_value_copy_on_edge (e, dest, src, locus); |
6de9cd9a DN |
795 | } |
796 | } | |
797 | ||
798 | ||
b8698a0f | 799 | /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME, |
ffd327a7 | 800 | check to see if this allows another PHI node to be removed. */ |
6de9cd9a DN |
801 | |
802 | static void | |
ffd327a7 AM |
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) | |
6de9cd9a DN |
845 | { |
846 | basic_block bb; | |
726a989a | 847 | gimple_stmt_iterator gsi; |
ffd327a7 | 848 | tree result; |
6de9cd9a | 849 | |
11cd3bed | 850 | FOR_EACH_BB_FN (bb, cfun) |
6de9cd9a | 851 | { |
726a989a | 852 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); ) |
6de9cd9a | 853 | { |
726a989a | 854 | gimple phi = gsi_stmt (gsi); |
ffd327a7 | 855 | result = gimple_phi_result (phi); |
ea057359 | 856 | if (virtual_operand_p (result)) |
6de9cd9a DN |
857 | { |
858 | #ifdef ENABLE_CHECKING | |
726a989a | 859 | size_t i; |
4b756989 AM |
860 | /* There should be no arguments which are not virtual, or the |
861 | results will be incorrect. */ | |
726a989a | 862 | for (i = 0; i < gimple_phi_num_args (phi); i++) |
6de9cd9a DN |
863 | { |
864 | tree arg = PHI_ARG_DEF (phi, i); | |
b8698a0f | 865 | if (TREE_CODE (arg) == SSA_NAME |
ea057359 | 866 | && !virtual_operand_p (arg)) |
6de9cd9a DN |
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 :"); | |
726a989a | 871 | print_gimple_stmt (stderr, phi, 0, TDF_SLIM); |
1e128c5f | 872 | internal_error ("SSA corruption"); |
6de9cd9a DN |
873 | } |
874 | } | |
875 | #endif | |
726a989a | 876 | remove_phi_node (&gsi, true); |
6de9cd9a | 877 | } |
726a989a | 878 | else |
ffd327a7 AM |
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 | } | |
6de9cd9a DN |
889 | } |
890 | } | |
891 | } | |
892 | ||
893 | ||
6de9cd9a | 894 | /* This function will rewrite the current program using the variable mapping |
b8698a0f L |
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 | |
6de9cd9a DN |
898 | variable. */ |
899 | ||
900 | static void | |
1fec7ed4 | 901 | rewrite_trees (var_map map ATTRIBUTE_UNUSED) |
6de9cd9a | 902 | { |
6de9cd9a | 903 | #ifdef ENABLE_CHECKING |
4e3825db | 904 | basic_block bb; |
6de9cd9a DN |
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. */ | |
11cd3bed | 908 | FOR_EACH_BB_FN (bb, cfun) |
6de9cd9a | 909 | { |
4e3825db | 910 | gimple_stmt_iterator gsi; |
726a989a | 911 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
6de9cd9a | 912 | { |
726a989a RB |
913 | gimple phi = gsi_stmt (gsi); |
914 | tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi)); | |
6de9cd9a DN |
915 | if (T0 == NULL_TREE) |
916 | { | |
726a989a RB |
917 | size_t i; |
918 | for (i = 0; i < gimple_phi_num_args (phi); i++) | |
6de9cd9a DN |
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 :"); | |
726a989a | 928 | print_gimple_stmt (stderr, phi, 0, TDF_SLIM); |
1e128c5f | 929 | internal_error ("SSA corruption"); |
6de9cd9a DN |
930 | } |
931 | } | |
932 | } | |
933 | } | |
934 | } | |
935 | #endif | |
edfaf675 AM |
936 | } |
937 | ||
4e3825db MM |
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. */ | |
edfaf675 | 942 | |
4e3825db MM |
943 | void |
944 | expand_phi_nodes (struct ssaexpand *sa) | |
edfaf675 AM |
945 | { |
946 | basic_block bb; | |
4e3825db MM |
947 | elim_graph g = new_elim_graph (sa->map->num_partitions); |
948 | g->map = sa->map; | |
edfaf675 | 949 | |
fefa31b5 DM |
950 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, |
951 | EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
4e3825db | 952 | if (!gimple_seq_empty_p (phi_nodes (bb))) |
edfaf675 | 953 | { |
4e3825db MM |
954 | edge e; |
955 | edge_iterator ei; | |
edfaf675 | 956 | FOR_EACH_EDGE (e, ei, bb->preds) |
4e3825db MM |
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)); ) | |
edfaf675 | 969 | { |
4e3825db MM |
970 | if (e->insns.r && (e->flags & EDGE_EH) |
971 | && !single_pred_p (e->dest)) | |
972 | { | |
3ffa95c2 | 973 | rtx_insn *insns = e->insns.r; |
4e3825db | 974 | basic_block bb; |
3ffa95c2 | 975 | e->insns.r = NULL; |
4e3825db MM |
976 | bb = split_edge (e); |
977 | single_pred_edge (bb)->insns.r = insns; | |
978 | } | |
979 | else | |
980 | ei_next (&ei); | |
edfaf675 | 981 | } |
edfaf675 | 982 | } |
4e3825db MM |
983 | |
984 | delete_elim_graph (g); | |
6de9cd9a DN |
985 | } |
986 | ||
987 | ||
7290d709 AM |
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. */ | |
6de9cd9a | 991 | |
56b043c8 | 992 | static void |
4e3825db | 993 | remove_ssa_form (bool perform_ter, struct ssaexpand *sa) |
6de9cd9a | 994 | { |
e97809c6 | 995 | bitmap values = NULL; |
7290d709 | 996 | var_map map; |
4e3825db | 997 | unsigned i; |
6de9cd9a | 998 | |
7290d709 | 999 | map = coalesce_ssa_name (); |
6de9cd9a | 1000 | |
7290d709 AM |
1001 | /* Return to viewing the variable list as just all reference variables after |
1002 | coalescing has been performed. */ | |
1003 | partition_view_normal (map, false); | |
6de9cd9a DN |
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 | ||
7290d709 | 1011 | if (perform_ter) |
6de9cd9a DN |
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 | ||
4e3825db | 1018 | rewrite_trees (map); |
6de9cd9a | 1019 | |
4e3825db MM |
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++) | |
6de9cd9a | 1024 | { |
4e3825db MM |
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 | } | |
6de9cd9a | 1032 | } |
6de9cd9a DN |
1033 | } |
1034 | ||
7290d709 | 1035 | |
ce985b43 MM |
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; | |
b8698a0f | 1044 | |
ce985b43 MM |
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); | |
d6600130 JJ |
1076 | if (is_gimple_debug (use_stmt)) |
1077 | continue; | |
ce985b43 MM |
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 | } | |
b8698a0f | 1094 | |
ce985b43 MM |
1095 | return false; |
1096 | } | |
1097 | ||
1098 | ||
06170e1d JL |
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; | |
726a989a | 1112 | gimple_stmt_iterator gsi; |
06170e1d | 1113 | |
f2521653 BS |
1114 | mark_dfs_back_edges (); |
1115 | ||
11cd3bed | 1116 | FOR_EACH_BB_FN (bb, cfun) |
06170e1d | 1117 | { |
ce985b43 MM |
1118 | /* Mark block as possibly needing calculation of UIDs. */ |
1119 | bb->aux = &bb->aux; | |
1120 | ||
726a989a | 1121 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
06170e1d | 1122 | { |
726a989a RB |
1123 | gimple phi = gsi_stmt (gsi); |
1124 | tree result = gimple_phi_result (phi); | |
726a989a | 1125 | size_t i; |
06170e1d | 1126 | |
ea057359 | 1127 | if (virtual_operand_p (result)) |
06170e1d JL |
1128 | continue; |
1129 | ||
726a989a | 1130 | for (i = 0; i < gimple_phi_num_args (phi); i++) |
06170e1d | 1131 | { |
726a989a RB |
1132 | tree arg = gimple_phi_arg_def (phi, i); |
1133 | edge e = gimple_phi_arg_edge (phi, i); | |
06170e1d | 1134 | |
b8698a0f | 1135 | /* If the argument is not an SSA_NAME, then we will need a |
7290d709 | 1136 | constant initialization. If the argument is an SSA_NAME with |
b8698a0f | 1137 | a different underlying variable then a copy statement will be |
7290d709 | 1138 | needed. */ |
06170e1d JL |
1139 | if ((e->flags & EDGE_DFS_BACK) |
1140 | && (TREE_CODE (arg) != SSA_NAME | |
6b4a85ad | 1141 | || SSA_NAME_VAR (arg) != SSA_NAME_VAR (result) |
ce985b43 | 1142 | || trivially_conflicts_p (bb, result, arg))) |
06170e1d | 1143 | { |
726a989a RB |
1144 | tree name; |
1145 | gimple stmt, last = NULL; | |
1146 | gimple_stmt_iterator gsi2; | |
06170e1d | 1147 | |
726a989a RB |
1148 | gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src); |
1149 | if (!gsi_end_p (gsi2)) | |
1150 | last = gsi_stmt (gsi2); | |
06170e1d JL |
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. | |
b8698a0f | 1154 | However, better safe than sorry. |
35fd3193 | 1155 | If the block ends with a control statement or |
06170e1d JL |
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 | ||
b8698a0f | 1169 | /* Create a new instance of the underlying variable of the |
7290d709 | 1170 | PHI result. */ |
6b4a85ad RG |
1171 | name = copy_ssa_name (result, NULL); |
1172 | stmt = gimple_build_assign (name, | |
726a989a | 1173 | gimple_phi_arg_def (phi, i)); |
06170e1d | 1174 | |
f5045c96 AM |
1175 | /* copy location if present. */ |
1176 | if (gimple_phi_arg_has_location (phi, i)) | |
9e227d60 DC |
1177 | gimple_set_location (stmt, |
1178 | gimple_phi_arg_location (phi, i)); | |
f5045c96 | 1179 | |
06170e1d JL |
1180 | /* Insert the new statement into the block and update |
1181 | the PHI node. */ | |
1182 | if (last && stmt_ends_bb_p (last)) | |
726a989a | 1183 | gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT); |
06170e1d | 1184 | else |
726a989a | 1185 | gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT); |
06170e1d JL |
1186 | SET_PHI_ARG_DEF (phi, i, name); |
1187 | } | |
1188 | } | |
1189 | } | |
ce985b43 MM |
1190 | |
1191 | /* Unmark this block again. */ | |
1192 | bb->aux = NULL; | |
06170e1d JL |
1193 | } |
1194 | } | |
1195 | ||
4e3825db MM |
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) | |
e97809c6 | 1204 | BITMAP_FREE (sa->values); |
4e3825db MM |
1205 | delete_var_map (sa->map); |
1206 | BITMAP_FREE (sa->partition_has_default_def); | |
1207 | memset (sa, 0, sizeof *sa); | |
1208 | } | |
1209 | ||
7290d709 | 1210 | /* Take the current function out of SSA form, translating PHIs as described in |
6de9cd9a DN |
1211 | R. Morgan, ``Building an Optimizing Compiler'', |
1212 | Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */ | |
1213 | ||
4e3825db MM |
1214 | unsigned int |
1215 | rewrite_out_of_ssa (struct ssaexpand *sa) | |
6de9cd9a | 1216 | { |
06170e1d JL |
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 | ||
ffd327a7 AM |
1225 | |
1226 | /* Eliminate PHIs which are of no use, such as virtual or dead phis. */ | |
1227 | eliminate_useless_phis (); | |
6de9cd9a DN |
1228 | |
1229 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
726a989a | 1230 | gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); |
6de9cd9a | 1231 | |
4e3825db | 1232 | remove_ssa_form (flag_tree_ter, sa); |
6de9cd9a DN |
1233 | |
1234 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
726a989a | 1235 | gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); |
6de9cd9a | 1236 | |
c2924966 | 1237 | return 0; |
6de9cd9a | 1238 | } |