1/* Routines for liveness in SSA trees.
2   Copyright (C) 2003-2020 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  /* 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;
77} *var_map;
78
79
80/* Value used to represent no partition number.  */
81#define NO_PARTITION		-1
82
83extern var_map init_var_map (int, class loop* = NULL);
84extern void delete_var_map (var_map);
85extern int var_union (var_map, tree, tree);
86extern void partition_view_normal (var_map);
87extern void partition_view_bitmap (var_map, bitmap);
88extern void dump_scope_blocks (FILE *, dump_flags_t);
89extern void debug_scope_block (tree, dump_flags_t);
90extern void debug_scope_blocks (dump_flags_t);
91extern void remove_unused_locals (void);
92extern void dump_var_map (FILE *, var_map);
93extern void debug (_var_map &ref);
94extern void debug (_var_map *ptr);
95
96
97/* Return TRUE if region of the MAP contains basic block BB.  */
98
99inline bool
100region_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
110/* Return number of partitions in MAP.  */
111
112static inline unsigned
113num_var_partitions (var_map map)
114{
115  return map->num_partitions;
116}
117
118
119/* Given partition index I from MAP, return the variable which represents that
120   partition.  */
121
122static inline tree
123partition_to_var (var_map map, int i)
124{
125  tree name;
126  if (map->view_to_partition)
127    i = map->view_to_partition[i];
128  i = partition_find (map->var_partition, i);
129  name = ssa_name (i);
130  return name;
131}
132
133
134/* Given ssa_name VERSION, if it has a partition in MAP,  return the var it
135   is associated with.  Otherwise return NULL.  */
136
137static inline tree
138version_to_var (var_map map, int version)
139{
140  int part;
141  part = partition_find (map->var_partition, version);
142  if (map->partition_to_view)
143    part = map->partition_to_view[part];
144  if (part == NO_PARTITION)
145    return NULL_TREE;
146
147  return partition_to_var (map, part);
148}
149
150
151/* Given VAR, return the partition number in MAP which contains it.
152   NO_PARTITION is returned if it's not in any partition.  */
153
154static inline int
155var_to_partition (var_map map, tree var)
156{
157  int part;
158
159  part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
160  if (map->partition_to_view)
161    part = map->partition_to_view[part];
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
169static inline tree
170var_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
181/* Return the index into the basevar table for PARTITION's base in MAP.  */
182
183static inline int
184basevar_index (var_map map, int partition)
185{
186  gcc_checking_assert (partition >= 0
187	      	       && partition <= (int) num_var_partitions (map));
188  return map->partition_to_base_index[partition];
189}
190
191
192/* Return the number of different base variables in MAP.  */
193
194static inline int
195num_basevars (var_map map)
196{
197  return map->num_basevars;
198}
199
200
201/*  ---------------- live on entry/exit info ------------------------------
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.
206    As well, partitions are marked as to whether they are global (live
207    outside the basic block they are defined in).
208
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
211    that block.
212
213    The live-on-exit information is per block.  It provides a bitmap for each
214    block indicating which partitions are live on exit from the block.
215
216    For the purposes of this implementation, we treat the elements of a PHI
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
225       block having a stmt (or block-preheader) before the first real stmt in
226       the block which defines all the variables that are defined by PHIs.
227
228    -----------------------------------------------------------------------  */
229
230
231typedef 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
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;
244
245  /* Number of basic blocks when live on exit calculated.  */
246  int num_blocks;
247
248  /* Vector used when creating live ranges as a visited stack.  */
249  int *work_stack;
250
251  /* Top of workstack.  */
252  int *stack_top;
253
254  /* Obstacks to allocate the bitmaps on.  */
255  bitmap_obstack livein_obstack;
256  bitmap_obstack liveout_obstack;
257} *tree_live_info_p;
258
259
260#define LIVEDUMP_ENTRY	0x01
261#define LIVEDUMP_EXIT	0x02
262#define LIVEDUMP_ALL	(LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
263extern void delete_tree_live_info (tree_live_info_p);
264extern tree_live_info_p calculate_live_ranges (var_map, bool);
265extern void debug (tree_live_info_d &ref);
266extern void debug (tree_live_info_d *ptr);
267extern void dump_live_info (FILE *, tree_live_info_p, int);
268
269typedef hash_map<int_hash <unsigned int, -1U>, unsigned int> live_vars_map;
270extern vec<bitmap_head> compute_live_vars (struct function *, live_vars_map *);
271extern bitmap live_vars_at_stmt (vec<bitmap_head> &, live_vars_map *,
272				 gimple *);
273extern void destroy_live_vars (vec<bitmap_head> &);
274
275/*  Return TRUE if P is marked as a global in LIVE.  */
276
277static inline int
278partition_is_global (tree_live_info_p live, int p)
279{
280  gcc_checking_assert (live->global);
281  return bitmap_bit_p (live->global, p);
282}
283
284
285/* Return the bitmap from LIVE representing the live on entry blocks for
286   partition P.  */
287
288static inline bitmap
289live_on_entry (tree_live_info_p live, basic_block bb)
290{
291  gcc_checking_assert (live->livein
292		       && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
293		       && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
294
295  return &live->livein[bb->index];
296}
297
298
299/* Return the bitmap from LIVE representing the live on exit partitions from
300   block BB.  */
301
302static inline bitmap
303live_on_exit (tree_live_info_p live, basic_block bb)
304{
305  gcc_checking_assert (live->liveout
306		       && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
307		       && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
308
309  return &live->liveout[bb->index];
310}
311
312
313/* Return the partition map which the information in LIVE utilizes.  */
314
315static inline var_map
316live_var_map (tree_live_info_p live)
317{
318  return live->map;
319}
320
321
322/* Mark partition P as live on entry to basic block BB in LIVE.  */
323
324static inline void
325make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
326{
327  bitmap_set_bit (&live->livein[bb->index], p);
328  bitmap_set_bit (live->global, p);
329}
330
331#endif /* _TREE_SSA_LIVE_H  */
332