Branch data Line data Source code
1 : : /* Routines for liveness in SSA trees.
2 : : Copyright (C) 2003-2024 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 : 67258006 : 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 : 67258006 : if (map->outofssa_p || map->bitint)
108 : 67258006 : return (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK);
109 : :
110 : 0 : return bitmap_bit_p (map->bmp_bbs, bb->index);
111 : : }
112 : :
113 : :
114 : : /* Return number of partitions in MAP. */
115 : :
116 : : inline unsigned
117 : 111799479 : num_var_partitions (var_map map)
118 : : {
119 : 48180366 : 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 : 54926151 : partition_to_var (var_map map, int i)
128 : : {
129 : 54926151 : tree name;
130 : 54926151 : if (map->view_to_partition)
131 : 54925989 : i = map->view_to_partition[i];
132 : 54926151 : i = partition_find (map->var_partition, i);
133 : 54926151 : name = ssa_name (i);
134 : 54926151 : 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 : 1157 : version_to_var (var_map map, int version)
143 : : {
144 : 1157 : int part;
145 : 1157 : part = partition_find (map->var_partition, version);
146 : 1157 : if (map->partition_to_view)
147 : 1157 : part = map->partition_to_view[part];
148 : 1157 : if (part == NO_PARTITION)
149 : : return NULL_TREE;
150 : :
151 : 344 : return partition_to_var (map, 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 : 482338213 : var_to_partition (var_map map, tree var)
160 : : {
161 : 482338213 : int part;
162 : :
163 : 482338213 : part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
164 : 482338213 : if (map->partition_to_view)
165 : 482338213 : part = map->partition_to_view[part];
166 : 482338213 : 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 : 2545404 : var_to_partition_to_var (var_map map, tree var)
175 : : {
176 : 2545404 : int part;
177 : :
178 : 2545404 : part = var_to_partition (map, var);
179 : 2545404 : if (part == NO_PARTITION)
180 : : return NULL_TREE;
181 : 2545404 : return partition_to_var (map, part);
182 : : }
183 : :
184 : :
185 : : /* Return the index into the basevar table for PARTITION's base in MAP. */
186 : :
187 : : inline int
188 : 62631178 : basevar_index (var_map map, int partition)
189 : : {
190 : 62631178 : gcc_checking_assert (partition >= 0
191 : : && partition <= (int) num_var_partitions (map));
192 : 62631178 : 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 : 1248243 : num_basevars (var_map map)
200 : : {
201 : 1248243 : 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 : 53258933 : live_on_entry (tree_live_info_p live, basic_block bb)
294 : : {
295 : 53258933 : gcc_checking_assert (live->livein
296 : : && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
297 : : && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
298 : :
299 : 53258933 : 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 : 10762132 : live_on_exit (tree_live_info_p live, basic_block bb)
308 : : {
309 : 10762132 : gcc_checking_assert (live->liveout
310 : : && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
311 : : && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
312 : :
313 : 10762132 : 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 : 1248243 : live_var_map (tree_live_info_p live)
321 : : {
322 : 1248243 : 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 : 1970613 : virtual_operand_live() : liveout (nullptr) {}
346 : 1970613 : ~virtual_operand_live()
347 : : {
348 : 1970613 : if (liveout)
349 : 202736 : free (liveout);
350 : 1970613 : }
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 (e->src); }
355 : :
356 : : private:
357 : : void init ();
358 : :
359 : : tree *liveout;
360 : : };
361 : :
362 : :
363 : : #endif /* _TREE_SSA_LIVE_H */
|
