OSDN Git Service

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