1 /* Routines for liveness in SSA trees.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
23 #ifndef _TREE_SSA_LIVE_H
24 #define _TREE_SSA_LIVE_H 1
26 #include "partition.h"
29 /* Used to create the variable mapping when we go out of SSA form. */
30 typedef struct _var_map
32 /* The partition of all variables. */
33 partition var_partition;
35 /* Vector for compacting partitions. */
36 int *partition_to_compact;
37 int *compact_to_partition;
39 /* Mapping of partition numbers to vars. */
40 tree *partition_to_var;
42 /* Current number of partitions. */
43 unsigned int num_partitions;
45 /* Original partition size. */
46 unsigned int partition_size;
49 #define VAR_ANN_PARTITION(ann) (ann->partition)
50 #define VAR_ANN_ROOT_INDEX(ann) (ann->root_index)
52 #define NO_PARTITION -1
54 /* Flags to pass to compact_var_map */
56 #define VARMAP_NORMAL 0
57 #define VARMAP_NO_SINGLE_DEFS 1
59 extern var_map init_var_map (int);
60 extern void delete_var_map (var_map);
61 extern void dump_var_map (FILE *, var_map);
62 extern int var_union (var_map, tree, tree);
63 extern void change_partition_var (var_map, tree, int);
64 extern void compact_var_map (var_map, int);
65 #ifdef ENABLE_CHECKING
66 extern void register_ssa_partition_check (tree ssa_var);
69 static inline unsigned num_var_partitions (var_map);
70 static inline tree var_to_partition_to_var (var_map, tree);
71 static inline tree partition_to_var (var_map, int);
72 static inline int var_to_partition (var_map, tree);
73 static inline tree version_to_var (var_map, int);
74 static inline void register_ssa_partition (var_map, tree);
76 extern var_map create_ssa_var_map (void);
78 /* Number of partitions in MAP. */
80 static inline unsigned
81 num_var_partitions (var_map map)
83 return map->num_partitions;
87 /* Given partition index I from MAP, return the variable which represents that
91 partition_to_var (var_map map, int i)
93 if (map->compact_to_partition)
94 i = map->compact_to_partition[i];
95 i = partition_find (map->var_partition, i);
96 return map->partition_to_var[i];
100 /* Given ssa_name VERSION, if it has a partition in MAP, return the var it
101 is associated with. Otherwise return NULL. */
103 static inline tree version_to_var (var_map map, int version)
106 part = partition_find (map->var_partition, version);
107 if (map->partition_to_compact)
108 part = map->partition_to_compact[part];
109 if (part == NO_PARTITION)
112 return partition_to_var (map, part);
116 /* Given VAR, return the partition number in MAP which contains it.
117 NO_PARTITION is returned if it's not in any partition. */
120 var_to_partition (var_map map, tree var)
125 if (TREE_CODE (var) == SSA_NAME)
127 part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
128 if (map->partition_to_compact)
129 part = map->partition_to_compact[part];
134 if (ann && ann->out_of_ssa_tag)
135 part = VAR_ANN_PARTITION (ann);
143 /* Given VAR, return the variable which represents the entire partition
144 it is a member of in MAP. NULL is returned if it is not in a partition. */
147 var_to_partition_to_var (var_map map, tree var)
151 part = var_to_partition (map, var);
152 if (part == NO_PARTITION)
154 return partition_to_var (map, part);
158 /* This routine registers a partition for SSA_VAR with MAP. IS_USE is used
159 to count references. Any unregistered partitions may be compacted out
163 register_ssa_partition (var_map map, tree ssa_var)
167 #if defined ENABLE_CHECKING
168 register_ssa_partition_check (ssa_var);
171 version = SSA_NAME_VERSION (ssa_var);
172 if (map->partition_to_var[version] == NULL_TREE)
173 map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var;
177 /* ---------------- live on entry/exit info ------------------------------
179 This structure is used to represent live range information on SSA based
180 trees. A partition map must be provided, and based on the active partitions,
181 live-on-entry information and live-on-exit information can be calculated.
182 As well, partitions are marked as to whether they are global (live
183 outside the basic block they are defined in).
185 The live-on-entry information is per block. It provide a bitmap for
186 each block which has a bit set for each partition that is live on entry to
189 The live-on-exit information is per block. It provides a bitmap for each
190 block indicating which partitions are live on exit from the block.
192 For the purposes of this implementation, we treat the elements of a PHI
195 Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
196 originate. They are *NOT* considered live on entry to the block
197 containing the PHI node.
199 The Def of a PHI node is *not* considered live on entry to the block.
200 It is considered to be "define early" in the block. Picture it as each
201 block having a stmt (or block-preheader) before the first real stmt in
202 the block which defines all the variables that are defined by PHIs.
204 ----------------------------------------------------------------------- */
207 typedef struct tree_live_info_d
209 /* Var map this relates to. */
212 /* Bitmap indicating which partitions are global. */
215 /* Bitmap of live on entry blocks for partition elements. */
218 /* Number of basic blocks when live on exit calculated. */
221 /* Vector used when creating live ranges as a visited stack. */
224 /* Top of workstack. */
227 /* Bitmap of what variables are live on exit for a basic blocks. */
232 extern tree_live_info_p calculate_live_ranges (var_map);
233 extern void calculate_live_on_exit (tree_live_info_p);
234 extern void delete_tree_live_info (tree_live_info_p);
236 #define LIVEDUMP_ENTRY 0x01
237 #define LIVEDUMP_EXIT 0x02
238 #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
239 extern void dump_live_info (FILE *, tree_live_info_p, int);
241 static inline int partition_is_global (tree_live_info_p, int);
242 static inline bitmap live_on_entry (tree_live_info_p, basic_block);
243 static inline bitmap live_on_exit (tree_live_info_p, basic_block);
244 static inline var_map live_var_map (tree_live_info_p);
245 static inline void live_merge_and_clear (tree_live_info_p, int, int);
246 static inline void make_live_on_entry (tree_live_info_p, basic_block, int);
249 /* Return TRUE if P is marked as a global in LIVE. */
252 partition_is_global (tree_live_info_p live, int p)
254 gcc_assert (live->global);
255 return bitmap_bit_p (live->global, p);
259 /* Return the bitmap from LIVE representing the live on entry blocks for
263 live_on_entry (tree_live_info_p live, basic_block bb)
265 gcc_assert (live->livein);
266 gcc_assert (bb != ENTRY_BLOCK_PTR);
267 gcc_assert (bb != EXIT_BLOCK_PTR);
269 return live->livein[bb->index];
273 /* Return the bitmap from LIVE representing the live on exit partitions from
277 live_on_exit (tree_live_info_p live, basic_block bb)
279 gcc_assert (live->liveout);
280 gcc_assert (bb != ENTRY_BLOCK_PTR);
281 gcc_assert (bb != EXIT_BLOCK_PTR);
283 return live->liveout[bb->index];
287 /* Return the partition map which the information in LIVE utilizes. */
289 static inline var_map
290 live_var_map (tree_live_info_p live)
296 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
297 the result into P1. Clear P2. */
300 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
302 gcc_assert (live->livein[p1]);
303 gcc_assert (live->livein[p2]);
304 bitmap_ior_into (live->livein[p1], live->livein[p2]);
305 bitmap_zero (live->livein[p2]);
309 /* Mark partition P as live on entry to basic block BB in LIVE. */
312 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
314 bitmap_set_bit (live->livein[bb->index], p);
315 bitmap_set_bit (live->global, p);
319 /* A tree_partition_associator (TPA)object is a base structure which allows
320 partitions to be associated with a tree object.
322 A varray of tree elements represent each distinct tree item.
323 A parallel int array represents the first partition number associated with
325 This partition number is then used as in index into the next_partition
326 array, which returns the index of the next partition which is associated
327 with the tree. TPA_NONE indicates the end of the list.
328 A varray paralleling the partition list 'partition_to_tree_map' is used
329 to indicate which tree index the partition is in. */
331 typedef struct tree_partition_associator_d
333 VEC(tree,heap) *trees;
334 VEC(int,heap) *first_partition;
336 int *partition_to_tree_map;
338 int uncompressed_num;
342 /* Value returned when there are no more partitions associated with a tree. */
345 static inline tree tpa_tree (tpa_p, int);
346 static inline int tpa_first_partition (tpa_p, int);
347 static inline int tpa_next_partition (tpa_p, int);
348 static inline int tpa_num_trees (tpa_p);
349 static inline int tpa_find_tree (tpa_p, int);
350 static inline void tpa_decompact (tpa_p);
351 extern void tpa_delete (tpa_p);
352 extern void tpa_dump (FILE *, tpa_p);
353 extern void tpa_remove_partition (tpa_p, int, int);
354 extern int tpa_compact (tpa_p);
357 /* Return the number of distinct tree nodes in TPA. */
360 tpa_num_trees (tpa_p tpa)
362 return tpa->num_trees;
366 /* Return the tree node for index I in TPA. */
369 tpa_tree (tpa_p tpa, int i)
371 return VEC_index (tree, tpa->trees, i);
375 /* Return the first partition associated with tree list I in TPA. */
378 tpa_first_partition (tpa_p tpa, int i)
380 return VEC_index (int, tpa->first_partition, i);
384 /* Return the next partition after partition I in TPA's list. */
387 tpa_next_partition (tpa_p tpa, int i)
389 return tpa->next_partition[i];
393 /* Return the tree index from TPA whose list contains partition I.
394 TPA_NONE is returned if I is not associated with any list. */
397 tpa_find_tree (tpa_p tpa, int i)
401 index = tpa->partition_to_tree_map[i];
402 /* When compressed, any index higher than the number of tree elements is
403 a compressed element, so return TPA_NONE. */
404 if (index != TPA_NONE && index >= tpa_num_trees (tpa))
406 gcc_assert (tpa->uncompressed_num != -1);
414 /* This function removes any compaction which was performed on TPA. */
417 tpa_decompact(tpa_p tpa)
419 gcc_assert (tpa->uncompressed_num != -1);
420 tpa->num_trees = tpa->uncompressed_num;
424 /* Once a var_map has been created and compressed, a complementary root_var
425 object can be built. This creates a list of all the root variables from
426 which ssa version names are derived. Each root variable has a list of
427 which partitions are versions of that root.
429 This is implemented using the tree_partition_associator.
431 The tree vector is used to represent the root variable.
432 The list of partitions represent SSA versions of the root variable. */
434 typedef tpa_p root_var_p;
436 static inline tree root_var (root_var_p, int);
437 static inline int root_var_first_partition (root_var_p, int);
438 static inline int root_var_next_partition (root_var_p, int);
439 static inline int root_var_num (root_var_p);
440 static inline void root_var_dump (FILE *, root_var_p);
441 static inline void root_var_remove_partition (root_var_p, int, int);
442 static inline void root_var_delete (root_var_p);
443 static inline int root_var_find (root_var_p, int);
444 static inline int root_var_compact (root_var_p);
445 static inline void root_var_decompact (tpa_p);
447 extern root_var_p root_var_init (var_map);
449 /* Value returned when there are no more partitions associated with a root
451 #define ROOT_VAR_NONE TPA_NONE
454 /* Return the number of distinct root variables in RV. */
457 root_var_num (root_var_p rv)
459 return tpa_num_trees (rv);
463 /* Return root variable I from RV. */
466 root_var (root_var_p rv, int i)
468 return tpa_tree (rv, i);
472 /* Return the first partition in RV belonging to root variable list I. */
475 root_var_first_partition (root_var_p rv, int i)
477 return tpa_first_partition (rv, i);
481 /* Return the next partition after partition I in a root list from RV. */
484 root_var_next_partition (root_var_p rv, int i)
486 return tpa_next_partition (rv, i);
490 /* Send debug info for root_var list RV to file F. */
493 root_var_dump (FILE *f, root_var_p rv)
495 fprintf (f, "\nRoot Var dump\n");
501 /* Destroy root_var object RV. */
504 root_var_delete (root_var_p rv)
510 /* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV. */
513 root_var_remove_partition (root_var_p rv, int root_index, int partition_index)
515 tpa_remove_partition (rv, root_index, partition_index);
519 /* Return the root_var list index for partition I in RV. */
522 root_var_find (root_var_p rv, int i)
524 return tpa_find_tree (rv, i);
528 /* Hide single element lists in RV. */
531 root_var_compact (root_var_p rv)
533 return tpa_compact (rv);
537 /* Expose the single element lists in RV. */
540 root_var_decompact (root_var_p rv)
546 /* This set of routines implements a coalesce_list. This is an object which
547 is used to track pairs of partitions which are desirable to coalesce
548 together at some point. Costs are associated with each pair, and when
549 all desired information has been collected, the object can be used to
550 order the pairs for processing. */
552 /* This structure defines a pair entry. */
554 typedef struct partition_pair
557 int second_partition;
559 } * partition_pair_p;
561 extern unsigned int partition_pair_map_hash (const void *);
562 extern int partition_pair_map_eq (const void *, const void *);
564 /* This structure maintains the list of coalesce pairs. */
566 typedef struct coalesce_list_d
570 partition_pair_p *sorted;
575 extern coalesce_list_p create_coalesce_list (var_map);
576 extern void add_coalesce (coalesce_list_p, int, int, int);
577 extern int coalesce_cost (int, bool, bool);
578 extern void sort_coalesce_list (coalesce_list_p);
579 extern void dump_coalesce_list (FILE *, coalesce_list_p);
580 extern void delete_coalesce_list (coalesce_list_p);
582 #define NO_BEST_COALESCE -1
584 extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p,
586 extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
587 coalesce_list_p cl, FILE *);
589 /* From tree-ssa-ter.c */
590 extern tree *find_replaceable_exprs (var_map);
591 extern void dump_replaceable_exprs (FILE *, tree *);
594 #endif /* _TREE_SSA_LIVE_H */