Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-live.h @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
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 */