1/* Routines for liveness in SSA trees.
2   Copyright (C) 2003-2015 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} *var_map;
66
67
68/* Value used to represent no partition number.  */
69#define NO_PARTITION		-1
70
71extern var_map init_var_map (int);
72extern void delete_var_map (var_map);
73extern int var_union (var_map, tree, tree);
74extern void partition_view_normal (var_map, bool);
75extern void partition_view_bitmap (var_map, bitmap, bool);
76extern void dump_scope_blocks (FILE *, int);
77extern void debug_scope_block (tree, int);
78extern void debug_scope_blocks (int);
79extern void remove_unused_locals (void);
80extern void dump_var_map (FILE *, var_map);
81extern void debug (_var_map &ref);
82extern void debug (_var_map *ptr);
83#ifdef ENABLE_CHECKING
84extern void register_ssa_partition_check (tree ssa_var);
85#endif
86
87
88/* Return number of partitions in MAP.  */
89
90static inline unsigned
91num_var_partitions (var_map map)
92{
93  return map->num_partitions;
94}
95
96
97/* Given partition index I from MAP, return the variable which represents that
98   partition.  */
99
100static inline tree
101partition_to_var (var_map map, int i)
102{
103  tree name;
104  if (map->view_to_partition)
105    i = map->view_to_partition[i];
106  i = partition_find (map->var_partition, i);
107  name = ssa_name (i);
108  return name;
109}
110
111
112/* Given ssa_name VERSION, if it has a partition in MAP,  return the var it
113   is associated with.  Otherwise return NULL.  */
114
115static inline tree
116version_to_var (var_map map, int version)
117{
118  int part;
119  part = partition_find (map->var_partition, version);
120  if (map->partition_to_view)
121    part = map->partition_to_view[part];
122  if (part == NO_PARTITION)
123    return NULL_TREE;
124
125  return partition_to_var (map, part);
126}
127
128
129/* Given VAR, return the partition number in MAP which contains it.
130   NO_PARTITION is returned if it's not in any partition.  */
131
132static inline int
133var_to_partition (var_map map, tree var)
134{
135  int part;
136
137  part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
138  if (map->partition_to_view)
139    part = map->partition_to_view[part];
140  return part;
141}
142
143
144/* Given VAR, return the variable which represents the entire partition
145   it is a member of in MAP.  NULL is returned if it is not in a partition.  */
146
147static inline tree
148var_to_partition_to_var (var_map map, tree var)
149{
150  int part;
151
152  part = var_to_partition (map, var);
153  if (part == NO_PARTITION)
154    return NULL_TREE;
155  return partition_to_var (map, part);
156}
157
158
159/* Return the index into the basevar table for PARTITION's base in MAP.  */
160
161static inline int
162basevar_index (var_map map, int partition)
163{
164  gcc_checking_assert (partition >= 0
165	      	       && partition <= (int) num_var_partitions (map));
166  return map->partition_to_base_index[partition];
167}
168
169
170/* Return the number of different base variables in MAP.  */
171
172static inline int
173num_basevars (var_map map)
174{
175  return map->num_basevars;
176}
177
178
179
180/* This routine registers a partition for SSA_VAR with MAP.  Any unregistered
181   partitions may be filtered out by a view later.  */
182
183static inline void
184register_ssa_partition (var_map map ATTRIBUTE_UNUSED,
185			tree ssa_var ATTRIBUTE_UNUSED)
186{
187#if defined ENABLE_CHECKING
188  register_ssa_partition_check (ssa_var);
189#endif
190}
191
192
193/*  ---------------- live on entry/exit info ------------------------------
194
195    This structure is used to represent live range information on SSA based
196    trees. A partition map must be provided, and based on the active partitions,
197    live-on-entry information and live-on-exit information can be calculated.
198    As well, partitions are marked as to whether they are global (live
199    outside the basic block they are defined in).
200
201    The live-on-entry information is per block.  It provide a bitmap for
202    each block which has a bit set for each partition that is live on entry to
203    that block.
204
205    The live-on-exit information is per block.  It provides a bitmap for each
206    block indicating which partitions are live on exit from the block.
207
208    For the purposes of this implementation, we treat the elements of a PHI
209    as follows:
210
211       Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
212       originate. They are *NOT* considered live on entry to the block
213       containing the PHI node.
214
215       The Def of a PHI node is *not* considered live on entry to the block.
216       It is considered to be "define early" in the block. Picture it as each
217       block having a stmt (or block-preheader) before the first real stmt in
218       the block which defines all the variables that are defined by PHIs.
219
220    -----------------------------------------------------------------------  */
221
222
223typedef struct tree_live_info_d
224{
225  /* Var map this relates to.  */
226  var_map map;
227
228  /* Bitmap indicating which partitions are global.  */
229  bitmap global;
230
231  /* Bitmaps of live on entry blocks for partition elements.  */
232  bitmap_head *livein;
233
234  /* Bitmaps of what variables are live on exit for a basic blocks.  */
235  bitmap_head *liveout;
236
237  /* Number of basic blocks when live on exit calculated.  */
238  int num_blocks;
239
240  /* Vector used when creating live ranges as a visited stack.  */
241  int *work_stack;
242
243  /* Top of workstack.  */
244  int *stack_top;
245
246  /* Obstacks to allocate the bitmaps on.  */
247  bitmap_obstack livein_obstack;
248  bitmap_obstack liveout_obstack;
249} *tree_live_info_p;
250
251
252#define LIVEDUMP_ENTRY	0x01
253#define LIVEDUMP_EXIT	0x02
254#define LIVEDUMP_ALL	(LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
255extern void delete_tree_live_info (tree_live_info_p);
256extern tree_live_info_p calculate_live_ranges (var_map, bool);
257extern void debug (tree_live_info_d &ref);
258extern void debug (tree_live_info_d *ptr);
259extern void dump_live_info (FILE *, tree_live_info_p, int);
260
261
262/*  Return TRUE if P is marked as a global in LIVE.  */
263
264static inline int
265partition_is_global (tree_live_info_p live, int p)
266{
267  gcc_checking_assert (live->global);
268  return bitmap_bit_p (live->global, p);
269}
270
271
272/* Return the bitmap from LIVE representing the live on entry blocks for
273   partition P.  */
274
275static inline bitmap
276live_on_entry (tree_live_info_p live, basic_block bb)
277{
278  gcc_checking_assert (live->livein
279		       && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
280		       && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
281
282  return &live->livein[bb->index];
283}
284
285
286/* Return the bitmap from LIVE representing the live on exit partitions from
287   block BB.  */
288
289static inline bitmap
290live_on_exit (tree_live_info_p live, basic_block bb)
291{
292  gcc_checking_assert (live->liveout
293		       && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
294		       && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
295
296  return &live->liveout[bb->index];
297}
298
299
300/* Return the partition map which the information in LIVE utilizes.  */
301
302static inline var_map
303live_var_map (tree_live_info_p live)
304{
305  return live->map;
306}
307
308
309/* Merge the live on entry information in LIVE for partitions P1 and P2. Place
310   the result into P1.  Clear P2.  */
311
312static inline void
313live_merge_and_clear (tree_live_info_p live, int p1, int p2)
314{
315  gcc_checking_assert (&live->livein[p1] && &live->livein[p2]);
316  bitmap_ior_into (&live->livein[p1], &live->livein[p2]);
317  bitmap_clear (&live->livein[p2]);
318}
319
320
321/* Mark partition P as live on entry to basic block BB in LIVE.  */
322
323static inline void
324make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
325{
326  bitmap_set_bit (&live->livein[bb->index], p);
327  bitmap_set_bit (live->global, p);
328}
329
330#endif /* _TREE_SSA_LIVE_H  */
331