|
0
|
1 /* Routines for liveness in SSA trees.
|
|
|
2 Copyright (C) 2003, 2004, 2005, 2007, 2008 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 #include "vecprim.h"
|
|
|
27
|
|
|
28
|
|
|
29
|
|
|
30 /* Used to create the variable mapping when we go out of SSA form.
|
|
|
31
|
|
|
32 Mapping from an ssa_name to a partition number is maintained, as well as
|
|
|
33 partition number to back to ssa_name. A partition can also be represented
|
|
|
34 by a non-ssa_name variable. This allows ssa_names and their partition to
|
|
|
35 be coalesced with live on entry compiler variables, as well as eventually
|
|
|
36 having real compiler variables assigned to each partition as part of the
|
|
|
37 final stage of going of of ssa.
|
|
|
38
|
|
|
39 Non-ssa_names maintain their partition index in the variable annotation.
|
|
|
40
|
|
|
41 This data structure also supports "views", which work on a subset of all
|
|
|
42 partitions. This allows the coalescer to decide what partitions are
|
|
|
43 interesting to it, and only work with those partitions. Whenever the view
|
|
|
44 is changed, the partition numbers change, but none of the partition groupings
|
|
|
45 change. (ie, it is truly a view since it doesn't change anything)
|
|
|
46
|
|
|
47 The final component of the data structure is the basevar map. This provides
|
|
|
48 a list of all the different base variables which occur in a partition view,
|
|
|
49 and a unique index for each one. Routines are provided to quickly produce
|
|
|
50 the base variable of a partition.
|
|
|
51
|
|
|
52 Note that members of a partition MUST all have the same base variable. */
|
|
|
53
|
|
|
54 typedef struct _var_map
|
|
|
55 {
|
|
|
56 /* The partition manager of all variables. */
|
|
|
57 partition var_partition;
|
|
|
58
|
|
|
59 /* Vector for managing partitions views. */
|
|
|
60 int *partition_to_view;
|
|
|
61 int *view_to_partition;
|
|
|
62
|
|
|
63 /* Mapping of partition numbers to variables. */
|
|
|
64 tree *partition_to_var;
|
|
|
65
|
|
|
66 /* Current number of partitions in var_map based on the current view. */
|
|
|
67 unsigned int num_partitions;
|
|
|
68
|
|
|
69 /* Original full partition size. */
|
|
|
70 unsigned int partition_size;
|
|
|
71
|
|
|
72 /* Number of base variables in the base var list. */
|
|
|
73 int num_basevars;
|
|
|
74
|
|
|
75 /* Map of partitions numbers to base variable table indexes. */
|
|
|
76 int *partition_to_base_index;
|
|
|
77
|
|
|
78 /* Table of base variable's. */
|
|
|
79 VEC (tree, heap) *basevars;
|
|
|
80 } *var_map;
|
|
|
81
|
|
|
82
|
|
|
83 /* Partition number of a non ssa-name variable. */
|
|
|
84 #define VAR_ANN_PARTITION(ann) (ann->partition)
|
|
|
85 /* Index to the basevar table of a non ssa-name variable. */
|
|
|
86 #define VAR_ANN_BASE_INDEX(ann) (ann->base_index)
|
|
|
87
|
|
|
88
|
|
|
89 /* Value used to represent no partition number. */
|
|
|
90 #define NO_PARTITION -1
|
|
|
91
|
|
|
92 extern var_map init_var_map (int);
|
|
|
93 extern void delete_var_map (var_map);
|
|
|
94 extern void dump_var_map (FILE *, var_map);
|
|
|
95 extern int var_union (var_map, tree, tree);
|
|
|
96 extern void change_partition_var (var_map, tree, int);
|
|
|
97 extern void partition_view_normal (var_map, bool);
|
|
|
98 extern void partition_view_bitmap (var_map, bitmap, bool);
|
|
|
99 #ifdef ENABLE_CHECKING
|
|
|
100 extern void register_ssa_partition_check (tree ssa_var);
|
|
|
101 #endif
|
|
|
102
|
|
|
103
|
|
|
104 /* Return number of partitions in MAP. */
|
|
|
105
|
|
|
106 static inline unsigned
|
|
|
107 num_var_partitions (var_map map)
|
|
|
108 {
|
|
|
109 return map->num_partitions;
|
|
|
110 }
|
|
|
111
|
|
|
112
|
|
|
113 /* Given partition index I from MAP, return the variable which represents that
|
|
|
114 partition. */
|
|
|
115
|
|
|
116 static inline tree
|
|
|
117 partition_to_var (var_map map, int i)
|
|
|
118 {
|
|
|
119 if (map->view_to_partition)
|
|
|
120 i = map->view_to_partition[i];
|
|
|
121 i = partition_find (map->var_partition, i);
|
|
|
122 return map->partition_to_var[i];
|
|
|
123 }
|
|
|
124
|
|
|
125
|
|
|
126 /* Given ssa_name VERSION, if it has a partition in MAP, return the var it
|
|
|
127 is associated with. Otherwise return NULL. */
|
|
|
128
|
|
|
129 static inline tree
|
|
|
130 version_to_var (var_map map, int version)
|
|
|
131 {
|
|
|
132 int part;
|
|
|
133 part = partition_find (map->var_partition, version);
|
|
|
134 if (map->partition_to_view)
|
|
|
135 part = map->partition_to_view[part];
|
|
|
136 if (part == NO_PARTITION)
|
|
|
137 return NULL_TREE;
|
|
|
138
|
|
|
139 return partition_to_var (map, part);
|
|
|
140 }
|
|
|
141
|
|
|
142
|
|
|
143 /* Given VAR, return the partition number in MAP which contains it.
|
|
|
144 NO_PARTITION is returned if it's not in any partition. */
|
|
|
145
|
|
|
146 static inline int
|
|
|
147 var_to_partition (var_map map, tree var)
|
|
|
148 {
|
|
|
149 var_ann_t ann;
|
|
|
150 int part;
|
|
|
151
|
|
|
152 if (TREE_CODE (var) == SSA_NAME)
|
|
|
153 {
|
|
|
154 part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
|
|
|
155 if (map->partition_to_view)
|
|
|
156 part = map->partition_to_view[part];
|
|
|
157 }
|
|
|
158 else
|
|
|
159 {
|
|
|
160 ann = var_ann (var);
|
|
|
161 if (ann && ann->out_of_ssa_tag)
|
|
|
162 part = VAR_ANN_PARTITION (ann);
|
|
|
163 else
|
|
|
164 part = NO_PARTITION;
|
|
|
165 }
|
|
|
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
|
|
|
173 static inline tree
|
|
|
174 var_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, part);
|
|
|
182 }
|
|
|
183
|
|
|
184
|
|
|
185 /* Return the index into the basevar table for PARTITION's base in MAP. */
|
|
|
186
|
|
|
187 static inline int
|
|
|
188 basevar_index (var_map map, int partition)
|
|
|
189 {
|
|
|
190 gcc_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
|
|
|
198 static inline int
|
|
|
199 num_basevars (var_map map)
|
|
|
200 {
|
|
|
201 return map->num_basevars;
|
|
|
202 }
|
|
|
203
|
|
|
204
|
|
|
205
|
|
|
206 /* This routine registers a partition for SSA_VAR with MAP. Any unregistered
|
|
|
207 partitions may be filtered out by a view later. */
|
|
|
208
|
|
|
209 static inline void
|
|
|
210 register_ssa_partition (var_map map, tree ssa_var)
|
|
|
211 {
|
|
|
212 int version;
|
|
|
213
|
|
|
214 #if defined ENABLE_CHECKING
|
|
|
215 register_ssa_partition_check (ssa_var);
|
|
|
216 #endif
|
|
|
217
|
|
|
218 version = SSA_NAME_VERSION (ssa_var);
|
|
|
219 if (map->partition_to_var[version] == NULL_TREE)
|
|
|
220 map->partition_to_var[version] = ssa_var;
|
|
|
221 }
|
|
|
222
|
|
|
223
|
|
|
224 /* ---------------- live on entry/exit info ------------------------------
|
|
|
225
|
|
|
226 This structure is used to represent live range information on SSA based
|
|
|
227 trees. A partition map must be provided, and based on the active partitions,
|
|
|
228 live-on-entry information and live-on-exit information can be calculated.
|
|
|
229 As well, partitions are marked as to whether they are global (live
|
|
|
230 outside the basic block they are defined in).
|
|
|
231
|
|
|
232 The live-on-entry information is per block. It provide a bitmap for
|
|
|
233 each block which has a bit set for each partition that is live on entry to
|
|
|
234 that block.
|
|
|
235
|
|
|
236 The live-on-exit information is per block. It provides a bitmap for each
|
|
|
237 block indicating which partitions are live on exit from the block.
|
|
|
238
|
|
|
239 For the purposes of this implementation, we treat the elements of a PHI
|
|
|
240 as follows:
|
|
|
241
|
|
|
242 Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
|
|
|
243 originate. They are *NOT* considered live on entry to the block
|
|
|
244 containing the PHI node.
|
|
|
245
|
|
|
246 The Def of a PHI node is *not* considered live on entry to the block.
|
|
|
247 It is considered to be "define early" in the block. Picture it as each
|
|
|
248 block having a stmt (or block-preheader) before the first real stmt in
|
|
|
249 the block which defines all the variables that are defined by PHIs.
|
|
|
250
|
|
|
251 ----------------------------------------------------------------------- */
|
|
|
252
|
|
|
253
|
|
|
254 typedef struct tree_live_info_d
|
|
|
255 {
|
|
|
256 /* Var map this relates to. */
|
|
|
257 var_map map;
|
|
|
258
|
|
|
259 /* Bitmap indicating which partitions are global. */
|
|
|
260 bitmap global;
|
|
|
261
|
|
|
262 /* Bitmap of live on entry blocks for partition elements. */
|
|
|
263 bitmap *livein;
|
|
|
264
|
|
|
265 /* Number of basic blocks when live on exit calculated. */
|
|
|
266 int num_blocks;
|
|
|
267
|
|
|
268 /* Vector used when creating live ranges as a visited stack. */
|
|
|
269 int *work_stack;
|
|
|
270
|
|
|
271 /* Top of workstack. */
|
|
|
272 int *stack_top;
|
|
|
273
|
|
|
274 /* Bitmap of what variables are live on exit for a basic blocks. */
|
|
|
275 bitmap *liveout;
|
|
|
276 } *tree_live_info_p;
|
|
|
277
|
|
|
278
|
|
|
279 extern tree_live_info_p calculate_live_ranges (var_map);
|
|
|
280 extern void calculate_live_on_exit (tree_live_info_p);
|
|
|
281 extern void delete_tree_live_info (tree_live_info_p);
|
|
|
282
|
|
|
283 #define LIVEDUMP_ENTRY 0x01
|
|
|
284 #define LIVEDUMP_EXIT 0x02
|
|
|
285 #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
|
|
|
286 extern void dump_live_info (FILE *, tree_live_info_p, int);
|
|
|
287
|
|
|
288
|
|
|
289 /* Return TRUE if P is marked as a global in LIVE. */
|
|
|
290
|
|
|
291 static inline int
|
|
|
292 partition_is_global (tree_live_info_p live, int p)
|
|
|
293 {
|
|
|
294 gcc_assert (live->global);
|
|
|
295 return bitmap_bit_p (live->global, p);
|
|
|
296 }
|
|
|
297
|
|
|
298
|
|
|
299 /* Return the bitmap from LIVE representing the live on entry blocks for
|
|
|
300 partition P. */
|
|
|
301
|
|
|
302 static inline bitmap
|
|
|
303 live_on_entry (tree_live_info_p live, basic_block bb)
|
|
|
304 {
|
|
|
305 gcc_assert (live->livein);
|
|
|
306 gcc_assert (bb != ENTRY_BLOCK_PTR);
|
|
|
307 gcc_assert (bb != EXIT_BLOCK_PTR);
|
|
|
308
|
|
|
309 return live->livein[bb->index];
|
|
|
310 }
|
|
|
311
|
|
|
312
|
|
|
313 /* Return the bitmap from LIVE representing the live on exit partitions from
|
|
|
314 block BB. */
|
|
|
315
|
|
|
316 static inline bitmap
|
|
|
317 live_on_exit (tree_live_info_p live, basic_block bb)
|
|
|
318 {
|
|
|
319 gcc_assert (live->liveout);
|
|
|
320 gcc_assert (bb != ENTRY_BLOCK_PTR);
|
|
|
321 gcc_assert (bb != EXIT_BLOCK_PTR);
|
|
|
322
|
|
|
323 return live->liveout[bb->index];
|
|
|
324 }
|
|
|
325
|
|
|
326
|
|
|
327 /* Return the partition map which the information in LIVE utilizes. */
|
|
|
328
|
|
|
329 static inline var_map
|
|
|
330 live_var_map (tree_live_info_p live)
|
|
|
331 {
|
|
|
332 return live->map;
|
|
|
333 }
|
|
|
334
|
|
|
335
|
|
|
336 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
|
|
|
337 the result into P1. Clear P2. */
|
|
|
338
|
|
|
339 static inline void
|
|
|
340 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
|
|
|
341 {
|
|
|
342 gcc_assert (live->livein[p1]);
|
|
|
343 gcc_assert (live->livein[p2]);
|
|
|
344 bitmap_ior_into (live->livein[p1], live->livein[p2]);
|
|
|
345 bitmap_zero (live->livein[p2]);
|
|
|
346 }
|
|
|
347
|
|
|
348
|
|
|
349 /* Mark partition P as live on entry to basic block BB in LIVE. */
|
|
|
350
|
|
|
351 static inline void
|
|
|
352 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
|
|
|
353 {
|
|
|
354 bitmap_set_bit (live->livein[bb->index], p);
|
|
|
355 bitmap_set_bit (live->global, p);
|
|
|
356 }
|
|
|
357
|
|
|
358
|
|
|
359 /* From tree-ssa-coalesce.c */
|
|
|
360 extern var_map coalesce_ssa_name (void);
|
|
|
361
|
|
|
362
|
|
|
363 /* From tree-ssa-ter.c */
|
|
|
364 extern gimple *find_replaceable_exprs (var_map);
|
|
|
365 extern void dump_replaceable_exprs (FILE *, gimple *);
|
|
|
366
|
|
|
367
|
|
|
368 #endif /* _TREE_SSA_LIVE_H */
|
