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