1 | /* Routines for liveness in SSA trees. |
2 | Copyright (C) 2003-2023 Free Software Foundation, Inc. |
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 |
9 | the Free Software Foundation; either version 3, or (at your option) |
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 |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ |
20 | |
21 | |
22 | #ifndef _TREE_SSA_LIVE_H |
23 | #define _TREE_SSA_LIVE_H 1 |
24 | |
25 | #include "partition.h" |
26 | |
27 | /* Used to create the variable mapping when we go out of SSA form. |
28 | |
29 | Mapping from an ssa_name to a partition number is maintained, as well as |
30 | partition number back to ssa_name. |
31 | |
32 | This data structure also supports "views", which work on a subset of all |
33 | partitions. This allows the coalescer to decide what partitions are |
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 |
36 | change. (ie, it is truly a view since it doesn't change anything) |
37 | |
38 | The final component of the data structure is the basevar map. This provides |
39 | a list of all the different base variables which occur in a partition view, |
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 | |
45 | typedef struct _var_map |
46 | { |
47 | /* The partition manager of all variables. */ |
48 | partition var_partition; |
49 | |
50 | /* Vector for managing partitions views. */ |
51 | int *partition_to_view; |
52 | int *view_to_partition; |
53 | |
54 | /* Current number of partitions in var_map based on the current view. */ |
55 | unsigned int num_partitions; |
56 | |
57 | /* Original full partition size. */ |
58 | unsigned int partition_size; |
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; |
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 | /* If non-NULL, only coalesce SSA_NAMEs from this bitmap, and try harder |
74 | for those (for bitint lowering pass). */ |
75 | bitmap bitint; |
76 | |
77 | /* True if this map is for out-of-ssa, otherwise for live range |
78 | computation. When for out-of-ssa, it also means the var map is computed |
79 | for whole current function. */ |
80 | bool outofssa_p; |
81 | } *var_map; |
82 | |
83 | |
84 | /* Value used to represent no partition number. */ |
85 | #define NO_PARTITION -1 |
86 | |
87 | extern var_map init_var_map (int, class loop * = NULL, bitmap = NULL); |
88 | extern void delete_var_map (var_map); |
89 | extern int var_union (var_map, tree, tree); |
90 | extern void partition_view_normal (var_map); |
91 | extern void partition_view_bitmap (var_map, bitmap); |
92 | extern void dump_scope_blocks (FILE *, dump_flags_t); |
93 | extern void debug_scope_block (tree, dump_flags_t); |
94 | extern void debug_scope_blocks (dump_flags_t); |
95 | extern void remove_unused_locals (void); |
96 | extern void dump_var_map (FILE *, var_map); |
97 | extern void debug (_var_map &ref); |
98 | extern void debug (_var_map *ptr); |
99 | |
100 | |
101 | /* Return TRUE if region of the MAP contains basic block BB. */ |
102 | |
103 | inline bool |
104 | region_contains_p (var_map map, basic_block bb) |
105 | { |
106 | /* It's possible that the function is called with ENTRY_BLOCK/EXIT_BLOCK. */ |
107 | if (map->outofssa_p || map->bitint) |
108 | return (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK); |
109 | |
110 | return bitmap_bit_p (map->bmp_bbs, bb->index); |
111 | } |
112 | |
113 | |
114 | /* Return number of partitions in MAP. */ |
115 | |
116 | inline unsigned |
117 | num_var_partitions (var_map map) |
118 | { |
119 | return map->num_partitions; |
120 | } |
121 | |
122 | |
123 | /* Given partition index I from MAP, return the variable which represents that |
124 | partition. */ |
125 | |
126 | inline tree |
127 | partition_to_var (var_map map, int i) |
128 | { |
129 | tree name; |
130 | if (map->view_to_partition) |
131 | i = map->view_to_partition[i]; |
132 | i = partition_find (map->var_partition, i); |
133 | name = ssa_name (i); |
134 | return name; |
135 | } |
136 | |
137 | |
138 | /* Given ssa_name VERSION, if it has a partition in MAP, return the var it |
139 | is associated with. Otherwise return NULL. */ |
140 | |
141 | inline tree |
142 | version_to_var (var_map map, int version) |
143 | { |
144 | int part; |
145 | part = partition_find (map->var_partition, version); |
146 | if (map->partition_to_view) |
147 | part = map->partition_to_view[part]; |
148 | if (part == NO_PARTITION) |
149 | return NULL_TREE; |
150 | |
151 | return partition_to_var (map, i: part); |
152 | } |
153 | |
154 | |
155 | /* Given VAR, return the partition number in MAP which contains it. |
156 | NO_PARTITION is returned if it's not in any partition. */ |
157 | |
158 | inline int |
159 | var_to_partition (var_map map, tree var) |
160 | { |
161 | int part; |
162 | |
163 | part = partition_find (map->var_partition, SSA_NAME_VERSION (var)); |
164 | if (map->partition_to_view) |
165 | part = map->partition_to_view[part]; |
166 | return part; |
167 | } |
168 | |
169 | |
170 | /* Given VAR, return the variable which represents the entire partition |
171 | it is a member of in MAP. NULL is returned if it is not in a partition. */ |
172 | |
173 | inline tree |
174 | var_to_partition_to_var (var_map map, tree var) |
175 | { |
176 | int part; |
177 | |
178 | part = var_to_partition (map, var); |
179 | if (part == NO_PARTITION) |
180 | return NULL_TREE; |
181 | return partition_to_var (map, i: part); |
182 | } |
183 | |
184 | |
185 | /* Return the index into the basevar table for PARTITION's base in MAP. */ |
186 | |
187 | inline int |
188 | basevar_index (var_map map, int partition) |
189 | { |
190 | gcc_checking_assert (partition >= 0 |
191 | && partition <= (int) num_var_partitions (map)); |
192 | return map->partition_to_base_index[partition]; |
193 | } |
194 | |
195 | |
196 | /* Return the number of different base variables in MAP. */ |
197 | |
198 | inline int |
199 | num_basevars (var_map map) |
200 | { |
201 | return map->num_basevars; |
202 | } |
203 | |
204 | |
205 | /* ---------------- live on entry/exit info ------------------------------ |
206 | |
207 | This structure is used to represent live range information on SSA based |
208 | trees. A partition map must be provided, and based on the active partitions, |
209 | live-on-entry information and live-on-exit information can be calculated. |
210 | As well, partitions are marked as to whether they are global (live |
211 | outside the basic block they are defined in). |
212 | |
213 | The live-on-entry information is per block. It provide a bitmap for |
214 | each block which has a bit set for each partition that is live on entry to |
215 | that block. |
216 | |
217 | The live-on-exit information is per block. It provides a bitmap for each |
218 | block indicating which partitions are live on exit from the block. |
219 | |
220 | For the purposes of this implementation, we treat the elements of a PHI |
221 | as follows: |
222 | |
223 | Uses in a PHI are considered LIVE-ON-EXIT to the block from which they |
224 | originate. They are *NOT* considered live on entry to the block |
225 | containing the PHI node. |
226 | |
227 | The Def of a PHI node is *not* considered live on entry to the block. |
228 | It is considered to be "define early" in the block. Picture it as each |
229 | block having a stmt (or block-preheader) before the first real stmt in |
230 | the block which defines all the variables that are defined by PHIs. |
231 | |
232 | ----------------------------------------------------------------------- */ |
233 | |
234 | |
235 | typedef struct tree_live_info_d |
236 | { |
237 | /* Var map this relates to. */ |
238 | var_map map; |
239 | |
240 | /* Bitmap indicating which partitions are global. */ |
241 | bitmap global; |
242 | |
243 | /* Bitmaps of live on entry blocks for partition elements. */ |
244 | bitmap_head *livein; |
245 | |
246 | /* Bitmaps of what variables are live on exit for a basic blocks. */ |
247 | bitmap_head *liveout; |
248 | |
249 | /* Number of basic blocks when live on exit calculated. */ |
250 | int num_blocks; |
251 | |
252 | /* Vector used when creating live ranges as a visited stack. */ |
253 | int *work_stack; |
254 | |
255 | /* Top of workstack. */ |
256 | int *stack_top; |
257 | |
258 | /* Obstacks to allocate the bitmaps on. */ |
259 | bitmap_obstack livein_obstack; |
260 | bitmap_obstack liveout_obstack; |
261 | } *tree_live_info_p; |
262 | |
263 | |
264 | #define LIVEDUMP_ENTRY 0x01 |
265 | #define LIVEDUMP_EXIT 0x02 |
266 | #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT) |
267 | extern void delete_tree_live_info (tree_live_info_p); |
268 | extern tree_live_info_p calculate_live_ranges (var_map, bool); |
269 | extern void debug (tree_live_info_d &ref); |
270 | extern void debug (tree_live_info_d *ptr); |
271 | extern void dump_live_info (FILE *, tree_live_info_p, int); |
272 | |
273 | typedef hash_map<int_hash <unsigned int, -1U>, unsigned int> live_vars_map; |
274 | extern vec<bitmap_head> compute_live_vars (struct function *, live_vars_map *); |
275 | extern bitmap live_vars_at_stmt (vec<bitmap_head> &, live_vars_map *, |
276 | gimple *); |
277 | extern void destroy_live_vars (vec<bitmap_head> &); |
278 | |
279 | /* Return TRUE if P is marked as a global in LIVE. */ |
280 | |
281 | inline int |
282 | partition_is_global (tree_live_info_p live, int p) |
283 | { |
284 | gcc_checking_assert (live->global); |
285 | return bitmap_bit_p (live->global, p); |
286 | } |
287 | |
288 | |
289 | /* Return the bitmap from LIVE representing the live on entry blocks for |
290 | partition P. */ |
291 | |
292 | inline bitmap |
293 | live_on_entry (tree_live_info_p live, basic_block bb) |
294 | { |
295 | gcc_checking_assert (live->livein |
296 | && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
297 | && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); |
298 | |
299 | return &live->livein[bb->index]; |
300 | } |
301 | |
302 | |
303 | /* Return the bitmap from LIVE representing the live on exit partitions from |
304 | block BB. */ |
305 | |
306 | inline bitmap |
307 | live_on_exit (tree_live_info_p live, basic_block bb) |
308 | { |
309 | gcc_checking_assert (live->liveout |
310 | && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
311 | && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); |
312 | |
313 | return &live->liveout[bb->index]; |
314 | } |
315 | |
316 | |
317 | /* Return the partition map which the information in LIVE utilizes. */ |
318 | |
319 | inline var_map |
320 | live_var_map (tree_live_info_p live) |
321 | { |
322 | return live->map; |
323 | } |
324 | |
325 | |
326 | /* Mark partition P as live on entry to basic block BB in LIVE. */ |
327 | |
328 | inline void |
329 | make_live_on_entry (tree_live_info_p live, basic_block bb , int p) |
330 | { |
331 | bitmap_set_bit (&live->livein[bb->index], p); |
332 | bitmap_set_bit (live->global, p); |
333 | } |
334 | |
335 | |
336 | /* On-demand virtual operand global live analysis. There is at most |
337 | a single virtual operand live at a time, the following computes and |
338 | caches the virtual operand live at the exit of a basic block |
339 | supporting related live-in and live-on-edge queries. It requires |
340 | up-to-date marked backedges. */ |
341 | |
342 | class virtual_operand_live |
343 | { |
344 | public: |
345 | virtual_operand_live() : liveout (nullptr) {} |
346 | ~virtual_operand_live() |
347 | { |
348 | if (liveout) |
349 | free (ptr: liveout); |
350 | } |
351 | |
352 | tree get_live_in (basic_block bb); |
353 | tree get_live_out (basic_block bb); |
354 | tree get_live_on_edge (edge e) { return get_live_out (bb: e->src); } |
355 | |
356 | private: |
357 | void init (); |
358 | |
359 | tree *liveout; |
360 | }; |
361 | |
362 | |
363 | #endif /* _TREE_SSA_LIVE_H */ |
364 | |