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