OSDN Git Service

* tree-outof-ssa.c (_elim_graph): Change the type of nodes and
[pf3gnuchains/gcc-fork.git] / gcc / tree-outof-ssa.c
1 /* Convert a program in SSA form into Normal form.
2    Copyright (C) 2004, 2005 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 2, 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 COPYING.  If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "flags.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "ggc.h"
31 #include "langhooks.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
34 #include "output.h"
35 #include "errors.h"
36 #include "expr.h"
37 #include "function.h"
38 #include "diagnostic.h"
39 #include "bitmap.h"
40 #include "tree-flow.h"
41 #include "tree-gimple.h"
42 #include "tree-inline.h"
43 #include "varray.h"
44 #include "timevar.h"
45 #include "hashtab.h"
46 #include "tree-dump.h"
47 #include "tree-ssa-live.h"
48 #include "tree-pass.h"
49
50 /* Flags to pass to remove_ssa_form.  */
51
52 #define SSANORM_PERFORM_TER             0x1
53 #define SSANORM_COMBINE_TEMPS           0x2
54 #define SSANORM_COALESCE_PARTITIONS     0x4
55
56 /* Used to hold all the components required to do SSA PHI elimination.
57    The node and pred/succ list is a simple linear list of nodes and
58    edges represented as pairs of nodes.
59
60    The predecessor and successor list:  Nodes are entered in pairs, where
61    [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent 
62    predecessors, all the odd elements are successors. 
63    
64    Rationale:
65    When implemented as bitmaps, very large programs SSA->Normal times were 
66    being dominated by clearing the interference graph.
67
68    Typically this list of edges is extremely small since it only includes 
69    PHI results and uses from a single edge which have not coalesced with 
70    each other.  This means that no virtual PHI nodes are included, and
71    empirical evidence suggests that the number of edges rarely exceed
72    3, and in a bootstrap of GCC, the maximum size encountered was 7.
73    This also limits the number of possible nodes that are involved to
74    rarely more than 6, and in the bootstrap of gcc, the maximum number
75    of nodes encountered was 12.  */
76  
77 typedef struct _elim_graph {
78   /* Size of the elimination vectors.  */
79   int size;
80
81   /* List of nodes in the elimination graph.  */
82   VEC(tree,heap) *nodes;
83
84   /*  The predecessor and successor edge list.  */
85   varray_type edge_list;
86
87   /* Visited vector.  */
88   sbitmap visited;
89
90   /* Stack for visited nodes.  */
91   varray_type stack;
92   
93   /* The variable partition map.  */
94   var_map map;
95
96   /* Edge being eliminated by this graph.  */
97   edge e;
98
99   /* List of constant copies to emit.  These are pushed on in pairs.  */
100   VEC(tree,heap) *const_copies;
101 } *elim_graph;
102
103
104 /* Local functions.  */
105 static tree create_temp (tree);
106 static void insert_copy_on_edge (edge, tree, tree);
107 static elim_graph new_elim_graph (int);
108 static inline void delete_elim_graph (elim_graph);
109 static inline void clear_elim_graph (elim_graph);
110 static inline int elim_graph_size (elim_graph);
111 static inline void elim_graph_add_node (elim_graph, tree);
112 static inline void elim_graph_add_edge (elim_graph, int, int);
113 static inline int elim_graph_remove_succ_edge (elim_graph, int);
114
115 static inline void eliminate_name (elim_graph, tree);
116 static void eliminate_build (elim_graph, basic_block);
117 static void elim_forward (elim_graph, int);
118 static int elim_unvisited_predecessor (elim_graph, int);
119 static void elim_backward (elim_graph, int);
120 static void elim_create (elim_graph, int);
121 static void eliminate_phi (edge, elim_graph);
122 static tree_live_info_p coalesce_ssa_name (var_map, int);
123 static void assign_vars (var_map);
124 static bool replace_use_variable (var_map, use_operand_p, tree *);
125 static bool replace_def_variable (var_map, def_operand_p, tree *);
126 static void eliminate_virtual_phis (void);
127 static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
128 static void print_exprs (FILE *, const char *, tree, const char *, tree,
129                          const char *);
130 static void print_exprs_edge (FILE *, edge, const char *, tree, const char *,
131                               tree);
132
133
134 /* Create a temporary variable based on the type of variable T.  Use T's name
135    as the prefix.  */
136
137 static tree
138 create_temp (tree t)
139 {
140   tree tmp;
141   const char *name = NULL;
142   tree type;
143
144   if (TREE_CODE (t) == SSA_NAME)
145     t = SSA_NAME_VAR (t);
146
147   gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
148
149   type = TREE_TYPE (t);
150   tmp = DECL_NAME (t);
151   if (tmp)
152     name = IDENTIFIER_POINTER (tmp);
153
154   if (name == NULL)
155     name = "temp";
156   tmp = create_tmp_var (type, name);
157
158   if (DECL_DEBUG_EXPR (t) && DECL_DEBUG_EXPR_IS_FROM (t))
159     {
160       DECL_DEBUG_EXPR (tmp) = DECL_DEBUG_EXPR (t);  
161       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
162     }
163   else if (!DECL_IGNORED_P (t))
164     {
165       DECL_DEBUG_EXPR (tmp) = t;
166       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
167     }
168   DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
169   DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
170   add_referenced_tmp_var (tmp);
171
172   /* add_referenced_tmp_var will create the annotation and set up some
173      of the flags in the annotation.  However, some flags we need to
174      inherit from our original variable.  */
175   var_ann (tmp)->type_mem_tag = var_ann (t)->type_mem_tag;
176   if (is_call_clobbered (t))
177     mark_call_clobbered (tmp);
178
179   return tmp;
180 }
181
182
183 /* This helper function fill insert a copy from a constant or variable SRC to 
184    variable DEST on edge E.  */
185
186 static void
187 insert_copy_on_edge (edge e, tree dest, tree src)
188 {
189   tree copy;
190
191   copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
192   set_is_used (dest);
193
194   if (TREE_CODE (src) == ADDR_EXPR)
195     src = TREE_OPERAND (src, 0);
196   if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
197     set_is_used (src);
198
199   if (dump_file && (dump_flags & TDF_DETAILS))
200     {
201       fprintf (dump_file,
202                "Inserting a copy on edge BB%d->BB%d :",
203                e->src->index,
204                e->dest->index);
205       print_generic_expr (dump_file, copy, dump_flags);
206       fprintf (dump_file, "\n");
207     }
208
209   bsi_insert_on_edge (e, copy);
210 }
211
212
213 /* Create an elimination graph with SIZE nodes and associated data
214    structures.  */
215
216 static elim_graph
217 new_elim_graph (int size)
218 {
219   elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
220
221   g->nodes = VEC_alloc (tree, heap, 30);
222   g->const_copies = VEC_alloc (tree, heap, 20);
223   VARRAY_INT_INIT (g->edge_list, 20, "Elimination Edge List");
224   VARRAY_INT_INIT (g->stack, 30, " Elimination Stack");
225   
226   g->visited = sbitmap_alloc (size);
227
228   return g;
229 }
230
231
232 /* Empty elimination graph G.  */
233
234 static inline void
235 clear_elim_graph (elim_graph g)
236 {
237   VEC_truncate (tree, g->nodes, 0);
238   VARRAY_POP_ALL (g->edge_list);
239 }
240
241
242 /* Delete elimination graph G.  */
243
244 static inline void
245 delete_elim_graph (elim_graph g)
246 {
247   sbitmap_free (g->visited);
248   VEC_free (tree, heap, g->const_copies);
249   VEC_free (tree, heap, g->nodes);
250   free (g);
251 }
252
253
254 /* Return the number of nodes in graph G.  */
255
256 static inline int
257 elim_graph_size (elim_graph g)
258 {
259   return VEC_length (tree, g->nodes);
260 }
261
262
263 /* Add NODE to graph G, if it doesn't exist already.  */
264
265 static inline void 
266 elim_graph_add_node (elim_graph g, tree node)
267 {
268   int x;
269   tree t;
270
271   for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++)
272     if (t == node)
273       return;
274   VEC_safe_push (tree, heap, g->nodes, node);
275 }
276
277
278 /* Add the edge PRED->SUCC to graph G.  */
279
280 static inline void
281 elim_graph_add_edge (elim_graph g, int pred, int succ)
282 {
283   VARRAY_PUSH_INT (g->edge_list, pred);
284   VARRAY_PUSH_INT (g->edge_list, succ);
285 }
286
287
288 /* Remove an edge from graph G for which NODE is the predecessor, and
289    return the successor node.  -1 is returned if there is no such edge.  */
290
291 static inline int
292 elim_graph_remove_succ_edge (elim_graph g, int node)
293 {
294   int y;
295   unsigned x;
296   for (x = 0; x < VARRAY_ACTIVE_SIZE (g->edge_list); x += 2)
297     if (VARRAY_INT (g->edge_list, x) == node)
298       {
299         VARRAY_INT (g->edge_list, x) = -1;
300         y = VARRAY_INT (g->edge_list, x + 1);
301         VARRAY_INT (g->edge_list, x + 1) = -1;
302         return y;
303       }
304   return -1;
305 }
306
307
308 /* Find all the nodes in GRAPH which are successors to NODE in the
309    edge list.  VAR will hold the partition number found.  CODE is the
310    code fragment executed for every node found.  */
311
312 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE)                \
313 do {                                                                    \
314   unsigned x_;                                                          \
315   int y_;                                                               \
316   for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2)   \
317     {                                                                   \
318       y_ = VARRAY_INT ((GRAPH)->edge_list, x_);                         \
319       if (y_ != (NODE))                                                 \
320         continue;                                                       \
321       (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_ + 1);                  \
322       CODE;                                                             \
323     }                                                                   \
324 } while (0)
325
326
327 /* Find all the nodes which are predecessors of NODE in the edge list for
328    GRAPH.  VAR will hold the partition number found.  CODE is the
329    code fragment executed for every node found.  */
330
331 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE)                \
332 do {                                                                    \
333   unsigned x_;                                                          \
334   int y_;                                                               \
335   for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2)   \
336     {                                                                   \
337       y_ = VARRAY_INT ((GRAPH)->edge_list, x_ + 1);                     \
338       if (y_ != (NODE))                                                 \
339         continue;                                                       \
340       (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_);                      \
341       CODE;                                                             \
342     }                                                                   \
343 } while (0)
344
345
346 /* Add T to elimination graph G.  */
347
348 static inline void
349 eliminate_name (elim_graph g, tree T)
350 {
351   elim_graph_add_node (g, T);
352 }
353
354
355 /* Build elimination graph G for basic block BB on incoming PHI edge
356    G->e.  */
357
358 static void
359 eliminate_build (elim_graph g, basic_block B)
360 {
361   tree phi;
362   tree T0, Ti;
363   int p0, pi;
364
365   clear_elim_graph (g);
366   
367   for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi))
368     {
369       T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
370       
371       /* Ignore results which are not in partitions.  */
372       if (T0 == NULL_TREE)
373         continue;
374
375       Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
376
377       /* If this argument is a constant, or a SSA_NAME which is being
378          left in SSA form, just queue a copy to be emitted on this
379          edge.  */
380       if (!phi_ssa_name_p (Ti)
381           || (TREE_CODE (Ti) == SSA_NAME
382               && var_to_partition (g->map, Ti) == NO_PARTITION))
383         {
384           /* Save constant copies until all other copies have been emitted
385              on this edge.  */
386           VEC_safe_push (tree, heap, g->const_copies, T0);
387           VEC_safe_push (tree, heap, g->const_copies, Ti);
388         }
389       else
390         {
391           Ti = var_to_partition_to_var (g->map, Ti);
392           if (T0 != Ti)
393             {
394               eliminate_name (g, T0);
395               eliminate_name (g, Ti);
396               p0 = var_to_partition (g->map, T0);
397               pi = var_to_partition (g->map, Ti);
398               elim_graph_add_edge (g, p0, pi);
399             }
400         }
401     }
402 }
403
404
405 /* Push successors of T onto the elimination stack for G.  */
406
407 static void 
408 elim_forward (elim_graph g, int T)
409 {
410   int S;
411   SET_BIT (g->visited, T);
412   FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
413     {
414       if (!TEST_BIT (g->visited, S))
415         elim_forward (g, S);
416     });
417   VARRAY_PUSH_INT (g->stack, T);
418 }
419
420
421 /* Return 1 if there unvisited predecessors of T in graph G.  */
422
423 static int
424 elim_unvisited_predecessor (elim_graph g, int T)
425 {
426   int P;
427   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 
428     {
429       if (!TEST_BIT (g->visited, P))
430         return 1;
431     });
432   return 0;
433 }
434
435 /* Process predecessors first, and insert a copy.  */
436
437 static void
438 elim_backward (elim_graph g, int T)
439 {
440   int P;
441   SET_BIT (g->visited, T);
442   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 
443     {
444       if (!TEST_BIT (g->visited, P))
445         {
446           elim_backward (g, P);
447           insert_copy_on_edge (g->e, 
448                                partition_to_var (g->map, P), 
449                                partition_to_var (g->map, T));
450         }
451     });
452 }
453
454 /* Insert required copies for T in graph G.  Check for a strongly connected 
455    region, and create a temporary to break the cycle if one is found.  */
456
457 static void 
458 elim_create (elim_graph g, int T)
459 {
460   tree U;
461   int P, S;
462
463   if (elim_unvisited_predecessor (g, T))
464     {
465       U = create_temp (partition_to_var (g->map, T));
466       insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
467       FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 
468         {
469           if (!TEST_BIT (g->visited, P))
470             {
471               elim_backward (g, P);
472               insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
473             }
474         });
475     }
476   else
477     {
478       S = elim_graph_remove_succ_edge (g, T);
479       if (S != -1)
480         {
481           SET_BIT (g->visited, T);
482           insert_copy_on_edge (g->e, 
483                                partition_to_var (g->map, T), 
484                                partition_to_var (g->map, S));
485         }
486     }
487   
488 }
489
490 /* Eliminate all the phi nodes on edge E in graph G.  */
491
492 static void
493 eliminate_phi (edge e, elim_graph g)
494 {
495   int x;
496   basic_block B = e->dest;
497
498   gcc_assert (VEC_length (tree, g->const_copies) == 0);
499
500   /* Abnormal edges already have everything coalesced.  */
501   if (e->flags & EDGE_ABNORMAL)
502     return;
503
504   g->e = e;
505
506   eliminate_build (g, B);
507
508   if (elim_graph_size (g) != 0)
509     {
510       tree var;
511
512       sbitmap_zero (g->visited);
513       VARRAY_POP_ALL (g->stack);
514
515       for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++)
516         {
517           int p = var_to_partition (g->map, var);
518           if (!TEST_BIT (g->visited, p))
519             elim_forward (g, p);
520         }
521        
522       sbitmap_zero (g->visited);
523       while (VARRAY_ACTIVE_SIZE (g->stack) > 0)
524         {
525           x = VARRAY_TOP_INT (g->stack);
526           VARRAY_POP (g->stack);
527           if (!TEST_BIT (g->visited, x))
528             elim_create (g, x);
529         }
530     }
531
532   /* If there are any pending constant copies, issue them now.  */
533   while (VEC_length (tree, g->const_copies) > 0)
534     {
535       tree src, dest;
536       src = VEC_pop (tree, g->const_copies);
537       dest = VEC_pop (tree, g->const_copies);
538       insert_copy_on_edge (e, dest, src);
539     }
540 }
541
542
543 /* Shortcut routine to print messages to file F of the form:
544    "STR1 EXPR1 STR2 EXPR2 STR3."  */
545
546 static void
547 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
548              tree expr2, const char *str3)
549 {
550   fprintf (f, "%s", str1);
551   print_generic_expr (f, expr1, TDF_SLIM);
552   fprintf (f, "%s", str2);
553   print_generic_expr (f, expr2, TDF_SLIM);
554   fprintf (f, "%s", str3);
555 }
556
557
558 /* Shortcut routine to print abnormal edge messages to file F of the form:
559    "STR1 EXPR1 STR2 EXPR2 across edge E.  */
560
561 static void
562 print_exprs_edge (FILE *f, edge e, const char *str1, tree expr1, 
563                   const char *str2, tree expr2)
564 {
565   print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge");
566   fprintf (f, " from BB%d->BB%d\n", e->src->index,
567                e->dest->index);
568 }
569
570
571 /* Coalesce partitions in MAP which are live across abnormal edges in GRAPH.
572    RV is the root variable groupings of the partitions in MAP.  Since code 
573    cannot be inserted on these edges, failure to coalesce something across
574    an abnormal edge is an error.  */
575
576 static void
577 coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv)
578 {
579   basic_block bb;
580   edge e;
581   tree phi, var, tmp;
582   int x, y, z;
583   edge_iterator ei;
584
585   /* Code cannot be inserted on abnormal edges. Look for all abnormal 
586      edges, and coalesce any PHI results with their arguments across 
587      that edge.  */
588
589   FOR_EACH_BB (bb)
590     FOR_EACH_EDGE (e, ei, bb->succs)
591       if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
592         for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
593           {
594             /* Visit each PHI on the destination side of this abnormal
595                edge, and attempt to coalesce the argument with the result.  */
596             var = PHI_RESULT (phi);
597             x = var_to_partition (map, var);
598
599             /* Ignore results which are not relevant.  */
600             if (x == NO_PARTITION)
601               continue;
602
603             tmp = PHI_ARG_DEF (phi, e->dest_idx);
604 #ifdef ENABLE_CHECKING
605             if (!phi_ssa_name_p (tmp))
606               {
607                 print_exprs_edge (stderr, e,
608                                   "\nConstant argument in PHI. Can't insert :",
609                                   var, " = ", tmp);
610                 internal_error ("SSA corruption");
611               }
612 #else
613             gcc_assert (phi_ssa_name_p (tmp));
614 #endif
615             y = var_to_partition (map, tmp);
616             gcc_assert (x != NO_PARTITION);
617             gcc_assert (y != NO_PARTITION);
618 #ifdef ENABLE_CHECKING
619             if (root_var_find (rv, x) != root_var_find (rv, y))
620               {
621                 print_exprs_edge (stderr, e, "\nDifferent root vars: ",
622                                   root_var (rv, root_var_find (rv, x)), 
623                                   " and ", 
624                                   root_var (rv, root_var_find (rv, y)));
625                 internal_error ("SSA corruption");
626               }
627 #else
628             gcc_assert (root_var_find (rv, x) == root_var_find (rv, y));
629 #endif
630
631             if (x != y)
632               {
633 #ifdef ENABLE_CHECKING
634                 if (conflict_graph_conflict_p (graph, x, y))
635                   {
636                     print_exprs_edge (stderr, e, "\n Conflict ", 
637                                       partition_to_var (map, x),
638                                       " and ", partition_to_var (map, y));
639                     internal_error ("SSA corruption");
640                   }
641 #else
642                 gcc_assert (!conflict_graph_conflict_p (graph, x, y));
643 #endif
644                 
645                 /* Now map the partitions back to their real variables.  */
646                 var = partition_to_var (map, x);
647                 tmp = partition_to_var (map, y);
648                 if (dump_file && (dump_flags & TDF_DETAILS))
649                   {
650                     print_exprs_edge (dump_file, e, 
651                                       "ABNORMAL: Coalescing ",
652                                       var, " and ", tmp);
653                   }
654                 z = var_union (map, var, tmp);
655 #ifdef ENABLE_CHECKING
656                 if (z == NO_PARTITION)
657                   {
658                     print_exprs_edge (stderr, e, "\nUnable to coalesce", 
659                                       partition_to_var (map, x), " and ", 
660                                       partition_to_var (map, y));
661                     internal_error ("SSA corruption");
662                   }
663 #else
664                 gcc_assert (z != NO_PARTITION);
665 #endif
666                 gcc_assert (z == x || z == y);
667                 if (z == x)
668                   conflict_graph_merge_regs (graph, x, y);
669                 else
670                   conflict_graph_merge_regs (graph, y, x);
671               }
672           }
673 }
674
675
676 /* Reduce the number of live ranges in MAP.  Live range information is 
677    returned if FLAGS indicates that we are combining temporaries, otherwise 
678    NULL is returned.  The only partitions which are associated with actual 
679    variables at this point are those which are forced to be coalesced for 
680    various reason. (live on entry, live across abnormal edges, etc.).  */
681
682 static tree_live_info_p
683 coalesce_ssa_name (var_map map, int flags)
684 {
685   unsigned num, x, i;
686   sbitmap live;
687   tree var, phi;
688   root_var_p rv;
689   tree_live_info_p liveinfo;
690   var_ann_t ann;
691   conflict_graph graph;
692   basic_block bb;
693   coalesce_list_p cl = NULL;
694
695   if (num_var_partitions (map) <= 1)
696     return NULL;
697
698   liveinfo = calculate_live_on_entry (map);
699   calculate_live_on_exit (liveinfo);
700   rv = root_var_init (map);
701
702   /* Remove single element variable from the list.  */
703   root_var_compact (rv);
704
705   cl = create_coalesce_list (map);
706
707   /* Add all potential copies via PHI arguments to the list.  */
708   FOR_EACH_BB (bb)
709     {
710       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
711         {
712           tree res = PHI_RESULT (phi);
713           int p = var_to_partition (map, res);
714           if (p == NO_PARTITION)
715             continue;
716           for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
717             {
718               tree arg = PHI_ARG_DEF (phi, x);
719               int p2;
720
721               if (TREE_CODE (arg) != SSA_NAME)
722                 continue;
723               if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
724                 continue;
725               p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
726               if (p2 != NO_PARTITION)
727                 add_coalesce (cl, p, p2, 1);
728             }
729         }
730     }
731
732   /* Coalesce all the result decls together.  */
733   var = NULL_TREE;
734   i = 0;
735   for (x = 0; x < num_var_partitions (map); x++)
736     {
737       tree p = partition_to_var (map, x);
738       if (TREE_CODE (SSA_NAME_VAR(p)) == RESULT_DECL)
739         {
740           if (var == NULL_TREE)
741             {
742               var = p;
743               i = x;
744             }
745           else
746             add_coalesce (cl, i, x, 1);
747         }
748     }
749
750   /* Build a conflict graph.  */
751   graph = build_tree_conflict_graph (liveinfo, rv, cl);
752
753   if (cl)
754     {
755       if (dump_file && (dump_flags & TDF_DETAILS))
756         {
757           fprintf (dump_file, "Before sorting:\n");
758           dump_coalesce_list (dump_file, cl);
759         }
760
761       sort_coalesce_list (cl);
762
763       if (dump_file && (dump_flags & TDF_DETAILS))
764         {
765           fprintf (dump_file, "\nAfter sorting:\n");
766           dump_coalesce_list (dump_file, cl);
767         }
768     }
769
770   /* Put the single element variables back in.  */
771   root_var_decompact (rv);
772
773   /* First, coalesce all live on entry variables to their root variable. 
774      This will ensure the first use is coming from the correct location.  */
775
776   live = sbitmap_alloc (num_var_partitions (map));
777   sbitmap_zero (live);
778
779   /* Set 'live' vector to indicate live on entry partitions.  */
780   num = num_var_partitions (map);
781   for (x = 0 ; x < num; x++)
782     {
783       var = partition_to_var (map, x);
784       if (default_def (SSA_NAME_VAR (var)) == var)
785         SET_BIT (live, x);
786     }
787
788   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
789     {
790       delete_tree_live_info (liveinfo);
791       liveinfo = NULL;
792     }
793
794   /* Assign root variable as partition representative for each live on entry
795      partition.  */
796   EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, 
797     {
798       var = root_var (rv, root_var_find (rv, x));
799       ann = var_ann (var);
800       /* If these aren't already coalesced...  */
801       if (partition_to_var (map, x) != var)
802         {
803           /* This root variable should have not already been assigned
804              to another partition which is not coalesced with this one.  */
805           gcc_assert (!ann->out_of_ssa_tag);
806
807           if (dump_file && (dump_flags & TDF_DETAILS))
808             {
809               print_exprs (dump_file, "Must coalesce ", 
810                            partition_to_var (map, x),
811                            " with the root variable ", var, ".\n");
812             }
813
814           change_partition_var (map, var, x);
815         }
816     });
817
818   sbitmap_free (live);
819
820   /* Coalesce partitions live across abnormal edges.  */
821   coalesce_abnormal_edges (map, graph, rv);
822
823   if (dump_file && (dump_flags & TDF_DETAILS))
824     dump_var_map (dump_file, map);
825
826   /* Coalesce partitions.  */
827   coalesce_tpa_members (rv, graph, map, cl,
828                         ((dump_flags & TDF_DETAILS) ? dump_file
829                          : NULL));
830
831   if (flags & SSANORM_COALESCE_PARTITIONS)
832     coalesce_tpa_members (rv, graph, map, NULL,
833                           ((dump_flags & TDF_DETAILS) ? dump_file
834                            : NULL));
835   if (cl)
836     delete_coalesce_list (cl);
837   root_var_delete (rv);
838   conflict_graph_delete (graph);
839
840   return liveinfo;
841 }
842
843
844 /* Take the ssa-name var_map MAP, and assign real variables to each 
845    partition.  */
846
847 static void
848 assign_vars (var_map map)
849 {
850   int x, i, num, rep;
851   tree t, var;
852   var_ann_t ann;
853   root_var_p rv;
854
855   rv = root_var_init (map);
856   if (!rv) 
857     return;
858
859   /* Coalescing may already have forced some partitions to their root 
860      variable. Find these and tag them.  */
861
862   num = num_var_partitions (map);
863   for (x = 0; x < num; x++)
864     {
865       var = partition_to_var (map, x);
866       if (TREE_CODE (var) != SSA_NAME)
867         {
868           /* Coalescing will already have verified that more than one
869              partition doesn't have the same root variable. Simply marked
870              the variable as assigned.  */
871           ann = var_ann (var);
872           ann->out_of_ssa_tag = 1;
873           if (dump_file && (dump_flags & TDF_DETAILS))
874             {
875               fprintf (dump_file, "partition %d has variable ", x);
876               print_generic_expr (dump_file, var, TDF_SLIM);
877               fprintf (dump_file, " assigned to it.\n");
878             }
879
880         }
881     }
882
883   num = root_var_num (rv);
884   for (x = 0; x < num; x++)
885     {
886       var = root_var (rv, x);
887       ann = var_ann (var);
888       for (i = root_var_first_partition (rv, x);
889            i != ROOT_VAR_NONE;
890            i = root_var_next_partition (rv, i))
891         {
892           t = partition_to_var (map, i);
893
894           if (t == var || TREE_CODE (t) != SSA_NAME)
895             continue;
896
897           rep = var_to_partition (map, t);
898           
899           if (!ann->out_of_ssa_tag)
900             {
901               if (dump_file && (dump_flags & TDF_DETAILS))
902                 print_exprs (dump_file, "", t, "  --> ", var, "\n");
903               change_partition_var (map, var, rep);
904               continue;
905             }
906
907           if (dump_file && (dump_flags & TDF_DETAILS))
908             print_exprs (dump_file, "", t, " not coalesced with ", var, 
909                          "");
910
911           var = create_temp (t);
912           change_partition_var (map, var, rep);
913           ann = var_ann (var);
914
915           if (dump_file && (dump_flags & TDF_DETAILS))
916             {
917               fprintf (dump_file, " -->  New temp:  '");
918               print_generic_expr (dump_file, var, TDF_SLIM);
919               fprintf (dump_file, "'\n");
920             }
921         }
922     }
923
924   root_var_delete (rv);
925 }
926
927
928 /* Replace use operand P with whatever variable it has been rewritten to based 
929    on the partitions in MAP.  EXPR is an optional expression vector over SSA 
930    versions which is used to replace P with an expression instead of a variable.
931    If the stmt is changed, return true.  */ 
932
933 static inline bool
934 replace_use_variable (var_map map, use_operand_p p, tree *expr)
935 {
936   tree new_var;
937   tree var = USE_FROM_PTR (p);
938
939   /* Check if we are replacing this variable with an expression.  */
940   if (expr)
941     {
942       int version = SSA_NAME_VERSION (var);
943       if (expr[version])
944         {
945           tree new_expr = TREE_OPERAND (expr[version], 1);
946           SET_USE (p, new_expr);
947           /* Clear the stmt's RHS, or GC might bite us.  */
948           TREE_OPERAND (expr[version], 1) = NULL_TREE;
949           return true;
950         }
951     }
952
953   new_var = var_to_partition_to_var (map, var);
954   if (new_var)
955     {
956       SET_USE (p, new_var);
957       set_is_used (new_var);
958       return true;
959     }
960   return false;
961 }
962
963
964 /* Replace def operand DEF_P with whatever variable it has been rewritten to 
965    based on the partitions in MAP.  EXPR is an optional expression vector over
966    SSA versions which is used to replace DEF_P with an expression instead of a 
967    variable.  If the stmt is changed, return true.  */ 
968
969 static inline bool
970 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
971 {
972   tree new_var;
973   tree var = DEF_FROM_PTR (def_p);
974
975   /* Check if we are replacing this variable with an expression.  */
976   if (expr)
977     {
978       int version = SSA_NAME_VERSION (var);
979       if (expr[version])
980         {
981           tree new_expr = TREE_OPERAND (expr[version], 1);
982           SET_DEF (def_p, new_expr);
983           /* Clear the stmt's RHS, or GC might bite us.  */
984           TREE_OPERAND (expr[version], 1) = NULL_TREE;
985           return true;
986         }
987     }
988
989   new_var = var_to_partition_to_var (map, var);
990   if (new_var)
991     {
992       SET_DEF (def_p, new_var);
993       set_is_used (new_var);
994       return true;
995     }
996   return false;
997 }
998
999
1000 /* Remove any PHI node which is a virtual PHI.  */
1001
1002 static void
1003 eliminate_virtual_phis (void)
1004 {
1005   basic_block bb;
1006   tree phi, next;
1007
1008   FOR_EACH_BB (bb)
1009     {
1010       for (phi = phi_nodes (bb); phi; phi = next)
1011         {
1012           next = PHI_CHAIN (phi);
1013           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1014             {
1015 #ifdef ENABLE_CHECKING
1016               int i;
1017               /* There should be no arguments of this PHI which are in
1018                  the partition list, or we get incorrect results.  */
1019               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1020                 {
1021                   tree arg = PHI_ARG_DEF (phi, i);
1022                   if (TREE_CODE (arg) == SSA_NAME 
1023                       && is_gimple_reg (SSA_NAME_VAR (arg)))
1024                     {
1025                       fprintf (stderr, "Argument of PHI is not virtual (");
1026                       print_generic_expr (stderr, arg, TDF_SLIM);
1027                       fprintf (stderr, "), but the result is :");
1028                       print_generic_stmt (stderr, phi, TDF_SLIM);
1029                       internal_error ("SSA corruption");
1030                     }
1031                 }
1032 #endif
1033               remove_phi_node (phi, NULL_TREE);
1034             }
1035         }
1036     }
1037 }
1038
1039
1040 /* This routine will coalesce variables in MAP of the same type which do not 
1041    interfere with each other. LIVEINFO is the live range info for variables
1042    of interest.  This will both reduce the memory footprint of the stack, and 
1043    allow us to coalesce together local copies of globals and scalarized 
1044    component refs.  */
1045
1046 static void
1047 coalesce_vars (var_map map, tree_live_info_p liveinfo)
1048 {
1049   basic_block bb;
1050   type_var_p tv;
1051   tree var;
1052   unsigned x, p, p2;
1053   coalesce_list_p cl;
1054   conflict_graph graph;
1055
1056   cl = create_coalesce_list (map);
1057
1058   /* Merge all the live on entry vectors for coalesced partitions.  */
1059   for (x = 0; x < num_var_partitions (map); x++)
1060     {
1061       var = partition_to_var (map, x);
1062       p = var_to_partition (map, var);
1063       if (p != x)
1064         live_merge_and_clear (liveinfo, p, x);
1065     }
1066
1067   /* When PHI nodes are turned into copies, the result of each PHI node
1068      becomes live on entry to the block. Mark these now.  */
1069   FOR_EACH_BB (bb)
1070     {
1071       tree phi, arg;
1072       unsigned p;
1073       
1074       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1075         {
1076           p = var_to_partition (map, PHI_RESULT (phi));
1077
1078           /* Skip virtual PHI nodes.  */
1079           if (p == (unsigned)NO_PARTITION)
1080             continue;
1081
1082           make_live_on_entry (liveinfo, bb, p);
1083
1084           /* Each argument is a potential copy operation. Add any arguments 
1085              which are not coalesced to the result to the coalesce list.  */
1086           for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
1087             {
1088               arg = PHI_ARG_DEF (phi, x);
1089               if (!phi_ssa_name_p (arg))
1090                 continue;
1091               p2 = var_to_partition (map, arg);
1092               if (p2 == (unsigned)NO_PARTITION)
1093                 continue;
1094               if (p != p2)
1095                 add_coalesce (cl, p, p2, 1);
1096             }
1097         }
1098    }
1099
1100   
1101   /* Re-calculate live on exit info.  */
1102   calculate_live_on_exit (liveinfo);
1103
1104   if (dump_file && (dump_flags & TDF_DETAILS))
1105     {
1106       fprintf (dump_file, "Live range info for variable memory coalescing.\n");
1107       dump_live_info (dump_file, liveinfo, LIVEDUMP_ALL);
1108
1109       fprintf (dump_file, "Coalesce list from phi nodes:\n");
1110       dump_coalesce_list (dump_file, cl);
1111     }
1112
1113
1114   tv = type_var_init (map);
1115   if (dump_file)
1116     type_var_dump (dump_file, tv);
1117   type_var_compact (tv);
1118   if (dump_file)
1119     type_var_dump (dump_file, tv);
1120
1121   graph = build_tree_conflict_graph (liveinfo, tv, cl);
1122
1123   type_var_decompact (tv);
1124   if (dump_file && (dump_flags & TDF_DETAILS))
1125     {
1126       fprintf (dump_file, "type var list now looks like:n");
1127       type_var_dump (dump_file, tv);
1128
1129       fprintf (dump_file, "Coalesce list after conflict graph build:\n");
1130       dump_coalesce_list (dump_file, cl);
1131     }
1132
1133   sort_coalesce_list (cl);
1134   if (dump_file && (dump_flags & TDF_DETAILS))
1135     {
1136       fprintf (dump_file, "Coalesce list after sorting:\n");
1137       dump_coalesce_list (dump_file, cl);
1138     }
1139
1140   coalesce_tpa_members (tv, graph, map, cl, 
1141                         ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1142
1143   type_var_delete (tv);
1144   delete_coalesce_list (cl);
1145 }
1146
1147
1148 /* Temporary Expression Replacement (TER)
1149
1150    Replace SSA version variables during out-of-ssa with their defining
1151    expression if there is only one use of the variable.
1152
1153    A pass is made through the function, one block at a time.  No cross block
1154    information is tracked.
1155
1156    Variables which only have one use, and whose defining stmt is considered
1157    a replaceable expression (see check_replaceable) are entered into 
1158    consideration by adding a list of dependent partitions to the version_info
1159    vector for that ssa_name_version.  This information comes from the partition
1160    mapping for each USE.  At the same time, the partition_dep_list vector for 
1161    these partitions have this version number entered into their lists.
1162
1163    When the use of a replaceable ssa_variable is encountered, the dependence
1164    list in version_info[] is moved to the "pending_dependence" list in case
1165    the current expression is also replaceable. (To be determined later in 
1166    processing this stmt.) version_info[] for the version is then updated to 
1167    point to the defining stmt and the 'replaceable' bit is set.
1168
1169    Any partition which is defined by a statement 'kills' any expression which
1170    is dependent on this partition.  Every ssa version in the partitions' 
1171    dependence list is removed from future consideration.
1172
1173    All virtual references are lumped together.  Any expression which is
1174    dependent on any virtual variable (via a VUSE) has a dependence added
1175    to the special partition defined by VIRTUAL_PARTITION.
1176
1177    Whenever a V_MAY_DEF is seen, all expressions dependent this 
1178    VIRTUAL_PARTITION are removed from consideration.
1179
1180    At the end of a basic block, all expression are removed from consideration
1181    in preparation for the next block.  
1182    
1183    The end result is a vector over SSA_NAME_VERSION which is passed back to
1184    rewrite_out_of_ssa.  As the SSA variables are being rewritten, instead of
1185    replacing the SSA_NAME tree element with the partition it was assigned, 
1186    it is replaced with the RHS of the defining expression.  */
1187
1188
1189 /* Dependency list element.  This can contain either a partition index or a
1190    version number, depending on which list it is in.  */
1191
1192 typedef struct value_expr_d 
1193 {
1194   int value;
1195   struct value_expr_d *next;
1196 } *value_expr_p;
1197
1198
1199 /* Temporary Expression Replacement (TER) table information.  */
1200
1201 typedef struct temp_expr_table_d 
1202 {
1203   var_map map;
1204   void **version_info;          
1205   value_expr_p *partition_dep_list;
1206   bitmap replaceable;
1207   bool saw_replaceable;
1208   int virtual_partition;
1209   bitmap partition_in_use;
1210   value_expr_p free_list;
1211   value_expr_p pending_dependence;
1212 } *temp_expr_table_p;
1213
1214 /* Used to indicate a dependency on V_MAY_DEFs.  */
1215 #define VIRTUAL_PARTITION(table)        (table->virtual_partition)
1216
1217 static temp_expr_table_p new_temp_expr_table (var_map);
1218 static tree *free_temp_expr_table (temp_expr_table_p);
1219 static inline value_expr_p new_value_expr (temp_expr_table_p);
1220 static inline void free_value_expr (temp_expr_table_p, value_expr_p);
1221 static inline value_expr_p find_value_in_list (value_expr_p, int, 
1222                                                value_expr_p *);
1223 static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
1224 static inline void add_info_to_list (temp_expr_table_p, value_expr_p *, 
1225                                      value_expr_p);
1226 static value_expr_p remove_value_from_list (value_expr_p *, int);
1227 static void add_dependance (temp_expr_table_p, int, tree);
1228 static bool check_replaceable (temp_expr_table_p, tree);
1229 static void finish_expr (temp_expr_table_p, int, bool);
1230 static void mark_replaceable (temp_expr_table_p, tree);
1231 static inline void kill_expr (temp_expr_table_p, int, bool);
1232 static inline void kill_virtual_exprs (temp_expr_table_p, bool);
1233 static void find_replaceable_in_bb (temp_expr_table_p, basic_block);
1234 static tree *find_replaceable_exprs (var_map);
1235 static void dump_replaceable_exprs (FILE *, tree *);
1236
1237
1238 /* Create a new TER table for MAP.  */
1239
1240 static temp_expr_table_p
1241 new_temp_expr_table (var_map map)
1242 {
1243   temp_expr_table_p t;
1244
1245   t = (temp_expr_table_p) xmalloc (sizeof (struct temp_expr_table_d));
1246   t->map = map;
1247
1248   t->version_info = xcalloc (num_ssa_names + 1, sizeof (void *));
1249   t->partition_dep_list = xcalloc (num_var_partitions (map) + 1, 
1250                                    sizeof (value_expr_p));
1251
1252   t->replaceable = BITMAP_ALLOC (NULL);
1253   t->partition_in_use = BITMAP_ALLOC (NULL);
1254
1255   t->saw_replaceable = false;
1256   t->virtual_partition = num_var_partitions (map);
1257   t->free_list = NULL;
1258   t->pending_dependence = NULL;
1259
1260   return t;
1261 }
1262
1263
1264 /* Free TER table T.  If there are valid replacements, return the expression 
1265    vector.  */
1266
1267 static tree *
1268 free_temp_expr_table (temp_expr_table_p t)
1269 {
1270   value_expr_p p;
1271   tree *ret = NULL;
1272
1273 #ifdef ENABLE_CHECKING
1274   unsigned x;
1275   for (x = 0; x <= num_var_partitions (t->map); x++)
1276     gcc_assert (!t->partition_dep_list[x]);
1277 #endif
1278
1279   while ((p = t->free_list))
1280     {
1281       t->free_list = p->next;
1282       free (p);
1283     }
1284
1285   BITMAP_FREE (t->partition_in_use);
1286   BITMAP_FREE (t->replaceable);
1287
1288   free (t->partition_dep_list);
1289   if (t->saw_replaceable)
1290     ret = (tree *)t->version_info;
1291   else
1292     free (t->version_info);
1293   
1294   free (t);
1295   return ret;
1296 }
1297
1298
1299 /* Allocate a new value list node. Take it from the free list in TABLE if 
1300    possible.  */
1301
1302 static inline value_expr_p
1303 new_value_expr (temp_expr_table_p table)
1304 {
1305   value_expr_p p;
1306   if (table->free_list)
1307     {
1308       p = table->free_list;
1309       table->free_list = p->next;
1310     }
1311   else
1312     p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
1313
1314   return p;
1315 }
1316
1317
1318 /* Add value list node P to the free list in TABLE.  */
1319
1320 static inline void
1321 free_value_expr (temp_expr_table_p table, value_expr_p p)
1322 {
1323   p->next = table->free_list;
1324   table->free_list = p;
1325 }
1326
1327
1328 /* Find VALUE if it's in LIST.  Return a pointer to the list object if found,  
1329    else return NULL.  If LAST_PTR is provided, it will point to the previous 
1330    item upon return, or NULL if this is the first item in the list.  */
1331
1332 static inline value_expr_p
1333 find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
1334 {
1335   value_expr_p curr;
1336   value_expr_p last = NULL;
1337
1338   for (curr = list; curr; last = curr, curr = curr->next)
1339     {
1340       if (curr->value == value)
1341         break;
1342     }
1343   if (last_ptr)
1344     *last_ptr = last;
1345   return curr;
1346 }
1347
1348
1349 /* Add VALUE to LIST, if it isn't already present.  TAB is the expression 
1350    table */
1351
1352 static inline void
1353 add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
1354 {
1355   value_expr_p info;
1356
1357   if (!find_value_in_list (*list, value, NULL))
1358     {
1359       info = new_value_expr (tab);
1360       info->value = value;
1361       info->next = *list;
1362       *list = info;
1363     }
1364 }
1365
1366
1367 /* Add value node INFO if it's value isn't already in LIST.  Free INFO if
1368    it is already in the list. TAB is the expression table.  */
1369
1370 static inline void
1371 add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
1372 {
1373   if (find_value_in_list (*list, info->value, NULL))
1374     free_value_expr (tab, info);
1375   else
1376     {
1377       info->next = *list;
1378       *list = info;
1379     }
1380 }
1381
1382
1383 /* Look for VALUE in LIST.  If found, remove it from the list and return it's 
1384    pointer.  */
1385
1386 static value_expr_p
1387 remove_value_from_list (value_expr_p *list, int value)
1388 {
1389   value_expr_p info, last;
1390
1391   info = find_value_in_list (*list, value, &last);
1392   if (!info)
1393     return NULL;
1394   if (!last)
1395     *list = info->next;
1396   else
1397     last->next = info->next;
1398  
1399   return info;
1400 }
1401
1402
1403 /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is 
1404    replaceable by an expression, add a dependence each of the elements of the 
1405    expression.  These are contained in the pending list.  TAB is the
1406    expression table.  */
1407
1408 static void
1409 add_dependance (temp_expr_table_p tab, int version, tree var)
1410 {
1411   int i, x;
1412   value_expr_p info;
1413
1414   i = SSA_NAME_VERSION (var);
1415   if (bitmap_bit_p (tab->replaceable, i))
1416     {
1417       /* This variable is being substituted, so use whatever dependences
1418          were queued up when we marked this as replaceable earlier.  */
1419       while ((info = tab->pending_dependence))
1420         {
1421           tab->pending_dependence = info->next;
1422           /* Get the partition this variable was dependent on. Reuse this
1423              object to represent the current  expression instead.  */
1424           x = info->value;
1425           info->value = version;
1426           add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
1427           add_value_to_list (tab, 
1428                              (value_expr_p *)&(tab->version_info[version]), x);
1429           bitmap_set_bit (tab->partition_in_use, x);
1430         }
1431     }
1432   else
1433     {
1434       i = var_to_partition (tab->map, var);
1435       gcc_assert (i != NO_PARTITION);
1436       add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
1437       add_value_to_list (tab, 
1438                          (value_expr_p *)&(tab->version_info[version]), i);
1439       bitmap_set_bit (tab->partition_in_use, i);
1440     }
1441 }
1442
1443
1444 /* Check if expression STMT is suitable for replacement in table TAB.  If so, 
1445    create an expression entry.  Return true if this stmt is replaceable.  */
1446
1447 static bool
1448 check_replaceable (temp_expr_table_p tab, tree stmt)
1449 {
1450   tree var, def;
1451   int version;
1452   var_map map = tab->map;
1453   ssa_op_iter iter;
1454   tree call_expr;
1455
1456   if (TREE_CODE (stmt) != MODIFY_EXPR)
1457     return false;
1458   
1459   /* Punt if there is more than 1 def, or more than 1 use.  */
1460   def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
1461   if (!def)
1462     return false;
1463
1464   if (version_ref_count (map, def) != 1)
1465     return false;
1466
1467   /* There must be no V_MAY_DEFS or V_MUST_DEFS.  */
1468   if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF))))
1469     return false;
1470
1471   /* Float expressions must go through memory if float-store is on.  */
1472   if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
1473     return false;
1474
1475   /* Calls to functions with side-effects cannot be replaced.  */
1476   if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
1477     {
1478       int call_flags = call_expr_flags (call_expr);
1479       if (TREE_SIDE_EFFECTS (call_expr)
1480           && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
1481         return false;
1482     }
1483
1484   version = SSA_NAME_VERSION (def);
1485
1486   /* Add this expression to the dependency list for each use partition.  */
1487   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1488     {
1489       add_dependance (tab, version, var);
1490     }
1491
1492   /* If there are VUSES, add a dependence on virtual defs.  */
1493   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
1494     {
1495       add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]), 
1496                          VIRTUAL_PARTITION (tab));
1497       add_value_to_list (tab, 
1498                          &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]), 
1499                          version);
1500       bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
1501     }
1502
1503   return true;
1504 }
1505
1506
1507 /* This function will remove the expression for VERSION from replacement 
1508    consideration.n table TAB  If 'replace' is true, it is marked as 
1509    replaceable, otherwise not.  */
1510
1511 static void
1512 finish_expr (temp_expr_table_p tab, int version, bool replace)
1513 {
1514   value_expr_p info, tmp;
1515   int partition;
1516
1517   /* Remove this expression from its dependent lists.  The partition dependence
1518      list is retained and transfered later to whomever uses this version.  */
1519   for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
1520     {
1521       partition = info->value;
1522       gcc_assert (tab->partition_dep_list[partition]);
1523       tmp = remove_value_from_list (&(tab->partition_dep_list[partition]), 
1524                                     version);
1525       gcc_assert (tmp);
1526       free_value_expr (tab, tmp);
1527       /* Only clear the bit when the dependency list is emptied via 
1528          a replacement. Otherwise kill_expr will take care of it.  */
1529       if (!(tab->partition_dep_list[partition]) && replace)
1530         bitmap_clear_bit (tab->partition_in_use, partition);
1531       tmp = info->next;
1532       if (!replace)
1533         free_value_expr (tab, info);
1534     }
1535
1536   if (replace)
1537     {
1538       tab->saw_replaceable = true;
1539       bitmap_set_bit (tab->replaceable, version);
1540     }
1541   else
1542     {
1543       gcc_assert (!bitmap_bit_p (tab->replaceable, version));
1544       tab->version_info[version] = NULL;
1545     }
1546 }
1547
1548
1549 /* Mark the expression associated with VAR as replaceable, and enter
1550    the defining stmt into the version_info table TAB.  */
1551
1552 static void
1553 mark_replaceable (temp_expr_table_p tab, tree var)
1554 {
1555   value_expr_p info;
1556   int version = SSA_NAME_VERSION (var);
1557   finish_expr (tab, version, true);
1558
1559   /* Move the dependence list to the pending list.  */
1560   if (tab->version_info[version])
1561     {
1562       info = (value_expr_p) tab->version_info[version]; 
1563       for ( ; info->next; info = info->next)
1564         continue;
1565       info->next = tab->pending_dependence;
1566       tab->pending_dependence = (value_expr_p)tab->version_info[version];
1567     }
1568
1569   tab->version_info[version] = SSA_NAME_DEF_STMT (var);
1570 }
1571
1572
1573 /* This function marks any expression in TAB which is dependent on PARTITION
1574    as NOT replaceable.  CLEAR_BIT is used to determine whether partition_in_use
1575    should have its bit cleared.  Since this routine can be called within an
1576    EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared.  */
1577
1578 static inline void
1579 kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
1580 {
1581   value_expr_p ptr;
1582
1583   /* Mark every active expr dependent on this var as not replaceable.  */
1584   while ((ptr = tab->partition_dep_list[partition]) != NULL)
1585     finish_expr (tab, ptr->value, false);
1586
1587   if (clear_bit)
1588     bitmap_clear_bit (tab->partition_in_use, partition);
1589 }
1590
1591
1592 /* This function kills all expressions in TAB which are dependent on virtual 
1593    DEFs.  CLEAR_BIT determines whether partition_in_use gets cleared.  */
1594
1595 static inline void
1596 kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
1597 {
1598   kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
1599 }
1600
1601
1602 /* This function processes basic block BB, and looks for variables which can
1603    be replaced by their expressions.  Results are stored in TAB.  */
1604
1605 static void
1606 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
1607 {
1608   block_stmt_iterator bsi;
1609   tree stmt, def;
1610   stmt_ann_t ann;
1611   int partition;
1612   var_map map = tab->map;
1613   value_expr_p p;
1614   ssa_op_iter iter;
1615
1616   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1617     {
1618       stmt = bsi_stmt (bsi);
1619       ann = stmt_ann (stmt);
1620
1621       /* Determine if this stmt finishes an existing expression.  */
1622       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_USE)
1623         {
1624           if (tab->version_info[SSA_NAME_VERSION (def)])
1625             {
1626               bool same_root_var = false;
1627               tree def2;
1628               ssa_op_iter iter2;
1629
1630               /* See if the root variables are the same.  If they are, we
1631                  do not want to do the replacement to avoid problems with
1632                  code size, see PR tree-optimization/17549.  */
1633               FOR_EACH_SSA_TREE_OPERAND (def2, stmt, iter2, SSA_OP_DEF)
1634                 if (SSA_NAME_VAR (def) == SSA_NAME_VAR (def2))
1635                   {
1636                     same_root_var = true;
1637                     break;
1638                   }
1639
1640               /* Mark expression as replaceable unless stmt is volatile
1641                  or DEF sets the same root variable as STMT.  */
1642               if (!ann->has_volatile_ops && !same_root_var)
1643                 mark_replaceable (tab, def);
1644               else
1645                 finish_expr (tab, SSA_NAME_VERSION (def), false);
1646             }
1647         }
1648       
1649       /* Next, see if this stmt kills off an active expression.  */
1650       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1651         {
1652           partition = var_to_partition (map, def);
1653           if (partition != NO_PARTITION && tab->partition_dep_list[partition])
1654             kill_expr (tab, partition, true);
1655         }
1656
1657       /* Now see if we are creating a new expression or not.  */
1658       if (!ann->has_volatile_ops)
1659         check_replaceable (tab, stmt);
1660
1661       /* Free any unused dependency lists.  */
1662       while ((p = tab->pending_dependence))
1663         {
1664           tab->pending_dependence = p->next;
1665           free_value_expr (tab, p);
1666         }
1667
1668       /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand.  */
1669       if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
1670         kill_virtual_exprs (tab, true);
1671     }
1672 }
1673
1674
1675 /* This function is the driver routine for replacement of temporary expressions
1676    in the SSA->normal phase, operating on MAP.  If there are replaceable 
1677    expressions, a table is returned which maps SSA versions to the 
1678    expressions they should be replaced with.  A NULL_TREE indicates no 
1679    replacement should take place.  If there are no replacements at all, 
1680    NULL is returned by the function, otherwise an expression vector indexed
1681    by SSA_NAME version numbers.  */
1682
1683 static tree *
1684 find_replaceable_exprs (var_map map)
1685 {
1686   basic_block bb;
1687   unsigned i;
1688   temp_expr_table_p table;
1689   tree *ret;
1690
1691   table = new_temp_expr_table (map);
1692   FOR_EACH_BB (bb)
1693     {
1694       bitmap_iterator bi;
1695
1696       find_replaceable_in_bb (table, bb);
1697       EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
1698         {
1699           kill_expr (table, i, false);
1700         }
1701     }
1702
1703   ret = free_temp_expr_table (table);
1704   return ret;
1705 }
1706
1707
1708 /* Dump TER expression table EXPR to file F.  */
1709
1710 static void
1711 dump_replaceable_exprs (FILE *f, tree *expr)
1712 {
1713   tree stmt, var;
1714   int x;
1715   fprintf (f, "\nReplacing Expressions\n");
1716   for (x = 0; x < (int)num_ssa_names + 1; x++)
1717     if (expr[x])
1718       {
1719         stmt = expr[x];
1720         var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
1721         gcc_assert (var != NULL_TREE);
1722         print_generic_expr (f, var, TDF_SLIM);
1723         fprintf (f, " replace with --> ");
1724         print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
1725         fprintf (f, "\n");
1726       }
1727   fprintf (f, "\n");
1728 }
1729
1730
1731 /* Helper function for discover_nonconstant_array_refs. 
1732    Look for ARRAY_REF nodes with non-constant indexes and mark them
1733    addressable.  */
1734
1735 static tree
1736 discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
1737                                    void *data ATTRIBUTE_UNUSED)
1738 {
1739   tree t = *tp;
1740
1741   if (IS_TYPE_OR_DECL_P (t))
1742     *walk_subtrees = 0;
1743   else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1744     {
1745       while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1746               && is_gimple_min_invariant (TREE_OPERAND (t, 1))
1747               && (!TREE_OPERAND (t, 2)
1748                   || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1749              || (TREE_CODE (t) == COMPONENT_REF
1750                  && (!TREE_OPERAND (t,2)
1751                      || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1752              || TREE_CODE (t) == BIT_FIELD_REF
1753              || TREE_CODE (t) == REALPART_EXPR
1754              || TREE_CODE (t) == IMAGPART_EXPR
1755              || TREE_CODE (t) == VIEW_CONVERT_EXPR
1756              || TREE_CODE (t) == NOP_EXPR
1757              || TREE_CODE (t) == CONVERT_EXPR)
1758         t = TREE_OPERAND (t, 0);
1759
1760       if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1761         {
1762           t = get_base_address (t);
1763           if (t && DECL_P (t))
1764             TREE_ADDRESSABLE (t) = 1;
1765         }
1766
1767       *walk_subtrees = 0;
1768     }
1769
1770   return NULL_TREE;
1771 }
1772
1773
1774 /* RTL expansion is not able to compile array references with variable
1775    offsets for arrays stored in single register.  Discover such
1776    expressions and mark variables as addressable to avoid this
1777    scenario.  */
1778
1779 static void
1780 discover_nonconstant_array_refs (void)
1781 {
1782   basic_block bb;
1783   block_stmt_iterator bsi;
1784
1785   FOR_EACH_BB (bb)
1786     {
1787       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1788         walk_tree (bsi_stmt_ptr (bsi), discover_nonconstant_array_refs_r,
1789                    NULL , NULL);
1790     }
1791 }
1792
1793
1794 /* This function will rewrite the current program using the variable mapping
1795    found in MAP.  If the replacement vector VALUES is provided, any 
1796    occurrences of partitions with non-null entries in the vector will be 
1797    replaced with the expression in the vector instead of its mapped 
1798    variable.  */
1799
1800 static void
1801 rewrite_trees (var_map map, tree *values)
1802 {
1803   elim_graph g;
1804   basic_block bb;
1805   block_stmt_iterator si;
1806   edge e;
1807   tree phi;
1808   bool changed;
1809  
1810 #ifdef ENABLE_CHECKING
1811   /* Search for PHIs where the destination has no partition, but one
1812      or more arguments has a partition.  This should not happen and can
1813      create incorrect code.  */
1814   FOR_EACH_BB (bb)
1815     {
1816       tree phi;
1817
1818       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1819         {
1820           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1821       
1822           if (T0 == NULL_TREE)
1823             {
1824               int i;
1825
1826               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1827                 {
1828                   tree arg = PHI_ARG_DEF (phi, i);
1829
1830                   if (TREE_CODE (arg) == SSA_NAME
1831                       && var_to_partition (map, arg) != NO_PARTITION)
1832                     {
1833                       fprintf (stderr, "Argument of PHI is in a partition :(");
1834                       print_generic_expr (stderr, arg, TDF_SLIM);
1835                       fprintf (stderr, "), but the result is not :");
1836                       print_generic_stmt (stderr, phi, TDF_SLIM);
1837                       internal_error ("SSA corruption");
1838                     }
1839                 }
1840             }
1841         }
1842     }
1843 #endif
1844
1845   /* Replace PHI nodes with any required copies.  */
1846   g = new_elim_graph (map->num_partitions);
1847   g->map = map;
1848   FOR_EACH_BB (bb)
1849     {
1850       for (si = bsi_start (bb); !bsi_end_p (si); )
1851         {
1852           tree stmt = bsi_stmt (si);
1853           use_operand_p use_p, copy_use_p;
1854           def_operand_p def_p;
1855           bool remove = false, is_copy = false;
1856           int num_uses = 0;
1857           stmt_ann_t ann;
1858           ssa_op_iter iter;
1859
1860           ann = stmt_ann (stmt);
1861           changed = false;
1862
1863           if (TREE_CODE (stmt) == MODIFY_EXPR 
1864               && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
1865             is_copy = true;
1866
1867           copy_use_p = NULL_USE_OPERAND_P;
1868           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1869             {
1870               if (replace_use_variable (map, use_p, values))
1871                 changed = true;
1872               copy_use_p = use_p;
1873               num_uses++;
1874             }
1875
1876           if (num_uses != 1)
1877             is_copy = false;
1878
1879           def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
1880
1881           if (def_p != NULL)
1882             {
1883               /* Mark this stmt for removal if it is the list of replaceable 
1884                  expressions.  */
1885               if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
1886                 remove = true;
1887               else
1888                 {
1889                   if (replace_def_variable (map, def_p, NULL))
1890                     changed = true;
1891                   /* If both SSA_NAMEs coalesce to the same variable,
1892                      mark the now redundant copy for removal.  */
1893                   if (is_copy)
1894                     {
1895                       gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
1896                       if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
1897                         remove = true;
1898                     }
1899                 }
1900             }
1901           else
1902             FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1903               if (replace_def_variable (map, def_p, NULL))
1904                 changed = true;
1905
1906           /* Remove any stmts marked for removal.  */
1907           if (remove)
1908             bsi_remove (&si);
1909           else
1910             bsi_next (&si);
1911         }
1912
1913       phi = phi_nodes (bb);
1914       if (phi)
1915         {
1916           edge_iterator ei;
1917           FOR_EACH_EDGE (e, ei, bb->preds)
1918             eliminate_phi (e, g);
1919         }
1920     }
1921
1922   delete_elim_graph (g);
1923 }
1924
1925
1926 DEF_VEC_ALLOC_P(edge,heap);
1927
1928 /* These are the local work structures used to determine the best place to 
1929    insert the copies that were placed on edges by the SSA->normal pass..  */
1930 static VEC(edge,heap) *edge_leader;
1931 static VEC(tree,heap) *stmt_list;
1932 static bitmap leader_has_match = NULL;
1933 static edge leader_match = NULL;
1934
1935
1936 /* Pass this function to make_forwarder_block so that all the edges with
1937    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  */
1938 static bool 
1939 same_stmt_list_p (edge e)
1940 {
1941   return (e->aux == (PTR) leader_match) ? true : false;
1942 }
1943
1944
1945 /* Return TRUE if S1 and S2 are equivalent copies.  */
1946 static inline bool
1947 identical_copies_p (tree s1, tree s2)
1948 {
1949 #ifdef ENABLE_CHECKING
1950   gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
1951   gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
1952   gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
1953   gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
1954 #endif
1955
1956   if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
1957     return false;
1958
1959   s1 = TREE_OPERAND (s1, 1);
1960   s2 = TREE_OPERAND (s2, 1);
1961
1962   if (s1 != s2)
1963     return false;
1964
1965   return true;
1966 }
1967
1968
1969 /* Compare the PENDING_STMT list for two edges, and return true if the lists
1970    contain the same sequence of copies.  */
1971
1972 static inline bool 
1973 identical_stmt_lists_p (edge e1, edge e2)
1974 {
1975   tree t1 = PENDING_STMT (e1);
1976   tree t2 = PENDING_STMT (e2);
1977   tree_stmt_iterator tsi1, tsi2;
1978
1979   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
1980   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
1981
1982   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
1983        !tsi_end_p (tsi1) && !tsi_end_p (tsi2); 
1984        tsi_next (&tsi1), tsi_next (&tsi2))
1985     {
1986       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
1987         break;
1988     }
1989
1990   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
1991     return false;
1992
1993   return true;
1994 }
1995
1996
1997 /* Allocate data structures used in analyze_edges_for_bb.   */
1998
1999 static void
2000 init_analyze_edges_for_bb (void)
2001 {
2002   edge_leader = VEC_alloc (edge, heap, 25);
2003   stmt_list = VEC_alloc (tree, heap, 25);
2004   leader_has_match = BITMAP_ALLOC (NULL);
2005 }
2006
2007
2008 /* Free data structures used in analyze_edges_for_bb.   */
2009
2010 static void
2011 fini_analyze_edges_for_bb (void)
2012 {
2013   VEC_free (edge, heap, edge_leader);
2014   VEC_free (tree, heap, stmt_list);
2015   BITMAP_FREE (leader_has_match);
2016 }
2017
2018
2019 /* Look at all the incoming edges to block BB, and decide where the best place
2020    to insert the stmts on each edge are, and perform those insertions.   Output
2021    any debug information to DEBUG_FILE.  */
2022
2023 static void
2024 analyze_edges_for_bb (basic_block bb, FILE *debug_file)
2025 {
2026   edge e;
2027   edge_iterator ei;
2028   int count;
2029   unsigned int x;
2030   bool have_opportunity;
2031   block_stmt_iterator bsi;
2032   tree stmt;
2033   edge single_edge = NULL;
2034   bool is_label;
2035   edge leader;
2036
2037   count = 0;
2038
2039   /* Blocks which contain at least one abnormal edge cannot use 
2040      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
2041      found on edges in these block.  */
2042   have_opportunity = true;
2043   FOR_EACH_EDGE (e, ei, bb->preds)
2044     if (e->flags & EDGE_ABNORMAL)
2045       {
2046         have_opportunity = false;
2047         break;
2048       }
2049
2050   if (!have_opportunity)
2051     {
2052       FOR_EACH_EDGE (e, ei, bb->preds)
2053         if (PENDING_STMT (e))
2054           bsi_commit_one_edge_insert (e, NULL);
2055       return;
2056     }
2057   /* Find out how many edges there are with interesting pending stmts on them.  
2058      Commit the stmts on edges we are not interested in.  */
2059   FOR_EACH_EDGE (e, ei, bb->preds)
2060     {
2061       if (PENDING_STMT (e))
2062         {
2063           gcc_assert (!(e->flags & EDGE_ABNORMAL));
2064           if (e->flags & EDGE_FALLTHRU)
2065             {
2066               bsi = bsi_start (e->src);
2067               if (!bsi_end_p (bsi))
2068                 {
2069                   stmt = bsi_stmt (bsi);
2070                   bsi_next (&bsi);
2071                   gcc_assert (stmt != NULL_TREE);
2072                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
2073                   /* Punt if it has non-label stmts, or isn't local.  */
2074                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0)) 
2075                       || !bsi_end_p (bsi))
2076                     {
2077                       bsi_commit_one_edge_insert (e, NULL);
2078                       continue;
2079                     }
2080                 }
2081             }
2082           single_edge = e;
2083           count++;
2084         }
2085     }
2086
2087   /* If there aren't at least 2 edges, no sharing will happen.  */
2088   if (count < 2)
2089     {
2090       if (single_edge)
2091         bsi_commit_one_edge_insert (single_edge, NULL);
2092       return;
2093     }
2094
2095   /* Ensure that we have empty worklists.  */
2096 #ifdef ENABLE_CHECKING
2097   gcc_assert (VEC_length (edge, edge_leader) == 0);
2098   gcc_assert (VEC_length (tree, stmt_list) == 0);
2099   gcc_assert (bitmap_empty_p (leader_has_match));
2100 #endif
2101
2102   /* Find the "leader" block for each set of unique stmt lists.  Preference is
2103      given to FALLTHRU blocks since they would need a GOTO to arrive at another
2104      block.  The leader edge destination is the block which all the other edges
2105      with the same stmt list will be redirected to.  */
2106   have_opportunity = false;
2107   FOR_EACH_EDGE (e, ei, bb->preds)
2108     {
2109       if (PENDING_STMT (e))
2110         {
2111           bool found = false;
2112
2113           /* Look for the same stmt list in edge leaders list.  */
2114           for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2115             {
2116               if (identical_stmt_lists_p (leader, e))
2117                 {
2118                   /* Give this edge the same stmt list pointer.  */
2119                   PENDING_STMT (e) = NULL;
2120                   e->aux = leader;
2121                   bitmap_set_bit (leader_has_match, x);
2122                   have_opportunity = found = true;
2123                   break;
2124                 }
2125             }
2126
2127           /* If no similar stmt list, add this edge to the leader list.  */
2128           if (!found)
2129             {
2130               VEC_safe_push (edge, heap, edge_leader, e);
2131               VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
2132             }
2133         }
2134      }
2135
2136   /* If there are no similar lists, just issue the stmts.  */
2137   if (!have_opportunity)
2138     {
2139       for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2140         bsi_commit_one_edge_insert (leader, NULL);
2141       VEC_truncate (edge, edge_leader, 0);
2142       VEC_truncate (tree, stmt_list, 0);
2143       bitmap_clear (leader_has_match);
2144       return;
2145     }
2146
2147
2148   if (debug_file)
2149     fprintf (debug_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
2150              bb->index);
2151
2152   
2153   /* For each common list, create a forwarding block and issue the stmt's
2154      in that block.  */
2155   for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2156     if (bitmap_bit_p (leader_has_match, x))
2157       {
2158         edge new_edge;
2159         block_stmt_iterator bsi;
2160         tree curr_stmt_list;
2161
2162         leader_match = leader;
2163
2164         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
2165            for various PHI manipulations, so it gets cleared whhen calls are 
2166            made to make_forwarder_block(). So make sure the edge is clear, 
2167            and use the saved stmt list.  */
2168         PENDING_STMT (leader) = NULL;
2169         leader->aux = leader;
2170         curr_stmt_list = VEC_index (tree, stmt_list, x);
2171
2172         new_edge = make_forwarder_block (leader->dest, same_stmt_list_p, 
2173                                          NULL);
2174         bb = new_edge->dest;
2175         if (debug_file)
2176           {
2177             fprintf (debug_file, "Splitting BB %d for Common stmt list.  ", 
2178                      leader->dest->index);
2179             fprintf (debug_file, "Original block is now BB%d.\n", bb->index);
2180             print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS);
2181           }
2182
2183         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
2184           {
2185             e->aux = NULL;
2186             if (debug_file)
2187               fprintf (debug_file, "  Edge (%d->%d) lands here.\n", 
2188                        e->src->index, e->dest->index);
2189           }
2190
2191         bsi = bsi_last (leader->dest);
2192         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
2193
2194         leader_match = NULL;
2195         /* We should never get a new block now.  */
2196       }
2197     else
2198       {
2199         PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
2200         bsi_commit_one_edge_insert (leader, NULL);
2201       }
2202
2203    
2204   /* Clear the working data structures.  */
2205   VEC_truncate (edge, edge_leader, 0);
2206   VEC_truncate (tree, stmt_list, 0);
2207   bitmap_clear (leader_has_match);
2208 }
2209
2210
2211 /* This function will analyze the insertions which were performed on edges,
2212    and decide whether they should be left on that edge, or whether it is more
2213    efficient to emit some subset of them in a single block.  All stmts are
2214    inserted somewhere, and if non-NULL, debug information is printed via 
2215    DUMP_FILE.  */
2216
2217 static void
2218 perform_edge_inserts (FILE *dump_file)
2219 {
2220   basic_block bb;
2221
2222   if (dump_file)
2223     fprintf(dump_file, "Analyzing Edge Insertions.\n");
2224
2225   /* analyze_edges_for_bb calls make_forwarder_block, which tries to
2226      incrementally update the dominator information.  Since we don't
2227      need dominator information after this pass, go ahead and free the
2228      dominator information.  */
2229   free_dominance_info (CDI_DOMINATORS);
2230   free_dominance_info (CDI_POST_DOMINATORS);
2231
2232   /* Allocate data structures used in analyze_edges_for_bb.   */
2233   init_analyze_edges_for_bb ();
2234
2235   FOR_EACH_BB (bb)
2236     analyze_edges_for_bb (bb, dump_file);
2237
2238   analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
2239
2240   /* Free data structures used in analyze_edges_for_bb.   */
2241   fini_analyze_edges_for_bb ();
2242
2243 #ifdef ENABLE_CHECKING
2244   {
2245     edge_iterator ei;
2246     edge e;
2247     FOR_EACH_BB (bb)
2248       {
2249         FOR_EACH_EDGE (e, ei, bb->preds)
2250           {
2251             if (PENDING_STMT (e))
2252               error (" Pending stmts not issued on PRED edge (%d, %d)\n", 
2253                      e->src->index, e->dest->index);
2254           }
2255         FOR_EACH_EDGE (e, ei, bb->succs)
2256           {
2257             if (PENDING_STMT (e))
2258               error (" Pending stmts not issued on SUCC edge (%d, %d)\n", 
2259                      e->src->index, e->dest->index);
2260           }
2261       }
2262     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2263       {
2264         if (PENDING_STMT (e))
2265           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n", 
2266                  e->src->index, e->dest->index);
2267       }
2268     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
2269       {
2270         if (PENDING_STMT (e))
2271           error (" Pending stmts not issued on EXIT edge (%d, %d)\n", 
2272                  e->src->index, e->dest->index);
2273       }
2274   }
2275 #endif
2276 }
2277
2278
2279 /* Remove the variables specified in MAP from SSA form.  Any debug information
2280    is sent to DUMP.  FLAGS indicate what options should be used.  */
2281
2282 static void
2283 remove_ssa_form (FILE *dump, var_map map, int flags)
2284 {
2285   tree_live_info_p liveinfo;
2286   basic_block bb;
2287   tree phi, next;
2288   FILE *save;
2289   tree *values = NULL;
2290
2291   save = dump_file;
2292   dump_file = dump;
2293
2294   /* If we are not combining temps, don't calculate live ranges for variables
2295      with only one SSA version.  */
2296   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2297     compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
2298   else
2299     compact_var_map (map, VARMAP_NORMAL);
2300
2301   if (dump_file && (dump_flags & TDF_DETAILS))
2302     dump_var_map (dump_file, map);
2303
2304   liveinfo = coalesce_ssa_name (map, flags);
2305
2306   /* Make sure even single occurrence variables are in the list now.  */
2307   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2308     compact_var_map (map, VARMAP_NORMAL);
2309
2310   if (dump_file && (dump_flags & TDF_DETAILS))
2311     {
2312       fprintf (dump_file, "After Coalescing:\n");
2313       dump_var_map (dump_file, map);
2314     }
2315
2316   if (flags & SSANORM_PERFORM_TER)
2317     {
2318       values = find_replaceable_exprs (map);
2319       if (values && dump_file && (dump_flags & TDF_DETAILS))
2320         dump_replaceable_exprs (dump_file, values);
2321     }
2322
2323   /* Assign real variables to the partitions now.  */
2324   assign_vars (map);
2325
2326   if (dump_file && (dump_flags & TDF_DETAILS))
2327     {
2328       fprintf (dump_file, "After Root variable replacement:\n");
2329       dump_var_map (dump_file, map);
2330     }
2331
2332   if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo)
2333     {
2334       coalesce_vars (map, liveinfo);
2335       if (dump_file && (dump_flags & TDF_DETAILS))
2336         {
2337           fprintf (dump_file, "After variable memory coalescing:\n");
2338           dump_var_map (dump_file, map);
2339         }
2340     }
2341   
2342   if (liveinfo)
2343     delete_tree_live_info (liveinfo);
2344
2345   rewrite_trees (map, values);
2346
2347   if (values)
2348     free (values);
2349
2350   /* Remove phi nodes which have been translated back to real variables.  */
2351   FOR_EACH_BB (bb)
2352     {
2353       for (phi = phi_nodes (bb); phi; phi = next)
2354         {
2355           next = PHI_CHAIN (phi);
2356           remove_phi_node (phi, NULL_TREE);
2357         }
2358     }
2359
2360   /* we no longer maintain the SSA operand cache at this point.  */
2361   fini_ssa_operands ();
2362
2363   /* If any copies were inserted on edges, analyze and insert them now.  */
2364   perform_edge_inserts (dump_file);
2365
2366   dump_file = save;
2367 }
2368
2369 /* Search every PHI node for arguments associated with backedges which
2370    we can trivially determine will need a copy (the argument is either
2371    not an SSA_NAME or the argument has a different underlying variable
2372    than the PHI result).
2373
2374    Insert a copy from the PHI argument to a new destination at the
2375    end of the block with the backedge to the top of the loop.  Update
2376    the PHI argument to reference this new destination.  */
2377
2378 static void
2379 insert_backedge_copies (void)
2380 {
2381   basic_block bb;
2382
2383   FOR_EACH_BB (bb)
2384     {
2385       tree phi;
2386
2387       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2388         {
2389           tree result = PHI_RESULT (phi);
2390           tree result_var;
2391           int i;
2392
2393           if (!is_gimple_reg (result))
2394             continue;
2395
2396           result_var = SSA_NAME_VAR (result);
2397           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2398             {
2399               tree arg = PHI_ARG_DEF (phi, i);
2400               edge e = PHI_ARG_EDGE (phi, i);
2401
2402               /* If the argument is not an SSA_NAME, then we will
2403                  need a constant initialization.  If the argument is
2404                  an SSA_NAME with a different underlying variable and
2405                  we are not combining temporaries, then we will
2406                  need a copy statement.  */
2407               if ((e->flags & EDGE_DFS_BACK)
2408                   && (TREE_CODE (arg) != SSA_NAME
2409                       || (!flag_tree_combine_temps
2410                           && SSA_NAME_VAR (arg) != result_var)))
2411                 {
2412                   tree stmt, name, last = NULL;
2413                   block_stmt_iterator bsi;
2414
2415                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
2416                   if (!bsi_end_p (bsi))
2417                     last = bsi_stmt (bsi);
2418
2419                   /* In theory the only way we ought to get back to the
2420                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
2421                      However, better safe than sorry. 
2422
2423                      If the block ends with a control statement or
2424                      something that might throw, then we have to
2425                      insert this assignment before the last
2426                      statement.  Else insert it after the last statement.  */
2427                   if (last && stmt_ends_bb_p (last))
2428                     {
2429                       /* If the last statement in the block is the definition
2430                          site of the PHI argument, then we can't insert
2431                          anything after it.  */
2432                       if (TREE_CODE (arg) == SSA_NAME
2433                           && SSA_NAME_DEF_STMT (arg) == last)
2434                         continue;
2435                     }
2436
2437                   /* Create a new instance of the underlying
2438                      variable of the PHI result.  */
2439                   stmt = build (MODIFY_EXPR, TREE_TYPE (result_var),
2440                                 NULL, PHI_ARG_DEF (phi, i));
2441                   name = make_ssa_name (result_var, stmt);
2442                   TREE_OPERAND (stmt, 0) = name;
2443
2444                   /* Insert the new statement into the block and update
2445                      the PHI node.  */
2446                   if (last && stmt_ends_bb_p (last))
2447                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2448                   else
2449                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2450                   SET_PHI_ARG_DEF (phi, i, name);
2451                 }
2452             }
2453         }
2454     }
2455 }
2456
2457 /* Take the current function out of SSA form, as described in
2458    R. Morgan, ``Building an Optimizing Compiler'',
2459    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
2460
2461 static void
2462 rewrite_out_of_ssa (void)
2463 {
2464   var_map map;
2465   int var_flags = 0;
2466   int ssa_flags = 0;
2467
2468   /* If elimination of a PHI requires inserting a copy on a backedge,
2469      then we will have to split the backedge which has numerous
2470      undesirable performance effects.
2471
2472      A significant number of such cases can be handled here by inserting
2473      copies into the loop itself.  */
2474   insert_backedge_copies ();
2475
2476   if (!flag_tree_live_range_split)
2477     ssa_flags |= SSANORM_COALESCE_PARTITIONS;
2478     
2479   eliminate_virtual_phis ();
2480
2481   if (dump_file && (dump_flags & TDF_DETAILS))
2482     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2483
2484   /* We cannot allow unssa to un-gimplify trees before we instrument them.  */
2485   if (flag_tree_ter && !flag_mudflap)
2486     var_flags = SSA_VAR_MAP_REF_COUNT;
2487
2488   map = create_ssa_var_map (var_flags);
2489
2490   if (flag_tree_combine_temps)
2491     ssa_flags |= SSANORM_COMBINE_TEMPS;
2492   if (flag_tree_ter && !flag_mudflap)
2493     ssa_flags |= SSANORM_PERFORM_TER;
2494
2495   remove_ssa_form (dump_file, map, ssa_flags);
2496
2497   if (dump_file && (dump_flags & TDF_DETAILS))
2498     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2499
2500   /* Flush out flow graph and SSA data.  */
2501   delete_var_map (map);
2502
2503   /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE.  */
2504   discover_nonconstant_array_refs ();
2505
2506   in_ssa_p = false;
2507 }
2508
2509
2510 /* Define the parameters of the out of SSA pass.  */
2511
2512 struct tree_opt_pass pass_del_ssa = 
2513 {
2514   "optimized",                          /* name */
2515   NULL,                                 /* gate */
2516   rewrite_out_of_ssa,                   /* execute */
2517   NULL,                                 /* sub */
2518   NULL,                                 /* next */
2519   0,                                    /* static_pass_number */
2520   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
2521   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2522   0,                                    /* properties_provided */
2523   /* ??? If TER is enabled, we also kill gimple.  */
2524   PROP_ssa,                             /* properties_destroyed */
2525   TODO_verify_ssa | TODO_verify_flow
2526     | TODO_verify_stmts,                /* todo_flags_start */
2527   TODO_dump_func | TODO_ggc_collect,    /* todo_flags_finish */
2528   0                                     /* letter */
2529 };