1 /* Liveness for SSA trees.
2 Copyright (C) 2003, 2004 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)
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. */
24 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-inline.h"
38 #include "tree-dump.h"
39 #include "tree-ssa-live.h"
42 static void live_worklist (tree_live_info_p, varray_type, int);
43 static tree_live_info_p new_tree_live_info (var_map);
44 static inline void set_if_valid (var_map, bitmap, tree);
45 static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
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
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. */
67 init_var_map (int size)
71 map = (var_map) xmalloc (sizeof (struct _var_map));
72 map->var_partition = partition_new (size);
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;
86 /* Free memory associated with MAP. */
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);
98 free (map->ref_count);
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)
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));
122 p1 = var_to_partition (map, var1);
123 if (map->compact_to_partition)
124 p1 = map->compact_to_partition[p1];
128 if (TREE_CODE (var2) == SSA_NAME)
129 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
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;
147 gcc_assert (p1 != NO_PARTITION);
148 gcc_assert (p2 != NO_PARTITION);
153 p3 = partition_union (map->var_partition, p1, p2);
155 if (map->partition_to_compact)
156 p3 = map->partition_to_compact[p3];
159 change_partition_var (map, root_var, p3);
161 change_partition_var (map, other_var, 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. */
185 compact_var_map (var_map map, int flags)
188 int x, limit, count, tmp, root, root_i;
190 root_var_p rv = NULL;
192 limit = map->partition_size;
193 used = sbitmap_alloc (limit);
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. */
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. */
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)
238 /* Build a compacted partitioning. */
241 map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
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);
256 free (map->partition_to_compact);
257 map->partition_to_compact = NULL;
260 map->num_partitions = count;
263 root_var_delete (rv);
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. */
273 change_partition_var (var_map map, tree var, int part)
277 gcc_assert (TREE_CODE (var) != SSA_NAME);
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. */
290 mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
291 void *data ATTRIBUTE_UNUSED)
295 /* Only need to mark VAR_DECLS; parameters and return results are not
296 eliminated as unused. */
297 if (TREE_CODE (t) == VAR_DECL)
300 if (IS_TYPE_OR_DECL_P (t))
306 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
307 eliminated during the tree->rtl conversion process. */
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. */
320 create_ssa_var_map (int flags)
322 block_stmt_iterator bsi;
329 #ifdef ENABLE_CHECKING
330 sbitmap used_in_real_ops;
331 sbitmap used_in_virtual_ops;
334 map = init_var_map (num_ssa_names + 1);
336 #ifdef ENABLE_CHECKING
337 used_in_real_ops = sbitmap_alloc (num_referenced_vars);
338 sbitmap_zero (used_in_real_ops);
340 used_in_virtual_ops = sbitmap_alloc (num_referenced_vars);
341 sbitmap_zero (used_in_virtual_ops);
344 if (flags & SSA_VAR_MAP_REF_COUNT)
347 = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
348 memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
354 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
357 register_ssa_partition (map, PHI_RESULT (phi), false);
358 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
360 arg = PHI_ARG_DEF (phi, i);
361 if (TREE_CODE (arg) == SSA_NAME)
362 register_ssa_partition (map, arg, true);
364 mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
368 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
370 stmt = bsi_stmt (bsi);
371 get_stmt_operands (stmt);
372 ann = stmt_ann (stmt);
374 /* Register USE and DEF operands in each statement. */
375 FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
377 register_ssa_partition (map, use, true);
379 #ifdef ENABLE_CHECKING
380 SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (use))->uid);
384 FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF)
386 register_ssa_partition (map, dest, false);
388 #ifdef ENABLE_CHECKING
389 SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (dest))->uid);
393 #ifdef ENABLE_CHECKING
394 /* Validate that virtual ops don't get used in funny ways. */
395 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter,
396 SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
398 SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (use))->uid);
401 #endif /* ENABLE_CHECKING */
403 mark_all_vars_used (bsi_stmt_ptr (bsi));
407 #if defined ENABLE_CHECKING
410 sbitmap both = sbitmap_alloc (num_referenced_vars);
411 sbitmap_a_and_b (both, used_in_real_ops, used_in_virtual_ops);
412 if (sbitmap_first_set_bit (both) >= 0)
414 EXECUTE_IF_SET_IN_SBITMAP (both, 0, i,
415 fprintf (stderr, "Variable %s used in real and virtual operands\n",
416 get_name (referenced_var (i))));
417 internal_error ("SSA corruption");
420 sbitmap_free (used_in_real_ops);
421 sbitmap_free (used_in_virtual_ops);
430 /* Allocate and return a new live range information object base on MAP. */
432 static tree_live_info_p
433 new_tree_live_info (var_map map)
435 tree_live_info_p live;
438 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
440 live->num_blocks = last_basic_block;
442 live->global = BITMAP_XMALLOC ();
444 live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
445 for (x = 0; x < num_var_partitions (map); x++)
446 live->livein[x] = BITMAP_XMALLOC ();
448 /* liveout is deferred until it is actually requested. */
449 live->liveout = NULL;
454 /* Free storage for live range info object LIVE. */
457 delete_tree_live_info (tree_live_info_p live)
462 for (x = live->num_blocks - 1; x >= 0; x--)
463 BITMAP_XFREE (live->liveout[x]);
464 free (live->liveout);
468 for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
469 BITMAP_XFREE (live->livein[x]);
473 BITMAP_XFREE (live->global);
479 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
480 for partition I. STACK is a varray used for temporary memory which is
481 passed in rather than being allocated on every call. */
484 live_worklist (tree_live_info_p live, varray_type stack, int i)
488 basic_block def_bb = NULL;
490 var_map map = live->map;
493 var = partition_to_var (map, i);
494 if (SSA_NAME_DEF_STMT (var))
495 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
497 EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
499 VARRAY_PUSH_INT (stack, b);
502 while (VARRAY_ACTIVE_SIZE (stack) > 0)
504 b = VARRAY_TOP_INT (stack);
507 for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
508 if (e->src != ENTRY_BLOCK_PTR)
510 /* Its not live on entry to the block its defined in. */
511 if (e->src == def_bb)
513 if (!bitmap_bit_p (live->livein[i], e->src->index))
515 bitmap_set_bit (live->livein[i], e->src->index);
516 VARRAY_PUSH_INT (stack, e->src->index);
523 /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
526 set_if_valid (var_map map, bitmap vec, tree var)
528 int p = var_to_partition (map, var);
529 if (p != NO_PARTITION)
530 bitmap_set_bit (vec, p);
534 /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
535 global bit for it in the LIVE object. BB is the block being processed. */
538 add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
539 tree var, basic_block bb)
541 int p = var_to_partition (live->map, var);
542 if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
544 if (!bitmap_bit_p (def_vec, p))
546 bitmap_set_bit (live->livein[p], bb->index);
547 bitmap_set_bit (live->global, p);
552 /* Given partition map MAP, calculate all the live on entry bitmaps for
553 each basic block. Return a live info object. */
556 calculate_live_on_entry (var_map map)
558 tree_live_info_p live;
566 block_stmt_iterator bsi;
570 #ifdef ENABLE_CHECKING
575 saw_def = BITMAP_XMALLOC ();
577 live = new_tree_live_info (map);
581 bitmap_clear (saw_def);
583 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
585 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
587 var = PHI_ARG_DEF (phi, i);
588 if (!phi_ssa_name_p (var))
590 stmt = SSA_NAME_DEF_STMT (var);
591 e = PHI_ARG_EDGE (phi, i);
593 /* Any uses in PHIs which either don't have def's or are not
594 defined in the block from which the def comes, will be live
595 on entry to that block. */
596 if (!stmt || e->src != bb_for_stmt (stmt))
597 add_livein_if_notdef (live, saw_def, var, e->src);
601 /* Don't mark PHI results as defined until all the PHI nodes have
602 been processed. If the PHI sequence is:
605 The a_3 referred to in b_3's PHI node is the one incoming on the
606 edge, *not* the PHI node just seen. */
608 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
610 var = PHI_RESULT (phi);
611 set_if_valid (map, saw_def, var);
614 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
616 stmt = bsi_stmt (bsi);
617 get_stmt_operands (stmt);
618 ann = stmt_ann (stmt);
620 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
622 add_livein_if_notdef (live, saw_def, op, bb);
625 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
627 set_if_valid (map, saw_def, op);
632 VARRAY_INT_INIT (stack, last_basic_block, "stack");
633 EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
635 live_worklist (live, stack, i);
638 #ifdef ENABLE_CHECKING
639 /* Check for live on entry partitions and report those with a DEF in
640 the program. This will typically mean an optimization has done
643 bb = ENTRY_BLOCK_PTR;
645 for (e = bb->succ; e; e = e->succ_next)
647 int entry_block = e->dest->index;
648 if (e->dest == EXIT_BLOCK_PTR)
650 for (i = 0; i < num_var_partitions (map); i++)
654 var = partition_to_var (map, i);
655 stmt = SSA_NAME_DEF_STMT (var);
656 tmp = bb_for_stmt (stmt);
657 d = default_def (SSA_NAME_VAR (var));
659 if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
661 if (!IS_EMPTY_STMT (stmt))
664 print_generic_expr (stderr, var, TDF_SLIM);
665 fprintf (stderr, " is defined ");
667 fprintf (stderr, " in BB%d, ", tmp->index);
668 fprintf (stderr, "by:\n");
669 print_generic_expr (stderr, stmt, TDF_SLIM);
670 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
672 fprintf (stderr, " So it appears to have multiple defs.\n");
679 print_generic_expr (stderr, var, TDF_SLIM);
680 fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
683 fprintf (stderr, " but is not the default def of ");
684 print_generic_expr (stderr, d, TDF_SLIM);
685 fprintf (stderr, "\n");
688 fprintf (stderr, " and there is no default def.\n");
695 /* The only way this var shouldn't be marked live on entry is
696 if it occurs in a PHI argument of the block. */
698 for (phi = phi_nodes (e->dest);
700 phi = PHI_CHAIN (phi))
702 for (z = 0; z < PHI_NUM_ARGS (phi); z++)
703 if (var == PHI_ARG_DEF (phi, z))
712 print_generic_expr (stderr, var, TDF_SLIM);
713 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
715 fprintf (stderr, "but it is a default def so it should be.\n");
719 gcc_assert (num <= 0);
722 BITMAP_XFREE (saw_def);
728 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
731 calculate_live_on_exit (tree_live_info_p liveinfo)
740 var_map map = liveinfo->map;
742 on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
743 for (x = 0; x < last_basic_block; x++)
744 on_exit[x] = BITMAP_XMALLOC ();
746 /* Set all the live-on-exit bits for uses in PHIs. */
749 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
750 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
752 t = PHI_ARG_DEF (phi, i);
753 e = PHI_ARG_EDGE (phi, i);
754 if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
756 set_if_valid (map, on_exit[e->src->index], t);
760 /* Set live on exit for all predecessors of live on entry's. */
761 for (i = 0; i < num_var_partitions (map); i++)
765 on_entry = live_entry_blocks (liveinfo, i);
766 EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
768 for (e = BASIC_BLOCK(b)->pred; e; e = e->pred_next)
769 if (e->src != ENTRY_BLOCK_PTR)
770 bitmap_set_bit (on_exit[e->src->index], i);
774 liveinfo->liveout = on_exit;
778 /* Initialize a tree_partition_associator object using MAP. */
781 tpa_init (var_map map)
784 int num_partitions = num_var_partitions (map);
787 if (num_partitions == 0)
790 tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
792 tpa->uncompressed_num = -1;
794 tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
795 memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
797 tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
798 memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
800 x = MAX (40, (num_partitions / 20));
801 VARRAY_TREE_INIT (tpa->trees, x, "trees");
802 VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
809 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
812 tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
816 i = tpa_first_partition (tpa, tree_index);
817 if (i == partition_index)
819 VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i];
823 for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
825 if (tpa->next_partition[i] == partition_index)
827 tpa->next_partition[i] = tpa->next_partition[partition_index];
835 /* Free the memory used by tree_partition_associator object TPA. */
838 tpa_delete (tpa_p tpa)
843 free (tpa->partition_to_tree_map);
844 free (tpa->next_partition);
849 /* This function will remove any tree entries from TPA which have only a single
850 element. This will help keep the size of the conflict graph down. The
851 function returns the number of remaining tree lists. */
854 tpa_compact (tpa_p tpa)
856 int last, x, y, first, swap_i;
859 /* Find the last list which has more than 1 partition. */
860 for (last = tpa->num_trees - 1; last > 0; last--)
862 first = tpa_first_partition (tpa, last);
863 if (tpa_next_partition (tpa, first) != NO_PARTITION)
870 first = tpa_first_partition (tpa, x);
872 /* If there is not more than one partition, swap with the current end
874 if (tpa_next_partition (tpa, first) == NO_PARTITION)
876 swap_t = VARRAY_TREE (tpa->trees, last);
877 swap_i = VARRAY_INT (tpa->first_partition, last);
879 /* Update the last entry. Since it is known to only have one
880 partition, there is nothing else to update. */
881 VARRAY_TREE (tpa->trees, last) = VARRAY_TREE (tpa->trees, x);
882 VARRAY_INT (tpa->first_partition, last)
883 = VARRAY_INT (tpa->first_partition, x);
884 tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
886 /* Since this list is known to have more than one partition, update
887 the list owner entries. */
888 VARRAY_TREE (tpa->trees, x) = swap_t;
889 VARRAY_INT (tpa->first_partition, x) = swap_i;
890 for (y = tpa_first_partition (tpa, x);
892 y = tpa_next_partition (tpa, y))
893 tpa->partition_to_tree_map[y] = x;
895 /* Ensure last is a list with more than one partition. */
897 for (; last > x; last--)
899 first = tpa_first_partition (tpa, last);
900 if (tpa_next_partition (tpa, first) != NO_PARTITION)
907 first = tpa_first_partition (tpa, x);
908 if (tpa_next_partition (tpa, first) != NO_PARTITION)
910 tpa->uncompressed_num = tpa->num_trees;
916 /* Initialize a root_var object with SSA partitions from MAP which are based
917 on each root variable. */
920 root_var_init (var_map map)
923 int num_partitions = num_var_partitions (map);
933 seen = sbitmap_alloc (num_partitions);
936 /* Start at the end and work towards the front. This will provide a list
937 that is ordered from smallest to largest. */
938 for (x = num_partitions - 1; x >= 0; x--)
940 t = partition_to_var (map, x);
942 /* The var map may not be compacted yet, so check for NULL. */
946 p = var_to_partition (map, t);
948 gcc_assert (p != NO_PARTITION);
950 /* Make sure we only put coalesced partitions into the list once. */
951 if (TEST_BIT (seen, p))
954 if (TREE_CODE (t) == SSA_NAME)
955 t = SSA_NAME_VAR (t);
957 if (ann->root_var_processed)
959 rv->next_partition[p] = VARRAY_INT (rv->first_partition,
960 VAR_ANN_ROOT_INDEX (ann));
961 VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p;
965 ann->root_var_processed = 1;
966 VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
967 VARRAY_PUSH_TREE (rv->trees, t);
968 VARRAY_PUSH_INT (rv->first_partition, p);
970 rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
973 /* Reset the out_of_ssa_tag flag on each variable for later use. */
974 for (x = 0; x < rv->num_trees; x++)
976 t = VARRAY_TREE (rv->trees, x);
977 var_ann (t)->root_var_processed = 0;
985 /* Initialize a type_var structure which associates all the partitions in MAP
986 of the same type to the type node's index. Volatiles are ignored. */
989 type_var_init (var_map map)
993 int num_partitions = num_var_partitions (map);
997 seen = sbitmap_alloc (num_partitions);
1000 tv = tpa_init (map);
1004 for (x = num_partitions - 1; x >= 0; x--)
1006 t = partition_to_var (map, x);
1008 /* Disallow coalescing of these types of variables. */
1010 || TREE_THIS_VOLATILE (t)
1011 || TREE_CODE (t) == RESULT_DECL
1012 || TREE_CODE (t) == PARM_DECL
1014 && (DECL_REGISTER (t)
1015 || !DECL_IGNORED_P (t)
1016 || DECL_RTL_SET_P (t))))
1019 p = var_to_partition (map, t);
1021 gcc_assert (p != NO_PARTITION);
1023 /* If partitions have been coalesced, only add the representative
1024 for the partition to the list once. */
1025 if (TEST_BIT (seen, p))
1030 /* Find the list for this type. */
1031 for (y = 0; y < tv->num_trees; y++)
1032 if (t == VARRAY_TREE (tv->trees, y))
1034 if (y == tv->num_trees)
1037 VARRAY_PUSH_TREE (tv->trees, t);
1038 VARRAY_PUSH_INT (tv->first_partition, p);
1042 tv->next_partition[p] = VARRAY_INT (tv->first_partition, y);
1043 VARRAY_INT (tv->first_partition, y) = p;
1045 tv->partition_to_tree_map[p] = y;
1047 sbitmap_free (seen);
1052 /* Create a new coalesce list object from MAP and return it. */
1055 create_coalesce_list (var_map map)
1057 coalesce_list_p list;
1059 list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
1062 list->add_mode = true;
1063 list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
1064 sizeof (struct partition_pair_d));
1069 /* Delete coalesce list CL. */
1072 delete_coalesce_list (coalesce_list_p cl)
1079 /* Find a matching coalesce pair object in CL for partitions P1 and P2. If
1080 one isn't found, return NULL if CREATE is false, otherwise create a new
1081 coalesce pair object and return it. */
1083 static partition_pair_p
1084 find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
1086 partition_pair_p node, tmp;
1089 /* Normalize so that p1 is the smaller value. */
1099 /* The list is sorted such that if we find a value greater than p2,
1100 p2 is not in the list. */
1101 for (node = cl->list[p1]; node; node = node->next)
1103 if (node->second_partition == p2)
1106 if (node->second_partition > p2)
1114 node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
1115 node->first_partition = p1;
1116 node->second_partition = p2;
1121 node->next = tmp->next;
1126 /* This is now the first node in the list. */
1127 node->next = cl->list[p1];
1128 cl->list[p1] = node;
1135 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
1138 add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
1140 partition_pair_p node;
1142 gcc_assert (cl->add_mode);
1147 node = find_partition_pair (cl, p1, p2, true);
1149 node->cost += value;
1153 /* Comparison function to allow qsort to sort P1 and P2 in descending order. */
1156 int compare_pairs (const void *p1, const void *p2)
1158 return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
1162 /* Prepare CL for removal of preferred pairs. When finished, list element
1163 0 has all the coalesce pairs, sorted in order from most important coalesce
1164 to least important. */
1167 sort_coalesce_list (coalesce_list_p cl)
1170 partition_pair_p chain, p;
1171 partition_pair_p *list;
1173 gcc_assert (cl->add_mode);
1175 cl->add_mode = false;
1177 /* Compact the array of lists to a single list, and count the elements. */
1180 for (x = 0; x < num_var_partitions (cl->map); x++)
1181 if (cl->list[x] != NULL)
1183 for (p = cl->list[x]; p->next != NULL; p = p->next)
1187 chain = cl->list[x];
1191 /* Only call qsort if there are more than 2 items. */
1194 list = xmalloc (sizeof (partition_pair_p) * num);
1196 for (p = chain; p != NULL; p = p->next)
1199 gcc_assert (count == num);
1201 qsort (list, count, sizeof (partition_pair_p), compare_pairs);
1204 for (x = 1; x < num; x++)
1210 cl->list[0] = list[0];
1215 cl->list[0] = chain;
1218 /* Simply swap the two elements if they are in the wrong order. */
1219 if (chain->cost < chain->next->cost)
1221 cl->list[0] = chain->next;
1222 cl->list[0]->next = chain;
1230 /* Retrieve the best remaining pair to coalesce from CL. Returns the 2
1231 partitions via P1 and P2. Their calculated cost is returned by the function.
1232 NO_BEST_COALESCE is returned if the coalesce list is empty. */
1235 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
1237 partition_pair_p node;
1240 gcc_assert (!cl->add_mode);
1244 return NO_BEST_COALESCE;
1246 cl->list[0] = node->next;
1248 *p1 = node->first_partition;
1249 *p2 = node->second_partition;
1257 /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
1258 VAR and any other live partitions in VEC which are associated via TPA.
1259 Reset the live bit in VEC. */
1262 add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
1263 var_map map, bitmap vec, tree var)
1266 p = var_to_partition (map, var);
1267 if (p != NO_PARTITION)
1269 bitmap_clear_bit (vec, p);
1270 first = tpa_find_tree (tpa, p);
1271 /* If find returns nothing, this object isn't interesting. */
1272 if (first == TPA_NONE)
1274 /* Only add interferences between objects in the same list. */
1275 for (y = tpa_first_partition (tpa, first);
1277 y = tpa_next_partition (tpa, y))
1279 if (bitmap_bit_p (vec, y))
1280 conflict_graph_add (graph, p, y);
1286 /* Return a conflict graph for the information contained in LIVE_INFO. Only
1287 conflicts between items in the same TPA list are added. If optional
1288 coalesce list CL is passed in, any copies encountered are added. */
1291 build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
1294 conflict_graph graph;
1299 varray_type partition_link, tpa_to_clear, tpa_nodes;
1304 map = live_var_map (liveinfo);
1305 graph = conflict_graph_new (num_var_partitions (map));
1307 if (tpa_num_trees (tpa) == 0)
1310 live = BITMAP_XMALLOC ();
1312 VARRAY_INT_INIT (partition_link, num_var_partitions (map) + 1, "part_link");
1313 VARRAY_INT_INIT (tpa_nodes, tpa_num_trees (tpa), "tpa nodes");
1314 VARRAY_INT_INIT (tpa_to_clear, 50, "tpa to clear");
1318 block_stmt_iterator bsi;
1321 /* Start with live on exit temporaries. */
1322 bitmap_copy (live, live_on_exit (liveinfo, bb));
1324 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1326 bool is_a_copy = false;
1327 tree stmt = bsi_stmt (bsi);
1330 get_stmt_operands (stmt);
1331 ann = stmt_ann (stmt);
1333 /* A copy between 2 partitions does not introduce an interference
1334 by itself. If they did, you would never be able to coalesce
1335 two things which are copied. If the two variables really do
1336 conflict, they will conflict elsewhere in the program.
1338 This is handled specially here since we may also be interested
1339 in copies between real variables and SSA_NAME variables. We may
1340 be interested in trying to coalesce SSA_NAME variables with
1341 root variables in some cases. */
1343 if (TREE_CODE (stmt) == MODIFY_EXPR)
1345 tree lhs = TREE_OPERAND (stmt, 0);
1346 tree rhs = TREE_OPERAND (stmt, 1);
1350 if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
1351 p1 = var_to_partition (map, lhs);
1355 if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
1356 p2 = var_to_partition (map, rhs);
1360 if (p1 != NO_PARTITION && p2 != NO_PARTITION)
1363 bit = bitmap_bit_p (live, p2);
1364 /* If the RHS is live, make it not live while we add
1365 the conflicts, then make it live again. */
1367 bitmap_clear_bit (live, p2);
1368 add_conflicts_if_valid (tpa, graph, map, live, lhs);
1370 bitmap_set_bit (live, p2);
1372 add_coalesce (cl, p1, p2, 1);
1373 set_if_valid (map, live, rhs);
1380 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
1382 add_conflicts_if_valid (tpa, graph, map, live, var);
1385 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1387 set_if_valid (map, live, var);
1392 /* If result of a PHI is unused, then the loops over the statements
1393 will not record any conflicts. However, since the PHI node is
1394 going to be translated out of SSA form we must record a conflict
1395 between the result of the PHI and any variables with are live.
1396 Otherwise the out-of-ssa translation may create incorrect code. */
1397 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1399 tree result = PHI_RESULT (phi);
1400 int p = var_to_partition (map, result);
1402 if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
1403 add_conflicts_if_valid (tpa, graph, map, live, result);
1406 /* Anything which is still live at this point interferes.
1407 In order to implement this efficiently, only conflicts between
1408 partitions which have the same TPA root need be added.
1409 TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
1410 entry points to an index into 'partition_link', which then indexes
1411 into itself forming a linked list of partitions sharing a tpa root
1412 which have been seen as live up to this point. Since partitions start
1413 at index zero, all entries in partition_link are (partition + 1).
1415 Conflicts are added between the current partition and any already seen.
1416 tpa_clear contains all the tpa_roots processed, and these are the only
1417 entries which need to be zero'd out for a clean restart. */
1419 EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
1421 i = tpa_find_tree (tpa, x);
1424 int start = VARRAY_INT (tpa_nodes, i);
1425 /* If start is 0, a new root reference list is being started.
1426 Register it to be cleared. */
1428 VARRAY_PUSH_INT (tpa_to_clear, i);
1430 /* Add interferences to other tpa members seen. */
1431 for (y = start; y != 0; y = VARRAY_INT (partition_link, y))
1432 conflict_graph_add (graph, x, y - 1);
1433 VARRAY_INT (tpa_nodes, i) = x + 1;
1434 VARRAY_INT (partition_link, x + 1) = start;
1438 /* Now clear the used tpa root references. */
1439 for (l = 0; l < VARRAY_ACTIVE_SIZE (tpa_to_clear); l++)
1440 VARRAY_INT (tpa_nodes, VARRAY_INT (tpa_to_clear, l)) = 0;
1441 VARRAY_POP_ALL (tpa_to_clear);
1444 BITMAP_XFREE (live);
1449 /* This routine will attempt to coalesce the elements in TPA subject to the
1450 conflicts found in GRAPH. If optional coalesce_list CL is provided,
1451 only coalesces specified within the coalesce list are attempted. Otherwise
1452 an attempt is made to coalesce as many partitions within each TPA grouping
1453 as possible. If DEBUG is provided, debug output will be sent there. */
1456 coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
1457 coalesce_list_p cl, FILE *debug)
1462 /* Attempt to coalesce any items in a coalesce list. */
1465 while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
1469 fprintf (debug, "Coalesce list: (%d)", x);
1470 print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
1471 fprintf (debug, " & (%d)", y);
1472 print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
1475 w = tpa_find_tree (tpa, x);
1476 z = tpa_find_tree (tpa, y);
1477 if (w != z || w == TPA_NONE || z == TPA_NONE)
1482 fprintf (debug, ": Fail, Non-matching TPA's\n");
1484 fprintf (debug, ": Fail %d non TPA.\n", x);
1486 fprintf (debug, ": Fail %d non TPA.\n", y);
1490 var = partition_to_var (map, x);
1491 tmp = partition_to_var (map, y);
1492 x = var_to_partition (map, var);
1493 y = var_to_partition (map, tmp);
1495 fprintf (debug, " [map: %d, %d] ", x, y);
1499 fprintf (debug, ": Already Coalesced.\n");
1502 if (!conflict_graph_conflict_p (graph, x, y))
1504 z = var_union (map, var, tmp);
1505 if (z == NO_PARTITION)
1508 fprintf (debug, ": Unable to perform partition union.\n");
1512 /* z is the new combined partition. We need to remove the other
1513 partition from the list. Set x to be that other partition. */
1516 conflict_graph_merge_regs (graph, x, y);
1517 w = tpa_find_tree (tpa, y);
1518 tpa_remove_partition (tpa, w, y);
1522 conflict_graph_merge_regs (graph, y, x);
1523 w = tpa_find_tree (tpa, x);
1524 tpa_remove_partition (tpa, w, x);
1528 fprintf (debug, ": Success -> %d\n", z);
1532 fprintf (debug, ": Fail due to conflict\n");
1534 /* If using a coalesce list, don't try to coalesce anything else. */
1538 for (x = 0; x < tpa_num_trees (tpa); x++)
1540 while (tpa_first_partition (tpa, x) != TPA_NONE)
1543 /* Coalesce first partition with anything that doesn't conflict. */
1544 y = tpa_first_partition (tpa, x);
1545 tpa_remove_partition (tpa, x, y);
1547 var = partition_to_var (map, y);
1548 /* p1 is the partition representative to which y belongs. */
1549 p1 = var_to_partition (map, var);
1551 for (z = tpa_next_partition (tpa, y);
1553 z = tpa_next_partition (tpa, z))
1555 tmp = partition_to_var (map, z);
1556 /* p2 is the partition representative to which z belongs. */
1557 p2 = var_to_partition (map, tmp);
1560 fprintf (debug, "Coalesce : ");
1561 print_generic_expr (debug, var, TDF_SLIM);
1562 fprintf (debug, " &");
1563 print_generic_expr (debug, tmp, TDF_SLIM);
1564 fprintf (debug, " (%d ,%d)", p1, p2);
1567 /* If partitions are already merged, don't check for conflict. */
1570 tpa_remove_partition (tpa, x, z);
1572 fprintf (debug, ": Already coalesced\n");
1575 if (!conflict_graph_conflict_p (graph, p1, p2))
1578 if (tpa_find_tree (tpa, y) == TPA_NONE
1579 || tpa_find_tree (tpa, z) == TPA_NONE)
1582 fprintf (debug, ": Fail non-TPA member\n");
1585 if ((v = var_union (map, var, tmp)) == NO_PARTITION)
1588 fprintf (debug, ": Fail cannot combine partitions\n");
1592 tpa_remove_partition (tpa, x, z);
1594 conflict_graph_merge_regs (graph, v, z);
1597 /* Update the first partition's representative. */
1598 conflict_graph_merge_regs (graph, v, y);
1602 /* The root variable of the partition may be changed
1604 var = partition_to_var (map, p1);
1607 fprintf (debug, ": Success -> %d\n", v);
1611 fprintf (debug, ": Fail, Conflict\n");
1618 /* Send debug info for coalesce list CL to file F. */
1621 dump_coalesce_list (FILE *f, coalesce_list_p cl)
1623 partition_pair_p node;
1629 fprintf (f, "Coalesce List:\n");
1630 num = num_var_partitions (cl->map);
1631 for (x = 0; x < num; x++)
1637 print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
1638 fprintf (f, "] - ");
1639 for ( ; node; node = node->next)
1641 var = partition_to_var (cl->map, node->second_partition);
1642 print_generic_expr (f, var, TDF_SLIM);
1643 fprintf (f, "(%1d), ", node->cost);
1651 fprintf (f, "Sorted Coalesce list:\n");
1652 for (node = cl->list[0]; node; node = node->next)
1654 fprintf (f, "(%d) ", node->cost);
1655 var = partition_to_var (cl->map, node->first_partition);
1656 print_generic_expr (f, var, TDF_SLIM);
1658 var = partition_to_var (cl->map, node->second_partition);
1659 print_generic_expr (f, var, TDF_SLIM);
1666 /* Output tree_partition_associator object TPA to file F.. */
1669 tpa_dump (FILE *f, tpa_p tpa)
1676 for (x = 0; x < tpa_num_trees (tpa); x++)
1678 print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
1679 fprintf (f, " : (");
1680 for (i = tpa_first_partition (tpa, x);
1682 i = tpa_next_partition (tpa, i))
1684 fprintf (f, "(%d)",i);
1685 print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
1688 #ifdef ENABLE_CHECKING
1689 if (tpa_find_tree (tpa, i) != x)
1690 fprintf (f, "**find tree incorrectly set** ");
1700 /* Output partition map MAP to file F. */
1703 dump_var_map (FILE *f, var_map map)
1709 fprintf (f, "\nPartition map \n\n");
1711 for (x = 0; x < map->num_partitions; x++)
1713 if (map->compact_to_partition != NULL)
1714 p = map->compact_to_partition[x];
1718 if (map->partition_to_var[p] == NULL_TREE)
1722 for (y = 1; y < num_ssa_names; y++)
1724 p = partition_find (map->var_partition, y);
1725 if (map->partition_to_compact)
1726 p = map->partition_to_compact[p];
1731 fprintf(f, "Partition %d (", x);
1732 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1735 fprintf (f, "%d ", y);
1745 /* Output live range info LIVE to file F, controlled by FLAG. */
1748 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1752 var_map map = live->map;
1755 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1759 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1760 for (i = 0; i < num_var_partitions (map); i++)
1762 if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
1764 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1772 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1776 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1777 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1779 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1787 #ifdef ENABLE_CHECKING
1789 register_ssa_partition_check (tree ssa_var)
1791 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1792 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1794 fprintf (stderr, "Illegally registering a virtual SSA name :");
1795 print_generic_expr (stderr, ssa_var, TDF_SLIM);
1796 fprintf (stderr, " in the SSA->Normal phase.\n");
1797 internal_error ("SSA corruption");