]> git.ipfire.org Git - thirdparty/gcc.git/blob - gcc/tree-outof-ssa.c
Merge in trunk.
[thirdparty/gcc.git] / gcc / tree-outof-ssa.c
1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004-2013 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 "tm.h"
25 #include "tree.h"
26 #include "ggc.h"
27 #include "basic-block.h"
28 #include "gimple-pretty-print.h"
29 #include "bitmap.h"
30 #include "tree-ssa.h"
31 #include "dumpfile.h"
32 #include "diagnostic-core.h"
33 #include "ssaexpand.h"
34
35 /* FIXME: A lot of code here deals with expanding to RTL. All that code
36 should be in cfgexpand.c. */
37 #include "expr.h"
38
39
40
41 /* Used to hold all the components required to do SSA PHI elimination.
42 The node and pred/succ list is a simple linear list of nodes and
43 edges represented as pairs of nodes.
44
45 The predecessor and successor list: Nodes are entered in pairs, where
46 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
47 predecessors, all the odd elements are successors.
48
49 Rationale:
50 When implemented as bitmaps, very large programs SSA->Normal times were
51 being dominated by clearing the interference graph.
52
53 Typically this list of edges is extremely small since it only includes
54 PHI results and uses from a single edge which have not coalesced with
55 each other. This means that no virtual PHI nodes are included, and
56 empirical evidence suggests that the number of edges rarely exceed
57 3, and in a bootstrap of GCC, the maximum size encountered was 7.
58 This also limits the number of possible nodes that are involved to
59 rarely more than 6, and in the bootstrap of gcc, the maximum number
60 of nodes encountered was 12. */
61
62 typedef struct _elim_graph {
63 /* Size of the elimination vectors. */
64 int size;
65
66 /* List of nodes in the elimination graph. */
67 vec<int> nodes;
68
69 /* The predecessor and successor edge list. */
70 vec<int> edge_list;
71
72 /* Source locus on each edge */
73 vec<source_location> edge_locus;
74
75 /* Visited vector. */
76 sbitmap visited;
77
78 /* Stack for visited nodes. */
79 vec<int> stack;
80
81 /* The variable partition map. */
82 var_map map;
83
84 /* Edge being eliminated by this graph. */
85 edge e;
86
87 /* List of constant copies to emit. These are pushed on in pairs. */
88 vec<int> const_dests;
89 vec<tree> const_copies;
90
91 /* Source locations for any constant copies. */
92 vec<source_location> copy_locus;
93 } *elim_graph;
94
95
96 /* For an edge E find out a good source location to associate with
97 instructions inserted on edge E. If E has an implicit goto set,
98 use its location. Otherwise search instructions in predecessors
99 of E for a location, and use that one. That makes sense because
100 we insert on edges for PHI nodes, and effects of PHIs happen on
101 the end of the predecessor conceptually. */
102
103 static void
104 set_location_for_edge (edge e)
105 {
106 if (e->goto_locus)
107 {
108 set_curr_insn_location (e->goto_locus);
109 }
110 else
111 {
112 basic_block bb = e->src;
113 gimple_stmt_iterator gsi;
114
115 do
116 {
117 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
118 {
119 gimple stmt = gsi_stmt (gsi);
120 if (is_gimple_debug (stmt))
121 continue;
122 if (gimple_has_location (stmt) || gimple_block (stmt))
123 {
124 set_curr_insn_location (gimple_location (stmt));
125 return;
126 }
127 }
128 /* Nothing found in this basic block. Make a half-assed attempt
129 to continue with another block. */
130 if (single_pred_p (bb))
131 bb = single_pred (bb);
132 else
133 bb = e->src;
134 }
135 while (bb != e->src);
136 }
137 }
138
139 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
140 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
141 which we deduce the size to copy in that case. */
142
143 static inline rtx
144 emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp)
145 {
146 rtx seq;
147
148 start_sequence ();
149
150 if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest))
151 src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp);
152 if (GET_MODE (src) == BLKmode)
153 {
154 gcc_assert (GET_MODE (dest) == BLKmode);
155 emit_block_move (dest, src, expr_size (sizeexp), BLOCK_OP_NORMAL);
156 }
157 else
158 emit_move_insn (dest, src);
159
160 seq = get_insns ();
161 end_sequence ();
162
163 return seq;
164 }
165
166 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
167
168 static void
169 insert_partition_copy_on_edge (edge e, int dest, int src, source_location locus)
170 {
171 tree var;
172 rtx seq;
173 if (dump_file && (dump_flags & TDF_DETAILS))
174 {
175 fprintf (dump_file,
176 "Inserting a partition copy on edge BB%d->BB%d :"
177 "PART.%d = PART.%d",
178 e->src->index,
179 e->dest->index, dest, src);
180 fprintf (dump_file, "\n");
181 }
182
183 gcc_assert (SA.partition_to_pseudo[dest]);
184 gcc_assert (SA.partition_to_pseudo[src]);
185
186 set_location_for_edge (e);
187 /* If a locus is provided, override the default. */
188 if (locus)
189 set_curr_insn_location (locus);
190
191 var = partition_to_var (SA.map, src);
192 seq = emit_partition_copy (SA.partition_to_pseudo[dest],
193 SA.partition_to_pseudo[src],
194 TYPE_UNSIGNED (TREE_TYPE (var)),
195 var);
196
197 insert_insn_on_edge (seq, e);
198 }
199
200 /* Insert a copy instruction from expression SRC to partition DEST
201 onto edge E. */
202
203 static void
204 insert_value_copy_on_edge (edge e, int dest, tree src, source_location locus)
205 {
206 rtx seq, x;
207 enum machine_mode dest_mode, src_mode;
208 int unsignedp;
209 tree var;
210
211 if (dump_file && (dump_flags & TDF_DETAILS))
212 {
213 fprintf (dump_file,
214 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
215 e->src->index,
216 e->dest->index, dest);
217 print_generic_expr (dump_file, src, TDF_SLIM);
218 fprintf (dump_file, "\n");
219 }
220
221 gcc_assert (SA.partition_to_pseudo[dest]);
222
223 set_location_for_edge (e);
224 /* If a locus is provided, override the default. */
225 if (locus)
226 set_curr_insn_location (locus);
227
228 start_sequence ();
229
230 var = SSA_NAME_VAR (partition_to_var (SA.map, dest));
231 src_mode = TYPE_MODE (TREE_TYPE (src));
232 dest_mode = GET_MODE (SA.partition_to_pseudo[dest]);
233 gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (var)));
234 gcc_assert (!REG_P (SA.partition_to_pseudo[dest])
235 || dest_mode == promote_decl_mode (var, &unsignedp));
236
237 if (src_mode != dest_mode)
238 {
239 x = expand_expr (src, NULL, src_mode, EXPAND_NORMAL);
240 x = convert_modes (dest_mode, src_mode, x, unsignedp);
241 }
242 else if (src_mode == BLKmode)
243 {
244 x = SA.partition_to_pseudo[dest];
245 store_expr (src, x, 0, false);
246 }
247 else
248 x = expand_expr (src, SA.partition_to_pseudo[dest],
249 dest_mode, EXPAND_NORMAL);
250
251 if (x != SA.partition_to_pseudo[dest])
252 emit_move_insn (SA.partition_to_pseudo[dest], x);
253 seq = get_insns ();
254 end_sequence ();
255
256 insert_insn_on_edge (seq, e);
257 }
258
259 /* Insert a copy instruction from RTL expression SRC to partition DEST
260 onto edge E. */
261
262 static void
263 insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
264 source_location locus)
265 {
266 rtx seq;
267 if (dump_file && (dump_flags & TDF_DETAILS))
268 {
269 fprintf (dump_file,
270 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
271 e->src->index,
272 e->dest->index, dest);
273 print_simple_rtl (dump_file, src);
274 fprintf (dump_file, "\n");
275 }
276
277 gcc_assert (SA.partition_to_pseudo[dest]);
278
279 set_location_for_edge (e);
280 /* If a locus is provided, override the default. */
281 if (locus)
282 set_curr_insn_location (locus);
283
284 /* We give the destination as sizeexp in case src/dest are BLKmode
285 mems. Usually we give the source. As we result from SSA names
286 the left and right size should be the same (and no WITH_SIZE_EXPR
287 involved), so it doesn't matter. */
288 seq = emit_partition_copy (SA.partition_to_pseudo[dest],
289 src, unsignedsrcp,
290 partition_to_var (SA.map, dest));
291
292 insert_insn_on_edge (seq, e);
293 }
294
295 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
296 onto edge E. */
297
298 static void
299 insert_part_to_rtx_on_edge (edge e, rtx dest, int src, source_location locus)
300 {
301 tree var;
302 rtx seq;
303 if (dump_file && (dump_flags & TDF_DETAILS))
304 {
305 fprintf (dump_file,
306 "Inserting a temp copy on edge BB%d->BB%d : ",
307 e->src->index,
308 e->dest->index);
309 print_simple_rtl (dump_file, dest);
310 fprintf (dump_file, "= PART.%d\n", src);
311 }
312
313 gcc_assert (SA.partition_to_pseudo[src]);
314
315 set_location_for_edge (e);
316 /* If a locus is provided, override the default. */
317 if (locus)
318 set_curr_insn_location (locus);
319
320 var = partition_to_var (SA.map, src);
321 seq = emit_partition_copy (dest,
322 SA.partition_to_pseudo[src],
323 TYPE_UNSIGNED (TREE_TYPE (var)),
324 var);
325
326 insert_insn_on_edge (seq, e);
327 }
328
329
330 /* Create an elimination graph with SIZE nodes and associated data
331 structures. */
332
333 static elim_graph
334 new_elim_graph (int size)
335 {
336 elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
337
338 g->nodes.create (30);
339 g->const_dests.create (20);
340 g->const_copies.create (20);
341 g->copy_locus.create (10);
342 g->edge_list.create (20);
343 g->edge_locus.create (10);
344 g->stack.create (30);
345
346 g->visited = sbitmap_alloc (size);
347
348 return g;
349 }
350
351
352 /* Empty elimination graph G. */
353
354 static inline void
355 clear_elim_graph (elim_graph g)
356 {
357 g->nodes.truncate (0);
358 g->edge_list.truncate (0);
359 g->edge_locus.truncate (0);
360 }
361
362
363 /* Delete elimination graph G. */
364
365 static inline void
366 delete_elim_graph (elim_graph g)
367 {
368 sbitmap_free (g->visited);
369 g->stack.release ();
370 g->edge_list.release ();
371 g->const_copies.release ();
372 g->const_dests.release ();
373 g->nodes.release ();
374 g->copy_locus.release ();
375 g->edge_locus.release ();
376
377 free (g);
378 }
379
380
381 /* Return the number of nodes in graph G. */
382
383 static inline int
384 elim_graph_size (elim_graph g)
385 {
386 return g->nodes.length ();
387 }
388
389
390 /* Add NODE to graph G, if it doesn't exist already. */
391
392 static inline void
393 elim_graph_add_node (elim_graph g, int node)
394 {
395 int x;
396 int t;
397
398 FOR_EACH_VEC_ELT (g->nodes, x, t)
399 if (t == node)
400 return;
401 g->nodes.safe_push (node);
402 }
403
404
405 /* Add the edge PRED->SUCC to graph G. */
406
407 static inline void
408 elim_graph_add_edge (elim_graph g, int pred, int succ, source_location locus)
409 {
410 g->edge_list.safe_push (pred);
411 g->edge_list.safe_push (succ);
412 g->edge_locus.safe_push (locus);
413 }
414
415
416 /* Remove an edge from graph G for which NODE is the predecessor, and
417 return the successor node. -1 is returned if there is no such edge. */
418
419 static inline int
420 elim_graph_remove_succ_edge (elim_graph g, int node, source_location *locus)
421 {
422 int y;
423 unsigned x;
424 for (x = 0; x < g->edge_list.length (); x += 2)
425 if (g->edge_list[x] == node)
426 {
427 g->edge_list[x] = -1;
428 y = g->edge_list[x + 1];
429 g->edge_list[x + 1] = -1;
430 *locus = g->edge_locus[x / 2];
431 g->edge_locus[x / 2] = UNKNOWN_LOCATION;
432 return y;
433 }
434 *locus = UNKNOWN_LOCATION;
435 return -1;
436 }
437
438
439 /* Find all the nodes in GRAPH which are successors to NODE in the
440 edge list. VAR will hold the partition number found. CODE is the
441 code fragment executed for every node found. */
442
443 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
444 do { \
445 unsigned x_; \
446 int y_; \
447 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
448 { \
449 y_ = (GRAPH)->edge_list[x_]; \
450 if (y_ != (NODE)) \
451 continue; \
452 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
453 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
454 CODE; \
455 } \
456 } while (0)
457
458
459 /* Find all the nodes which are predecessors of NODE in the edge list for
460 GRAPH. VAR will hold the partition number found. CODE is the
461 code fragment executed for every node found. */
462
463 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
464 do { \
465 unsigned x_; \
466 int y_; \
467 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
468 { \
469 y_ = (GRAPH)->edge_list[x_ + 1]; \
470 if (y_ != (NODE)) \
471 continue; \
472 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
473 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
474 CODE; \
475 } \
476 } while (0)
477
478
479 /* Add T to elimination graph G. */
480
481 static inline void
482 eliminate_name (elim_graph g, int T)
483 {
484 elim_graph_add_node (g, T);
485 }
486
487
488 /* Build elimination graph G for basic block BB on incoming PHI edge
489 G->e. */
490
491 static void
492 eliminate_build (elim_graph g)
493 {
494 tree Ti;
495 int p0, pi;
496 gimple_stmt_iterator gsi;
497
498 clear_elim_graph (g);
499
500 for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
501 {
502 gimple phi = gsi_stmt (gsi);
503 source_location locus;
504
505 p0 = var_to_partition (g->map, gimple_phi_result (phi));
506 /* Ignore results which are not in partitions. */
507 if (p0 == NO_PARTITION)
508 continue;
509
510 Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
511 locus = gimple_phi_arg_location_from_edge (phi, g->e);
512
513 /* If this argument is a constant, or a SSA_NAME which is being
514 left in SSA form, just queue a copy to be emitted on this
515 edge. */
516 if (!phi_ssa_name_p (Ti)
517 || (TREE_CODE (Ti) == SSA_NAME
518 && var_to_partition (g->map, Ti) == NO_PARTITION))
519 {
520 /* Save constant copies until all other copies have been emitted
521 on this edge. */
522 g->const_dests.safe_push (p0);
523 g->const_copies.safe_push (Ti);
524 g->copy_locus.safe_push (locus);
525 }
526 else
527 {
528 pi = var_to_partition (g->map, Ti);
529 if (p0 != pi)
530 {
531 eliminate_name (g, p0);
532 eliminate_name (g, pi);
533 elim_graph_add_edge (g, p0, pi, locus);
534 }
535 }
536 }
537 }
538
539
540 /* Push successors of T onto the elimination stack for G. */
541
542 static void
543 elim_forward (elim_graph g, int T)
544 {
545 int S;
546 source_location locus;
547
548 bitmap_set_bit (g->visited, T);
549 FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus,
550 {
551 if (!bitmap_bit_p (g->visited, S))
552 elim_forward (g, S);
553 });
554 g->stack.safe_push (T);
555 }
556
557
558 /* Return 1 if there unvisited predecessors of T in graph G. */
559
560 static int
561 elim_unvisited_predecessor (elim_graph g, int T)
562 {
563 int P;
564 source_location locus;
565
566 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
567 {
568 if (!bitmap_bit_p (g->visited, P))
569 return 1;
570 });
571 return 0;
572 }
573
574 /* Process predecessors first, and insert a copy. */
575
576 static void
577 elim_backward (elim_graph g, int T)
578 {
579 int P;
580 source_location locus;
581
582 bitmap_set_bit (g->visited, T);
583 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
584 {
585 if (!bitmap_bit_p (g->visited, P))
586 {
587 elim_backward (g, P);
588 insert_partition_copy_on_edge (g->e, P, T, locus);
589 }
590 });
591 }
592
593 /* Allocate a new pseudo register usable for storing values sitting
594 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
595
596 static rtx
597 get_temp_reg (tree name)
598 {
599 tree var = TREE_CODE (name) == SSA_NAME ? SSA_NAME_VAR (name) : name;
600 tree type = TREE_TYPE (var);
601 int unsignedp;
602 enum machine_mode reg_mode = promote_decl_mode (var, &unsignedp);
603 rtx x = gen_reg_rtx (reg_mode);
604 if (POINTER_TYPE_P (type))
605 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var))));
606 return x;
607 }
608
609 /* Insert required copies for T in graph G. Check for a strongly connected
610 region, and create a temporary to break the cycle if one is found. */
611
612 static void
613 elim_create (elim_graph g, int T)
614 {
615 int P, S;
616 source_location locus;
617
618 if (elim_unvisited_predecessor (g, T))
619 {
620 tree var = partition_to_var (g->map, T);
621 rtx U = get_temp_reg (var);
622 int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
623
624 insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION);
625 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
626 {
627 if (!bitmap_bit_p (g->visited, P))
628 {
629 elim_backward (g, P);
630 insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus);
631 }
632 });
633 }
634 else
635 {
636 S = elim_graph_remove_succ_edge (g, T, &locus);
637 if (S != -1)
638 {
639 bitmap_set_bit (g->visited, T);
640 insert_partition_copy_on_edge (g->e, T, S, locus);
641 }
642 }
643 }
644
645
646 /* Eliminate all the phi nodes on edge E in graph G. */
647
648 static void
649 eliminate_phi (edge e, elim_graph g)
650 {
651 int x;
652
653 gcc_assert (g->const_copies.length () == 0);
654 gcc_assert (g->copy_locus.length () == 0);
655
656 /* Abnormal edges already have everything coalesced. */
657 if (e->flags & EDGE_ABNORMAL)
658 return;
659
660 g->e = e;
661
662 eliminate_build (g);
663
664 if (elim_graph_size (g) != 0)
665 {
666 int part;
667
668 bitmap_clear (g->visited);
669 g->stack.truncate (0);
670
671 FOR_EACH_VEC_ELT (g->nodes, x, part)
672 {
673 if (!bitmap_bit_p (g->visited, part))
674 elim_forward (g, part);
675 }
676
677 bitmap_clear (g->visited);
678 while (g->stack.length () > 0)
679 {
680 x = g->stack.pop ();
681 if (!bitmap_bit_p (g->visited, x))
682 elim_create (g, x);
683 }
684 }
685
686 /* If there are any pending constant copies, issue them now. */
687 while (g->const_copies.length () > 0)
688 {
689 int dest;
690 tree src;
691 source_location locus;
692
693 src = g->const_copies.pop ();
694 dest = g->const_dests.pop ();
695 locus = g->copy_locus.pop ();
696 insert_value_copy_on_edge (e, dest, src, locus);
697 }
698 }
699
700
701 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
702 check to see if this allows another PHI node to be removed. */
703
704 static void
705 remove_gimple_phi_args (gimple phi)
706 {
707 use_operand_p arg_p;
708 ssa_op_iter iter;
709
710 if (dump_file && (dump_flags & TDF_DETAILS))
711 {
712 fprintf (dump_file, "Removing Dead PHI definition: ");
713 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
714 }
715
716 FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
717 {
718 tree arg = USE_FROM_PTR (arg_p);
719 if (TREE_CODE (arg) == SSA_NAME)
720 {
721 /* Remove the reference to the existing argument. */
722 SET_USE (arg_p, NULL_TREE);
723 if (has_zero_uses (arg))
724 {
725 gimple stmt;
726 gimple_stmt_iterator gsi;
727
728 stmt = SSA_NAME_DEF_STMT (arg);
729
730 /* Also remove the def if it is a PHI node. */
731 if (gimple_code (stmt) == GIMPLE_PHI)
732 {
733 remove_gimple_phi_args (stmt);
734 gsi = gsi_for_stmt (stmt);
735 remove_phi_node (&gsi, true);
736 }
737
738 }
739 }
740 }
741 }
742
743 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
744
745 static void
746 eliminate_useless_phis (void)
747 {
748 basic_block bb;
749 gimple_stmt_iterator gsi;
750 tree result;
751
752 FOR_EACH_BB (bb)
753 {
754 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
755 {
756 gimple phi = gsi_stmt (gsi);
757 result = gimple_phi_result (phi);
758 if (virtual_operand_p (result))
759 {
760 #ifdef ENABLE_CHECKING
761 size_t i;
762 /* There should be no arguments which are not virtual, or the
763 results will be incorrect. */
764 for (i = 0; i < gimple_phi_num_args (phi); i++)
765 {
766 tree arg = PHI_ARG_DEF (phi, i);
767 if (TREE_CODE (arg) == SSA_NAME
768 && !virtual_operand_p (arg))
769 {
770 fprintf (stderr, "Argument of PHI is not virtual (");
771 print_generic_expr (stderr, arg, TDF_SLIM);
772 fprintf (stderr, "), but the result is :");
773 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
774 internal_error ("SSA corruption");
775 }
776 }
777 #endif
778 remove_phi_node (&gsi, true);
779 }
780 else
781 {
782 /* Also remove real PHIs with no uses. */
783 if (has_zero_uses (result))
784 {
785 remove_gimple_phi_args (phi);
786 remove_phi_node (&gsi, true);
787 }
788 else
789 gsi_next (&gsi);
790 }
791 }
792 }
793 }
794
795
796 /* This function will rewrite the current program using the variable mapping
797 found in MAP. If the replacement vector VALUES is provided, any
798 occurrences of partitions with non-null entries in the vector will be
799 replaced with the expression in the vector instead of its mapped
800 variable. */
801
802 static void
803 rewrite_trees (var_map map ATTRIBUTE_UNUSED)
804 {
805 #ifdef ENABLE_CHECKING
806 basic_block bb;
807 /* Search for PHIs where the destination has no partition, but one
808 or more arguments has a partition. This should not happen and can
809 create incorrect code. */
810 FOR_EACH_BB (bb)
811 {
812 gimple_stmt_iterator gsi;
813 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
814 {
815 gimple phi = gsi_stmt (gsi);
816 tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
817 if (T0 == NULL_TREE)
818 {
819 size_t i;
820 for (i = 0; i < gimple_phi_num_args (phi); i++)
821 {
822 tree arg = PHI_ARG_DEF (phi, i);
823
824 if (TREE_CODE (arg) == SSA_NAME
825 && var_to_partition (map, arg) != NO_PARTITION)
826 {
827 fprintf (stderr, "Argument of PHI is in a partition :(");
828 print_generic_expr (stderr, arg, TDF_SLIM);
829 fprintf (stderr, "), but the result is not :");
830 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
831 internal_error ("SSA corruption");
832 }
833 }
834 }
835 }
836 }
837 #endif
838 }
839
840 /* Given the out-of-ssa info object SA (with prepared partitions)
841 eliminate all phi nodes in all basic blocks. Afterwards no
842 basic block will have phi nodes anymore and there are possibly
843 some RTL instructions inserted on edges. */
844
845 void
846 expand_phi_nodes (struct ssaexpand *sa)
847 {
848 basic_block bb;
849 elim_graph g = new_elim_graph (sa->map->num_partitions);
850 g->map = sa->map;
851
852 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
853 if (!gimple_seq_empty_p (phi_nodes (bb)))
854 {
855 edge e;
856 edge_iterator ei;
857 FOR_EACH_EDGE (e, ei, bb->preds)
858 eliminate_phi (e, g);
859 set_phi_nodes (bb, NULL);
860 /* We can't redirect EH edges in RTL land, so we need to do this
861 here. Redirection happens only when splitting is necessary,
862 which it is only for critical edges, normally. For EH edges
863 it might also be necessary when the successor has more than
864 one predecessor. In that case the edge is either required to
865 be fallthru (which EH edges aren't), or the predecessor needs
866 to end with a jump (which again, isn't the case with EH edges).
867 Hence, split all EH edges on which we inserted instructions
868 and whose successor has multiple predecessors. */
869 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
870 {
871 if (e->insns.r && (e->flags & EDGE_EH)
872 && !single_pred_p (e->dest))
873 {
874 rtx insns = e->insns.r;
875 basic_block bb;
876 e->insns.r = NULL_RTX;
877 bb = split_edge (e);
878 single_pred_edge (bb)->insns.r = insns;
879 }
880 else
881 ei_next (&ei);
882 }
883 }
884
885 delete_elim_graph (g);
886 }
887
888
889 /* Remove the ssa-names in the current function and translate them into normal
890 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
891 should also be used. */
892
893 static void
894 remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
895 {
896 bitmap values = NULL;
897 var_map map;
898 unsigned i;
899
900 map = coalesce_ssa_name ();
901
902 /* Return to viewing the variable list as just all reference variables after
903 coalescing has been performed. */
904 partition_view_normal (map, false);
905
906 if (dump_file && (dump_flags & TDF_DETAILS))
907 {
908 fprintf (dump_file, "After Coalescing:\n");
909 dump_var_map (dump_file, map);
910 }
911
912 if (perform_ter)
913 {
914 values = find_replaceable_exprs (map);
915 if (values && dump_file && (dump_flags & TDF_DETAILS))
916 dump_replaceable_exprs (dump_file, values);
917 }
918
919 rewrite_trees (map);
920
921 sa->map = map;
922 sa->values = values;
923 sa->partition_has_default_def = BITMAP_ALLOC (NULL);
924 for (i = 1; i < num_ssa_names; i++)
925 {
926 tree t = ssa_name (i);
927 if (t && SSA_NAME_IS_DEFAULT_DEF (t))
928 {
929 int p = var_to_partition (map, t);
930 if (p != NO_PARTITION)
931 bitmap_set_bit (sa->partition_has_default_def, p);
932 }
933 }
934 }
935
936
937 /* If not already done so for basic block BB, assign increasing uids
938 to each of its instructions. */
939
940 static void
941 maybe_renumber_stmts_bb (basic_block bb)
942 {
943 unsigned i = 0;
944 gimple_stmt_iterator gsi;
945
946 if (!bb->aux)
947 return;
948 bb->aux = NULL;
949 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
950 {
951 gimple stmt = gsi_stmt (gsi);
952 gimple_set_uid (stmt, i);
953 i++;
954 }
955 }
956
957
958 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
959 of a PHI node) and ARG (one of its arguments) conflict. Return false
960 otherwise, also when we simply aren't sure. */
961
962 static bool
963 trivially_conflicts_p (basic_block bb, tree result, tree arg)
964 {
965 use_operand_p use;
966 imm_use_iterator imm_iter;
967 gimple defa = SSA_NAME_DEF_STMT (arg);
968
969 /* If ARG isn't defined in the same block it's too complicated for
970 our little mind. */
971 if (gimple_bb (defa) != bb)
972 return false;
973
974 FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
975 {
976 gimple use_stmt = USE_STMT (use);
977 if (is_gimple_debug (use_stmt))
978 continue;
979 /* Now, if there's a use of RESULT that lies outside this basic block,
980 then there surely is a conflict with ARG. */
981 if (gimple_bb (use_stmt) != bb)
982 return true;
983 if (gimple_code (use_stmt) == GIMPLE_PHI)
984 continue;
985 /* The use now is in a real stmt of BB, so if ARG was defined
986 in a PHI node (like RESULT) both conflict. */
987 if (gimple_code (defa) == GIMPLE_PHI)
988 return true;
989 maybe_renumber_stmts_bb (bb);
990 /* If the use of RESULT occurs after the definition of ARG,
991 the two conflict too. */
992 if (gimple_uid (defa) < gimple_uid (use_stmt))
993 return true;
994 }
995
996 return false;
997 }
998
999
1000 /* Search every PHI node for arguments associated with backedges which
1001 we can trivially determine will need a copy (the argument is either
1002 not an SSA_NAME or the argument has a different underlying variable
1003 than the PHI result).
1004
1005 Insert a copy from the PHI argument to a new destination at the
1006 end of the block with the backedge to the top of the loop. Update
1007 the PHI argument to reference this new destination. */
1008
1009 static void
1010 insert_backedge_copies (void)
1011 {
1012 basic_block bb;
1013 gimple_stmt_iterator gsi;
1014
1015 mark_dfs_back_edges ();
1016
1017 FOR_EACH_BB (bb)
1018 {
1019 /* Mark block as possibly needing calculation of UIDs. */
1020 bb->aux = &bb->aux;
1021
1022 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1023 {
1024 gimple phi = gsi_stmt (gsi);
1025 tree result = gimple_phi_result (phi);
1026 size_t i;
1027
1028 if (virtual_operand_p (result))
1029 continue;
1030
1031 for (i = 0; i < gimple_phi_num_args (phi); i++)
1032 {
1033 tree arg = gimple_phi_arg_def (phi, i);
1034 edge e = gimple_phi_arg_edge (phi, i);
1035
1036 /* If the argument is not an SSA_NAME, then we will need a
1037 constant initialization. If the argument is an SSA_NAME with
1038 a different underlying variable then a copy statement will be
1039 needed. */
1040 if ((e->flags & EDGE_DFS_BACK)
1041 && (TREE_CODE (arg) != SSA_NAME
1042 || SSA_NAME_VAR (arg) != SSA_NAME_VAR (result)
1043 || trivially_conflicts_p (bb, result, arg)))
1044 {
1045 tree name;
1046 gimple stmt, last = NULL;
1047 gimple_stmt_iterator gsi2;
1048
1049 gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
1050 if (!gsi_end_p (gsi2))
1051 last = gsi_stmt (gsi2);
1052
1053 /* In theory the only way we ought to get back to the
1054 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1055 However, better safe than sorry.
1056 If the block ends with a control statement or
1057 something that might throw, then we have to
1058 insert this assignment before the last
1059 statement. Else insert it after the last statement. */
1060 if (last && stmt_ends_bb_p (last))
1061 {
1062 /* If the last statement in the block is the definition
1063 site of the PHI argument, then we can't insert
1064 anything after it. */
1065 if (TREE_CODE (arg) == SSA_NAME
1066 && SSA_NAME_DEF_STMT (arg) == last)
1067 continue;
1068 }
1069
1070 /* Create a new instance of the underlying variable of the
1071 PHI result. */
1072 name = copy_ssa_name (result, NULL);
1073 stmt = gimple_build_assign (name,
1074 gimple_phi_arg_def (phi, i));
1075
1076 /* copy location if present. */
1077 if (gimple_phi_arg_has_location (phi, i))
1078 gimple_set_location (stmt,
1079 gimple_phi_arg_location (phi, i));
1080
1081 /* Insert the new statement into the block and update
1082 the PHI node. */
1083 if (last && stmt_ends_bb_p (last))
1084 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1085 else
1086 gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1087 SET_PHI_ARG_DEF (phi, i, name);
1088 }
1089 }
1090 }
1091
1092 /* Unmark this block again. */
1093 bb->aux = NULL;
1094 }
1095 }
1096
1097 /* Free all memory associated with going out of SSA form. SA is
1098 the outof-SSA info object. */
1099
1100 void
1101 finish_out_of_ssa (struct ssaexpand *sa)
1102 {
1103 free (sa->partition_to_pseudo);
1104 if (sa->values)
1105 BITMAP_FREE (sa->values);
1106 delete_var_map (sa->map);
1107 BITMAP_FREE (sa->partition_has_default_def);
1108 memset (sa, 0, sizeof *sa);
1109 }
1110
1111 /* Take the current function out of SSA form, translating PHIs as described in
1112 R. Morgan, ``Building an Optimizing Compiler'',
1113 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1114
1115 unsigned int
1116 rewrite_out_of_ssa (struct ssaexpand *sa)
1117 {
1118 /* If elimination of a PHI requires inserting a copy on a backedge,
1119 then we will have to split the backedge which has numerous
1120 undesirable performance effects.
1121
1122 A significant number of such cases can be handled here by inserting
1123 copies into the loop itself. */
1124 insert_backedge_copies ();
1125
1126
1127 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1128 eliminate_useless_phis ();
1129
1130 if (dump_file && (dump_flags & TDF_DETAILS))
1131 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1132
1133 remove_ssa_form (flag_tree_ter, sa);
1134
1135 if (dump_file && (dump_flags & TDF_DETAILS))
1136 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1137
1138 return 0;
1139 }