OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[pf3gnuchains/gcc-fork.git] / gcc / tree-outof-ssa.c
1 /* Convert a program in SSA form into Normal form.
2    Copyright (C) 2004 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 "tree-alias-common.h"
46 #include "hashtab.h"
47 #include "tree-dump.h"
48 #include "tree-ssa-live.h"
49 #include "tree-pass.h"
50
51 /* Flags to pass to remove_ssa_form.  */
52
53 #define SSANORM_PERFORM_TER             0x1
54 #define SSANORM_COMBINE_TEMPS           0x2
55 #define SSANORM_REMOVE_ALL_PHIS         0x4
56 #define SSANORM_COALESCE_PARTITIONS     0x8
57 #define SSANORM_USE_COALESCE_LIST       0x10
58
59 /* Used to hold all the components required to do SSA PHI elimination.
60    The node and pred/succ list is a simple linear list of nodes and
61    edges represented as pairs of nodes.
62
63    The predecessor and successor list:  Nodes are entered in pairs, where
64    [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent 
65    predecessors, all the odd elements are successors. 
66    
67    Rationale:
68    When implemented as bitmaps, very large programs SSA->Normal times were 
69    being dominated by clearing the interference graph.
70
71    Typically this list of edges is extremely small since it only includes 
72    PHI results and uses from a single edge which have not coalesced with 
73    each other.  This means that no virtual PHI nodes are included, and
74    empirical evidence suggests that the number of edges rarely exceed
75    3, and in a bootstrap of GCC, the maximum size encountered was 7.
76    This also limits the number of possible nodes that are involved to
77    rarely more than 6, and in the bootstrap of gcc, the maximum number
78    of nodes encountered was 12.  */
79  
80 typedef struct _elim_graph {
81   /* Size of the elimination vectors.  */
82   int size;
83
84   /* List of nodes in the elimination graph.  */
85   varray_type nodes;
86
87   /*  The predecessor and successor edge list.  */
88   varray_type edge_list;
89
90   /* Visited vector.  */
91   sbitmap visited;
92
93   /* Stack for visited nodes.  */
94   varray_type stack;
95   
96   /* The variable partition map.  */
97   var_map map;
98
99   /* Edge being eliminated by this graph.  */
100   edge e;
101
102   /* List of constant copies to emit.  These are pushed on in pairs.  */
103   varray_type  const_copies;
104 } *elim_graph;
105
106
107 /* Local functions.  */
108 static tree create_temp (tree);
109 static void insert_copy_on_edge (edge, tree, tree);
110 static elim_graph new_elim_graph (int);
111 static inline void delete_elim_graph (elim_graph);
112 static inline void clear_elim_graph (elim_graph);
113 static inline int elim_graph_size (elim_graph);
114 static inline void elim_graph_add_node (elim_graph, tree);
115 static inline void elim_graph_add_edge (elim_graph, int, int);
116 static inline int elim_graph_remove_succ_edge (elim_graph, int);
117
118 static inline void eliminate_name (elim_graph, tree);
119 static void eliminate_build (elim_graph, basic_block, int);
120 static void elim_forward (elim_graph, int);
121 static int elim_unvisited_predecessor (elim_graph, int);
122 static void elim_backward (elim_graph, int);
123 static void elim_create (elim_graph, int);
124 static void eliminate_phi (edge, int, elim_graph);
125 static tree_live_info_p coalesce_ssa_name (var_map, int);
126 static void assign_vars (var_map);
127 static bool replace_use_variable (var_map, use_operand_p, tree *);
128 static bool replace_def_variable (var_map, def_operand_p, tree *);
129 static void eliminate_virtual_phis (void);
130 static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
131 static void print_exprs (FILE *, const char *, tree, const char *, tree,
132                          const char *);
133 static void print_exprs_edge (FILE *, edge, const char *, tree, const char *,
134                               tree);
135
136
137 /* Create a temporary variable based on the type of variable T.  Use T's name
138    as the prefix.  */
139
140 static tree
141 create_temp (tree t)
142 {
143   tree tmp;
144   const char *name = NULL;
145   tree type;
146
147   if (TREE_CODE (t) == SSA_NAME)
148     t = SSA_NAME_VAR (t);
149
150   gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
151
152   type = TREE_TYPE (t);
153   tmp = DECL_NAME (t);
154   if (tmp)
155     name = IDENTIFIER_POINTER (tmp);
156
157   if (name == NULL)
158     name = "temp";
159   tmp = create_tmp_var (type, name);
160   DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
161   add_referenced_tmp_var (tmp);
162
163   /* add_referenced_tmp_var will create the annotation and set up some
164      of the flags in the annotation.  However, some flags we need to
165      inherit from our original variable.  */
166   var_ann (tmp)->type_mem_tag = var_ann (t)->type_mem_tag;
167   if (is_call_clobbered (t))
168     mark_call_clobbered (tmp);
169
170   return tmp;
171 }
172
173
174 /* This helper function fill insert a copy from a constant or variable SRC to 
175    variable DEST on edge E.  */
176
177 static void
178 insert_copy_on_edge (edge e, tree dest, tree src)
179 {
180   tree copy;
181
182   copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
183   set_is_used (dest);
184
185   if (TREE_CODE (src) == ADDR_EXPR)
186     src = TREE_OPERAND (src, 0);
187   if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
188     set_is_used (src);
189
190   if (dump_file && (dump_flags & TDF_DETAILS))
191     {
192       fprintf (dump_file,
193                "Inserting a copy on edge BB%d->BB%d :",
194                e->src->index,
195                e->dest->index);
196       print_generic_expr (dump_file, copy, dump_flags);
197       fprintf (dump_file, "\n");
198     }
199
200   bsi_insert_on_edge (e, copy);
201 }
202
203
204 /* Create an elimination graph with SIZE nodes and associated data
205    structures.  */
206
207 static elim_graph
208 new_elim_graph (int size)
209 {
210   elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
211
212   VARRAY_TREE_INIT (g->nodes, 30, "Elimination Node List");
213   VARRAY_TREE_INIT (g->const_copies, 20, "Elimination Constant Copies");
214   VARRAY_INT_INIT (g->edge_list, 20, "Elimination Edge List");
215   VARRAY_INT_INIT (g->stack, 30, " Elimination Stack");
216   
217   g->visited = sbitmap_alloc (size);
218
219   return g;
220 }
221
222
223 /* Empty elimination graph G.  */
224
225 static inline void
226 clear_elim_graph (elim_graph g)
227 {
228   VARRAY_POP_ALL (g->nodes);
229   VARRAY_POP_ALL (g->edge_list);
230 }
231
232
233 /* Delete elimination graph G.  */
234
235 static inline void
236 delete_elim_graph (elim_graph g)
237 {
238   sbitmap_free (g->visited);
239   free (g);
240 }
241
242
243 /* Return the number of nodes in graph G.  */
244
245 static inline int
246 elim_graph_size (elim_graph g)
247 {
248   return VARRAY_ACTIVE_SIZE (g->nodes);
249 }
250
251
252 /* Add NODE to graph G, if it doesn't exist already.  */
253
254 static inline void 
255 elim_graph_add_node (elim_graph g, tree node)
256 {
257   int x;
258   for (x = 0; x < elim_graph_size (g); x++)
259     if (VARRAY_TREE (g->nodes, x) == node)
260       return;
261   VARRAY_PUSH_TREE (g->nodes, node);
262 }
263
264
265 /* Add the edge PRED->SUCC to graph G.  */
266
267 static inline void
268 elim_graph_add_edge (elim_graph g, int pred, int succ)
269 {
270   VARRAY_PUSH_INT (g->edge_list, pred);
271   VARRAY_PUSH_INT (g->edge_list, succ);
272 }
273
274
275 /* Remove an edge from graph G for which NODE is the predecessor, and
276    return the successor node.  -1 is returned if there is no such edge.  */
277
278 static inline int
279 elim_graph_remove_succ_edge (elim_graph g, int node)
280 {
281   int y;
282   unsigned x;
283   for (x = 0; x < VARRAY_ACTIVE_SIZE (g->edge_list); x += 2)
284     if (VARRAY_INT (g->edge_list, x) == node)
285       {
286         VARRAY_INT (g->edge_list, x) = -1;
287         y = VARRAY_INT (g->edge_list, x + 1);
288         VARRAY_INT (g->edge_list, x + 1) = -1;
289         return y;
290       }
291   return -1;
292 }
293
294
295 /* Find all the nodes in GRAPH which are successors to NODE in the
296    edge list.  VAR will hold the partition number found.  CODE is the
297    code fragment executed for every node found.  */
298
299 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE)                \
300 do {                                                                    \
301   unsigned x_;                                                          \
302   int y_;                                                               \
303   for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2)   \
304     {                                                                   \
305       y_ = VARRAY_INT ((GRAPH)->edge_list, x_);                         \
306       if (y_ != (NODE))                                                 \
307         continue;                                                       \
308       (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_ + 1);                  \
309       CODE;                                                             \
310     }                                                                   \
311 } while (0)
312
313
314 /* Find all the nodes which are predecessors of NODE in the edge list for
315    GRAPH.  VAR will hold the partition number found.  CODE is the
316    code fragment executed for every node found.  */
317
318 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE)                \
319 do {                                                                    \
320   unsigned x_;                                                          \
321   int y_;                                                               \
322   for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2)   \
323     {                                                                   \
324       y_ = VARRAY_INT ((GRAPH)->edge_list, x_ + 1);                     \
325       if (y_ != (NODE))                                                 \
326         continue;                                                       \
327       (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_);                      \
328       CODE;                                                             \
329     }                                                                   \
330 } while (0)
331
332
333 /* Add T to elimination graph G.  */
334
335 static inline void
336 eliminate_name (elim_graph g, tree T)
337 {
338   elim_graph_add_node (g, T);
339 }
340
341
342 /* Build elimination graph G for basic block BB on incoming PHI edge I.  */
343
344 static void
345 eliminate_build (elim_graph g, basic_block B, int i)
346 {
347   tree phi;
348   tree T0, Ti;
349   int p0, pi;
350
351   clear_elim_graph (g);
352   
353   for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi))
354     {
355       T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
356       
357       /* Ignore results which are not in partitions.  */
358       if (T0 == NULL_TREE)
359         continue;
360
361       if (PHI_ARG_EDGE (phi, i) == g->e)
362         Ti = PHI_ARG_DEF (phi, i);
363       else
364         {
365           /* On rare occasions, a PHI node may not have the arguments
366              in the same order as all of the other PHI nodes. If they don't 
367              match, find the appropriate index here.  */
368           pi = phi_arg_from_edge (phi, g->e);
369           gcc_assert (pi != -1);
370           Ti = PHI_ARG_DEF (phi, pi);
371         }
372
373       /* If this argument is a constant, or a SSA_NAME which is being
374          left in SSA form, just queue a copy to be emitted on this
375          edge.  */
376       if (!phi_ssa_name_p (Ti)
377           || (TREE_CODE (Ti) == SSA_NAME
378               && var_to_partition (g->map, Ti) == NO_PARTITION))
379         {
380           /* Save constant copies until all other copies have been emitted
381              on this edge.  */
382           VARRAY_PUSH_TREE (g->const_copies, T0);
383           VARRAY_PUSH_TREE (g->const_copies, Ti);
384         }
385       else
386         {
387           Ti = var_to_partition_to_var (g->map, Ti);
388           if (T0 != Ti)
389             {
390               eliminate_name (g, T0);
391               eliminate_name (g, Ti);
392               p0 = var_to_partition (g->map, T0);
393               pi = var_to_partition (g->map, Ti);
394               elim_graph_add_edge (g, p0, pi);
395             }
396         }
397     }
398 }
399
400
401 /* Push successors of T onto the elimination stack for G.  */
402
403 static void 
404 elim_forward (elim_graph g, int T)
405 {
406   int S;
407   SET_BIT (g->visited, T);
408   FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
409     {
410       if (!TEST_BIT (g->visited, S))
411         elim_forward (g, S);
412     });
413   VARRAY_PUSH_INT (g->stack, T);
414 }
415
416
417 /* Return 1 if there unvisited predecessors of T in graph G.  */
418
419 static int
420 elim_unvisited_predecessor (elim_graph g, int T)
421 {
422   int P;
423   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 
424     {
425       if (!TEST_BIT (g->visited, P))
426         return 1;
427     });
428   return 0;
429 }
430
431 /* Process predecessors first, and insert a copy.  */
432
433 static void
434 elim_backward (elim_graph g, int T)
435 {
436   int P;
437   SET_BIT (g->visited, T);
438   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 
439     {
440       if (!TEST_BIT (g->visited, P))
441         {
442           elim_backward (g, P);
443           insert_copy_on_edge (g->e, 
444                                partition_to_var (g->map, P), 
445                                partition_to_var (g->map, T));
446         }
447     });
448 }
449
450 /* Insert required copies for T in graph G.  Check for a strongly connected 
451    region, and create a temporary to break the cycle if one is found.  */
452
453 static void 
454 elim_create (elim_graph g, int T)
455 {
456   tree U;
457   int P, S;
458
459   if (elim_unvisited_predecessor (g, T))
460     {
461       U = create_temp (partition_to_var (g->map, T));
462       insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
463       FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 
464         {
465           if (!TEST_BIT (g->visited, P))
466             {
467               elim_backward (g, P);
468               insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
469             }
470         });
471     }
472   else
473     {
474       S = elim_graph_remove_succ_edge (g, T);
475       if (S != -1)
476         {
477           SET_BIT (g->visited, T);
478           insert_copy_on_edge (g->e, 
479                                partition_to_var (g->map, T), 
480                                partition_to_var (g->map, S));
481         }
482     }
483   
484 }
485
486 /* Eliminate all the phi nodes on edge E in graph G. I is the usual PHI
487    index that edge E's values are found on.  */
488
489 static void
490 eliminate_phi (edge e, int i, elim_graph g)
491 {
492   int num_nodes = 0;
493   int x;
494   basic_block B = e->dest;
495
496   gcc_assert (i != -1);
497   gcc_assert (VARRAY_ACTIVE_SIZE (g->const_copies) == 0);
498
499   /* Abnormal edges already have everything coalesced, or the coalescer
500      would have aborted.  */
501   if (e->flags & EDGE_ABNORMAL)
502     return;
503
504   num_nodes = num_var_partitions (g->map);
505   g->e = e;
506
507   eliminate_build (g, B, i);
508
509   if (elim_graph_size (g) != 0)
510     {
511       sbitmap_zero (g->visited);
512       VARRAY_POP_ALL (g->stack);
513
514       for (x = 0; x < elim_graph_size (g); x++)
515         {
516           tree var = VARRAY_TREE (g->nodes, x);
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 (VARRAY_ACTIVE_SIZE (g->const_copies) > 0)
534     {
535       tree src, dest;
536       src = VARRAY_TOP_TREE (g->const_copies);
537       VARRAY_POP (g->const_copies);
538       dest = VARRAY_TOP_TREE (g->const_copies);
539       VARRAY_POP (g->const_copies);
540       insert_copy_on_edge (e, dest, src);
541     }
542 }
543
544
545 /* Shortcut routine to print messages to file F of the form:
546    "STR1 EXPR1 STR2 EXPR2 STR3."  */
547
548 static void
549 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
550              tree expr2, const char *str3)
551 {
552   fprintf (f, "%s", str1);
553   print_generic_expr (f, expr1, TDF_SLIM);
554   fprintf (f, "%s", str2);
555   print_generic_expr (f, expr2, TDF_SLIM);
556   fprintf (f, "%s", str3);
557 }
558
559
560 /* Shortcut routine to print abnormal edge messages to file F of the form:
561    "STR1 EXPR1 STR2 EXPR2 across edge E.  */
562
563 static void
564 print_exprs_edge (FILE *f, edge e, const char *str1, tree expr1, 
565                   const char *str2, tree expr2)
566 {
567   print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge");
568   fprintf (f, " from BB%d->BB%d\n", e->src->index,
569                e->dest->index);
570 }
571
572
573 /* Coalesce partitions in MAP which are live across abnormal edges in GRAPH.
574    RV is the root variable groupings of the partitions in MAP.  Since code 
575    cannot be inserted on these edges, failure to coalesce something across
576    an abnormal edge is an error.  */
577
578 static void
579 coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv)
580 {
581   basic_block bb;
582   edge e;
583   tree phi, var, tmp;
584   int x, y;
585
586   /* Code cannot be inserted on abnormal edges. Look for all abnormal 
587      edges, and coalesce any PHI results with their arguments across 
588      that edge.  */
589
590   FOR_EACH_BB (bb)
591     for (e = bb->succ; e; e = e->succ_next)
592       if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
593         for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
594           {
595             /* Visit each PHI on the destination side of this abnormal
596                edge, and attempt to coalesce the argument with the result.  */
597             var = PHI_RESULT (phi);
598             x = var_to_partition (map, var);
599
600             /* Ignore results which are not relevant.  */
601             if (x == NO_PARTITION)
602               continue;
603
604             y = phi_arg_from_edge (phi, e);
605             gcc_assert (y != -1);
606
607             tmp = PHI_ARG_DEF (phi, y);
608 #ifdef ENABLE_CHECKING
609             if (!phi_ssa_name_p (tmp))
610               {
611                 print_exprs_edge (stderr, e,
612                                   "\nConstant argument in PHI. Can't insert :",
613                                   var, " = ", tmp);
614                 internal_error ("SSA corruption");
615               }
616 #else
617             gcc_assert (phi_ssa_name (tmp));
618 #endif
619             y = var_to_partition (map, tmp);
620             gcc_assert (x != NO_PARTITION);
621             gcc_assert (y != NO_PARTITION);
622 #ifdef ENABLE_CHECKING
623             if (root_var_find (rv, x) != root_var_find (rv, y))
624               {
625                 print_exprs_edge (stderr, e, "\nDifferent root vars: ",
626                                   root_var (rv, root_var_find (rv, x)), 
627                                   " and ", 
628                                   root_var (rv, root_var_find (rv, y)));
629                 internal_error ("SSA corruption");
630               }
631 #else
632             gcc_assert (root_var_find (rv, x) == root_var_find (rv, y));
633 #endif
634
635             if (x != y)
636               {
637 #ifdef ENABLE_CHECKING
638                 if (conflict_graph_conflict_p (graph, x, y))
639                   {
640                     print_exprs_edge (stderr, e, "\n Conflict ", 
641                                       partition_to_var (map, x),
642                                       " and ", partition_to_var (map, y));
643                     internal_error ("SSA corruption");
644                   }
645 #else
646                 gcc_assert (!conflict_graph_conflict_p (graph, x, y));
647 #endif
648                 
649                 /* Now map the partitions back to their real variables.  */
650                 var = partition_to_var (map, x);
651                 tmp = partition_to_var (map, y);
652                 if (dump_file && (dump_flags & TDF_DETAILS))
653                   {
654                     print_exprs_edge (dump_file, e, 
655                                       "ABNORMAL: Coalescing ",
656                                       var, " and ", tmp);
657                   }
658 #ifdef ENABLE_CHECKING
659                 if (var_union (map, var, tmp) == NO_PARTITION)
660                   {
661                     print_exprs_edge (stderr, e, "\nUnable to coalesce", 
662                                       partition_to_var (map, x), " and ", 
663                                       partition_to_var (map, y));
664                     internal_error ("SSA corruption");
665                   }
666 #else
667                 gcc_assert (var_union (map, var, tmp) != NO_PARTITION);
668 #endif
669                 conflict_graph_merge_regs (graph, x, y);
670               }
671           }
672 }
673
674
675 /* Reduce the number of live ranges in MAP.  Live range information is 
676    returned if FLAGS indicates that we are combining temporaries, otherwise 
677    NULL is returned.  The only partitions which are associated with actual 
678    variables at this point are those which are forced to be coalesced for 
679    various reason. (live on entry, live across abnormal edges, etc.).  */
680
681 static tree_live_info_p
682 coalesce_ssa_name (var_map map, int flags)
683 {
684   int num, x, i;
685   sbitmap live;
686   tree var, phi;
687   root_var_p rv;
688   tree_live_info_p liveinfo;
689   var_ann_t ann;
690   conflict_graph graph;
691   basic_block bb;
692   coalesce_list_p cl = NULL;
693
694   if (num_var_partitions (map) <= 1)
695     return NULL;
696
697   /* If no preference given, use cheap coalescing of all partitions.  */
698   if ((flags & (SSANORM_COALESCE_PARTITIONS | SSANORM_USE_COALESCE_LIST)) == 0)
699     flags |= SSANORM_COALESCE_PARTITIONS;
700   
701   liveinfo = calculate_live_on_entry (map);
702   calculate_live_on_exit (liveinfo);
703   rv = root_var_init (map);
704
705   /* Remove single element variable from the list.  */
706   root_var_compact (rv);
707
708   if (flags & SSANORM_USE_COALESCE_LIST)
709     {
710       cl = create_coalesce_list (map);
711       
712       /* Add all potential copies via PHI arguments to the list.  */
713       FOR_EACH_BB (bb)
714         {
715           for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
716             {
717               tree res = PHI_RESULT (phi);
718               int p = var_to_partition (map, res);
719               if (p == NO_PARTITION)
720                 continue;
721               for (x = 0; x < PHI_NUM_ARGS (phi); x++)
722                 {
723                   tree arg = PHI_ARG_DEF (phi, x);
724                   int p2;
725
726                   if (TREE_CODE (arg) != SSA_NAME)
727                     continue;
728                   if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
729                     continue;
730                   p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
731                   if (p2 != NO_PARTITION)
732                     add_coalesce (cl, p, p2, 1);
733                 }
734             }
735         }
736
737       /* Coalesce all the result decls together.  */
738       var = NULL_TREE;
739       i = 0;
740       for (x = 0; x < num_var_partitions (map); x++)
741         {
742           tree p = partition_to_var (map, x);
743           if (TREE_CODE (SSA_NAME_VAR(p)) == RESULT_DECL)
744             {
745               if (var == NULL_TREE)
746                 {
747                   var = p;
748                   i = x;
749                 }
750               else
751                 add_coalesce (cl, i, x, 1);
752             }
753         }
754     }
755
756   /* Build a conflict graph.  */
757   graph = build_tree_conflict_graph (liveinfo, rv, cl);
758
759   if (cl)
760     {
761       if (dump_file && (dump_flags & TDF_DETAILS))
762         {
763           fprintf (dump_file, "Before sorting:\n");
764           dump_coalesce_list (dump_file, cl);
765         }
766
767       sort_coalesce_list (cl);
768
769       if (dump_file && (dump_flags & TDF_DETAILS))
770         {
771           fprintf (dump_file, "\nAfter sorting:\n");
772           dump_coalesce_list (dump_file, cl);
773         }
774     }
775
776   /* Put the single element variables back in.  */
777   root_var_decompact (rv);
778
779   /* First, coalesce all live on entry variables to their root variable. 
780      This will ensure the first use is coming from the correct location.  */
781
782   live = sbitmap_alloc (num_var_partitions (map));
783   sbitmap_zero (live);
784
785   /* Set 'live' vector to indicate live on entry partitions.  */
786   num = num_var_partitions (map);
787   for (x = 0 ; x < num; x++)
788     {
789       var = partition_to_var (map, x);
790       if (default_def (SSA_NAME_VAR (var)) == var)
791         SET_BIT (live, x);
792     }
793
794   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
795     {
796       delete_tree_live_info (liveinfo);
797       liveinfo = NULL;
798     }
799
800   /* Assign root variable as partition representative for each live on entry
801      partition.  */
802   EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, 
803     {
804       var = root_var (rv, root_var_find (rv, x));
805       ann = var_ann (var);
806       /* If these aren't already coalesced...  */
807       if (partition_to_var (map, x) != var)
808         {
809           /* This root variable should have not already been assigned
810              to another partition which is not coalesced with this one.  */
811           gcc_assert (!ann->out_of_ssa_tag);
812
813           if (dump_file && (dump_flags & TDF_DETAILS))
814             {
815               print_exprs (dump_file, "Must coalesce ", 
816                            partition_to_var (map, x),
817                            " with the root variable ", var, ".\n");
818             }
819
820           change_partition_var (map, var, x);
821         }
822     });
823
824   sbitmap_free (live);
825
826   /* Coalesce partitions live across abnormal edges.  */
827   coalesce_abnormal_edges (map, graph, rv);
828
829   if (dump_file && (dump_flags & TDF_DETAILS))
830     dump_var_map (dump_file, map);
831
832   /* Coalesce partitions.  */
833   if (flags & SSANORM_USE_COALESCE_LIST)
834     coalesce_tpa_members (rv, graph, map, cl, 
835                           ((dump_flags & TDF_DETAILS) ? dump_file 
836                                                            : NULL));
837
838   
839   if (flags & SSANORM_COALESCE_PARTITIONS)
840     coalesce_tpa_members (rv, graph, map, NULL, 
841                           ((dump_flags & TDF_DETAILS) ? dump_file 
842                                                            : NULL));
843   if (cl)
844     delete_coalesce_list (cl);
845   root_var_delete (rv);
846   conflict_graph_delete (graph);
847
848   return liveinfo;
849 }
850
851
852 /* Take the ssa-name var_map MAP, and assign real variables to each 
853    partition.  */
854
855 static void
856 assign_vars (var_map map)
857 {
858   int x, i, num, rep;
859   tree t, var;
860   var_ann_t ann;
861   root_var_p rv;
862
863   rv = root_var_init (map);
864   if (!rv) 
865     return;
866
867   /* Coalescing may already have forced some partitions to their root 
868      variable. Find these and tag them.  */
869
870   num = num_var_partitions (map);
871   for (x = 0; x < num; x++)
872     {
873       var = partition_to_var (map, x);
874       if (TREE_CODE (var) != SSA_NAME)
875         {
876           /* Coalescing will already have verified that more than one
877              partition doesn't have the same root variable. Simply marked
878              the variable as assigned.  */
879           ann = var_ann (var);
880           ann->out_of_ssa_tag = 1;
881           if (dump_file && (dump_flags & TDF_DETAILS))
882             {
883               fprintf (dump_file, "partition %d has variable ", x);
884               print_generic_expr (dump_file, var, TDF_SLIM);
885               fprintf (dump_file, " assigned to it.\n");
886             }
887
888         }
889     }
890
891   num = root_var_num (rv);
892   for (x = 0; x < num; x++)
893     {
894       var = root_var (rv, x);
895       ann = var_ann (var);
896       for (i = root_var_first_partition (rv, x);
897            i != ROOT_VAR_NONE;
898            i = root_var_next_partition (rv, i))
899         {
900           t = partition_to_var (map, i);
901
902           if (t == var || TREE_CODE (t) != SSA_NAME)
903             continue;
904
905           rep = var_to_partition (map, t);
906           
907           if (!ann->out_of_ssa_tag)
908             {
909               if (dump_file && (dump_flags & TDF_DETAILS))
910                 print_exprs (dump_file, "", t, "  --> ", var, "\n");
911               change_partition_var (map, var, rep);
912               continue;
913             }
914
915           if (dump_file && (dump_flags & TDF_DETAILS))
916             print_exprs (dump_file, "", t, " not coalesced with ", var, 
917                          "");
918
919           var = create_temp (t);
920           change_partition_var (map, var, rep);
921           ann = var_ann (var);
922
923           if (dump_file && (dump_flags & TDF_DETAILS))
924             {
925               fprintf (dump_file, " -->  New temp:  '");
926               print_generic_expr (dump_file, var, TDF_SLIM);
927               fprintf (dump_file, "'\n");
928             }
929         }
930     }
931
932   root_var_delete (rv);
933 }
934
935
936 /* Replace use operand P with whatever variable it has been rewritten to based 
937    on the partitions in MAP.  EXPR is an optional expression vector over SSA 
938    versions which is used to replace P with an expression instead of a variable.
939    If the stmt is changed, return true.  */ 
940
941 static inline bool
942 replace_use_variable (var_map map, use_operand_p p, tree *expr)
943 {
944   tree new_var;
945   tree var = USE_FROM_PTR (p);
946
947   /* Check if we are replacing this variable with an expression.  */
948   if (expr)
949     {
950       int version = SSA_NAME_VERSION (var);
951       if (expr[version])
952         {
953           tree new_expr = TREE_OPERAND (expr[version], 1);
954           SET_USE (p, new_expr);
955           /* Clear the stmt's RHS, or GC might bite us.  */
956           TREE_OPERAND (expr[version], 1) = NULL_TREE;
957           return true;
958         }
959     }
960
961   new_var = var_to_partition_to_var (map, var);
962   if (new_var)
963     {
964       SET_USE (p, new_var);
965       set_is_used (new_var);
966       return true;
967     }
968   return false;
969 }
970
971
972 /* Replace def operand DEF_P with whatever variable it has been rewritten to 
973    based on the partitions in MAP.  EXPR is an optional expression vector over
974    SSA versions which is used to replace DEF_P with an expression instead of a 
975    variable.  If the stmt is changed, return true.  */ 
976
977 static inline bool
978 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
979 {
980   tree new_var;
981   tree var = DEF_FROM_PTR (def_p);
982
983   /* Check if we are replacing this variable with an expression.  */
984   if (expr)
985     {
986       int version = SSA_NAME_VERSION (var);
987       if (expr[version])
988         {
989           tree new_expr = TREE_OPERAND (expr[version], 1);
990           SET_DEF (def_p, new_expr);
991           /* Clear the stmt's RHS, or GC might bite us.  */
992           TREE_OPERAND (expr[version], 1) = NULL_TREE;
993           return true;
994         }
995     }
996
997   new_var = var_to_partition_to_var (map, var);
998   if (new_var)
999     {
1000       SET_DEF (def_p, new_var);
1001       set_is_used (new_var);
1002       return true;
1003     }
1004   return false;
1005 }
1006
1007
1008 /* Remove any PHI node which is a virtual PHI.  */
1009
1010 static void
1011 eliminate_virtual_phis (void)
1012 {
1013   basic_block bb;
1014   tree phi, next;
1015
1016   FOR_EACH_BB (bb)
1017     {
1018       for (phi = phi_nodes (bb); phi; phi = next)
1019         {
1020           next = PHI_CHAIN (phi);
1021           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1022             {
1023 #ifdef ENABLE_CHECKING
1024               int i;
1025               /* There should be no arguments of this PHI which are in
1026                  the partition list, or we get incorrect results.  */
1027               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1028                 {
1029                   tree arg = PHI_ARG_DEF (phi, i);
1030                   if (TREE_CODE (arg) == SSA_NAME 
1031                       && is_gimple_reg (SSA_NAME_VAR (arg)))
1032                     {
1033                       fprintf (stderr, "Argument of PHI is not virtual (");
1034                       print_generic_expr (stderr, arg, TDF_SLIM);
1035                       fprintf (stderr, "), but the result is :");
1036                       print_generic_stmt (stderr, phi, TDF_SLIM);
1037                       internal_error ("SSA corruption");
1038                     }
1039                 }
1040 #endif
1041               remove_phi_node (phi, NULL_TREE, bb);
1042             }
1043         }
1044     }
1045 }
1046
1047
1048 /* This routine will coalesce variables in MAP of the same type which do not 
1049    interfere with each other. LIVEINFO is the live range info for variables
1050    of interest.  This will both reduce the memory footprint of the stack, and 
1051    allow us to coalesce together local copies of globals and scalarized 
1052    component refs.  */
1053
1054 static void
1055 coalesce_vars (var_map map, tree_live_info_p liveinfo)
1056 {
1057   basic_block bb;
1058   type_var_p tv;
1059   tree var;
1060   int x, p, p2;
1061   coalesce_list_p cl;
1062   conflict_graph graph;
1063
1064   cl = create_coalesce_list (map);
1065
1066   /* Merge all the live on entry vectors for coalesced partitions.  */
1067   for (x = 0; x < num_var_partitions (map); x++)
1068     {
1069       var = partition_to_var (map, x);
1070       p = var_to_partition (map, var);
1071       if (p != x)
1072         live_merge_and_clear (liveinfo, p, x);
1073     }
1074
1075   /* When PHI nodes are turned into copies, the result of each PHI node
1076      becomes live on entry to the block. Mark these now.  */
1077   FOR_EACH_BB (bb)
1078     {
1079       tree phi, arg;
1080       int p;
1081       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1082         {
1083           p = var_to_partition (map, PHI_RESULT (phi));
1084
1085           /* Skip virtual PHI nodes.  */
1086           if (p == NO_PARTITION)
1087             continue;
1088
1089           make_live_on_entry (liveinfo, bb, p);
1090
1091           /* Each argument is a potential copy operation. Add any arguments 
1092              which are not coalesced to the result to the coalesce list.  */
1093           for (x = 0; x < PHI_NUM_ARGS (phi); x++)
1094             {
1095               arg = PHI_ARG_DEF (phi, x);
1096               if (!phi_ssa_name_p (arg))
1097                 continue;
1098               p2 = var_to_partition (map, arg);
1099               if (p2 == NO_PARTITION)
1100                 continue;
1101               if (p != p2)
1102                 add_coalesce (cl, p, p2, 1);
1103             }
1104         }
1105    }
1106
1107   
1108   /* Re-calculate live on exit info.  */
1109   calculate_live_on_exit (liveinfo);
1110
1111   if (dump_file && (dump_flags & TDF_DETAILS))
1112     {
1113       fprintf (dump_file, "Live range info for variable memory coalescing.\n");
1114       dump_live_info (dump_file, liveinfo, LIVEDUMP_ALL);
1115
1116       fprintf (dump_file, "Coalesce list from phi nodes:\n");
1117       dump_coalesce_list (dump_file, cl);
1118     }
1119
1120
1121   tv = type_var_init (map);
1122   if (dump_file)
1123     type_var_dump (dump_file, tv);
1124   type_var_compact (tv);
1125   if (dump_file)
1126     type_var_dump (dump_file, tv);
1127
1128   graph = build_tree_conflict_graph (liveinfo, tv, cl);
1129
1130   type_var_decompact (tv);
1131   if (dump_file && (dump_flags & TDF_DETAILS))
1132     {
1133       fprintf (dump_file, "type var list now looks like:n");
1134       type_var_dump (dump_file, tv);
1135
1136       fprintf (dump_file, "Coalesce list after conflict graph build:\n");
1137       dump_coalesce_list (dump_file, cl);
1138     }
1139
1140   sort_coalesce_list (cl);
1141   if (dump_file && (dump_flags & TDF_DETAILS))
1142     {
1143       fprintf (dump_file, "Coalesce list after sorting:\n");
1144       dump_coalesce_list (dump_file, cl);
1145     }
1146
1147   coalesce_tpa_members (tv, graph, map, cl, 
1148                         ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1149
1150   type_var_delete (tv);
1151   delete_coalesce_list (cl);
1152 }
1153
1154
1155 /* Temporary Expression Replacement (TER)
1156
1157    Replace SSA version variables during out-of-ssa with their defining
1158    expression if there is only one use of the variable.
1159
1160    A pass is made through the function, one block at a time.  No cross block
1161    information is tracked.
1162
1163    Variables which only have one use, and whose defining stmt is considered
1164    a replaceable expression (see check_replaceable) are entered into 
1165    consideration by adding a list of dependent partitions to the version_info
1166    vector for that ssa_name_version.  This information comes from the partition
1167    mapping for each USE.  At the same time, the partition_dep_list vector for 
1168    these partitions have this version number entered into their lists.
1169
1170    When the use of a replaceable ssa_variable is encountered, the dependence
1171    list in version_info[] is moved to the "pending_dependence" list in case
1172    the current expression is also replaceable. (To be determined later in 
1173    processing this stmt.) version_info[] for the version is then updated to 
1174    point to the defining stmt and the 'replaceable' bit is set.
1175
1176    Any partition which is defined by a statement 'kills' any expression which
1177    is dependent on this partition.  Every ssa version in the partitions' 
1178    dependence list is removed from future consideration.
1179
1180    All virtual references are lumped together.  Any expression which is
1181    dependent on any virtual variable (via a VUSE) has a dependence added
1182    to the special partition defined by VIRTUAL_PARTITION.
1183
1184    Whenever a V_MAY_DEF is seen, all expressions dependent this 
1185    VIRTUAL_PARTITION are removed from consideration.
1186
1187    At the end of a basic block, all expression are removed from consideration
1188    in preparation for the next block.  
1189    
1190    The end result is a vector over SSA_NAME_VERSION which is passed back to
1191    rewrite_out_of_ssa.  As the SSA variables are being rewritten, instead of
1192    replacing the SSA_NAME tree element with the partition it was assigned, 
1193    it is replaced with the RHS of the defining expression.  */
1194
1195
1196 /* Dependency list element.  This can contain either a partition index or a
1197    version number, depending on which list it is in.  */
1198
1199 typedef struct value_expr_d 
1200 {
1201   int value;
1202   struct value_expr_d *next;
1203 } *value_expr_p;
1204
1205
1206 /* Temporary Expression Replacement (TER) table information.  */
1207
1208 typedef struct temp_expr_table_d 
1209 {
1210   var_map map;
1211   void **version_info;          
1212   value_expr_p *partition_dep_list;
1213   bitmap replaceable;
1214   bool saw_replaceable;
1215   int virtual_partition;
1216   bitmap partition_in_use;
1217   value_expr_p free_list;
1218   value_expr_p pending_dependence;
1219 } *temp_expr_table_p;
1220
1221 /* Used to indicate a dependency on V_MAY_DEFs.  */
1222 #define VIRTUAL_PARTITION(table)        (table->virtual_partition)
1223
1224 static temp_expr_table_p new_temp_expr_table (var_map);
1225 static tree *free_temp_expr_table (temp_expr_table_p);
1226 static inline value_expr_p new_value_expr (temp_expr_table_p);
1227 static inline void free_value_expr (temp_expr_table_p, value_expr_p);
1228 static inline value_expr_p find_value_in_list (value_expr_p, int, 
1229                                                value_expr_p *);
1230 static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
1231 static inline void add_info_to_list (temp_expr_table_p, value_expr_p *, 
1232                                      value_expr_p);
1233 static value_expr_p remove_value_from_list (value_expr_p *, int);
1234 static void add_dependance (temp_expr_table_p, int, tree);
1235 static bool check_replaceable (temp_expr_table_p, tree);
1236 static void finish_expr (temp_expr_table_p, int, bool);
1237 static void mark_replaceable (temp_expr_table_p, tree);
1238 static inline void kill_expr (temp_expr_table_p, int, bool);
1239 static inline void kill_virtual_exprs (temp_expr_table_p, bool);
1240 static void find_replaceable_in_bb (temp_expr_table_p, basic_block);
1241 static tree *find_replaceable_exprs (var_map);
1242 static void dump_replaceable_exprs (FILE *, tree *);
1243
1244
1245 /* Create a new TER table for MAP.  */
1246
1247 static temp_expr_table_p
1248 new_temp_expr_table (var_map map)
1249 {
1250   temp_expr_table_p t;
1251
1252   t = (temp_expr_table_p) xmalloc (sizeof (struct temp_expr_table_d));
1253   t->map = map;
1254
1255   t->version_info = xcalloc (num_ssa_names + 1, sizeof (void *));
1256   t->partition_dep_list = xcalloc (num_var_partitions (map) + 1, 
1257                                    sizeof (value_expr_p));
1258
1259   t->replaceable = BITMAP_XMALLOC ();
1260   t->partition_in_use = BITMAP_XMALLOC ();
1261
1262   t->saw_replaceable = false;
1263   t->virtual_partition = num_var_partitions (map);
1264   t->free_list = NULL;
1265   t->pending_dependence = NULL;
1266
1267   return t;
1268 }
1269
1270
1271 /* Free TER table T.  If there are valid replacements, return the expression 
1272    vector.  */
1273
1274 static tree *
1275 free_temp_expr_table (temp_expr_table_p t)
1276 {
1277   value_expr_p p;
1278   tree *ret = NULL;
1279
1280 #ifdef ENABLE_CHECKING
1281   int x;
1282   for (x = 0; x <= num_var_partitions (t->map); x++)
1283     if (t->partition_dep_list[x] != NULL)
1284       gcc_unreachable ();
1285 #endif
1286
1287   while ((p = t->free_list))
1288     {
1289       t->free_list = p->next;
1290       free (p);
1291     }
1292
1293   BITMAP_XFREE (t->partition_in_use);
1294   BITMAP_XFREE (t->replaceable);
1295
1296   free (t->partition_dep_list);
1297   if (t->saw_replaceable)
1298     ret = (tree *)t->version_info;
1299   else
1300     free (t->version_info);
1301   
1302   free (t);
1303   return ret;
1304 }
1305
1306
1307 /* Allocate a new value list node. Take it from the free list in TABLE if 
1308    possible.  */
1309
1310 static inline value_expr_p
1311 new_value_expr (temp_expr_table_p table)
1312 {
1313   value_expr_p p;
1314   if (table->free_list)
1315     {
1316       p = table->free_list;
1317       table->free_list = p->next;
1318     }
1319   else
1320     p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
1321
1322   return p;
1323 }
1324
1325
1326 /* Add value list node P to the free list in TABLE.  */
1327
1328 static inline void
1329 free_value_expr (temp_expr_table_p table, value_expr_p p)
1330 {
1331   p->next = table->free_list;
1332   table->free_list = p;
1333 }
1334
1335
1336 /* Find VALUE if its in LIST.  Return a pointer to the list object if found,  
1337    else return NULL.  If LAST_PTR is provided, it will point to the previous 
1338    item upon return, or NULL if this is the first item in the list.  */
1339
1340 static inline value_expr_p
1341 find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
1342 {
1343   value_expr_p curr;
1344   value_expr_p last = NULL;
1345
1346   for (curr = list; curr; last = curr, curr = curr->next)
1347     {
1348       if (curr->value == value)
1349         break;
1350     }
1351   if (last_ptr)
1352     *last_ptr = last;
1353   return curr;
1354 }
1355
1356
1357 /* Add VALUE to LIST, if it isn't already present.  TAB is the expression 
1358    table */
1359
1360 static inline void
1361 add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
1362 {
1363   value_expr_p info;
1364
1365   if (!find_value_in_list (*list, value, NULL))
1366     {
1367       info = new_value_expr (tab);
1368       info->value = value;
1369       info->next = *list;
1370       *list = info;
1371     }
1372 }
1373
1374
1375 /* Add value node INFO if it's value isn't already in LIST.  Free INFO if
1376    it is already in the list. TAB is the expression table.  */
1377
1378 static inline void
1379 add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
1380 {
1381   if (find_value_in_list (*list, info->value, NULL))
1382     free_value_expr (tab, info);
1383   else
1384     {
1385       info->next = *list;
1386       *list = info;
1387     }
1388 }
1389
1390
1391 /* Look for VALUE in LIST.  If found, remove it from the list and return it's 
1392    pointer.  */
1393
1394 static value_expr_p
1395 remove_value_from_list (value_expr_p *list, int value)
1396 {
1397   value_expr_p info, last;
1398
1399   info = find_value_in_list (*list, value, &last);
1400   if (!info)
1401     return NULL;
1402   if (!last)
1403     *list = info->next;
1404   else
1405     last->next = info->next;
1406  
1407   return info;
1408 }
1409
1410
1411 /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is 
1412    replaceable by an expression, add a dependence each of the elements of the 
1413    expression.  These are contained in the pending list.  TAB is the
1414    expression table.  */
1415
1416 static void
1417 add_dependance (temp_expr_table_p tab, int version, tree var)
1418 {
1419   int i, x;
1420   value_expr_p info;
1421
1422   i = SSA_NAME_VERSION (var);
1423   if (bitmap_bit_p (tab->replaceable, i))
1424     {
1425       /* This variable is being substituted, so use whatever dependences
1426          were queued up when we marked this as replaceable earlier.  */
1427       while ((info = tab->pending_dependence))
1428         {
1429           tab->pending_dependence = info->next;
1430           /* Get the partition this variable was dependent on. Reuse this
1431              object to represent the current  expression instead.  */
1432           x = info->value;
1433           info->value = version;
1434           add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
1435           add_value_to_list (tab, 
1436                              (value_expr_p *)&(tab->version_info[version]), x);
1437           bitmap_set_bit (tab->partition_in_use, x);
1438         }
1439     }
1440   else
1441     {
1442       i = var_to_partition (tab->map, var);
1443       gcc_assert (i != NO_PARTITION);
1444       add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
1445       add_value_to_list (tab, 
1446                          (value_expr_p *)&(tab->version_info[version]), i);
1447       bitmap_set_bit (tab->partition_in_use, i);
1448     }
1449 }
1450
1451
1452 /* Check if expression STMT is suitable for replacement in table TAB.  If so, 
1453    create an expression entry.  Return true if this stmt is replaceable.  */
1454
1455 static bool
1456 check_replaceable (temp_expr_table_p tab, tree stmt)
1457 {
1458   stmt_ann_t ann;
1459   vuse_optype vuseops;
1460   def_optype defs;
1461   use_optype uses;
1462   tree var, def;
1463   int num_use_ops, version;
1464   var_map map = tab->map;
1465   ssa_op_iter iter;
1466
1467   if (TREE_CODE (stmt) != MODIFY_EXPR)
1468     return false;
1469   
1470   ann = stmt_ann (stmt);
1471   defs = DEF_OPS (ann);
1472
1473   /* Punt if there is more than 1 def, or more than 1 use.  */
1474   if (NUM_DEFS (defs) != 1)
1475     return false;
1476   def = DEF_OP (defs, 0);
1477   if (version_ref_count (map, def) != 1)
1478     return false;
1479
1480   /* Assignments to variables assigned to hard registers are not
1481      replaceable.  */
1482   if (DECL_HARD_REGISTER (SSA_NAME_VAR (def)))
1483     return false;
1484
1485   /* There must be no V_MAY_DEFS.  */
1486   if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) != 0)
1487     return false;
1488
1489   /* There must be no V_MUST_DEFS.  */
1490   if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) != 0)
1491     return false;
1492
1493   /* Float expressions must go through memory if float-store is on.  */
1494   if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
1495     return false;
1496
1497   uses = USE_OPS (ann);
1498   num_use_ops = NUM_USES (uses);
1499   vuseops = VUSE_OPS (ann);
1500
1501   /* Any expression which has no virtual operands and no real operands
1502      should have been propagated if it's possible to do anything with them. 
1503      If this happens here, it probably exists that way for a reason, so we 
1504      won't touch it.   An example is:
1505          b_4 = &tab
1506      There are no virtual uses nor any real uses, so we just leave this 
1507      alone to be safe.  */
1508
1509   if (num_use_ops == 0 && NUM_VUSES (vuseops) == 0)
1510     return false;
1511
1512   version = SSA_NAME_VERSION (def);
1513
1514   /* Add this expression to the dependency list for each use partition.  */
1515   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1516     {
1517       add_dependance (tab, version, var);
1518     }
1519
1520   /* If there are VUSES, add a dependence on virtual defs.  */
1521   if (NUM_VUSES (vuseops) != 0)
1522     {
1523       add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]), 
1524                          VIRTUAL_PARTITION (tab));
1525       add_value_to_list (tab, 
1526                          &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]), 
1527                          version);
1528       bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
1529     }
1530
1531   return true;
1532 }
1533
1534
1535 /* This function will remove the expression for VERSION from replacement 
1536    consideration.n table TAB  If 'replace' is true, it is marked as 
1537    replaceable, otherwise not.  */
1538
1539 static void
1540 finish_expr (temp_expr_table_p tab, int version, bool replace)
1541 {
1542   value_expr_p info, tmp;
1543   int partition;
1544
1545   /* Remove this expression from its dependent lists.  The partition dependence
1546      list is retained and transfered later to whomever uses this version.  */
1547   for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
1548     {
1549       partition = info->value;
1550       gcc_assert (tab->partition_dep_list[partition]);
1551       tmp = remove_value_from_list (&(tab->partition_dep_list[partition]), 
1552                                     version);
1553       gcc_assert (tmp);
1554       free_value_expr (tab, tmp);
1555       /* Only clear the bit when the dependency list is emptied via 
1556          a replacement. Otherwise kill_expr will take care of it.  */
1557       if (!(tab->partition_dep_list[partition]) && replace)
1558         bitmap_clear_bit (tab->partition_in_use, partition);
1559       tmp = info->next;
1560       if (!replace)
1561         free_value_expr (tab, info);
1562     }
1563
1564   if (replace)
1565     {
1566       tab->saw_replaceable = true;
1567       bitmap_set_bit (tab->replaceable, version);
1568     }
1569   else
1570     {
1571       gcc_assert (!bitmap_bit_p (tab->replaceable, version));
1572       tab->version_info[version] = NULL;
1573     }
1574 }
1575
1576
1577 /* Mark the expression associated with VAR as replaceable, and enter
1578    the defining stmt into the version_info table TAB.  */
1579
1580 static void
1581 mark_replaceable (temp_expr_table_p tab, tree var)
1582 {
1583   value_expr_p info;
1584   int version = SSA_NAME_VERSION (var);
1585   finish_expr (tab, version, true);
1586
1587   /* Move the dependence list to the pending list.  */
1588   if (tab->version_info[version])
1589     {
1590       info = (value_expr_p) tab->version_info[version]; 
1591       for ( ; info->next; info = info->next)
1592         continue;
1593       info->next = tab->pending_dependence;
1594       tab->pending_dependence = (value_expr_p)tab->version_info[version];
1595     }
1596
1597   tab->version_info[version] = SSA_NAME_DEF_STMT (var);
1598 }
1599
1600
1601 /* This function marks any expression in TAB which is dependent on PARTITION
1602    as NOT replaceable.  CLEAR_BIT is used to determine whether partition_in_use
1603    should have its bit cleared.  Since this routine can be called within an
1604    EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared.  */
1605
1606 static inline void
1607 kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
1608 {
1609   value_expr_p ptr;
1610
1611   /* Mark every active expr dependent on this var as not replaceable.  */
1612   while ((ptr = tab->partition_dep_list[partition]) != NULL)
1613     finish_expr (tab, ptr->value, false);
1614
1615   if (clear_bit)
1616     bitmap_clear_bit (tab->partition_in_use, partition);
1617 }
1618
1619
1620 /* This function kills all expressions in TAB which are dependent on virtual 
1621    DEFs.  CLEAR_BIT determines whether partition_in_use gets cleared.  */
1622
1623 static inline void
1624 kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
1625 {
1626   kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
1627 }
1628
1629
1630 /* This function processes basic block BB, and looks for variables which can
1631    be replaced by their expressions.  Results are stored in TAB.  */
1632
1633 static void
1634 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
1635 {
1636   block_stmt_iterator bsi;
1637   tree stmt, def;
1638   stmt_ann_t ann;
1639   int partition;
1640   var_map map = tab->map;
1641   value_expr_p p;
1642   ssa_op_iter iter;
1643
1644   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1645     {
1646       stmt = bsi_stmt (bsi);
1647       ann = stmt_ann (stmt);
1648
1649       /* Determine if this stmt finishes an existing expression.  */
1650       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_USE)
1651         {
1652           if (tab->version_info[SSA_NAME_VERSION (def)])
1653             {
1654               /* Mark expression as replaceable unless stmt is volatile.  */
1655               if (!ann->has_volatile_ops)
1656                 mark_replaceable (tab, def);
1657               else
1658                 finish_expr (tab, SSA_NAME_VERSION (def), false);
1659             }
1660         }
1661       
1662       /* Next, see if this stmt kills off an active expression.  */
1663       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1664         {
1665           partition = var_to_partition (map, def);
1666           if (partition != NO_PARTITION && tab->partition_dep_list[partition])
1667             kill_expr (tab, partition, true);
1668         }
1669
1670       /* Now see if we are creating a new expression or not.  */
1671       if (!ann->has_volatile_ops)
1672         check_replaceable (tab, stmt);
1673
1674       /* Free any unused dependency lists.  */
1675       while ((p = tab->pending_dependence))
1676         {
1677           tab->pending_dependence = p->next;
1678           free_value_expr (tab, p);
1679         }
1680
1681       /* A V_MAY_DEF kills any expression using a virtual operand.  */
1682       if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0)
1683         kill_virtual_exprs (tab, true);
1684         
1685       /* A V_MUST_DEF kills any expression using a virtual operand.  */
1686       if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0)
1687         kill_virtual_exprs (tab, true);
1688     }
1689 }
1690
1691
1692 /* This function is the driver routine for replacement of temporary expressions
1693    in the SSA->normal phase, operating on MAP.  If there are replaceable 
1694    expressions, a table is returned which maps SSA versions to the 
1695    expressions they should be replaced with.  A NULL_TREE indicates no 
1696    replacement should take place.  If there are no replacements at all, 
1697    NULL is returned by the function, otherwise an expression vector indexed
1698    by SSA_NAME version numbers.  */
1699
1700 static tree *
1701 find_replaceable_exprs (var_map map)
1702 {
1703   basic_block bb;
1704   int i;
1705   temp_expr_table_p table;
1706   tree *ret;
1707
1708   table = new_temp_expr_table (map);
1709   FOR_EACH_BB (bb)
1710     {
1711       find_replaceable_in_bb (table, bb);
1712       EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i,
1713         {
1714           kill_expr (table, i, false);
1715         });
1716     }
1717
1718   ret = free_temp_expr_table (table);
1719   return ret;
1720 }
1721
1722
1723 /* Dump TER expression table EXPR to file F.  */
1724
1725 static void
1726 dump_replaceable_exprs (FILE *f, tree *expr)
1727 {
1728   tree stmt, var;
1729   int x;
1730   fprintf (f, "\nReplacing Expressions\n");
1731   for (x = 0; x < (int)num_ssa_names + 1; x++)
1732     if (expr[x])
1733       {
1734         stmt = expr[x];
1735         var = DEF_OP (STMT_DEF_OPS (stmt), 0);
1736         print_generic_expr (f, var, TDF_SLIM);
1737         fprintf (f, " replace with --> ");
1738         print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
1739         fprintf (f, "\n");
1740       }
1741   fprintf (f, "\n");
1742 }
1743
1744
1745 /* Helper function for discover_nonconstant_array_refs. 
1746    Look for ARRAY_REF nodes with non-constant indexes and mark them
1747    addressable.  */
1748
1749 static tree
1750 discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
1751                                    void *data ATTRIBUTE_UNUSED)
1752 {
1753   tree t = *tp;
1754
1755   if (TYPE_P (t) || DECL_P (t))
1756     *walk_subtrees = 0;
1757   else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1758     {
1759       while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1760               && is_gimple_min_invariant (TREE_OPERAND (t, 1))
1761               && (!TREE_OPERAND (t, 2)
1762                   || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1763              || (TREE_CODE (t) == COMPONENT_REF
1764                  && (!TREE_OPERAND (t,2)
1765                      || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1766              || TREE_CODE (t) == BIT_FIELD_REF
1767              || TREE_CODE (t) == REALPART_EXPR
1768              || TREE_CODE (t) == IMAGPART_EXPR
1769              || TREE_CODE (t) == VIEW_CONVERT_EXPR
1770              || TREE_CODE (t) == NOP_EXPR
1771              || TREE_CODE (t) == CONVERT_EXPR)
1772         t = TREE_OPERAND (t, 0);
1773
1774       if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1775         {
1776           t = get_base_address (t);
1777           if (t && DECL_P (t))
1778             TREE_ADDRESSABLE (t) = 1;
1779         }
1780
1781       *walk_subtrees = 0;
1782     }
1783
1784   return NULL_TREE;
1785 }
1786
1787
1788 /* RTL expansion is not able to compile array references with variable
1789    offsets for arrays stored in single register.  Discover such
1790    expressions and mark variables as addressable to avoid this
1791    scenario.  */
1792
1793 static void
1794 discover_nonconstant_array_refs (void)
1795 {
1796   basic_block bb;
1797   block_stmt_iterator bsi;
1798
1799   FOR_EACH_BB (bb)
1800     {
1801       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1802         walk_tree (bsi_stmt_ptr (bsi), discover_nonconstant_array_refs_r,
1803                    NULL , NULL);
1804     }
1805 }
1806
1807
1808 /* This function will rewrite the current program using the variable mapping
1809    found in MAP.  If the replacement vector VALUES is provided, any 
1810    occurrences of partitions with non-null entries in the vector will be 
1811    replaced with the expression in the vector instead of its mapped 
1812    variable.  */
1813
1814 static void
1815 rewrite_trees (var_map map, tree *values)
1816 {
1817   elim_graph g;
1818   basic_block bb;
1819   block_stmt_iterator si;
1820   edge e;
1821   tree phi;
1822   bool changed;
1823  
1824 #ifdef ENABLE_CHECKING
1825   /* Search for PHIs where the destination has no partition, but one
1826      or more arguments has a partition.  This should not happen and can
1827      create incorrect code.  */
1828   FOR_EACH_BB (bb)
1829     {
1830       tree phi;
1831
1832       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1833         {
1834           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1835       
1836           if (T0 == NULL_TREE)
1837             {
1838               int i;
1839
1840               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1841                 {
1842                   tree arg = PHI_ARG_DEF (phi, i);
1843
1844                   if (TREE_CODE (arg) == SSA_NAME
1845                       && var_to_partition (map, arg) != NO_PARTITION)
1846                     {
1847                       fprintf (stderr, "Argument of PHI is in a partition :(");
1848                       print_generic_expr (stderr, arg, TDF_SLIM);
1849                       fprintf (stderr, "), but the result is not :");
1850                       print_generic_stmt (stderr, phi, TDF_SLIM);
1851                       internal_error ("SSA corruption");
1852                     }
1853                 }
1854             }
1855         }
1856     }
1857 #endif
1858
1859   /* Replace PHI nodes with any required copies.  */
1860   g = new_elim_graph (map->num_partitions);
1861   g->map = map;
1862   FOR_EACH_BB (bb)
1863     {
1864       for (si = bsi_start (bb); !bsi_end_p (si); )
1865         {
1866           size_t num_uses, num_defs;
1867           use_optype uses;
1868           def_optype defs;
1869           tree stmt = bsi_stmt (si);
1870           use_operand_p use_p;
1871           def_operand_p def_p;
1872           int remove = 0, is_copy = 0;
1873           stmt_ann_t ann;
1874           ssa_op_iter iter;
1875
1876           get_stmt_operands (stmt);
1877           ann = stmt_ann (stmt);
1878           changed = false;
1879
1880           if (TREE_CODE (stmt) == MODIFY_EXPR 
1881               && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
1882             is_copy = 1;
1883
1884           uses = USE_OPS (ann);
1885           num_uses = NUM_USES (uses);
1886           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1887             {
1888               if (replace_use_variable (map, use_p, values))
1889                 changed = true;
1890             }
1891
1892           defs = DEF_OPS (ann);
1893           num_defs = NUM_DEFS (defs);
1894
1895           /* Mark this stmt for removal if it is the list of replaceable 
1896              expressions.  */
1897           if (values && num_defs == 1)
1898             {
1899               tree def = DEF_OP (defs, 0);
1900               tree val;
1901               val = values[SSA_NAME_VERSION (def)];
1902               if (val)
1903                 remove = 1;
1904             }
1905           if (!remove)
1906             {
1907               FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1908                 {
1909                   if (replace_def_variable (map, def_p, NULL))
1910                     changed = true;
1911
1912                   /* If both SSA_NAMEs coalesce to the same variable,
1913                      mark the now redundant copy for removal.  */
1914                   if (is_copy
1915                       && num_uses == 1
1916                       && (DEF_FROM_PTR (def_p) == USE_OP (uses, 0)))
1917                     remove = 1;
1918                 }
1919               if (changed & !remove)
1920                 modify_stmt (stmt);
1921             }
1922
1923           /* Remove any stmts marked for removal.  */
1924           if (remove)
1925             bsi_remove (&si);
1926           else
1927             bsi_next (&si);
1928         }
1929
1930       phi = phi_nodes (bb);
1931       if (phi)
1932         {
1933           for (e = bb->pred; e; e = e->pred_next)
1934             eliminate_phi (e, phi_arg_from_edge (phi, e), g);
1935         }
1936     }
1937
1938   delete_elim_graph (g);
1939
1940   /* If any copies were inserted on edges, actually insert them now.  */
1941   bsi_commit_edge_inserts (NULL);
1942 }
1943
1944
1945 /* Remove the variables specified in MAP from SSA form.  Any debug information
1946    is sent to DUMP.  FLAGS indicate what options should be used.  */
1947
1948 static void
1949 remove_ssa_form (FILE *dump, var_map map, int flags)
1950 {
1951   tree_live_info_p liveinfo;
1952   basic_block bb;
1953   tree phi, next;
1954   FILE *save;
1955   tree *values = NULL;
1956
1957   save = dump_file;
1958   dump_file = dump;
1959
1960   /* If we are not combining temps, don't calculate live ranges for variables
1961      with only one SSA version.  */
1962   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
1963     compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
1964   else
1965     compact_var_map (map, VARMAP_NORMAL);
1966
1967   if (dump_file && (dump_flags & TDF_DETAILS))
1968     dump_var_map (dump_file, map);
1969
1970   liveinfo = coalesce_ssa_name (map, flags);
1971
1972   /* Make sure even single occurrence variables are in the list now.  */
1973   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
1974     compact_var_map (map, VARMAP_NORMAL);
1975
1976   if (dump_file && (dump_flags & TDF_DETAILS))
1977     {
1978       fprintf (dump_file, "After Coalescing:\n");
1979       dump_var_map (dump_file, map);
1980     }
1981
1982   if (flags & SSANORM_PERFORM_TER)
1983     {
1984       values = find_replaceable_exprs (map);
1985       if (values && dump_file && (dump_flags & TDF_DETAILS))
1986         dump_replaceable_exprs (dump_file, values);
1987     }
1988
1989   /* Assign real variables to the partitions now.  */
1990   assign_vars (map);
1991
1992   if (dump_file && (dump_flags & TDF_DETAILS))
1993     {
1994       fprintf (dump_file, "After Root variable replacement:\n");
1995       dump_var_map (dump_file, map);
1996     }
1997
1998   if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo)
1999     {
2000       coalesce_vars (map, liveinfo);
2001       if (dump_file && (dump_flags & TDF_DETAILS))
2002         {
2003           fprintf (dump_file, "After variable memory coalescing:\n");
2004           dump_var_map (dump_file, map);
2005         }
2006     }
2007   
2008   if (liveinfo)
2009     delete_tree_live_info (liveinfo);
2010
2011   rewrite_trees (map, values);
2012
2013   if (values)
2014     free (values);
2015
2016   /* Remove phi nodes which have been translated back to real variables.  */
2017   FOR_EACH_BB (bb)
2018     {
2019       for (phi = phi_nodes (bb); phi; phi = next)
2020         {
2021           next = PHI_CHAIN (phi);
2022           if ((flags & SSANORM_REMOVE_ALL_PHIS) 
2023               || var_to_partition (map, PHI_RESULT (phi)) != NO_PARTITION)
2024             remove_phi_node (phi, NULL_TREE, bb);
2025         }
2026     }
2027
2028   dump_file = save;
2029 }
2030
2031 /* Take the current function out of SSA form, as described in
2032    R. Morgan, ``Building an Optimizing Compiler'',
2033    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
2034
2035 static void
2036 rewrite_out_of_ssa (void)
2037 {
2038   var_map map;
2039   int var_flags = 0;
2040   int ssa_flags = (SSANORM_REMOVE_ALL_PHIS | SSANORM_USE_COALESCE_LIST);
2041
2042   if (!flag_tree_live_range_split)
2043     ssa_flags |= SSANORM_COALESCE_PARTITIONS;
2044     
2045   eliminate_virtual_phis ();
2046
2047   if (dump_file && (dump_flags & TDF_DETAILS))
2048     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2049
2050   /* We cannot allow unssa to un-gimplify trees before we instrument them.  */
2051   if (flag_tree_ter && !flag_mudflap)
2052     var_flags = SSA_VAR_MAP_REF_COUNT;
2053
2054   map = create_ssa_var_map (var_flags);
2055
2056   if (flag_tree_combine_temps)
2057     ssa_flags |= SSANORM_COMBINE_TEMPS;
2058   if (flag_tree_ter && !flag_mudflap)
2059     ssa_flags |= SSANORM_PERFORM_TER;
2060
2061   remove_ssa_form (dump_file, map, ssa_flags);
2062
2063   if (dump_file && (dump_flags & TDF_DETAILS))
2064     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2065
2066   /* Do some cleanups which reduce the amount of data the
2067      tree->rtl expanders deal with.  */
2068   cfg_remove_useless_stmts ();
2069
2070   /* Flush out flow graph and SSA data.  */
2071   delete_var_map (map);
2072
2073   /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE.  */
2074   discover_nonconstant_array_refs ();
2075 }
2076
2077
2078 /* Define the parameters of the out of SSA pass.  */
2079
2080 struct tree_opt_pass pass_del_ssa = 
2081 {
2082   "optimized",                          /* name */
2083   NULL,                                 /* gate */
2084   rewrite_out_of_ssa,                   /* execute */
2085   NULL,                                 /* sub */
2086   NULL,                                 /* next */
2087   0,                                    /* static_pass_number */
2088   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
2089   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2090   0,                                    /* properties_provided */
2091   /* ??? If TER is enabled, we also kill gimple.  */
2092   PROP_ssa,                             /* properties_destroyed */
2093   TODO_verify_ssa | TODO_verify_flow
2094     | TODO_verify_stmts,                /* todo_flags_start */
2095   TODO_dump_func | TODO_ggc_collect,    /* todo_flags_finish */
2096   0                                     /* letter */
2097 };