Line data Source code
1 : /* Routines for liveness in SSA trees.
2 : Copyright (C) 2003-2026 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 74154028 : 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 74154028 : if (map->outofssa_p || map->bitint)
108 74154028 : 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 123381597 : num_var_partitions (var_map map)
118 : {
119 52182403 : 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 60262015 : partition_to_var (var_map map, int i)
128 : {
129 60262015 : tree name;
130 60262015 : if (map->view_to_partition)
131 60261758 : i = map->view_to_partition[i];
132 60262015 : i = partition_find (map->var_partition, i);
133 60262015 : name = ssa_name (i);
134 60262015 : 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 1538 : version_to_var (var_map map, int version)
143 : {
144 1538 : int part;
145 1538 : part = partition_find (map->var_partition, version);
146 1538 : if (map->partition_to_view)
147 1538 : part = map->partition_to_view[part];
148 1538 : if (part == NO_PARTITION)
149 : return NULL_TREE;
150 :
151 492 : 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 526479871 : var_to_partition (var_map map, tree var)
160 : {
161 526479871 : int part;
162 :
163 526479871 : part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
164 526479871 : if (map->partition_to_view)
165 526479871 : part = map->partition_to_view[part];
166 526479871 : 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 2906812 : var_to_partition_to_var (var_map map, tree var)
175 : {
176 2906812 : int part;
177 :
178 2906812 : part = var_to_partition (map, var);
179 2906812 : if (part == NO_PARTITION)
180 : return NULL_TREE;
181 2906812 : 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 70155198 : basevar_index (var_map map, int partition)
189 : {
190 70155198 : gcc_checking_assert (partition >= 0
191 : && partition <= (int) num_var_partitions (map));
192 70155198 : 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 1293864 : num_basevars (var_map map)
200 : {
201 1293864 : 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 : /* Bitmaps of live on entry blocks for partition elements. */
241 : bitmap_head *livein;
242 :
243 : /* Bitmaps of what variables are live on exit for a basic blocks. */
244 : bitmap_head *liveout;
245 :
246 : /* Number of basic blocks when live on exit calculated. */
247 : int num_blocks;
248 :
249 : /* Vector used when creating live ranges as a visited stack. */
250 : int *work_stack;
251 :
252 : /* Top of workstack. */
253 : int *stack_top;
254 :
255 : /* Obstacks to allocate the bitmaps on. */
256 : bitmap_obstack livein_obstack;
257 : bitmap_obstack liveout_obstack;
258 : } *tree_live_info_p;
259 :
260 :
261 : #define LIVEDUMP_ENTRY 0x01
262 : #define LIVEDUMP_EXIT 0x02
263 : #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
264 : extern void delete_tree_live_info (tree_live_info_p);
265 : extern tree_live_info_p calculate_live_ranges (var_map, bool);
266 : extern void debug (tree_live_info_d &ref);
267 : extern void debug (tree_live_info_d *ptr);
268 : extern void dump_live_info (FILE *, tree_live_info_p, int);
269 :
270 : typedef hash_map<int_hash <unsigned int, -1U>, unsigned int> live_vars_map;
271 : extern vec<bitmap_head> compute_live_vars (struct function *, live_vars_map *);
272 : extern bitmap live_vars_at_stmt (vec<bitmap_head> &, live_vars_map *,
273 : gimple *);
274 : extern void destroy_live_vars (vec<bitmap_head> &);
275 :
276 :
277 : /* Return the bitmap from LIVE representing the live on entry blocks for
278 : partition P. */
279 :
280 : inline bitmap
281 59070325 : live_on_entry (tree_live_info_p live, basic_block bb)
282 : {
283 59070325 : gcc_checking_assert (live->livein
284 : && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
285 : && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
286 :
287 59070325 : return &live->livein[bb->index];
288 : }
289 :
290 :
291 : /* Return the bitmap from LIVE representing the live on exit partitions from
292 : block BB. */
293 :
294 : inline bitmap
295 11806736 : live_on_exit (tree_live_info_p live, basic_block bb)
296 : {
297 11806736 : gcc_checking_assert (live->liveout
298 : && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
299 : && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
300 :
301 11806736 : return &live->liveout[bb->index];
302 : }
303 :
304 :
305 : /* Return the partition map which the information in LIVE utilizes. */
306 :
307 : inline var_map
308 1293864 : live_var_map (tree_live_info_p live)
309 : {
310 1293864 : return live->map;
311 : }
312 :
313 :
314 : /* Mark partition P as live on entry to basic block BB in LIVE. */
315 :
316 : inline void
317 : make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
318 : {
319 : bitmap_set_bit (&live->livein[bb->index], p);
320 : }
321 :
322 :
323 : /* On-demand virtual operand global live analysis. There is at most
324 : a single virtual operand live at a time, the following computes and
325 : caches the virtual operand live at the exit of a basic block
326 : supporting related live-in and live-on-edge queries. It requires
327 : up-to-date marked backedges. */
328 :
329 : class virtual_operand_live
330 : {
331 : public:
332 2082802 : virtual_operand_live() : liveout (nullptr) {}
333 2082802 : ~virtual_operand_live()
334 : {
335 2082802 : if (liveout)
336 196543 : free (liveout);
337 2082802 : }
338 :
339 : tree get_live_in (basic_block bb);
340 : tree get_live_out (basic_block bb);
341 : tree get_live_on_edge (edge e) { return get_live_out (e->src); }
342 :
343 : private:
344 : void init ();
345 :
346 : tree *liveout;
347 : };
348 :
349 :
350 : #endif /* _TREE_SSA_LIVE_H */
|
