1*38fd1498Szrj /* Routines for liveness in SSA trees.
2*38fd1498Szrj Copyright (C) 2003-2018 Free Software Foundation, Inc.
3*38fd1498Szrj Contributed by Andrew MacLeod <amacleod@redhat.com>
4*38fd1498Szrj
5*38fd1498Szrj This file is part of GCC.
6*38fd1498Szrj
7*38fd1498Szrj GCC is free software; you can redistribute it and/or modify
8*38fd1498Szrj it under the terms of the GNU General Public License as published by
9*38fd1498Szrj the Free Software Foundation; either version 3, or (at your option)
10*38fd1498Szrj any later version.
11*38fd1498Szrj
12*38fd1498Szrj GCC is distributed in the hope that it will be useful,
13*38fd1498Szrj but WITHOUT ANY WARRANTY; without even the implied warranty of
14*38fd1498Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15*38fd1498Szrj GNU General Public License for more details.
16*38fd1498Szrj
17*38fd1498Szrj You should have received a copy of the GNU General Public License
18*38fd1498Szrj along with GCC; see the file COPYING3. If not see
19*38fd1498Szrj <http://www.gnu.org/licenses/>. */
20*38fd1498Szrj
21*38fd1498Szrj
22*38fd1498Szrj #ifndef _TREE_SSA_LIVE_H
23*38fd1498Szrj #define _TREE_SSA_LIVE_H 1
24*38fd1498Szrj
25*38fd1498Szrj #include "partition.h"
26*38fd1498Szrj
27*38fd1498Szrj /* Used to create the variable mapping when we go out of SSA form.
28*38fd1498Szrj
29*38fd1498Szrj Mapping from an ssa_name to a partition number is maintained, as well as
30*38fd1498Szrj partition number back to ssa_name.
31*38fd1498Szrj
32*38fd1498Szrj This data structure also supports "views", which work on a subset of all
33*38fd1498Szrj partitions. This allows the coalescer to decide what partitions are
34*38fd1498Szrj interesting to it, and only work with those partitions. Whenever the view
35*38fd1498Szrj is changed, the partition numbers change, but none of the partition groupings
36*38fd1498Szrj change. (ie, it is truly a view since it doesn't change anything)
37*38fd1498Szrj
38*38fd1498Szrj The final component of the data structure is the basevar map. This provides
39*38fd1498Szrj a list of all the different base variables which occur in a partition view,
40*38fd1498Szrj and a unique index for each one. Routines are provided to quickly produce
41*38fd1498Szrj the base variable of a partition.
42*38fd1498Szrj
43*38fd1498Szrj Note that members of a partition MUST all have the same base variable. */
44*38fd1498Szrj
45*38fd1498Szrj typedef struct _var_map
46*38fd1498Szrj {
47*38fd1498Szrj /* The partition manager of all variables. */
48*38fd1498Szrj partition var_partition;
49*38fd1498Szrj
50*38fd1498Szrj /* Vector for managing partitions views. */
51*38fd1498Szrj int *partition_to_view;
52*38fd1498Szrj int *view_to_partition;
53*38fd1498Szrj
54*38fd1498Szrj /* Current number of partitions in var_map based on the current view. */
55*38fd1498Szrj unsigned int num_partitions;
56*38fd1498Szrj
57*38fd1498Szrj /* Original full partition size. */
58*38fd1498Szrj unsigned int partition_size;
59*38fd1498Szrj
60*38fd1498Szrj /* Number of base variables in the base var list. */
61*38fd1498Szrj int num_basevars;
62*38fd1498Szrj
63*38fd1498Szrj /* Map of partitions numbers to base variable table indexes. */
64*38fd1498Szrj int *partition_to_base_index;
65*38fd1498Szrj } *var_map;
66*38fd1498Szrj
67*38fd1498Szrj
68*38fd1498Szrj /* Value used to represent no partition number. */
69*38fd1498Szrj #define NO_PARTITION -1
70*38fd1498Szrj
71*38fd1498Szrj extern var_map init_var_map (int);
72*38fd1498Szrj extern void delete_var_map (var_map);
73*38fd1498Szrj extern int var_union (var_map, tree, tree);
74*38fd1498Szrj extern void partition_view_normal (var_map);
75*38fd1498Szrj extern void partition_view_bitmap (var_map, bitmap);
76*38fd1498Szrj extern void dump_scope_blocks (FILE *, dump_flags_t);
77*38fd1498Szrj extern void debug_scope_block (tree, dump_flags_t);
78*38fd1498Szrj extern void debug_scope_blocks (dump_flags_t);
79*38fd1498Szrj extern void remove_unused_locals (void);
80*38fd1498Szrj extern void dump_var_map (FILE *, var_map);
81*38fd1498Szrj extern void debug (_var_map &ref);
82*38fd1498Szrj extern void debug (_var_map *ptr);
83*38fd1498Szrj
84*38fd1498Szrj
85*38fd1498Szrj /* Return number of partitions in MAP. */
86*38fd1498Szrj
87*38fd1498Szrj static inline unsigned
num_var_partitions(var_map map)88*38fd1498Szrj num_var_partitions (var_map map)
89*38fd1498Szrj {
90*38fd1498Szrj return map->num_partitions;
91*38fd1498Szrj }
92*38fd1498Szrj
93*38fd1498Szrj
94*38fd1498Szrj /* Given partition index I from MAP, return the variable which represents that
95*38fd1498Szrj partition. */
96*38fd1498Szrj
97*38fd1498Szrj static inline tree
partition_to_var(var_map map,int i)98*38fd1498Szrj partition_to_var (var_map map, int i)
99*38fd1498Szrj {
100*38fd1498Szrj tree name;
101*38fd1498Szrj if (map->view_to_partition)
102*38fd1498Szrj i = map->view_to_partition[i];
103*38fd1498Szrj i = partition_find (map->var_partition, i);
104*38fd1498Szrj name = ssa_name (i);
105*38fd1498Szrj return name;
106*38fd1498Szrj }
107*38fd1498Szrj
108*38fd1498Szrj
109*38fd1498Szrj /* Given ssa_name VERSION, if it has a partition in MAP, return the var it
110*38fd1498Szrj is associated with. Otherwise return NULL. */
111*38fd1498Szrj
112*38fd1498Szrj static inline tree
version_to_var(var_map map,int version)113*38fd1498Szrj version_to_var (var_map map, int version)
114*38fd1498Szrj {
115*38fd1498Szrj int part;
116*38fd1498Szrj part = partition_find (map->var_partition, version);
117*38fd1498Szrj if (map->partition_to_view)
118*38fd1498Szrj part = map->partition_to_view[part];
119*38fd1498Szrj if (part == NO_PARTITION)
120*38fd1498Szrj return NULL_TREE;
121*38fd1498Szrj
122*38fd1498Szrj return partition_to_var (map, part);
123*38fd1498Szrj }
124*38fd1498Szrj
125*38fd1498Szrj
126*38fd1498Szrj /* Given VAR, return the partition number in MAP which contains it.
127*38fd1498Szrj NO_PARTITION is returned if it's not in any partition. */
128*38fd1498Szrj
129*38fd1498Szrj static inline int
var_to_partition(var_map map,tree var)130*38fd1498Szrj var_to_partition (var_map map, tree var)
131*38fd1498Szrj {
132*38fd1498Szrj int part;
133*38fd1498Szrj
134*38fd1498Szrj part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
135*38fd1498Szrj if (map->partition_to_view)
136*38fd1498Szrj part = map->partition_to_view[part];
137*38fd1498Szrj return part;
138*38fd1498Szrj }
139*38fd1498Szrj
140*38fd1498Szrj
141*38fd1498Szrj /* Given VAR, return the variable which represents the entire partition
142*38fd1498Szrj it is a member of in MAP. NULL is returned if it is not in a partition. */
143*38fd1498Szrj
144*38fd1498Szrj static inline tree
var_to_partition_to_var(var_map map,tree var)145*38fd1498Szrj var_to_partition_to_var (var_map map, tree var)
146*38fd1498Szrj {
147*38fd1498Szrj int part;
148*38fd1498Szrj
149*38fd1498Szrj part = var_to_partition (map, var);
150*38fd1498Szrj if (part == NO_PARTITION)
151*38fd1498Szrj return NULL_TREE;
152*38fd1498Szrj return partition_to_var (map, part);
153*38fd1498Szrj }
154*38fd1498Szrj
155*38fd1498Szrj
156*38fd1498Szrj /* Return the index into the basevar table for PARTITION's base in MAP. */
157*38fd1498Szrj
158*38fd1498Szrj static inline int
basevar_index(var_map map,int partition)159*38fd1498Szrj basevar_index (var_map map, int partition)
160*38fd1498Szrj {
161*38fd1498Szrj gcc_checking_assert (partition >= 0
162*38fd1498Szrj && partition <= (int) num_var_partitions (map));
163*38fd1498Szrj return map->partition_to_base_index[partition];
164*38fd1498Szrj }
165*38fd1498Szrj
166*38fd1498Szrj
167*38fd1498Szrj /* Return the number of different base variables in MAP. */
168*38fd1498Szrj
169*38fd1498Szrj static inline int
num_basevars(var_map map)170*38fd1498Szrj num_basevars (var_map map)
171*38fd1498Szrj {
172*38fd1498Szrj return map->num_basevars;
173*38fd1498Szrj }
174*38fd1498Szrj
175*38fd1498Szrj
176*38fd1498Szrj /* ---------------- live on entry/exit info ------------------------------
177*38fd1498Szrj
178*38fd1498Szrj This structure is used to represent live range information on SSA based
179*38fd1498Szrj trees. A partition map must be provided, and based on the active partitions,
180*38fd1498Szrj live-on-entry information and live-on-exit information can be calculated.
181*38fd1498Szrj As well, partitions are marked as to whether they are global (live
182*38fd1498Szrj outside the basic block they are defined in).
183*38fd1498Szrj
184*38fd1498Szrj The live-on-entry information is per block. It provide a bitmap for
185*38fd1498Szrj each block which has a bit set for each partition that is live on entry to
186*38fd1498Szrj that block.
187*38fd1498Szrj
188*38fd1498Szrj The live-on-exit information is per block. It provides a bitmap for each
189*38fd1498Szrj block indicating which partitions are live on exit from the block.
190*38fd1498Szrj
191*38fd1498Szrj For the purposes of this implementation, we treat the elements of a PHI
192*38fd1498Szrj as follows:
193*38fd1498Szrj
194*38fd1498Szrj Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
195*38fd1498Szrj originate. They are *NOT* considered live on entry to the block
196*38fd1498Szrj containing the PHI node.
197*38fd1498Szrj
198*38fd1498Szrj The Def of a PHI node is *not* considered live on entry to the block.
199*38fd1498Szrj It is considered to be "define early" in the block. Picture it as each
200*38fd1498Szrj block having a stmt (or block-preheader) before the first real stmt in
201*38fd1498Szrj the block which defines all the variables that are defined by PHIs.
202*38fd1498Szrj
203*38fd1498Szrj ----------------------------------------------------------------------- */
204*38fd1498Szrj
205*38fd1498Szrj
206*38fd1498Szrj typedef struct tree_live_info_d
207*38fd1498Szrj {
208*38fd1498Szrj /* Var map this relates to. */
209*38fd1498Szrj var_map map;
210*38fd1498Szrj
211*38fd1498Szrj /* Bitmap indicating which partitions are global. */
212*38fd1498Szrj bitmap global;
213*38fd1498Szrj
214*38fd1498Szrj /* Bitmaps of live on entry blocks for partition elements. */
215*38fd1498Szrj bitmap_head *livein;
216*38fd1498Szrj
217*38fd1498Szrj /* Bitmaps of what variables are live on exit for a basic blocks. */
218*38fd1498Szrj bitmap_head *liveout;
219*38fd1498Szrj
220*38fd1498Szrj /* Number of basic blocks when live on exit calculated. */
221*38fd1498Szrj int num_blocks;
222*38fd1498Szrj
223*38fd1498Szrj /* Vector used when creating live ranges as a visited stack. */
224*38fd1498Szrj int *work_stack;
225*38fd1498Szrj
226*38fd1498Szrj /* Top of workstack. */
227*38fd1498Szrj int *stack_top;
228*38fd1498Szrj
229*38fd1498Szrj /* Obstacks to allocate the bitmaps on. */
230*38fd1498Szrj bitmap_obstack livein_obstack;
231*38fd1498Szrj bitmap_obstack liveout_obstack;
232*38fd1498Szrj } *tree_live_info_p;
233*38fd1498Szrj
234*38fd1498Szrj
235*38fd1498Szrj #define LIVEDUMP_ENTRY 0x01
236*38fd1498Szrj #define LIVEDUMP_EXIT 0x02
237*38fd1498Szrj #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
238*38fd1498Szrj extern void delete_tree_live_info (tree_live_info_p);
239*38fd1498Szrj extern tree_live_info_p calculate_live_ranges (var_map, bool);
240*38fd1498Szrj extern void debug (tree_live_info_d &ref);
241*38fd1498Szrj extern void debug (tree_live_info_d *ptr);
242*38fd1498Szrj extern void dump_live_info (FILE *, tree_live_info_p, int);
243*38fd1498Szrj
244*38fd1498Szrj
245*38fd1498Szrj /* Return TRUE if P is marked as a global in LIVE. */
246*38fd1498Szrj
247*38fd1498Szrj static inline int
partition_is_global(tree_live_info_p live,int p)248*38fd1498Szrj partition_is_global (tree_live_info_p live, int p)
249*38fd1498Szrj {
250*38fd1498Szrj gcc_checking_assert (live->global);
251*38fd1498Szrj return bitmap_bit_p (live->global, p);
252*38fd1498Szrj }
253*38fd1498Szrj
254*38fd1498Szrj
255*38fd1498Szrj /* Return the bitmap from LIVE representing the live on entry blocks for
256*38fd1498Szrj partition P. */
257*38fd1498Szrj
258*38fd1498Szrj static inline bitmap
live_on_entry(tree_live_info_p live,basic_block bb)259*38fd1498Szrj live_on_entry (tree_live_info_p live, basic_block bb)
260*38fd1498Szrj {
261*38fd1498Szrj gcc_checking_assert (live->livein
262*38fd1498Szrj && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
263*38fd1498Szrj && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
264*38fd1498Szrj
265*38fd1498Szrj return &live->livein[bb->index];
266*38fd1498Szrj }
267*38fd1498Szrj
268*38fd1498Szrj
269*38fd1498Szrj /* Return the bitmap from LIVE representing the live on exit partitions from
270*38fd1498Szrj block BB. */
271*38fd1498Szrj
272*38fd1498Szrj static inline bitmap
live_on_exit(tree_live_info_p live,basic_block bb)273*38fd1498Szrj live_on_exit (tree_live_info_p live, basic_block bb)
274*38fd1498Szrj {
275*38fd1498Szrj gcc_checking_assert (live->liveout
276*38fd1498Szrj && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
277*38fd1498Szrj && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
278*38fd1498Szrj
279*38fd1498Szrj return &live->liveout[bb->index];
280*38fd1498Szrj }
281*38fd1498Szrj
282*38fd1498Szrj
283*38fd1498Szrj /* Return the partition map which the information in LIVE utilizes. */
284*38fd1498Szrj
285*38fd1498Szrj static inline var_map
live_var_map(tree_live_info_p live)286*38fd1498Szrj live_var_map (tree_live_info_p live)
287*38fd1498Szrj {
288*38fd1498Szrj return live->map;
289*38fd1498Szrj }
290*38fd1498Szrj
291*38fd1498Szrj
292*38fd1498Szrj /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
293*38fd1498Szrj the result into P1. Clear P2. */
294*38fd1498Szrj
295*38fd1498Szrj static inline void
live_merge_and_clear(tree_live_info_p live,int p1,int p2)296*38fd1498Szrj live_merge_and_clear (tree_live_info_p live, int p1, int p2)
297*38fd1498Szrj {
298*38fd1498Szrj gcc_checking_assert (&live->livein[p1] && &live->livein[p2]);
299*38fd1498Szrj bitmap_ior_into (&live->livein[p1], &live->livein[p2]);
300*38fd1498Szrj bitmap_clear (&live->livein[p2]);
301*38fd1498Szrj }
302*38fd1498Szrj
303*38fd1498Szrj
304*38fd1498Szrj /* Mark partition P as live on entry to basic block BB in LIVE. */
305*38fd1498Szrj
306*38fd1498Szrj static inline void
make_live_on_entry(tree_live_info_p live,basic_block bb,int p)307*38fd1498Szrj make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
308*38fd1498Szrj {
309*38fd1498Szrj bitmap_set_bit (&live->livein[bb->index], p);
310*38fd1498Szrj bitmap_set_bit (live->global, p);
311*38fd1498Szrj }
312*38fd1498Szrj
313*38fd1498Szrj #endif /* _TREE_SSA_LIVE_H */
314