OSDN Git Service

PR tree-optimization/34618
[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-ssa-live.h"
34 #include "tree-pass.h"
35 #include "toplev.h"
36
37
38 /* Used to hold all the components required to do SSA PHI elimination.
39    The node and pred/succ list is a simple linear list of nodes and
40    edges represented as pairs of nodes.
41
42    The predecessor and successor list:  Nodes are entered in pairs, where
43    [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent 
44    predecessors, all the odd elements are successors. 
45    
46    Rationale:
47    When implemented as bitmaps, very large programs SSA->Normal times were 
48    being dominated by clearing the interference graph.
49
50    Typically this list of edges is extremely small since it only includes 
51    PHI results and uses from a single edge which have not coalesced with 
52    each other.  This means that no virtual PHI nodes are included, and
53    empirical evidence suggests that the number of edges rarely exceed
54    3, and in a bootstrap of GCC, the maximum size encountered was 7.
55    This also limits the number of possible nodes that are involved to
56    rarely more than 6, and in the bootstrap of gcc, the maximum number
57    of nodes encountered was 12.  */
58  
59 typedef struct _elim_graph {
60   /* Size of the elimination vectors.  */
61   int size;
62
63   /* List of nodes in the elimination graph.  */
64   VEC(tree,heap) *nodes;
65
66   /*  The predecessor and successor edge list.  */
67   VEC(int,heap) *edge_list;
68
69   /* Visited vector.  */
70   sbitmap visited;
71
72   /* Stack for visited nodes.  */
73   VEC(int,heap) *stack;
74   
75   /* The variable partition map.  */
76   var_map map;
77
78   /* Edge being eliminated by this graph.  */
79   edge e;
80
81   /* List of constant copies to emit.  These are pushed on in pairs.  */
82   VEC(tree,heap) *const_copies;
83 } *elim_graph;
84
85
86 /* Create a temporary variable based on the type of variable T.  Use T's name
87    as the prefix.  */
88
89 static tree
90 create_temp (tree t)
91 {
92   tree tmp;
93   const char *name = NULL;
94   tree type;
95
96   if (TREE_CODE (t) == SSA_NAME)
97     t = SSA_NAME_VAR (t);
98
99   gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
100
101   type = TREE_TYPE (t);
102   tmp = DECL_NAME (t);
103   if (tmp)
104     name = IDENTIFIER_POINTER (tmp);
105
106   if (name == NULL)
107     name = "temp";
108   tmp = create_tmp_var (type, name);
109
110   if (DECL_DEBUG_EXPR_IS_FROM (t) && DECL_DEBUG_EXPR (t))
111     {
112       SET_DECL_DEBUG_EXPR (tmp, DECL_DEBUG_EXPR (t));  
113       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
114     }
115   else if (!DECL_IGNORED_P (t))
116     {
117       SET_DECL_DEBUG_EXPR (tmp, t);
118       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
119     }
120   DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
121   DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
122   DECL_GIMPLE_REG_P (tmp) = DECL_GIMPLE_REG_P (t);
123   add_referenced_var (tmp);
124
125   /* add_referenced_var will create the annotation and set up some
126      of the flags in the annotation.  However, some flags we need to
127      inherit from our original variable.  */
128   set_symbol_mem_tag (tmp, symbol_mem_tag (t));
129   if (is_call_clobbered (t))
130     mark_call_clobbered (tmp, var_ann (t)->escape_mask);
131
132   return tmp;
133 }
134
135
136 /* This helper function fill insert a copy from a constant or variable SRC to 
137    variable DEST on edge E.  */
138
139 static void
140 insert_copy_on_edge (edge e, tree dest, tree src)
141 {
142   tree copy;
143
144   copy = build_gimple_modify_stmt (dest, src);
145   set_is_used (dest);
146
147   if (TREE_CODE (src) == ADDR_EXPR)
148     src = TREE_OPERAND (src, 0);
149   if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
150     set_is_used (src);
151
152   if (dump_file && (dump_flags & TDF_DETAILS))
153     {
154       fprintf (dump_file,
155                "Inserting a copy on edge BB%d->BB%d :",
156                e->src->index,
157                e->dest->index);
158       print_generic_expr (dump_file, copy, dump_flags);
159       fprintf (dump_file, "\n");
160     }
161
162   bsi_insert_on_edge (e, copy);
163 }
164
165
166 /* Create an elimination graph with SIZE nodes and associated data
167    structures.  */
168
169 static elim_graph
170 new_elim_graph (int size)
171 {
172   elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
173
174   g->nodes = VEC_alloc (tree, heap, 30);
175   g->const_copies = VEC_alloc (tree, heap, 20);
176   g->edge_list = VEC_alloc (int, heap, 20);
177   g->stack = VEC_alloc (int, heap, 30);
178   
179   g->visited = sbitmap_alloc (size);
180
181   return g;
182 }
183
184
185 /* Empty elimination graph G.  */
186
187 static inline void
188 clear_elim_graph (elim_graph g)
189 {
190   VEC_truncate (tree, g->nodes, 0);
191   VEC_truncate (int, g->edge_list, 0);
192 }
193
194
195 /* Delete elimination graph G.  */
196
197 static inline void
198 delete_elim_graph (elim_graph g)
199 {
200   sbitmap_free (g->visited);
201   VEC_free (int, heap, g->stack);
202   VEC_free (int, heap, g->edge_list);
203   VEC_free (tree, heap, g->const_copies);
204   VEC_free (tree, heap, g->nodes);
205   free (g);
206 }
207
208
209 /* Return the number of nodes in graph G.  */
210
211 static inline int
212 elim_graph_size (elim_graph g)
213 {
214   return VEC_length (tree, g->nodes);
215 }
216
217
218 /* Add NODE to graph G, if it doesn't exist already.  */
219
220 static inline void 
221 elim_graph_add_node (elim_graph g, tree node)
222 {
223   int x;
224   tree t;
225
226   for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++)
227     if (t == node)
228       return;
229   VEC_safe_push (tree, heap, g->nodes, node);
230 }
231
232
233 /* Add the edge PRED->SUCC to graph G.  */
234
235 static inline void
236 elim_graph_add_edge (elim_graph g, int pred, int succ)
237 {
238   VEC_safe_push (int, heap, g->edge_list, pred);
239   VEC_safe_push (int, heap, g->edge_list, succ);
240 }
241
242
243 /* Remove an edge from graph G for which NODE is the predecessor, and
244    return the successor node.  -1 is returned if there is no such edge.  */
245
246 static inline int
247 elim_graph_remove_succ_edge (elim_graph g, int node)
248 {
249   int y;
250   unsigned x;
251   for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
252     if (VEC_index (int, g->edge_list, x) == node)
253       {
254         VEC_replace (int, g->edge_list, x, -1);
255         y = VEC_index (int, g->edge_list, x + 1);
256         VEC_replace (int, g->edge_list, x + 1, -1);
257         return y;
258       }
259   return -1;
260 }
261
262
263 /* Find all the nodes in GRAPH which are successors to NODE in the
264    edge list.  VAR will hold the partition number found.  CODE is the
265    code fragment executed for every node found.  */
266
267 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE)                \
268 do {                                                                    \
269   unsigned x_;                                                          \
270   int y_;                                                               \
271   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
272     {                                                                   \
273       y_ = VEC_index (int, (GRAPH)->edge_list, x_);                     \
274       if (y_ != (NODE))                                                 \
275         continue;                                                       \
276       (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1);              \
277       CODE;                                                             \
278     }                                                                   \
279 } while (0)
280
281
282 /* Find all the nodes which are predecessors of NODE in the edge list for
283    GRAPH.  VAR will hold the partition number found.  CODE is the
284    code fragment executed for every node found.  */
285
286 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE)                \
287 do {                                                                    \
288   unsigned x_;                                                          \
289   int y_;                                                               \
290   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
291     {                                                                   \
292       y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1);                 \
293       if (y_ != (NODE))                                                 \
294         continue;                                                       \
295       (VAR) = VEC_index (int, (GRAPH)->edge_list, x_);                  \
296       CODE;                                                             \
297     }                                                                   \
298 } while (0)
299
300
301 /* Add T to elimination graph G.  */
302
303 static inline void
304 eliminate_name (elim_graph g, tree T)
305 {
306   elim_graph_add_node (g, T);
307 }
308
309
310 /* Build elimination graph G for basic block BB on incoming PHI edge
311    G->e.  */
312
313 static void
314 eliminate_build (elim_graph g, basic_block B)
315 {
316   tree phi;
317   tree T0, Ti;
318   int p0, pi;
319
320   clear_elim_graph (g);
321   
322   for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi))
323     {
324       T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
325       
326       /* Ignore results which are not in partitions.  */
327       if (T0 == NULL_TREE)
328         continue;
329
330       Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
331
332       /* If this argument is a constant, or a SSA_NAME which is being
333          left in SSA form, just queue a copy to be emitted on this
334          edge.  */
335       if (!phi_ssa_name_p (Ti)
336           || (TREE_CODE (Ti) == SSA_NAME
337               && var_to_partition (g->map, Ti) == NO_PARTITION))
338         {
339           /* Save constant copies until all other copies have been emitted
340              on this edge.  */
341           VEC_safe_push (tree, heap, g->const_copies, T0);
342           VEC_safe_push (tree, heap, g->const_copies, Ti);
343         }
344       else
345         {
346           Ti = var_to_partition_to_var (g->map, Ti);
347           if (T0 != Ti)
348             {
349               eliminate_name (g, T0);
350               eliminate_name (g, Ti);
351               p0 = var_to_partition (g->map, T0);
352               pi = var_to_partition (g->map, Ti);
353               elim_graph_add_edge (g, p0, pi);
354             }
355         }
356     }
357 }
358
359
360 /* Push successors of T onto the elimination stack for G.  */
361
362 static void 
363 elim_forward (elim_graph g, int T)
364 {
365   int S;
366   SET_BIT (g->visited, T);
367   FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
368     {
369       if (!TEST_BIT (g->visited, S))
370         elim_forward (g, S);
371     });
372   VEC_safe_push (int, heap, g->stack, T);
373 }
374
375
376 /* Return 1 if there unvisited predecessors of T in graph G.  */
377
378 static int
379 elim_unvisited_predecessor (elim_graph g, int T)
380 {
381   int P;
382   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 
383     {
384       if (!TEST_BIT (g->visited, P))
385         return 1;
386     });
387   return 0;
388 }
389
390 /* Process predecessors first, and insert a copy.  */
391
392 static void
393 elim_backward (elim_graph g, int T)
394 {
395   int P;
396   SET_BIT (g->visited, T);
397   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 
398     {
399       if (!TEST_BIT (g->visited, P))
400         {
401           elim_backward (g, P);
402           insert_copy_on_edge (g->e, 
403                                partition_to_var (g->map, P), 
404                                partition_to_var (g->map, T));
405         }
406     });
407 }
408
409 /* Insert required copies for T in graph G.  Check for a strongly connected 
410    region, and create a temporary to break the cycle if one is found.  */
411
412 static void 
413 elim_create (elim_graph g, int T)
414 {
415   tree U;
416   int P, S;
417
418   if (elim_unvisited_predecessor (g, T))
419     {
420       U = create_temp (partition_to_var (g->map, T));
421       insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
422       FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 
423         {
424           if (!TEST_BIT (g->visited, P))
425             {
426               elim_backward (g, P);
427               insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
428             }
429         });
430     }
431   else
432     {
433       S = elim_graph_remove_succ_edge (g, T);
434       if (S != -1)
435         {
436           SET_BIT (g->visited, T);
437           insert_copy_on_edge (g->e, 
438                                partition_to_var (g->map, T), 
439                                partition_to_var (g->map, S));
440         }
441     }
442   
443 }
444
445
446 /* Eliminate all the phi nodes on edge E in graph G.  */
447
448 static void
449 eliminate_phi (edge e, elim_graph g)
450 {
451   int x;
452   basic_block B = e->dest;
453
454   gcc_assert (VEC_length (tree, g->const_copies) == 0);
455
456   /* Abnormal edges already have everything coalesced.  */
457   if (e->flags & EDGE_ABNORMAL)
458     return;
459
460   g->e = e;
461
462   eliminate_build (g, B);
463
464   if (elim_graph_size (g) != 0)
465     {
466       tree var;
467
468       sbitmap_zero (g->visited);
469       VEC_truncate (int, g->stack, 0);
470
471       for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++)
472         {
473           int p = var_to_partition (g->map, var);
474           if (!TEST_BIT (g->visited, p))
475             elim_forward (g, p);
476         }
477        
478       sbitmap_zero (g->visited);
479       while (VEC_length (int, g->stack) > 0)
480         {
481           x = VEC_pop (int, g->stack);
482           if (!TEST_BIT (g->visited, x))
483             elim_create (g, x);
484         }
485     }
486
487   /* If there are any pending constant copies, issue them now.  */
488   while (VEC_length (tree, g->const_copies) > 0)
489     {
490       tree src, dest;
491       src = VEC_pop (tree, g->const_copies);
492       dest = VEC_pop (tree, g->const_copies);
493       insert_copy_on_edge (e, dest, src);
494     }
495 }
496
497
498 /* Take the ssa-name var_map MAP, and assign real variables to each 
499    partition.  */
500
501 static void
502 assign_vars (var_map map)
503 {
504   int x, num;
505   tree var, root;
506   var_ann_t ann;
507
508   num = num_var_partitions (map);
509   for (x = 0; x < num; x++)
510     {
511       var = partition_to_var (map, x);
512       if (TREE_CODE (var) != SSA_NAME)
513         {
514           ann = var_ann (var);
515           /* It must already be coalesced.  */
516           gcc_assert (ann->out_of_ssa_tag == 1);
517           if (dump_file && (dump_flags & TDF_DETAILS))
518             {
519               fprintf (dump_file, "partition %d already has variable ", x);
520               print_generic_expr (dump_file, var, TDF_SLIM);
521               fprintf (dump_file, " assigned to it.\n");
522             }
523         }
524       else
525         {
526           root = SSA_NAME_VAR (var);
527           ann = var_ann (root);
528           /* If ROOT is already associated, create a new one.  */
529           if (ann->out_of_ssa_tag)
530             {
531               root = create_temp (root);
532               ann = var_ann (root);
533             }
534           /* ROOT has not been coalesced yet, so use it.  */
535           if (dump_file && (dump_flags & TDF_DETAILS))
536             {
537               fprintf (dump_file, "Partition %d is assigned to var ", x);
538               print_generic_stmt (dump_file, root, TDF_SLIM);
539             }
540           change_partition_var (map, root, x);
541         }
542     }
543 }
544
545
546 /* Replace use operand P with whatever variable it has been rewritten to based 
547    on the partitions in MAP.  EXPR is an optional expression vector over SSA 
548    versions which is used to replace P with an expression instead of a variable.
549    If the stmt is changed, return true.  */ 
550
551 static inline bool
552 replace_use_variable (var_map map, use_operand_p p, tree *expr)
553 {
554   tree new_var;
555   tree var = USE_FROM_PTR (p);
556
557   /* Check if we are replacing this variable with an expression.  */
558   if (expr)
559     {
560       int version = SSA_NAME_VERSION (var);
561       if (expr[version])
562         {
563           tree new_expr = GIMPLE_STMT_OPERAND (expr[version], 1);
564           SET_USE (p, new_expr);
565
566           /* Clear the stmt's RHS, or GC might bite us.  */
567           GIMPLE_STMT_OPERAND (expr[version], 1) = NULL_TREE;
568           return true;
569         }
570     }
571
572   new_var = var_to_partition_to_var (map, var);
573   if (new_var)
574     {
575       SET_USE (p, new_var);
576       set_is_used (new_var);
577       return true;
578     }
579   return false;
580 }
581
582
583 /* Replace def operand DEF_P with whatever variable it has been rewritten to 
584    based on the partitions in MAP.  EXPR is an optional expression vector over
585    SSA versions which is used to replace DEF_P with an expression instead of a 
586    variable.  If the stmt is changed, return true.  */ 
587
588 static inline bool
589 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
590 {
591   tree new_var;
592   tree var = DEF_FROM_PTR (def_p);
593
594   /* Do nothing if we are replacing this variable with an expression.  */
595   if (expr && expr[SSA_NAME_VERSION (var)])
596     return true;
597
598   new_var = var_to_partition_to_var (map, var);
599   if (new_var)
600     {
601       SET_DEF (def_p, new_var);
602       set_is_used (new_var);
603       return true;
604     }
605   return false;
606 }
607
608
609 /* Remove any PHI node which is a virtual PHI.  */
610
611 static void
612 eliminate_virtual_phis (void)
613 {
614   basic_block bb;
615   tree phi, next;
616
617   FOR_EACH_BB (bb)
618     {
619       for (phi = phi_nodes (bb); phi; phi = next)
620         {
621           next = PHI_CHAIN (phi);
622           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
623             {
624 #ifdef ENABLE_CHECKING
625               int i;
626               /* There should be no arguments of this PHI which are in
627                  the partition list, or we get incorrect results.  */
628               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
629                 {
630                   tree arg = PHI_ARG_DEF (phi, i);
631                   if (TREE_CODE (arg) == SSA_NAME 
632                       && is_gimple_reg (SSA_NAME_VAR (arg)))
633                     {
634                       fprintf (stderr, "Argument of PHI is not virtual (");
635                       print_generic_expr (stderr, arg, TDF_SLIM);
636                       fprintf (stderr, "), but the result is :");
637                       print_generic_stmt (stderr, phi, TDF_SLIM);
638                       internal_error ("SSA corruption");
639                     }
640                 }
641 #endif
642               remove_phi_node (phi, NULL_TREE, true);
643             }
644         }
645     }
646 }
647
648
649 /* This function will rewrite the current program using the variable mapping
650    found in MAP.  If the replacement vector VALUES is provided, any 
651    occurrences of partitions with non-null entries in the vector will be 
652    replaced with the expression in the vector instead of its mapped 
653    variable.  */
654
655 static void
656 rewrite_trees (var_map map, tree *values)
657 {
658   elim_graph g;
659   basic_block bb;
660   block_stmt_iterator si;
661   edge e;
662   tree phi;
663   bool changed;
664  
665 #ifdef ENABLE_CHECKING
666   /* Search for PHIs where the destination has no partition, but one
667      or more arguments has a partition.  This should not happen and can
668      create incorrect code.  */
669   FOR_EACH_BB (bb)
670     {
671       tree phi;
672       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
673         {
674           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
675           if (T0 == NULL_TREE)
676             {
677               int i;
678               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
679                 {
680                   tree arg = PHI_ARG_DEF (phi, i);
681
682                   if (TREE_CODE (arg) == SSA_NAME
683                       && var_to_partition (map, arg) != NO_PARTITION)
684                     {
685                       fprintf (stderr, "Argument of PHI is in a partition :(");
686                       print_generic_expr (stderr, arg, TDF_SLIM);
687                       fprintf (stderr, "), but the result is not :");
688                       print_generic_stmt (stderr, phi, TDF_SLIM);
689                       internal_error ("SSA corruption");
690                     }
691                 }
692             }
693         }
694     }
695 #endif
696
697   /* Replace PHI nodes with any required copies.  */
698   g = new_elim_graph (map->num_partitions);
699   g->map = map;
700   FOR_EACH_BB (bb)
701     {
702       for (si = bsi_start (bb); !bsi_end_p (si); )
703         {
704           tree stmt = bsi_stmt (si);
705           use_operand_p use_p, copy_use_p;
706           def_operand_p def_p;
707           bool remove = false, is_copy = false;
708           int num_uses = 0;
709           stmt_ann_t ann;
710           ssa_op_iter iter;
711
712           ann = stmt_ann (stmt);
713           changed = false;
714
715           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT 
716               && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == SSA_NAME))
717             is_copy = true;
718
719           copy_use_p = NULL_USE_OPERAND_P;
720           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
721             {
722               if (replace_use_variable (map, use_p, values))
723                 changed = true;
724               copy_use_p = use_p;
725               num_uses++;
726             }
727
728           if (num_uses != 1)
729             is_copy = false;
730
731           def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
732
733           if (def_p != NULL)
734             {
735               /* Mark this stmt for removal if it is the list of replaceable 
736                  expressions.  */
737               if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
738                 remove = true;
739               else
740                 {
741                   if (replace_def_variable (map, def_p, NULL))
742                     changed = true;
743                   /* If both SSA_NAMEs coalesce to the same variable,
744                      mark the now redundant copy for removal.  */
745                   if (is_copy)
746                     {
747                       gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
748                       if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
749                         remove = true;
750                     }
751                 }
752             }
753           else
754             FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
755               if (replace_def_variable (map, def_p, NULL))
756                 changed = true;
757
758           /* Remove any stmts marked for removal.  */
759           if (remove)
760             bsi_remove (&si, true);
761           else
762             {
763               if (changed)
764                 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
765                   tree_purge_dead_eh_edges (bb);
766               bsi_next (&si);
767             }
768         }
769
770       phi = phi_nodes (bb);
771       if (phi)
772         {
773           edge_iterator ei;
774           FOR_EACH_EDGE (e, ei, bb->preds)
775             eliminate_phi (e, g);
776         }
777     }
778
779   delete_elim_graph (g);
780 }
781
782 /* These are the local work structures used to determine the best place to 
783    insert the copies that were placed on edges by the SSA->normal pass..  */
784 static VEC(edge,heap) *edge_leader;
785 static VEC(tree,heap) *stmt_list;
786 static bitmap leader_has_match = NULL;
787 static edge leader_match = NULL;
788
789
790 /* Pass this function to make_forwarder_block so that all the edges with
791    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  E is the
792    edge to test for a match.  */
793
794 static inline bool 
795 same_stmt_list_p (edge e)
796 {
797   return (e->aux == (PTR) leader_match) ? true : false;
798 }
799
800
801 /* Return TRUE if S1 and S2 are equivalent copies.  */
802
803 static inline bool
804 identical_copies_p (const_tree s1, const_tree s2)
805 {
806 #ifdef ENABLE_CHECKING
807   gcc_assert (TREE_CODE (s1) == GIMPLE_MODIFY_STMT);
808   gcc_assert (TREE_CODE (s2) == GIMPLE_MODIFY_STMT);
809   gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s1, 0)));
810   gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s2, 0)));
811 #endif
812
813   if (GIMPLE_STMT_OPERAND (s1, 0) != GIMPLE_STMT_OPERAND (s2, 0))
814     return false;
815
816   s1 = GIMPLE_STMT_OPERAND (s1, 1);
817   s2 = GIMPLE_STMT_OPERAND (s2, 1);
818
819   if (s1 != s2)
820     return false;
821
822   return true;
823 }
824
825
826 /* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists
827    contain the same sequence of copies.  */
828
829 static inline bool 
830 identical_stmt_lists_p (const_edge e1, const_edge e2)
831 {
832   tree t1 = PENDING_STMT (e1);
833   tree t2 = PENDING_STMT (e2);
834   tree_stmt_iterator tsi1, tsi2;
835
836   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
837   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
838
839   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
840        !tsi_end_p (tsi1) && !tsi_end_p (tsi2); 
841        tsi_next (&tsi1), tsi_next (&tsi2))
842     {
843       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
844         break;
845     }
846
847   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
848     return false;
849
850   return true;
851 }
852
853
854 /* Allocate data structures used in analyze_edges_for_bb.   */
855
856 static void
857 init_analyze_edges_for_bb (void)
858 {
859   edge_leader = VEC_alloc (edge, heap, 25);
860   stmt_list = VEC_alloc (tree, heap, 25);
861   leader_has_match = BITMAP_ALLOC (NULL);
862 }
863
864
865 /* Free data structures used in analyze_edges_for_bb.   */
866
867 static void
868 fini_analyze_edges_for_bb (void)
869 {
870   VEC_free (edge, heap, edge_leader);
871   VEC_free (tree, heap, stmt_list);
872   BITMAP_FREE (leader_has_match);
873 }
874
875
876 /* Look at all the incoming edges to block BB, and decide where the best place
877    to insert the stmts on each edge are, and perform those insertions.  */
878
879 static void
880 analyze_edges_for_bb (basic_block bb)
881 {
882   edge e;
883   edge_iterator ei;
884   int count;
885   unsigned int x;
886   bool have_opportunity;
887   block_stmt_iterator bsi;
888   tree stmt;
889   edge single_edge = NULL;
890   bool is_label;
891   edge leader;
892
893   count = 0;
894
895   /* Blocks which contain at least one abnormal edge cannot use 
896      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
897      found on edges in these block.  */
898   have_opportunity = true;
899   FOR_EACH_EDGE (e, ei, bb->preds)
900     if (e->flags & EDGE_ABNORMAL)
901       {
902         have_opportunity = false;
903         break;
904       }
905
906   if (!have_opportunity)
907     {
908       FOR_EACH_EDGE (e, ei, bb->preds)
909         if (PENDING_STMT (e))
910           bsi_commit_one_edge_insert (e, NULL);
911       return;
912     }
913
914   /* Find out how many edges there are with interesting pending stmts on them.  
915      Commit the stmts on edges we are not interested in.  */
916   FOR_EACH_EDGE (e, ei, bb->preds)
917     {
918       if (PENDING_STMT (e))
919         {
920           gcc_assert (!(e->flags & EDGE_ABNORMAL));
921           if (e->flags & EDGE_FALLTHRU)
922             {
923               bsi = bsi_start (e->src);
924               if (!bsi_end_p (bsi))
925                 {
926                   stmt = bsi_stmt (bsi);
927                   bsi_next (&bsi);
928                   gcc_assert (stmt != NULL_TREE);
929                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
930                   /* Punt if it has non-label stmts, or isn't local.  */
931                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0)) 
932                       || !bsi_end_p (bsi))
933                     {
934                       bsi_commit_one_edge_insert (e, NULL);
935                       continue;
936                     }
937                 }
938             }
939           single_edge = e;
940           count++;
941         }
942     }
943
944   /* If there aren't at least 2 edges, no sharing will happen.  */
945   if (count < 2)
946     {
947       if (single_edge)
948         bsi_commit_one_edge_insert (single_edge, NULL);
949       return;
950     }
951
952   /* Ensure that we have empty worklists.  */
953 #ifdef ENABLE_CHECKING
954   gcc_assert (VEC_length (edge, edge_leader) == 0);
955   gcc_assert (VEC_length (tree, stmt_list) == 0);
956   gcc_assert (bitmap_empty_p (leader_has_match));
957 #endif
958
959   /* Find the "leader" block for each set of unique stmt lists.  Preference is
960      given to FALLTHRU blocks since they would need a GOTO to arrive at another
961      block.  The leader edge destination is the block which all the other edges
962      with the same stmt list will be redirected to.  */
963   have_opportunity = false;
964   FOR_EACH_EDGE (e, ei, bb->preds)
965     {
966       if (PENDING_STMT (e))
967         {
968           bool found = false;
969
970           /* Look for the same stmt list in edge leaders list.  */
971           for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
972             {
973               if (identical_stmt_lists_p (leader, e))
974                 {
975                   /* Give this edge the same stmt list pointer.  */
976                   PENDING_STMT (e) = NULL;
977                   e->aux = leader;
978                   bitmap_set_bit (leader_has_match, x);
979                   have_opportunity = found = true;
980                   break;
981                 }
982             }
983
984           /* If no similar stmt list, add this edge to the leader list.  */
985           if (!found)
986             {
987               VEC_safe_push (edge, heap, edge_leader, e);
988               VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
989             }
990         }
991      }
992
993   /* If there are no similar lists, just issue the stmts.  */
994   if (!have_opportunity)
995     {
996       for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
997         bsi_commit_one_edge_insert (leader, NULL);
998       VEC_truncate (edge, edge_leader, 0);
999       VEC_truncate (tree, stmt_list, 0);
1000       bitmap_clear (leader_has_match);
1001       return;
1002     }
1003
1004   if (dump_file)
1005     fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
1006              bb->index);
1007   
1008   /* For each common list, create a forwarding block and issue the stmt's
1009      in that block.  */
1010   for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
1011     if (bitmap_bit_p (leader_has_match, x))
1012       {
1013         edge new_edge;
1014         block_stmt_iterator bsi;
1015         tree curr_stmt_list;
1016
1017         leader_match = leader;
1018
1019         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
1020            for various PHI manipulations, so it gets cleared when calls are 
1021            made to make_forwarder_block(). So make sure the edge is clear, 
1022            and use the saved stmt list.  */
1023         PENDING_STMT (leader) = NULL;
1024         leader->aux = leader;
1025         curr_stmt_list = VEC_index (tree, stmt_list, x);
1026
1027         new_edge = make_forwarder_block (leader->dest, same_stmt_list_p, 
1028                                          NULL);
1029         bb = new_edge->dest;
1030         if (dump_file)
1031           {
1032             fprintf (dump_file, "Splitting BB %d for Common stmt list.  ", 
1033                      leader->dest->index);
1034             fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
1035             print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS);
1036           }
1037
1038         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
1039           {
1040             e->aux = NULL;
1041             if (dump_file)
1042               fprintf (dump_file, "  Edge (%d->%d) lands here.\n", 
1043                        e->src->index, e->dest->index);
1044           }
1045
1046         bsi = bsi_last (leader->dest);
1047         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
1048
1049         leader_match = NULL;
1050         /* We should never get a new block now.  */
1051       }
1052     else
1053       {
1054         PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
1055         bsi_commit_one_edge_insert (leader, NULL);
1056       }
1057
1058    
1059   /* Clear the working data structures.  */
1060   VEC_truncate (edge, edge_leader, 0);
1061   VEC_truncate (tree, stmt_list, 0);
1062   bitmap_clear (leader_has_match);
1063 }
1064
1065
1066 /* This function will analyze the insertions which were performed on edges,
1067    and decide whether they should be left on that edge, or whether it is more
1068    efficient to emit some subset of them in a single block.  All stmts are
1069    inserted somewhere.  */
1070
1071 static void
1072 perform_edge_inserts (void)
1073 {
1074   basic_block bb;
1075
1076   if (dump_file)
1077     fprintf(dump_file, "Analyzing Edge Insertions.\n");
1078
1079   /* analyze_edges_for_bb calls make_forwarder_block, which tries to
1080      incrementally update the dominator information.  Since we don't
1081      need dominator information after this pass, go ahead and free the
1082      dominator information.  */
1083   free_dominance_info (CDI_DOMINATORS);
1084   free_dominance_info (CDI_POST_DOMINATORS);
1085
1086   /* Allocate data structures used in analyze_edges_for_bb.   */
1087   init_analyze_edges_for_bb ();
1088
1089   FOR_EACH_BB (bb)
1090     analyze_edges_for_bb (bb);
1091
1092   analyze_edges_for_bb (EXIT_BLOCK_PTR);
1093
1094   /* Free data structures used in analyze_edges_for_bb.   */
1095   fini_analyze_edges_for_bb ();
1096
1097 #ifdef ENABLE_CHECKING
1098   {
1099     edge_iterator ei;
1100     edge e;
1101     FOR_EACH_BB (bb)
1102       {
1103         FOR_EACH_EDGE (e, ei, bb->preds)
1104           {
1105             if (PENDING_STMT (e))
1106               error (" Pending stmts not issued on PRED edge (%d, %d)\n", 
1107                      e->src->index, e->dest->index);
1108           }
1109         FOR_EACH_EDGE (e, ei, bb->succs)
1110           {
1111             if (PENDING_STMT (e))
1112               error (" Pending stmts not issued on SUCC edge (%d, %d)\n", 
1113                      e->src->index, e->dest->index);
1114           }
1115       }
1116     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1117       {
1118         if (PENDING_STMT (e))
1119           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n", 
1120                  e->src->index, e->dest->index);
1121       }
1122     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1123       {
1124         if (PENDING_STMT (e))
1125           error (" Pending stmts not issued on EXIT edge (%d, %d)\n", 
1126                  e->src->index, e->dest->index);
1127       }
1128   }
1129 #endif
1130 }
1131
1132
1133 /* Remove the ssa-names in the current function and translate them into normal
1134    compiler variables.  PERFORM_TER is true if Temporary Expression Replacement
1135    should also be used.  */
1136
1137 static void
1138 remove_ssa_form (bool perform_ter)
1139 {
1140   basic_block bb;
1141   tree phi, next;
1142   tree *values = NULL;
1143   var_map map;
1144
1145   map = coalesce_ssa_name ();
1146
1147   /* Return to viewing the variable list as just all reference variables after
1148      coalescing has been performed.  */
1149   partition_view_normal (map, false);
1150
1151   if (dump_file && (dump_flags & TDF_DETAILS))
1152     {
1153       fprintf (dump_file, "After Coalescing:\n");
1154       dump_var_map (dump_file, map);
1155     }
1156
1157   if (perform_ter)
1158     {
1159       values = find_replaceable_exprs (map);
1160       if (values && dump_file && (dump_flags & TDF_DETAILS))
1161         dump_replaceable_exprs (dump_file, values);
1162     }
1163
1164   /* Assign real variables to the partitions now.  */
1165   assign_vars (map);
1166
1167   if (dump_file && (dump_flags & TDF_DETAILS))
1168     {
1169       fprintf (dump_file, "After Base variable replacement:\n");
1170       dump_var_map (dump_file, map);
1171     }
1172
1173   rewrite_trees (map, values);
1174
1175   if (values)
1176     free (values);
1177
1178   /* Remove PHI nodes which have been translated back to real variables.  */
1179   FOR_EACH_BB (bb)
1180     {
1181       for (phi = phi_nodes (bb); phi; phi = next)
1182         {
1183           next = PHI_CHAIN (phi);
1184           remove_phi_node (phi, NULL_TREE, true);
1185         }
1186     }
1187
1188   /* If any copies were inserted on edges, analyze and insert them now.  */
1189   perform_edge_inserts ();
1190
1191   delete_var_map (map);
1192 }
1193
1194
1195 /* Search every PHI node for arguments associated with backedges which
1196    we can trivially determine will need a copy (the argument is either
1197    not an SSA_NAME or the argument has a different underlying variable
1198    than the PHI result).
1199
1200    Insert a copy from the PHI argument to a new destination at the
1201    end of the block with the backedge to the top of the loop.  Update
1202    the PHI argument to reference this new destination.  */
1203
1204 static void
1205 insert_backedge_copies (void)
1206 {
1207   basic_block bb;
1208
1209   FOR_EACH_BB (bb)
1210     {
1211       tree phi;
1212
1213       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1214         {
1215           tree result = PHI_RESULT (phi);
1216           tree result_var;
1217           int i;
1218
1219           if (!is_gimple_reg (result))
1220             continue;
1221
1222           result_var = SSA_NAME_VAR (result);
1223           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1224             {
1225               tree arg = PHI_ARG_DEF (phi, i);
1226               edge e = PHI_ARG_EDGE (phi, i);
1227
1228               /* If the argument is not an SSA_NAME, then we will need a 
1229                  constant initialization.  If the argument is an SSA_NAME with
1230                  a different underlying variable then a copy statement will be 
1231                  needed.  */
1232               if ((e->flags & EDGE_DFS_BACK)
1233                   && (TREE_CODE (arg) != SSA_NAME
1234                       || SSA_NAME_VAR (arg) != result_var))
1235                 {
1236                   tree stmt, name, last = NULL;
1237                   block_stmt_iterator bsi;
1238
1239                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
1240                   if (!bsi_end_p (bsi))
1241                     last = bsi_stmt (bsi);
1242
1243                   /* In theory the only way we ought to get back to the
1244                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
1245                      However, better safe than sorry. 
1246                      If the block ends with a control statement or
1247                      something that might throw, then we have to
1248                      insert this assignment before the last
1249                      statement.  Else insert it after the last statement.  */
1250                   if (last && stmt_ends_bb_p (last))
1251                     {
1252                       /* If the last statement in the block is the definition
1253                          site of the PHI argument, then we can't insert
1254                          anything after it.  */
1255                       if (TREE_CODE (arg) == SSA_NAME
1256                           && SSA_NAME_DEF_STMT (arg) == last)
1257                         continue;
1258                     }
1259
1260                   /* Create a new instance of the underlying variable of the 
1261                      PHI result.  */
1262                   stmt = build_gimple_modify_stmt (NULL_TREE,
1263                                                    PHI_ARG_DEF (phi, i));
1264                   name = make_ssa_name (result_var, stmt);
1265                   GIMPLE_STMT_OPERAND (stmt, 0) = name;
1266
1267                   /* Insert the new statement into the block and update
1268                      the PHI node.  */
1269                   if (last && stmt_ends_bb_p (last))
1270                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
1271                   else
1272                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
1273                   SET_PHI_ARG_DEF (phi, i, name);
1274                 }
1275             }
1276         }
1277     }
1278 }
1279
1280 /* Take the current function out of SSA form, translating PHIs as described in
1281    R. Morgan, ``Building an Optimizing Compiler'',
1282    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
1283
1284 static unsigned int
1285 rewrite_out_of_ssa (void)
1286 {
1287   /* If elimination of a PHI requires inserting a copy on a backedge,
1288      then we will have to split the backedge which has numerous
1289      undesirable performance effects.
1290
1291      A significant number of such cases can be handled here by inserting
1292      copies into the loop itself.  */
1293   insert_backedge_copies ();
1294
1295   eliminate_virtual_phis ();
1296
1297   if (dump_file && (dump_flags & TDF_DETAILS))
1298     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1299
1300   remove_ssa_form (flag_tree_ter && !flag_mudflap);
1301
1302   if (dump_file && (dump_flags & TDF_DETAILS))
1303     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1304
1305   cfun->gimple_df->in_ssa_p = false;
1306   return 0;
1307 }
1308
1309
1310 /* Define the parameters of the out of SSA pass.  */
1311
1312 struct tree_opt_pass pass_del_ssa = 
1313 {
1314   "optimized",                          /* name */
1315   NULL,                                 /* gate */
1316   rewrite_out_of_ssa,                   /* execute */
1317   NULL,                                 /* sub */
1318   NULL,                                 /* next */
1319   0,                                    /* static_pass_number */
1320   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
1321   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1322   0,                                    /* properties_provided */
1323   /* ??? If TER is enabled, we also kill gimple.  */
1324   PROP_ssa,                             /* properties_destroyed */
1325   TODO_verify_ssa | TODO_verify_flow
1326     | TODO_verify_stmts,                /* todo_flags_start */
1327   TODO_dump_func
1328   | TODO_ggc_collect
1329   | TODO_remove_unused_locals,          /* todo_flags_finish */
1330   0                                     /* letter */
1331 };