1 /* Routines for liveness in SSA trees.
2 Copyright (C) 2003, 2004 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. */
23 #ifndef _TREE_SSA_LIVE_H
24 #define _TREE_SSA_LIVE_H 1
26 /* Used to create the variable mapping when we go out of SSA form. */
27 typedef struct _var_map
29 /* The partition of all variables. */
30 partition var_partition
;
32 /* Vector for compacting partitions. */
33 int *partition_to_compact
;
34 int *compact_to_partition
;
36 /* Mapping of partition numbers to vars. */
37 tree
*partition_to_var
;
39 /* Current number of partitions. */
40 unsigned int num_partitions
;
42 /* Original partition size. */
43 unsigned int partition_size
;
45 /* Reference count, if required. */
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 /* Flags to pass to remove_ssa_form. */
61 #define SSANORM_PERFORM_TER 0x1
62 #define SSANORM_COMBINE_TEMPS 0x2
63 #define SSANORM_REMOVE_ALL_PHIS 0x4
64 #define SSANORM_COALESCE_PARTITIONS 0x8
65 #define SSANORM_USE_COALESCE_LIST 0x10
67 extern var_map
init_var_map (int);
68 extern void delete_var_map (var_map
);
69 extern void dump_var_map (FILE *, var_map
);
70 extern int var_union (var_map
, tree
, tree
);
71 extern void change_partition_var (var_map
, tree
, int);
72 extern void compact_var_map (var_map
, int);
73 extern void remove_ssa_form (FILE *, var_map
, int);
74 extern void register_ssa_partitions_for_vars (bitmap vars
, var_map map
);
76 static inline int num_var_partitions (var_map
);
77 static inline tree
var_to_partition_to_var (var_map
, tree
);
78 static inline tree
partition_to_var (var_map
, int);
79 static inline int var_to_partition (var_map
, tree
);
80 static inline tree
version_to_var (var_map
, int);
81 static inline int version_ref_count (var_map
, tree
);
82 static inline void register_ssa_partition (var_map
, tree
, bool);
84 #define SSA_VAR_MAP_REF_COUNT 0x01
85 extern var_map
create_ssa_var_map (int);
88 /* Number of partitions in MAP. */
91 num_var_partitions (var_map map
)
93 return map
->num_partitions
;
97 /* Return the reference count for SSA_VAR's partition in MAP. */
100 version_ref_count (var_map map
, tree ssa_var
)
102 int version
= SSA_NAME_VERSION (ssa_var
);
103 #ifdef ENABLE_CHECKING
107 return map
->ref_count
[version
];
111 /* Given partition index I from MAP, return the variable which represents that
115 partition_to_var (var_map map
, int i
)
117 if (map
->compact_to_partition
)
118 i
= map
->compact_to_partition
[i
];
119 i
= partition_find (map
->var_partition
, i
);
120 return map
->partition_to_var
[i
];
124 /* Given ssa_name VERSION, if it has a partition in MAP, return the var it
125 is associated with. Otherwise return NULL. */
127 static inline tree
version_to_var (var_map map
, int version
)
130 part
= partition_find (map
->var_partition
, version
);
131 if (map
->partition_to_compact
)
132 part
= map
->partition_to_compact
[part
];
133 if (part
== NO_PARTITION
)
136 return partition_to_var (map
, part
);
140 /* Given VAR, return the partition number in MAP which contains it.
141 NO_PARTITION is returned if its not in any partition. */
144 var_to_partition (var_map map
, tree var
)
149 if (TREE_CODE (var
) == SSA_NAME
)
151 part
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var
));
152 if (map
->partition_to_compact
)
153 part
= map
->partition_to_compact
[part
];
158 if (ann
->out_of_ssa_tag
)
159 part
= VAR_ANN_PARTITION (ann
);
167 /* Given VAR, return the variable which represents the entire partition
168 it is a member of in MAP. NULL is returned if it is not in a partition. */
171 var_to_partition_to_var (var_map map
, tree var
)
175 part
= var_to_partition (map
, var
);
176 if (part
== NO_PARTITION
)
178 return partition_to_var (map
, part
);
182 /* This routine registers a partition for SSA_VAR with MAP. IS_USE is used
183 to count references. Any unregistered partitions may be compacted out
187 register_ssa_partition (var_map map
, tree ssa_var
, bool is_use
)
191 #if defined ENABLE_CHECKING
192 if (TREE_CODE (ssa_var
) != SSA_NAME
)
195 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
197 fprintf (stderr
, "Illegally registering a virtual SSA name :");
198 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
199 fprintf (stderr
, " in the SSA->Normal phase.\n");
204 version
= SSA_NAME_VERSION (ssa_var
);
205 if (is_use
&& map
->ref_count
)
206 map
->ref_count
[version
]++;
208 if (map
->partition_to_var
[version
] == NULL_TREE
)
209 map
->partition_to_var
[SSA_NAME_VERSION (ssa_var
)] = ssa_var
;
213 /* ---------------- live on entry/exit info ------------------------------
215 This structure is used to represent live range information on SSA based
216 trees. A partition map must be provided, and based on the active partitions,
217 live-on-entry information and live-on-exit information can be calculated.
218 As well, partitions are marked as to whether they are global (live
219 outside the basic block they are defined in).
221 The live-on-entry information is per variable. It provide a bitmap for
222 each variable which has a bit set for each basic block that the variable
223 is live on entry to that block.
225 The live-on-exit information is per block. It provides a bitmap for each
226 block indicating which partitions are live on exit from the block.
228 For the purposes of this implementation, we treat the elements of a PHI
231 Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
232 originate. They are *NOT* considered live on entry to the block
233 containing the PHI node.
235 The Def of a PHI node is *not* considered live on entry to the block.
236 It is considered to be "define early" in the block. Picture it as each
237 block having a stmt (or block-preheader) before the first real stmt in
238 the block which defines all the variables that are defined by PHIs.
240 ----------------------------------------------------------------------- */
243 typedef struct tree_live_info_d
245 /* Var map this relates to. */
248 /* Bitmap indicating which partitions are global. */
251 /* Bitmap of live on entry blocks for partition elements. */
254 /* Number of basic blocks when live on exit calculated. */
257 /* Bitmap of what variables are live on exit for a basic blocks. */
262 extern tree_live_info_p
calculate_live_on_entry (var_map
);
263 extern void calculate_live_on_exit (tree_live_info_p
);
264 extern void delete_tree_live_info (tree_live_info_p
);
266 #define LIVEDUMP_ENTRY 0x01
267 #define LIVEDUMP_EXIT 0x02
268 #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
269 extern void dump_live_info (FILE *, tree_live_info_p
, int);
271 static inline int partition_is_global (tree_live_info_p
, int);
272 static inline bitmap
live_entry_blocks (tree_live_info_p
, int);
273 static inline bitmap
live_on_exit (tree_live_info_p
, basic_block
);
274 static inline var_map
live_var_map (tree_live_info_p
);
275 static inline void live_merge_and_clear (tree_live_info_p
, int, int);
276 static inline void make_live_on_entry (tree_live_info_p
, basic_block
, int);
279 /* Return TRUE if P is marked as a global in LIVE. */
282 partition_is_global (tree_live_info_p live
, int p
)
287 return bitmap_bit_p (live
->global
, p
);
291 /* Return the bitmap from LIVE representing the live on entry blocks for
295 live_entry_blocks (tree_live_info_p live
, int p
)
300 return live
->livein
[p
];
304 /* Return the bitmap from LIVE representing the live on exit partitions from
308 live_on_exit (tree_live_info_p live
, basic_block bb
)
313 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
316 return live
->liveout
[bb
->index
];
320 /* Return the partition map which the information in LIVE utilizes. */
322 static inline var_map
323 live_var_map (tree_live_info_p live
)
329 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
330 the result into P1. Clear P2. */
333 live_merge_and_clear (tree_live_info_p live
, int p1
, int p2
)
335 bitmap_a_or_b (live
->livein
[p1
], live
->livein
[p1
], live
->livein
[p2
]);
336 bitmap_zero (live
->livein
[p2
]);
340 /* Mark partition P as live on entry to basic block BB in LIVE. */
343 make_live_on_entry (tree_live_info_p live
, basic_block bb
, int p
)
345 bitmap_set_bit (live
->livein
[p
], bb
->index
);
346 bitmap_set_bit (live
->global
, p
);
350 /* A tree_partition_associator (TPA)object is a base structure which allows
351 partitions to be associated with a tree object.
353 A varray of tree elements represent each distinct tree item.
354 A parallel int array represents the first partition number associated with
356 This partition number is then used as in index into the next_partition
357 array, which returns the index of the next partition which is associated
358 with the tree. TPA_NONE indicates the end of the list.
359 A varray paralleling the partition list 'partition_to_tree_map' is used
360 to indicate which tree index the partition is in. */
362 typedef struct tree_partition_associator_d
365 varray_type first_partition
;
367 int *partition_to_tree_map
;
369 int uncompressed_num
;
373 /* Value returned when there are no more partitions associated with a tree. */
376 static inline tree
tpa_tree (tpa_p
, int);
377 static inline int tpa_first_partition (tpa_p
, int);
378 static inline int tpa_next_partition (tpa_p
, int);
379 static inline int tpa_num_trees (tpa_p
);
380 static inline int tpa_find_tree (tpa_p
, int);
381 static inline void tpa_decompact (tpa_p
);
382 extern tpa_p
tpa_init (var_map
);
383 extern void tpa_delete (tpa_p
);
384 extern void tpa_dump (FILE *, tpa_p
);
385 extern void tpa_remove_partition (tpa_p
, int, int);
386 extern int tpa_compact (tpa_p
);
389 /* Return the number of distinct tree nodes in TPA. */
392 tpa_num_trees (tpa_p tpa
)
394 return tpa
->num_trees
;
398 /* Return the tree node for index I in TPA. */
401 tpa_tree (tpa_p tpa
, int i
)
403 return VARRAY_TREE (tpa
->trees
, i
);
407 /* Return the first partition associated with tree list I in TPA. */
410 tpa_first_partition (tpa_p tpa
, int i
)
412 return VARRAY_INT (tpa
->first_partition
, i
);
416 /* Return the next partition after partition I in TPA's list. */
419 tpa_next_partition (tpa_p tpa
, int i
)
421 return tpa
->next_partition
[i
];
425 /* Return the tree index from TPA whose list contains partition I.
426 TPA_NONE is returned if I is not associated with any list. */
429 tpa_find_tree (tpa_p tpa
, int i
)
433 index
= tpa
->partition_to_tree_map
[i
];
434 /* When compressed, any index higher than the number of tree elements is
435 a compressed element, so return TPA_NONE. */
436 if (index
!= TPA_NONE
&& index
>= tpa_num_trees (tpa
))
438 #ifdef ENABLE_CHECKING
439 if (tpa
->uncompressed_num
== -1)
449 /* This function removes any compaction which was performed on TPA. */
452 tpa_decompact(tpa_p tpa
)
454 #ifdef ENABLE_CHECKING
455 if (tpa
->uncompressed_num
== -1)
458 tpa
->num_trees
= tpa
->uncompressed_num
;
462 /* Once a var_map has been created and compressed, a complimentary root_var
463 object can be built. This creates a list of all the root variables from
464 which ssa version names are derived. Each root variable has a list of
465 which partitions are versions of that root.
467 This is implemented using the tree_partition_associator.
469 The tree vector is used to represent the root variable.
470 The list of partitions represent SSA versions of the root variable. */
472 typedef tpa_p root_var_p
;
474 static inline tree
root_var (root_var_p
, int);
475 static inline int root_var_first_partition (root_var_p
, int);
476 static inline int root_var_next_partition (root_var_p
, int);
477 static inline int root_var_num (root_var_p
);
478 static inline void root_var_dump (FILE *, root_var_p
);
479 static inline void root_var_remove_partition (root_var_p
, int, int);
480 static inline void root_var_delete (root_var_p
);
481 static inline int root_var_find (root_var_p
, int);
482 static inline int root_var_compact (root_var_p
);
483 static inline void root_var_decompact (tpa_p
);
485 extern root_var_p
root_var_init (var_map
);
487 /* Value returned when there are no more partitions associated with a root
489 #define ROOT_VAR_NONE TPA_NONE
492 /* Return the number of distinct root variables in RV. */
495 root_var_num (root_var_p rv
)
497 return tpa_num_trees (rv
);
501 /* Return root variable I from RV. */
504 root_var (root_var_p rv
, int i
)
506 return tpa_tree (rv
, i
);
510 /* Return the first partition in RV belonging to root variable list I. */
513 root_var_first_partition (root_var_p rv
, int i
)
515 return tpa_first_partition (rv
, i
);
519 /* Return the next partition after partition I in a root list from RV. */
522 root_var_next_partition (root_var_p rv
, int i
)
524 return tpa_next_partition (rv
, i
);
528 /* Send debug info for root_var list RV to file F. */
531 root_var_dump (FILE *f
, root_var_p rv
)
533 fprintf (f
, "\nRoot Var dump\n");
539 /* Destroy root_var object RV. */
542 root_var_delete (root_var_p rv
)
548 /* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV. */
551 root_var_remove_partition (root_var_p rv
, int root_index
, int partition_index
)
553 tpa_remove_partition (rv
, root_index
, partition_index
);
557 /* Return the root_var list index for partition I in RV. */
560 root_var_find (root_var_p rv
, int i
)
562 return tpa_find_tree (rv
, i
);
566 /* Hide single element lists in RV. */
569 root_var_compact (root_var_p rv
)
571 return tpa_compact (rv
);
575 /* Expose the single element lists in RV. */
578 root_var_decompact (root_var_p rv
)
584 /* A TYPE_VAR object is similar to a root_var object, except this associates
585 partitions with their type rather than their root variable. This is used to
586 coalesce memory locations based on type. */
588 typedef tpa_p type_var_p
;
590 static inline tree
type_var (type_var_p
, int);
591 static inline int type_var_first_partition (type_var_p
, int);
592 static inline int type_var_next_partition (type_var_p
, int);
593 static inline int type_var_num (type_var_p
);
594 static inline void type_var_dump (FILE *, type_var_p
);
595 static inline void type_var_remove_partition (type_var_p
, int, int);
596 static inline void type_var_delete (type_var_p
);
597 static inline int type_var_find (type_var_p
, int);
598 static inline int type_var_compact (type_var_p
);
599 static inline void type_var_decompact (type_var_p
);
601 extern type_var_p
type_var_init (var_map
);
603 /* Value returned when there is no partitions associated with a list. */
604 #define TYPE_VAR_NONE TPA_NONE
607 /* Return the number of distinct type lists in TV. */
610 type_var_num (type_var_p tv
)
612 return tpa_num_trees (tv
);
616 /* Return the type of list I in TV. */
619 type_var (type_var_p tv
, int i
)
621 return tpa_tree (tv
, i
);
625 /* Return the first partition belonging to type list I in TV. */
628 type_var_first_partition (type_var_p tv
, int i
)
630 return tpa_first_partition (tv
, i
);
634 /* Return the next partition after partition I in a type list within TV. */
637 type_var_next_partition (type_var_p tv
, int i
)
639 return tpa_next_partition (tv
, i
);
643 /* Send debug info for type_var object TV to file F. */
646 type_var_dump (FILE *f
, type_var_p tv
)
648 fprintf (f
, "\nType Var dump\n");
654 /* Delete type_var object TV. */
657 type_var_delete (type_var_p tv
)
663 /* Remove partition PARTITION_INDEX from type list TYPE_INDEX in TV. */
666 type_var_remove_partition (type_var_p tv
, int type_index
, int partition_index
)
668 tpa_remove_partition (tv
, type_index
, partition_index
);
672 /* Return the type index in TV for the list partition I is in. */
675 type_var_find (type_var_p tv
, int i
)
677 return tpa_find_tree (tv
, i
);
681 /* Hide single element lists in TV. */
684 type_var_compact (type_var_p tv
)
686 return tpa_compact (tv
);
690 /* Expose single element lists in TV. */
693 type_var_decompact (type_var_p tv
)
698 /* This set of routines implements a coalesce_list. This is an object which
699 is used to track pairs of partitions which are desirable to coalesce
700 together at some point. Costs are associated with each pair, and when
701 all desired information has been collected, the object can be used to
702 order the pairs for processing. */
704 /* This structure defines a pair for coalescing. */
706 typedef struct partition_pair_d
709 int second_partition
;
711 struct partition_pair_d
*next
;
714 /* This structure maintains the list of coalesce pairs.
715 When add_mode is true, list is a triangular shaped list of coalesce pairs.
716 The smaller partition number is used to index the list, and the larger is
717 index is located in a partition_pair_p object. These lists are sorted from
718 smallest to largest by 'second_partition'. New coalesce pairs are allowed
719 to be added in this mode.
720 When add_mode is false, the lists have all been merged into list[0]. The
721 rest of the lists are not used. list[0] is ordered from most desirable
722 coalesce to least desirable. pop_best_coalesce() retrieves the pairs
725 typedef struct coalesce_list_d
728 partition_pair_p
*list
;
732 extern coalesce_list_p
create_coalesce_list (var_map
);
733 extern void add_coalesce (coalesce_list_p
, int, int, int);
734 extern void sort_coalesce_list (coalesce_list_p
);
735 extern void dump_coalesce_list (FILE *, coalesce_list_p
);
736 extern void delete_coalesce_list (coalesce_list_p
);
738 #define NO_BEST_COALESCE -1
739 extern int pop_best_coalesce (coalesce_list_p
, int *, int *);
741 extern conflict_graph
build_tree_conflict_graph (tree_live_info_p
, tpa_p
,
743 extern void coalesce_tpa_members (tpa_p tpa
, conflict_graph graph
, var_map map
,
744 coalesce_list_p cl
, FILE *);
747 #endif /* _TREE_SSA_LIVE_H */