]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* Routines for liveness in SSA trees. |
fbd26352 | 2 | Copyright (C) 2003-2019 Free Software Foundation, Inc. |
4ee9c684 | 3 | Contributed by Andrew MacLeod <amacleod@redhat.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
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 | |
8c4c00c1 | 9 | the Free Software Foundation; either version 3, or (at your option) |
4ee9c684 | 10 | any later version. |
11 | ||
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. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
4ee9c684 | 20 | |
21 | ||
22 | #ifndef _TREE_SSA_LIVE_H | |
23 | #define _TREE_SSA_LIVE_H 1 | |
24 | ||
bcf3c70d | 25 | #include "partition.h" |
2d043327 | 26 | |
48e1416a | 27 | /* Used to create the variable mapping when we go out of SSA form. |
2d043327 | 28 | |
29 | Mapping from an ssa_name to a partition number is maintained, as well as | |
4ae5778c | 30 | partition number back to ssa_name. |
2d043327 | 31 | |
32 | This data structure also supports "views", which work on a subset of all | |
48e1416a | 33 | partitions. This allows the coalescer to decide what partitions are |
2d043327 | 34 | interesting to it, and only work with those partitions. Whenever the view |
35 | is changed, the partition numbers change, but none of the partition groupings | |
7920eed5 | 36 | change. (ie, it is truly a view since it doesn't change anything) |
2d043327 | 37 | |
38 | The final component of the data structure is the basevar map. This provides | |
f2b32076 | 39 | a list of all the different base variables which occur in a partition view, |
2d043327 | 40 | and a unique index for each one. Routines are provided to quickly produce |
41 | the base variable of a partition. | |
42 | ||
43 | Note that members of a partition MUST all have the same base variable. */ | |
44 | ||
4ee9c684 | 45 | typedef struct _var_map |
46 | { | |
2d043327 | 47 | /* The partition manager of all variables. */ |
4ee9c684 | 48 | partition var_partition; |
49 | ||
2d043327 | 50 | /* Vector for managing partitions views. */ |
51 | int *partition_to_view; | |
52 | int *view_to_partition; | |
4ee9c684 | 53 | |
2d043327 | 54 | /* Current number of partitions in var_map based on the current view. */ |
4ee9c684 | 55 | unsigned int num_partitions; |
56 | ||
2d043327 | 57 | /* Original full partition size. */ |
4ee9c684 | 58 | unsigned int partition_size; |
2d043327 | 59 | |
60 | /* Number of base variables in the base var list. */ | |
61 | int num_basevars; | |
62 | ||
63 | /* Map of partitions numbers to base variable table indexes. */ | |
64 | int *partition_to_base_index; | |
74bfe107 | 65 | |
66 | /* Bitmap of basic block. It describes the region within which the analysis | |
67 | is done. Using pointer avoids allocating memory in out-of-ssa case. */ | |
68 | bitmap bmp_bbs; | |
69 | ||
70 | /* Vector of basic block in the region. */ | |
71 | vec<basic_block> vec_bbs; | |
72 | ||
73 | /* True if this map is for out-of-ssa, otherwise for live range | |
74 | computation. When for out-of-ssa, it also means the var map is computed | |
75 | for whole current function. */ | |
76 | bool outofssa_p; | |
4ee9c684 | 77 | } *var_map; |
78 | ||
4ee9c684 | 79 | |
2d043327 | 80 | /* Value used to represent no partition number. */ |
81 | #define NO_PARTITION -1 | |
4ee9c684 | 82 | |
2e966e2a | 83 | extern var_map init_var_map (int, class loop* = NULL); |
4ee9c684 | 84 | extern void delete_var_map (var_map); |
4ee9c684 | 85 | extern int var_union (var_map, tree, tree); |
94f92c36 | 86 | extern void partition_view_normal (var_map); |
87 | extern void partition_view_bitmap (var_map, bitmap); | |
3f6e5ced | 88 | extern void dump_scope_blocks (FILE *, dump_flags_t); |
89 | extern void debug_scope_block (tree, dump_flags_t); | |
90 | extern void debug_scope_blocks (dump_flags_t); | |
64641360 | 91 | extern void remove_unused_locals (void); |
92 | extern void dump_var_map (FILE *, var_map); | |
93 | extern void debug (_var_map &ref); | |
94 | extern void debug (_var_map *ptr); | |
4ee9c684 | 95 | |
4ee9c684 | 96 | |
74bfe107 | 97 | /* Return TRUE if region of the MAP contains basic block BB. */ |
98 | ||
99 | inline bool | |
100 | region_contains_p (var_map map, basic_block bb) | |
101 | { | |
102 | /* It's possible that the function is called with ENTRY_BLOCK/EXIT_BLOCK. */ | |
103 | if (map->outofssa_p) | |
104 | return (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK); | |
105 | ||
106 | return bitmap_bit_p (map->bmp_bbs, bb->index); | |
107 | } | |
108 | ||
109 | ||
2d043327 | 110 | /* Return number of partitions in MAP. */ |
4ee9c684 | 111 | |
4f917ffe | 112 | static inline unsigned |
4ee9c684 | 113 | num_var_partitions (var_map map) |
114 | { | |
115 | return map->num_partitions; | |
116 | } | |
117 | ||
118 | ||
48e1416a | 119 | /* Given partition index I from MAP, return the variable which represents that |
4ee9c684 | 120 | partition. */ |
48e1416a | 121 | |
4ee9c684 | 122 | static inline tree |
123 | partition_to_var (var_map map, int i) | |
124 | { | |
a8dd994c | 125 | tree name; |
2d043327 | 126 | if (map->view_to_partition) |
127 | i = map->view_to_partition[i]; | |
4ee9c684 | 128 | i = partition_find (map->var_partition, i); |
a8dd994c | 129 | name = ssa_name (i); |
130 | return name; | |
4ee9c684 | 131 | } |
132 | ||
133 | ||
48e1416a | 134 | /* Given ssa_name VERSION, if it has a partition in MAP, return the var it |
4ee9c684 | 135 | is associated with. Otherwise return NULL. */ |
136 | ||
48e1416a | 137 | static inline tree |
2d043327 | 138 | version_to_var (var_map map, int version) |
4ee9c684 | 139 | { |
140 | int part; | |
141 | part = partition_find (map->var_partition, version); | |
2d043327 | 142 | if (map->partition_to_view) |
143 | part = map->partition_to_view[part]; | |
4ee9c684 | 144 | if (part == NO_PARTITION) |
145 | return NULL_TREE; | |
48e1416a | 146 | |
4ee9c684 | 147 | return partition_to_var (map, part); |
148 | } | |
4ee9c684 | 149 | |
48e1416a | 150 | |
151 | /* Given VAR, return the partition number in MAP which contains it. | |
5c9dae64 | 152 | NO_PARTITION is returned if it's not in any partition. */ |
4ee9c684 | 153 | |
154 | static inline int | |
155 | var_to_partition (var_map map, tree var) | |
156 | { | |
4ee9c684 | 157 | int part; |
158 | ||
a8dd994c | 159 | part = partition_find (map->var_partition, SSA_NAME_VERSION (var)); |
160 | if (map->partition_to_view) | |
161 | part = map->partition_to_view[part]; | |
4ee9c684 | 162 | return part; |
163 | } | |
164 | ||
165 | ||
166 | /* Given VAR, return the variable which represents the entire partition | |
167 | it is a member of in MAP. NULL is returned if it is not in a partition. */ | |
168 | ||
169 | static inline tree | |
170 | var_to_partition_to_var (var_map map, tree var) | |
171 | { | |
172 | int part; | |
173 | ||
174 | part = var_to_partition (map, var); | |
175 | if (part == NO_PARTITION) | |
176 | return NULL_TREE; | |
177 | return partition_to_var (map, part); | |
178 | } | |
179 | ||
180 | ||
2d043327 | 181 | /* Return the index into the basevar table for PARTITION's base in MAP. */ |
182 | ||
183 | static inline int | |
184 | basevar_index (var_map map, int partition) | |
185 | { | |
e95895ef | 186 | gcc_checking_assert (partition >= 0 |
187 | && partition <= (int) num_var_partitions (map)); | |
2d043327 | 188 | return map->partition_to_base_index[partition]; |
189 | } | |
190 | ||
191 | ||
192 | /* Return the number of different base variables in MAP. */ | |
193 | ||
194 | static inline int | |
195 | num_basevars (var_map map) | |
196 | { | |
197 | return map->num_basevars; | |
198 | } | |
199 | ||
200 | ||
48e1416a | 201 | /* ---------------- live on entry/exit info ------------------------------ |
4ee9c684 | 202 | |
203 | This structure is used to represent live range information on SSA based | |
204 | trees. A partition map must be provided, and based on the active partitions, | |
205 | live-on-entry information and live-on-exit information can be calculated. | |
48e1416a | 206 | As well, partitions are marked as to whether they are global (live |
4ee9c684 | 207 | outside the basic block they are defined in). |
208 | ||
48e1416a | 209 | The live-on-entry information is per block. It provide a bitmap for |
210 | each block which has a bit set for each partition that is live on entry to | |
30928c44 | 211 | that block. |
4ee9c684 | 212 | |
30928c44 | 213 | The live-on-exit information is per block. It provides a bitmap for each |
4ee9c684 | 214 | block indicating which partitions are live on exit from the block. |
215 | ||
48e1416a | 216 | For the purposes of this implementation, we treat the elements of a PHI |
4ee9c684 | 217 | as follows: |
218 | ||
219 | Uses in a PHI are considered LIVE-ON-EXIT to the block from which they | |
220 | originate. They are *NOT* considered live on entry to the block | |
221 | containing the PHI node. | |
222 | ||
223 | The Def of a PHI node is *not* considered live on entry to the block. | |
224 | It is considered to be "define early" in the block. Picture it as each | |
48e1416a | 225 | block having a stmt (or block-preheader) before the first real stmt in |
4ee9c684 | 226 | the block which defines all the variables that are defined by PHIs. |
48e1416a | 227 | |
4ee9c684 | 228 | ----------------------------------------------------------------------- */ |
229 | ||
230 | ||
231 | typedef struct tree_live_info_d | |
232 | { | |
233 | /* Var map this relates to. */ | |
234 | var_map map; | |
235 | ||
236 | /* Bitmap indicating which partitions are global. */ | |
237 | bitmap global; | |
238 | ||
4fb07d00 | 239 | /* Bitmaps of live on entry blocks for partition elements. */ |
240 | bitmap_head *livein; | |
241 | ||
242 | /* Bitmaps of what variables are live on exit for a basic blocks. */ | |
243 | bitmap_head *liveout; | |
4ee9c684 | 244 | |
245 | /* Number of basic blocks when live on exit calculated. */ | |
246 | int num_blocks; | |
247 | ||
30928c44 | 248 | /* Vector used when creating live ranges as a visited stack. */ |
249 | int *work_stack; | |
250 | ||
251 | /* Top of workstack. */ | |
252 | int *stack_top; | |
78775228 | 253 | |
254 | /* Obstacks to allocate the bitmaps on. */ | |
255 | bitmap_obstack livein_obstack; | |
256 | bitmap_obstack liveout_obstack; | |
4ee9c684 | 257 | } *tree_live_info_p; |
258 | ||
259 | ||
4ee9c684 | 260 | #define LIVEDUMP_ENTRY 0x01 |
261 | #define LIVEDUMP_EXIT 0x02 | |
262 | #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT) | |
64641360 | 263 | extern void delete_tree_live_info (tree_live_info_p); |
78775228 | 264 | extern tree_live_info_p calculate_live_ranges (var_map, bool); |
c7d89805 | 265 | extern void debug (tree_live_info_d &ref); |
266 | extern void debug (tree_live_info_d *ptr); | |
64641360 | 267 | extern void dump_live_info (FILE *, tree_live_info_p, int); |
4ee9c684 | 268 | |
91b30299 | 269 | typedef hash_map<int_hash <unsigned int, -1U>, unsigned int> live_vars_map; |
270 | extern vec<bitmap_head> compute_live_vars (struct function *, live_vars_map *); | |
271 | extern bitmap live_vars_at_stmt (vec<bitmap_head> &, live_vars_map *, | |
272 | gimple *); | |
273 | extern void destroy_live_vars (vec<bitmap_head> &); | |
4ee9c684 | 274 | |
275 | /* Return TRUE if P is marked as a global in LIVE. */ | |
276 | ||
277 | static inline int | |
278 | partition_is_global (tree_live_info_p live, int p) | |
279 | { | |
e95895ef | 280 | gcc_checking_assert (live->global); |
4ee9c684 | 281 | return bitmap_bit_p (live->global, p); |
282 | } | |
283 | ||
284 | ||
48e1416a | 285 | /* Return the bitmap from LIVE representing the live on entry blocks for |
4ee9c684 | 286 | partition P. */ |
287 | ||
288 | static inline bitmap | |
30928c44 | 289 | live_on_entry (tree_live_info_p live, basic_block bb) |
4ee9c684 | 290 | { |
e95895ef | 291 | gcc_checking_assert (live->livein |
34154e27 | 292 | && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
293 | && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
30928c44 | 294 | |
4fb07d00 | 295 | return &live->livein[bb->index]; |
4ee9c684 | 296 | } |
297 | ||
298 | ||
299 | /* Return the bitmap from LIVE representing the live on exit partitions from | |
300 | block BB. */ | |
301 | ||
302 | static inline bitmap | |
303 | live_on_exit (tree_live_info_p live, basic_block bb) | |
304 | { | |
e95895ef | 305 | gcc_checking_assert (live->liveout |
34154e27 | 306 | && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
307 | && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
4ee9c684 | 308 | |
4fb07d00 | 309 | return &live->liveout[bb->index]; |
4ee9c684 | 310 | } |
311 | ||
312 | ||
313 | /* Return the partition map which the information in LIVE utilizes. */ | |
314 | ||
48e1416a | 315 | static inline var_map |
4ee9c684 | 316 | live_var_map (tree_live_info_p live) |
317 | { | |
318 | return live->map; | |
319 | } | |
320 | ||
321 | ||
4ee9c684 | 322 | /* Mark partition P as live on entry to basic block BB in LIVE. */ |
323 | ||
48e1416a | 324 | static inline void |
4ee9c684 | 325 | make_live_on_entry (tree_live_info_p live, basic_block bb , int p) |
326 | { | |
4fb07d00 | 327 | bitmap_set_bit (&live->livein[bb->index], p); |
4ee9c684 | 328 | bitmap_set_bit (live->global, p); |
329 | } | |
330 | ||
4ee9c684 | 331 | #endif /* _TREE_SSA_LIVE_H */ |