OSDN Git Service

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