OSDN Git Service

2006-01-05 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-live.c
1 /* Liveness for SSA trees.
2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3    Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, 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 "basic-block.h"
29 #include "function.h"
30 #include "diagnostic.h"
31 #include "bitmap.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-inline.h"
35 #include "varray.h"
36 #include "timevar.h"
37 #include "hashtab.h"
38 #include "tree-dump.h"
39 #include "tree-ssa-live.h"
40 #include "toplev.h"
41
42 static void live_worklist (tree_live_info_p, int *, int);
43 static tree_live_info_p new_tree_live_info (var_map);
44 static inline void set_if_valid (var_map, bitmap, tree);
45 static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
46                                          tree, basic_block);
47 static inline void register_ssa_partition (var_map, tree, bool);
48 static inline void add_conflicts_if_valid (tpa_p, conflict_graph,
49                                            var_map, bitmap, tree);
50 static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool);
51
52 /* This is where the mapping from SSA version number to real storage variable
53    is tracked.  
54
55    All SSA versions of the same variable may not ultimately be mapped back to
56    the same real variable. In that instance, we need to detect the live
57    range overlap, and give one of the variable new storage. The vector
58    'partition_to_var' tracks which partition maps to which variable.
59
60    Given a VAR, it is sometimes desirable to know which partition that VAR
61    represents.  There is an additional field in the variable annotation to
62    track that information.  */
63
64 /* Create a variable partition map of SIZE, initialize and return it.  */
65
66 var_map
67 init_var_map (int size)
68 {
69   var_map map;
70
71   map = (var_map) xmalloc (sizeof (struct _var_map));
72   map->var_partition = partition_new (size);
73   map->partition_to_var 
74               = (tree *)xmalloc (size * sizeof (tree));
75   memset (map->partition_to_var, 0, size * sizeof (tree));
76
77   map->partition_to_compact = NULL;
78   map->compact_to_partition = NULL;
79   map->num_partitions = size;
80   map->partition_size = size;
81   map->ref_count = NULL;
82   return map;
83 }
84
85
86 /* Free memory associated with MAP.  */
87
88 void
89 delete_var_map (var_map map)
90 {
91   free (map->partition_to_var);
92   partition_delete (map->var_partition);
93   if (map->partition_to_compact)
94     free (map->partition_to_compact);
95   if (map->compact_to_partition)
96     free (map->compact_to_partition);
97   if (map->ref_count)
98     free (map->ref_count);
99   free (map);
100 }
101
102
103 /* This function will combine the partitions in MAP for VAR1 and VAR2.  It 
104    Returns the partition which represents the new partition.  If the two 
105    partitions cannot be combined, NO_PARTITION is returned.  */
106
107 int
108 var_union (var_map map, tree var1, tree var2)
109 {
110   int p1, p2, p3;
111   tree root_var = NULL_TREE;
112   tree other_var = NULL_TREE;
113
114   /* This is independent of partition_to_compact. If partition_to_compact is 
115      on, then whichever one of these partitions is absorbed will never have a
116      dereference into the partition_to_compact array any more.  */
117
118   if (TREE_CODE (var1) == SSA_NAME)
119     p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
120   else
121     {
122       p1 = var_to_partition (map, var1);
123       if (map->compact_to_partition)
124         p1 = map->compact_to_partition[p1];
125       root_var = var1;
126     }
127   
128   if (TREE_CODE (var2) == SSA_NAME)
129     p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
130   else
131     {
132       p2 = var_to_partition (map, var2);
133       if (map->compact_to_partition)
134         p2 = map->compact_to_partition[p2];
135
136       /* If there is no root_var set, or it's not a user variable, set the
137          root_var to this one.  */
138       if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
139         {
140           other_var = root_var;
141           root_var = var2;
142         }
143       else 
144         other_var = var2;
145     }
146
147   gcc_assert (p1 != NO_PARTITION);
148   gcc_assert (p2 != NO_PARTITION);
149
150   if (p1 == p2)
151     p3 = p1;
152   else
153     p3 = partition_union (map->var_partition, p1, p2);
154
155   if (map->partition_to_compact)
156     p3 = map->partition_to_compact[p3];
157
158   if (root_var)
159     change_partition_var (map, root_var, p3);
160   if (other_var)
161     change_partition_var (map, other_var, p3);
162
163   return p3;
164 }
165
166
167 /* Compress the partition numbers in MAP such that they fall in the range 
168    0..(num_partitions-1) instead of wherever they turned out during
169    the partitioning exercise.  This removes any references to unused
170    partitions, thereby allowing bitmaps and other vectors to be much
171    denser.  Compression type is controlled by FLAGS.
172
173    This is implemented such that compaction doesn't affect partitioning.
174    Ie., once partitions are created and possibly merged, running one
175    or more different kind of compaction will not affect the partitions
176    themselves.  Their index might change, but all the same variables will
177    still be members of the same partition group.  This allows work on reduced
178    sets, and no loss of information when a larger set is later desired.
179
180    In particular, coalescing can work on partitions which have 2 or more
181    definitions, and then 'recompact' later to include all the single
182    definitions for assignment to program variables.  */
183
184 void 
185 compact_var_map (var_map map, int flags)
186 {
187   sbitmap used;
188   int tmp, root, root_i;
189   unsigned int x, limit, count;
190   tree var;
191   root_var_p rv = NULL;
192
193   limit = map->partition_size;
194   used = sbitmap_alloc (limit);
195   sbitmap_zero (used);
196
197   /* Already compressed? Abandon the old one.  */
198   if (map->partition_to_compact)
199     {
200       free (map->partition_to_compact);
201       map->partition_to_compact = NULL;
202     }
203   if (map->compact_to_partition)
204     {
205       free (map->compact_to_partition);
206       map->compact_to_partition = NULL;
207     }
208
209   map->num_partitions = map->partition_size;
210
211   if (flags & VARMAP_NO_SINGLE_DEFS)
212     rv = root_var_init (map);
213
214   map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
215   memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
216
217   /* Find out which partitions are actually referenced.  */
218   count = 0;
219   for (x = 0; x < limit; x++)
220     {
221       tmp = partition_find (map->var_partition, x);
222       if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
223         {
224           /* It is referenced, check to see if there is more than one version
225              in the root_var table, if one is available.  */
226           if (rv)
227             {
228               root = root_var_find (rv, tmp);
229               root_i = root_var_first_partition (rv, root);
230               /* If there is only one, don't include this in the compaction.  */
231               if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE)
232                 continue;
233             }
234           SET_BIT (used, tmp);
235           count++;
236         }
237     }
238
239   /* Build a compacted partitioning.  */
240   if (count != limit)
241     {
242       sbitmap_iterator sbi;
243
244       map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
245       count = 0;
246       /* SSA renaming begins at 1, so skip 0 when compacting.  */
247       EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi)
248         {
249           map->partition_to_compact[x] = count;
250           map->compact_to_partition[count] = x;
251           var = map->partition_to_var[x];
252           if (TREE_CODE (var) != SSA_NAME)
253             change_partition_var (map, var, count);
254           count++;
255         }
256     }
257   else
258     {
259       free (map->partition_to_compact);
260       map->partition_to_compact = NULL;
261     }
262
263   map->num_partitions = count;
264
265   if (rv)
266     root_var_delete (rv);
267   sbitmap_free (used);
268 }
269
270
271 /* This function is used to change the representative variable in MAP for VAR's 
272    partition from an SSA_NAME variable to a regular variable.  This allows 
273    partitions to be mapped back to real variables.  */
274   
275 void 
276 change_partition_var (var_map map, tree var, int part)
277 {
278   var_ann_t ann;
279
280   gcc_assert (TREE_CODE (var) != SSA_NAME);
281
282   ann = var_ann (var);
283   ann->out_of_ssa_tag = 1;
284   VAR_ANN_PARTITION (ann) = part;
285   if (map->compact_to_partition)
286     map->partition_to_var[map->compact_to_partition[part]] = var;
287 }
288
289 static inline void mark_all_vars_used (tree *);
290
291 /* Helper function for mark_all_vars_used, called via walk_tree.  */
292
293 static tree
294 mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
295                       void *data ATTRIBUTE_UNUSED)
296 {
297   tree t = *tp;
298
299   if (TREE_CODE (t) == SSA_NAME)
300     t = SSA_NAME_VAR (t);
301
302   /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
303      fields that do not contain vars.  */
304   if (TREE_CODE (t) == TARGET_MEM_REF)
305     {
306       mark_all_vars_used (&TMR_SYMBOL (t));
307       mark_all_vars_used (&TMR_BASE (t));
308       mark_all_vars_used (&TMR_INDEX (t));
309       *walk_subtrees = 0;
310       return NULL;
311     }
312
313   /* Only need to mark VAR_DECLS; parameters and return results are not
314      eliminated as unused.  */
315   if (TREE_CODE (t) == VAR_DECL)
316     set_is_used (t);
317
318   if (IS_TYPE_OR_DECL_P (t))
319     *walk_subtrees = 0;
320
321   return NULL;
322 }
323
324 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be 
325    eliminated during the tree->rtl conversion process.  */
326
327 static inline void
328 mark_all_vars_used (tree *expr_p)
329 {
330   walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
331 }
332
333
334 /* Remove local variables that are not referenced in the IL.  */
335
336 void
337 remove_unused_locals (void)
338 {
339   basic_block bb;
340   tree t, *cell;
341
342   /* Assume all locals are unused.  */
343   for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
344     {
345       tree var = TREE_VALUE (t);
346       if (TREE_CODE (var) != FUNCTION_DECL
347           && var_ann (var))
348         var_ann (var)->used = false;
349     }
350
351   /* Walk the CFG marking all referenced symbols.  */
352   FOR_EACH_BB (bb)
353     {
354       block_stmt_iterator bsi;
355       tree phi, def;
356
357       /* Walk the statements.  */
358       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
359         mark_all_vars_used (bsi_stmt_ptr (bsi));
360
361       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
362         {
363           use_operand_p arg_p;
364           ssa_op_iter i;
365
366           /* No point processing globals.  */
367           if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
368             continue;
369
370           def = PHI_RESULT (phi);
371           mark_all_vars_used (&def);
372
373           FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
374             {
375               tree arg = USE_FROM_PTR (arg_p);
376               mark_all_vars_used (&arg);
377             }
378         }
379     }
380
381   /* Remove unmarked vars and clear used flag.  */
382   for (cell = &cfun->unexpanded_var_list; *cell; )
383     {
384       tree var = TREE_VALUE (*cell);
385       var_ann_t ann;
386
387       if (TREE_CODE (var) != FUNCTION_DECL
388           && (!(ann = var_ann (var))
389               || !ann->used))
390         {
391           *cell = TREE_CHAIN (*cell);
392           continue;
393         }
394
395       cell = &TREE_CHAIN (*cell);
396     }
397 }
398
399 /* This function looks through the program and uses FLAGS to determine what 
400    SSA versioned variables are given entries in a new partition table.  This
401    new partition map is returned.  */
402
403 var_map
404 create_ssa_var_map (int flags)
405 {
406   block_stmt_iterator bsi;
407   basic_block bb;
408   tree dest, use;
409   tree stmt;
410   var_map map;
411   ssa_op_iter iter;
412 #ifdef ENABLE_CHECKING
413   bitmap used_in_real_ops;
414   bitmap used_in_virtual_ops;
415 #endif
416
417   map = init_var_map (num_ssa_names + 1);
418
419 #ifdef ENABLE_CHECKING
420   used_in_real_ops = BITMAP_ALLOC (NULL);
421   used_in_virtual_ops = BITMAP_ALLOC (NULL);
422 #endif
423
424   if (flags & SSA_VAR_MAP_REF_COUNT)
425     {
426       map->ref_count
427         = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
428       memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
429     }
430
431   FOR_EACH_BB (bb)
432     {
433       tree phi, arg;
434
435       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
436         {
437           int i;
438           register_ssa_partition (map, PHI_RESULT (phi), false);
439           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
440             {
441               arg = PHI_ARG_DEF (phi, i);
442               if (TREE_CODE (arg) == SSA_NAME)
443                 register_ssa_partition (map, arg, true);
444
445               mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
446             }
447         }
448
449       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
450         {
451           stmt = bsi_stmt (bsi);
452
453           /* Register USE and DEF operands in each statement.  */
454           FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
455             {
456               register_ssa_partition (map, use, true);
457
458 #ifdef ENABLE_CHECKING
459               bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use)));
460 #endif
461             }
462
463           FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF)
464             {
465               register_ssa_partition (map, dest, false);
466
467 #ifdef ENABLE_CHECKING
468               bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest)));
469 #endif
470             }
471
472 #ifdef ENABLE_CHECKING
473           /* Validate that virtual ops don't get used in funny ways.  */
474           FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, 
475                                      SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
476             {
477               bitmap_set_bit (used_in_virtual_ops, 
478                               DECL_UID (SSA_NAME_VAR (use)));
479             }
480
481 #endif /* ENABLE_CHECKING */
482
483           mark_all_vars_used (bsi_stmt_ptr (bsi));
484         }
485     }
486
487 #if defined ENABLE_CHECKING
488   {
489     unsigned i;
490     bitmap both = BITMAP_ALLOC (NULL);
491     bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
492     if (!bitmap_empty_p (both))
493       {
494         bitmap_iterator bi;
495
496         EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
497           fprintf (stderr, "Variable %s used in real and virtual operands\n",
498                    get_name (referenced_var (i)));
499         internal_error ("SSA corruption");
500       }
501
502     BITMAP_FREE (used_in_real_ops);
503     BITMAP_FREE (used_in_virtual_ops);
504     BITMAP_FREE (both);
505   }
506 #endif
507
508   return map;
509 }
510
511
512 /* Allocate and return a new live range information object base on MAP.  */
513
514 static tree_live_info_p
515 new_tree_live_info (var_map map)
516 {
517   tree_live_info_p live;
518   unsigned x;
519
520   live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
521   live->map = map;
522   live->num_blocks = last_basic_block;
523
524   live->global = BITMAP_ALLOC (NULL);
525
526   live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
527   for (x = 0; x < num_var_partitions (map); x++)
528     live->livein[x] = BITMAP_ALLOC (NULL);
529
530   /* liveout is deferred until it is actually requested.  */
531   live->liveout = NULL;
532   return live;
533 }
534
535
536 /* Free storage for live range info object LIVE.  */
537
538 void 
539 delete_tree_live_info (tree_live_info_p live)
540 {
541   int x;
542   if (live->liveout)
543     {
544       for (x = live->num_blocks - 1; x >= 0; x--)
545         BITMAP_FREE (live->liveout[x]);
546       free (live->liveout);
547     }
548   if (live->livein)
549     {
550       for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
551         BITMAP_FREE (live->livein[x]);
552       free (live->livein);
553     }
554   if (live->global)
555     BITMAP_FREE (live->global);
556   
557   free (live);
558 }
559
560
561 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses 
562    for partition I.  STACK is a varray used for temporary memory which is 
563    passed in rather than being allocated on every call.  */
564
565 static void
566 live_worklist (tree_live_info_p live, int *stack, int i)
567 {
568   unsigned b;
569   tree var;
570   basic_block def_bb = NULL;
571   edge e;
572   var_map map = live->map;
573   edge_iterator ei;
574   bitmap_iterator bi;
575   int *tos = stack;
576
577   var = partition_to_var (map, i);
578   if (SSA_NAME_DEF_STMT (var))
579     def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
580
581   EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
582     {
583       *tos++ = b;
584     }
585
586   while (tos != stack)
587     {
588       b = *--tos;
589
590       FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
591         if (e->src != ENTRY_BLOCK_PTR)
592           {
593             /* Its not live on entry to the block its defined in.  */
594             if (e->src == def_bb)
595               continue;
596             if (!bitmap_bit_p (live->livein[i], e->src->index))
597               {
598                 bitmap_set_bit (live->livein[i], e->src->index);
599                 *tos++ = e->src->index;
600               }
601           }
602     }
603 }
604
605
606 /* If VAR is in a partition of MAP, set the bit for that partition in VEC.  */
607
608 static inline void
609 set_if_valid (var_map map, bitmap vec, tree var)
610 {
611   int p = var_to_partition (map, var);
612   if (p != NO_PARTITION)
613     bitmap_set_bit (vec, p);
614 }
615
616
617 /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and 
618    global bit for it in the LIVE object.  BB is the block being processed.  */
619
620 static inline void
621 add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
622                       tree var, basic_block bb)
623 {
624   int p = var_to_partition (live->map, var);
625   if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
626     return;
627   if (!bitmap_bit_p (def_vec, p))
628     {
629       bitmap_set_bit (live->livein[p], bb->index);
630       bitmap_set_bit (live->global, p);
631     }
632 }
633
634
635 /* Given partition map MAP, calculate all the live on entry bitmaps for 
636    each basic block.  Return a live info object.  */
637
638 tree_live_info_p 
639 calculate_live_on_entry (var_map map)
640 {
641   tree_live_info_p live;
642   unsigned i;
643   basic_block bb;
644   bitmap saw_def;
645   tree phi, var, stmt;
646   tree op;
647   edge e;
648   int *stack;
649   block_stmt_iterator bsi;
650   ssa_op_iter iter;
651   bitmap_iterator bi;
652 #ifdef ENABLE_CHECKING
653   int num;
654   edge_iterator ei;
655 #endif
656
657   saw_def = BITMAP_ALLOC (NULL);
658
659   live = new_tree_live_info (map);
660
661   FOR_EACH_BB (bb)
662     {
663       bitmap_clear (saw_def);
664
665       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
666         {
667           for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
668             {
669               var = PHI_ARG_DEF (phi, i);
670               if (!phi_ssa_name_p (var))
671                 continue;
672               stmt = SSA_NAME_DEF_STMT (var);
673               e = EDGE_PRED (bb, i);
674
675               /* Any uses in PHIs which either don't have def's or are not
676                  defined in the block from which the def comes, will be live
677                  on entry to that block.  */
678               if (!stmt || e->src != bb_for_stmt (stmt))
679                 add_livein_if_notdef (live, saw_def, var, e->src);
680             }
681         }
682
683       /* Don't mark PHI results as defined until all the PHI nodes have
684          been processed. If the PHI sequence is:
685             a_3 = PHI <a_1, a_2>
686             b_3 = PHI <b_1, a_3>
687          The a_3 referred to in b_3's PHI node is the one incoming on the
688          edge, *not* the PHI node just seen.  */
689
690       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
691         {
692           var = PHI_RESULT (phi);
693           set_if_valid (map, saw_def, var);
694         }
695
696       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
697         {
698           stmt = bsi_stmt (bsi);
699
700           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
701             {
702               add_livein_if_notdef (live, saw_def, op, bb);
703             }
704
705           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
706             {
707               set_if_valid (map, saw_def, op);
708             }
709         }
710     }
711
712   stack = XNEWVEC (int, last_basic_block);
713   EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
714     {
715       live_worklist (live, stack, i);
716     }
717   free (stack);
718
719 #ifdef ENABLE_CHECKING
720    /* Check for live on entry partitions and report those with a DEF in
721       the program. This will typically mean an optimization has done
722       something wrong.  */
723
724   bb = ENTRY_BLOCK_PTR;
725   num = 0;
726   FOR_EACH_EDGE (e, ei, bb->succs)
727     {
728       int entry_block = e->dest->index;
729       if (e->dest == EXIT_BLOCK_PTR)
730         continue;
731       for (i = 0; i < (unsigned)num_var_partitions (map); i++)
732         {
733           basic_block tmp;
734           tree d;
735           var = partition_to_var (map, i);
736           stmt = SSA_NAME_DEF_STMT (var);
737           tmp = bb_for_stmt (stmt);
738           d = default_def (SSA_NAME_VAR (var));
739
740           if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
741             {
742               if (!IS_EMPTY_STMT (stmt))
743                 {
744                   num++;
745                   print_generic_expr (stderr, var, TDF_SLIM);
746                   fprintf (stderr, " is defined ");
747                   if (tmp)
748                     fprintf (stderr, " in BB%d, ", tmp->index);
749                   fprintf (stderr, "by:\n");
750                   print_generic_expr (stderr, stmt, TDF_SLIM);
751                   fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", 
752                            entry_block);
753                   fprintf (stderr, " So it appears to have multiple defs.\n");
754                 }
755               else
756                 {
757                   if (d != var)
758                     {
759                       num++;
760                       print_generic_expr (stderr, var, TDF_SLIM);
761                       fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
762                       if (d)
763                         {
764                           fprintf (stderr, " but is not the default def of ");
765                           print_generic_expr (stderr, d, TDF_SLIM);
766                           fprintf (stderr, "\n");
767                         }
768                       else
769                         fprintf (stderr, " and there is no default def.\n");
770                     }
771                 }
772             }
773           else
774             if (d == var)
775               {
776                 /* The only way this var shouldn't be marked live on entry is 
777                    if it occurs in a PHI argument of the block.  */
778                 int z, ok = 0;
779                 for (phi = phi_nodes (e->dest); 
780                      phi && !ok; 
781                      phi = PHI_CHAIN (phi))
782                   {
783                     for (z = 0; z < PHI_NUM_ARGS (phi); z++)
784                       if (var == PHI_ARG_DEF (phi, z))
785                         {
786                           ok = 1;
787                           break;
788                         }
789                   }
790                 if (ok)
791                   continue;
792                 num++;
793                 print_generic_expr (stderr, var, TDF_SLIM);
794                 fprintf (stderr, " is not marked live-on-entry to entry BB%d ", 
795                          entry_block);
796                 fprintf (stderr, "but it is a default def so it should be.\n");
797               }
798         }
799     }
800   gcc_assert (num <= 0);
801 #endif
802
803   BITMAP_FREE (saw_def);
804
805   return live;
806 }
807
808
809 /* Calculate the live on exit vectors based on the entry info in LIVEINFO.  */
810
811 void
812 calculate_live_on_exit (tree_live_info_p liveinfo)
813 {
814   unsigned b;
815   unsigned i, x;
816   bitmap *on_exit;
817   basic_block bb;
818   edge e;
819   tree t, phi;
820   bitmap on_entry;
821   var_map map = liveinfo->map;
822
823   on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
824   for (x = 0; x < (unsigned)last_basic_block; x++)
825     on_exit[x] = BITMAP_ALLOC (NULL);
826
827   /* Set all the live-on-exit bits for uses in PHIs.  */
828   FOR_EACH_BB (bb)
829     {
830       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
831         for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
832           { 
833             t = PHI_ARG_DEF (phi, i);
834             e = PHI_ARG_EDGE (phi, i);
835             if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
836               continue;
837             set_if_valid (map, on_exit[e->src->index], t);
838           }
839     }
840
841   /* Set live on exit for all predecessors of live on entry's.  */
842   for (i = 0; i < num_var_partitions (map); i++)
843     {
844       bitmap_iterator bi;
845
846       on_entry = live_entry_blocks (liveinfo, i);
847       EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
848         {
849           edge_iterator ei;
850           FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
851             if (e->src != ENTRY_BLOCK_PTR)
852               bitmap_set_bit (on_exit[e->src->index], i);
853         }
854     }
855
856   liveinfo->liveout = on_exit;
857 }
858
859
860 /* Initialize a tree_partition_associator object using MAP.  */
861
862 static tpa_p
863 tpa_init (var_map map)
864 {
865   tpa_p tpa;
866   int num_partitions = num_var_partitions (map);
867   int x;
868
869   if (num_partitions == 0)
870     return NULL;
871
872   tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
873   tpa->num_trees = 0;
874   tpa->uncompressed_num = -1;
875   tpa->map = map;
876   tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
877   memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
878
879   tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
880   memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
881
882   x = MAX (40, (num_partitions / 20));
883   tpa->trees = VEC_alloc (tree, heap, x);
884   VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
885
886   return tpa;
887
888 }
889
890
891 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA.  */
892
893 void
894 tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
895 {
896   int i;
897
898   i = tpa_first_partition (tpa, tree_index);
899   if (i == partition_index)
900     {
901       VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i];
902     }
903   else
904     {
905       for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
906         {
907           if (tpa->next_partition[i] == partition_index)
908             {
909               tpa->next_partition[i] = tpa->next_partition[partition_index];
910               break;
911             }
912         }
913     }
914 }
915
916
917 /* Free the memory used by tree_partition_associator object TPA.  */
918
919 void
920 tpa_delete (tpa_p tpa)
921 {
922   if (!tpa)
923     return;
924
925   VEC_free (tree, heap, tpa->trees);
926   free (tpa->partition_to_tree_map);
927   free (tpa->next_partition);
928   free (tpa);
929 }
930
931
932 /* This function will remove any tree entries from TPA which have only a single
933    element.  This will help keep the size of the conflict graph down.  The 
934    function returns the number of remaining tree lists.  */
935
936 int 
937 tpa_compact (tpa_p tpa)
938 {
939   int last, x, y, first, swap_i;
940   tree swap_t;
941
942   /* Find the last list which has more than 1 partition.  */
943   for (last = tpa->num_trees - 1; last > 0; last--)
944     {
945       first = tpa_first_partition (tpa, last);
946       if (tpa_next_partition (tpa, first) != NO_PARTITION)
947         break;
948     }
949
950   x = 0;
951   while (x < last)
952     {
953       first = tpa_first_partition (tpa, x);
954
955       /* If there is not more than one partition, swap with the current end
956          of the tree list.  */
957       if (tpa_next_partition (tpa, first) == NO_PARTITION)
958         {
959           swap_t = VEC_index (tree, tpa->trees, last);
960           swap_i = VARRAY_INT (tpa->first_partition, last);
961
962           /* Update the last entry. Since it is known to only have one
963              partition, there is nothing else to update.  */
964           VEC_replace (tree, tpa->trees, last,
965                        VEC_index (tree, tpa->trees, x));
966           VARRAY_INT (tpa->first_partition, last) 
967             = VARRAY_INT (tpa->first_partition, x);
968           tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
969
970           /* Since this list is known to have more than one partition, update
971              the list owner entries.  */
972           VEC_replace (tree, tpa->trees, x, swap_t);
973           VARRAY_INT (tpa->first_partition, x) = swap_i;
974           for (y = tpa_first_partition (tpa, x); 
975                y != NO_PARTITION; 
976                y = tpa_next_partition (tpa, y))
977             tpa->partition_to_tree_map[y] = x;
978
979           /* Ensure last is a list with more than one partition.  */
980           last--;
981           for (; last > x; last--)
982             {
983               first = tpa_first_partition (tpa, last);
984               if (tpa_next_partition (tpa, first) != NO_PARTITION)
985                 break;
986             }
987         }
988       x++;
989     }
990
991   first = tpa_first_partition (tpa, x);
992   if (tpa_next_partition (tpa, first) != NO_PARTITION)
993     x++;
994   tpa->uncompressed_num = tpa->num_trees;
995   tpa->num_trees = x;
996   return last;
997 }
998
999
1000 /* Initialize a root_var object with SSA partitions from MAP which are based 
1001    on each root variable.  */
1002
1003 root_var_p
1004 root_var_init (var_map map)
1005 {
1006   root_var_p rv;
1007   int num_partitions = num_var_partitions (map);
1008   int x, p;
1009   tree t;
1010   var_ann_t ann;
1011   sbitmap seen;
1012
1013   rv = tpa_init (map);
1014   if (!rv)
1015     return NULL;
1016
1017   seen = sbitmap_alloc (num_partitions);
1018   sbitmap_zero (seen);
1019
1020   /* Start at the end and work towards the front. This will provide a list
1021      that is ordered from smallest to largest.  */
1022   for (x = num_partitions - 1; x >= 0; x--)
1023     {
1024       t = partition_to_var (map, x);
1025
1026       /* The var map may not be compacted yet, so check for NULL.  */
1027       if (!t) 
1028         continue;
1029
1030       p = var_to_partition (map, t);
1031
1032       gcc_assert (p != NO_PARTITION);
1033
1034       /* Make sure we only put coalesced partitions into the list once.  */
1035       if (TEST_BIT (seen, p))
1036         continue;
1037       SET_BIT (seen, p);
1038       if (TREE_CODE (t) == SSA_NAME)
1039         t = SSA_NAME_VAR (t);
1040       ann = var_ann (t);
1041       if (ann->root_var_processed)
1042         {
1043           rv->next_partition[p] = VARRAY_INT (rv->first_partition, 
1044                                               VAR_ANN_ROOT_INDEX (ann));
1045           VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p;
1046         }
1047       else
1048         {
1049           ann->root_var_processed = 1;
1050           VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
1051           VEC_safe_push (tree, heap, rv->trees, t);
1052           VARRAY_PUSH_INT (rv->first_partition, p);
1053         }
1054       rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
1055     }
1056
1057   /* Reset the out_of_ssa_tag flag on each variable for later use.  */
1058   for (x = 0; x < rv->num_trees; x++)
1059     {
1060       t = VEC_index (tree, rv->trees, x);
1061       var_ann (t)->root_var_processed = 0;
1062     }
1063
1064   sbitmap_free (seen);
1065   return rv;
1066 }
1067
1068
1069 /* Initialize a type_var structure which associates all the partitions in MAP 
1070    of the same type to the type node's index.  Volatiles are ignored.  */
1071
1072 type_var_p
1073 type_var_init (var_map map)
1074 {
1075   type_var_p tv;
1076   int x, y, p;
1077   int num_partitions = num_var_partitions (map);
1078   tree t;
1079   sbitmap seen;
1080
1081   seen = sbitmap_alloc (num_partitions);
1082   sbitmap_zero (seen);
1083
1084   tv = tpa_init (map);
1085   if (!tv)
1086     return NULL;
1087
1088   for (x = num_partitions - 1; x >= 0; x--)
1089     {
1090       t = partition_to_var (map, x);
1091
1092       /* Disallow coalescing of these types of variables.  */
1093       if (!t
1094           || TREE_THIS_VOLATILE (t)
1095           || TREE_CODE (t) == RESULT_DECL
1096           || TREE_CODE (t) == PARM_DECL 
1097           || (DECL_P (t)
1098               && (DECL_REGISTER (t)
1099                   || !DECL_IGNORED_P (t)
1100                   || DECL_RTL_SET_P (t))))
1101         continue;
1102
1103       p = var_to_partition (map, t);
1104
1105       gcc_assert (p != NO_PARTITION);
1106
1107       /* If partitions have been coalesced, only add the representative 
1108          for the partition to the list once.  */
1109       if (TEST_BIT (seen, p))
1110         continue;
1111       SET_BIT (seen, p);
1112       t = TREE_TYPE (t);
1113
1114       /* Find the list for this type.  */
1115       for (y = 0; y < tv->num_trees; y++)
1116         if (t == VEC_index (tree, tv->trees, y))
1117           break;
1118       if (y == tv->num_trees)
1119         {
1120           tv->num_trees++;
1121           VEC_safe_push (tree, heap, tv->trees, t);
1122           VARRAY_PUSH_INT (tv->first_partition, p);
1123         }
1124       else
1125         {
1126           tv->next_partition[p] = VARRAY_INT (tv->first_partition, y);
1127           VARRAY_INT (tv->first_partition, y) = p;
1128         }
1129       tv->partition_to_tree_map[p] = y;
1130     }
1131   sbitmap_free (seen);
1132   return tv;
1133 }
1134
1135
1136 /* Create a new coalesce list object from MAP and return it.  */
1137
1138 coalesce_list_p 
1139 create_coalesce_list (var_map map)
1140 {
1141   coalesce_list_p list;
1142
1143   list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
1144
1145   list->map = map;
1146   list->add_mode = true;
1147   list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
1148                                              sizeof (struct partition_pair_d));
1149   return list;
1150 }
1151
1152
1153 /* Delete coalesce list CL.  */
1154
1155 void 
1156 delete_coalesce_list (coalesce_list_p cl)
1157 {
1158   free (cl->list);
1159   free (cl);
1160 }
1161
1162
1163 /* Find a matching coalesce pair object in CL for partitions P1 and P2.  If 
1164    one isn't found, return NULL if CREATE is false, otherwise create a new 
1165    coalesce pair object and return it.  */
1166
1167 static partition_pair_p
1168 find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
1169 {
1170   partition_pair_p node, tmp;
1171   int s;
1172     
1173   /* Normalize so that p1 is the smaller value.  */
1174   if (p2 < p1)
1175     {
1176       s = p1;
1177       p1 = p2;
1178       p2 = s;
1179     }
1180   
1181   tmp = NULL;
1182
1183   /* The list is sorted such that if we find a value greater than p2,
1184      p2 is not in the list.  */
1185   for (node = cl->list[p1]; node; node = node->next)
1186     {
1187       if (node->second_partition == p2)
1188         return node;
1189       else
1190         if (node->second_partition > p2)
1191           break;
1192      tmp = node;
1193     }
1194
1195   if (!create)
1196     return NULL;
1197
1198   node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
1199   node->first_partition = p1;
1200   node->second_partition = p2;
1201   node->cost = 0;
1202     
1203   if (tmp != NULL)
1204     {
1205       node->next = tmp->next;
1206       tmp->next = node;
1207     }
1208   else
1209     {
1210       /* This is now the first node in the list.  */
1211       node->next = cl->list[p1];
1212       cl->list[p1] = node;
1213     }
1214
1215   return node;
1216 }
1217
1218 /* Return cost of execution of copy instruction with FREQUENCY
1219    possibly on CRITICAL edge and in HOT basic block.  */
1220 int
1221 coalesce_cost (int frequency, bool hot, bool critical)
1222 {
1223   /* Base costs on BB frequencies bounded by 1.  */
1224   int cost = frequency;
1225
1226   if (!cost)
1227     cost = 1;
1228   if (optimize_size || hot)
1229     cost = 1;
1230   /* Inserting copy on critical edge costs more
1231      than inserting it elsewhere.  */
1232   if (critical)
1233     cost *= 2;
1234   return cost;
1235 }
1236
1237 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE.  */
1238
1239 void 
1240 add_coalesce (coalesce_list_p cl, int p1, int p2,
1241               int value)
1242 {
1243   partition_pair_p node;
1244
1245   gcc_assert (cl->add_mode);
1246
1247   if (p1 == p2)
1248     return;
1249
1250   node = find_partition_pair (cl, p1, p2, true);
1251
1252   node->cost += value;
1253 }
1254
1255
1256 /* Comparison function to allow qsort to sort P1 and P2 in descending order.  */
1257
1258 static
1259 int compare_pairs (const void *p1, const void *p2)
1260 {
1261   return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
1262 }
1263
1264
1265 /* Prepare CL for removal of preferred pairs.  When finished, list element 
1266    0 has all the coalesce pairs, sorted in order from most important coalesce 
1267    to least important.  */
1268
1269 void
1270 sort_coalesce_list (coalesce_list_p cl)
1271 {
1272   unsigned x, num, count;
1273   partition_pair_p chain, p;
1274   partition_pair_p  *list;
1275
1276   gcc_assert (cl->add_mode);
1277
1278   cl->add_mode = false;
1279
1280   /* Compact the array of lists to a single list, and count the elements.  */
1281   num = 0;
1282   chain = NULL;
1283   for (x = 0; x < num_var_partitions (cl->map); x++)
1284     if (cl->list[x] != NULL)
1285       {
1286         for (p = cl->list[x]; p->next != NULL; p = p->next)
1287           num++;
1288         num++;
1289         p->next = chain;
1290         chain = cl->list[x];
1291         cl->list[x] = NULL;
1292       }
1293
1294   /* Only call qsort if there are more than 2 items.  */
1295   if (num > 2)
1296     {
1297       list = XNEWVEC (partition_pair_p, num);
1298       count = 0;
1299       for (p = chain; p != NULL; p = p->next)
1300         list[count++] = p;
1301
1302       gcc_assert (count == num);
1303         
1304       qsort (list, count, sizeof (partition_pair_p), compare_pairs);
1305
1306       p = list[0];
1307       for (x = 1; x < num; x++)
1308         {
1309           p->next = list[x];
1310           p = list[x];
1311         }
1312       p->next = NULL;
1313       cl->list[0] = list[0];
1314       free (list);
1315     }
1316   else
1317     {
1318       cl->list[0] = chain;
1319       if (num == 2)
1320         {
1321           /* Simply swap the two elements if they are in the wrong order.  */
1322           if (chain->cost < chain->next->cost)
1323             {
1324               cl->list[0] = chain->next;
1325               cl->list[0]->next = chain;
1326               chain->next = NULL;
1327             }
1328         }
1329     }
1330 }
1331
1332
1333 /* Retrieve the best remaining pair to coalesce from CL.  Returns the 2 
1334    partitions via P1 and P2.  Their calculated cost is returned by the function.
1335    NO_BEST_COALESCE is returned if the coalesce list is empty.  */
1336
1337 static int
1338 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
1339 {
1340   partition_pair_p node;
1341   int ret;
1342
1343   gcc_assert (!cl->add_mode);
1344
1345   node = cl->list[0];
1346   if (!node)
1347     return NO_BEST_COALESCE;
1348
1349   cl->list[0] = node->next;
1350
1351   *p1 = node->first_partition;
1352   *p2 = node->second_partition;
1353   ret = node->cost;
1354   free (node);
1355
1356   return ret;
1357 }
1358
1359
1360 /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between 
1361    VAR and any other live partitions in VEC which are associated via TPA.  
1362    Reset the live bit in VEC.  */
1363
1364 static inline void 
1365 add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
1366                         var_map map, bitmap vec, tree var)
1367
1368   int p, y, first;
1369   p = var_to_partition (map, var);
1370   if (p != NO_PARTITION)
1371     { 
1372       bitmap_clear_bit (vec, p);
1373       first = tpa_find_tree (tpa, p);
1374       /* If find returns nothing, this object isn't interesting.  */
1375       if (first == TPA_NONE)
1376         return;
1377       /* Only add interferences between objects in the same list.  */
1378       for (y = tpa_first_partition (tpa, first);
1379            y != TPA_NONE;
1380            y = tpa_next_partition (tpa, y))
1381         {
1382           if (bitmap_bit_p (vec, y))
1383             conflict_graph_add (graph, p, y);
1384         }
1385     }
1386 }
1387
1388 DEF_VEC_I(int);
1389 DEF_VEC_ALLOC_I(int,heap);
1390
1391 /* Return a conflict graph for the information contained in LIVE_INFO.  Only
1392    conflicts between items in the same TPA list are added.  If optional 
1393    coalesce list CL is passed in, any copies encountered are added.  */
1394
1395 conflict_graph
1396 build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, 
1397                            coalesce_list_p cl)
1398 {
1399   conflict_graph graph;
1400   var_map map;
1401   bitmap live;
1402   unsigned x, y, i;
1403   basic_block bb;
1404   int *partition_link, *tpa_nodes;
1405   VEC(int,heap) *tpa_to_clear;
1406   unsigned l;
1407   ssa_op_iter iter;
1408   bitmap_iterator bi;
1409
1410   map = live_var_map (liveinfo);
1411   graph = conflict_graph_new (num_var_partitions (map));
1412
1413   if (tpa_num_trees (tpa) == 0)
1414     return graph;
1415
1416   live = BITMAP_ALLOC (NULL);
1417
1418   partition_link = XCNEWVEC (int, num_var_partitions (map) + 1);
1419   tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa));
1420   tpa_to_clear = VEC_alloc (int, heap, 50);
1421
1422   FOR_EACH_BB (bb)
1423     {
1424       block_stmt_iterator bsi;
1425       tree phi;
1426       int idx;
1427
1428       /* Start with live on exit temporaries.  */
1429       bitmap_copy (live, live_on_exit (liveinfo, bb));
1430
1431       for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1432         {
1433           bool is_a_copy = false;
1434           tree stmt = bsi_stmt (bsi);
1435
1436           /* A copy between 2 partitions does not introduce an interference 
1437              by itself.  If they did, you would never be able to coalesce 
1438              two things which are copied.  If the two variables really do 
1439              conflict, they will conflict elsewhere in the program.  
1440              
1441              This is handled specially here since we may also be interested 
1442              in copies between real variables and SSA_NAME variables.  We may
1443              be interested in trying to coalesce SSA_NAME variables with
1444              root variables in some cases.  */
1445
1446           if (TREE_CODE (stmt) == MODIFY_EXPR)
1447             {
1448               tree lhs = TREE_OPERAND (stmt, 0);
1449               tree rhs = TREE_OPERAND (stmt, 1);
1450               int p1, p2;
1451               int bit;
1452
1453               if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
1454                 p1 = var_to_partition (map, lhs);
1455               else 
1456                 p1 = NO_PARTITION;
1457
1458               if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
1459                 p2 = var_to_partition (map, rhs);
1460               else 
1461                 p2 = NO_PARTITION;
1462
1463               if (p1 != NO_PARTITION && p2 != NO_PARTITION)
1464                 {
1465                   is_a_copy = true;
1466                   bit = bitmap_bit_p (live, p2);
1467                   /* If the RHS is live, make it not live while we add
1468                      the conflicts, then make it live again.  */
1469                   if (bit)
1470                     bitmap_clear_bit (live, p2);
1471                   add_conflicts_if_valid (tpa, graph, map, live, lhs);
1472                   if (bit)
1473                     bitmap_set_bit (live, p2);
1474                   if (cl)
1475                     add_coalesce (cl, p1, p2,
1476                                   coalesce_cost (bb->frequency,
1477                                                  maybe_hot_bb_p (bb), false));
1478                   set_if_valid (map, live, rhs);
1479                 }
1480             }
1481
1482           if (!is_a_copy)
1483             {
1484               tree var;
1485               FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
1486                 {
1487                   add_conflicts_if_valid (tpa, graph, map, live, var);
1488                 }
1489
1490               FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1491                 {
1492                   set_if_valid (map, live, var);
1493                 }
1494             }
1495         }
1496
1497       /* If result of a PHI is unused, then the loops over the statements
1498          will not record any conflicts.  However, since the PHI node is 
1499          going to be translated out of SSA form we must record a conflict
1500          between the result of the PHI and any variables with are live. 
1501          Otherwise the out-of-ssa translation may create incorrect code.  */
1502       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1503         {
1504           tree result = PHI_RESULT (phi);
1505           int p = var_to_partition (map, result);
1506
1507           if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
1508             add_conflicts_if_valid (tpa, graph, map, live, result);
1509         }
1510
1511       /* Anything which is still live at this point interferes.  
1512          In order to implement this efficiently, only conflicts between
1513          partitions which have the same TPA root need be added.
1514          TPA roots which have been seen are tracked in 'tpa_nodes'.  A nonzero
1515          entry points to an index into 'partition_link', which then indexes 
1516          into itself forming a linked list of partitions sharing a tpa root 
1517          which have been seen as live up to this point.  Since partitions start
1518          at index zero, all entries in partition_link are (partition + 1).
1519
1520          Conflicts are added between the current partition and any already seen.
1521          tpa_clear contains all the tpa_roots processed, and these are the only
1522          entries which need to be zero'd out for a clean restart.  */
1523
1524       EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
1525         {
1526           i = tpa_find_tree (tpa, x);
1527           if (i != (unsigned)TPA_NONE)
1528             {
1529               int start = tpa_nodes[i];
1530               /* If start is 0, a new root reference list is being started.
1531                  Register it to be cleared.  */
1532               if (!start)
1533                 VEC_safe_push (int, heap, tpa_to_clear, i);
1534
1535               /* Add interferences to other tpa members seen.  */
1536               for (y = start; y != 0; y = partition_link[y])
1537                 conflict_graph_add (graph, x, y - 1);
1538               tpa_nodes[i] = x + 1;
1539               partition_link[x + 1] = start;
1540             }
1541         }
1542
1543         /* Now clear the used tpa root references.  */
1544         for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++)
1545           tpa_nodes[idx] = 0;
1546         VEC_truncate (int, tpa_to_clear, 0);
1547     }
1548
1549   free (tpa_nodes);
1550   free (partition_link);
1551   VEC_free (int, heap, tpa_to_clear);
1552   BITMAP_FREE (live);
1553   return graph;
1554 }
1555
1556
1557 /* This routine will attempt to coalesce the elements in TPA subject to the
1558    conflicts found in GRAPH.  If optional coalesce_list CL is provided, 
1559    only coalesces specified within the coalesce list are attempted.  Otherwise 
1560    an attempt is made to coalesce as many partitions within each TPA grouping 
1561    as possible.  If DEBUG is provided, debug output will be sent there.  */
1562
1563 void
1564 coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, 
1565                       coalesce_list_p cl, FILE *debug)
1566 {
1567   int x, y, z, w;
1568   tree var, tmp;
1569
1570   /* Attempt to coalesce any items in a coalesce list.  */
1571   if (cl)
1572     {
1573       while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
1574         {
1575           if (debug)
1576             {
1577               fprintf (debug, "Coalesce list: (%d)", x);
1578               print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
1579               fprintf (debug, " & (%d)", y);
1580               print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
1581             }
1582
1583           w = tpa_find_tree (tpa, x);
1584           z = tpa_find_tree (tpa, y);
1585           if (w != z || w == TPA_NONE || z == TPA_NONE)
1586             {
1587               if (debug)
1588                 {
1589                   if (w != z)
1590                     fprintf (debug, ": Fail, Non-matching TPA's\n");
1591                   if (w == TPA_NONE)
1592                     fprintf (debug, ": Fail %d non TPA.\n", x);
1593                   else
1594                     fprintf (debug, ": Fail %d non TPA.\n", y);
1595                 }
1596               continue;
1597             }
1598           var = partition_to_var (map, x);
1599           tmp = partition_to_var (map, y);
1600           x = var_to_partition (map, var);
1601           y = var_to_partition (map, tmp);
1602           if (debug)
1603             fprintf (debug, " [map: %d, %d] ", x, y);
1604           if (x == y)
1605             {
1606               if (debug)
1607                 fprintf (debug, ": Already Coalesced.\n");
1608               continue;
1609             }
1610           if (!conflict_graph_conflict_p (graph, x, y))
1611             {
1612               z = var_union (map, var, tmp);
1613               if (z == NO_PARTITION)
1614                 {
1615                   if (debug)
1616                     fprintf (debug, ": Unable to perform partition union.\n");
1617                   continue;
1618                 }
1619
1620               /* z is the new combined partition. We need to remove the other
1621                  partition from the list. Set x to be that other partition.  */
1622               if (z == x)
1623                 {
1624                   conflict_graph_merge_regs (graph, x, y);
1625                   w = tpa_find_tree (tpa, y);
1626                   tpa_remove_partition (tpa, w, y);
1627                 }
1628               else
1629                 {
1630                   conflict_graph_merge_regs (graph, y, x);
1631                   w = tpa_find_tree (tpa, x);
1632                   tpa_remove_partition (tpa, w, x);
1633                 }
1634
1635               if (debug)
1636                 fprintf (debug, ": Success -> %d\n", z);
1637             }
1638           else
1639             if (debug)
1640               fprintf (debug, ": Fail due to conflict\n");
1641         }
1642       /* If using a coalesce list, don't try to coalesce anything else.  */
1643       return;
1644     }
1645
1646   for (x = 0; x < tpa_num_trees (tpa); x++)
1647     {
1648       while (tpa_first_partition (tpa, x) != TPA_NONE)
1649         {
1650           int p1, p2;
1651           /* Coalesce first partition with anything that doesn't conflict.  */
1652           y = tpa_first_partition (tpa, x);
1653           tpa_remove_partition (tpa, x, y);
1654
1655           var = partition_to_var (map, y);
1656           /* p1 is the partition representative to which y belongs.  */
1657           p1 = var_to_partition (map, var);
1658           
1659           for (z = tpa_next_partition (tpa, y); 
1660                z != TPA_NONE; 
1661                z = tpa_next_partition (tpa, z))
1662             {
1663               tmp = partition_to_var (map, z);
1664               /* p2 is the partition representative to which z belongs.  */
1665               p2 = var_to_partition (map, tmp);
1666               if (debug)
1667                 {
1668                   fprintf (debug, "Coalesce : ");
1669                   print_generic_expr (debug, var, TDF_SLIM);
1670                   fprintf (debug, " &");
1671                   print_generic_expr (debug, tmp, TDF_SLIM);
1672                   fprintf (debug, "  (%d ,%d)", p1, p2);
1673                 }
1674
1675               /* If partitions are already merged, don't check for conflict.  */
1676               if (tmp == var)
1677                 {
1678                   tpa_remove_partition (tpa, x, z);
1679                   if (debug)
1680                     fprintf (debug, ": Already coalesced\n");
1681                 }
1682               else
1683                 if (!conflict_graph_conflict_p (graph, p1, p2))
1684                   {
1685                     int v;
1686                     if (tpa_find_tree (tpa, y) == TPA_NONE 
1687                         || tpa_find_tree (tpa, z) == TPA_NONE)
1688                       {
1689                         if (debug)
1690                           fprintf (debug, ": Fail non-TPA member\n");
1691                         continue;
1692                       }
1693                     if ((v = var_union (map, var, tmp)) == NO_PARTITION)
1694                       {
1695                         if (debug)
1696                           fprintf (debug, ": Fail cannot combine partitions\n");
1697                         continue;
1698                       }
1699
1700                     tpa_remove_partition (tpa, x, z);
1701                     if (v == p1)
1702                       conflict_graph_merge_regs (graph, v, z);
1703                     else
1704                       {
1705                         /* Update the first partition's representative.  */
1706                         conflict_graph_merge_regs (graph, v, y);
1707                         p1 = v;
1708                       }
1709
1710                     /* The root variable of the partition may be changed
1711                        now.  */
1712                     var = partition_to_var (map, p1);
1713
1714                     if (debug)
1715                       fprintf (debug, ": Success -> %d\n", v);
1716                   }
1717                 else
1718                   if (debug)
1719                     fprintf (debug, ": Fail, Conflict\n");
1720             }
1721         }
1722     }
1723 }
1724
1725
1726 /* Send debug info for coalesce list CL to file F.  */
1727
1728 void 
1729 dump_coalesce_list (FILE *f, coalesce_list_p cl)
1730 {
1731   partition_pair_p node;
1732   int x, num;
1733   tree var;
1734
1735   if (cl->add_mode)
1736     {
1737       fprintf (f, "Coalesce List:\n");
1738       num = num_var_partitions (cl->map);
1739       for (x = 0; x < num; x++)
1740         {
1741           node = cl->list[x];
1742           if (node)
1743             {
1744               fprintf (f, "[");
1745               print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
1746               fprintf (f, "] - ");
1747               for ( ; node; node = node->next)
1748                 {
1749                   var = partition_to_var (cl->map, node->second_partition);
1750                   print_generic_expr (f, var, TDF_SLIM);
1751                   fprintf (f, "(%1d), ", node->cost);
1752                 }
1753               fprintf (f, "\n");
1754             }
1755         }
1756     }
1757   else
1758     {
1759       fprintf (f, "Sorted Coalesce list:\n");
1760       for (node = cl->list[0]; node; node = node->next)
1761         {
1762           fprintf (f, "(%d) ", node->cost);
1763           var = partition_to_var (cl->map, node->first_partition);
1764           print_generic_expr (f, var, TDF_SLIM);
1765           fprintf (f, " : ");
1766           var = partition_to_var (cl->map, node->second_partition);
1767           print_generic_expr (f, var, TDF_SLIM);
1768           fprintf (f, "\n");
1769         }
1770     }
1771 }
1772
1773
1774 /* Output tree_partition_associator object TPA to file F..  */
1775
1776 void
1777 tpa_dump (FILE *f, tpa_p tpa)
1778 {
1779   int x, i;
1780
1781   if (!tpa)
1782     return;
1783
1784   for (x = 0; x < tpa_num_trees (tpa); x++)
1785     {
1786       print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
1787       fprintf (f, " : (");
1788       for (i = tpa_first_partition (tpa, x); 
1789            i != TPA_NONE;
1790            i = tpa_next_partition (tpa, i))
1791         {
1792           fprintf (f, "(%d)",i);
1793           print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
1794           fprintf (f, " ");
1795
1796 #ifdef ENABLE_CHECKING
1797           if (tpa_find_tree (tpa, i) != x)
1798             fprintf (f, "**find tree incorrectly set** ");
1799 #endif
1800
1801         }
1802       fprintf (f, ")\n");
1803     }
1804   fflush (f);
1805 }
1806
1807
1808 /* Output partition map MAP to file F.  */
1809
1810 void
1811 dump_var_map (FILE *f, var_map map)
1812 {
1813   int t;
1814   unsigned x, y;
1815   int p;
1816
1817   fprintf (f, "\nPartition map \n\n");
1818
1819   for (x = 0; x < map->num_partitions; x++)
1820     {
1821       if (map->compact_to_partition != NULL)
1822         p = map->compact_to_partition[x];
1823       else
1824         p = x;
1825
1826       if (map->partition_to_var[p] == NULL_TREE)
1827         continue;
1828
1829       t = 0;
1830       for (y = 1; y < num_ssa_names; y++)
1831         {
1832           p = partition_find (map->var_partition, y);
1833           if (map->partition_to_compact)
1834             p = map->partition_to_compact[p];
1835           if (p == (int)x)
1836             {
1837               if (t++ == 0)
1838                 {
1839                   fprintf(f, "Partition %d (", x);
1840                   print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1841                   fprintf (f, " - ");
1842                 }
1843               fprintf (f, "%d ", y);
1844             }
1845         }
1846       if (t != 0)
1847         fprintf (f, ")\n");
1848     }
1849   fprintf (f, "\n");
1850 }
1851
1852
1853 /* Output live range info LIVE to file F, controlled by FLAG.  */
1854
1855 void
1856 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1857 {
1858   basic_block bb;
1859   unsigned i;
1860   var_map map = live->map;
1861   bitmap_iterator bi;
1862
1863   if ((flag & LIVEDUMP_ENTRY) && live->livein)
1864     {
1865       FOR_EACH_BB (bb)
1866         {
1867           fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1868           for (i = 0; i < num_var_partitions (map); i++)
1869             {
1870               if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
1871                 {
1872                   print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1873                   fprintf (f, "  ");
1874                 }
1875             }
1876           fprintf (f, "\n");
1877         }
1878     }
1879
1880   if ((flag & LIVEDUMP_EXIT) && live->liveout)
1881     {
1882       FOR_EACH_BB (bb)
1883         {
1884           fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1885           EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1886             {
1887               print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1888               fprintf (f, "  ");
1889             }
1890           fprintf (f, "\n");
1891         }
1892     }
1893 }
1894
1895 #ifdef ENABLE_CHECKING
1896 void
1897 register_ssa_partition_check (tree ssa_var)
1898 {
1899   gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1900   if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1901     {
1902       fprintf (stderr, "Illegally registering a virtual SSA name :");
1903       print_generic_expr (stderr, ssa_var, TDF_SLIM);
1904       fprintf (stderr, " in the SSA->Normal phase.\n");
1905       internal_error ("SSA corruption");
1906     }
1907 }
1908 #endif