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 variable. It provide a bitmap for
186 each variable which has a bit set for each basic block that the variable
187 is live on entry to that block.
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 /* Bitmap of what variables are live on exit for a basic blocks. */
226 extern tree_live_info_p
calculate_live_on_entry (var_map
);
227 extern void calculate_live_on_exit (tree_live_info_p
);
228 extern void delete_tree_live_info (tree_live_info_p
);
230 #define LIVEDUMP_ENTRY 0x01
231 #define LIVEDUMP_EXIT 0x02
232 #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
233 extern void dump_live_info (FILE *, tree_live_info_p
, int);
235 static inline int partition_is_global (tree_live_info_p
, int);
236 static inline bitmap
live_entry_blocks (tree_live_info_p
, int);
237 static inline bitmap
live_on_exit (tree_live_info_p
, basic_block
);
238 static inline var_map
live_var_map (tree_live_info_p
);
239 static inline void live_merge_and_clear (tree_live_info_p
, int, int);
240 static inline void make_live_on_entry (tree_live_info_p
, basic_block
, int);
243 /* Return TRUE if P is marked as a global in LIVE. */
246 partition_is_global (tree_live_info_p live
, int p
)
248 gcc_assert (live
->global
);
249 return bitmap_bit_p (live
->global
, p
);
253 /* Return the bitmap from LIVE representing the live on entry blocks for
257 live_entry_blocks (tree_live_info_p live
, int p
)
259 gcc_assert (live
->livein
);
260 return live
->livein
[p
];
264 /* Return the bitmap from LIVE representing the live on exit partitions from
268 live_on_exit (tree_live_info_p live
, basic_block bb
)
270 gcc_assert (live
->liveout
);
271 gcc_assert (bb
!= ENTRY_BLOCK_PTR
);
272 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
274 return live
->liveout
[bb
->index
];
278 /* Return the partition map which the information in LIVE utilizes. */
280 static inline var_map
281 live_var_map (tree_live_info_p live
)
287 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
288 the result into P1. Clear P2. */
291 live_merge_and_clear (tree_live_info_p live
, int p1
, int p2
)
293 bitmap_ior_into (live
->livein
[p1
], live
->livein
[p2
]);
294 bitmap_zero (live
->livein
[p2
]);
298 /* Mark partition P as live on entry to basic block BB in LIVE. */
301 make_live_on_entry (tree_live_info_p live
, basic_block bb
, int p
)
303 bitmap_set_bit (live
->livein
[p
], bb
->index
);
304 bitmap_set_bit (live
->global
, p
);
308 /* A tree_partition_associator (TPA)object is a base structure which allows
309 partitions to be associated with a tree object.
311 A varray of tree elements represent each distinct tree item.
312 A parallel int array represents the first partition number associated with
314 This partition number is then used as in index into the next_partition
315 array, which returns the index of the next partition which is associated
316 with the tree. TPA_NONE indicates the end of the list.
317 A varray paralleling the partition list 'partition_to_tree_map' is used
318 to indicate which tree index the partition is in. */
320 typedef struct tree_partition_associator_d
322 VEC(tree
,heap
) *trees
;
323 VEC(int,heap
) *first_partition
;
325 int *partition_to_tree_map
;
327 int uncompressed_num
;
331 /* Value returned when there are no more partitions associated with a tree. */
334 static inline tree
tpa_tree (tpa_p
, int);
335 static inline int tpa_first_partition (tpa_p
, int);
336 static inline int tpa_next_partition (tpa_p
, int);
337 static inline int tpa_num_trees (tpa_p
);
338 static inline int tpa_find_tree (tpa_p
, int);
339 static inline void tpa_decompact (tpa_p
);
340 extern void tpa_delete (tpa_p
);
341 extern void tpa_dump (FILE *, tpa_p
);
342 extern void tpa_remove_partition (tpa_p
, int, int);
343 extern int tpa_compact (tpa_p
);
346 /* Return the number of distinct tree nodes in TPA. */
349 tpa_num_trees (tpa_p tpa
)
351 return tpa
->num_trees
;
355 /* Return the tree node for index I in TPA. */
358 tpa_tree (tpa_p tpa
, int i
)
360 return VEC_index (tree
, tpa
->trees
, i
);
364 /* Return the first partition associated with tree list I in TPA. */
367 tpa_first_partition (tpa_p tpa
, int i
)
369 return VEC_index (int, tpa
->first_partition
, i
);
373 /* Return the next partition after partition I in TPA's list. */
376 tpa_next_partition (tpa_p tpa
, int i
)
378 return tpa
->next_partition
[i
];
382 /* Return the tree index from TPA whose list contains partition I.
383 TPA_NONE is returned if I is not associated with any list. */
386 tpa_find_tree (tpa_p tpa
, int i
)
390 index
= tpa
->partition_to_tree_map
[i
];
391 /* When compressed, any index higher than the number of tree elements is
392 a compressed element, so return TPA_NONE. */
393 if (index
!= TPA_NONE
&& index
>= tpa_num_trees (tpa
))
395 gcc_assert (tpa
->uncompressed_num
!= -1);
403 /* This function removes any compaction which was performed on TPA. */
406 tpa_decompact(tpa_p tpa
)
408 gcc_assert (tpa
->uncompressed_num
!= -1);
409 tpa
->num_trees
= tpa
->uncompressed_num
;
413 /* Once a var_map has been created and compressed, a complementary root_var
414 object can be built. This creates a list of all the root variables from
415 which ssa version names are derived. Each root variable has a list of
416 which partitions are versions of that root.
418 This is implemented using the tree_partition_associator.
420 The tree vector is used to represent the root variable.
421 The list of partitions represent SSA versions of the root variable. */
423 typedef tpa_p root_var_p
;
425 static inline tree
root_var (root_var_p
, int);
426 static inline int root_var_first_partition (root_var_p
, int);
427 static inline int root_var_next_partition (root_var_p
, int);
428 static inline int root_var_num (root_var_p
);
429 static inline void root_var_dump (FILE *, root_var_p
);
430 static inline void root_var_remove_partition (root_var_p
, int, int);
431 static inline void root_var_delete (root_var_p
);
432 static inline int root_var_find (root_var_p
, int);
433 static inline int root_var_compact (root_var_p
);
434 static inline void root_var_decompact (tpa_p
);
436 extern root_var_p
root_var_init (var_map
);
438 /* Value returned when there are no more partitions associated with a root
440 #define ROOT_VAR_NONE TPA_NONE
443 /* Return the number of distinct root variables in RV. */
446 root_var_num (root_var_p rv
)
448 return tpa_num_trees (rv
);
452 /* Return root variable I from RV. */
455 root_var (root_var_p rv
, int i
)
457 return tpa_tree (rv
, i
);
461 /* Return the first partition in RV belonging to root variable list I. */
464 root_var_first_partition (root_var_p rv
, int i
)
466 return tpa_first_partition (rv
, i
);
470 /* Return the next partition after partition I in a root list from RV. */
473 root_var_next_partition (root_var_p rv
, int i
)
475 return tpa_next_partition (rv
, i
);
479 /* Send debug info for root_var list RV to file F. */
482 root_var_dump (FILE *f
, root_var_p rv
)
484 fprintf (f
, "\nRoot Var dump\n");
490 /* Destroy root_var object RV. */
493 root_var_delete (root_var_p rv
)
499 /* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV. */
502 root_var_remove_partition (root_var_p rv
, int root_index
, int partition_index
)
504 tpa_remove_partition (rv
, root_index
, partition_index
);
508 /* Return the root_var list index for partition I in RV. */
511 root_var_find (root_var_p rv
, int i
)
513 return tpa_find_tree (rv
, i
);
517 /* Hide single element lists in RV. */
520 root_var_compact (root_var_p rv
)
522 return tpa_compact (rv
);
526 /* Expose the single element lists in RV. */
529 root_var_decompact (root_var_p rv
)
535 /* This set of routines implements a coalesce_list. This is an object which
536 is used to track pairs of partitions which are desirable to coalesce
537 together at some point. Costs are associated with each pair, and when
538 all desired information has been collected, the object can be used to
539 order the pairs for processing. */
541 /* This structure defines a pair entry. */
543 typedef struct partition_pair
546 int second_partition
;
548 } * partition_pair_p
;
550 extern unsigned int partition_pair_map_hash (const void *);
551 extern int partition_pair_map_eq (const void *, const void *);
553 /* This structure maintains the list of coalesce pairs. */
555 typedef struct coalesce_list_d
559 partition_pair_p
*sorted
;
564 extern coalesce_list_p
create_coalesce_list (var_map
);
565 extern void add_coalesce (coalesce_list_p
, int, int, int);
566 extern int coalesce_cost (int, bool, bool);
567 extern void sort_coalesce_list (coalesce_list_p
);
568 extern void dump_coalesce_list (FILE *, coalesce_list_p
);
569 extern void delete_coalesce_list (coalesce_list_p
);
571 #define NO_BEST_COALESCE -1
573 extern conflict_graph
build_tree_conflict_graph (tree_live_info_p
, tpa_p
,
575 extern void coalesce_tpa_members (tpa_p tpa
, conflict_graph graph
, var_map map
,
576 coalesce_list_p cl
, FILE *);
579 #endif /* _TREE_SSA_LIVE_H */