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-simple.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. */
138 if (!root_var || is_gimple_tmp_var (root_var))
140 other_var = root_var;
147 if (p1 == NO_PARTITION || 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 if (TREE_CODE (var) == SSA_NAME)
281 ann->out_of_ssa_tag = 1;
282 VAR_ANN_PARTITION (ann) = part;
283 if (map->compact_to_partition)
284 map->partition_to_var[map->compact_to_partition[part]] = var;
288 /* This function looks through the program and uses FLAGS to determine what
289 SSA versioned variables are given entries in a new partition table. This
290 new partition map is returned. */
293 create_ssa_var_map (int flags)
295 block_stmt_iterator bsi;
306 #if defined ENABLE_CHECKING
307 sbitmap used_in_real_ops;
308 sbitmap used_in_virtual_ops;
311 map = init_var_map (highest_ssa_version + 1);
313 #if defined ENABLE_CHECKING
314 used_in_real_ops = sbitmap_alloc (num_referenced_vars);
315 sbitmap_zero (used_in_real_ops);
317 used_in_virtual_ops = sbitmap_alloc (num_referenced_vars);
318 sbitmap_zero (used_in_virtual_ops);
321 if (flags & SSA_VAR_MAP_REF_COUNT)
324 = (int *)xmalloc (((highest_ssa_version + 1) * sizeof (int)));
325 memset (map->ref_count, 0, (highest_ssa_version + 1) * sizeof (int));
331 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
334 register_ssa_partition (map, PHI_RESULT (phi), false);
335 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
337 arg = PHI_ARG_DEF (phi, i);
338 if (TREE_CODE (arg) == SSA_NAME)
339 register_ssa_partition (map, arg, true);
343 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
345 stmt = bsi_stmt (bsi);
346 get_stmt_operands (stmt);
347 ann = stmt_ann (stmt);
349 /* Register USE and DEF operands in each statement. */
350 uses = USE_OPS (ann);
351 for (x = 0; x < NUM_USES (uses); x++)
353 use = USE_OP_PTR (uses, x);
354 register_ssa_partition (map, *use, true);
356 #if defined ENABLE_CHECKING
357 SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*use))->uid);
361 defs = DEF_OPS (ann);
362 for (x = 0; x < NUM_DEFS (defs); x++)
364 dest = DEF_OP_PTR (defs, x);
365 register_ssa_partition (map, *dest, false);
367 #if defined ENABLE_CHECKING
368 SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*dest))->uid);
372 /* While we do not care about virtual operands for
373 out of SSA, we do need to look at them to make sure
374 we mark all the variables which are used. */
375 vuses = VUSE_OPS (ann);
376 for (x = 0; x < NUM_VUSES (vuses); x++)
378 tree var = VUSE_OP (vuses, x);
381 #if defined ENABLE_CHECKING
382 SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid);
386 vdefs = VDEF_OPS (ann);
387 for (x = 0; x < NUM_VDEFS (vdefs); x++)
389 tree var = VDEF_OP (vdefs, x);
392 #if defined ENABLE_CHECKING
393 SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid);
399 #if defined ENABLE_CHECKING
402 sbitmap both = sbitmap_alloc (num_referenced_vars);
403 sbitmap_a_and_b (both, used_in_real_ops, used_in_virtual_ops);
404 if (sbitmap_first_set_bit (both) >= 0)
406 EXECUTE_IF_SET_IN_SBITMAP (both, 0, i,
407 fprintf (stderr, "Variable %s used in real and virtual operands\n",
408 get_name (referenced_var (i))));
412 sbitmap_free (used_in_real_ops);
413 sbitmap_free (used_in_virtual_ops);
422 /* Allocate and return a new live range information object base on MAP. */
424 static tree_live_info_p
425 new_tree_live_info (var_map map)
427 tree_live_info_p live;
430 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
432 live->num_blocks = last_basic_block;
434 live->global = BITMAP_XMALLOC ();
436 live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
437 for (x = 0; x < num_var_partitions (map); x++)
438 live->livein[x] = BITMAP_XMALLOC ();
440 /* liveout is deferred until it is actually requested. */
441 live->liveout = NULL;
446 /* Free storage for live range info object LIVE. */
449 delete_tree_live_info (tree_live_info_p live)
454 for (x = live->num_blocks - 1; x >= 0; x--)
455 BITMAP_XFREE (live->liveout[x]);
456 free (live->liveout);
460 for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
461 BITMAP_XFREE (live->livein[x]);
465 BITMAP_XFREE (live->global);
471 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
472 for partition I. STACK is a varray used for temporary memory which is
473 passed in rather than being allocated on every call. */
476 live_worklist (tree_live_info_p live, varray_type stack, int i)
480 basic_block def_bb = NULL;
482 var_map map = live->map;
484 var = partition_to_var (map, i);
485 if (SSA_NAME_DEF_STMT (var))
486 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
488 EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b,
490 VARRAY_PUSH_INT (stack, b);
493 while (VARRAY_ACTIVE_SIZE (stack) > 0)
495 b = VARRAY_TOP_INT (stack);
498 for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
499 if (e->src != ENTRY_BLOCK_PTR)
501 /* Its not live on entry to the block its defined in. */
502 if (e->src == def_bb)
504 if (!bitmap_bit_p (live->livein[i], e->src->index))
506 bitmap_set_bit (live->livein[i], e->src->index);
507 VARRAY_PUSH_INT (stack, e->src->index);
514 /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
517 set_if_valid (var_map map, bitmap vec, tree var)
519 int p = var_to_partition (map, var);
520 if (p != NO_PARTITION)
521 bitmap_set_bit (vec, p);
525 /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
526 global bit for it in the LIVE object. BB is the block being processed. */
529 add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
530 tree var, basic_block bb)
532 int p = var_to_partition (live->map, var);
533 if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
535 if (!bitmap_bit_p (def_vec, p))
537 bitmap_set_bit (live->livein[p], bb->index);
538 bitmap_set_bit (live->global, p);
543 /* Given partition map MAP, calculate all the live on entry bitmaps for
544 each basic block. Return a live info object. */
547 calculate_live_on_entry (var_map map)
549 tree_live_info_p live;
557 block_stmt_iterator bsi;
564 saw_def = BITMAP_XMALLOC ();
566 live = new_tree_live_info (map);
570 bitmap_clear (saw_def);
572 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
574 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
576 var = PHI_ARG_DEF (phi, i);
577 if (!phi_ssa_name_p (var))
579 stmt = SSA_NAME_DEF_STMT (var);
580 e = PHI_ARG_EDGE (phi, i);
582 /* Any uses in PHIs which either don't have def's or are not
583 defined in the block from which the def comes, will be live
584 on entry to that block. */
585 if (!stmt || e->src != bb_for_stmt (stmt))
586 add_livein_if_notdef (live, saw_def, var, e->src);
590 /* Don't mark PHI results as defined until all the PHI nodes have
591 been processed. If the PHI sequence is:
594 The a_3 referred to in b_3's PHI node is the one incoming on the
595 edge, *not* the PHI node just seen. */
597 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
599 var = PHI_RESULT (phi);
600 set_if_valid (map, saw_def, var);
603 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
605 stmt = bsi_stmt (bsi);
606 get_stmt_operands (stmt);
607 ann = stmt_ann (stmt);
609 uses = USE_OPS (ann);
610 num = NUM_USES (uses);
611 for (i = 0; i < num; i++)
613 vec = USE_OP_PTR (uses, i);
614 add_livein_if_notdef (live, saw_def, *vec, bb);
617 vuses = VUSE_OPS (ann);
618 num = NUM_VUSES (vuses);
619 for (i = 0; i < num; i++)
621 var = VUSE_OP (vuses, i);
622 add_livein_if_notdef (live, saw_def, var, bb);
625 vdefs = VDEF_OPS (ann);
626 num = NUM_VDEFS (vdefs);
627 for (i = 0; i < num; i++)
629 var = VDEF_OP (vdefs, i);
630 add_livein_if_notdef (live, saw_def, var, bb);
633 defs = DEF_OPS (ann);
634 num = NUM_DEFS (defs);
635 for (i = 0; i < num; i++)
637 vec = DEF_OP_PTR (defs, i);
638 set_if_valid (map, saw_def, *vec);
641 num = NUM_VDEFS (vdefs);
642 for (i = 0; i < num; i++)
644 var = VDEF_RESULT (vdefs, i);
645 set_if_valid (map, saw_def, var);
650 VARRAY_INT_INIT (stack, last_basic_block, "stack");
651 EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i,
653 live_worklist (live, stack, i);
656 #ifdef ENABLE_CHECKING
657 /* Check for live on entry partitions and report those with a DEF in
658 the program. This will typically mean an optimization has done
661 bb = ENTRY_BLOCK_PTR;
663 for (e = bb->succ; e; e = e->succ_next)
665 int entry_block = e->dest->index;
666 if (e->dest == EXIT_BLOCK_PTR)
668 for (i = 0; i < num_var_partitions (map); i++)
672 var = partition_to_var (map, i);
673 stmt = SSA_NAME_DEF_STMT (var);
674 tmp = bb_for_stmt (stmt);
675 d = default_def (SSA_NAME_VAR (var));
677 if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
679 if (!IS_EMPTY_STMT (stmt))
682 print_generic_expr (stderr, var, TDF_SLIM);
683 fprintf (stderr, " is defined ");
685 fprintf (stderr, " in BB%d, ", tmp->index);
686 fprintf (stderr, "by:\n");
687 print_generic_expr (stderr, stmt, TDF_SLIM);
688 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
690 fprintf (stderr, " So it appears to have multiple defs.\n");
697 print_generic_expr (stderr, var, TDF_SLIM);
698 fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
701 fprintf (stderr, " but is not the default def of ");
702 print_generic_expr (stderr, d, TDF_SLIM);
703 fprintf (stderr, "\n");
706 fprintf (stderr, " and there is no default def.\n");
713 /* The only way this var shouldn't be marked live on entry is
714 if it occurs in a PHI argument of the block. */
716 for (phi = phi_nodes (e->dest);
718 phi = TREE_CHAIN (phi))
720 for (z = 0; z < PHI_NUM_ARGS (phi); z++)
721 if (var == PHI_ARG_DEF (phi, z))
730 print_generic_expr (stderr, var, TDF_SLIM);
731 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
733 fprintf (stderr, "but it is a default def so it should be.\n");
741 BITMAP_XFREE (saw_def);
747 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
750 calculate_live_on_exit (tree_live_info_p liveinfo)
759 var_map map = liveinfo->map;
761 on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
762 for (x = 0; x < last_basic_block; x++)
763 on_exit[x] = BITMAP_XMALLOC ();
765 /* Set all the live-on-exit bits for uses in PHIs. */
768 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
769 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
771 t = PHI_ARG_DEF (phi, i);
772 e = PHI_ARG_EDGE (phi, i);
773 if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
775 set_if_valid (map, on_exit[e->src->index], t);
779 /* Set live on exit for all predecessors of live on entry's. */
780 for (i = 0; i < num_var_partitions (map); i++)
782 on_entry = live_entry_blocks (liveinfo, i);
783 EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b,
785 for (e = BASIC_BLOCK(b)->pred; e; e = e->pred_next)
786 if (e->src != ENTRY_BLOCK_PTR)
787 bitmap_set_bit (on_exit[e->src->index], i);
791 liveinfo->liveout = on_exit;
795 /* Initialize a tree_partition_associator object using MAP. */
798 tpa_init (var_map map)
801 int num_partitions = num_var_partitions (map);
804 if (num_partitions == 0)
807 tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
809 tpa->uncompressed_num = -1;
811 tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
812 memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
814 tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
815 memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
817 x = MAX (40, (num_partitions / 20));
818 VARRAY_TREE_INIT (tpa->trees, x, "trees");
819 VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
826 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
829 tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
833 i = tpa_first_partition (tpa, tree_index);
834 if (i == partition_index)
836 VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i];
840 for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
842 if (tpa->next_partition[i] == partition_index)
844 tpa->next_partition[i] = tpa->next_partition[partition_index];
852 /* Free the memory used by tree_partition_associator object TPA. */
855 tpa_delete (tpa_p tpa)
860 free (tpa->partition_to_tree_map);
861 free (tpa->next_partition);
866 /* This function will remove any tree entires from TPA which have only a single
867 element. This will help keep the size of the conflict graph down. The
868 function returns the number of remaining tree lists. */
871 tpa_compact (tpa_p tpa)
873 int last, x, y, first, swap_i;
876 /* Find the last list which has more than 1 partition. */
877 for (last = tpa->num_trees - 1; last > 0; last--)
879 first = tpa_first_partition (tpa, last);
880 if (tpa_next_partition (tpa, first) != NO_PARTITION)
887 first = tpa_first_partition (tpa, x);
889 /* If there is not more than one partition, swap with the current end
891 if (tpa_next_partition (tpa, first) == NO_PARTITION)
893 swap_t = VARRAY_TREE (tpa->trees, last);
894 swap_i = VARRAY_INT (tpa->first_partition, last);
896 /* Update the last entry. Since it is known to only have one
897 partition, there is nothing else to update. */
898 VARRAY_TREE (tpa->trees, last) = VARRAY_TREE (tpa->trees, x);
899 VARRAY_INT (tpa->first_partition, last)
900 = VARRAY_INT (tpa->first_partition, x);
901 tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
903 /* Since this list is known to have more than one partition, update
904 the list owner entries. */
905 VARRAY_TREE (tpa->trees, x) = swap_t;
906 VARRAY_INT (tpa->first_partition, x) = swap_i;
907 for (y = tpa_first_partition (tpa, x);
909 y = tpa_next_partition (tpa, y))
910 tpa->partition_to_tree_map[y] = x;
912 /* Ensure last is a list with more than one partition. */
914 for (; last > x; last--)
916 first = tpa_first_partition (tpa, last);
917 if (tpa_next_partition (tpa, first) != NO_PARTITION)
924 first = tpa_first_partition (tpa, x);
925 if (tpa_next_partition (tpa, first) != NO_PARTITION)
927 tpa->uncompressed_num = tpa->num_trees;
933 /* Initialize a root_var object with SSA partitions from MAP which are based
934 on each root variable. */
937 root_var_init (var_map map)
940 int num_partitions = num_var_partitions (map);
950 seen = sbitmap_alloc (num_partitions);
953 /* Start at the end and work towards the front. This will provide a list
954 that is ordered from smallest to largest. */
955 for (x = num_partitions - 1; x >= 0; x--)
957 t = partition_to_var (map, x);
959 /* The var map may not be compacted yet, so check for NULL. */
963 p = var_to_partition (map, t);
965 #ifdef ENABLE_CHECKING
966 if (p == NO_PARTITION)
970 /* Make sure we only put coalesced partitions into the list once. */
971 if (TEST_BIT (seen, p))
974 if (TREE_CODE (t) == SSA_NAME)
975 t = SSA_NAME_VAR (t);
977 if (ann->root_var_processed)
979 rv->next_partition[p] = VARRAY_INT (rv->first_partition,
980 VAR_ANN_ROOT_INDEX (ann));
981 VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p;
985 ann->root_var_processed = 1;
986 VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
987 VARRAY_PUSH_TREE (rv->trees, t);
988 VARRAY_PUSH_INT (rv->first_partition, p);
990 rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
993 /* Reset the out_of_ssa_tag flag on each variable for later use. */
994 for (x = 0; x < rv->num_trees; x++)
996 t = VARRAY_TREE (rv->trees, x);
997 var_ann (t)->root_var_processed = 0;
1000 sbitmap_free (seen);
1005 /* Initialize a type_var structure which associates all the partitions in MAP
1006 of the same type to the type node's index. Volatiles are ignored. */
1009 type_var_init (var_map map)
1013 int num_partitions = num_var_partitions (map);
1017 seen = sbitmap_alloc (num_partitions);
1018 sbitmap_zero (seen);
1020 tv = tpa_init (map);
1024 for (x = num_partitions - 1; x >= 0; x--)
1026 t = partition_to_var (map, x);
1028 /* Disallow coalescing of these types of variables. */
1030 || TREE_THIS_VOLATILE (t)
1031 || TREE_CODE (t) == RESULT_DECL
1032 || TREE_CODE (t) == PARM_DECL
1034 && (DECL_REGISTER (t)
1035 || !DECL_ARTIFICIAL (t)
1036 || DECL_RTL_SET_P (t))))
1039 p = var_to_partition (map, t);
1041 #ifdef ENABLE_CHECKING
1042 if (p == NO_PARTITION)
1046 /* If partitions have been coalesced, only add the representative
1047 for the partition to the list once. */
1048 if (TEST_BIT (seen, p))
1053 /* Find the list for this type. */
1054 for (y = 0; y < tv->num_trees; y++)
1055 if (t == VARRAY_TREE (tv->trees, y))
1057 if (y == tv->num_trees)
1060 VARRAY_PUSH_TREE (tv->trees, t);
1061 VARRAY_PUSH_INT (tv->first_partition, p);
1065 tv->next_partition[p] = VARRAY_INT (tv->first_partition, y);
1066 VARRAY_INT (tv->first_partition, y) = p;
1068 tv->partition_to_tree_map[p] = y;
1070 sbitmap_free (seen);
1075 /* Create a new coalesce list object from MAP and return it. */
1078 create_coalesce_list (var_map map)
1080 coalesce_list_p list;
1082 list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
1085 list->add_mode = true;
1086 list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
1087 sizeof (struct partition_pair_d));
1092 /* Delete coalesce list CL. */
1095 delete_coalesce_list (coalesce_list_p cl)
1102 /* Find a matching coalesce pair object in CL for partitions P1 and P2. If
1103 one isn't found, return NULL if CREATE is false, otherwise create a new
1104 coalesce pair object and return it. */
1106 static partition_pair_p
1107 find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
1109 partition_pair_p node, tmp;
1112 /* Normalize so that p1 is the smaller value. */
1122 /* The list is sorted such that if we find a value greater than p2,
1123 p2 is not in the list. */
1124 for (node = cl->list[p1]; node; node = node->next)
1126 if (node->second_partition == p2)
1129 if (node->second_partition > p2)
1137 node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
1138 node->first_partition = p1;
1139 node->second_partition = p2;
1144 node->next = tmp->next;
1149 /* This is now the first node in the list. */
1150 node->next = cl->list[p1];
1151 cl->list[p1] = node;
1158 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
1161 add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
1163 partition_pair_p node;
1165 #ifdef ENABLE_CHECKING
1173 node = find_partition_pair (cl, p1, p2, true);
1175 node->cost += value;
1179 /* Comparison function to allow qsort to sort P1 and P2 in descending order. */
1182 int compare_pairs (const void *p1, const void *p2)
1184 return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
1188 /* Prepare CL for removal of preferred pairs. When finished, list element
1189 0 has all the coalesce pairs, sorted in order from most important coalesce
1190 to least important. */
1193 sort_coalesce_list (coalesce_list_p cl)
1196 partition_pair_p chain, p;
1197 partition_pair_p *list;
1202 cl->add_mode = false;
1204 /* Compact the array of lists to a single list, and count the elements. */
1207 for (x = 0; x < num_var_partitions (cl->map); x++)
1208 if (cl->list[x] != NULL)
1210 for (p = cl->list[x]; p->next != NULL; p = p->next)
1214 chain = cl->list[x];
1218 /* Only call qsort if there are more than 2 items. */
1221 list = xmalloc (sizeof (partition_pair_p) * num);
1223 for (p = chain; p != NULL; p = p->next)
1226 #ifdef ENABLE_CHECKING
1231 qsort (list, count, sizeof (partition_pair_p), compare_pairs);
1234 for (x = 1; x < num; x++)
1240 cl->list[0] = list[0];
1245 cl->list[0] = chain;
1248 /* Simply swap the two elements if they are in the wrong order. */
1249 if (chain->cost < chain->next->cost)
1251 cl->list[0] = chain->next;
1252 cl->list[0]->next = chain;
1260 /* Retrieve the best remaining pair to coalesce from CL. Returns the 2
1261 partitions via P1 and P2. Their calculated cost is returned by the function.
1262 NO_BEST_COALESCE is returned if the coalesce list is empty. */
1265 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
1267 partition_pair_p node;
1275 return NO_BEST_COALESCE;
1277 cl->list[0] = node->next;
1279 *p1 = node->first_partition;
1280 *p2 = node->second_partition;
1288 /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
1289 VAR and any other live partitions in VEC which are associated via TPA.
1290 Reset the live bit in VEC. */
1293 add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
1294 var_map map, bitmap vec, tree var)
1297 p = var_to_partition (map, var);
1298 if (p != NO_PARTITION)
1300 bitmap_clear_bit (vec, p);
1301 first = tpa_find_tree (tpa, p);
1302 /* If find returns nothing, this object isn't interesting. */
1303 if (first == TPA_NONE)
1305 /* Only add interferences between objects in the same list. */
1306 for (y = tpa_first_partition (tpa, first);
1308 y = tpa_next_partition (tpa, y))
1310 if (bitmap_bit_p (vec, y))
1311 conflict_graph_add (graph, p, y);
1317 /* Return a conflict graph for the information contained in LIVE_INFO. Only
1318 conflicts between items in the same TPA list are added. If optional
1319 coalesce list CL is passed in, any copies encountered are added. */
1322 build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
1325 conflict_graph graph;
1330 varray_type partition_link, tpa_to_clear, tpa_nodes;
1335 map = live_var_map (liveinfo);
1336 graph = conflict_graph_new (num_var_partitions (map));
1338 if (tpa_num_trees (tpa) == 0)
1341 live = BITMAP_XMALLOC ();
1343 VARRAY_INT_INIT (partition_link, num_var_partitions (map) + 1, "part_link");
1344 VARRAY_INT_INIT (tpa_nodes, tpa_num_trees (tpa), "tpa nodes");
1345 VARRAY_INT_INIT (tpa_to_clear, 50, "tpa to clear");
1349 block_stmt_iterator bsi;
1352 /* Start with live on exit temporaries. */
1353 bitmap_copy (live, live_on_exit (liveinfo, bb));
1355 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1357 bool is_a_copy = false;
1358 tree stmt = bsi_stmt (bsi);
1361 get_stmt_operands (stmt);
1362 ann = stmt_ann (stmt);
1364 /* A copy between 2 partitions does not introduce an interference
1365 by itself. If they did, you would never be able to coalesce
1366 two things which are copied. If the two variables really do
1367 conflict, they will conflict elsewhere in the program.
1369 This is handled specially here since we may also be interested
1370 in copies between real variables and SSA_NAME variables. We may
1371 be interested in trying to coalesce SSA_NAME variables with
1372 root variables in some cases. */
1374 if (TREE_CODE (stmt) == MODIFY_EXPR)
1376 tree lhs = TREE_OPERAND (stmt, 0);
1377 tree rhs = TREE_OPERAND (stmt, 1);
1381 if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
1382 p1 = var_to_partition (map, lhs);
1386 if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
1387 p2 = var_to_partition (map, rhs);
1391 if (p1 != NO_PARTITION && p2 != NO_PARTITION)
1394 bit = bitmap_bit_p (live, p2);
1395 /* If the RHS is live, make it not live while we add
1396 the conflicts, then make it live again. */
1398 bitmap_clear_bit (live, p2);
1399 add_conflicts_if_valid (tpa, graph, map, live, lhs);
1401 bitmap_set_bit (live, p2);
1403 add_coalesce (cl, p1, p2, 1);
1404 set_if_valid (map, live, rhs);
1412 defs = DEF_OPS (ann);
1413 num = NUM_DEFS (defs);
1414 for (x = 0; x < num; x++)
1416 var_p = DEF_OP_PTR (defs, x);
1417 add_conflicts_if_valid (tpa, graph, map, live, *var_p);
1420 uses = USE_OPS (ann);
1421 num = NUM_USES (uses);
1422 for (x = 0; x < num; x++)
1424 var_p = USE_OP_PTR (uses, x);
1425 set_if_valid (map, live, *var_p);
1430 /* If result of a PHI is unused, then the loops over the statements
1431 will not record any conflicts. However, since the PHI node is
1432 going to be translated out of SSA form we must record a conflict
1433 between the result of the PHI and any variables with are live.
1434 Otherwise the out-of-ssa translation may create incorrect code. */
1435 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1437 tree result = PHI_RESULT (phi);
1438 int p = var_to_partition (map, result);
1440 if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
1441 add_conflicts_if_valid (tpa, graph, map, live, result);
1444 /* Anything which is still live at this point interferes.
1445 In order to implement this efficiently, only conflicts between
1446 partitions which have the same TPA root need be added.
1447 TPA roots which have been seen are tracked in 'tpa_nodes'. A non-zero
1448 entry points to an index into 'partition_link', which then indexes
1449 into itself forming a linked list of partitions sharing a tpa root
1450 which have been seen as live up to this point. Since partitions start
1451 at index zero, all entries in partition_link are (partition + 1).
1453 Conflicts are added between the current partition and any already seen.
1454 tpa_clear contains all the tpa_roots processed, and these are the only
1455 entries which need to be zero'd out for a clean restart. */
1457 EXECUTE_IF_SET_IN_BITMAP (live, 0, x,
1459 i = tpa_find_tree (tpa, x);
1462 int start = VARRAY_INT (tpa_nodes, i);
1463 /* If start is 0, a new root reference list is being started.
1464 Register it to be cleared. */
1466 VARRAY_PUSH_INT (tpa_to_clear, i);
1468 /* Add interferences to other tpa members seen. */
1469 for (y = start; y != 0; y = VARRAY_INT (partition_link, y))
1470 conflict_graph_add (graph, x, y - 1);
1471 VARRAY_INT (tpa_nodes, i) = x + 1;
1472 VARRAY_INT (partition_link, x + 1) = start;
1476 /* Now clear the used tpa root references. */
1477 for (l = 0; l < VARRAY_ACTIVE_SIZE (tpa_to_clear); l++)
1478 VARRAY_INT (tpa_nodes, VARRAY_INT (tpa_to_clear, l)) = 0;
1479 VARRAY_POP_ALL (tpa_to_clear);
1482 BITMAP_XFREE (live);
1487 /* This routine will attempt to coalesce the elements in TPA subject to the
1488 conflicts found in GRAPH. If optional coalesce_list CL is provided,
1489 only coalesces specified within the coalesce list are attempted. Otherwise
1490 an attempt is made to coalesce as many partitions within each TPA grouping
1491 as possible. If DEBUG is provided, debug output will be sent there. */
1494 coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
1495 coalesce_list_p cl, FILE *debug)
1500 /* Attempt to coalesce any items in a coalesce list. */
1503 while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
1507 fprintf (debug, "Coalesce list: (%d)", x);
1508 print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
1509 fprintf (debug, " & (%d)", y);
1510 print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
1513 w = tpa_find_tree (tpa, x);
1514 z = tpa_find_tree (tpa, y);
1515 if (w != z || w == TPA_NONE || z == TPA_NONE)
1520 fprintf (debug, ": Fail, Non-matching TPA's\n");
1522 fprintf (debug, ": Fail %d non TPA.\n", x);
1524 fprintf (debug, ": Fail %d non TPA.\n", y);
1528 var = partition_to_var (map, x);
1529 tmp = partition_to_var (map, y);
1530 x = var_to_partition (map, var);
1531 y = var_to_partition (map, tmp);
1533 fprintf (debug, " [map: %d, %d] ", x, y);
1537 fprintf (debug, ": Already Coalesced.\n");
1540 if (!conflict_graph_conflict_p (graph, x, y))
1542 z = var_union (map, var, tmp);
1543 if (z == NO_PARTITION)
1546 fprintf (debug, ": Unable to perform partition union.\n");
1550 /* z is the new combined partition. We need to remove the other
1551 partition from the list. Set x to be that other partition. */
1554 conflict_graph_merge_regs (graph, x, y);
1555 w = tpa_find_tree (tpa, y);
1556 tpa_remove_partition (tpa, w, y);
1560 conflict_graph_merge_regs (graph, y, x);
1561 w = tpa_find_tree (tpa, x);
1562 tpa_remove_partition (tpa, w, x);
1566 fprintf (debug, ": Success -> %d\n", z);
1570 fprintf (debug, ": Fail due to conflict\n");
1572 /* If using a coalesce list, don't try to coalesce anything else. */
1576 for (x = 0; x < tpa_num_trees (tpa); x++)
1578 while (tpa_first_partition (tpa, x) != TPA_NONE)
1581 /* Coalesce first partition with anything that doesn't conflict. */
1582 y = tpa_first_partition (tpa, x);
1583 tpa_remove_partition (tpa, x, y);
1585 var = partition_to_var (map, y);
1586 /* p1 is the partition representative to which y belongs. */
1587 p1 = var_to_partition (map, var);
1589 for (z = tpa_next_partition (tpa, y);
1591 z = tpa_next_partition (tpa, z))
1593 tmp = partition_to_var (map, z);
1594 /* p2 is the partition representative to which z belongs. */
1595 p2 = var_to_partition (map, tmp);
1598 fprintf (debug, "Coalesce : ");
1599 print_generic_expr (debug, var, TDF_SLIM);
1600 fprintf (debug, " &");
1601 print_generic_expr (debug, tmp, TDF_SLIM);
1602 fprintf (debug, " (%d ,%d)", p1, p2);
1605 /* If partitions are already merged, don't check for conflict. */
1608 tpa_remove_partition (tpa, x, z);
1610 fprintf (debug, ": Already coalesced\n");
1613 if (!conflict_graph_conflict_p (graph, p1, p2))
1616 if (tpa_find_tree (tpa, y) == TPA_NONE
1617 || tpa_find_tree (tpa, z) == TPA_NONE)
1620 fprintf (debug, ": Fail non-TPA member\n");
1623 if ((v = var_union (map, var, tmp)) == NO_PARTITION)
1626 fprintf (debug, ": Fail cannot combine partitions\n");
1630 tpa_remove_partition (tpa, x, z);
1632 conflict_graph_merge_regs (graph, v, z);
1635 /* Update the first partition's representative. */
1636 conflict_graph_merge_regs (graph, v, y);
1640 /* The root variable of the partition may be changed
1642 var = partition_to_var (map, p1);
1645 fprintf (debug, ": Success -> %d\n", v);
1649 fprintf (debug, ": Fail, Conflict\n");
1656 /* Send debug info for coalesce list CL to file F. */
1659 dump_coalesce_list (FILE *f, coalesce_list_p cl)
1661 partition_pair_p node;
1667 fprintf (f, "Coalesce List:\n");
1668 num = num_var_partitions (cl->map);
1669 for (x = 0; x < num; x++)
1675 print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
1676 fprintf (f, "] - ");
1677 for ( ; node; node = node->next)
1679 var = partition_to_var (cl->map, node->second_partition);
1680 print_generic_expr (f, var, TDF_SLIM);
1681 fprintf (f, "(%1d), ", node->cost);
1689 fprintf (f, "Sorted Coalesce list:\n");
1690 for (node = cl->list[0]; node; node = node->next)
1692 fprintf (f, "(%d) ", node->cost);
1693 var = partition_to_var (cl->map, node->first_partition);
1694 print_generic_expr (f, var, TDF_SLIM);
1696 var = partition_to_var (cl->map, node->second_partition);
1697 print_generic_expr (f, var, TDF_SLIM);
1704 /* Output tree_partition_associator object TPA to file F.. */
1707 tpa_dump (FILE *f, tpa_p tpa)
1714 for (x = 0; x < tpa_num_trees (tpa); x++)
1716 print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
1717 fprintf (f, " : (");
1718 for (i = tpa_first_partition (tpa, x);
1720 i = tpa_next_partition (tpa, i))
1722 fprintf (f, "(%d)",i);
1723 print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
1726 #ifdef ENABLE_CHECKING
1727 if (tpa_find_tree (tpa, i) != x)
1728 fprintf (f, "**find tree incorrectly set** ");
1738 /* Output partition map MAP to file F. */
1741 dump_var_map (FILE *f, var_map map)
1747 fprintf (f, "\nPartition map \n\n");
1749 for (x = 0; x < map->num_partitions; x++)
1751 if (map->compact_to_partition != NULL)
1752 p = map->compact_to_partition[x];
1756 if (map->partition_to_var[p] == NULL_TREE)
1760 for (y = 1; y < highest_ssa_version; y++)
1762 p = partition_find (map->var_partition, y);
1763 if (map->partition_to_compact)
1764 p = map->partition_to_compact[p];
1769 fprintf(f, "Partition %d (", x);
1770 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1773 fprintf (f, "%d ", y);
1783 /* Output live range info LIVE to file F, controlled by FLAG. */
1786 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1790 var_map map = live->map;
1792 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1796 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1797 for (i = 0; i < num_var_partitions (map); i++)
1799 if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
1801 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1809 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1813 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1814 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i,
1816 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1824 /* Register partitions in MAP so that we can take VARS out of SSA form.
1825 This requires a walk over all the PHI nodes and all the statements. */
1828 register_ssa_partitions_for_vars (bitmap vars, var_map map)
1832 if (bitmap_first_set_bit (vars) >= 0)
1835 /* Find every instance (SSA_NAME) of variables in VARs and
1836 register a new partition for them. This requires examining
1837 every statement and every PHI node once. */
1840 block_stmt_iterator bsi;
1844 /* Register partitions for SSA_NAMEs appearing in the PHI
1845 nodes in this basic block.
1847 Note we delete PHI nodes in this loop if they are
1848 associated with virtual vars which are going to be
1850 for (phi = phi_nodes (bb); phi; phi = next)
1852 tree result = SSA_NAME_VAR (PHI_RESULT (phi));
1854 next = TREE_CHAIN (phi);
1855 if (bitmap_bit_p (vars, var_ann (result)->uid))
1857 if (! is_gimple_reg (result))
1858 remove_phi_node (phi, NULL_TREE, bb);
1863 /* Register a partition for the result. */
1864 register_ssa_partition (map, PHI_RESULT (phi), 0);
1866 /* Register a partition for each argument as needed. */
1867 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1869 tree arg = PHI_ARG_DEF (phi, i);
1871 if (TREE_CODE (arg) != SSA_NAME)
1873 if (!bitmap_bit_p (vars,
1874 var_ann (SSA_NAME_VAR (arg))->uid))
1877 register_ssa_partition (map, arg, 1);
1883 /* Now register partitions for SSA_NAMEs appearing in each
1884 statement in this block. */
1885 for (bsi = bsi_start (bb); ! bsi_end_p (bsi); bsi_next (&bsi))
1887 stmt_ann_t ann = stmt_ann (bsi_stmt (bsi));
1888 use_optype uses = USE_OPS (ann);
1889 def_optype defs = DEF_OPS (ann);
1892 for (i = 0; i < NUM_USES (uses); i++)
1894 tree op = USE_OP (uses, i);
1896 if (TREE_CODE (op) == SSA_NAME
1897 && bitmap_bit_p (vars, var_ann (SSA_NAME_VAR (op))->uid))
1898 register_ssa_partition (map, op, 1);
1901 for (i = 0; i < NUM_DEFS (defs); i++)
1903 tree op = DEF_OP (defs, i);
1905 if (TREE_CODE (op) == SSA_NAME
1906 && bitmap_bit_p (vars,
1907 var_ann (SSA_NAME_VAR (op))->uid))
1908 register_ssa_partition (map, op, 0);