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)
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, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, 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"
43 static void live_worklist (tree_live_info_p, int *, int);
44 static tree_live_info_p new_tree_live_info (var_map);
45 static inline void set_if_valid (var_map, bitmap, tree);
46 static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
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;
85 /* Free memory associated with MAP. */
88 delete_var_map (var_map map)
90 free (map->partition_to_var);
91 partition_delete (map->var_partition);
92 if (map->partition_to_compact)
93 free (map->partition_to_compact);
94 if (map->compact_to_partition)
95 free (map->compact_to_partition);
100 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
101 Returns the partition which represents the new partition. If the two
102 partitions cannot be combined, NO_PARTITION is returned. */
105 var_union (var_map map, tree var1, tree var2)
108 tree root_var = NULL_TREE;
109 tree other_var = NULL_TREE;
111 /* This is independent of partition_to_compact. If partition_to_compact is
112 on, then whichever one of these partitions is absorbed will never have a
113 dereference into the partition_to_compact array any more. */
115 if (TREE_CODE (var1) == SSA_NAME)
116 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
119 p1 = var_to_partition (map, var1);
120 if (map->compact_to_partition)
121 p1 = map->compact_to_partition[p1];
125 if (TREE_CODE (var2) == SSA_NAME)
126 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
129 p2 = var_to_partition (map, var2);
130 if (map->compact_to_partition)
131 p2 = map->compact_to_partition[p2];
133 /* If there is no root_var set, or it's not a user variable, set the
134 root_var to this one. */
135 if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
137 other_var = root_var;
144 gcc_assert (p1 != NO_PARTITION);
145 gcc_assert (p2 != NO_PARTITION);
150 p3 = partition_union (map->var_partition, p1, p2);
152 if (map->partition_to_compact)
153 p3 = map->partition_to_compact[p3];
156 change_partition_var (map, root_var, p3);
158 change_partition_var (map, other_var, p3);
164 /* Compress the partition numbers in MAP such that they fall in the range
165 0..(num_partitions-1) instead of wherever they turned out during
166 the partitioning exercise. This removes any references to unused
167 partitions, thereby allowing bitmaps and other vectors to be much
168 denser. Compression type is controlled by FLAGS.
170 This is implemented such that compaction doesn't affect partitioning.
171 Ie., once partitions are created and possibly merged, running one
172 or more different kind of compaction will not affect the partitions
173 themselves. Their index might change, but all the same variables will
174 still be members of the same partition group. This allows work on reduced
175 sets, and no loss of information when a larger set is later desired.
177 In particular, coalescing can work on partitions which have 2 or more
178 definitions, and then 'recompact' later to include all the single
179 definitions for assignment to program variables. */
182 compact_var_map (var_map map, int flags)
185 int tmp, root, root_i;
186 unsigned int x, limit, count;
188 root_var_p rv = NULL;
190 limit = map->partition_size;
191 used = sbitmap_alloc (limit);
194 /* Already compressed? Abandon the old one. */
195 if (map->partition_to_compact)
197 free (map->partition_to_compact);
198 map->partition_to_compact = NULL;
200 if (map->compact_to_partition)
202 free (map->compact_to_partition);
203 map->compact_to_partition = NULL;
206 map->num_partitions = map->partition_size;
208 if (flags & VARMAP_NO_SINGLE_DEFS)
209 rv = root_var_init (map);
211 map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
212 memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
214 /* Find out which partitions are actually referenced. */
216 for (x = 0; x < limit; x++)
218 tmp = partition_find (map->var_partition, x);
219 if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
221 /* It is referenced, check to see if there is more than one version
222 in the root_var table, if one is available. */
225 root = root_var_find (rv, tmp);
226 root_i = root_var_first_partition (rv, root);
227 /* If there is only one, don't include this in the compaction. */
228 if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE)
236 /* Build a compacted partitioning. */
239 sbitmap_iterator sbi;
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, sbi)
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;
286 static inline void mark_all_vars_used (tree *);
288 /* Helper function for mark_all_vars_used, called via walk_tree. */
291 mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
292 void *data ATTRIBUTE_UNUSED)
296 if (TREE_CODE (t) == SSA_NAME)
297 t = SSA_NAME_VAR (t);
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)
303 mark_all_vars_used (&TMR_SYMBOL (t));
304 mark_all_vars_used (&TMR_BASE (t));
305 mark_all_vars_used (&TMR_INDEX (t));
310 /* Only need to mark VAR_DECLS; parameters and return results are not
311 eliminated as unused. */
312 if (TREE_CODE (t) == VAR_DECL)
315 if (IS_TYPE_OR_DECL_P (t))
321 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
322 eliminated during the tree->rtl conversion process. */
325 mark_all_vars_used (tree *expr_p)
327 walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
331 /* Remove local variables that are not referenced in the IL. */
334 remove_unused_locals (void)
339 /* Assume all locals are unused. */
340 for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
342 tree var = TREE_VALUE (t);
343 if (TREE_CODE (var) != FUNCTION_DECL
345 var_ann (var)->used = false;
348 /* Walk the CFG marking all referenced symbols. */
351 block_stmt_iterator bsi;
354 /* Walk the statements. */
355 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
356 mark_all_vars_used (bsi_stmt_ptr (bsi));
358 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
363 /* No point processing globals. */
364 if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
367 def = PHI_RESULT (phi);
368 mark_all_vars_used (&def);
370 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
372 tree arg = USE_FROM_PTR (arg_p);
373 mark_all_vars_used (&arg);
378 /* Remove unmarked vars and clear used flag. */
379 for (cell = &cfun->unexpanded_var_list; *cell; )
381 tree var = TREE_VALUE (*cell);
384 if (TREE_CODE (var) != FUNCTION_DECL
385 && (!(ann = var_ann (var))
388 *cell = TREE_CHAIN (*cell);
392 cell = &TREE_CHAIN (*cell);
396 /* This function looks through the program and uses FLAGS to determine what
397 SSA versioned variables are given entries in a new partition table. This
398 new partition map is returned. */
401 create_ssa_var_map (void)
403 block_stmt_iterator bsi;
409 #ifdef ENABLE_CHECKING
410 bitmap used_in_real_ops;
411 bitmap used_in_virtual_ops;
414 map = init_var_map (num_ssa_names + 1);
416 #ifdef ENABLE_CHECKING
417 used_in_real_ops = BITMAP_ALLOC (NULL);
418 used_in_virtual_ops = BITMAP_ALLOC (NULL);
425 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
428 register_ssa_partition (map, PHI_RESULT (phi));
429 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
431 arg = PHI_ARG_DEF (phi, i);
432 if (TREE_CODE (arg) == SSA_NAME)
433 register_ssa_partition (map, arg);
435 mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
439 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
441 stmt = bsi_stmt (bsi);
443 /* Register USE and DEF operands in each statement. */
444 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
446 register_ssa_partition (map, var);
448 #ifdef ENABLE_CHECKING
449 bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var)));
453 #ifdef ENABLE_CHECKING
454 /* Validate that virtual ops don't get used in funny ways. */
455 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter,
456 SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
458 bitmap_set_bit (used_in_virtual_ops,
459 DECL_UID (SSA_NAME_VAR (var)));
462 #endif /* ENABLE_CHECKING */
464 mark_all_vars_used (bsi_stmt_ptr (bsi));
468 #if defined ENABLE_CHECKING
471 bitmap both = BITMAP_ALLOC (NULL);
472 bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
473 if (!bitmap_empty_p (both))
477 EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
478 fprintf (stderr, "Variable %s used in real and virtual operands\n",
479 get_name (referenced_var (i)));
480 internal_error ("SSA corruption");
483 BITMAP_FREE (used_in_real_ops);
484 BITMAP_FREE (used_in_virtual_ops);
493 /* Allocate and return a new live range information object base on MAP. */
495 static tree_live_info_p
496 new_tree_live_info (var_map map)
498 tree_live_info_p live;
501 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
503 live->num_blocks = last_basic_block;
505 live->global = BITMAP_ALLOC (NULL);
507 live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
508 for (x = 0; x < num_var_partitions (map); x++)
509 live->livein[x] = BITMAP_ALLOC (NULL);
511 /* liveout is deferred until it is actually requested. */
512 live->liveout = NULL;
517 /* Free storage for live range info object LIVE. */
520 delete_tree_live_info (tree_live_info_p live)
525 for (x = live->num_blocks - 1; x >= 0; x--)
526 BITMAP_FREE (live->liveout[x]);
527 free (live->liveout);
531 for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
532 BITMAP_FREE (live->livein[x]);
536 BITMAP_FREE (live->global);
542 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
543 for partition I. STACK is a varray used for temporary memory which is
544 passed in rather than being allocated on every call. */
547 live_worklist (tree_live_info_p live, int *stack, int i)
551 basic_block def_bb = NULL;
553 var_map map = live->map;
558 var = partition_to_var (map, i);
559 if (SSA_NAME_DEF_STMT (var))
560 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
562 EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
571 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
572 if (e->src != ENTRY_BLOCK_PTR)
574 /* Its not live on entry to the block its defined in. */
575 if (e->src == def_bb)
577 if (!bitmap_bit_p (live->livein[i], e->src->index))
579 bitmap_set_bit (live->livein[i], e->src->index);
580 *tos++ = e->src->index;
587 /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
590 set_if_valid (var_map map, bitmap vec, tree var)
592 int p = var_to_partition (map, var);
593 if (p != NO_PARTITION)
594 bitmap_set_bit (vec, p);
598 /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
599 global bit for it in the LIVE object. BB is the block being processed. */
602 add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
603 tree var, basic_block bb)
605 int p = var_to_partition (live->map, var);
606 if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
608 if (!bitmap_bit_p (def_vec, p))
610 bitmap_set_bit (live->livein[p], bb->index);
611 bitmap_set_bit (live->global, p);
616 /* Given partition map MAP, calculate all the live on entry bitmaps for
617 each basic block. Return a live info object. */
620 calculate_live_on_entry (var_map map)
622 tree_live_info_p live;
630 block_stmt_iterator bsi;
633 #ifdef ENABLE_CHECKING
638 saw_def = BITMAP_ALLOC (NULL);
640 live = new_tree_live_info (map);
644 bitmap_clear (saw_def);
646 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
648 for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
650 var = PHI_ARG_DEF (phi, i);
651 if (!phi_ssa_name_p (var))
653 stmt = SSA_NAME_DEF_STMT (var);
654 e = EDGE_PRED (bb, i);
656 /* Any uses in PHIs which either don't have def's or are not
657 defined in the block from which the def comes, will be live
658 on entry to that block. */
659 if (!stmt || e->src != bb_for_stmt (stmt))
660 add_livein_if_notdef (live, saw_def, var, e->src);
664 /* Don't mark PHI results as defined until all the PHI nodes have
665 been processed. If the PHI sequence is:
668 The a_3 referred to in b_3's PHI node is the one incoming on the
669 edge, *not* the PHI node just seen. */
671 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
673 var = PHI_RESULT (phi);
674 set_if_valid (map, saw_def, var);
677 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
679 stmt = bsi_stmt (bsi);
681 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
683 add_livein_if_notdef (live, saw_def, op, bb);
686 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
688 set_if_valid (map, saw_def, op);
693 stack = XNEWVEC (int, last_basic_block);
694 EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
696 live_worklist (live, stack, i);
700 #ifdef ENABLE_CHECKING
701 /* Check for live on entry partitions and report those with a DEF in
702 the program. This will typically mean an optimization has done
705 bb = ENTRY_BLOCK_PTR;
707 FOR_EACH_EDGE (e, ei, bb->succs)
709 int entry_block = e->dest->index;
710 if (e->dest == EXIT_BLOCK_PTR)
712 for (i = 0; i < (unsigned)num_var_partitions (map); i++)
716 var = partition_to_var (map, i);
717 stmt = SSA_NAME_DEF_STMT (var);
718 tmp = bb_for_stmt (stmt);
719 d = gimple_default_def (cfun, SSA_NAME_VAR (var));
721 if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
723 if (!IS_EMPTY_STMT (stmt))
726 print_generic_expr (stderr, var, TDF_SLIM);
727 fprintf (stderr, " is defined ");
729 fprintf (stderr, " in BB%d, ", tmp->index);
730 fprintf (stderr, "by:\n");
731 print_generic_expr (stderr, stmt, TDF_SLIM);
732 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
734 fprintf (stderr, " So it appears to have multiple defs.\n");
741 print_generic_expr (stderr, var, TDF_SLIM);
742 fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
745 fprintf (stderr, " but is not the default def of ");
746 print_generic_expr (stderr, d, TDF_SLIM);
747 fprintf (stderr, "\n");
750 fprintf (stderr, " and there is no default def.\n");
757 /* The only way this var shouldn't be marked live on entry is
758 if it occurs in a PHI argument of the block. */
760 for (phi = phi_nodes (e->dest);
762 phi = PHI_CHAIN (phi))
764 for (z = 0; z < PHI_NUM_ARGS (phi); z++)
765 if (var == PHI_ARG_DEF (phi, z))
774 print_generic_expr (stderr, var, TDF_SLIM);
775 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
777 fprintf (stderr, "but it is a default def so it should be.\n");
781 gcc_assert (num <= 0);
784 BITMAP_FREE (saw_def);
790 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
793 calculate_live_on_exit (tree_live_info_p liveinfo)
802 var_map map = liveinfo->map;
804 on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
805 for (x = 0; x < (unsigned)last_basic_block; x++)
806 on_exit[x] = BITMAP_ALLOC (NULL);
808 /* Set all the live-on-exit bits for uses in PHIs. */
811 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
812 for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
814 t = PHI_ARG_DEF (phi, i);
815 e = PHI_ARG_EDGE (phi, i);
816 if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
818 set_if_valid (map, on_exit[e->src->index], t);
822 /* Set live on exit for all predecessors of live on entry's. */
823 for (i = 0; i < num_var_partitions (map); i++)
827 on_entry = live_entry_blocks (liveinfo, i);
828 EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
831 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
832 if (e->src != ENTRY_BLOCK_PTR)
833 bitmap_set_bit (on_exit[e->src->index], i);
837 liveinfo->liveout = on_exit;
841 /* Initialize a tree_partition_associator object using MAP. */
844 tpa_init (var_map map)
847 int num_partitions = num_var_partitions (map);
850 if (num_partitions == 0)
853 tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
855 tpa->uncompressed_num = -1;
857 tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
858 memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
860 tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
861 memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
863 x = MAX (40, (num_partitions / 20));
864 tpa->trees = VEC_alloc (tree, heap, x);
865 tpa->first_partition = VEC_alloc (int, heap, x);
872 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
875 tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
879 i = tpa_first_partition (tpa, tree_index);
880 if (i == partition_index)
882 VEC_replace (int, tpa->first_partition, tree_index,
883 tpa->next_partition[i]);
887 for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
889 if (tpa->next_partition[i] == partition_index)
891 tpa->next_partition[i] = tpa->next_partition[partition_index];
899 /* Free the memory used by tree_partition_associator object TPA. */
902 tpa_delete (tpa_p tpa)
907 VEC_free (tree, heap, tpa->trees);
908 VEC_free (int, heap, tpa->first_partition);
909 free (tpa->partition_to_tree_map);
910 free (tpa->next_partition);
915 /* This function will remove any tree entries from TPA which have only a single
916 element. This will help keep the size of the conflict graph down. The
917 function returns the number of remaining tree lists. */
920 tpa_compact (tpa_p tpa)
922 int last, x, y, first, swap_i;
925 /* Find the last list which has more than 1 partition. */
926 for (last = tpa->num_trees - 1; last > 0; last--)
928 first = tpa_first_partition (tpa, last);
929 if (tpa_next_partition (tpa, first) != NO_PARTITION)
936 first = tpa_first_partition (tpa, x);
938 /* If there is not more than one partition, swap with the current end
940 if (tpa_next_partition (tpa, first) == NO_PARTITION)
942 swap_t = VEC_index (tree, tpa->trees, last);
943 swap_i = VEC_index (int, tpa->first_partition, last);
945 /* Update the last entry. Since it is known to only have one
946 partition, there is nothing else to update. */
947 VEC_replace (tree, tpa->trees, last,
948 VEC_index (tree, tpa->trees, x));
949 VEC_replace (int, tpa->first_partition, last,
950 VEC_index (int, tpa->first_partition, x));
951 tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
953 /* Since this list is known to have more than one partition, update
954 the list owner entries. */
955 VEC_replace (tree, tpa->trees, x, swap_t);
956 VEC_replace (int, tpa->first_partition, x, swap_i);
957 for (y = tpa_first_partition (tpa, x);
959 y = tpa_next_partition (tpa, y))
960 tpa->partition_to_tree_map[y] = x;
962 /* Ensure last is a list with more than one partition. */
964 for (; last > x; last--)
966 first = tpa_first_partition (tpa, last);
967 if (tpa_next_partition (tpa, first) != NO_PARTITION)
974 first = tpa_first_partition (tpa, x);
975 if (tpa_next_partition (tpa, first) != NO_PARTITION)
977 tpa->uncompressed_num = tpa->num_trees;
983 /* Initialize a root_var object with SSA partitions from MAP which are based
984 on each root variable. */
987 root_var_init (var_map map)
990 int num_partitions = num_var_partitions (map);
1000 seen = sbitmap_alloc (num_partitions);
1001 sbitmap_zero (seen);
1003 /* Start at the end and work towards the front. This will provide a list
1004 that is ordered from smallest to largest. */
1005 for (x = num_partitions - 1; x >= 0; x--)
1007 t = partition_to_var (map, x);
1009 /* The var map may not be compacted yet, so check for NULL. */
1013 p = var_to_partition (map, t);
1015 gcc_assert (p != NO_PARTITION);
1017 /* Make sure we only put coalesced partitions into the list once. */
1018 if (TEST_BIT (seen, p))
1021 if (TREE_CODE (t) == SSA_NAME)
1022 t = SSA_NAME_VAR (t);
1024 if (ann->root_var_processed)
1026 rv->next_partition[p] = VEC_index (int, rv->first_partition,
1027 VAR_ANN_ROOT_INDEX (ann));
1028 VEC_replace (int, rv->first_partition, VAR_ANN_ROOT_INDEX (ann), p);
1032 ann->root_var_processed = 1;
1033 VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
1034 VEC_safe_push (tree, heap, rv->trees, t);
1035 VEC_safe_push (int, heap, rv->first_partition, p);
1037 rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
1040 /* Reset the out_of_ssa_tag flag on each variable for later use. */
1041 for (x = 0; x < rv->num_trees; x++)
1043 t = VEC_index (tree, rv->trees, x);
1044 var_ann (t)->root_var_processed = 0;
1047 sbitmap_free (seen);
1052 /* Hash function for 2 integer coalesce pairs. */
1053 #define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
1056 /* Return hash value for partition pair PAIR. */
1059 partition_pair_map_hash (const void *pair)
1061 hashval_t a = (hashval_t)(((partition_pair_p)pair)->first_partition);
1062 hashval_t b = (hashval_t)(((partition_pair_p)pair)->second_partition);
1064 return COALESCE_HASH_FN (a,b);
1068 /* Return TRUE if PAIR1 is equivilent to PAIR2. */
1071 partition_pair_map_eq (const void *pair1, const void *pair2)
1073 partition_pair_p p1 = (partition_pair_p) pair1;
1074 partition_pair_p p2 = (partition_pair_p) pair2;
1076 return (p1->first_partition == p2->first_partition
1077 && p1->second_partition == p2->second_partition);
1081 /* Create a new coalesce list object from MAP and return it. */
1084 create_coalesce_list (var_map map)
1086 coalesce_list_p list;
1087 unsigned size = num_ssa_names * 3;
1092 list = xmalloc (sizeof (struct coalesce_list_d));
1093 list->list = htab_create (size, partition_pair_map_hash,
1094 partition_pair_map_eq, NULL);
1097 list->sorted = NULL;
1098 list->add_mode = true;
1099 list->num_sorted = 0;
1104 /* Delete coalesce list CL. */
1107 delete_coalesce_list (coalesce_list_p cl)
1109 htab_delete (cl->list);
1112 gcc_assert (cl->num_sorted == 0);
1117 /* Find a matching coalesce pair object in CL for partitions P1 and P2. If
1118 one isn't found, return NULL if CREATE is false, otherwise create a new
1119 coalesce pair object and return it. */
1121 static partition_pair_p
1122 find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
1124 struct partition_pair p, *pair;
1128 /* normalize so that p1 is the smaller value. */
1131 p.first_partition = p2;
1132 p.second_partition = p1;
1136 p.first_partition = p1;
1137 p.second_partition = p2;
1141 hash = partition_pair_map_hash (&p);
1142 pair = (struct partition_pair *) htab_find_with_hash (cl->list, &p, hash);
1144 if (create && !pair)
1146 gcc_assert (cl->add_mode);
1147 pair = xmalloc (sizeof (struct partition_pair));
1148 pair->first_partition = p.first_partition;
1149 pair->second_partition = p.second_partition;
1151 slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT);
1152 *(struct partition_pair **)slot = pair;
1158 /* Return cost of execution of copy instruction with FREQUENCY
1159 possibly on CRITICAL edge and in HOT basic block. */
1161 coalesce_cost (int frequency, bool hot, bool critical)
1163 /* Base costs on BB frequencies bounded by 1. */
1164 int cost = frequency;
1168 if (optimize_size || hot)
1170 /* Inserting copy on critical edge costs more
1171 than inserting it elsewhere. */
1177 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
1180 add_coalesce (coalesce_list_p cl, int p1, int p2,
1183 partition_pair_p node;
1185 gcc_assert (cl->add_mode);
1190 node = find_partition_pair (cl, p1, p2, true);
1192 node->cost += value;
1196 /* Comparison function to allow qsort to sort P1 and P2 in Ascendiong order. */
1199 int compare_pairs (const void *p1, const void *p2)
1201 return (*(partition_pair_p *)p1)->cost - (*(partition_pair_p *)p2)->cost;
1206 num_coalesce_pairs (coalesce_list_p cl)
1208 return htab_elements (cl->list);
1214 } partition_pair_iterator;
1216 static inline partition_pair_p
1217 first_partition_pair (coalesce_list_p cl, partition_pair_iterator *iter)
1219 partition_pair_p pair;
1221 pair = (partition_pair_p) first_htab_element (&(iter->hti), cl->list);
1226 end_partition_pair_p (partition_pair_iterator *iter)
1228 return end_htab_p (&(iter->hti));
1231 static inline partition_pair_p
1232 next_partition_pair (partition_pair_iterator *iter)
1234 partition_pair_p pair;
1236 pair = (partition_pair_p) next_htab_element (&(iter->hti));
1240 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
1241 for ((PAIR) = first_partition_pair ((CL), &(ITER)); \
1242 !end_partition_pair_p (&(ITER)); \
1243 (PAIR) = next_partition_pair (&(ITER)))
1246 /* Prepare CL for removal of preferred pairs. When finished, list element
1247 0 has all the coalesce pairs, sorted in order from most important coalesce
1248 to least important. */
1251 sort_coalesce_list (coalesce_list_p cl)
1255 partition_pair_iterator ppi;
1257 gcc_assert (cl->add_mode);
1259 cl->add_mode = false;
1261 /* allocate a vector for the pair pointers. */
1262 num = num_coalesce_pairs (cl);
1263 cl->num_sorted = num;
1266 cl->sorted = XNEWVEC (partition_pair_p, num);
1268 /* Populate the vector with pointers to the partition pairs. */
1271 FOR_EACH_PARTITION_PAIR (p, ppi, cl)
1272 cl->sorted[x++] = p;
1273 gcc_assert (x == num);
1280 if (cl->sorted[0]->cost > cl->sorted[1]->cost)
1283 cl->sorted[0] = cl->sorted[1];
1289 /* Only call qsort if there are more than 2 items. */
1291 qsort (cl->sorted, num, sizeof (partition_pair_p), compare_pairs);
1295 /* Retrieve the best remaining pair to coalesce from CL. Returns the 2
1296 partitions via P1 and P2. Their calculated cost is returned by the function.
1297 NO_BEST_COALESCE is returned if the coalesce list is empty. */
1300 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
1302 partition_pair_p node;
1305 gcc_assert (!cl->add_mode);
1307 if (cl->num_sorted == 0)
1308 return NO_BEST_COALESCE;
1310 node = cl->sorted[--(cl->num_sorted)];
1312 *p1 = node->first_partition;
1313 *p2 = node->second_partition;
1321 /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
1322 VAR and any other live partitions in VEC which are associated via TPA.
1323 Reset the live bit in VEC. */
1326 add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
1327 var_map map, bitmap vec, tree var)
1330 p = var_to_partition (map, var);
1331 if (p != NO_PARTITION)
1333 bitmap_clear_bit (vec, p);
1334 first = tpa_find_tree (tpa, p);
1335 /* If find returns nothing, this object isn't interesting. */
1336 if (first == TPA_NONE)
1338 /* Only add interferences between objects in the same list. */
1339 for (y = tpa_first_partition (tpa, first);
1341 y = tpa_next_partition (tpa, y))
1343 if (bitmap_bit_p (vec, y))
1344 conflict_graph_add (graph, p, y);
1349 /* Return a conflict graph for the information contained in LIVE_INFO. Only
1350 conflicts between items in the same TPA list are added. If optional
1351 coalesce list CL is passed in, any copies encountered are added. */
1354 build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
1357 conflict_graph graph;
1362 int *partition_link, *tpa_nodes;
1363 VEC(int,heap) *tpa_to_clear;
1368 map = live_var_map (liveinfo);
1369 graph = conflict_graph_new (num_var_partitions (map));
1371 if (tpa_num_trees (tpa) == 0)
1374 live = BITMAP_ALLOC (NULL);
1376 partition_link = XCNEWVEC (int, num_var_partitions (map) + 1);
1377 tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa));
1378 tpa_to_clear = VEC_alloc (int, heap, 50);
1382 block_stmt_iterator bsi;
1386 /* Start with live on exit temporaries. */
1387 bitmap_copy (live, live_on_exit (liveinfo, bb));
1389 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1391 bool is_a_copy = false;
1392 tree stmt = bsi_stmt (bsi);
1394 /* A copy between 2 partitions does not introduce an interference
1395 by itself. If they did, you would never be able to coalesce
1396 two things which are copied. If the two variables really do
1397 conflict, they will conflict elsewhere in the program.
1399 This is handled specially here since we may also be interested
1400 in copies between real variables and SSA_NAME variables. We may
1401 be interested in trying to coalesce SSA_NAME variables with
1402 root variables in some cases. */
1404 if (TREE_CODE (stmt) == MODIFY_EXPR)
1406 tree lhs = TREE_OPERAND (stmt, 0);
1407 tree rhs = TREE_OPERAND (stmt, 1);
1411 if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
1412 p1 = var_to_partition (map, lhs);
1416 if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
1417 p2 = var_to_partition (map, rhs);
1421 if (p1 != NO_PARTITION && p2 != NO_PARTITION)
1424 bit = bitmap_bit_p (live, p2);
1425 /* If the RHS is live, make it not live while we add
1426 the conflicts, then make it live again. */
1428 bitmap_clear_bit (live, p2);
1429 add_conflicts_if_valid (tpa, graph, map, live, lhs);
1431 bitmap_set_bit (live, p2);
1433 add_coalesce (cl, p1, p2,
1434 coalesce_cost (bb->frequency,
1435 maybe_hot_bb_p (bb), false));
1436 set_if_valid (map, live, rhs);
1443 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
1445 add_conflicts_if_valid (tpa, graph, map, live, var);
1448 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1450 set_if_valid (map, live, var);
1455 /* If result of a PHI is unused, then the loops over the statements
1456 will not record any conflicts. However, since the PHI node is
1457 going to be translated out of SSA form we must record a conflict
1458 between the result of the PHI and any variables with are live.
1459 Otherwise the out-of-ssa translation may create incorrect code. */
1460 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1462 tree result = PHI_RESULT (phi);
1463 int p = var_to_partition (map, result);
1465 if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
1466 add_conflicts_if_valid (tpa, graph, map, live, result);
1469 /* Anything which is still live at this point interferes.
1470 In order to implement this efficiently, only conflicts between
1471 partitions which have the same TPA root need be added.
1472 TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
1473 entry points to an index into 'partition_link', which then indexes
1474 into itself forming a linked list of partitions sharing a tpa root
1475 which have been seen as live up to this point. Since partitions start
1476 at index zero, all entries in partition_link are (partition + 1).
1478 Conflicts are added between the current partition and any already seen.
1479 tpa_clear contains all the tpa_roots processed, and these are the only
1480 entries which need to be zero'd out for a clean restart. */
1482 EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
1484 i = tpa_find_tree (tpa, x);
1485 if (i != (unsigned)TPA_NONE)
1487 int start = tpa_nodes[i];
1488 /* If start is 0, a new root reference list is being started.
1489 Register it to be cleared. */
1491 VEC_safe_push (int, heap, tpa_to_clear, i);
1493 /* Add interferences to other tpa members seen. */
1494 for (y = start; y != 0; y = partition_link[y])
1495 conflict_graph_add (graph, x, y - 1);
1496 tpa_nodes[i] = x + 1;
1497 partition_link[x + 1] = start;
1501 /* Now clear the used tpa root references. */
1502 for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++)
1504 VEC_truncate (int, tpa_to_clear, 0);
1508 free (partition_link);
1509 VEC_free (int, heap, tpa_to_clear);
1515 /* This routine will attempt to coalesce the elements in TPA subject to the
1516 conflicts found in GRAPH. If optional coalesce_list CL is provided,
1517 only coalesces specified within the coalesce list are attempted. Otherwise
1518 an attempt is made to coalesce as many partitions within each TPA grouping
1519 as possible. If DEBUG is provided, debug output will be sent there. */
1522 coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
1523 coalesce_list_p cl, FILE *debug)
1528 /* Attempt to coalesce any items in a coalesce list. */
1531 while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
1535 fprintf (debug, "Coalesce list: (%d)", x);
1536 print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
1537 fprintf (debug, " & (%d)", y);
1538 print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
1541 w = tpa_find_tree (tpa, x);
1542 z = tpa_find_tree (tpa, y);
1543 if (w != z || w == TPA_NONE || z == TPA_NONE)
1548 fprintf (debug, ": Fail, Non-matching TPA's\n");
1550 fprintf (debug, ": Fail %d non TPA.\n", x);
1552 fprintf (debug, ": Fail %d non TPA.\n", y);
1556 var = partition_to_var (map, x);
1557 tmp = partition_to_var (map, y);
1558 x = var_to_partition (map, var);
1559 y = var_to_partition (map, tmp);
1561 fprintf (debug, " [map: %d, %d] ", x, y);
1565 fprintf (debug, ": Already Coalesced.\n");
1568 if (!conflict_graph_conflict_p (graph, x, y))
1570 z = var_union (map, var, tmp);
1571 if (z == NO_PARTITION)
1574 fprintf (debug, ": Unable to perform partition union.\n");
1578 /* z is the new combined partition. We need to remove the other
1579 partition from the list. Set x to be that other partition. */
1582 conflict_graph_merge_regs (graph, x, y);
1583 w = tpa_find_tree (tpa, y);
1584 tpa_remove_partition (tpa, w, y);
1588 conflict_graph_merge_regs (graph, y, x);
1589 w = tpa_find_tree (tpa, x);
1590 tpa_remove_partition (tpa, w, x);
1594 fprintf (debug, ": Success -> %d\n", z);
1598 fprintf (debug, ": Fail due to conflict\n");
1600 /* If using a coalesce list, don't try to coalesce anything else. */
1604 for (x = 0; x < tpa_num_trees (tpa); x++)
1606 while (tpa_first_partition (tpa, x) != TPA_NONE)
1609 /* Coalesce first partition with anything that doesn't conflict. */
1610 y = tpa_first_partition (tpa, x);
1611 tpa_remove_partition (tpa, x, y);
1613 var = partition_to_var (map, y);
1614 /* p1 is the partition representative to which y belongs. */
1615 p1 = var_to_partition (map, var);
1617 for (z = tpa_next_partition (tpa, y);
1619 z = tpa_next_partition (tpa, z))
1621 tmp = partition_to_var (map, z);
1622 /* p2 is the partition representative to which z belongs. */
1623 p2 = var_to_partition (map, tmp);
1626 fprintf (debug, "Coalesce : ");
1627 print_generic_expr (debug, var, TDF_SLIM);
1628 fprintf (debug, " &");
1629 print_generic_expr (debug, tmp, TDF_SLIM);
1630 fprintf (debug, " (%d ,%d)", p1, p2);
1633 /* If partitions are already merged, don't check for conflict. */
1636 tpa_remove_partition (tpa, x, z);
1638 fprintf (debug, ": Already coalesced\n");
1641 if (!conflict_graph_conflict_p (graph, p1, p2))
1644 if (tpa_find_tree (tpa, y) == TPA_NONE
1645 || tpa_find_tree (tpa, z) == TPA_NONE)
1648 fprintf (debug, ": Fail non-TPA member\n");
1651 if ((v = var_union (map, var, tmp)) == NO_PARTITION)
1654 fprintf (debug, ": Fail cannot combine partitions\n");
1658 tpa_remove_partition (tpa, x, z);
1660 conflict_graph_merge_regs (graph, v, z);
1663 /* Update the first partition's representative. */
1664 conflict_graph_merge_regs (graph, v, y);
1668 /* The root variable of the partition may be changed
1670 var = partition_to_var (map, p1);
1673 fprintf (debug, ": Success -> %d\n", v);
1677 fprintf (debug, ": Fail, Conflict\n");
1684 /* Send debug info for coalesce list CL to file F. */
1687 dump_coalesce_list (FILE *f, coalesce_list_p cl)
1689 partition_pair_p node;
1690 partition_pair_iterator ppi;
1696 fprintf (f, "Coalesce List:\n");
1697 FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1699 tree var1 = partition_to_var (cl->map, node->first_partition);
1700 tree var2 = partition_to_var (cl->map, node->second_partition);
1701 print_generic_expr (f, var1, TDF_SLIM);
1702 fprintf (f, " <-> ");
1703 print_generic_expr (f, var2, TDF_SLIM);
1704 fprintf (f, " (%1d), ", node->cost);
1710 fprintf (f, "Sorted Coalesce list:\n");
1711 for (x = cl->num_sorted - 1 ; x >=0; x--)
1713 node = cl->sorted[x];
1714 fprintf (f, "(%d) ", node->cost);
1715 var = partition_to_var (cl->map, node->first_partition);
1716 print_generic_expr (f, var, TDF_SLIM);
1717 fprintf (f, " <-> ");
1718 var = partition_to_var (cl->map, node->second_partition);
1719 print_generic_expr (f, var, TDF_SLIM);
1726 /* Output tree_partition_associator object TPA to file F.. */
1729 tpa_dump (FILE *f, tpa_p tpa)
1736 for (x = 0; x < tpa_num_trees (tpa); x++)
1738 print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
1739 fprintf (f, " : (");
1740 for (i = tpa_first_partition (tpa, x);
1742 i = tpa_next_partition (tpa, i))
1744 fprintf (f, "(%d)",i);
1745 print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
1748 #ifdef ENABLE_CHECKING
1749 if (tpa_find_tree (tpa, i) != x)
1750 fprintf (f, "**find tree incorrectly set** ");
1760 /* Output partition map MAP to file F. */
1763 dump_var_map (FILE *f, var_map map)
1769 fprintf (f, "\nPartition map \n\n");
1771 for (x = 0; x < map->num_partitions; x++)
1773 if (map->compact_to_partition != NULL)
1774 p = map->compact_to_partition[x];
1778 if (map->partition_to_var[p] == NULL_TREE)
1782 for (y = 1; y < num_ssa_names; y++)
1784 p = partition_find (map->var_partition, y);
1785 if (map->partition_to_compact)
1786 p = map->partition_to_compact[p];
1791 fprintf(f, "Partition %d (", x);
1792 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1795 fprintf (f, "%d ", y);
1805 /* Output live range info LIVE to file F, controlled by FLAG. */
1808 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1812 var_map map = live->map;
1815 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1819 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1820 for (i = 0; i < num_var_partitions (map); i++)
1822 if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
1824 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1832 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1836 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1837 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1839 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1847 #ifdef ENABLE_CHECKING
1849 register_ssa_partition_check (tree ssa_var)
1851 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1852 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1854 fprintf (stderr, "Illegally registering a virtual SSA name :");
1855 print_generic_expr (stderr, ssa_var, TDF_SLIM);
1856 fprintf (stderr, " in the SSA->Normal phase.\n");
1857 internal_error ("SSA corruption");