]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Convert a program in SSA form into Normal form. |
8d9254fc | 2 | Copyright (C) 2004-2020 Free Software Foundation, Inc. |
6de9cd9a DN |
3 | Contributed by Andrew Macleod <amacleod@redhat.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
10 | any later version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
c7131fb2 | 24 | #include "backend.h" |
957060b5 | 25 | #include "rtl.h" |
6de9cd9a | 26 | #include "tree.h" |
c7131fb2 | 27 | #include "gimple.h" |
957060b5 | 28 | #include "cfghooks.h" |
c7131fb2 | 29 | #include "ssa.h" |
e3bfa377 | 30 | #include "tree-ssa.h" |
4d0cdd0c | 31 | #include "memmodel.h" |
957060b5 AM |
32 | #include "emit-rtl.h" |
33 | #include "gimple-pretty-print.h" | |
34 | #include "diagnostic-core.h" | |
e3bfa377 | 35 | #include "tree-dfa.h" |
d8a2d370 | 36 | #include "stor-layout.h" |
60393bbc AM |
37 | #include "cfgrtl.h" |
38 | #include "cfganal.h" | |
2fb9a547 | 39 | #include "tree-eh.h" |
5be5c238 | 40 | #include "gimple-iterator.h" |
442b4905 | 41 | #include "tree-cfg.h" |
7ee2468b | 42 | #include "dumpfile.h" |
8e9055ae AM |
43 | #include "tree-ssa-live.h" |
44 | #include "tree-ssa-ter.h" | |
45 | #include "tree-ssa-coalesce.h" | |
78bca40d | 46 | #include "tree-outof-ssa.h" |
5edb9853 | 47 | #include "dojump.h" |
6de9cd9a | 48 | |
2eb79bbb SB |
49 | /* FIXME: A lot of code here deals with expanding to RTL. All that code |
50 | should be in cfgexpand.c. */ | |
36566b39 | 51 | #include "explow.h" |
2eb79bbb SB |
52 | #include "expr.h" |
53 | ||
78bca40d AM |
54 | /* Return TRUE if expression STMT is suitable for replacement. */ |
55 | ||
56 | bool | |
355fe088 | 57 | ssa_is_replaceable_p (gimple *stmt) |
78bca40d AM |
58 | { |
59 | use_operand_p use_p; | |
60 | tree def; | |
355fe088 | 61 | gimple *use_stmt; |
78bca40d AM |
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. */ | |
36bbc05d | 68 | if (stmt_could_throw_p (cfun, stmt)) |
78bca40d AM |
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 | } | |
56b043c8 | 109 | |
f5045c96 | 110 | |
6de9cd9a DN |
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 | |
b8698a0f L |
116 | [0] ->PRED, [1]->SUCC. All the even indexes in the array represent |
117 | predecessors, all the odd elements are successors. | |
118 | ||
6de9cd9a | 119 | Rationale: |
b8698a0f | 120 | When implemented as bitmaps, very large programs SSA->Normal times were |
6de9cd9a DN |
121 | being dominated by clearing the interference graph. |
122 | ||
b8698a0f L |
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 | |
6de9cd9a DN |
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. */ | |
b8698a0f | 131 | |
6c1dae73 | 132 | class elim_graph |
c8b1ebd9 | 133 | { |
6c1dae73 | 134 | public: |
61801db9 TS |
135 | elim_graph (var_map map); |
136 | ||
6de9cd9a DN |
137 | /* Size of the elimination vectors. */ |
138 | int size; | |
139 | ||
140 | /* List of nodes in the elimination graph. */ | |
61801db9 | 141 | auto_vec<int> nodes; |
6de9cd9a | 142 | |
9cf737f8 | 143 | /* The predecessor and successor edge list. */ |
61801db9 | 144 | auto_vec<int> edge_list; |
6de9cd9a | 145 | |
f5045c96 | 146 | /* Source locus on each edge */ |
620e594b | 147 | auto_vec<location_t> edge_locus; |
f5045c96 | 148 | |
6de9cd9a | 149 | /* Visited vector. */ |
61801db9 | 150 | auto_sbitmap visited; |
6de9cd9a DN |
151 | |
152 | /* Stack for visited nodes. */ | |
61801db9 | 153 | auto_vec<int> stack; |
b8698a0f | 154 | |
6de9cd9a DN |
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. */ | |
61801db9 TS |
162 | auto_vec<int> const_dests; |
163 | auto_vec<tree> const_copies; | |
f5045c96 AM |
164 | |
165 | /* Source locations for any constant copies. */ | |
620e594b | 166 | auto_vec<location_t> copy_locus; |
c8b1ebd9 | 167 | }; |
6de9cd9a DN |
168 | |
169 | ||
4e3825db MM |
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 | |
4500f751 EB |
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. */ | |
6de9cd9a | 180 | |
4e3825db MM |
181 | static void |
182 | set_location_for_edge (edge e) | |
6de9cd9a | 183 | { |
4e3825db | 184 | if (e->goto_locus) |
4500f751 EB |
185 | set_curr_insn_location (e->goto_locus); |
186 | else if (e->flags & EDGE_EH) | |
4e3825db | 187 | { |
4500f751 EB |
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); | |
4e3825db MM |
212 | } |
213 | else | |
214 | { | |
215 | basic_block bb = e->src; | |
216 | gimple_stmt_iterator gsi; | |
6de9cd9a | 217 | |
4e3825db MM |
218 | do |
219 | { | |
220 | for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) | |
221 | { | |
355fe088 | 222 | gimple *stmt = gsi_stmt (gsi); |
b5b8b0ac AO |
223 | if (is_gimple_debug (stmt)) |
224 | continue; | |
4e3825db MM |
225 | if (gimple_has_location (stmt) || gimple_block (stmt)) |
226 | { | |
5368224f | 227 | set_curr_insn_location (gimple_location (stmt)); |
4e3825db MM |
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 | } | |
6de9cd9a | 241 | |
c2172338 MM |
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. */ | |
8e001680 | 245 | |
ec0c6743 | 246 | static inline rtx_insn * |
c2172338 | 247 | emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp) |
8e001680 | 248 | { |
8e001680 AK |
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); | |
c2172338 MM |
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); | |
5edb9853 | 260 | do_pending_stack_adjust (); |
8e001680 | 261 | |
ec0c6743 | 262 | rtx_insn *seq = get_insns (); |
8e001680 AK |
263 | end_sequence (); |
264 | ||
265 | return seq; | |
266 | } | |
267 | ||
4e3825db | 268 | /* Insert a copy instruction from partition SRC to DEST onto edge E. */ |
ac3bfd86 | 269 | |
4e3825db | 270 | static void |
620e594b | 271 | insert_partition_copy_on_edge (edge e, int dest, int src, location_t locus) |
4e3825db | 272 | { |
c2172338 | 273 | tree var; |
4e3825db | 274 | if (dump_file && (dump_flags & TDF_DETAILS)) |
dad2a933 | 275 | { |
4e3825db | 276 | fprintf (dump_file, |
aa326bfb | 277 | "Inserting a partition copy on edge BB%d->BB%d : " |
4e3825db MM |
278 | "PART.%d = PART.%d", |
279 | e->src->index, | |
280 | e->dest->index, dest, src); | |
281 | fprintf (dump_file, "\n"); | |
dad2a933 | 282 | } |
4e3825db MM |
283 | |
284 | gcc_assert (SA.partition_to_pseudo[dest]); | |
285 | gcc_assert (SA.partition_to_pseudo[src]); | |
286 | ||
287 | set_location_for_edge (e); | |
f5045c96 AM |
288 | /* If a locus is provided, override the default. */ |
289 | if (locus) | |
5368224f | 290 | set_curr_insn_location (locus); |
4e3825db | 291 | |
c2172338 | 292 | var = partition_to_var (SA.map, src); |
ec0c6743 TS |
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); | |
4e3825db MM |
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 | |
620e594b | 305 | insert_value_copy_on_edge (edge e, int dest, tree src, location_t locus) |
4e3825db | 306 | { |
02b278a8 | 307 | rtx dest_rtx, seq, x; |
ef4bddc2 | 308 | machine_mode dest_mode, src_mode; |
8f048d2f RS |
309 | int unsignedp; |
310 | ||
4e3825db | 311 | if (dump_file && (dump_flags & TDF_DETAILS)) |
dad2a933 | 312 | { |
4e3825db MM |
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"); | |
dad2a933 | 319 | } |
6de9cd9a | 320 | |
02b278a8 RS |
321 | dest_rtx = copy_rtx (SA.partition_to_pseudo[dest]); |
322 | gcc_assert (dest_rtx); | |
6de9cd9a | 323 | |
4e3825db | 324 | set_location_for_edge (e); |
f5045c96 AM |
325 | /* If a locus is provided, override the default. */ |
326 | if (locus) | |
5368224f | 327 | set_curr_insn_location (locus); |
4e3825db MM |
328 | |
329 | start_sequence (); | |
8f048d2f | 330 | |
1f9ceff1 | 331 | tree name = partition_to_var (SA.map, dest); |
8f048d2f | 332 | src_mode = TYPE_MODE (TREE_TYPE (src)); |
02b278a8 | 333 | dest_mode = GET_MODE (dest_rtx); |
1f9ceff1 | 334 | gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (name))); |
02b278a8 | 335 | gcc_assert (!REG_P (dest_rtx) |
1f9ceff1 | 336 | || dest_mode == promote_ssa_mode (name, &unsignedp)); |
8f048d2f RS |
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 | } | |
c2172338 MM |
343 | else if (src_mode == BLKmode) |
344 | { | |
02b278a8 | 345 | x = dest_rtx; |
ee45a32d | 346 | store_expr (src, x, 0, false, false); |
c2172338 | 347 | } |
8f048d2f | 348 | else |
02b278a8 | 349 | x = expand_expr (src, dest_rtx, dest_mode, EXPAND_NORMAL); |
8f048d2f | 350 | |
02b278a8 RS |
351 | if (x != dest_rtx) |
352 | emit_move_insn (dest_rtx, x); | |
5edb9853 RH |
353 | do_pending_stack_adjust (); |
354 | ||
4e3825db MM |
355 | seq = get_insns (); |
356 | end_sequence (); | |
6de9cd9a | 357 | |
4e3825db MM |
358 | insert_insn_on_edge (seq, e); |
359 | } | |
6de9cd9a | 360 | |
4e3825db MM |
361 | /* Insert a copy instruction from RTL expression SRC to partition DEST |
362 | onto edge E. */ | |
6de9cd9a DN |
363 | |
364 | static void | |
f5045c96 | 365 | insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp, |
620e594b | 366 | location_t locus) |
6de9cd9a | 367 | { |
4e3825db MM |
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 | } | |
6de9cd9a | 377 | |
4e3825db | 378 | gcc_assert (SA.partition_to_pseudo[dest]); |
f5045c96 | 379 | |
4e3825db | 380 | set_location_for_edge (e); |
f5045c96 AM |
381 | /* If a locus is provided, override the default. */ |
382 | if (locus) | |
5368224f | 383 | set_curr_insn_location (locus); |
6de9cd9a | 384 | |
c2172338 MM |
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. */ | |
ec0c6743 TS |
389 | rtx_insn *seq = emit_partition_copy (copy_rtx (SA.partition_to_pseudo[dest]), |
390 | src, unsignedsrcp, | |
391 | partition_to_var (SA.map, dest)); | |
6de9cd9a | 392 | |
4e3825db MM |
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 | |
620e594b | 400 | insert_part_to_rtx_on_edge (edge e, rtx dest, int src, location_t locus) |
4e3825db | 401 | { |
c2172338 | 402 | tree var; |
6de9cd9a DN |
403 | if (dump_file && (dump_flags & TDF_DETAILS)) |
404 | { | |
405 | fprintf (dump_file, | |
4e3825db | 406 | "Inserting a temp copy on edge BB%d->BB%d : ", |
6de9cd9a DN |
407 | e->src->index, |
408 | e->dest->index); | |
4e3825db MM |
409 | print_simple_rtl (dump_file, dest); |
410 | fprintf (dump_file, "= PART.%d\n", src); | |
6de9cd9a DN |
411 | } |
412 | ||
4e3825db | 413 | gcc_assert (SA.partition_to_pseudo[src]); |
f5045c96 | 414 | |
4e3825db | 415 | set_location_for_edge (e); |
f5045c96 AM |
416 | /* If a locus is provided, override the default. */ |
417 | if (locus) | |
5368224f | 418 | set_curr_insn_location (locus); |
4e3825db | 419 | |
c2172338 | 420 | var = partition_to_var (SA.map, src); |
ec0c6743 TS |
421 | rtx_insn *seq = emit_partition_copy (dest, |
422 | copy_rtx (SA.partition_to_pseudo[src]), | |
423 | TYPE_UNSIGNED (TREE_TYPE (var)), | |
424 | var); | |
4e3825db MM |
425 | |
426 | insert_insn_on_edge (seq, e); | |
6de9cd9a DN |
427 | } |
428 | ||
429 | ||
61801db9 | 430 | /* Create an elimination graph for map. */ |
6de9cd9a | 431 | |
61801db9 TS |
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) | |
6de9cd9a | 435 | { |
6de9cd9a DN |
436 | } |
437 | ||
438 | ||
439 | /* Empty elimination graph G. */ | |
440 | ||
441 | static inline void | |
c8b1ebd9 | 442 | clear_elim_graph (elim_graph *g) |
6de9cd9a | 443 | { |
9771b263 DN |
444 | g->nodes.truncate (0); |
445 | g->edge_list.truncate (0); | |
446 | g->edge_locus.truncate (0); | |
6de9cd9a DN |
447 | } |
448 | ||
449 | ||
6de9cd9a DN |
450 | /* Return the number of nodes in graph G. */ |
451 | ||
452 | static inline int | |
c8b1ebd9 | 453 | elim_graph_size (elim_graph *g) |
6de9cd9a | 454 | { |
9771b263 | 455 | return g->nodes.length (); |
6de9cd9a DN |
456 | } |
457 | ||
458 | ||
459 | /* Add NODE to graph G, if it doesn't exist already. */ | |
460 | ||
b8698a0f | 461 | static inline void |
c8b1ebd9 | 462 | elim_graph_add_node (elim_graph *g, int node) |
6de9cd9a DN |
463 | { |
464 | int x; | |
4e3825db | 465 | int t; |
bf645d6f | 466 | |
9771b263 | 467 | FOR_EACH_VEC_ELT (g->nodes, x, t) |
bf645d6f | 468 | if (t == node) |
6de9cd9a | 469 | return; |
9771b263 | 470 | g->nodes.safe_push (node); |
6de9cd9a DN |
471 | } |
472 | ||
473 | ||
474 | /* Add the edge PRED->SUCC to graph G. */ | |
475 | ||
476 | static inline void | |
620e594b | 477 | elim_graph_add_edge (elim_graph *g, int pred, int succ, location_t locus) |
6de9cd9a | 478 | { |
9771b263 DN |
479 | g->edge_list.safe_push (pred); |
480 | g->edge_list.safe_push (succ); | |
481 | g->edge_locus.safe_push (locus); | |
6de9cd9a DN |
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 | |
620e594b | 489 | elim_graph_remove_succ_edge (elim_graph *g, int node, location_t *locus) |
6de9cd9a DN |
490 | { |
491 | int y; | |
492 | unsigned x; | |
9771b263 DN |
493 | for (x = 0; x < g->edge_list.length (); x += 2) |
494 | if (g->edge_list[x] == node) | |
6de9cd9a | 495 | { |
9771b263 DN |
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; | |
6de9cd9a DN |
501 | return y; |
502 | } | |
f5045c96 | 503 | *locus = UNKNOWN_LOCATION; |
6de9cd9a DN |
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 | ||
9e227d60 | 512 | #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \ |
6de9cd9a DN |
513 | do { \ |
514 | unsigned x_; \ | |
515 | int y_; \ | |
9771b263 | 516 | for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \ |
6de9cd9a | 517 | { \ |
9771b263 | 518 | y_ = (GRAPH)->edge_list[x_]; \ |
6de9cd9a DN |
519 | if (y_ != (NODE)) \ |
520 | continue; \ | |
9771b263 DN |
521 | (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \ |
522 | (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \ | |
6de9cd9a DN |
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 | ||
9e227d60 | 532 | #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \ |
6de9cd9a DN |
533 | do { \ |
534 | unsigned x_; \ | |
535 | int y_; \ | |
9771b263 | 536 | for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \ |
6de9cd9a | 537 | { \ |
9771b263 | 538 | y_ = (GRAPH)->edge_list[x_ + 1]; \ |
6de9cd9a DN |
539 | if (y_ != (NODE)) \ |
540 | continue; \ | |
9771b263 DN |
541 | (void) ((VAR) = (GRAPH)->edge_list[x_]); \ |
542 | (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \ | |
6de9cd9a DN |
543 | CODE; \ |
544 | } \ | |
545 | } while (0) | |
546 | ||
547 | ||
548 | /* Add T to elimination graph G. */ | |
549 | ||
550 | static inline void | |
c8b1ebd9 | 551 | eliminate_name (elim_graph *g, int T) |
6de9cd9a DN |
552 | { |
553 | elim_graph_add_node (g, T); | |
554 | } | |
555 | ||
c8d97db2 AM |
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 | } | |
6de9cd9a | 573 | |
41f683ef KH |
574 | /* Build elimination graph G for basic block BB on incoming PHI edge |
575 | G->e. */ | |
6de9cd9a DN |
576 | |
577 | static void | |
c8b1ebd9 | 578 | eliminate_build (elim_graph *g) |
6de9cd9a | 579 | { |
4e3825db | 580 | tree Ti; |
6de9cd9a | 581 | int p0, pi; |
538dd0b7 | 582 | gphi_iterator gsi; |
6de9cd9a DN |
583 | |
584 | clear_elim_graph (g); | |
b8698a0f | 585 | |
4e3825db | 586 | for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
6de9cd9a | 587 | { |
538dd0b7 | 588 | gphi *phi = gsi.phi (); |
620e594b | 589 | location_t locus; |
726a989a | 590 | |
4e3825db | 591 | p0 = var_to_partition (g->map, gimple_phi_result (phi)); |
6de9cd9a | 592 | /* Ignore results which are not in partitions. */ |
4e3825db | 593 | if (p0 == NO_PARTITION) |
6de9cd9a DN |
594 | continue; |
595 | ||
41f683ef | 596 | Ti = PHI_ARG_DEF (phi, g->e->dest_idx); |
4500f751 EB |
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); | |
6de9cd9a DN |
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. */ | |
c8d97db2 | 606 | if (queue_phi_copy_p (g->map, Ti)) |
6de9cd9a DN |
607 | { |
608 | /* Save constant copies until all other copies have been emitted | |
609 | on this edge. */ | |
9771b263 DN |
610 | g->const_dests.safe_push (p0); |
611 | g->const_copies.safe_push (Ti); | |
612 | g->copy_locus.safe_push (locus); | |
6de9cd9a DN |
613 | } |
614 | else | |
615 | { | |
4e3825db MM |
616 | pi = var_to_partition (g->map, Ti); |
617 | if (p0 != pi) | |
6de9cd9a | 618 | { |
4e3825db MM |
619 | eliminate_name (g, p0); |
620 | eliminate_name (g, pi); | |
9e227d60 | 621 | elim_graph_add_edge (g, p0, pi, locus); |
6de9cd9a DN |
622 | } |
623 | } | |
624 | } | |
625 | } | |
626 | ||
627 | ||
628 | /* Push successors of T onto the elimination stack for G. */ | |
629 | ||
b8698a0f | 630 | static void |
c8b1ebd9 | 631 | elim_forward (elim_graph *g, int T) |
6de9cd9a DN |
632 | { |
633 | int S; | |
620e594b | 634 | location_t locus; |
f5045c96 | 635 | |
d7c028c0 | 636 | bitmap_set_bit (g->visited, T); |
9e227d60 | 637 | FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus, |
6de9cd9a | 638 | { |
d7c028c0 | 639 | if (!bitmap_bit_p (g->visited, S)) |
6de9cd9a DN |
640 | elim_forward (g, S); |
641 | }); | |
9771b263 | 642 | g->stack.safe_push (T); |
6de9cd9a DN |
643 | } |
644 | ||
645 | ||
646 | /* Return 1 if there unvisited predecessors of T in graph G. */ | |
647 | ||
648 | static int | |
c8b1ebd9 | 649 | elim_unvisited_predecessor (elim_graph *g, int T) |
6de9cd9a DN |
650 | { |
651 | int P; | |
620e594b | 652 | location_t locus; |
f5045c96 | 653 | |
9e227d60 | 654 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, |
6de9cd9a | 655 | { |
d7c028c0 | 656 | if (!bitmap_bit_p (g->visited, P)) |
6de9cd9a DN |
657 | return 1; |
658 | }); | |
659 | return 0; | |
660 | } | |
661 | ||
662 | /* Process predecessors first, and insert a copy. */ | |
663 | ||
664 | static void | |
c8b1ebd9 | 665 | elim_backward (elim_graph *g, int T) |
6de9cd9a DN |
666 | { |
667 | int P; | |
620e594b | 668 | location_t locus; |
f5045c96 | 669 | |
d7c028c0 | 670 | bitmap_set_bit (g->visited, T); |
9e227d60 | 671 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, |
6de9cd9a | 672 | { |
d7c028c0 | 673 | if (!bitmap_bit_p (g->visited, P)) |
6de9cd9a DN |
674 | { |
675 | elim_backward (g, P); | |
9e227d60 | 676 | insert_partition_copy_on_edge (g->e, P, T, locus); |
6de9cd9a DN |
677 | } |
678 | }); | |
679 | } | |
680 | ||
4e3825db MM |
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 | { | |
1f9ceff1 | 687 | tree type = TREE_TYPE (name); |
cde0f3fd | 688 | int unsignedp; |
1f9ceff1 | 689 | machine_mode reg_mode = promote_ssa_mode (name, &unsignedp); |
a7bfaee5 JJ |
690 | if (reg_mode == BLKmode) |
691 | return assign_temp (type, 0, 0); | |
4e3825db MM |
692 | rtx x = gen_reg_rtx (reg_mode); |
693 | if (POINTER_TYPE_P (type)) | |
1f9ceff1 | 694 | mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (type))); |
4e3825db MM |
695 | return x; |
696 | } | |
697 | ||
b8698a0f | 698 | /* Insert required copies for T in graph G. Check for a strongly connected |
6de9cd9a DN |
699 | region, and create a temporary to break the cycle if one is found. */ |
700 | ||
b8698a0f | 701 | static void |
c8b1ebd9 | 702 | elim_create (elim_graph *g, int T) |
6de9cd9a | 703 | { |
6de9cd9a | 704 | int P, S; |
620e594b | 705 | location_t locus; |
6de9cd9a DN |
706 | |
707 | if (elim_unvisited_predecessor (g, T)) | |
708 | { | |
8e001680 AK |
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 | ||
9e227d60 DC |
713 | insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION); |
714 | FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, | |
6de9cd9a | 715 | { |
d7c028c0 | 716 | if (!bitmap_bit_p (g->visited, P)) |
6de9cd9a DN |
717 | { |
718 | elim_backward (g, P); | |
9e227d60 | 719 | insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus); |
6de9cd9a DN |
720 | } |
721 | }); | |
722 | } | |
723 | else | |
724 | { | |
9e227d60 | 725 | S = elim_graph_remove_succ_edge (g, T, &locus); |
6de9cd9a DN |
726 | if (S != -1) |
727 | { | |
d7c028c0 | 728 | bitmap_set_bit (g->visited, T); |
9e227d60 | 729 | insert_partition_copy_on_edge (g->e, T, S, locus); |
6de9cd9a DN |
730 | } |
731 | } | |
6de9cd9a DN |
732 | } |
733 | ||
7290d709 | 734 | |
41f683ef | 735 | /* Eliminate all the phi nodes on edge E in graph G. */ |
6de9cd9a DN |
736 | |
737 | static void | |
c8b1ebd9 | 738 | eliminate_phi (edge e, elim_graph *g) |
6de9cd9a | 739 | { |
6de9cd9a | 740 | int x; |
6de9cd9a | 741 | |
9771b263 DN |
742 | gcc_assert (g->const_copies.length () == 0); |
743 | gcc_assert (g->copy_locus.length () == 0); | |
6de9cd9a | 744 | |
0e61db61 | 745 | /* Abnormal edges already have everything coalesced. */ |
6de9cd9a DN |
746 | if (e->flags & EDGE_ABNORMAL) |
747 | return; | |
748 | ||
6de9cd9a DN |
749 | g->e = e; |
750 | ||
4e3825db | 751 | eliminate_build (g); |
6de9cd9a DN |
752 | |
753 | if (elim_graph_size (g) != 0) | |
754 | { | |
4e3825db | 755 | int part; |
bf645d6f | 756 | |
f61e445a | 757 | bitmap_clear (g->visited); |
9771b263 | 758 | g->stack.truncate (0); |
6de9cd9a | 759 | |
9771b263 | 760 | FOR_EACH_VEC_ELT (g->nodes, x, part) |
6de9cd9a | 761 | { |
d7c028c0 | 762 | if (!bitmap_bit_p (g->visited, part)) |
4e3825db | 763 | elim_forward (g, part); |
6de9cd9a | 764 | } |
b8698a0f | 765 | |
f61e445a | 766 | bitmap_clear (g->visited); |
9771b263 | 767 | while (g->stack.length () > 0) |
6de9cd9a | 768 | { |
9771b263 | 769 | x = g->stack.pop (); |
d7c028c0 | 770 | if (!bitmap_bit_p (g->visited, x)) |
6de9cd9a DN |
771 | elim_create (g, x); |
772 | } | |
773 | } | |
774 | ||
775 | /* If there are any pending constant copies, issue them now. */ | |
9771b263 | 776 | while (g->const_copies.length () > 0) |
6de9cd9a | 777 | { |
4e3825db MM |
778 | int dest; |
779 | tree src; | |
620e594b | 780 | location_t locus; |
f5045c96 | 781 | |
9771b263 DN |
782 | src = g->const_copies.pop (); |
783 | dest = g->const_dests.pop (); | |
784 | locus = g->copy_locus.pop (); | |
9e227d60 | 785 | insert_value_copy_on_edge (e, dest, src, locus); |
6de9cd9a DN |
786 | } |
787 | } | |
788 | ||
789 | ||
b8698a0f | 790 | /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME, |
ffd327a7 | 791 | check to see if this allows another PHI node to be removed. */ |
6de9cd9a DN |
792 | |
793 | static void | |
538dd0b7 | 794 | remove_gimple_phi_args (gphi *phi) |
ffd327a7 AM |
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 | { | |
355fe088 | 814 | gimple *stmt; |
ffd327a7 AM |
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 | { | |
538dd0b7 | 822 | remove_gimple_phi_args (as_a <gphi *> (stmt)); |
ffd327a7 AM |
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) | |
6de9cd9a DN |
836 | { |
837 | basic_block bb; | |
538dd0b7 | 838 | gphi_iterator gsi; |
ffd327a7 | 839 | tree result; |
6de9cd9a | 840 | |
11cd3bed | 841 | FOR_EACH_BB_FN (bb, cfun) |
6de9cd9a | 842 | { |
726a989a | 843 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); ) |
6de9cd9a | 844 | { |
538dd0b7 | 845 | gphi *phi = gsi.phi (); |
ffd327a7 | 846 | result = gimple_phi_result (phi); |
ea057359 | 847 | if (virtual_operand_p (result)) |
ca6d4a08 | 848 | remove_phi_node (&gsi, true); |
726a989a | 849 | else |
ffd327a7 AM |
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 | } | |
6de9cd9a DN |
860 | } |
861 | } | |
862 | } | |
863 | ||
864 | ||
6de9cd9a | 865 | /* This function will rewrite the current program using the variable mapping |
b8698a0f L |
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 | |
6de9cd9a DN |
869 | variable. */ |
870 | ||
871 | static void | |
b2b29377 | 872 | rewrite_trees (var_map map) |
6de9cd9a | 873 | { |
b2b29377 MM |
874 | if (!flag_checking) |
875 | return; | |
876 | ||
4e3825db | 877 | basic_block bb; |
6de9cd9a DN |
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. */ | |
11cd3bed | 881 | FOR_EACH_BB_FN (bb, cfun) |
6de9cd9a | 882 | { |
538dd0b7 | 883 | gphi_iterator gsi; |
726a989a | 884 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
6de9cd9a | 885 | { |
538dd0b7 | 886 | gphi *phi = gsi.phi (); |
726a989a | 887 | tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi)); |
6de9cd9a DN |
888 | if (T0 == NULL_TREE) |
889 | { | |
726a989a RB |
890 | size_t i; |
891 | for (i = 0; i < gimple_phi_num_args (phi); i++) | |
6de9cd9a DN |
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 :"); | |
726a989a | 901 | print_gimple_stmt (stderr, phi, 0, TDF_SLIM); |
1e128c5f | 902 | internal_error ("SSA corruption"); |
6de9cd9a DN |
903 | } |
904 | } | |
905 | } | |
906 | } | |
907 | } | |
edfaf675 AM |
908 | } |
909 | ||
e3bfa377 BC |
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 | ||
4e3825db MM |
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. */ | |
edfaf675 | 1010 | |
4e3825db MM |
1011 | void |
1012 | expand_phi_nodes (struct ssaexpand *sa) | |
edfaf675 AM |
1013 | { |
1014 | basic_block bb; | |
61801db9 | 1015 | elim_graph g (sa->map); |
edfaf675 | 1016 | |
fefa31b5 DM |
1017 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, |
1018 | EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
4e3825db | 1019 | if (!gimple_seq_empty_p (phi_nodes (bb))) |
edfaf675 | 1020 | { |
4e3825db MM |
1021 | edge e; |
1022 | edge_iterator ei; | |
edfaf675 | 1023 | FOR_EACH_EDGE (e, ei, bb->preds) |
61801db9 | 1024 | eliminate_phi (e, &g); |
4e3825db MM |
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)); ) | |
edfaf675 | 1036 | { |
4e3825db MM |
1037 | if (e->insns.r && (e->flags & EDGE_EH) |
1038 | && !single_pred_p (e->dest)) | |
1039 | { | |
3ffa95c2 | 1040 | rtx_insn *insns = e->insns.r; |
4e3825db | 1041 | basic_block bb; |
3ffa95c2 | 1042 | e->insns.r = NULL; |
4e3825db MM |
1043 | bb = split_edge (e); |
1044 | single_pred_edge (bb)->insns.r = insns; | |
1045 | } | |
1046 | else | |
1047 | ei_next (&ei); | |
edfaf675 | 1048 | } |
edfaf675 | 1049 | } |
6de9cd9a DN |
1050 | } |
1051 | ||
1052 | ||
7290d709 AM |
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. */ | |
6de9cd9a | 1056 | |
56b043c8 | 1057 | static void |
4e3825db | 1058 | remove_ssa_form (bool perform_ter, struct ssaexpand *sa) |
6de9cd9a | 1059 | { |
e97809c6 | 1060 | bitmap values = NULL; |
7290d709 | 1061 | var_map map; |
6de9cd9a | 1062 | |
e3bfa377 BC |
1063 | for_all_parms (create_default_def, NULL); |
1064 | map = init_var_map (num_ssa_names); | |
1065 | coalesce_ssa_name (map); | |
6de9cd9a | 1066 | |
7290d709 AM |
1067 | /* Return to viewing the variable list as just all reference variables after |
1068 | coalescing has been performed. */ | |
1f9ceff1 | 1069 | partition_view_normal (map); |
6de9cd9a DN |
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 | ||
7290d709 | 1077 | if (perform_ter) |
6de9cd9a DN |
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 | ||
4e3825db | 1084 | rewrite_trees (map); |
6de9cd9a | 1085 | |
4e3825db MM |
1086 | sa->map = map; |
1087 | sa->values = values; | |
f11a7b6d | 1088 | sa->partitions_for_parm_default_defs = get_parm_default_def_partitions (map); |
561593c1 | 1089 | sa->partitions_for_undefined_values = get_undefined_value_partitions (map); |
6de9cd9a DN |
1090 | } |
1091 | ||
7290d709 | 1092 | |
ce985b43 MM |
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; | |
b8698a0f | 1101 | |
ce985b43 MM |
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 | { | |
355fe088 | 1107 | gimple *stmt = gsi_stmt (gsi); |
ce985b43 MM |
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; | |
355fe088 | 1123 | gimple *defa = SSA_NAME_DEF_STMT (arg); |
ce985b43 MM |
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 | { | |
355fe088 | 1132 | gimple *use_stmt = USE_STMT (use); |
d6600130 JJ |
1133 | if (is_gimple_debug (use_stmt)) |
1134 | continue; | |
ce985b43 MM |
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 | } | |
b8698a0f | 1151 | |
ce985b43 MM |
1152 | return false; |
1153 | } | |
1154 | ||
1155 | ||
06170e1d JL |
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; | |
538dd0b7 | 1169 | gphi_iterator gsi; |
06170e1d | 1170 | |
f2521653 BS |
1171 | mark_dfs_back_edges (); |
1172 | ||
11cd3bed | 1173 | FOR_EACH_BB_FN (bb, cfun) |
06170e1d | 1174 | { |
ce985b43 MM |
1175 | /* Mark block as possibly needing calculation of UIDs. */ |
1176 | bb->aux = &bb->aux; | |
1177 | ||
726a989a | 1178 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
06170e1d | 1179 | { |
538dd0b7 | 1180 | gphi *phi = gsi.phi (); |
726a989a | 1181 | tree result = gimple_phi_result (phi); |
726a989a | 1182 | size_t i; |
06170e1d | 1183 | |
ea057359 | 1184 | if (virtual_operand_p (result)) |
06170e1d JL |
1185 | continue; |
1186 | ||
726a989a | 1187 | for (i = 0; i < gimple_phi_num_args (phi); i++) |
06170e1d | 1188 | { |
726a989a RB |
1189 | tree arg = gimple_phi_arg_def (phi, i); |
1190 | edge e = gimple_phi_arg_edge (phi, i); | |
ef976be1 RB |
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; | |
06170e1d | 1196 | |
b8698a0f | 1197 | /* If the argument is not an SSA_NAME, then we will need a |
ef976be1 RB |
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))) | |
06170e1d | 1204 | { |
726a989a | 1205 | tree name; |
538dd0b7 | 1206 | gassign *stmt; |
355fe088 | 1207 | gimple *last = NULL; |
726a989a | 1208 | gimple_stmt_iterator gsi2; |
06170e1d | 1209 | |
726a989a RB |
1210 | gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src); |
1211 | if (!gsi_end_p (gsi2)) | |
1212 | last = gsi_stmt (gsi2); | |
06170e1d JL |
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. | |
b8698a0f | 1216 | However, better safe than sorry. |
35fd3193 | 1217 | If the block ends with a control statement or |
06170e1d JL |
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 | ||
b8698a0f | 1231 | /* Create a new instance of the underlying variable of the |
7290d709 | 1232 | PHI result. */ |
b731b390 | 1233 | name = copy_ssa_name (result); |
6b4a85ad | 1234 | stmt = gimple_build_assign (name, |
726a989a | 1235 | gimple_phi_arg_def (phi, i)); |
06170e1d | 1236 | |
f5045c96 AM |
1237 | /* copy location if present. */ |
1238 | if (gimple_phi_arg_has_location (phi, i)) | |
9e227d60 DC |
1239 | gimple_set_location (stmt, |
1240 | gimple_phi_arg_location (phi, i)); | |
f5045c96 | 1241 | |
06170e1d JL |
1242 | /* Insert the new statement into the block and update |
1243 | the PHI node. */ | |
1244 | if (last && stmt_ends_bb_p (last)) | |
726a989a | 1245 | gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT); |
06170e1d | 1246 | else |
726a989a | 1247 | gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT); |
06170e1d JL |
1248 | SET_PHI_ARG_DEF (phi, i, name); |
1249 | } | |
ef976be1 RB |
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 | } | |
06170e1d JL |
1278 | } |
1279 | } | |
ce985b43 MM |
1280 | |
1281 | /* Unmark this block again. */ | |
1282 | bb->aux = NULL; | |
06170e1d JL |
1283 | } |
1284 | } | |
1285 | ||
4e3825db MM |
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) | |
e97809c6 | 1294 | BITMAP_FREE (sa->values); |
4e3825db | 1295 | delete_var_map (sa->map); |
f11a7b6d | 1296 | BITMAP_FREE (sa->partitions_for_parm_default_defs); |
561593c1 | 1297 | BITMAP_FREE (sa->partitions_for_undefined_values); |
4e3825db MM |
1298 | memset (sa, 0, sizeof *sa); |
1299 | } | |
1300 | ||
7290d709 | 1301 | /* Take the current function out of SSA form, translating PHIs as described in |
6de9cd9a DN |
1302 | R. Morgan, ``Building an Optimizing Compiler'', |
1303 | Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */ | |
1304 | ||
4e3825db MM |
1305 | unsigned int |
1306 | rewrite_out_of_ssa (struct ssaexpand *sa) | |
6de9cd9a | 1307 | { |
06170e1d JL |
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 | ||
ffd327a7 AM |
1316 | |
1317 | /* Eliminate PHIs which are of no use, such as virtual or dead phis. */ | |
1318 | eliminate_useless_phis (); | |
6de9cd9a DN |
1319 | |
1320 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
726a989a | 1321 | gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); |
6de9cd9a | 1322 | |
4e3825db | 1323 | remove_ssa_form (flag_tree_ter, sa); |
6de9cd9a DN |
1324 | |
1325 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
726a989a | 1326 | gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); |
6de9cd9a | 1327 | |
c2924966 | 1328 | return 0; |
6de9cd9a | 1329 | } |