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
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
45typedef 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
87extern var_map init_var_map (int, class loop * = NULL, bitmap = NULL);
88extern void delete_var_map (var_map);
89extern int var_union (var_map, tree, tree);
90extern void partition_view_normal (var_map);
91extern void partition_view_bitmap (var_map, bitmap);
92extern void dump_scope_blocks (FILE *, dump_flags_t);
93extern void debug_scope_block (tree, dump_flags_t);
94extern void debug_scope_blocks (dump_flags_t);
95extern void remove_unused_locals (void);
96extern void dump_var_map (FILE *, var_map);
97extern void debug (_var_map &ref);
98extern void debug (_var_map *ptr);
99
100
101/* Return TRUE if region of the MAP contains basic block BB. */
102
103inline bool
104region_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
116inline unsigned
117num_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
126inline tree
127partition_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
141inline tree
142version_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
158inline int
159var_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
173inline tree
174var_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
187inline int
188basevar_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
198inline int
199num_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
235typedef 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)
267extern void delete_tree_live_info (tree_live_info_p);
268extern tree_live_info_p calculate_live_ranges (var_map, bool);
269extern void debug (tree_live_info_d &ref);
270extern void debug (tree_live_info_d *ptr);
271extern void dump_live_info (FILE *, tree_live_info_p, int);
272
273typedef hash_map<int_hash <unsigned int, -1U>, unsigned int> live_vars_map;
274extern vec<bitmap_head> compute_live_vars (struct function *, live_vars_map *);
275extern bitmap live_vars_at_stmt (vec<bitmap_head> &, live_vars_map *,
276 gimple *);
277extern void destroy_live_vars (vec<bitmap_head> &);
278
279/* Return TRUE if P is marked as a global in LIVE. */
280
281inline int
282partition_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
292inline bitmap
293live_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
306inline bitmap
307live_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
319inline var_map
320live_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
328inline void
329make_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
342class virtual_operand_live
343{
344public:
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
356private:
357 void init ();
358
359 tree *liveout;
360};
361
362
363#endif /* _TREE_SSA_LIVE_H */
364

source code of gcc/tree-ssa-live.h