1 /* Liveness for SSA trees.
2 Copyright (C) 2003 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"
37 #include "tree-alias-common.h"
39 #include "tree-dump.h"
40 #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 its not a user variable, set the
137 root_var to this one. */
139 || (TREE_CODE (root_var) == VAR_DECL && DECL_ARTIFICIAL (root_var)))
141 other_var = root_var;
148 if (p1 == NO_PARTITION || p2 == NO_PARTITION)
154 p3 = partition_union (map->var_partition, p1, p2);
156 if (map->partition_to_compact)
157 p3 = map->partition_to_compact[p3];
160 change_partition_var (map, root_var, p3);
162 change_partition_var (map, other_var, p3);
168 /* Compress the partition numbers in MAP such that they fall in the range
169 0..(num_partitions-1) instead of wherever they turned out during
170 the partitioning exercise. This removes any references to unused
171 partitions, thereby allowing bitmaps and other vectors to be much
172 denser. Compression type is controlled by FLAGS.
174 This is implemented such that compaction doesn't affect partitioning.
175 Ie., once partitions are created and possibly merged, running one
176 or more different kind of compaction will not affect the partitions
177 themselves. Their index might change, but all the same variables will
178 still be members of the same partition group. This allows work on reduced
179 sets, and no loss of information when a larger set is later desired.
181 In particular, coalescing can work on partitions which have 2 or more
182 definitions, and then 'recompact' later to include all the single
183 definitions for assignment to program variables. */
186 compact_var_map (var_map map, int flags)
189 int x, limit, count, tmp, root, root_i;
191 root_var_p rv = NULL;
193 limit = map->partition_size;
194 used = sbitmap_alloc (limit);
197 /* Already compressed? Abandon the old one. */
198 if (map->partition_to_compact)
200 free (map->partition_to_compact);
201 map->partition_to_compact = NULL;
203 if (map->compact_to_partition)
205 free (map->compact_to_partition);
206 map->compact_to_partition = NULL;
209 map->num_partitions = map->partition_size;
211 if (flags & VARMAP_NO_SINGLE_DEFS)
212 rv = root_var_init (map);
214 map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
215 memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
217 /* Find out which partitions are actually referenced. */
219 for (x = 0; x < limit; x++)
221 tmp = partition_find (map->var_partition, x);
222 if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
224 /* It is referenced, check to see if there is more than one version
225 in the root_var table, if one is available. */
228 root = root_var_find (rv, tmp);
229 root_i = root_var_first_partition (rv, root);
230 /* If there is only one, don't include this in the compaction. */
231 if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE)
239 /* Build a compacted partitioning. */
242 map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
244 /* SSA renaming begins at 1, so skip 0 when compacting. */
245 EXECUTE_IF_SET_IN_SBITMAP (used, 1, x,
247 map->partition_to_compact[x] = count;
248 map->compact_to_partition[count] = x;
249 var = map->partition_to_var[x];
250 if (TREE_CODE (var) != SSA_NAME)
251 change_partition_var (map, var, count);
257 free (map->partition_to_compact);
258 map->partition_to_compact = NULL;
261 map->num_partitions = count;
264 root_var_delete (rv);
269 /* This function is used to change the representative variable in MAP for VAR's
270 partition from an SSA_NAME variable to a regular variable. This allows
271 partitions to be mapped back to real variables. */
274 change_partition_var (var_map map, tree var, int part)
278 if (TREE_CODE (var) == SSA_NAME)
282 ann->out_of_ssa_tag = 1;
283 VAR_ANN_PARTITION (ann) = part;
284 if (map->compact_to_partition)
285 map->partition_to_var[map->compact_to_partition[part]] = var;
289 /* Helper function for mark_all_vars_used, called via walk_tree. */
292 mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
293 void *data ATTRIBUTE_UNUSED)
297 /* Only need to mark VAR_DECLS; parameters and return results are not
298 eliminated as unused. */
299 if (TREE_CODE (t) == VAR_DECL)
302 if (DECL_P (t) || TYPE_P (t))
308 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
309 eliminated during the tree->rtl conversion process. */
312 mark_all_vars_used (tree *expr_p)
314 walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
317 /* This function looks through the program and uses FLAGS to determine what
318 SSA versioned variables are given entries in a new partition table. This
319 new partition map is returned. */
322 create_ssa_var_map (int flags)
324 block_stmt_iterator bsi;
333 #ifdef ENABLE_CHECKING
334 sbitmap used_in_real_ops;
335 sbitmap used_in_virtual_ops;
337 v_may_def_optype v_may_defs;
338 v_must_def_optype v_must_defs;
341 map = init_var_map (num_ssa_names + 1);
343 #ifdef ENABLE_CHECKING
344 used_in_real_ops = sbitmap_alloc (num_referenced_vars);
345 sbitmap_zero (used_in_real_ops);
347 used_in_virtual_ops = sbitmap_alloc (num_referenced_vars);
348 sbitmap_zero (used_in_virtual_ops);
351 if (flags & SSA_VAR_MAP_REF_COUNT)
354 = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
355 memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
361 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
364 register_ssa_partition (map, PHI_RESULT (phi), false);
365 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
367 arg = PHI_ARG_DEF (phi, i);
368 if (TREE_CODE (arg) == SSA_NAME)
369 register_ssa_partition (map, arg, true);
371 mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
375 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
377 stmt = bsi_stmt (bsi);
378 get_stmt_operands (stmt);
379 ann = stmt_ann (stmt);
381 /* Register USE and DEF operands in each statement. */
382 uses = USE_OPS (ann);
383 for (x = 0; x < NUM_USES (uses); x++)
385 use = USE_OP (uses, x);
386 register_ssa_partition (map, use, true);
388 #ifdef ENABLE_CHECKING
389 SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (use))->uid);
393 defs = DEF_OPS (ann);
394 for (x = 0; x < NUM_DEFS (defs); x++)
396 dest = DEF_OP (defs, x);
397 register_ssa_partition (map, dest, false);
399 #ifdef ENABLE_CHECKING
400 SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (dest))->uid);
404 #ifdef ENABLE_CHECKING
405 /* Validate that virtual ops don't get used in funny ways. */
406 vuses = VUSE_OPS (ann);
407 for (x = 0; x < NUM_VUSES (vuses); x++)
409 tree var = VUSE_OP (vuses, x);
410 SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid);
413 v_may_defs = V_MAY_DEF_OPS (ann);
414 for (x = 0; x < NUM_V_MAY_DEFS (v_may_defs); x++)
416 tree var = V_MAY_DEF_OP (v_may_defs, x);
417 SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid);
420 v_must_defs = V_MUST_DEF_OPS (ann);
421 for (x = 0; x < NUM_V_MUST_DEFS (v_must_defs); x++)
423 tree var = V_MUST_DEF_OP (v_must_defs, x);
424 SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid);
426 #endif /* ENABLE_CHECKING */
428 mark_all_vars_used (bsi_stmt_ptr (bsi));
432 #if defined ENABLE_CHECKING
435 sbitmap both = sbitmap_alloc (num_referenced_vars);
436 sbitmap_a_and_b (both, used_in_real_ops, used_in_virtual_ops);
437 if (sbitmap_first_set_bit (both) >= 0)
439 EXECUTE_IF_SET_IN_SBITMAP (both, 0, i,
440 fprintf (stderr, "Variable %s used in real and virtual operands\n",
441 get_name (referenced_var (i))));
445 sbitmap_free (used_in_real_ops);
446 sbitmap_free (used_in_virtual_ops);
455 /* Allocate and return a new live range information object base on MAP. */
457 static tree_live_info_p
458 new_tree_live_info (var_map map)
460 tree_live_info_p live;
463 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
465 live->num_blocks = last_basic_block;
467 live->global = BITMAP_XMALLOC ();
469 live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
470 for (x = 0; x < num_var_partitions (map); x++)
471 live->livein[x] = BITMAP_XMALLOC ();
473 /* liveout is deferred until it is actually requested. */
474 live->liveout = NULL;
479 /* Free storage for live range info object LIVE. */
482 delete_tree_live_info (tree_live_info_p live)
487 for (x = live->num_blocks - 1; x >= 0; x--)
488 BITMAP_XFREE (live->liveout[x]);
489 free (live->liveout);
493 for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
494 BITMAP_XFREE (live->livein[x]);
498 BITMAP_XFREE (live->global);
504 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
505 for partition I. STACK is a varray used for temporary memory which is
506 passed in rather than being allocated on every call. */
509 live_worklist (tree_live_info_p live, varray_type stack, int i)
513 basic_block def_bb = NULL;
515 var_map map = live->map;
517 var = partition_to_var (map, i);
518 if (SSA_NAME_DEF_STMT (var))
519 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
521 EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b,
523 VARRAY_PUSH_INT (stack, b);
526 while (VARRAY_ACTIVE_SIZE (stack) > 0)
528 b = VARRAY_TOP_INT (stack);
531 for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
532 if (e->src != ENTRY_BLOCK_PTR)
534 /* Its not live on entry to the block its defined in. */
535 if (e->src == def_bb)
537 if (!bitmap_bit_p (live->livein[i], e->src->index))
539 bitmap_set_bit (live->livein[i], e->src->index);
540 VARRAY_PUSH_INT (stack, e->src->index);
547 /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
550 set_if_valid (var_map map, bitmap vec, tree var)
552 int p = var_to_partition (map, var);
553 if (p != NO_PARTITION)
554 bitmap_set_bit (vec, p);
558 /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
559 global bit for it in the LIVE object. BB is the block being processed. */
562 add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
563 tree var, basic_block bb)
565 int p = var_to_partition (live->map, var);
566 if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
568 if (!bitmap_bit_p (def_vec, p))
570 bitmap_set_bit (live->livein[p], bb->index);
571 bitmap_set_bit (live->global, p);
576 /* Given partition map MAP, calculate all the live on entry bitmaps for
577 each basic block. Return a live info object. */
580 calculate_live_on_entry (var_map map)
582 tree_live_info_p live;
590 block_stmt_iterator bsi;
595 saw_def = BITMAP_XMALLOC ();
597 live = new_tree_live_info (map);
601 bitmap_clear (saw_def);
603 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
605 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
607 var = PHI_ARG_DEF (phi, i);
608 if (!phi_ssa_name_p (var))
610 stmt = SSA_NAME_DEF_STMT (var);
611 e = PHI_ARG_EDGE (phi, i);
613 /* Any uses in PHIs which either don't have def's or are not
614 defined in the block from which the def comes, will be live
615 on entry to that block. */
616 if (!stmt || e->src != bb_for_stmt (stmt))
617 add_livein_if_notdef (live, saw_def, var, e->src);
621 /* Don't mark PHI results as defined until all the PHI nodes have
622 been processed. If the PHI sequence is:
625 The a_3 referred to in b_3's PHI node is the one incoming on the
626 edge, *not* the PHI node just seen. */
628 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
630 var = PHI_RESULT (phi);
631 set_if_valid (map, saw_def, var);
634 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
636 stmt = bsi_stmt (bsi);
637 get_stmt_operands (stmt);
638 ann = stmt_ann (stmt);
640 uses = USE_OPS (ann);
641 num = NUM_USES (uses);
642 for (i = 0; i < num; i++)
644 op = USE_OP (uses, i);
645 add_livein_if_notdef (live, saw_def, op, bb);
648 defs = DEF_OPS (ann);
649 num = NUM_DEFS (defs);
650 for (i = 0; i < num; i++)
652 op = DEF_OP (defs, i);
653 set_if_valid (map, saw_def, op);
658 VARRAY_INT_INIT (stack, last_basic_block, "stack");
659 EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i,
661 live_worklist (live, stack, i);
664 #ifdef ENABLE_CHECKING
665 /* Check for live on entry partitions and report those with a DEF in
666 the program. This will typically mean an optimization has done
669 bb = ENTRY_BLOCK_PTR;
671 for (e = bb->succ; e; e = e->succ_next)
673 int entry_block = e->dest->index;
674 if (e->dest == EXIT_BLOCK_PTR)
676 for (i = 0; i < num_var_partitions (map); i++)
680 var = partition_to_var (map, i);
681 stmt = SSA_NAME_DEF_STMT (var);
682 tmp = bb_for_stmt (stmt);
683 d = default_def (SSA_NAME_VAR (var));
685 if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
687 if (!IS_EMPTY_STMT (stmt))
690 print_generic_expr (stderr, var, TDF_SLIM);
691 fprintf (stderr, " is defined ");
693 fprintf (stderr, " in BB%d, ", tmp->index);
694 fprintf (stderr, "by:\n");
695 print_generic_expr (stderr, stmt, TDF_SLIM);
696 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
698 fprintf (stderr, " So it appears to have multiple defs.\n");
705 print_generic_expr (stderr, var, TDF_SLIM);
706 fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
709 fprintf (stderr, " but is not the default def of ");
710 print_generic_expr (stderr, d, TDF_SLIM);
711 fprintf (stderr, "\n");
714 fprintf (stderr, " and there is no default def.\n");
721 /* The only way this var shouldn't be marked live on entry is
722 if it occurs in a PHI argument of the block. */
724 for (phi = phi_nodes (e->dest);
726 phi = PHI_CHAIN (phi))
728 for (z = 0; z < PHI_NUM_ARGS (phi); z++)
729 if (var == PHI_ARG_DEF (phi, z))
738 print_generic_expr (stderr, var, TDF_SLIM);
739 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
741 fprintf (stderr, "but it is a default def so it should be.\n");
749 BITMAP_XFREE (saw_def);
755 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
758 calculate_live_on_exit (tree_live_info_p liveinfo)
767 var_map map = liveinfo->map;
769 on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
770 for (x = 0; x < last_basic_block; x++)
771 on_exit[x] = BITMAP_XMALLOC ();
773 /* Set all the live-on-exit bits for uses in PHIs. */
776 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
777 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
779 t = PHI_ARG_DEF (phi, i);
780 e = PHI_ARG_EDGE (phi, i);
781 if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
783 set_if_valid (map, on_exit[e->src->index], t);
787 /* Set live on exit for all predecessors of live on entry's. */
788 for (i = 0; i < num_var_partitions (map); i++)
790 on_entry = live_entry_blocks (liveinfo, i);
791 EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b,
793 for (e = BASIC_BLOCK(b)->pred; e; e = e->pred_next)
794 if (e->src != ENTRY_BLOCK_PTR)
795 bitmap_set_bit (on_exit[e->src->index], i);
799 liveinfo->liveout = on_exit;
803 /* Initialize a tree_partition_associator object using MAP. */
806 tpa_init (var_map map)
809 int num_partitions = num_var_partitions (map);
812 if (num_partitions == 0)
815 tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
817 tpa->uncompressed_num = -1;
819 tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
820 memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
822 tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
823 memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
825 x = MAX (40, (num_partitions / 20));
826 VARRAY_TREE_INIT (tpa->trees, x, "trees");
827 VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
834 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
837 tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
841 i = tpa_first_partition (tpa, tree_index);
842 if (i == partition_index)
844 VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i];
848 for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
850 if (tpa->next_partition[i] == partition_index)
852 tpa->next_partition[i] = tpa->next_partition[partition_index];
860 /* Free the memory used by tree_partition_associator object TPA. */
863 tpa_delete (tpa_p tpa)
868 free (tpa->partition_to_tree_map);
869 free (tpa->next_partition);
874 /* This function will remove any tree entries from TPA which have only a single
875 element. This will help keep the size of the conflict graph down. The
876 function returns the number of remaining tree lists. */
879 tpa_compact (tpa_p tpa)
881 int last, x, y, first, swap_i;
884 /* Find the last list which has more than 1 partition. */
885 for (last = tpa->num_trees - 1; last > 0; last--)
887 first = tpa_first_partition (tpa, last);
888 if (tpa_next_partition (tpa, first) != NO_PARTITION)
895 first = tpa_first_partition (tpa, x);
897 /* If there is not more than one partition, swap with the current end
899 if (tpa_next_partition (tpa, first) == NO_PARTITION)
901 swap_t = VARRAY_TREE (tpa->trees, last);
902 swap_i = VARRAY_INT (tpa->first_partition, last);
904 /* Update the last entry. Since it is known to only have one
905 partition, there is nothing else to update. */
906 VARRAY_TREE (tpa->trees, last) = VARRAY_TREE (tpa->trees, x);
907 VARRAY_INT (tpa->first_partition, last)
908 = VARRAY_INT (tpa->first_partition, x);
909 tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
911 /* Since this list is known to have more than one partition, update
912 the list owner entries. */
913 VARRAY_TREE (tpa->trees, x) = swap_t;
914 VARRAY_INT (tpa->first_partition, x) = swap_i;
915 for (y = tpa_first_partition (tpa, x);
917 y = tpa_next_partition (tpa, y))
918 tpa->partition_to_tree_map[y] = x;
920 /* Ensure last is a list with more than one partition. */
922 for (; last > x; last--)
924 first = tpa_first_partition (tpa, last);
925 if (tpa_next_partition (tpa, first) != NO_PARTITION)
932 first = tpa_first_partition (tpa, x);
933 if (tpa_next_partition (tpa, first) != NO_PARTITION)
935 tpa->uncompressed_num = tpa->num_trees;
941 /* Initialize a root_var object with SSA partitions from MAP which are based
942 on each root variable. */
945 root_var_init (var_map map)
948 int num_partitions = num_var_partitions (map);
958 seen = sbitmap_alloc (num_partitions);
961 /* Start at the end and work towards the front. This will provide a list
962 that is ordered from smallest to largest. */
963 for (x = num_partitions - 1; x >= 0; x--)
965 t = partition_to_var (map, x);
967 /* The var map may not be compacted yet, so check for NULL. */
971 p = var_to_partition (map, t);
973 #ifdef ENABLE_CHECKING
974 if (p == NO_PARTITION)
978 /* Make sure we only put coalesced partitions into the list once. */
979 if (TEST_BIT (seen, p))
982 if (TREE_CODE (t) == SSA_NAME)
983 t = SSA_NAME_VAR (t);
985 if (ann->root_var_processed)
987 rv->next_partition[p] = VARRAY_INT (rv->first_partition,
988 VAR_ANN_ROOT_INDEX (ann));
989 VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p;
993 ann->root_var_processed = 1;
994 VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
995 VARRAY_PUSH_TREE (rv->trees, t);
996 VARRAY_PUSH_INT (rv->first_partition, p);
998 rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
1001 /* Reset the out_of_ssa_tag flag on each variable for later use. */
1002 for (x = 0; x < rv->num_trees; x++)
1004 t = VARRAY_TREE (rv->trees, x);
1005 var_ann (t)->root_var_processed = 0;
1008 sbitmap_free (seen);
1013 /* Initialize a type_var structure which associates all the partitions in MAP
1014 of the same type to the type node's index. Volatiles are ignored. */
1017 type_var_init (var_map map)
1021 int num_partitions = num_var_partitions (map);
1025 seen = sbitmap_alloc (num_partitions);
1026 sbitmap_zero (seen);
1028 tv = tpa_init (map);
1032 for (x = num_partitions - 1; x >= 0; x--)
1034 t = partition_to_var (map, x);
1036 /* Disallow coalescing of these types of variables. */
1038 || TREE_THIS_VOLATILE (t)
1039 || TREE_CODE (t) == RESULT_DECL
1040 || TREE_CODE (t) == PARM_DECL
1042 && (DECL_REGISTER (t)
1043 || !DECL_ARTIFICIAL (t)
1044 || DECL_RTL_SET_P (t))))
1047 p = var_to_partition (map, t);
1049 #ifdef ENABLE_CHECKING
1050 if (p == NO_PARTITION)
1054 /* If partitions have been coalesced, only add the representative
1055 for the partition to the list once. */
1056 if (TEST_BIT (seen, p))
1061 /* Find the list for this type. */
1062 for (y = 0; y < tv->num_trees; y++)
1063 if (t == VARRAY_TREE (tv->trees, y))
1065 if (y == tv->num_trees)
1068 VARRAY_PUSH_TREE (tv->trees, t);
1069 VARRAY_PUSH_INT (tv->first_partition, p);
1073 tv->next_partition[p] = VARRAY_INT (tv->first_partition, y);
1074 VARRAY_INT (tv->first_partition, y) = p;
1076 tv->partition_to_tree_map[p] = y;
1078 sbitmap_free (seen);
1083 /* Create a new coalesce list object from MAP and return it. */
1086 create_coalesce_list (var_map map)
1088 coalesce_list_p list;
1090 list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
1093 list->add_mode = true;
1094 list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
1095 sizeof (struct partition_pair_d));
1100 /* Delete coalesce list CL. */
1103 delete_coalesce_list (coalesce_list_p cl)
1110 /* Find a matching coalesce pair object in CL for partitions P1 and P2. If
1111 one isn't found, return NULL if CREATE is false, otherwise create a new
1112 coalesce pair object and return it. */
1114 static partition_pair_p
1115 find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
1117 partition_pair_p node, tmp;
1120 /* Normalize so that p1 is the smaller value. */
1130 /* The list is sorted such that if we find a value greater than p2,
1131 p2 is not in the list. */
1132 for (node = cl->list[p1]; node; node = node->next)
1134 if (node->second_partition == p2)
1137 if (node->second_partition > p2)
1145 node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
1146 node->first_partition = p1;
1147 node->second_partition = p2;
1152 node->next = tmp->next;
1157 /* This is now the first node in the list. */
1158 node->next = cl->list[p1];
1159 cl->list[p1] = node;
1166 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
1169 add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
1171 partition_pair_p node;
1173 #ifdef ENABLE_CHECKING
1181 node = find_partition_pair (cl, p1, p2, true);
1183 node->cost += value;
1187 /* Comparison function to allow qsort to sort P1 and P2 in descending order. */
1190 int compare_pairs (const void *p1, const void *p2)
1192 return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
1196 /* Prepare CL for removal of preferred pairs. When finished, list element
1197 0 has all the coalesce pairs, sorted in order from most important coalesce
1198 to least important. */
1201 sort_coalesce_list (coalesce_list_p cl)
1204 partition_pair_p chain, p;
1205 partition_pair_p *list;
1210 cl->add_mode = false;
1212 /* Compact the array of lists to a single list, and count the elements. */
1215 for (x = 0; x < num_var_partitions (cl->map); x++)
1216 if (cl->list[x] != NULL)
1218 for (p = cl->list[x]; p->next != NULL; p = p->next)
1222 chain = cl->list[x];
1226 /* Only call qsort if there are more than 2 items. */
1229 list = xmalloc (sizeof (partition_pair_p) * num);
1231 for (p = chain; p != NULL; p = p->next)
1234 #ifdef ENABLE_CHECKING
1239 qsort (list, count, sizeof (partition_pair_p), compare_pairs);
1242 for (x = 1; x < num; x++)
1248 cl->list[0] = list[0];
1253 cl->list[0] = chain;
1256 /* Simply swap the two elements if they are in the wrong order. */
1257 if (chain->cost < chain->next->cost)
1259 cl->list[0] = chain->next;
1260 cl->list[0]->next = chain;
1268 /* Retrieve the best remaining pair to coalesce from CL. Returns the 2
1269 partitions via P1 and P2. Their calculated cost is returned by the function.
1270 NO_BEST_COALESCE is returned if the coalesce list is empty. */
1273 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
1275 partition_pair_p node;
1283 return NO_BEST_COALESCE;
1285 cl->list[0] = node->next;
1287 *p1 = node->first_partition;
1288 *p2 = node->second_partition;
1296 /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
1297 VAR and any other live partitions in VEC which are associated via TPA.
1298 Reset the live bit in VEC. */
1301 add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
1302 var_map map, bitmap vec, tree var)
1305 p = var_to_partition (map, var);
1306 if (p != NO_PARTITION)
1308 bitmap_clear_bit (vec, p);
1309 first = tpa_find_tree (tpa, p);
1310 /* If find returns nothing, this object isn't interesting. */
1311 if (first == TPA_NONE)
1313 /* Only add interferences between objects in the same list. */
1314 for (y = tpa_first_partition (tpa, first);
1316 y = tpa_next_partition (tpa, y))
1318 if (bitmap_bit_p (vec, y))
1319 conflict_graph_add (graph, p, y);
1325 /* Return a conflict graph for the information contained in LIVE_INFO. Only
1326 conflicts between items in the same TPA list are added. If optional
1327 coalesce list CL is passed in, any copies encountered are added. */
1330 build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
1333 conflict_graph graph;
1338 varray_type partition_link, tpa_to_clear, tpa_nodes;
1343 map = live_var_map (liveinfo);
1344 graph = conflict_graph_new (num_var_partitions (map));
1346 if (tpa_num_trees (tpa) == 0)
1349 live = BITMAP_XMALLOC ();
1351 VARRAY_INT_INIT (partition_link, num_var_partitions (map) + 1, "part_link");
1352 VARRAY_INT_INIT (tpa_nodes, tpa_num_trees (tpa), "tpa nodes");
1353 VARRAY_INT_INIT (tpa_to_clear, 50, "tpa to clear");
1357 block_stmt_iterator bsi;
1360 /* Start with live on exit temporaries. */
1361 bitmap_copy (live, live_on_exit (liveinfo, bb));
1363 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1365 bool is_a_copy = false;
1366 tree stmt = bsi_stmt (bsi);
1369 get_stmt_operands (stmt);
1370 ann = stmt_ann (stmt);
1372 /* A copy between 2 partitions does not introduce an interference
1373 by itself. If they did, you would never be able to coalesce
1374 two things which are copied. If the two variables really do
1375 conflict, they will conflict elsewhere in the program.
1377 This is handled specially here since we may also be interested
1378 in copies between real variables and SSA_NAME variables. We may
1379 be interested in trying to coalesce SSA_NAME variables with
1380 root variables in some cases. */
1382 if (TREE_CODE (stmt) == MODIFY_EXPR)
1384 tree lhs = TREE_OPERAND (stmt, 0);
1385 tree rhs = TREE_OPERAND (stmt, 1);
1389 if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
1390 p1 = var_to_partition (map, lhs);
1394 if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
1395 p2 = var_to_partition (map, rhs);
1399 if (p1 != NO_PARTITION && p2 != NO_PARTITION)
1402 bit = bitmap_bit_p (live, p2);
1403 /* If the RHS is live, make it not live while we add
1404 the conflicts, then make it live again. */
1406 bitmap_clear_bit (live, p2);
1407 add_conflicts_if_valid (tpa, graph, map, live, lhs);
1409 bitmap_set_bit (live, p2);
1411 add_coalesce (cl, p1, p2, 1);
1412 set_if_valid (map, live, rhs);
1420 defs = DEF_OPS (ann);
1421 num = NUM_DEFS (defs);
1422 for (x = 0; x < num; x++)
1424 var = DEF_OP (defs, x);
1425 add_conflicts_if_valid (tpa, graph, map, live, var);
1428 uses = USE_OPS (ann);
1429 num = NUM_USES (uses);
1430 for (x = 0; x < num; x++)
1432 var = USE_OP (uses, x);
1433 set_if_valid (map, live, var);
1438 /* If result of a PHI is unused, then the loops over the statements
1439 will not record any conflicts. However, since the PHI node is
1440 going to be translated out of SSA form we must record a conflict
1441 between the result of the PHI and any variables with are live.
1442 Otherwise the out-of-ssa translation may create incorrect code. */
1443 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1445 tree result = PHI_RESULT (phi);
1446 int p = var_to_partition (map, result);
1448 if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
1449 add_conflicts_if_valid (tpa, graph, map, live, result);
1452 /* Anything which is still live at this point interferes.
1453 In order to implement this efficiently, only conflicts between
1454 partitions which have the same TPA root need be added.
1455 TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
1456 entry points to an index into 'partition_link', which then indexes
1457 into itself forming a linked list of partitions sharing a tpa root
1458 which have been seen as live up to this point. Since partitions start
1459 at index zero, all entries in partition_link are (partition + 1).
1461 Conflicts are added between the current partition and any already seen.
1462 tpa_clear contains all the tpa_roots processed, and these are the only
1463 entries which need to be zero'd out for a clean restart. */
1465 EXECUTE_IF_SET_IN_BITMAP (live, 0, x,
1467 i = tpa_find_tree (tpa, x);
1470 int start = VARRAY_INT (tpa_nodes, i);
1471 /* If start is 0, a new root reference list is being started.
1472 Register it to be cleared. */
1474 VARRAY_PUSH_INT (tpa_to_clear, i);
1476 /* Add interferences to other tpa members seen. */
1477 for (y = start; y != 0; y = VARRAY_INT (partition_link, y))
1478 conflict_graph_add (graph, x, y - 1);
1479 VARRAY_INT (tpa_nodes, i) = x + 1;
1480 VARRAY_INT (partition_link, x + 1) = start;
1484 /* Now clear the used tpa root references. */
1485 for (l = 0; l < VARRAY_ACTIVE_SIZE (tpa_to_clear); l++)
1486 VARRAY_INT (tpa_nodes, VARRAY_INT (tpa_to_clear, l)) = 0;
1487 VARRAY_POP_ALL (tpa_to_clear);
1490 BITMAP_XFREE (live);
1495 /* This routine will attempt to coalesce the elements in TPA subject to the
1496 conflicts found in GRAPH. If optional coalesce_list CL is provided,
1497 only coalesces specified within the coalesce list are attempted. Otherwise
1498 an attempt is made to coalesce as many partitions within each TPA grouping
1499 as possible. If DEBUG is provided, debug output will be sent there. */
1502 coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
1503 coalesce_list_p cl, FILE *debug)
1508 /* Attempt to coalesce any items in a coalesce list. */
1511 while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
1515 fprintf (debug, "Coalesce list: (%d)", x);
1516 print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
1517 fprintf (debug, " & (%d)", y);
1518 print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
1521 w = tpa_find_tree (tpa, x);
1522 z = tpa_find_tree (tpa, y);
1523 if (w != z || w == TPA_NONE || z == TPA_NONE)
1528 fprintf (debug, ": Fail, Non-matching TPA's\n");
1530 fprintf (debug, ": Fail %d non TPA.\n", x);
1532 fprintf (debug, ": Fail %d non TPA.\n", y);
1536 var = partition_to_var (map, x);
1537 tmp = partition_to_var (map, y);
1538 x = var_to_partition (map, var);
1539 y = var_to_partition (map, tmp);
1541 fprintf (debug, " [map: %d, %d] ", x, y);
1545 fprintf (debug, ": Already Coalesced.\n");
1548 if (!conflict_graph_conflict_p (graph, x, y))
1550 z = var_union (map, var, tmp);
1551 if (z == NO_PARTITION)
1554 fprintf (debug, ": Unable to perform partition union.\n");
1558 /* z is the new combined partition. We need to remove the other
1559 partition from the list. Set x to be that other partition. */
1562 conflict_graph_merge_regs (graph, x, y);
1563 w = tpa_find_tree (tpa, y);
1564 tpa_remove_partition (tpa, w, y);
1568 conflict_graph_merge_regs (graph, y, x);
1569 w = tpa_find_tree (tpa, x);
1570 tpa_remove_partition (tpa, w, x);
1574 fprintf (debug, ": Success -> %d\n", z);
1578 fprintf (debug, ": Fail due to conflict\n");
1580 /* If using a coalesce list, don't try to coalesce anything else. */
1584 for (x = 0; x < tpa_num_trees (tpa); x++)
1586 while (tpa_first_partition (tpa, x) != TPA_NONE)
1589 /* Coalesce first partition with anything that doesn't conflict. */
1590 y = tpa_first_partition (tpa, x);
1591 tpa_remove_partition (tpa, x, y);
1593 var = partition_to_var (map, y);
1594 /* p1 is the partition representative to which y belongs. */
1595 p1 = var_to_partition (map, var);
1597 for (z = tpa_next_partition (tpa, y);
1599 z = tpa_next_partition (tpa, z))
1601 tmp = partition_to_var (map, z);
1602 /* p2 is the partition representative to which z belongs. */
1603 p2 = var_to_partition (map, tmp);
1606 fprintf (debug, "Coalesce : ");
1607 print_generic_expr (debug, var, TDF_SLIM);
1608 fprintf (debug, " &");
1609 print_generic_expr (debug, tmp, TDF_SLIM);
1610 fprintf (debug, " (%d ,%d)", p1, p2);
1613 /* If partitions are already merged, don't check for conflict. */
1616 tpa_remove_partition (tpa, x, z);
1618 fprintf (debug, ": Already coalesced\n");
1621 if (!conflict_graph_conflict_p (graph, p1, p2))
1624 if (tpa_find_tree (tpa, y) == TPA_NONE
1625 || tpa_find_tree (tpa, z) == TPA_NONE)
1628 fprintf (debug, ": Fail non-TPA member\n");
1631 if ((v = var_union (map, var, tmp)) == NO_PARTITION)
1634 fprintf (debug, ": Fail cannot combine partitions\n");
1638 tpa_remove_partition (tpa, x, z);
1640 conflict_graph_merge_regs (graph, v, z);
1643 /* Update the first partition's representative. */
1644 conflict_graph_merge_regs (graph, v, y);
1648 /* The root variable of the partition may be changed
1650 var = partition_to_var (map, p1);
1653 fprintf (debug, ": Success -> %d\n", v);
1657 fprintf (debug, ": Fail, Conflict\n");
1664 /* Send debug info for coalesce list CL to file F. */
1667 dump_coalesce_list (FILE *f, coalesce_list_p cl)
1669 partition_pair_p node;
1675 fprintf (f, "Coalesce List:\n");
1676 num = num_var_partitions (cl->map);
1677 for (x = 0; x < num; x++)
1683 print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
1684 fprintf (f, "] - ");
1685 for ( ; node; node = node->next)
1687 var = partition_to_var (cl->map, node->second_partition);
1688 print_generic_expr (f, var, TDF_SLIM);
1689 fprintf (f, "(%1d), ", node->cost);
1697 fprintf (f, "Sorted Coalesce list:\n");
1698 for (node = cl->list[0]; node; node = node->next)
1700 fprintf (f, "(%d) ", node->cost);
1701 var = partition_to_var (cl->map, node->first_partition);
1702 print_generic_expr (f, var, TDF_SLIM);
1704 var = partition_to_var (cl->map, node->second_partition);
1705 print_generic_expr (f, var, TDF_SLIM);
1712 /* Output tree_partition_associator object TPA to file F.. */
1715 tpa_dump (FILE *f, tpa_p tpa)
1722 for (x = 0; x < tpa_num_trees (tpa); x++)
1724 print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
1725 fprintf (f, " : (");
1726 for (i = tpa_first_partition (tpa, x);
1728 i = tpa_next_partition (tpa, i))
1730 fprintf (f, "(%d)",i);
1731 print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
1734 #ifdef ENABLE_CHECKING
1735 if (tpa_find_tree (tpa, i) != x)
1736 fprintf (f, "**find tree incorrectly set** ");
1746 /* Output partition map MAP to file F. */
1749 dump_var_map (FILE *f, var_map map)
1755 fprintf (f, "\nPartition map \n\n");
1757 for (x = 0; x < map->num_partitions; x++)
1759 if (map->compact_to_partition != NULL)
1760 p = map->compact_to_partition[x];
1764 if (map->partition_to_var[p] == NULL_TREE)
1768 for (y = 1; y < num_ssa_names; y++)
1770 p = partition_find (map->var_partition, y);
1771 if (map->partition_to_compact)
1772 p = map->partition_to_compact[p];
1777 fprintf(f, "Partition %d (", x);
1778 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1781 fprintf (f, "%d ", y);
1791 /* Output live range info LIVE to file F, controlled by FLAG. */
1794 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1798 var_map map = live->map;
1800 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1804 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1805 for (i = 0; i < num_var_partitions (map); i++)
1807 if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
1809 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1817 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1821 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1822 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i,
1824 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);