]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Convert a program in SSA form into Normal form. |
c75c517d | 2 | Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 |
b5b8b0ac | 3 | Free Software Foundation, Inc. |
6de9cd9a DN |
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 | |
9dcd6f09 | 10 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
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 | |
9dcd6f09 NC |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
21 | |
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "tree.h" | |
6de9cd9a | 27 | #include "ggc.h" |
6de9cd9a | 28 | #include "basic-block.h" |
cf835838 | 29 | #include "gimple-pretty-print.h" |
6de9cd9a DN |
30 | #include "bitmap.h" |
31 | #include "tree-flow.h" | |
7ee2468b | 32 | #include "dumpfile.h" |
718f9c0f | 33 | #include "diagnostic-core.h" |
4e3825db | 34 | #include "ssaexpand.h" |
6de9cd9a | 35 | |
2eb79bbb SB |
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 | ||
56b043c8 | 40 | |
f5045c96 AM |
41 | DEF_VEC_I(source_location); |
42 | DEF_VEC_ALLOC_I(source_location,heap); | |
43 | ||
6de9cd9a DN |
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 | |
b8698a0f L |
49 | [0] ->PRED, [1]->SUCC. All the even indexes in the array represent |
50 | predecessors, all the odd elements are successors. | |
51 | ||
6de9cd9a | 52 | Rationale: |
b8698a0f | 53 | When implemented as bitmaps, very large programs SSA->Normal times were |
6de9cd9a DN |
54 | being dominated by clearing the interference graph. |
55 | ||
b8698a0f L |
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 | |
6de9cd9a DN |
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. */ | |
b8698a0f | 64 | |
6de9cd9a DN |
65 | typedef struct _elim_graph { |
66 | /* Size of the elimination vectors. */ | |
67 | int size; | |
68 | ||
69 | /* List of nodes in the elimination graph. */ | |
4e3825db | 70 | VEC(int,heap) *nodes; |
6de9cd9a | 71 | |
9cf737f8 | 72 | /* The predecessor and successor edge list. */ |
a9b31c40 | 73 | VEC(int,heap) *edge_list; |
6de9cd9a | 74 | |
f5045c96 AM |
75 | /* Source locus on each edge */ |
76 | VEC(source_location,heap) *edge_locus; | |
77 | ||
6de9cd9a DN |
78 | /* Visited vector. */ |
79 | sbitmap visited; | |
80 | ||
81 | /* Stack for visited nodes. */ | |
1f452424 | 82 | VEC(int,heap) *stack; |
b8698a0f | 83 | |
6de9cd9a DN |
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. */ | |
4e3825db | 91 | VEC(int,heap) *const_dests; |
bf645d6f | 92 | VEC(tree,heap) *const_copies; |
f5045c96 AM |
93 | |
94 | /* Source locations for any constant copies. */ | |
95 | VEC(source_location,heap) *copy_locus; | |
6de9cd9a DN |
96 | } *elim_graph; |
97 | ||
98 | ||
4e3825db MM |
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. */ | |
6de9cd9a | 105 | |
4e3825db MM |
106 | static void |
107 | set_location_for_edge (edge e) | |
6de9cd9a | 108 | { |
4e3825db MM |
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; | |
6de9cd9a | 118 | |
4e3825db MM |
119 | do |
120 | { | |
121 | for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) | |
122 | { | |
123 | gimple stmt = gsi_stmt (gsi); | |
b5b8b0ac AO |
124 | if (is_gimple_debug (stmt)) |
125 | continue; | |
4e3825db MM |
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 | } | |
6de9cd9a | 143 | |
c2172338 MM |
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. */ | |
8e001680 AK |
147 | |
148 | static inline rtx | |
c2172338 | 149 | emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp) |
8e001680 AK |
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); | |
c2172338 MM |
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); | |
8e001680 AK |
164 | |
165 | seq = get_insns (); | |
166 | end_sequence (); | |
167 | ||
168 | return seq; | |
169 | } | |
170 | ||
4e3825db | 171 | /* Insert a copy instruction from partition SRC to DEST onto edge E. */ |
ac3bfd86 | 172 | |
4e3825db | 173 | static void |
9e227d60 | 174 | insert_partition_copy_on_edge (edge e, int dest, int src, source_location locus) |
4e3825db | 175 | { |
c2172338 | 176 | tree var; |
4e3825db MM |
177 | rtx seq; |
178 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
dad2a933 | 179 | { |
4e3825db MM |
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"); | |
dad2a933 | 186 | } |
4e3825db MM |
187 | |
188 | gcc_assert (SA.partition_to_pseudo[dest]); | |
189 | gcc_assert (SA.partition_to_pseudo[src]); | |
190 | ||
191 | set_location_for_edge (e); | |
f5045c96 AM |
192 | /* If a locus is provided, override the default. */ |
193 | if (locus) | |
9e227d60 | 194 | set_curr_insn_source_location (locus); |
4e3825db | 195 | |
c2172338 | 196 | var = partition_to_var (SA.map, src); |
8e001680 AK |
197 | seq = emit_partition_copy (SA.partition_to_pseudo[dest], |
198 | SA.partition_to_pseudo[src], | |
c2172338 MM |
199 | TYPE_UNSIGNED (TREE_TYPE (var)), |
200 | var); | |
4e3825db MM |
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 | |
9e227d60 | 209 | insert_value_copy_on_edge (edge e, int dest, tree src, source_location locus) |
4e3825db MM |
210 | { |
211 | rtx seq, x; | |
8f048d2f RS |
212 | enum machine_mode dest_mode, src_mode; |
213 | int unsignedp; | |
b2a58473 | 214 | tree var; |
8f048d2f | 215 | |
4e3825db | 216 | if (dump_file && (dump_flags & TDF_DETAILS)) |
dad2a933 | 217 | { |
4e3825db MM |
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"); | |
dad2a933 | 224 | } |
6de9cd9a | 225 | |
4e3825db | 226 | gcc_assert (SA.partition_to_pseudo[dest]); |
6de9cd9a | 227 | |
4e3825db | 228 | set_location_for_edge (e); |
f5045c96 AM |
229 | /* If a locus is provided, override the default. */ |
230 | if (locus) | |
9e227d60 | 231 | set_curr_insn_source_location (locus); |
4e3825db MM |
232 | |
233 | start_sequence (); | |
8f048d2f | 234 | |
b2a58473 | 235 | var = SSA_NAME_VAR (partition_to_var (SA.map, dest)); |
8f048d2f | 236 | src_mode = TYPE_MODE (TREE_TYPE (src)); |
b200cc3f | 237 | dest_mode = GET_MODE (SA.partition_to_pseudo[dest]); |
b2a58473 | 238 | gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (var))); |
b200cc3f RG |
239 | gcc_assert (!REG_P (SA.partition_to_pseudo[dest]) |
240 | || dest_mode == promote_decl_mode (var, &unsignedp)); | |
8f048d2f RS |
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 | } | |
c2172338 MM |
247 | else if (src_mode == BLKmode) |
248 | { | |
249 | x = SA.partition_to_pseudo[dest]; | |
250 | store_expr (src, x, 0, false); | |
251 | } | |
8f048d2f RS |
252 | else |
253 | x = expand_expr (src, SA.partition_to_pseudo[dest], | |
254 | dest_mode, EXPAND_NORMAL); | |
255 | ||
4e3825db MM |
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 (); | |
6de9cd9a | 260 | |
4e3825db MM |
261 | insert_insn_on_edge (seq, e); |
262 | } | |
6de9cd9a | 263 | |
4e3825db MM |
264 | /* Insert a copy instruction from RTL expression SRC to partition DEST |
265 | onto edge E. */ | |
6de9cd9a DN |
266 | |
267 | static void | |
f5045c96 | 268 | insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp, |
9e227d60 | 269 | source_location locus) |
6de9cd9a | 270 | { |
4e3825db MM |
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 | } | |
6de9cd9a | 281 | |
4e3825db | 282 | gcc_assert (SA.partition_to_pseudo[dest]); |
f5045c96 | 283 | |
4e3825db | 284 | set_location_for_edge (e); |
f5045c96 AM |
285 | /* If a locus is provided, override the default. */ |
286 | if (locus) | |
9e227d60 | 287 | set_curr_insn_source_location (locus); |
6de9cd9a | 288 | |
c2172338 MM |
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. */ | |
8e001680 | 293 | seq = emit_partition_copy (SA.partition_to_pseudo[dest], |
c2172338 MM |
294 | src, unsignedsrcp, |
295 | partition_to_var (SA.map, dest)); | |
6de9cd9a | 296 | |
4e3825db MM |
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 | |
9e227d60 | 304 | insert_part_to_rtx_on_edge (edge e, rtx dest, int src, source_location locus) |
4e3825db | 305 | { |
c2172338 | 306 | tree var; |
4e3825db | 307 | rtx seq; |
6de9cd9a DN |
308 | if (dump_file && (dump_flags & TDF_DETAILS)) |
309 | { | |
310 | fprintf (dump_file, | |
4e3825db | 311 | "Inserting a temp copy on edge BB%d->BB%d : ", |
6de9cd9a DN |
312 | e->src->index, |
313 | e->dest->index); | |
4e3825db MM |
314 | print_simple_rtl (dump_file, dest); |
315 | fprintf (dump_file, "= PART.%d\n", src); | |
6de9cd9a DN |
316 | } |
317 | ||
4e3825db | 318 | gcc_assert (SA.partition_to_pseudo[src]); |
f5045c96 | 319 | |
4e3825db | 320 | set_location_for_edge (e); |
f5045c96 AM |
321 | /* If a locus is provided, override the default. */ |
322 | if (locus) | |
9e227d60 | 323 | set_curr_insn_source_location (locus); |
4e3825db | 324 | |
c2172338 | 325 | var = partition_to_var (SA.map, src); |
8e001680 AK |
326 | seq = emit_partition_copy (dest, |
327 | SA.partition_to_pseudo[src], | |
c2172338 MM |
328 | TYPE_UNSIGNED (TREE_TYPE (var)), |
329 | var); | |
4e3825db MM |
330 | |
331 | insert_insn_on_edge (seq, e); | |
6de9cd9a DN |
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 | ||
4e3825db MM |
343 | g->nodes = VEC_alloc (int, heap, 30); |
344 | g->const_dests = VEC_alloc (int, heap, 20); | |
bf645d6f | 345 | g->const_copies = VEC_alloc (tree, heap, 20); |
f5045c96 | 346 | g->copy_locus = VEC_alloc (source_location, heap, 10); |
a9b31c40 | 347 | g->edge_list = VEC_alloc (int, heap, 20); |
f5045c96 | 348 | g->edge_locus = VEC_alloc (source_location, heap, 10); |
1f452424 | 349 | g->stack = VEC_alloc (int, heap, 30); |
b8698a0f | 350 | |
6de9cd9a DN |
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 | { | |
4e3825db | 362 | VEC_truncate (int, g->nodes, 0); |
a9b31c40 | 363 | VEC_truncate (int, g->edge_list, 0); |
f5045c96 | 364 | VEC_truncate (source_location, g->edge_locus, 0); |
6de9cd9a DN |
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); | |
1f452424 | 374 | VEC_free (int, heap, g->stack); |
a9b31c40 | 375 | VEC_free (int, heap, g->edge_list); |
bf645d6f | 376 | VEC_free (tree, heap, g->const_copies); |
4e3825db MM |
377 | VEC_free (int, heap, g->const_dests); |
378 | VEC_free (int, heap, g->nodes); | |
f5045c96 AM |
379 | VEC_free (source_location, heap, g->copy_locus); |
380 | VEC_free (source_location, heap, g->edge_locus); | |
381 | ||
6de9cd9a DN |
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 | { | |
4e3825db | 391 | return VEC_length (int, g->nodes); |
6de9cd9a DN |
392 | } |
393 | ||
394 | ||
395 | /* Add NODE to graph G, if it doesn't exist already. */ | |
396 | ||
b8698a0f | 397 | static inline void |
4e3825db | 398 | elim_graph_add_node (elim_graph g, int node) |
6de9cd9a DN |
399 | { |
400 | int x; | |
4e3825db | 401 | int t; |
bf645d6f | 402 | |
ac47786e | 403 | FOR_EACH_VEC_ELT (int, g->nodes, x, t) |
bf645d6f | 404 | if (t == node) |
6de9cd9a | 405 | return; |
4e3825db | 406 | VEC_safe_push (int, heap, g->nodes, node); |
6de9cd9a DN |
407 | } |
408 | ||
409 | ||
410 | /* Add the edge PRED->SUCC to graph G. */ | |
411 | ||
412 | static inline void | |
9e227d60 | 413 | elim_graph_add_edge (elim_graph g, int pred, int succ, source_location locus) |
6de9cd9a | 414 | { |
a9b31c40 KH |
415 | VEC_safe_push (int, heap, g->edge_list, pred); |
416 | VEC_safe_push (int, heap, g->edge_list, succ); | |
f5045c96 | 417 | VEC_safe_push (source_location, heap, g->edge_locus, locus); |
6de9cd9a DN |
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 | |
9e227d60 | 425 | elim_graph_remove_succ_edge (elim_graph g, int node, source_location *locus) |
6de9cd9a DN |
426 | { |
427 | int y; | |
428 | unsigned x; | |
a9b31c40 KH |
429 | for (x = 0; x < VEC_length (int, g->edge_list); x += 2) |
430 | if (VEC_index (int, g->edge_list, x) == node) | |
6de9cd9a | 431 | { |
a9b31c40 KH |
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); | |
f5045c96 AM |
435 | *locus = VEC_index (source_location, g->edge_locus, x / 2); |
436 | VEC_replace (source_location, g->edge_locus, x / 2, UNKNOWN_LOCATION); | |
6de9cd9a DN |
437 | return y; |
438 | } | |
f5045c96 | 439 | *locus = UNKNOWN_LOCATION; |
6de9cd9a DN |
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 | ||
9e227d60 | 448 | #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \ |
6de9cd9a DN |
449 | do { \ |
450 | unsigned x_; \ | |
451 | int y_; \ | |
a9b31c40 | 452 | for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \ |
6de9cd9a | 453 | { \ |
a9b31c40 | 454 | y_ = VEC_index (int, (GRAPH)->edge_list, x_); \ |
6de9cd9a DN |
455 | if (y_ != (NODE)) \ |
456 | continue; \ | |
60d3aec4 JJ |
457 | (void) ((VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1)); \ |
458 | (void) ((LOCUS) = VEC_index (source_location, \ | |
459 | (GRAPH)->edge_locus, x_ / 2)); \ | |
6de9cd9a DN |
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 | ||
9e227d60 | 469 | #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \ |
6de9cd9a DN |
470 | do { \ |
471 | unsigned x_; \ | |
472 | int y_; \ | |
a9b31c40 | 473 | for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \ |
6de9cd9a | 474 | { \ |
a9b31c40 | 475 | y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \ |
6de9cd9a DN |
476 | if (y_ != (NODE)) \ |
477 | continue; \ | |
60d3aec4 JJ |
478 | (void) ((VAR) = VEC_index (int, (GRAPH)->edge_list, x_)); \ |
479 | (void) ((LOCUS) = VEC_index (source_location, \ | |
480 | (GRAPH)->edge_locus, x_ / 2)); \ | |
6de9cd9a DN |
481 | CODE; \ |
482 | } \ | |
483 | } while (0) | |
484 | ||
485 | ||
486 | /* Add T to elimination graph G. */ | |
487 | ||
488 | static inline void | |
4e3825db | 489 | eliminate_name (elim_graph g, int T) |
6de9cd9a DN |
490 | { |
491 | elim_graph_add_node (g, T); | |
492 | } | |
493 | ||
494 | ||
41f683ef KH |
495 | /* Build elimination graph G for basic block BB on incoming PHI edge |
496 | G->e. */ | |
6de9cd9a DN |
497 | |
498 | static void | |
4e3825db | 499 | eliminate_build (elim_graph g) |
6de9cd9a | 500 | { |
4e3825db | 501 | tree Ti; |
6de9cd9a | 502 | int p0, pi; |
726a989a | 503 | gimple_stmt_iterator gsi; |
6de9cd9a DN |
504 | |
505 | clear_elim_graph (g); | |
b8698a0f | 506 | |
4e3825db | 507 | for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
6de9cd9a | 508 | { |
726a989a | 509 | gimple phi = gsi_stmt (gsi); |
f5045c96 | 510 | source_location locus; |
726a989a | 511 | |
4e3825db | 512 | p0 = var_to_partition (g->map, gimple_phi_result (phi)); |
6de9cd9a | 513 | /* Ignore results which are not in partitions. */ |
4e3825db | 514 | if (p0 == NO_PARTITION) |
6de9cd9a DN |
515 | continue; |
516 | ||
41f683ef | 517 | Ti = PHI_ARG_DEF (phi, g->e->dest_idx); |
f5045c96 | 518 | locus = gimple_phi_arg_location_from_edge (phi, g->e); |
6de9cd9a DN |
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. */ | |
4e3825db | 529 | VEC_safe_push (int, heap, g->const_dests, p0); |
bf645d6f | 530 | VEC_safe_push (tree, heap, g->const_copies, Ti); |
f5045c96 | 531 | VEC_safe_push (source_location, heap, g->copy_locus, locus); |
6de9cd9a DN |
532 | } |
533 | else | |
534 | { | |
4e3825db MM |
535 | pi = var_to_partition (g->map, Ti); |
536 | if (p0 != pi) | |
6de9cd9a | 537 | { |
4e3825db MM |
538 | eliminate_name (g, p0); |
539 | eliminate_name (g, pi); | |
9e227d60 | 540 | elim_graph_add_edge (g, p0, pi, locus); |
6de9cd9a DN |
541 | } |
542 | } | |
543 | } | |
544 | } | |
545 | ||
546 | ||
547 | /* Push successors of T onto the elimination stack for G. */ | |
548 | ||
b8698a0f | 549 | static void |
6de9cd9a DN |
550 | elim_forward (elim_graph g, int T) |
551 | { | |
552 | int S; | |
f5045c96 AM |
553 | source_location locus; |
554 | ||
6de9cd9a | 555 | SET_BIT (g->visited, T); |
9e227d60 | 556 | FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus, |
6de9cd9a DN |
557 | { |
558 | if (!TEST_BIT (g->visited, S)) | |
559 | elim_forward (g, S); | |
560 | }); | |
1f452424 | 561 | VEC_safe_push (int, heap, g->stack, T); |
6de9cd9a DN |
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; | |
f5045c96 AM |
571 | source_location locus; |
572 | ||
9e227d60 | 573 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, |
6de9cd9a DN |
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; | |
f5045c96 AM |
587 | source_location locus; |
588 | ||
6de9cd9a | 589 | SET_BIT (g->visited, T); |
9e227d60 | 590 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, |
6de9cd9a DN |
591 | { |
592 | if (!TEST_BIT (g->visited, P)) | |
593 | { | |
594 | elim_backward (g, P); | |
9e227d60 | 595 | insert_partition_copy_on_edge (g->e, P, T, locus); |
6de9cd9a DN |
596 | } |
597 | }); | |
598 | } | |
599 | ||
4e3825db MM |
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); | |
cde0f3fd PB |
608 | int unsignedp; |
609 | enum machine_mode reg_mode = promote_decl_mode (var, &unsignedp); | |
4e3825db MM |
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 | ||
b8698a0f | 616 | /* Insert required copies for T in graph G. Check for a strongly connected |
6de9cd9a DN |
617 | region, and create a temporary to break the cycle if one is found. */ |
618 | ||
b8698a0f | 619 | static void |
6de9cd9a DN |
620 | elim_create (elim_graph g, int T) |
621 | { | |
6de9cd9a | 622 | int P, S; |
f5045c96 | 623 | source_location locus; |
6de9cd9a DN |
624 | |
625 | if (elim_unvisited_predecessor (g, T)) | |
626 | { | |
8e001680 AK |
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 | ||
9e227d60 DC |
631 | insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION); |
632 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, | |
6de9cd9a DN |
633 | { |
634 | if (!TEST_BIT (g->visited, P)) | |
635 | { | |
636 | elim_backward (g, P); | |
9e227d60 | 637 | insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus); |
6de9cd9a DN |
638 | } |
639 | }); | |
640 | } | |
641 | else | |
642 | { | |
9e227d60 | 643 | S = elim_graph_remove_succ_edge (g, T, &locus); |
6de9cd9a DN |
644 | if (S != -1) |
645 | { | |
646 | SET_BIT (g->visited, T); | |
9e227d60 | 647 | insert_partition_copy_on_edge (g->e, T, S, locus); |
6de9cd9a DN |
648 | } |
649 | } | |
6de9cd9a DN |
650 | } |
651 | ||
7290d709 | 652 | |
41f683ef | 653 | /* Eliminate all the phi nodes on edge E in graph G. */ |
6de9cd9a DN |
654 | |
655 | static void | |
41f683ef | 656 | eliminate_phi (edge e, elim_graph g) |
6de9cd9a | 657 | { |
6de9cd9a | 658 | int x; |
6de9cd9a | 659 | |
bf645d6f | 660 | gcc_assert (VEC_length (tree, g->const_copies) == 0); |
f5045c96 | 661 | gcc_assert (VEC_length (source_location, g->copy_locus) == 0); |
6de9cd9a | 662 | |
0e61db61 | 663 | /* Abnormal edges already have everything coalesced. */ |
6de9cd9a DN |
664 | if (e->flags & EDGE_ABNORMAL) |
665 | return; | |
666 | ||
6de9cd9a DN |
667 | g->e = e; |
668 | ||
4e3825db | 669 | eliminate_build (g); |
6de9cd9a DN |
670 | |
671 | if (elim_graph_size (g) != 0) | |
672 | { | |
4e3825db | 673 | int part; |
bf645d6f | 674 | |
6de9cd9a | 675 | sbitmap_zero (g->visited); |
1f452424 | 676 | VEC_truncate (int, g->stack, 0); |
6de9cd9a | 677 | |
ac47786e | 678 | FOR_EACH_VEC_ELT (int, g->nodes, x, part) |
6de9cd9a | 679 | { |
4e3825db MM |
680 | if (!TEST_BIT (g->visited, part)) |
681 | elim_forward (g, part); | |
6de9cd9a | 682 | } |
b8698a0f | 683 | |
6de9cd9a | 684 | sbitmap_zero (g->visited); |
1f452424 | 685 | while (VEC_length (int, g->stack) > 0) |
6de9cd9a | 686 | { |
1f452424 | 687 | x = VEC_pop (int, g->stack); |
6de9cd9a DN |
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. */ | |
bf645d6f | 694 | while (VEC_length (tree, g->const_copies) > 0) |
6de9cd9a | 695 | { |
4e3825db MM |
696 | int dest; |
697 | tree src; | |
f5045c96 AM |
698 | source_location locus; |
699 | ||
bf645d6f | 700 | src = VEC_pop (tree, g->const_copies); |
4e3825db | 701 | dest = VEC_pop (int, g->const_dests); |
f5045c96 | 702 | locus = VEC_pop (source_location, g->copy_locus); |
9e227d60 | 703 | insert_value_copy_on_edge (e, dest, src, locus); |
6de9cd9a DN |
704 | } |
705 | } | |
706 | ||
707 | ||
b8698a0f | 708 | /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME, |
ffd327a7 | 709 | check to see if this allows another PHI node to be removed. */ |
6de9cd9a DN |
710 | |
711 | static void | |
ffd327a7 AM |
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) | |
6de9cd9a DN |
754 | { |
755 | basic_block bb; | |
726a989a | 756 | gimple_stmt_iterator gsi; |
ffd327a7 | 757 | tree result; |
6de9cd9a DN |
758 | |
759 | FOR_EACH_BB (bb) | |
760 | { | |
726a989a | 761 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); ) |
6de9cd9a | 762 | { |
726a989a | 763 | gimple phi = gsi_stmt (gsi); |
ffd327a7 | 764 | result = gimple_phi_result (phi); |
ea057359 | 765 | if (virtual_operand_p (result)) |
6de9cd9a DN |
766 | { |
767 | #ifdef ENABLE_CHECKING | |
726a989a | 768 | size_t i; |
4b756989 AM |
769 | /* There should be no arguments which are not virtual, or the |
770 | results will be incorrect. */ | |
726a989a | 771 | for (i = 0; i < gimple_phi_num_args (phi); i++) |
6de9cd9a DN |
772 | { |
773 | tree arg = PHI_ARG_DEF (phi, i); | |
b8698a0f | 774 | if (TREE_CODE (arg) == SSA_NAME |
ea057359 | 775 | && !virtual_operand_p (arg)) |
6de9cd9a DN |
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 :"); | |
726a989a | 780 | print_gimple_stmt (stderr, phi, 0, TDF_SLIM); |
1e128c5f | 781 | internal_error ("SSA corruption"); |
6de9cd9a DN |
782 | } |
783 | } | |
784 | #endif | |
726a989a | 785 | remove_phi_node (&gsi, true); |
6de9cd9a | 786 | } |
726a989a | 787 | else |
ffd327a7 AM |
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 | } | |
6de9cd9a DN |
798 | } |
799 | } | |
800 | } | |
801 | ||
802 | ||
6de9cd9a | 803 | /* This function will rewrite the current program using the variable mapping |
b8698a0f L |
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 | |
6de9cd9a DN |
807 | variable. */ |
808 | ||
809 | static void | |
1fec7ed4 | 810 | rewrite_trees (var_map map ATTRIBUTE_UNUSED) |
6de9cd9a | 811 | { |
6de9cd9a | 812 | #ifdef ENABLE_CHECKING |
4e3825db | 813 | basic_block bb; |
6de9cd9a DN |
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 | { | |
4e3825db | 819 | gimple_stmt_iterator gsi; |
726a989a | 820 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
6de9cd9a | 821 | { |
726a989a RB |
822 | gimple phi = gsi_stmt (gsi); |
823 | tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi)); | |
6de9cd9a DN |
824 | if (T0 == NULL_TREE) |
825 | { | |
726a989a RB |
826 | size_t i; |
827 | for (i = 0; i < gimple_phi_num_args (phi); i++) | |
6de9cd9a DN |
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 :"); | |
726a989a | 837 | print_gimple_stmt (stderr, phi, 0, TDF_SLIM); |
1e128c5f | 838 | internal_error ("SSA corruption"); |
6de9cd9a DN |
839 | } |
840 | } | |
841 | } | |
842 | } | |
843 | } | |
844 | #endif | |
edfaf675 AM |
845 | } |
846 | ||
4e3825db MM |
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. */ | |
edfaf675 | 851 | |
4e3825db MM |
852 | void |
853 | expand_phi_nodes (struct ssaexpand *sa) | |
edfaf675 AM |
854 | { |
855 | basic_block bb; | |
4e3825db MM |
856 | elim_graph g = new_elim_graph (sa->map->num_partitions); |
857 | g->map = sa->map; | |
edfaf675 | 858 | |
4e3825db MM |
859 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb) |
860 | if (!gimple_seq_empty_p (phi_nodes (bb))) | |
edfaf675 | 861 | { |
4e3825db MM |
862 | edge e; |
863 | edge_iterator ei; | |
edfaf675 | 864 | FOR_EACH_EDGE (e, ei, bb->preds) |
4e3825db MM |
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)); ) | |
edfaf675 | 877 | { |
4e3825db MM |
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); | |
edfaf675 | 889 | } |
edfaf675 | 890 | } |
4e3825db MM |
891 | |
892 | delete_elim_graph (g); | |
6de9cd9a DN |
893 | } |
894 | ||
895 | ||
7290d709 AM |
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. */ | |
6de9cd9a | 899 | |
56b043c8 | 900 | static void |
4e3825db | 901 | remove_ssa_form (bool perform_ter, struct ssaexpand *sa) |
6de9cd9a | 902 | { |
e97809c6 | 903 | bitmap values = NULL; |
7290d709 | 904 | var_map map; |
4e3825db | 905 | unsigned i; |
6de9cd9a | 906 | |
7290d709 | 907 | map = coalesce_ssa_name (); |
6de9cd9a | 908 | |
7290d709 AM |
909 | /* Return to viewing the variable list as just all reference variables after |
910 | coalescing has been performed. */ | |
911 | partition_view_normal (map, false); | |
6de9cd9a DN |
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 | ||
7290d709 | 919 | if (perform_ter) |
6de9cd9a DN |
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 | ||
4e3825db | 926 | rewrite_trees (map); |
6de9cd9a | 927 | |
4e3825db MM |
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++) | |
6de9cd9a | 932 | { |
4e3825db MM |
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 | } | |
6de9cd9a | 940 | } |
6de9cd9a DN |
941 | } |
942 | ||
7290d709 | 943 | |
ce985b43 MM |
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; | |
b8698a0f | 952 | |
ce985b43 MM |
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); | |
d6600130 JJ |
984 | if (is_gimple_debug (use_stmt)) |
985 | continue; | |
ce985b43 MM |
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 | } | |
b8698a0f | 1002 | |
ce985b43 MM |
1003 | return false; |
1004 | } | |
1005 | ||
1006 | ||
06170e1d JL |
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; | |
726a989a | 1020 | gimple_stmt_iterator gsi; |
06170e1d | 1021 | |
f2521653 BS |
1022 | mark_dfs_back_edges (); |
1023 | ||
06170e1d JL |
1024 | FOR_EACH_BB (bb) |
1025 | { | |
ce985b43 MM |
1026 | /* Mark block as possibly needing calculation of UIDs. */ |
1027 | bb->aux = &bb->aux; | |
1028 | ||
726a989a | 1029 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
06170e1d | 1030 | { |
726a989a RB |
1031 | gimple phi = gsi_stmt (gsi); |
1032 | tree result = gimple_phi_result (phi); | |
726a989a | 1033 | size_t i; |
06170e1d | 1034 | |
ea057359 | 1035 | if (virtual_operand_p (result)) |
06170e1d JL |
1036 | continue; |
1037 | ||
726a989a | 1038 | for (i = 0; i < gimple_phi_num_args (phi); i++) |
06170e1d | 1039 | { |
726a989a RB |
1040 | tree arg = gimple_phi_arg_def (phi, i); |
1041 | edge e = gimple_phi_arg_edge (phi, i); | |
06170e1d | 1042 | |
b8698a0f | 1043 | /* If the argument is not an SSA_NAME, then we will need a |
7290d709 | 1044 | constant initialization. If the argument is an SSA_NAME with |
b8698a0f | 1045 | a different underlying variable then a copy statement will be |
7290d709 | 1046 | needed. */ |
06170e1d JL |
1047 | if ((e->flags & EDGE_DFS_BACK) |
1048 | && (TREE_CODE (arg) != SSA_NAME | |
6b4a85ad | 1049 | || SSA_NAME_VAR (arg) != SSA_NAME_VAR (result) |
ce985b43 | 1050 | || trivially_conflicts_p (bb, result, arg))) |
06170e1d | 1051 | { |
726a989a RB |
1052 | tree name; |
1053 | gimple stmt, last = NULL; | |
1054 | gimple_stmt_iterator gsi2; | |
06170e1d | 1055 | |
726a989a RB |
1056 | gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src); |
1057 | if (!gsi_end_p (gsi2)) | |
1058 | last = gsi_stmt (gsi2); | |
06170e1d JL |
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. | |
b8698a0f | 1062 | However, better safe than sorry. |
35fd3193 | 1063 | If the block ends with a control statement or |
06170e1d JL |
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 | ||
b8698a0f | 1077 | /* Create a new instance of the underlying variable of the |
7290d709 | 1078 | PHI result. */ |
6b4a85ad RG |
1079 | name = copy_ssa_name (result, NULL); |
1080 | stmt = gimple_build_assign (name, | |
726a989a | 1081 | gimple_phi_arg_def (phi, i)); |
06170e1d | 1082 | |
f5045c96 AM |
1083 | /* copy location if present. */ |
1084 | if (gimple_phi_arg_has_location (phi, i)) | |
9e227d60 DC |
1085 | gimple_set_location (stmt, |
1086 | gimple_phi_arg_location (phi, i)); | |
f5045c96 | 1087 | |
06170e1d JL |
1088 | /* Insert the new statement into the block and update |
1089 | the PHI node. */ | |
1090 | if (last && stmt_ends_bb_p (last)) | |
726a989a | 1091 | gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT); |
06170e1d | 1092 | else |
726a989a | 1093 | gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT); |
06170e1d JL |
1094 | SET_PHI_ARG_DEF (phi, i, name); |
1095 | } | |
1096 | } | |
1097 | } | |
ce985b43 MM |
1098 | |
1099 | /* Unmark this block again. */ | |
1100 | bb->aux = NULL; | |
06170e1d JL |
1101 | } |
1102 | } | |
1103 | ||
4e3825db MM |
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) | |
e97809c6 | 1112 | BITMAP_FREE (sa->values); |
4e3825db MM |
1113 | delete_var_map (sa->map); |
1114 | BITMAP_FREE (sa->partition_has_default_def); | |
1115 | memset (sa, 0, sizeof *sa); | |
1116 | } | |
1117 | ||
7290d709 | 1118 | /* Take the current function out of SSA form, translating PHIs as described in |
6de9cd9a DN |
1119 | R. Morgan, ``Building an Optimizing Compiler'', |
1120 | Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */ | |
1121 | ||
4e3825db MM |
1122 | unsigned int |
1123 | rewrite_out_of_ssa (struct ssaexpand *sa) | |
6de9cd9a | 1124 | { |
06170e1d JL |
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 | ||
ffd327a7 AM |
1133 | |
1134 | /* Eliminate PHIs which are of no use, such as virtual or dead phis. */ | |
1135 | eliminate_useless_phis (); | |
6de9cd9a DN |
1136 | |
1137 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
726a989a | 1138 | gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); |
6de9cd9a | 1139 | |
4e3825db | 1140 | remove_ssa_form (flag_tree_ter, sa); |
6de9cd9a DN |
1141 | |
1142 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
726a989a | 1143 | gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); |
6de9cd9a | 1144 | |
c2924966 | 1145 | return 0; |
6de9cd9a | 1146 | } |