OSDN Git Service

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