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, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-inline.h"
38 #include "tree-dump.h"
39 #include "tree-ssa-live.h"
42 static void live_worklist (tree_live_info_p
, int *, int);
43 static tree_live_info_p
new_tree_live_info (var_map
);
44 static inline void set_if_valid (var_map
, bitmap
, tree
);
45 static inline void add_livein_if_notdef (tree_live_info_p
, bitmap
,
47 static inline void register_ssa_partition (var_map
, tree
, bool);
48 static inline void add_conflicts_if_valid (tpa_p
, conflict_graph
,
49 var_map
, bitmap
, tree
);
50 static partition_pair_p
find_partition_pair (coalesce_list_p
, int, int, bool);
52 /* This is where the mapping from SSA version number to real storage variable
55 All SSA versions of the same variable may not ultimately be mapped back to
56 the same real variable. In that instance, we need to detect the live
57 range overlap, and give one of the variable new storage. The vector
58 'partition_to_var' tracks which partition maps to which variable.
60 Given a VAR, it is sometimes desirable to know which partition that VAR
61 represents. There is an additional field in the variable annotation to
62 track that information. */
64 /* Create a variable partition map of SIZE, initialize and return it. */
67 init_var_map (int size
)
71 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
72 map
->var_partition
= partition_new (size
);
74 = (tree
*)xmalloc (size
* sizeof (tree
));
75 memset (map
->partition_to_var
, 0, size
* sizeof (tree
));
77 map
->partition_to_compact
= NULL
;
78 map
->compact_to_partition
= NULL
;
79 map
->num_partitions
= size
;
80 map
->partition_size
= size
;
81 map
->ref_count
= NULL
;
86 /* Free memory associated with MAP. */
89 delete_var_map (var_map map
)
91 free (map
->partition_to_var
);
92 partition_delete (map
->var_partition
);
93 if (map
->partition_to_compact
)
94 free (map
->partition_to_compact
);
95 if (map
->compact_to_partition
)
96 free (map
->compact_to_partition
);
98 free (map
->ref_count
);
103 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
104 Returns the partition which represents the new partition. If the two
105 partitions cannot be combined, NO_PARTITION is returned. */
108 var_union (var_map map
, tree var1
, tree var2
)
111 tree root_var
= NULL_TREE
;
112 tree other_var
= NULL_TREE
;
114 /* This is independent of partition_to_compact. If partition_to_compact is
115 on, then whichever one of these partitions is absorbed will never have a
116 dereference into the partition_to_compact array any more. */
118 if (TREE_CODE (var1
) == SSA_NAME
)
119 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
122 p1
= var_to_partition (map
, var1
);
123 if (map
->compact_to_partition
)
124 p1
= map
->compact_to_partition
[p1
];
128 if (TREE_CODE (var2
) == SSA_NAME
)
129 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
132 p2
= var_to_partition (map
, var2
);
133 if (map
->compact_to_partition
)
134 p2
= map
->compact_to_partition
[p2
];
136 /* If there is no root_var set, or it's not a user variable, set the
137 root_var to this one. */
138 if (!root_var
|| (DECL_P (root_var
) && DECL_IGNORED_P (root_var
)))
140 other_var
= root_var
;
147 gcc_assert (p1
!= NO_PARTITION
);
148 gcc_assert (p2
!= NO_PARTITION
);
153 p3
= partition_union (map
->var_partition
, p1
, p2
);
155 if (map
->partition_to_compact
)
156 p3
= map
->partition_to_compact
[p3
];
159 change_partition_var (map
, root_var
, p3
);
161 change_partition_var (map
, other_var
, p3
);
167 /* Compress the partition numbers in MAP such that they fall in the range
168 0..(num_partitions-1) instead of wherever they turned out during
169 the partitioning exercise. This removes any references to unused
170 partitions, thereby allowing bitmaps and other vectors to be much
171 denser. Compression type is controlled by FLAGS.
173 This is implemented such that compaction doesn't affect partitioning.
174 Ie., once partitions are created and possibly merged, running one
175 or more different kind of compaction will not affect the partitions
176 themselves. Their index might change, but all the same variables will
177 still be members of the same partition group. This allows work on reduced
178 sets, and no loss of information when a larger set is later desired.
180 In particular, coalescing can work on partitions which have 2 or more
181 definitions, and then 'recompact' later to include all the single
182 definitions for assignment to program variables. */
185 compact_var_map (var_map map
, int flags
)
188 int x
, limit
, count
, tmp
, root
, root_i
;
190 root_var_p rv
= NULL
;
192 limit
= map
->partition_size
;
193 used
= sbitmap_alloc (limit
);
196 /* Already compressed? Abandon the old one. */
197 if (map
->partition_to_compact
)
199 free (map
->partition_to_compact
);
200 map
->partition_to_compact
= NULL
;
202 if (map
->compact_to_partition
)
204 free (map
->compact_to_partition
);
205 map
->compact_to_partition
= NULL
;
208 map
->num_partitions
= map
->partition_size
;
210 if (flags
& VARMAP_NO_SINGLE_DEFS
)
211 rv
= root_var_init (map
);
213 map
->partition_to_compact
= (int *)xmalloc (limit
* sizeof (int));
214 memset (map
->partition_to_compact
, 0xff, (limit
* sizeof (int)));
216 /* Find out which partitions are actually referenced. */
218 for (x
= 0; x
< limit
; x
++)
220 tmp
= partition_find (map
->var_partition
, x
);
221 if (!TEST_BIT (used
, tmp
) && map
->partition_to_var
[tmp
] != NULL_TREE
)
223 /* It is referenced, check to see if there is more than one version
224 in the root_var table, if one is available. */
227 root
= root_var_find (rv
, tmp
);
228 root_i
= root_var_first_partition (rv
, root
);
229 /* If there is only one, don't include this in the compaction. */
230 if (root_var_next_partition (rv
, root_i
) == ROOT_VAR_NONE
)
238 /* Build a compacted partitioning. */
241 map
->compact_to_partition
= (int *)xmalloc (count
* sizeof (int));
243 /* SSA renaming begins at 1, so skip 0 when compacting. */
244 EXECUTE_IF_SET_IN_SBITMAP (used
, 1, x
,
246 map
->partition_to_compact
[x
] = count
;
247 map
->compact_to_partition
[count
] = x
;
248 var
= map
->partition_to_var
[x
];
249 if (TREE_CODE (var
) != SSA_NAME
)
250 change_partition_var (map
, var
, count
);
256 free (map
->partition_to_compact
);
257 map
->partition_to_compact
= NULL
;
260 map
->num_partitions
= count
;
263 root_var_delete (rv
);
268 /* This function is used to change the representative variable in MAP for VAR's
269 partition from an SSA_NAME variable to a regular variable. This allows
270 partitions to be mapped back to real variables. */
273 change_partition_var (var_map map
, tree var
, int part
)
277 gcc_assert (TREE_CODE (var
) != SSA_NAME
);
280 ann
->out_of_ssa_tag
= 1;
281 VAR_ANN_PARTITION (ann
) = part
;
282 if (map
->compact_to_partition
)
283 map
->partition_to_var
[map
->compact_to_partition
[part
]] = var
;
287 /* Helper function for mark_all_vars_used, called via walk_tree. */
290 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
,
291 void *data ATTRIBUTE_UNUSED
)
295 /* Only need to mark VAR_DECLS; parameters and return results are not
296 eliminated as unused. */
297 if (TREE_CODE (t
) == VAR_DECL
)
300 if (IS_TYPE_OR_DECL_P (t
))
306 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
307 eliminated during the tree->rtl conversion process. */
310 mark_all_vars_used (tree
*expr_p
)
312 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
315 /* This function looks through the program and uses FLAGS to determine what
316 SSA versioned variables are given entries in a new partition table. This
317 new partition map is returned. */
320 create_ssa_var_map (int flags
)
322 block_stmt_iterator bsi
;
328 #ifdef ENABLE_CHECKING
329 sbitmap used_in_real_ops
;
330 sbitmap used_in_virtual_ops
;
333 map
= init_var_map (num_ssa_names
+ 1);
335 #ifdef ENABLE_CHECKING
336 used_in_real_ops
= sbitmap_alloc (num_referenced_vars
);
337 sbitmap_zero (used_in_real_ops
);
339 used_in_virtual_ops
= sbitmap_alloc (num_referenced_vars
);
340 sbitmap_zero (used_in_virtual_ops
);
343 if (flags
& SSA_VAR_MAP_REF_COUNT
)
346 = (int *)xmalloc (((num_ssa_names
+ 1) * sizeof (int)));
347 memset (map
->ref_count
, 0, (num_ssa_names
+ 1) * sizeof (int));
353 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
356 register_ssa_partition (map
, PHI_RESULT (phi
), false);
357 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
359 arg
= PHI_ARG_DEF (phi
, i
);
360 if (TREE_CODE (arg
) == SSA_NAME
)
361 register_ssa_partition (map
, arg
, true);
363 mark_all_vars_used (&PHI_ARG_DEF_TREE (phi
, i
));
367 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
369 stmt
= bsi_stmt (bsi
);
371 /* Register USE and DEF operands in each statement. */
372 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
374 register_ssa_partition (map
, use
, true);
376 #ifdef ENABLE_CHECKING
377 SET_BIT (used_in_real_ops
, var_ann (SSA_NAME_VAR (use
))->uid
);
381 FOR_EACH_SSA_TREE_OPERAND (dest
, stmt
, iter
, SSA_OP_DEF
)
383 register_ssa_partition (map
, dest
, false);
385 #ifdef ENABLE_CHECKING
386 SET_BIT (used_in_real_ops
, var_ann (SSA_NAME_VAR (dest
))->uid
);
390 #ifdef ENABLE_CHECKING
391 /* Validate that virtual ops don't get used in funny ways. */
392 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
,
393 SSA_OP_VIRTUAL_USES
| SSA_OP_VMUSTDEF
)
395 SET_BIT (used_in_virtual_ops
, var_ann (SSA_NAME_VAR (use
))->uid
);
398 #endif /* ENABLE_CHECKING */
400 mark_all_vars_used (bsi_stmt_ptr (bsi
));
404 #if defined ENABLE_CHECKING
407 sbitmap both
= sbitmap_alloc (num_referenced_vars
);
408 sbitmap_a_and_b (both
, used_in_real_ops
, used_in_virtual_ops
);
409 if (sbitmap_first_set_bit (both
) >= 0)
411 EXECUTE_IF_SET_IN_SBITMAP (both
, 0, i
,
412 fprintf (stderr
, "Variable %s used in real and virtual operands\n",
413 get_name (referenced_var (i
))));
414 internal_error ("SSA corruption");
417 sbitmap_free (used_in_real_ops
);
418 sbitmap_free (used_in_virtual_ops
);
427 /* Allocate and return a new live range information object base on MAP. */
429 static tree_live_info_p
430 new_tree_live_info (var_map map
)
432 tree_live_info_p live
;
435 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
437 live
->num_blocks
= last_basic_block
;
439 live
->global
= BITMAP_ALLOC (NULL
);
441 live
->livein
= (bitmap
*)xmalloc (num_var_partitions (map
) * sizeof (bitmap
));
442 for (x
= 0; x
< num_var_partitions (map
); x
++)
443 live
->livein
[x
] = BITMAP_ALLOC (NULL
);
445 /* liveout is deferred until it is actually requested. */
446 live
->liveout
= NULL
;
451 /* Free storage for live range info object LIVE. */
454 delete_tree_live_info (tree_live_info_p live
)
459 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
460 BITMAP_FREE (live
->liveout
[x
]);
461 free (live
->liveout
);
465 for (x
= num_var_partitions (live
->map
) - 1; x
>= 0; x
--)
466 BITMAP_FREE (live
->livein
[x
]);
470 BITMAP_FREE (live
->global
);
476 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
477 for partition I. STACK is a varray used for temporary memory which is
478 passed in rather than being allocated on every call. */
481 live_worklist (tree_live_info_p live
, int *stack
, int i
)
485 basic_block def_bb
= NULL
;
487 var_map map
= live
->map
;
492 var
= partition_to_var (map
, i
);
493 if (SSA_NAME_DEF_STMT (var
))
494 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
496 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[i
], 0, b
, bi
)
505 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (b
)->preds
)
506 if (e
->src
!= ENTRY_BLOCK_PTR
)
508 /* Its not live on entry to the block its defined in. */
509 if (e
->src
== def_bb
)
511 if (!bitmap_bit_p (live
->livein
[i
], e
->src
->index
))
513 bitmap_set_bit (live
->livein
[i
], e
->src
->index
);
514 *tos
++ = e
->src
->index
;
521 /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
524 set_if_valid (var_map map
, bitmap vec
, tree var
)
526 int p
= var_to_partition (map
, var
);
527 if (p
!= NO_PARTITION
)
528 bitmap_set_bit (vec
, p
);
532 /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
533 global bit for it in the LIVE object. BB is the block being processed. */
536 add_livein_if_notdef (tree_live_info_p live
, bitmap def_vec
,
537 tree var
, basic_block bb
)
539 int p
= var_to_partition (live
->map
, var
);
540 if (p
== NO_PARTITION
|| bb
== ENTRY_BLOCK_PTR
)
542 if (!bitmap_bit_p (def_vec
, p
))
544 bitmap_set_bit (live
->livein
[p
], bb
->index
);
545 bitmap_set_bit (live
->global
, p
);
550 /* Given partition map MAP, calculate all the live on entry bitmaps for
551 each basic block. Return a live info object. */
554 calculate_live_on_entry (var_map map
)
556 tree_live_info_p live
;
564 block_stmt_iterator bsi
;
567 #ifdef ENABLE_CHECKING
572 saw_def
= BITMAP_ALLOC (NULL
);
574 live
= new_tree_live_info (map
);
578 bitmap_clear (saw_def
);
580 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
582 for (i
= 0; i
< (unsigned)PHI_NUM_ARGS (phi
); i
++)
584 var
= PHI_ARG_DEF (phi
, i
);
585 if (!phi_ssa_name_p (var
))
587 stmt
= SSA_NAME_DEF_STMT (var
);
588 e
= EDGE_PRED (bb
, i
);
590 /* Any uses in PHIs which either don't have def's or are not
591 defined in the block from which the def comes, will be live
592 on entry to that block. */
593 if (!stmt
|| e
->src
!= bb_for_stmt (stmt
))
594 add_livein_if_notdef (live
, saw_def
, var
, e
->src
);
598 /* Don't mark PHI results as defined until all the PHI nodes have
599 been processed. If the PHI sequence is:
602 The a_3 referred to in b_3's PHI node is the one incoming on the
603 edge, *not* the PHI node just seen. */
605 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
607 var
= PHI_RESULT (phi
);
608 set_if_valid (map
, saw_def
, var
);
611 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
613 stmt
= bsi_stmt (bsi
);
615 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
617 add_livein_if_notdef (live
, saw_def
, op
, bb
);
620 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
622 set_if_valid (map
, saw_def
, op
);
627 stack
= xmalloc (sizeof (int) * last_basic_block
);
628 EXECUTE_IF_SET_IN_BITMAP (live
->global
, 0, i
, bi
)
630 live_worklist (live
, stack
, i
);
634 #ifdef ENABLE_CHECKING
635 /* Check for live on entry partitions and report those with a DEF in
636 the program. This will typically mean an optimization has done
639 bb
= ENTRY_BLOCK_PTR
;
641 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
643 int entry_block
= e
->dest
->index
;
644 if (e
->dest
== EXIT_BLOCK_PTR
)
646 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
650 var
= partition_to_var (map
, i
);
651 stmt
= SSA_NAME_DEF_STMT (var
);
652 tmp
= bb_for_stmt (stmt
);
653 d
= default_def (SSA_NAME_VAR (var
));
655 if (bitmap_bit_p (live_entry_blocks (live
, i
), entry_block
))
657 if (!IS_EMPTY_STMT (stmt
))
660 print_generic_expr (stderr
, var
, TDF_SLIM
);
661 fprintf (stderr
, " is defined ");
663 fprintf (stderr
, " in BB%d, ", tmp
->index
);
664 fprintf (stderr
, "by:\n");
665 print_generic_expr (stderr
, stmt
, TDF_SLIM
);
666 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
668 fprintf (stderr
, " So it appears to have multiple defs.\n");
675 print_generic_expr (stderr
, var
, TDF_SLIM
);
676 fprintf (stderr
, " is live-on-entry to BB%d ",entry_block
);
679 fprintf (stderr
, " but is not the default def of ");
680 print_generic_expr (stderr
, d
, TDF_SLIM
);
681 fprintf (stderr
, "\n");
684 fprintf (stderr
, " and there is no default def.\n");
691 /* The only way this var shouldn't be marked live on entry is
692 if it occurs in a PHI argument of the block. */
694 for (phi
= phi_nodes (e
->dest
);
696 phi
= PHI_CHAIN (phi
))
698 for (z
= 0; z
< PHI_NUM_ARGS (phi
); z
++)
699 if (var
== PHI_ARG_DEF (phi
, z
))
708 print_generic_expr (stderr
, var
, TDF_SLIM
);
709 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
711 fprintf (stderr
, "but it is a default def so it should be.\n");
715 gcc_assert (num
<= 0);
718 BITMAP_FREE (saw_def
);
724 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
727 calculate_live_on_exit (tree_live_info_p liveinfo
)
736 var_map map
= liveinfo
->map
;
738 on_exit
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
739 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
740 on_exit
[x
] = BITMAP_ALLOC (NULL
);
742 /* Set all the live-on-exit bits for uses in PHIs. */
745 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
746 for (i
= 0; i
< (unsigned)PHI_NUM_ARGS (phi
); i
++)
748 t
= PHI_ARG_DEF (phi
, i
);
749 e
= PHI_ARG_EDGE (phi
, i
);
750 if (!phi_ssa_name_p (t
) || e
->src
== ENTRY_BLOCK_PTR
)
752 set_if_valid (map
, on_exit
[e
->src
->index
], t
);
756 /* Set live on exit for all predecessors of live on entry's. */
757 for (i
= 0; i
< num_var_partitions (map
); i
++)
761 on_entry
= live_entry_blocks (liveinfo
, i
);
762 EXECUTE_IF_SET_IN_BITMAP (on_entry
, 0, b
, bi
)
765 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (b
)->preds
)
766 if (e
->src
!= ENTRY_BLOCK_PTR
)
767 bitmap_set_bit (on_exit
[e
->src
->index
], i
);
771 liveinfo
->liveout
= on_exit
;
775 /* Initialize a tree_partition_associator object using MAP. */
778 tpa_init (var_map map
)
781 int num_partitions
= num_var_partitions (map
);
784 if (num_partitions
== 0)
787 tpa
= (tpa_p
) xmalloc (sizeof (struct tree_partition_associator_d
));
789 tpa
->uncompressed_num
= -1;
791 tpa
->next_partition
= (int *)xmalloc (num_partitions
* sizeof (int));
792 memset (tpa
->next_partition
, TPA_NONE
, num_partitions
* sizeof (int));
794 tpa
->partition_to_tree_map
= (int *)xmalloc (num_partitions
* sizeof (int));
795 memset (tpa
->partition_to_tree_map
, TPA_NONE
, num_partitions
* sizeof (int));
797 x
= MAX (40, (num_partitions
/ 20));
798 VARRAY_TREE_INIT (tpa
->trees
, x
, "trees");
799 VARRAY_INT_INIT (tpa
->first_partition
, x
, "first_partition");
806 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
809 tpa_remove_partition (tpa_p tpa
, int tree_index
, int partition_index
)
813 i
= tpa_first_partition (tpa
, tree_index
);
814 if (i
== partition_index
)
816 VARRAY_INT (tpa
->first_partition
, tree_index
) = tpa
->next_partition
[i
];
820 for ( ; i
!= TPA_NONE
; i
= tpa_next_partition (tpa
, i
))
822 if (tpa
->next_partition
[i
] == partition_index
)
824 tpa
->next_partition
[i
] = tpa
->next_partition
[partition_index
];
832 /* Free the memory used by tree_partition_associator object TPA. */
835 tpa_delete (tpa_p tpa
)
840 free (tpa
->partition_to_tree_map
);
841 free (tpa
->next_partition
);
846 /* This function will remove any tree entries from TPA which have only a single
847 element. This will help keep the size of the conflict graph down. The
848 function returns the number of remaining tree lists. */
851 tpa_compact (tpa_p tpa
)
853 int last
, x
, y
, first
, swap_i
;
856 /* Find the last list which has more than 1 partition. */
857 for (last
= tpa
->num_trees
- 1; last
> 0; last
--)
859 first
= tpa_first_partition (tpa
, last
);
860 if (tpa_next_partition (tpa
, first
) != NO_PARTITION
)
867 first
= tpa_first_partition (tpa
, x
);
869 /* If there is not more than one partition, swap with the current end
871 if (tpa_next_partition (tpa
, first
) == NO_PARTITION
)
873 swap_t
= VARRAY_TREE (tpa
->trees
, last
);
874 swap_i
= VARRAY_INT (tpa
->first_partition
, last
);
876 /* Update the last entry. Since it is known to only have one
877 partition, there is nothing else to update. */
878 VARRAY_TREE (tpa
->trees
, last
) = VARRAY_TREE (tpa
->trees
, x
);
879 VARRAY_INT (tpa
->first_partition
, last
)
880 = VARRAY_INT (tpa
->first_partition
, x
);
881 tpa
->partition_to_tree_map
[tpa_first_partition (tpa
, last
)] = last
;
883 /* Since this list is known to have more than one partition, update
884 the list owner entries. */
885 VARRAY_TREE (tpa
->trees
, x
) = swap_t
;
886 VARRAY_INT (tpa
->first_partition
, x
) = swap_i
;
887 for (y
= tpa_first_partition (tpa
, x
);
889 y
= tpa_next_partition (tpa
, y
))
890 tpa
->partition_to_tree_map
[y
] = x
;
892 /* Ensure last is a list with more than one partition. */
894 for (; last
> x
; last
--)
896 first
= tpa_first_partition (tpa
, last
);
897 if (tpa_next_partition (tpa
, first
) != NO_PARTITION
)
904 first
= tpa_first_partition (tpa
, x
);
905 if (tpa_next_partition (tpa
, first
) != NO_PARTITION
)
907 tpa
->uncompressed_num
= tpa
->num_trees
;
913 /* Initialize a root_var object with SSA partitions from MAP which are based
914 on each root variable. */
917 root_var_init (var_map map
)
920 int num_partitions
= num_var_partitions (map
);
930 seen
= sbitmap_alloc (num_partitions
);
933 /* Start at the end and work towards the front. This will provide a list
934 that is ordered from smallest to largest. */
935 for (x
= num_partitions
- 1; x
>= 0; x
--)
937 t
= partition_to_var (map
, x
);
939 /* The var map may not be compacted yet, so check for NULL. */
943 p
= var_to_partition (map
, t
);
945 gcc_assert (p
!= NO_PARTITION
);
947 /* Make sure we only put coalesced partitions into the list once. */
948 if (TEST_BIT (seen
, p
))
951 if (TREE_CODE (t
) == SSA_NAME
)
952 t
= SSA_NAME_VAR (t
);
954 if (ann
->root_var_processed
)
956 rv
->next_partition
[p
] = VARRAY_INT (rv
->first_partition
,
957 VAR_ANN_ROOT_INDEX (ann
));
958 VARRAY_INT (rv
->first_partition
, VAR_ANN_ROOT_INDEX (ann
)) = p
;
962 ann
->root_var_processed
= 1;
963 VAR_ANN_ROOT_INDEX (ann
) = rv
->num_trees
++;
964 VARRAY_PUSH_TREE (rv
->trees
, t
);
965 VARRAY_PUSH_INT (rv
->first_partition
, p
);
967 rv
->partition_to_tree_map
[p
] = VAR_ANN_ROOT_INDEX (ann
);
970 /* Reset the out_of_ssa_tag flag on each variable for later use. */
971 for (x
= 0; x
< rv
->num_trees
; x
++)
973 t
= VARRAY_TREE (rv
->trees
, x
);
974 var_ann (t
)->root_var_processed
= 0;
982 /* Initialize a type_var structure which associates all the partitions in MAP
983 of the same type to the type node's index. Volatiles are ignored. */
986 type_var_init (var_map map
)
990 int num_partitions
= num_var_partitions (map
);
994 seen
= sbitmap_alloc (num_partitions
);
1001 for (x
= num_partitions
- 1; x
>= 0; x
--)
1003 t
= partition_to_var (map
, x
);
1005 /* Disallow coalescing of these types of variables. */
1007 || TREE_THIS_VOLATILE (t
)
1008 || TREE_CODE (t
) == RESULT_DECL
1009 || TREE_CODE (t
) == PARM_DECL
1011 && (DECL_REGISTER (t
)
1012 || !DECL_IGNORED_P (t
)
1013 || DECL_RTL_SET_P (t
))))
1016 p
= var_to_partition (map
, t
);
1018 gcc_assert (p
!= NO_PARTITION
);
1020 /* If partitions have been coalesced, only add the representative
1021 for the partition to the list once. */
1022 if (TEST_BIT (seen
, p
))
1027 /* Find the list for this type. */
1028 for (y
= 0; y
< tv
->num_trees
; y
++)
1029 if (t
== VARRAY_TREE (tv
->trees
, y
))
1031 if (y
== tv
->num_trees
)
1034 VARRAY_PUSH_TREE (tv
->trees
, t
);
1035 VARRAY_PUSH_INT (tv
->first_partition
, p
);
1039 tv
->next_partition
[p
] = VARRAY_INT (tv
->first_partition
, y
);
1040 VARRAY_INT (tv
->first_partition
, y
) = p
;
1042 tv
->partition_to_tree_map
[p
] = y
;
1044 sbitmap_free (seen
);
1049 /* Create a new coalesce list object from MAP and return it. */
1052 create_coalesce_list (var_map map
)
1054 coalesce_list_p list
;
1056 list
= (coalesce_list_p
) xmalloc (sizeof (struct coalesce_list_d
));
1059 list
->add_mode
= true;
1060 list
->list
= (partition_pair_p
*) xcalloc (num_var_partitions (map
),
1061 sizeof (struct partition_pair_d
));
1066 /* Delete coalesce list CL. */
1069 delete_coalesce_list (coalesce_list_p cl
)
1076 /* Find a matching coalesce pair object in CL for partitions P1 and P2. If
1077 one isn't found, return NULL if CREATE is false, otherwise create a new
1078 coalesce pair object and return it. */
1080 static partition_pair_p
1081 find_partition_pair (coalesce_list_p cl
, int p1
, int p2
, bool create
)
1083 partition_pair_p node
, tmp
;
1086 /* Normalize so that p1 is the smaller value. */
1096 /* The list is sorted such that if we find a value greater than p2,
1097 p2 is not in the list. */
1098 for (node
= cl
->list
[p1
]; node
; node
= node
->next
)
1100 if (node
->second_partition
== p2
)
1103 if (node
->second_partition
> p2
)
1111 node
= (partition_pair_p
) xmalloc (sizeof (struct partition_pair_d
));
1112 node
->first_partition
= p1
;
1113 node
->second_partition
= p2
;
1118 node
->next
= tmp
->next
;
1123 /* This is now the first node in the list. */
1124 node
->next
= cl
->list
[p1
];
1125 cl
->list
[p1
] = node
;
1132 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
1135 add_coalesce (coalesce_list_p cl
, int p1
, int p2
, int value
)
1137 partition_pair_p node
;
1139 gcc_assert (cl
->add_mode
);
1144 node
= find_partition_pair (cl
, p1
, p2
, true);
1146 node
->cost
+= value
;
1150 /* Comparison function to allow qsort to sort P1 and P2 in descending order. */
1153 int compare_pairs (const void *p1
, const void *p2
)
1155 return (*(partition_pair_p
*)p2
)->cost
- (*(partition_pair_p
*)p1
)->cost
;
1159 /* Prepare CL for removal of preferred pairs. When finished, list element
1160 0 has all the coalesce pairs, sorted in order from most important coalesce
1161 to least important. */
1164 sort_coalesce_list (coalesce_list_p cl
)
1166 unsigned x
, num
, count
;
1167 partition_pair_p chain
, p
;
1168 partition_pair_p
*list
;
1170 gcc_assert (cl
->add_mode
);
1172 cl
->add_mode
= false;
1174 /* Compact the array of lists to a single list, and count the elements. */
1177 for (x
= 0; x
< num_var_partitions (cl
->map
); x
++)
1178 if (cl
->list
[x
] != NULL
)
1180 for (p
= cl
->list
[x
]; p
->next
!= NULL
; p
= p
->next
)
1184 chain
= cl
->list
[x
];
1188 /* Only call qsort if there are more than 2 items. */
1191 list
= xmalloc (sizeof (partition_pair_p
) * num
);
1193 for (p
= chain
; p
!= NULL
; p
= p
->next
)
1196 gcc_assert (count
== num
);
1198 qsort (list
, count
, sizeof (partition_pair_p
), compare_pairs
);
1201 for (x
= 1; x
< num
; x
++)
1207 cl
->list
[0] = list
[0];
1212 cl
->list
[0] = chain
;
1215 /* Simply swap the two elements if they are in the wrong order. */
1216 if (chain
->cost
< chain
->next
->cost
)
1218 cl
->list
[0] = chain
->next
;
1219 cl
->list
[0]->next
= chain
;
1227 /* Retrieve the best remaining pair to coalesce from CL. Returns the 2
1228 partitions via P1 and P2. Their calculated cost is returned by the function.
1229 NO_BEST_COALESCE is returned if the coalesce list is empty. */
1232 pop_best_coalesce (coalesce_list_p cl
, int *p1
, int *p2
)
1234 partition_pair_p node
;
1237 gcc_assert (!cl
->add_mode
);
1241 return NO_BEST_COALESCE
;
1243 cl
->list
[0] = node
->next
;
1245 *p1
= node
->first_partition
;
1246 *p2
= node
->second_partition
;
1254 /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
1255 VAR and any other live partitions in VEC which are associated via TPA.
1256 Reset the live bit in VEC. */
1259 add_conflicts_if_valid (tpa_p tpa
, conflict_graph graph
,
1260 var_map map
, bitmap vec
, tree var
)
1263 p
= var_to_partition (map
, var
);
1264 if (p
!= NO_PARTITION
)
1266 bitmap_clear_bit (vec
, p
);
1267 first
= tpa_find_tree (tpa
, p
);
1268 /* If find returns nothing, this object isn't interesting. */
1269 if (first
== TPA_NONE
)
1271 /* Only add interferences between objects in the same list. */
1272 for (y
= tpa_first_partition (tpa
, first
);
1274 y
= tpa_next_partition (tpa
, y
))
1276 if (bitmap_bit_p (vec
, y
))
1277 conflict_graph_add (graph
, p
, y
);
1283 /* Return a conflict graph for the information contained in LIVE_INFO. Only
1284 conflicts between items in the same TPA list are added. If optional
1285 coalesce list CL is passed in, any copies encountered are added. */
1288 build_tree_conflict_graph (tree_live_info_p liveinfo
, tpa_p tpa
,
1291 conflict_graph graph
;
1296 varray_type partition_link
, tpa_to_clear
, tpa_nodes
;
1301 map
= live_var_map (liveinfo
);
1302 graph
= conflict_graph_new (num_var_partitions (map
));
1304 if (tpa_num_trees (tpa
) == 0)
1307 live
= BITMAP_ALLOC (NULL
);
1309 VARRAY_INT_INIT (partition_link
, num_var_partitions (map
) + 1, "part_link");
1310 VARRAY_INT_INIT (tpa_nodes
, tpa_num_trees (tpa
), "tpa nodes");
1311 VARRAY_INT_INIT (tpa_to_clear
, 50, "tpa to clear");
1315 block_stmt_iterator bsi
;
1318 /* Start with live on exit temporaries. */
1319 bitmap_copy (live
, live_on_exit (liveinfo
, bb
));
1321 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
); bsi_prev (&bsi
))
1323 bool is_a_copy
= false;
1324 tree stmt
= bsi_stmt (bsi
);
1326 /* A copy between 2 partitions does not introduce an interference
1327 by itself. If they did, you would never be able to coalesce
1328 two things which are copied. If the two variables really do
1329 conflict, they will conflict elsewhere in the program.
1331 This is handled specially here since we may also be interested
1332 in copies between real variables and SSA_NAME variables. We may
1333 be interested in trying to coalesce SSA_NAME variables with
1334 root variables in some cases. */
1336 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1338 tree lhs
= TREE_OPERAND (stmt
, 0);
1339 tree rhs
= TREE_OPERAND (stmt
, 1);
1343 if (DECL_P (lhs
) || TREE_CODE (lhs
) == SSA_NAME
)
1344 p1
= var_to_partition (map
, lhs
);
1348 if (DECL_P (rhs
) || TREE_CODE (rhs
) == SSA_NAME
)
1349 p2
= var_to_partition (map
, rhs
);
1353 if (p1
!= NO_PARTITION
&& p2
!= NO_PARTITION
)
1356 bit
= bitmap_bit_p (live
, p2
);
1357 /* If the RHS is live, make it not live while we add
1358 the conflicts, then make it live again. */
1360 bitmap_clear_bit (live
, p2
);
1361 add_conflicts_if_valid (tpa
, graph
, map
, live
, lhs
);
1363 bitmap_set_bit (live
, p2
);
1365 add_coalesce (cl
, p1
, p2
, 1);
1366 set_if_valid (map
, live
, rhs
);
1373 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_DEF
)
1375 add_conflicts_if_valid (tpa
, graph
, map
, live
, var
);
1378 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_USE
)
1380 set_if_valid (map
, live
, var
);
1385 /* If result of a PHI is unused, then the loops over the statements
1386 will not record any conflicts. However, since the PHI node is
1387 going to be translated out of SSA form we must record a conflict
1388 between the result of the PHI and any variables with are live.
1389 Otherwise the out-of-ssa translation may create incorrect code. */
1390 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1392 tree result
= PHI_RESULT (phi
);
1393 int p
= var_to_partition (map
, result
);
1395 if (p
!= NO_PARTITION
&& ! bitmap_bit_p (live
, p
))
1396 add_conflicts_if_valid (tpa
, graph
, map
, live
, result
);
1399 /* Anything which is still live at this point interferes.
1400 In order to implement this efficiently, only conflicts between
1401 partitions which have the same TPA root need be added.
1402 TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
1403 entry points to an index into 'partition_link', which then indexes
1404 into itself forming a linked list of partitions sharing a tpa root
1405 which have been seen as live up to this point. Since partitions start
1406 at index zero, all entries in partition_link are (partition + 1).
1408 Conflicts are added between the current partition and any already seen.
1409 tpa_clear contains all the tpa_roots processed, and these are the only
1410 entries which need to be zero'd out for a clean restart. */
1412 EXECUTE_IF_SET_IN_BITMAP (live
, 0, x
, bi
)
1414 i
= tpa_find_tree (tpa
, x
);
1415 if (i
!= (unsigned)TPA_NONE
)
1417 int start
= VARRAY_INT (tpa_nodes
, i
);
1418 /* If start is 0, a new root reference list is being started.
1419 Register it to be cleared. */
1421 VARRAY_PUSH_INT (tpa_to_clear
, i
);
1423 /* Add interferences to other tpa members seen. */
1424 for (y
= start
; y
!= 0; y
= VARRAY_INT (partition_link
, y
))
1425 conflict_graph_add (graph
, x
, y
- 1);
1426 VARRAY_INT (tpa_nodes
, i
) = x
+ 1;
1427 VARRAY_INT (partition_link
, x
+ 1) = start
;
1431 /* Now clear the used tpa root references. */
1432 for (l
= 0; l
< VARRAY_ACTIVE_SIZE (tpa_to_clear
); l
++)
1433 VARRAY_INT (tpa_nodes
, VARRAY_INT (tpa_to_clear
, l
)) = 0;
1434 VARRAY_POP_ALL (tpa_to_clear
);
1442 /* This routine will attempt to coalesce the elements in TPA subject to the
1443 conflicts found in GRAPH. If optional coalesce_list CL is provided,
1444 only coalesces specified within the coalesce list are attempted. Otherwise
1445 an attempt is made to coalesce as many partitions within each TPA grouping
1446 as possible. If DEBUG is provided, debug output will be sent there. */
1449 coalesce_tpa_members (tpa_p tpa
, conflict_graph graph
, var_map map
,
1450 coalesce_list_p cl
, FILE *debug
)
1455 /* Attempt to coalesce any items in a coalesce list. */
1458 while (pop_best_coalesce (cl
, &x
, &y
) != NO_BEST_COALESCE
)
1462 fprintf (debug
, "Coalesce list: (%d)", x
);
1463 print_generic_expr (debug
, partition_to_var (map
, x
), TDF_SLIM
);
1464 fprintf (debug
, " & (%d)", y
);
1465 print_generic_expr (debug
, partition_to_var (map
, y
), TDF_SLIM
);
1468 w
= tpa_find_tree (tpa
, x
);
1469 z
= tpa_find_tree (tpa
, y
);
1470 if (w
!= z
|| w
== TPA_NONE
|| z
== TPA_NONE
)
1475 fprintf (debug
, ": Fail, Non-matching TPA's\n");
1477 fprintf (debug
, ": Fail %d non TPA.\n", x
);
1479 fprintf (debug
, ": Fail %d non TPA.\n", y
);
1483 var
= partition_to_var (map
, x
);
1484 tmp
= partition_to_var (map
, y
);
1485 x
= var_to_partition (map
, var
);
1486 y
= var_to_partition (map
, tmp
);
1488 fprintf (debug
, " [map: %d, %d] ", x
, y
);
1492 fprintf (debug
, ": Already Coalesced.\n");
1495 if (!conflict_graph_conflict_p (graph
, x
, y
))
1497 z
= var_union (map
, var
, tmp
);
1498 if (z
== NO_PARTITION
)
1501 fprintf (debug
, ": Unable to perform partition union.\n");
1505 /* z is the new combined partition. We need to remove the other
1506 partition from the list. Set x to be that other partition. */
1509 conflict_graph_merge_regs (graph
, x
, y
);
1510 w
= tpa_find_tree (tpa
, y
);
1511 tpa_remove_partition (tpa
, w
, y
);
1515 conflict_graph_merge_regs (graph
, y
, x
);
1516 w
= tpa_find_tree (tpa
, x
);
1517 tpa_remove_partition (tpa
, w
, x
);
1521 fprintf (debug
, ": Success -> %d\n", z
);
1525 fprintf (debug
, ": Fail due to conflict\n");
1527 /* If using a coalesce list, don't try to coalesce anything else. */
1531 for (x
= 0; x
< tpa_num_trees (tpa
); x
++)
1533 while (tpa_first_partition (tpa
, x
) != TPA_NONE
)
1536 /* Coalesce first partition with anything that doesn't conflict. */
1537 y
= tpa_first_partition (tpa
, x
);
1538 tpa_remove_partition (tpa
, x
, y
);
1540 var
= partition_to_var (map
, y
);
1541 /* p1 is the partition representative to which y belongs. */
1542 p1
= var_to_partition (map
, var
);
1544 for (z
= tpa_next_partition (tpa
, y
);
1546 z
= tpa_next_partition (tpa
, z
))
1548 tmp
= partition_to_var (map
, z
);
1549 /* p2 is the partition representative to which z belongs. */
1550 p2
= var_to_partition (map
, tmp
);
1553 fprintf (debug
, "Coalesce : ");
1554 print_generic_expr (debug
, var
, TDF_SLIM
);
1555 fprintf (debug
, " &");
1556 print_generic_expr (debug
, tmp
, TDF_SLIM
);
1557 fprintf (debug
, " (%d ,%d)", p1
, p2
);
1560 /* If partitions are already merged, don't check for conflict. */
1563 tpa_remove_partition (tpa
, x
, z
);
1565 fprintf (debug
, ": Already coalesced\n");
1568 if (!conflict_graph_conflict_p (graph
, p1
, p2
))
1571 if (tpa_find_tree (tpa
, y
) == TPA_NONE
1572 || tpa_find_tree (tpa
, z
) == TPA_NONE
)
1575 fprintf (debug
, ": Fail non-TPA member\n");
1578 if ((v
= var_union (map
, var
, tmp
)) == NO_PARTITION
)
1581 fprintf (debug
, ": Fail cannot combine partitions\n");
1585 tpa_remove_partition (tpa
, x
, z
);
1587 conflict_graph_merge_regs (graph
, v
, z
);
1590 /* Update the first partition's representative. */
1591 conflict_graph_merge_regs (graph
, v
, y
);
1595 /* The root variable of the partition may be changed
1597 var
= partition_to_var (map
, p1
);
1600 fprintf (debug
, ": Success -> %d\n", v
);
1604 fprintf (debug
, ": Fail, Conflict\n");
1611 /* Send debug info for coalesce list CL to file F. */
1614 dump_coalesce_list (FILE *f
, coalesce_list_p cl
)
1616 partition_pair_p node
;
1622 fprintf (f
, "Coalesce List:\n");
1623 num
= num_var_partitions (cl
->map
);
1624 for (x
= 0; x
< num
; x
++)
1630 print_generic_expr (f
, partition_to_var (cl
->map
, x
), TDF_SLIM
);
1631 fprintf (f
, "] - ");
1632 for ( ; node
; node
= node
->next
)
1634 var
= partition_to_var (cl
->map
, node
->second_partition
);
1635 print_generic_expr (f
, var
, TDF_SLIM
);
1636 fprintf (f
, "(%1d), ", node
->cost
);
1644 fprintf (f
, "Sorted Coalesce list:\n");
1645 for (node
= cl
->list
[0]; node
; node
= node
->next
)
1647 fprintf (f
, "(%d) ", node
->cost
);
1648 var
= partition_to_var (cl
->map
, node
->first_partition
);
1649 print_generic_expr (f
, var
, TDF_SLIM
);
1651 var
= partition_to_var (cl
->map
, node
->second_partition
);
1652 print_generic_expr (f
, var
, TDF_SLIM
);
1659 /* Output tree_partition_associator object TPA to file F.. */
1662 tpa_dump (FILE *f
, tpa_p tpa
)
1669 for (x
= 0; x
< tpa_num_trees (tpa
); x
++)
1671 print_generic_expr (f
, tpa_tree (tpa
, x
), TDF_SLIM
);
1672 fprintf (f
, " : (");
1673 for (i
= tpa_first_partition (tpa
, x
);
1675 i
= tpa_next_partition (tpa
, i
))
1677 fprintf (f
, "(%d)",i
);
1678 print_generic_expr (f
, partition_to_var (tpa
->map
, i
), TDF_SLIM
);
1681 #ifdef ENABLE_CHECKING
1682 if (tpa_find_tree (tpa
, i
) != x
)
1683 fprintf (f
, "**find tree incorrectly set** ");
1693 /* Output partition map MAP to file F. */
1696 dump_var_map (FILE *f
, var_map map
)
1702 fprintf (f
, "\nPartition map \n\n");
1704 for (x
= 0; x
< map
->num_partitions
; x
++)
1706 if (map
->compact_to_partition
!= NULL
)
1707 p
= map
->compact_to_partition
[x
];
1711 if (map
->partition_to_var
[p
] == NULL_TREE
)
1715 for (y
= 1; y
< num_ssa_names
; y
++)
1717 p
= partition_find (map
->var_partition
, y
);
1718 if (map
->partition_to_compact
)
1719 p
= map
->partition_to_compact
[p
];
1724 fprintf(f
, "Partition %d (", x
);
1725 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1728 fprintf (f
, "%d ", y
);
1738 /* Output live range info LIVE to file F, controlled by FLAG. */
1741 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1745 var_map map
= live
->map
;
1748 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1752 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1753 for (i
= 0; i
< num_var_partitions (map
); i
++)
1755 if (bitmap_bit_p (live_entry_blocks (live
, i
), bb
->index
))
1757 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1765 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1769 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1770 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
, bi
)
1772 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1780 #ifdef ENABLE_CHECKING
1782 register_ssa_partition_check (tree ssa_var
)
1784 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1785 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
1787 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1788 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1789 fprintf (stderr
, " in the SSA->Normal phase.\n");
1790 internal_error ("SSA corruption");