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