OSDN Git Service

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