2005-05-19 Paul Brook <paul@codesourcery.com>
[official-gcc.git] / gcc / tree-ssa-live.c
blobf40df907d6adb5afc258d5c97e4911edf764daae
1 /* Liveness for SSA trees.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
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.
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.
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. */
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 "errors.h"
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);
52 /* This is where the mapping from SSA version number to real storage variable
53 is tracked.
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.
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. */
64 /* Create a variable partition map of SIZE, initialize and return it. */
66 var_map
67 init_var_map (int size)
69 var_map map;
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));
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;
86 /* Free memory associated with MAP. */
88 void
89 delete_var_map (var_map map)
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);
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. */
108 var_union (var_map map, tree var1, tree var2)
110 int p1, p2, p3;
111 tree root_var = NULL_TREE;
112 tree other_var = NULL_TREE;
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. */
118 if (TREE_CODE (var1) == SSA_NAME)
119 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
120 else
122 p1 = var_to_partition (map, var1);
123 if (map->compact_to_partition)
124 p1 = map->compact_to_partition[p1];
125 root_var = var1;
128 if (TREE_CODE (var2) == SSA_NAME)
129 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
130 else
132 p2 = var_to_partition (map, var2);
133 if (map->compact_to_partition)
134 p2 = map->compact_to_partition[p2];
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)))
140 other_var = root_var;
141 root_var = var2;
143 else
144 other_var = var2;
147 gcc_assert (p1 != NO_PARTITION);
148 gcc_assert (p2 != NO_PARTITION);
150 if (p1 == p2)
151 p3 = p1;
152 else
153 p3 = partition_union (map->var_partition, p1, p2);
155 if (map->partition_to_compact)
156 p3 = map->partition_to_compact[p3];
158 if (root_var)
159 change_partition_var (map, root_var, p3);
160 if (other_var)
161 change_partition_var (map, other_var, p3);
163 return p3;
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.
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.
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. */
184 void
185 compact_var_map (var_map map, int flags)
187 sbitmap used;
188 int x, limit, count, tmp, root, root_i;
189 tree var;
190 root_var_p rv = NULL;
192 limit = map->partition_size;
193 used = sbitmap_alloc (limit);
194 sbitmap_zero (used);
196 /* Already compressed? Abandon the old one. */
197 if (map->partition_to_compact)
199 free (map->partition_to_compact);
200 map->partition_to_compact = NULL;
202 if (map->compact_to_partition)
204 free (map->compact_to_partition);
205 map->compact_to_partition = NULL;
208 map->num_partitions = map->partition_size;
210 if (flags & VARMAP_NO_SINGLE_DEFS)
211 rv = root_var_init (map);
213 map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
214 memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
216 /* Find out which partitions are actually referenced. */
217 count = 0;
218 for (x = 0; x < limit; x++)
220 tmp = partition_find (map->var_partition, x);
221 if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
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)
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;
233 SET_BIT (used, tmp);
234 count++;
238 /* Build a compacted partitioning. */
239 if (count != limit)
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,
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++;
254 else
256 free (map->partition_to_compact);
257 map->partition_to_compact = NULL;
260 map->num_partitions = count;
262 if (rv)
263 root_var_delete (rv);
264 sbitmap_free (used);
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. */
272 void
273 change_partition_var (var_map map, tree var, int part)
275 var_ann_t ann;
277 gcc_assert (TREE_CODE (var) != SSA_NAME);
279 ann = var_ann (var);
280 ann->out_of_ssa_tag = 1;
281 VAR_ANN_PARTITION (ann) = part;
282 if (map->compact_to_partition)
283 map->partition_to_var[map->compact_to_partition[part]] = var;
287 /* Helper function for mark_all_vars_used, called via walk_tree. */
289 static tree
290 mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
291 void *data ATTRIBUTE_UNUSED)
293 tree t = *tp;
295 /* Only need to mark VAR_DECLS; parameters and return results are not
296 eliminated as unused. */
297 if (TREE_CODE (t) == VAR_DECL)
298 set_is_used (t);
300 if (IS_TYPE_OR_DECL_P (t))
301 *walk_subtrees = 0;
303 return NULL;
306 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
307 eliminated during the tree->rtl conversion process. */
309 static inline void
310 mark_all_vars_used (tree *expr_p)
312 walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
315 /* This function looks through the program and uses FLAGS to determine what
316 SSA versioned variables are given entries in a new partition table. This
317 new partition map is returned. */
319 var_map
320 create_ssa_var_map (int flags)
322 block_stmt_iterator bsi;
323 basic_block bb;
324 tree dest, use;
325 tree stmt;
326 var_map map;
327 ssa_op_iter iter;
328 #ifdef ENABLE_CHECKING
329 sbitmap used_in_real_ops;
330 sbitmap used_in_virtual_ops;
331 #endif
333 map = init_var_map (num_ssa_names + 1);
335 #ifdef ENABLE_CHECKING
336 used_in_real_ops = sbitmap_alloc (num_referenced_vars);
337 sbitmap_zero (used_in_real_ops);
339 used_in_virtual_ops = sbitmap_alloc (num_referenced_vars);
340 sbitmap_zero (used_in_virtual_ops);
341 #endif
343 if (flags & SSA_VAR_MAP_REF_COUNT)
345 map->ref_count
346 = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
347 memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
350 FOR_EACH_BB (bb)
352 tree phi, arg;
353 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
355 int i;
356 register_ssa_partition (map, PHI_RESULT (phi), false);
357 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
359 arg = PHI_ARG_DEF (phi, i);
360 if (TREE_CODE (arg) == SSA_NAME)
361 register_ssa_partition (map, arg, true);
363 mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
367 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
369 stmt = bsi_stmt (bsi);
371 /* Register USE and DEF operands in each statement. */
372 FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
374 register_ssa_partition (map, use, true);
376 #ifdef ENABLE_CHECKING
377 SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (use))->uid);
378 #endif
381 FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF)
383 register_ssa_partition (map, dest, false);
385 #ifdef ENABLE_CHECKING
386 SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (dest))->uid);
387 #endif
390 #ifdef ENABLE_CHECKING
391 /* Validate that virtual ops don't get used in funny ways. */
392 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter,
393 SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
395 SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (use))->uid);
398 #endif /* ENABLE_CHECKING */
400 mark_all_vars_used (bsi_stmt_ptr (bsi));
404 #if defined ENABLE_CHECKING
406 unsigned i;
407 sbitmap both = sbitmap_alloc (num_referenced_vars);
408 sbitmap_a_and_b (both, used_in_real_ops, used_in_virtual_ops);
409 if (sbitmap_first_set_bit (both) >= 0)
411 EXECUTE_IF_SET_IN_SBITMAP (both, 0, i,
412 fprintf (stderr, "Variable %s used in real and virtual operands\n",
413 get_name (referenced_var (i))));
414 internal_error ("SSA corruption");
417 sbitmap_free (used_in_real_ops);
418 sbitmap_free (used_in_virtual_ops);
419 sbitmap_free (both);
421 #endif
423 return map;
427 /* Allocate and return a new live range information object base on MAP. */
429 static tree_live_info_p
430 new_tree_live_info (var_map map)
432 tree_live_info_p live;
433 unsigned x;
435 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
436 live->map = map;
437 live->num_blocks = last_basic_block;
439 live->global = BITMAP_ALLOC (NULL);
441 live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
442 for (x = 0; x < num_var_partitions (map); x++)
443 live->livein[x] = BITMAP_ALLOC (NULL);
445 /* liveout is deferred until it is actually requested. */
446 live->liveout = NULL;
447 return live;
451 /* Free storage for live range info object LIVE. */
453 void
454 delete_tree_live_info (tree_live_info_p live)
456 int x;
457 if (live->liveout)
459 for (x = live->num_blocks - 1; x >= 0; x--)
460 BITMAP_FREE (live->liveout[x]);
461 free (live->liveout);
463 if (live->livein)
465 for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
466 BITMAP_FREE (live->livein[x]);
467 free (live->livein);
469 if (live->global)
470 BITMAP_FREE (live->global);
472 free (live);
476 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
477 for partition I. STACK is a varray used for temporary memory which is
478 passed in rather than being allocated on every call. */
480 static void
481 live_worklist (tree_live_info_p live, int *stack, int i)
483 unsigned b;
484 tree var;
485 basic_block def_bb = NULL;
486 edge e;
487 var_map map = live->map;
488 edge_iterator ei;
489 bitmap_iterator bi;
490 int *tos = stack;
492 var = partition_to_var (map, i);
493 if (SSA_NAME_DEF_STMT (var))
494 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
496 EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
498 *tos++ = b;
501 while (tos != stack)
503 b = *--tos;
505 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
506 if (e->src != ENTRY_BLOCK_PTR)
508 /* Its not live on entry to the block its defined in. */
509 if (e->src == def_bb)
510 continue;
511 if (!bitmap_bit_p (live->livein[i], e->src->index))
513 bitmap_set_bit (live->livein[i], e->src->index);
514 *tos++ = e->src->index;
521 /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
523 static inline void
524 set_if_valid (var_map map, bitmap vec, tree var)
526 int p = var_to_partition (map, var);
527 if (p != NO_PARTITION)
528 bitmap_set_bit (vec, p);
532 /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
533 global bit for it in the LIVE object. BB is the block being processed. */
535 static inline void
536 add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
537 tree var, basic_block bb)
539 int p = var_to_partition (live->map, var);
540 if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
541 return;
542 if (!bitmap_bit_p (def_vec, p))
544 bitmap_set_bit (live->livein[p], bb->index);
545 bitmap_set_bit (live->global, p);
550 /* Given partition map MAP, calculate all the live on entry bitmaps for
551 each basic block. Return a live info object. */
553 tree_live_info_p
554 calculate_live_on_entry (var_map map)
556 tree_live_info_p live;
557 unsigned i;
558 basic_block bb;
559 bitmap saw_def;
560 tree phi, var, stmt;
561 tree op;
562 edge e;
563 int *stack;
564 block_stmt_iterator bsi;
565 ssa_op_iter iter;
566 bitmap_iterator bi;
567 #ifdef ENABLE_CHECKING
568 int num;
569 edge_iterator ei;
570 #endif
572 saw_def = BITMAP_ALLOC (NULL);
574 live = new_tree_live_info (map);
576 FOR_EACH_BB (bb)
578 bitmap_clear (saw_def);
580 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
582 for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
584 var = PHI_ARG_DEF (phi, i);
585 if (!phi_ssa_name_p (var))
586 continue;
587 stmt = SSA_NAME_DEF_STMT (var);
588 e = EDGE_PRED (bb, i);
590 /* Any uses in PHIs which either don't have def's or are not
591 defined in the block from which the def comes, will be live
592 on entry to that block. */
593 if (!stmt || e->src != bb_for_stmt (stmt))
594 add_livein_if_notdef (live, saw_def, var, e->src);
598 /* Don't mark PHI results as defined until all the PHI nodes have
599 been processed. If the PHI sequence is:
600 a_3 = PHI <a_1, a_2>
601 b_3 = PHI <b_1, a_3>
602 The a_3 referred to in b_3's PHI node is the one incoming on the
603 edge, *not* the PHI node just seen. */
605 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
607 var = PHI_RESULT (phi);
608 set_if_valid (map, saw_def, var);
611 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
613 stmt = bsi_stmt (bsi);
615 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
617 add_livein_if_notdef (live, saw_def, op, bb);
620 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
622 set_if_valid (map, saw_def, op);
627 stack = xmalloc (sizeof (int) * last_basic_block);
628 EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
630 live_worklist (live, stack, i);
632 free (stack);
634 #ifdef ENABLE_CHECKING
635 /* Check for live on entry partitions and report those with a DEF in
636 the program. This will typically mean an optimization has done
637 something wrong. */
639 bb = ENTRY_BLOCK_PTR;
640 num = 0;
641 FOR_EACH_EDGE (e, ei, bb->succs)
643 int entry_block = e->dest->index;
644 if (e->dest == EXIT_BLOCK_PTR)
645 continue;
646 for (i = 0; i < (unsigned)num_var_partitions (map); i++)
648 basic_block tmp;
649 tree d;
650 var = partition_to_var (map, i);
651 stmt = SSA_NAME_DEF_STMT (var);
652 tmp = bb_for_stmt (stmt);
653 d = default_def (SSA_NAME_VAR (var));
655 if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
657 if (!IS_EMPTY_STMT (stmt))
659 num++;
660 print_generic_expr (stderr, var, TDF_SLIM);
661 fprintf (stderr, " is defined ");
662 if (tmp)
663 fprintf (stderr, " in BB%d, ", tmp->index);
664 fprintf (stderr, "by:\n");
665 print_generic_expr (stderr, stmt, TDF_SLIM);
666 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
667 entry_block);
668 fprintf (stderr, " So it appears to have multiple defs.\n");
670 else
672 if (d != var)
674 num++;
675 print_generic_expr (stderr, var, TDF_SLIM);
676 fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
677 if (d)
679 fprintf (stderr, " but is not the default def of ");
680 print_generic_expr (stderr, d, TDF_SLIM);
681 fprintf (stderr, "\n");
683 else
684 fprintf (stderr, " and there is no default def.\n");
688 else
689 if (d == var)
691 /* The only way this var shouldn't be marked live on entry is
692 if it occurs in a PHI argument of the block. */
693 int z, ok = 0;
694 for (phi = phi_nodes (e->dest);
695 phi && !ok;
696 phi = PHI_CHAIN (phi))
698 for (z = 0; z < PHI_NUM_ARGS (phi); z++)
699 if (var == PHI_ARG_DEF (phi, z))
701 ok = 1;
702 break;
705 if (ok)
706 continue;
707 num++;
708 print_generic_expr (stderr, var, TDF_SLIM);
709 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
710 entry_block);
711 fprintf (stderr, "but it is a default def so it should be.\n");
715 gcc_assert (num <= 0);
716 #endif
718 BITMAP_FREE (saw_def);
720 return live;
724 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
726 void
727 calculate_live_on_exit (tree_live_info_p liveinfo)
729 unsigned b;
730 unsigned i, x;
731 bitmap *on_exit;
732 basic_block bb;
733 edge e;
734 tree t, phi;
735 bitmap on_entry;
736 var_map map = liveinfo->map;
738 on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
739 for (x = 0; x < (unsigned)last_basic_block; x++)
740 on_exit[x] = BITMAP_ALLOC (NULL);
742 /* Set all the live-on-exit bits for uses in PHIs. */
743 FOR_EACH_BB (bb)
745 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
746 for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
748 t = PHI_ARG_DEF (phi, i);
749 e = PHI_ARG_EDGE (phi, i);
750 if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
751 continue;
752 set_if_valid (map, on_exit[e->src->index], t);
756 /* Set live on exit for all predecessors of live on entry's. */
757 for (i = 0; i < num_var_partitions (map); i++)
759 bitmap_iterator bi;
761 on_entry = live_entry_blocks (liveinfo, i);
762 EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
764 edge_iterator ei;
765 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
766 if (e->src != ENTRY_BLOCK_PTR)
767 bitmap_set_bit (on_exit[e->src->index], i);
771 liveinfo->liveout = on_exit;
775 /* Initialize a tree_partition_associator object using MAP. */
777 static tpa_p
778 tpa_init (var_map map)
780 tpa_p tpa;
781 int num_partitions = num_var_partitions (map);
782 int x;
784 if (num_partitions == 0)
785 return NULL;
787 tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
788 tpa->num_trees = 0;
789 tpa->uncompressed_num = -1;
790 tpa->map = map;
791 tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
792 memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
794 tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
795 memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
797 x = MAX (40, (num_partitions / 20));
798 tpa->trees = VEC_alloc (tree, heap, x);
799 VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
801 return tpa;
806 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
808 void
809 tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
811 int i;
813 i = tpa_first_partition (tpa, tree_index);
814 if (i == partition_index)
816 VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i];
818 else
820 for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
822 if (tpa->next_partition[i] == partition_index)
824 tpa->next_partition[i] = tpa->next_partition[partition_index];
825 break;
832 /* Free the memory used by tree_partition_associator object TPA. */
834 void
835 tpa_delete (tpa_p tpa)
837 if (!tpa)
838 return;
840 VEC_free (tree, heap, tpa->trees);
841 free (tpa->partition_to_tree_map);
842 free (tpa->next_partition);
843 free (tpa);
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. */
851 int
852 tpa_compact (tpa_p tpa)
854 int last, x, y, first, swap_i;
855 tree swap_t;
857 /* Find the last list which has more than 1 partition. */
858 for (last = tpa->num_trees - 1; last > 0; last--)
860 first = tpa_first_partition (tpa, last);
861 if (tpa_next_partition (tpa, first) != NO_PARTITION)
862 break;
865 x = 0;
866 while (x < last)
868 first = tpa_first_partition (tpa, x);
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)
874 swap_t = VEC_index (tree, tpa->trees, last);
875 swap_i = VARRAY_INT (tpa->first_partition, last);
877 /* Update the last entry. Since it is known to only have one
878 partition, there is nothing else to update. */
879 VEC_replace (tree, tpa->trees, last,
880 VEC_index (tree, tpa->trees, x));
881 VARRAY_INT (tpa->first_partition, last)
882 = VARRAY_INT (tpa->first_partition, x);
883 tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
885 /* Since this list is known to have more than one partition, update
886 the list owner entries. */
887 VEC_replace (tree, tpa->trees, x, swap_t);
888 VARRAY_INT (tpa->first_partition, x) = swap_i;
889 for (y = tpa_first_partition (tpa, x);
890 y != NO_PARTITION;
891 y = tpa_next_partition (tpa, y))
892 tpa->partition_to_tree_map[y] = x;
894 /* Ensure last is a list with more than one partition. */
895 last--;
896 for (; last > x; last--)
898 first = tpa_first_partition (tpa, last);
899 if (tpa_next_partition (tpa, first) != NO_PARTITION)
900 break;
903 x++;
906 first = tpa_first_partition (tpa, x);
907 if (tpa_next_partition (tpa, first) != NO_PARTITION)
908 x++;
909 tpa->uncompressed_num = tpa->num_trees;
910 tpa->num_trees = x;
911 return last;
915 /* Initialize a root_var object with SSA partitions from MAP which are based
916 on each root variable. */
918 root_var_p
919 root_var_init (var_map map)
921 root_var_p rv;
922 int num_partitions = num_var_partitions (map);
923 int x, p;
924 tree t;
925 var_ann_t ann;
926 sbitmap seen;
928 rv = tpa_init (map);
929 if (!rv)
930 return NULL;
932 seen = sbitmap_alloc (num_partitions);
933 sbitmap_zero (seen);
935 /* Start at the end and work towards the front. This will provide a list
936 that is ordered from smallest to largest. */
937 for (x = num_partitions - 1; x >= 0; x--)
939 t = partition_to_var (map, x);
941 /* The var map may not be compacted yet, so check for NULL. */
942 if (!t)
943 continue;
945 p = var_to_partition (map, t);
947 gcc_assert (p != NO_PARTITION);
949 /* Make sure we only put coalesced partitions into the list once. */
950 if (TEST_BIT (seen, p))
951 continue;
952 SET_BIT (seen, p);
953 if (TREE_CODE (t) == SSA_NAME)
954 t = SSA_NAME_VAR (t);
955 ann = var_ann (t);
956 if (ann->root_var_processed)
958 rv->next_partition[p] = VARRAY_INT (rv->first_partition,
959 VAR_ANN_ROOT_INDEX (ann));
960 VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p;
962 else
964 ann->root_var_processed = 1;
965 VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
966 VEC_safe_push (tree, heap, rv->trees, t);
967 VARRAY_PUSH_INT (rv->first_partition, p);
969 rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
972 /* Reset the out_of_ssa_tag flag on each variable for later use. */
973 for (x = 0; x < rv->num_trees; x++)
975 t = VEC_index (tree, rv->trees, x);
976 var_ann (t)->root_var_processed = 0;
979 sbitmap_free (seen);
980 return rv;
984 /* Initialize a type_var structure which associates all the partitions in MAP
985 of the same type to the type node's index. Volatiles are ignored. */
987 type_var_p
988 type_var_init (var_map map)
990 type_var_p tv;
991 int x, y, p;
992 int num_partitions = num_var_partitions (map);
993 tree t;
994 sbitmap seen;
996 seen = sbitmap_alloc (num_partitions);
997 sbitmap_zero (seen);
999 tv = tpa_init (map);
1000 if (!tv)
1001 return NULL;
1003 for (x = num_partitions - 1; x >= 0; x--)
1005 t = partition_to_var (map, x);
1007 /* Disallow coalescing of these types of variables. */
1008 if (!t
1009 || TREE_THIS_VOLATILE (t)
1010 || TREE_CODE (t) == RESULT_DECL
1011 || TREE_CODE (t) == PARM_DECL
1012 || (DECL_P (t)
1013 && (DECL_REGISTER (t)
1014 || !DECL_IGNORED_P (t)
1015 || DECL_RTL_SET_P (t))))
1016 continue;
1018 p = var_to_partition (map, t);
1020 gcc_assert (p != NO_PARTITION);
1022 /* If partitions have been coalesced, only add the representative
1023 for the partition to the list once. */
1024 if (TEST_BIT (seen, p))
1025 continue;
1026 SET_BIT (seen, p);
1027 t = TREE_TYPE (t);
1029 /* Find the list for this type. */
1030 for (y = 0; y < tv->num_trees; y++)
1031 if (t == VEC_index (tree, tv->trees, y))
1032 break;
1033 if (y == tv->num_trees)
1035 tv->num_trees++;
1036 VEC_safe_push (tree, heap, tv->trees, t);
1037 VARRAY_PUSH_INT (tv->first_partition, p);
1039 else
1041 tv->next_partition[p] = VARRAY_INT (tv->first_partition, y);
1042 VARRAY_INT (tv->first_partition, y) = p;
1044 tv->partition_to_tree_map[p] = y;
1046 sbitmap_free (seen);
1047 return tv;
1051 /* Create a new coalesce list object from MAP and return it. */
1053 coalesce_list_p
1054 create_coalesce_list (var_map map)
1056 coalesce_list_p list;
1058 list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
1060 list->map = map;
1061 list->add_mode = true;
1062 list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
1063 sizeof (struct partition_pair_d));
1064 return list;
1068 /* Delete coalesce list CL. */
1070 void
1071 delete_coalesce_list (coalesce_list_p cl)
1073 free (cl->list);
1074 free (cl);
1078 /* Find a matching coalesce pair object in CL for partitions P1 and P2. If
1079 one isn't found, return NULL if CREATE is false, otherwise create a new
1080 coalesce pair object and return it. */
1082 static partition_pair_p
1083 find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
1085 partition_pair_p node, tmp;
1086 int s;
1088 /* Normalize so that p1 is the smaller value. */
1089 if (p2 < p1)
1091 s = p1;
1092 p1 = p2;
1093 p2 = s;
1096 tmp = NULL;
1098 /* The list is sorted such that if we find a value greater than p2,
1099 p2 is not in the list. */
1100 for (node = cl->list[p1]; node; node = node->next)
1102 if (node->second_partition == p2)
1103 return node;
1104 else
1105 if (node->second_partition > p2)
1106 break;
1107 tmp = node;
1110 if (!create)
1111 return NULL;
1113 node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
1114 node->first_partition = p1;
1115 node->second_partition = p2;
1116 node->cost = 0;
1118 if (tmp != NULL)
1120 node->next = tmp->next;
1121 tmp->next = node;
1123 else
1125 /* This is now the first node in the list. */
1126 node->next = cl->list[p1];
1127 cl->list[p1] = node;
1130 return node;
1134 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
1136 void
1137 add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
1139 partition_pair_p node;
1141 gcc_assert (cl->add_mode);
1143 if (p1 == p2)
1144 return;
1146 node = find_partition_pair (cl, p1, p2, true);
1148 node->cost += value;
1152 /* Comparison function to allow qsort to sort P1 and P2 in descending order. */
1154 static
1155 int compare_pairs (const void *p1, const void *p2)
1157 return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
1161 /* Prepare CL for removal of preferred pairs. When finished, list element
1162 0 has all the coalesce pairs, sorted in order from most important coalesce
1163 to least important. */
1165 void
1166 sort_coalesce_list (coalesce_list_p cl)
1168 unsigned x, num, count;
1169 partition_pair_p chain, p;
1170 partition_pair_p *list;
1172 gcc_assert (cl->add_mode);
1174 cl->add_mode = false;
1176 /* Compact the array of lists to a single list, and count the elements. */
1177 num = 0;
1178 chain = NULL;
1179 for (x = 0; x < num_var_partitions (cl->map); x++)
1180 if (cl->list[x] != NULL)
1182 for (p = cl->list[x]; p->next != NULL; p = p->next)
1183 num++;
1184 num++;
1185 p->next = chain;
1186 chain = cl->list[x];
1187 cl->list[x] = NULL;
1190 /* Only call qsort if there are more than 2 items. */
1191 if (num > 2)
1193 list = xmalloc (sizeof (partition_pair_p) * num);
1194 count = 0;
1195 for (p = chain; p != NULL; p = p->next)
1196 list[count++] = p;
1198 gcc_assert (count == num);
1200 qsort (list, count, sizeof (partition_pair_p), compare_pairs);
1202 p = list[0];
1203 for (x = 1; x < num; x++)
1205 p->next = list[x];
1206 p = list[x];
1208 p->next = NULL;
1209 cl->list[0] = list[0];
1210 free (list);
1212 else
1214 cl->list[0] = chain;
1215 if (num == 2)
1217 /* Simply swap the two elements if they are in the wrong order. */
1218 if (chain->cost < chain->next->cost)
1220 cl->list[0] = chain->next;
1221 cl->list[0]->next = chain;
1222 chain->next = NULL;
1229 /* Retrieve the best remaining pair to coalesce from CL. Returns the 2
1230 partitions via P1 and P2. Their calculated cost is returned by the function.
1231 NO_BEST_COALESCE is returned if the coalesce list is empty. */
1233 static int
1234 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
1236 partition_pair_p node;
1237 int ret;
1239 gcc_assert (!cl->add_mode);
1241 node = cl->list[0];
1242 if (!node)
1243 return NO_BEST_COALESCE;
1245 cl->list[0] = node->next;
1247 *p1 = node->first_partition;
1248 *p2 = node->second_partition;
1249 ret = node->cost;
1250 free (node);
1252 return ret;
1256 /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
1257 VAR and any other live partitions in VEC which are associated via TPA.
1258 Reset the live bit in VEC. */
1260 static inline void
1261 add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
1262 var_map map, bitmap vec, tree var)
1264 int p, y, first;
1265 p = var_to_partition (map, var);
1266 if (p != NO_PARTITION)
1268 bitmap_clear_bit (vec, p);
1269 first = tpa_find_tree (tpa, p);
1270 /* If find returns nothing, this object isn't interesting. */
1271 if (first == TPA_NONE)
1272 return;
1273 /* Only add interferences between objects in the same list. */
1274 for (y = tpa_first_partition (tpa, first);
1275 y != TPA_NONE;
1276 y = tpa_next_partition (tpa, y))
1278 if (bitmap_bit_p (vec, y))
1279 conflict_graph_add (graph, p, y);
1284 DEF_VEC_P(int);
1285 DEF_VEC_ALLOC_P(int,heap);
1287 /* Return a conflict graph for the information contained in LIVE_INFO. Only
1288 conflicts between items in the same TPA list are added. If optional
1289 coalesce list CL is passed in, any copies encountered are added. */
1291 conflict_graph
1292 build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
1293 coalesce_list_p cl)
1295 conflict_graph graph;
1296 var_map map;
1297 bitmap live;
1298 unsigned x, y, i;
1299 basic_block bb;
1300 int *partition_link, *tpa_nodes;
1301 VEC(int,heap) *tpa_to_clear;
1302 unsigned l;
1303 ssa_op_iter iter;
1304 bitmap_iterator bi;
1306 map = live_var_map (liveinfo);
1307 graph = conflict_graph_new (num_var_partitions (map));
1309 if (tpa_num_trees (tpa) == 0)
1310 return graph;
1312 live = BITMAP_ALLOC (NULL);
1314 partition_link = xcalloc (num_var_partitions (map) + 1, sizeof (int));
1315 tpa_nodes = xcalloc (tpa_num_trees (tpa), sizeof (int));
1316 tpa_to_clear = VEC_alloc (int, heap, 50);
1318 FOR_EACH_BB (bb)
1320 block_stmt_iterator bsi;
1321 tree phi;
1322 int idx;
1324 /* Start with live on exit temporaries. */
1325 bitmap_copy (live, live_on_exit (liveinfo, bb));
1327 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1329 bool is_a_copy = false;
1330 tree stmt = bsi_stmt (bsi);
1332 /* A copy between 2 partitions does not introduce an interference
1333 by itself. If they did, you would never be able to coalesce
1334 two things which are copied. If the two variables really do
1335 conflict, they will conflict elsewhere in the program.
1337 This is handled specially here since we may also be interested
1338 in copies between real variables and SSA_NAME variables. We may
1339 be interested in trying to coalesce SSA_NAME variables with
1340 root variables in some cases. */
1342 if (TREE_CODE (stmt) == MODIFY_EXPR)
1344 tree lhs = TREE_OPERAND (stmt, 0);
1345 tree rhs = TREE_OPERAND (stmt, 1);
1346 int p1, p2;
1347 int bit;
1349 if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
1350 p1 = var_to_partition (map, lhs);
1351 else
1352 p1 = NO_PARTITION;
1354 if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
1355 p2 = var_to_partition (map, rhs);
1356 else
1357 p2 = NO_PARTITION;
1359 if (p1 != NO_PARTITION && p2 != NO_PARTITION)
1361 is_a_copy = true;
1362 bit = bitmap_bit_p (live, p2);
1363 /* If the RHS is live, make it not live while we add
1364 the conflicts, then make it live again. */
1365 if (bit)
1366 bitmap_clear_bit (live, p2);
1367 add_conflicts_if_valid (tpa, graph, map, live, lhs);
1368 if (bit)
1369 bitmap_set_bit (live, p2);
1370 if (cl)
1371 add_coalesce (cl, p1, p2, 1);
1372 set_if_valid (map, live, rhs);
1376 if (!is_a_copy)
1378 tree var;
1379 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
1381 add_conflicts_if_valid (tpa, graph, map, live, var);
1384 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1386 set_if_valid (map, live, var);
1391 /* If result of a PHI is unused, then the loops over the statements
1392 will not record any conflicts. However, since the PHI node is
1393 going to be translated out of SSA form we must record a conflict
1394 between the result of the PHI and any variables with are live.
1395 Otherwise the out-of-ssa translation may create incorrect code. */
1396 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1398 tree result = PHI_RESULT (phi);
1399 int p = var_to_partition (map, result);
1401 if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
1402 add_conflicts_if_valid (tpa, graph, map, live, result);
1405 /* Anything which is still live at this point interferes.
1406 In order to implement this efficiently, only conflicts between
1407 partitions which have the same TPA root need be added.
1408 TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
1409 entry points to an index into 'partition_link', which then indexes
1410 into itself forming a linked list of partitions sharing a tpa root
1411 which have been seen as live up to this point. Since partitions start
1412 at index zero, all entries in partition_link are (partition + 1).
1414 Conflicts are added between the current partition and any already seen.
1415 tpa_clear contains all the tpa_roots processed, and these are the only
1416 entries which need to be zero'd out for a clean restart. */
1418 EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
1420 i = tpa_find_tree (tpa, x);
1421 if (i != (unsigned)TPA_NONE)
1423 int start = tpa_nodes[i];
1424 /* If start is 0, a new root reference list is being started.
1425 Register it to be cleared. */
1426 if (!start)
1427 VEC_safe_push (int, heap, tpa_to_clear, i);
1429 /* Add interferences to other tpa members seen. */
1430 for (y = start; y != 0; y = partition_link[y])
1431 conflict_graph_add (graph, x, y - 1);
1432 tpa_nodes[i] = x + 1;
1433 partition_link[x + 1] = start;
1437 /* Now clear the used tpa root references. */
1438 for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++)
1439 tpa_nodes[idx] = 0;
1440 VEC_truncate (int, tpa_to_clear, 0);
1443 free (tpa_nodes);
1444 free (partition_link);
1445 VEC_free (int, heap, tpa_to_clear);
1446 BITMAP_FREE (live);
1447 return graph;
1451 /* This routine will attempt to coalesce the elements in TPA subject to the
1452 conflicts found in GRAPH. If optional coalesce_list CL is provided,
1453 only coalesces specified within the coalesce list are attempted. Otherwise
1454 an attempt is made to coalesce as many partitions within each TPA grouping
1455 as possible. If DEBUG is provided, debug output will be sent there. */
1457 void
1458 coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
1459 coalesce_list_p cl, FILE *debug)
1461 int x, y, z, w;
1462 tree var, tmp;
1464 /* Attempt to coalesce any items in a coalesce list. */
1465 if (cl)
1467 while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
1469 if (debug)
1471 fprintf (debug, "Coalesce list: (%d)", x);
1472 print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
1473 fprintf (debug, " & (%d)", y);
1474 print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
1477 w = tpa_find_tree (tpa, x);
1478 z = tpa_find_tree (tpa, y);
1479 if (w != z || w == TPA_NONE || z == TPA_NONE)
1481 if (debug)
1483 if (w != z)
1484 fprintf (debug, ": Fail, Non-matching TPA's\n");
1485 if (w == TPA_NONE)
1486 fprintf (debug, ": Fail %d non TPA.\n", x);
1487 else
1488 fprintf (debug, ": Fail %d non TPA.\n", y);
1490 continue;
1492 var = partition_to_var (map, x);
1493 tmp = partition_to_var (map, y);
1494 x = var_to_partition (map, var);
1495 y = var_to_partition (map, tmp);
1496 if (debug)
1497 fprintf (debug, " [map: %d, %d] ", x, y);
1498 if (x == y)
1500 if (debug)
1501 fprintf (debug, ": Already Coalesced.\n");
1502 continue;
1504 if (!conflict_graph_conflict_p (graph, x, y))
1506 z = var_union (map, var, tmp);
1507 if (z == NO_PARTITION)
1509 if (debug)
1510 fprintf (debug, ": Unable to perform partition union.\n");
1511 continue;
1514 /* z is the new combined partition. We need to remove the other
1515 partition from the list. Set x to be that other partition. */
1516 if (z == x)
1518 conflict_graph_merge_regs (graph, x, y);
1519 w = tpa_find_tree (tpa, y);
1520 tpa_remove_partition (tpa, w, y);
1522 else
1524 conflict_graph_merge_regs (graph, y, x);
1525 w = tpa_find_tree (tpa, x);
1526 tpa_remove_partition (tpa, w, x);
1529 if (debug)
1530 fprintf (debug, ": Success -> %d\n", z);
1532 else
1533 if (debug)
1534 fprintf (debug, ": Fail due to conflict\n");
1536 /* If using a coalesce list, don't try to coalesce anything else. */
1537 return;
1540 for (x = 0; x < tpa_num_trees (tpa); x++)
1542 while (tpa_first_partition (tpa, x) != TPA_NONE)
1544 int p1, p2;
1545 /* Coalesce first partition with anything that doesn't conflict. */
1546 y = tpa_first_partition (tpa, x);
1547 tpa_remove_partition (tpa, x, y);
1549 var = partition_to_var (map, y);
1550 /* p1 is the partition representative to which y belongs. */
1551 p1 = var_to_partition (map, var);
1553 for (z = tpa_next_partition (tpa, y);
1554 z != TPA_NONE;
1555 z = tpa_next_partition (tpa, z))
1557 tmp = partition_to_var (map, z);
1558 /* p2 is the partition representative to which z belongs. */
1559 p2 = var_to_partition (map, tmp);
1560 if (debug)
1562 fprintf (debug, "Coalesce : ");
1563 print_generic_expr (debug, var, TDF_SLIM);
1564 fprintf (debug, " &");
1565 print_generic_expr (debug, tmp, TDF_SLIM);
1566 fprintf (debug, " (%d ,%d)", p1, p2);
1569 /* If partitions are already merged, don't check for conflict. */
1570 if (tmp == var)
1572 tpa_remove_partition (tpa, x, z);
1573 if (debug)
1574 fprintf (debug, ": Already coalesced\n");
1576 else
1577 if (!conflict_graph_conflict_p (graph, p1, p2))
1579 int v;
1580 if (tpa_find_tree (tpa, y) == TPA_NONE
1581 || tpa_find_tree (tpa, z) == TPA_NONE)
1583 if (debug)
1584 fprintf (debug, ": Fail non-TPA member\n");
1585 continue;
1587 if ((v = var_union (map, var, tmp)) == NO_PARTITION)
1589 if (debug)
1590 fprintf (debug, ": Fail cannot combine partitions\n");
1591 continue;
1594 tpa_remove_partition (tpa, x, z);
1595 if (v == p1)
1596 conflict_graph_merge_regs (graph, v, z);
1597 else
1599 /* Update the first partition's representative. */
1600 conflict_graph_merge_regs (graph, v, y);
1601 p1 = v;
1604 /* The root variable of the partition may be changed
1605 now. */
1606 var = partition_to_var (map, p1);
1608 if (debug)
1609 fprintf (debug, ": Success -> %d\n", v);
1611 else
1612 if (debug)
1613 fprintf (debug, ": Fail, Conflict\n");
1620 /* Send debug info for coalesce list CL to file F. */
1622 void
1623 dump_coalesce_list (FILE *f, coalesce_list_p cl)
1625 partition_pair_p node;
1626 int x, num;
1627 tree var;
1629 if (cl->add_mode)
1631 fprintf (f, "Coalesce List:\n");
1632 num = num_var_partitions (cl->map);
1633 for (x = 0; x < num; x++)
1635 node = cl->list[x];
1636 if (node)
1638 fprintf (f, "[");
1639 print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
1640 fprintf (f, "] - ");
1641 for ( ; node; node = node->next)
1643 var = partition_to_var (cl->map, node->second_partition);
1644 print_generic_expr (f, var, TDF_SLIM);
1645 fprintf (f, "(%1d), ", node->cost);
1647 fprintf (f, "\n");
1651 else
1653 fprintf (f, "Sorted Coalesce list:\n");
1654 for (node = cl->list[0]; node; node = node->next)
1656 fprintf (f, "(%d) ", node->cost);
1657 var = partition_to_var (cl->map, node->first_partition);
1658 print_generic_expr (f, var, TDF_SLIM);
1659 fprintf (f, " : ");
1660 var = partition_to_var (cl->map, node->second_partition);
1661 print_generic_expr (f, var, TDF_SLIM);
1662 fprintf (f, "\n");
1668 /* Output tree_partition_associator object TPA to file F.. */
1670 void
1671 tpa_dump (FILE *f, tpa_p tpa)
1673 int x, i;
1675 if (!tpa)
1676 return;
1678 for (x = 0; x < tpa_num_trees (tpa); x++)
1680 print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
1681 fprintf (f, " : (");
1682 for (i = tpa_first_partition (tpa, x);
1683 i != TPA_NONE;
1684 i = tpa_next_partition (tpa, i))
1686 fprintf (f, "(%d)",i);
1687 print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
1688 fprintf (f, " ");
1690 #ifdef ENABLE_CHECKING
1691 if (tpa_find_tree (tpa, i) != x)
1692 fprintf (f, "**find tree incorrectly set** ");
1693 #endif
1696 fprintf (f, ")\n");
1698 fflush (f);
1702 /* Output partition map MAP to file F. */
1704 void
1705 dump_var_map (FILE *f, var_map map)
1707 int t;
1708 unsigned x, y;
1709 int p;
1711 fprintf (f, "\nPartition map \n\n");
1713 for (x = 0; x < map->num_partitions; x++)
1715 if (map->compact_to_partition != NULL)
1716 p = map->compact_to_partition[x];
1717 else
1718 p = x;
1720 if (map->partition_to_var[p] == NULL_TREE)
1721 continue;
1723 t = 0;
1724 for (y = 1; y < num_ssa_names; y++)
1726 p = partition_find (map->var_partition, y);
1727 if (map->partition_to_compact)
1728 p = map->partition_to_compact[p];
1729 if (p == (int)x)
1731 if (t++ == 0)
1733 fprintf(f, "Partition %d (", x);
1734 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1735 fprintf (f, " - ");
1737 fprintf (f, "%d ", y);
1740 if (t != 0)
1741 fprintf (f, ")\n");
1743 fprintf (f, "\n");
1747 /* Output live range info LIVE to file F, controlled by FLAG. */
1749 void
1750 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1752 basic_block bb;
1753 unsigned i;
1754 var_map map = live->map;
1755 bitmap_iterator bi;
1757 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1759 FOR_EACH_BB (bb)
1761 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1762 for (i = 0; i < num_var_partitions (map); i++)
1764 if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
1766 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1767 fprintf (f, " ");
1770 fprintf (f, "\n");
1774 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1776 FOR_EACH_BB (bb)
1778 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1779 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1781 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1782 fprintf (f, " ");
1784 fprintf (f, "\n");
1789 #ifdef ENABLE_CHECKING
1790 void
1791 register_ssa_partition_check (tree ssa_var)
1793 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1794 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1796 fprintf (stderr, "Illegally registering a virtual SSA name :");
1797 print_generic_expr (stderr, ssa_var, TDF_SLIM);
1798 fprintf (stderr, " in the SSA->Normal phase.\n");
1799 internal_error ("SSA corruption");
1802 #endif