* ru.po: Update.
[official-gcc.git] / gcc / tree-outof-ssa.c
blob41255293e3e41f787318bde0f1669685deeed26b
1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004-2016 Free Software Foundation, Inc.
3 Contributed by Andrew Macleod <amacleod@redhat.com>
5 This file is part of GCC.
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.
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.
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/>. */
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 "emit-rtl.h"
31 #include "gimple-pretty-print.h"
32 #include "diagnostic-core.h"
33 #include "stor-layout.h"
34 #include "cfgrtl.h"
35 #include "cfganal.h"
36 #include "tree-eh.h"
37 #include "gimple-iterator.h"
38 #include "tree-cfg.h"
39 #include "dumpfile.h"
40 #include "tree-ssa-live.h"
41 #include "tree-ssa-ter.h"
42 #include "tree-ssa-coalesce.h"
43 #include "tree-outof-ssa.h"
44 #include "dojump.h"
46 /* FIXME: A lot of code here deals with expanding to RTL. All that code
47 should be in cfgexpand.c. */
48 #include "explow.h"
49 #include "expr.h"
51 /* Return TRUE if expression STMT is suitable for replacement. */
53 bool
54 ssa_is_replaceable_p (gimple *stmt)
56 use_operand_p use_p;
57 tree def;
58 gimple *use_stmt;
60 /* Only consider modify stmts. */
61 if (!is_gimple_assign (stmt))
62 return false;
64 /* If the statement may throw an exception, it cannot be replaced. */
65 if (stmt_could_throw_p (stmt))
66 return false;
68 /* Punt if there is more than 1 def. */
69 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
70 if (!def)
71 return false;
73 /* Only consider definitions which have a single use. */
74 if (!single_imm_use (def, &use_p, &use_stmt))
75 return false;
77 /* Used in this block, but at the TOP of the block, not the end. */
78 if (gimple_code (use_stmt) == GIMPLE_PHI)
79 return false;
81 /* There must be no VDEFs. */
82 if (gimple_vdef (stmt))
83 return false;
85 /* Float expressions must go through memory if float-store is on. */
86 if (flag_float_store
87 && FLOAT_TYPE_P (gimple_expr_type (stmt)))
88 return false;
90 /* An assignment with a register variable on the RHS is not
91 replaceable. */
92 if (gimple_assign_rhs_code (stmt) == VAR_DECL
93 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
94 return false;
96 /* No function calls can be replaced. */
97 if (is_gimple_call (stmt))
98 return false;
100 /* Leave any stmt with volatile operands alone as well. */
101 if (gimple_has_volatile_ops (stmt))
102 return false;
104 return true;
108 /* Used to hold all the components required to do SSA PHI elimination.
109 The node and pred/succ list is a simple linear list of nodes and
110 edges represented as pairs of nodes.
112 The predecessor and successor list: Nodes are entered in pairs, where
113 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
114 predecessors, all the odd elements are successors.
116 Rationale:
117 When implemented as bitmaps, very large programs SSA->Normal times were
118 being dominated by clearing the interference graph.
120 Typically this list of edges is extremely small since it only includes
121 PHI results and uses from a single edge which have not coalesced with
122 each other. This means that no virtual PHI nodes are included, and
123 empirical evidence suggests that the number of edges rarely exceed
124 3, and in a bootstrap of GCC, the maximum size encountered was 7.
125 This also limits the number of possible nodes that are involved to
126 rarely more than 6, and in the bootstrap of gcc, the maximum number
127 of nodes encountered was 12. */
129 typedef struct _elim_graph {
130 /* Size of the elimination vectors. */
131 int size;
133 /* List of nodes in the elimination graph. */
134 vec<int> nodes;
136 /* The predecessor and successor edge list. */
137 vec<int> edge_list;
139 /* Source locus on each edge */
140 vec<source_location> edge_locus;
142 /* Visited vector. */
143 sbitmap visited;
145 /* Stack for visited nodes. */
146 vec<int> stack;
148 /* The variable partition map. */
149 var_map map;
151 /* Edge being eliminated by this graph. */
152 edge e;
154 /* List of constant copies to emit. These are pushed on in pairs. */
155 vec<int> const_dests;
156 vec<tree> const_copies;
158 /* Source locations for any constant copies. */
159 vec<source_location> copy_locus;
160 } *elim_graph;
163 /* For an edge E find out a good source location to associate with
164 instructions inserted on edge E. If E has an implicit goto set,
165 use its location. Otherwise search instructions in predecessors
166 of E for a location, and use that one. That makes sense because
167 we insert on edges for PHI nodes, and effects of PHIs happen on
168 the end of the predecessor conceptually. */
170 static void
171 set_location_for_edge (edge e)
173 if (e->goto_locus)
175 set_curr_insn_location (e->goto_locus);
177 else
179 basic_block bb = e->src;
180 gimple_stmt_iterator gsi;
184 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
186 gimple *stmt = gsi_stmt (gsi);
187 if (is_gimple_debug (stmt))
188 continue;
189 if (gimple_has_location (stmt) || gimple_block (stmt))
191 set_curr_insn_location (gimple_location (stmt));
192 return;
195 /* Nothing found in this basic block. Make a half-assed attempt
196 to continue with another block. */
197 if (single_pred_p (bb))
198 bb = single_pred (bb);
199 else
200 bb = e->src;
202 while (bb != e->src);
206 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
207 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
208 which we deduce the size to copy in that case. */
210 static inline rtx_insn *
211 emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp)
213 start_sequence ();
215 if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest))
216 src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp);
217 if (GET_MODE (src) == BLKmode)
219 gcc_assert (GET_MODE (dest) == BLKmode);
220 emit_block_move (dest, src, expr_size (sizeexp), BLOCK_OP_NORMAL);
222 else
223 emit_move_insn (dest, src);
224 do_pending_stack_adjust ();
226 rtx_insn *seq = get_insns ();
227 end_sequence ();
229 return seq;
232 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
234 static void
235 insert_partition_copy_on_edge (edge e, int dest, int src, source_location locus)
237 tree var;
238 if (dump_file && (dump_flags & TDF_DETAILS))
240 fprintf (dump_file,
241 "Inserting a partition copy on edge BB%d->BB%d :"
242 "PART.%d = PART.%d",
243 e->src->index,
244 e->dest->index, dest, src);
245 fprintf (dump_file, "\n");
248 gcc_assert (SA.partition_to_pseudo[dest]);
249 gcc_assert (SA.partition_to_pseudo[src]);
251 set_location_for_edge (e);
252 /* If a locus is provided, override the default. */
253 if (locus)
254 set_curr_insn_location (locus);
256 var = partition_to_var (SA.map, src);
257 rtx_insn *seq = emit_partition_copy (copy_rtx (SA.partition_to_pseudo[dest]),
258 copy_rtx (SA.partition_to_pseudo[src]),
259 TYPE_UNSIGNED (TREE_TYPE (var)),
260 var);
262 insert_insn_on_edge (seq, e);
265 /* Insert a copy instruction from expression SRC to partition DEST
266 onto edge E. */
268 static void
269 insert_value_copy_on_edge (edge e, int dest, tree src, source_location locus)
271 rtx dest_rtx, seq, x;
272 machine_mode dest_mode, src_mode;
273 int unsignedp;
275 if (dump_file && (dump_flags & TDF_DETAILS))
277 fprintf (dump_file,
278 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
279 e->src->index,
280 e->dest->index, dest);
281 print_generic_expr (dump_file, src, TDF_SLIM);
282 fprintf (dump_file, "\n");
285 dest_rtx = copy_rtx (SA.partition_to_pseudo[dest]);
286 gcc_assert (dest_rtx);
288 set_location_for_edge (e);
289 /* If a locus is provided, override the default. */
290 if (locus)
291 set_curr_insn_location (locus);
293 start_sequence ();
295 tree name = partition_to_var (SA.map, dest);
296 src_mode = TYPE_MODE (TREE_TYPE (src));
297 dest_mode = GET_MODE (dest_rtx);
298 gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (name)));
299 gcc_assert (!REG_P (dest_rtx)
300 || dest_mode == promote_ssa_mode (name, &unsignedp));
302 if (src_mode != dest_mode)
304 x = expand_expr (src, NULL, src_mode, EXPAND_NORMAL);
305 x = convert_modes (dest_mode, src_mode, x, unsignedp);
307 else if (src_mode == BLKmode)
309 x = dest_rtx;
310 store_expr (src, x, 0, false, false);
312 else
313 x = expand_expr (src, dest_rtx, dest_mode, EXPAND_NORMAL);
315 if (x != dest_rtx)
316 emit_move_insn (dest_rtx, x);
317 do_pending_stack_adjust ();
319 seq = get_insns ();
320 end_sequence ();
322 insert_insn_on_edge (seq, e);
325 /* Insert a copy instruction from RTL expression SRC to partition DEST
326 onto edge E. */
328 static void
329 insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
330 source_location locus)
332 if (dump_file && (dump_flags & TDF_DETAILS))
334 fprintf (dump_file,
335 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
336 e->src->index,
337 e->dest->index, dest);
338 print_simple_rtl (dump_file, src);
339 fprintf (dump_file, "\n");
342 gcc_assert (SA.partition_to_pseudo[dest]);
344 set_location_for_edge (e);
345 /* If a locus is provided, override the default. */
346 if (locus)
347 set_curr_insn_location (locus);
349 /* We give the destination as sizeexp in case src/dest are BLKmode
350 mems. Usually we give the source. As we result from SSA names
351 the left and right size should be the same (and no WITH_SIZE_EXPR
352 involved), so it doesn't matter. */
353 rtx_insn *seq = emit_partition_copy (copy_rtx (SA.partition_to_pseudo[dest]),
354 src, unsignedsrcp,
355 partition_to_var (SA.map, dest));
357 insert_insn_on_edge (seq, e);
360 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
361 onto edge E. */
363 static void
364 insert_part_to_rtx_on_edge (edge e, rtx dest, int src, source_location locus)
366 tree var;
367 if (dump_file && (dump_flags & TDF_DETAILS))
369 fprintf (dump_file,
370 "Inserting a temp copy on edge BB%d->BB%d : ",
371 e->src->index,
372 e->dest->index);
373 print_simple_rtl (dump_file, dest);
374 fprintf (dump_file, "= PART.%d\n", src);
377 gcc_assert (SA.partition_to_pseudo[src]);
379 set_location_for_edge (e);
380 /* If a locus is provided, override the default. */
381 if (locus)
382 set_curr_insn_location (locus);
384 var = partition_to_var (SA.map, src);
385 rtx_insn *seq = emit_partition_copy (dest,
386 copy_rtx (SA.partition_to_pseudo[src]),
387 TYPE_UNSIGNED (TREE_TYPE (var)),
388 var);
390 insert_insn_on_edge (seq, e);
394 /* Create an elimination graph with SIZE nodes and associated data
395 structures. */
397 static elim_graph
398 new_elim_graph (int size)
400 elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
402 g->nodes.create (30);
403 g->const_dests.create (20);
404 g->const_copies.create (20);
405 g->copy_locus.create (10);
406 g->edge_list.create (20);
407 g->edge_locus.create (10);
408 g->stack.create (30);
410 g->visited = sbitmap_alloc (size);
412 return g;
416 /* Empty elimination graph G. */
418 static inline void
419 clear_elim_graph (elim_graph g)
421 g->nodes.truncate (0);
422 g->edge_list.truncate (0);
423 g->edge_locus.truncate (0);
427 /* Delete elimination graph G. */
429 static inline void
430 delete_elim_graph (elim_graph g)
432 sbitmap_free (g->visited);
433 g->stack.release ();
434 g->edge_list.release ();
435 g->const_copies.release ();
436 g->const_dests.release ();
437 g->nodes.release ();
438 g->copy_locus.release ();
439 g->edge_locus.release ();
441 free (g);
445 /* Return the number of nodes in graph G. */
447 static inline int
448 elim_graph_size (elim_graph g)
450 return g->nodes.length ();
454 /* Add NODE to graph G, if it doesn't exist already. */
456 static inline void
457 elim_graph_add_node (elim_graph g, int node)
459 int x;
460 int t;
462 FOR_EACH_VEC_ELT (g->nodes, x, t)
463 if (t == node)
464 return;
465 g->nodes.safe_push (node);
469 /* Add the edge PRED->SUCC to graph G. */
471 static inline void
472 elim_graph_add_edge (elim_graph g, int pred, int succ, source_location locus)
474 g->edge_list.safe_push (pred);
475 g->edge_list.safe_push (succ);
476 g->edge_locus.safe_push (locus);
480 /* Remove an edge from graph G for which NODE is the predecessor, and
481 return the successor node. -1 is returned if there is no such edge. */
483 static inline int
484 elim_graph_remove_succ_edge (elim_graph g, int node, source_location *locus)
486 int y;
487 unsigned x;
488 for (x = 0; x < g->edge_list.length (); x += 2)
489 if (g->edge_list[x] == node)
491 g->edge_list[x] = -1;
492 y = g->edge_list[x + 1];
493 g->edge_list[x + 1] = -1;
494 *locus = g->edge_locus[x / 2];
495 g->edge_locus[x / 2] = UNKNOWN_LOCATION;
496 return y;
498 *locus = UNKNOWN_LOCATION;
499 return -1;
503 /* Find all the nodes in GRAPH which are successors to NODE in the
504 edge list. VAR will hold the partition number found. CODE is the
505 code fragment executed for every node found. */
507 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
508 do { \
509 unsigned x_; \
510 int y_; \
511 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
513 y_ = (GRAPH)->edge_list[x_]; \
514 if (y_ != (NODE)) \
515 continue; \
516 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
517 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
518 CODE; \
520 } while (0)
523 /* Find all the nodes which are predecessors of NODE in the edge list for
524 GRAPH. VAR will hold the partition number found. CODE is the
525 code fragment executed for every node found. */
527 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
528 do { \
529 unsigned x_; \
530 int y_; \
531 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
533 y_ = (GRAPH)->edge_list[x_ + 1]; \
534 if (y_ != (NODE)) \
535 continue; \
536 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
537 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
538 CODE; \
540 } while (0)
543 /* Add T to elimination graph G. */
545 static inline void
546 eliminate_name (elim_graph g, int T)
548 elim_graph_add_node (g, T);
551 /* Return true if this phi argument T should have a copy queued when using
552 var_map MAP. PHI nodes should contain only ssa_names and invariants. A
553 test for ssa_name is definitely simpler, but don't let invalid contents
554 slip through in the meantime. */
556 static inline bool
557 queue_phi_copy_p (var_map map, tree t)
559 if (TREE_CODE (t) == SSA_NAME)
561 if (var_to_partition (map, t) == NO_PARTITION)
562 return true;
563 return false;
565 gcc_checking_assert (is_gimple_min_invariant (t));
566 return true;
569 /* Build elimination graph G for basic block BB on incoming PHI edge
570 G->e. */
572 static void
573 eliminate_build (elim_graph g)
575 tree Ti;
576 int p0, pi;
577 gphi_iterator gsi;
579 clear_elim_graph (g);
581 for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
583 gphi *phi = gsi.phi ();
584 source_location locus;
586 p0 = var_to_partition (g->map, gimple_phi_result (phi));
587 /* Ignore results which are not in partitions. */
588 if (p0 == NO_PARTITION)
589 continue;
591 Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
592 locus = gimple_phi_arg_location_from_edge (phi, g->e);
594 /* If this argument is a constant, or a SSA_NAME which is being
595 left in SSA form, just queue a copy to be emitted on this
596 edge. */
597 if (queue_phi_copy_p (g->map, Ti))
599 /* Save constant copies until all other copies have been emitted
600 on this edge. */
601 g->const_dests.safe_push (p0);
602 g->const_copies.safe_push (Ti);
603 g->copy_locus.safe_push (locus);
605 else
607 pi = var_to_partition (g->map, Ti);
608 if (p0 != pi)
610 eliminate_name (g, p0);
611 eliminate_name (g, pi);
612 elim_graph_add_edge (g, p0, pi, locus);
619 /* Push successors of T onto the elimination stack for G. */
621 static void
622 elim_forward (elim_graph g, int T)
624 int S;
625 source_location locus;
627 bitmap_set_bit (g->visited, T);
628 FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus,
630 if (!bitmap_bit_p (g->visited, S))
631 elim_forward (g, S);
633 g->stack.safe_push (T);
637 /* Return 1 if there unvisited predecessors of T in graph G. */
639 static int
640 elim_unvisited_predecessor (elim_graph g, int T)
642 int P;
643 source_location locus;
645 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
647 if (!bitmap_bit_p (g->visited, P))
648 return 1;
650 return 0;
653 /* Process predecessors first, and insert a copy. */
655 static void
656 elim_backward (elim_graph g, int T)
658 int P;
659 source_location locus;
661 bitmap_set_bit (g->visited, T);
662 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
664 if (!bitmap_bit_p (g->visited, P))
666 elim_backward (g, P);
667 insert_partition_copy_on_edge (g->e, P, T, locus);
672 /* Allocate a new pseudo register usable for storing values sitting
673 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
675 static rtx
676 get_temp_reg (tree name)
678 tree type = TREE_TYPE (name);
679 int unsignedp;
680 machine_mode reg_mode = promote_ssa_mode (name, &unsignedp);
681 rtx x = gen_reg_rtx (reg_mode);
682 if (POINTER_TYPE_P (type))
683 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (type)));
684 return x;
687 /* Insert required copies for T in graph G. Check for a strongly connected
688 region, and create a temporary to break the cycle if one is found. */
690 static void
691 elim_create (elim_graph g, int T)
693 int P, S;
694 source_location locus;
696 if (elim_unvisited_predecessor (g, T))
698 tree var = partition_to_var (g->map, T);
699 rtx U = get_temp_reg (var);
700 int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
702 insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION);
703 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
705 if (!bitmap_bit_p (g->visited, P))
707 elim_backward (g, P);
708 insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus);
712 else
714 S = elim_graph_remove_succ_edge (g, T, &locus);
715 if (S != -1)
717 bitmap_set_bit (g->visited, T);
718 insert_partition_copy_on_edge (g->e, T, S, locus);
724 /* Eliminate all the phi nodes on edge E in graph G. */
726 static void
727 eliminate_phi (edge e, elim_graph g)
729 int x;
731 gcc_assert (g->const_copies.length () == 0);
732 gcc_assert (g->copy_locus.length () == 0);
734 /* Abnormal edges already have everything coalesced. */
735 if (e->flags & EDGE_ABNORMAL)
736 return;
738 g->e = e;
740 eliminate_build (g);
742 if (elim_graph_size (g) != 0)
744 int part;
746 bitmap_clear (g->visited);
747 g->stack.truncate (0);
749 FOR_EACH_VEC_ELT (g->nodes, x, part)
751 if (!bitmap_bit_p (g->visited, part))
752 elim_forward (g, part);
755 bitmap_clear (g->visited);
756 while (g->stack.length () > 0)
758 x = g->stack.pop ();
759 if (!bitmap_bit_p (g->visited, x))
760 elim_create (g, x);
764 /* If there are any pending constant copies, issue them now. */
765 while (g->const_copies.length () > 0)
767 int dest;
768 tree src;
769 source_location locus;
771 src = g->const_copies.pop ();
772 dest = g->const_dests.pop ();
773 locus = g->copy_locus.pop ();
774 insert_value_copy_on_edge (e, dest, src, locus);
779 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
780 check to see if this allows another PHI node to be removed. */
782 static void
783 remove_gimple_phi_args (gphi *phi)
785 use_operand_p arg_p;
786 ssa_op_iter iter;
788 if (dump_file && (dump_flags & TDF_DETAILS))
790 fprintf (dump_file, "Removing Dead PHI definition: ");
791 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
794 FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
796 tree arg = USE_FROM_PTR (arg_p);
797 if (TREE_CODE (arg) == SSA_NAME)
799 /* Remove the reference to the existing argument. */
800 SET_USE (arg_p, NULL_TREE);
801 if (has_zero_uses (arg))
803 gimple *stmt;
804 gimple_stmt_iterator gsi;
806 stmt = SSA_NAME_DEF_STMT (arg);
808 /* Also remove the def if it is a PHI node. */
809 if (gimple_code (stmt) == GIMPLE_PHI)
811 remove_gimple_phi_args (as_a <gphi *> (stmt));
812 gsi = gsi_for_stmt (stmt);
813 remove_phi_node (&gsi, true);
821 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
823 static void
824 eliminate_useless_phis (void)
826 basic_block bb;
827 gphi_iterator gsi;
828 tree result;
830 FOR_EACH_BB_FN (bb, cfun)
832 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
834 gphi *phi = gsi.phi ();
835 result = gimple_phi_result (phi);
836 if (virtual_operand_p (result))
838 /* There should be no arguments which are not virtual, or the
839 results will be incorrect. */
840 if (flag_checking)
841 for (size_t i = 0; i < gimple_phi_num_args (phi); i++)
843 tree arg = PHI_ARG_DEF (phi, i);
844 if (TREE_CODE (arg) == SSA_NAME
845 && !virtual_operand_p (arg))
847 fprintf (stderr, "Argument of PHI is not virtual (");
848 print_generic_expr (stderr, arg, TDF_SLIM);
849 fprintf (stderr, "), but the result is :");
850 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
851 internal_error ("SSA corruption");
855 remove_phi_node (&gsi, true);
857 else
859 /* Also remove real PHIs with no uses. */
860 if (has_zero_uses (result))
862 remove_gimple_phi_args (phi);
863 remove_phi_node (&gsi, true);
865 else
866 gsi_next (&gsi);
873 /* This function will rewrite the current program using the variable mapping
874 found in MAP. If the replacement vector VALUES is provided, any
875 occurrences of partitions with non-null entries in the vector will be
876 replaced with the expression in the vector instead of its mapped
877 variable. */
879 static void
880 rewrite_trees (var_map map)
882 if (!flag_checking)
883 return;
885 basic_block bb;
886 /* Search for PHIs where the destination has no partition, but one
887 or more arguments has a partition. This should not happen and can
888 create incorrect code. */
889 FOR_EACH_BB_FN (bb, cfun)
891 gphi_iterator gsi;
892 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
894 gphi *phi = gsi.phi ();
895 tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
896 if (T0 == NULL_TREE)
898 size_t i;
899 for (i = 0; i < gimple_phi_num_args (phi); i++)
901 tree arg = PHI_ARG_DEF (phi, i);
903 if (TREE_CODE (arg) == SSA_NAME
904 && var_to_partition (map, arg) != NO_PARTITION)
906 fprintf (stderr, "Argument of PHI is in a partition :(");
907 print_generic_expr (stderr, arg, TDF_SLIM);
908 fprintf (stderr, "), but the result is not :");
909 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
910 internal_error ("SSA corruption");
918 /* Given the out-of-ssa info object SA (with prepared partitions)
919 eliminate all phi nodes in all basic blocks. Afterwards no
920 basic block will have phi nodes anymore and there are possibly
921 some RTL instructions inserted on edges. */
923 void
924 expand_phi_nodes (struct ssaexpand *sa)
926 basic_block bb;
927 elim_graph g = new_elim_graph (sa->map->num_partitions);
928 g->map = sa->map;
930 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb,
931 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
932 if (!gimple_seq_empty_p (phi_nodes (bb)))
934 edge e;
935 edge_iterator ei;
936 FOR_EACH_EDGE (e, ei, bb->preds)
937 eliminate_phi (e, g);
938 set_phi_nodes (bb, NULL);
939 /* We can't redirect EH edges in RTL land, so we need to do this
940 here. Redirection happens only when splitting is necessary,
941 which it is only for critical edges, normally. For EH edges
942 it might also be necessary when the successor has more than
943 one predecessor. In that case the edge is either required to
944 be fallthru (which EH edges aren't), or the predecessor needs
945 to end with a jump (which again, isn't the case with EH edges).
946 Hence, split all EH edges on which we inserted instructions
947 and whose successor has multiple predecessors. */
948 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
950 if (e->insns.r && (e->flags & EDGE_EH)
951 && !single_pred_p (e->dest))
953 rtx_insn *insns = e->insns.r;
954 basic_block bb;
955 e->insns.r = NULL;
956 bb = split_edge (e);
957 single_pred_edge (bb)->insns.r = insns;
959 else
960 ei_next (&ei);
964 delete_elim_graph (g);
968 /* Remove the ssa-names in the current function and translate them into normal
969 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
970 should also be used. */
972 static void
973 remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
975 bitmap values = NULL;
976 var_map map;
978 map = coalesce_ssa_name ();
980 /* Return to viewing the variable list as just all reference variables after
981 coalescing has been performed. */
982 partition_view_normal (map);
984 if (dump_file && (dump_flags & TDF_DETAILS))
986 fprintf (dump_file, "After Coalescing:\n");
987 dump_var_map (dump_file, map);
990 if (perform_ter)
992 values = find_replaceable_exprs (map);
993 if (values && dump_file && (dump_flags & TDF_DETAILS))
994 dump_replaceable_exprs (dump_file, values);
997 rewrite_trees (map);
999 sa->map = map;
1000 sa->values = values;
1001 sa->partitions_for_parm_default_defs = get_parm_default_def_partitions (map);
1005 /* If not already done so for basic block BB, assign increasing uids
1006 to each of its instructions. */
1008 static void
1009 maybe_renumber_stmts_bb (basic_block bb)
1011 unsigned i = 0;
1012 gimple_stmt_iterator gsi;
1014 if (!bb->aux)
1015 return;
1016 bb->aux = NULL;
1017 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1019 gimple *stmt = gsi_stmt (gsi);
1020 gimple_set_uid (stmt, i);
1021 i++;
1026 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
1027 of a PHI node) and ARG (one of its arguments) conflict. Return false
1028 otherwise, also when we simply aren't sure. */
1030 static bool
1031 trivially_conflicts_p (basic_block bb, tree result, tree arg)
1033 use_operand_p use;
1034 imm_use_iterator imm_iter;
1035 gimple *defa = SSA_NAME_DEF_STMT (arg);
1037 /* If ARG isn't defined in the same block it's too complicated for
1038 our little mind. */
1039 if (gimple_bb (defa) != bb)
1040 return false;
1042 FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
1044 gimple *use_stmt = USE_STMT (use);
1045 if (is_gimple_debug (use_stmt))
1046 continue;
1047 /* Now, if there's a use of RESULT that lies outside this basic block,
1048 then there surely is a conflict with ARG. */
1049 if (gimple_bb (use_stmt) != bb)
1050 return true;
1051 if (gimple_code (use_stmt) == GIMPLE_PHI)
1052 continue;
1053 /* The use now is in a real stmt of BB, so if ARG was defined
1054 in a PHI node (like RESULT) both conflict. */
1055 if (gimple_code (defa) == GIMPLE_PHI)
1056 return true;
1057 maybe_renumber_stmts_bb (bb);
1058 /* If the use of RESULT occurs after the definition of ARG,
1059 the two conflict too. */
1060 if (gimple_uid (defa) < gimple_uid (use_stmt))
1061 return true;
1064 return false;
1068 /* Search every PHI node for arguments associated with backedges which
1069 we can trivially determine will need a copy (the argument is either
1070 not an SSA_NAME or the argument has a different underlying variable
1071 than the PHI result).
1073 Insert a copy from the PHI argument to a new destination at the
1074 end of the block with the backedge to the top of the loop. Update
1075 the PHI argument to reference this new destination. */
1077 static void
1078 insert_backedge_copies (void)
1080 basic_block bb;
1081 gphi_iterator gsi;
1083 mark_dfs_back_edges ();
1085 FOR_EACH_BB_FN (bb, cfun)
1087 /* Mark block as possibly needing calculation of UIDs. */
1088 bb->aux = &bb->aux;
1090 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1092 gphi *phi = gsi.phi ();
1093 tree result = gimple_phi_result (phi);
1094 size_t i;
1096 if (virtual_operand_p (result))
1097 continue;
1099 for (i = 0; i < gimple_phi_num_args (phi); i++)
1101 tree arg = gimple_phi_arg_def (phi, i);
1102 edge e = gimple_phi_arg_edge (phi, i);
1104 /* If the argument is not an SSA_NAME, then we will need a
1105 constant initialization. If the argument is an SSA_NAME with
1106 a different underlying variable then a copy statement will be
1107 needed. */
1108 if ((e->flags & EDGE_DFS_BACK)
1109 && (TREE_CODE (arg) != SSA_NAME
1110 || SSA_NAME_VAR (arg) != SSA_NAME_VAR (result)
1111 || trivially_conflicts_p (bb, result, arg)))
1113 tree name;
1114 gassign *stmt;
1115 gimple *last = NULL;
1116 gimple_stmt_iterator gsi2;
1118 gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
1119 if (!gsi_end_p (gsi2))
1120 last = gsi_stmt (gsi2);
1122 /* In theory the only way we ought to get back to the
1123 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1124 However, better safe than sorry.
1125 If the block ends with a control statement or
1126 something that might throw, then we have to
1127 insert this assignment before the last
1128 statement. Else insert it after the last statement. */
1129 if (last && stmt_ends_bb_p (last))
1131 /* If the last statement in the block is the definition
1132 site of the PHI argument, then we can't insert
1133 anything after it. */
1134 if (TREE_CODE (arg) == SSA_NAME
1135 && SSA_NAME_DEF_STMT (arg) == last)
1136 continue;
1139 /* Create a new instance of the underlying variable of the
1140 PHI result. */
1141 name = copy_ssa_name (result);
1142 stmt = gimple_build_assign (name,
1143 gimple_phi_arg_def (phi, i));
1145 /* copy location if present. */
1146 if (gimple_phi_arg_has_location (phi, i))
1147 gimple_set_location (stmt,
1148 gimple_phi_arg_location (phi, i));
1150 /* Insert the new statement into the block and update
1151 the PHI node. */
1152 if (last && stmt_ends_bb_p (last))
1153 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1154 else
1155 gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1156 SET_PHI_ARG_DEF (phi, i, name);
1161 /* Unmark this block again. */
1162 bb->aux = NULL;
1166 /* Free all memory associated with going out of SSA form. SA is
1167 the outof-SSA info object. */
1169 void
1170 finish_out_of_ssa (struct ssaexpand *sa)
1172 free (sa->partition_to_pseudo);
1173 if (sa->values)
1174 BITMAP_FREE (sa->values);
1175 delete_var_map (sa->map);
1176 BITMAP_FREE (sa->partitions_for_parm_default_defs);
1177 memset (sa, 0, sizeof *sa);
1180 /* Take the current function out of SSA form, translating PHIs as described in
1181 R. Morgan, ``Building an Optimizing Compiler'',
1182 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1184 unsigned int
1185 rewrite_out_of_ssa (struct ssaexpand *sa)
1187 /* If elimination of a PHI requires inserting a copy on a backedge,
1188 then we will have to split the backedge which has numerous
1189 undesirable performance effects.
1191 A significant number of such cases can be handled here by inserting
1192 copies into the loop itself. */
1193 insert_backedge_copies ();
1196 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1197 eliminate_useless_phis ();
1199 if (dump_file && (dump_flags & TDF_DETAILS))
1200 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1202 remove_ssa_form (flag_tree_ter, sa);
1204 if (dump_file && (dump_flags & TDF_DETAILS))
1205 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1207 return 0;