1 |
12 |
jlechner |
/* Routines for liveness in SSA trees.
|
2 |
|
|
Copyright (C) 2003, 2004, 2005 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 2, 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 COPYING. If not, write to
|
19 |
|
|
the Free Software Foundation, 51 Franklin Street, Fifth Floor,
|
20 |
|
|
Boston, MA 02110-1301, USA. */
|
21 |
|
|
|
22 |
|
|
|
23 |
|
|
#ifndef _TREE_SSA_LIVE_H
|
24 |
|
|
#define _TREE_SSA_LIVE_H 1
|
25 |
|
|
|
26 |
|
|
#include "partition.h"
|
27 |
|
|
|
28 |
|
|
/* Used to create the variable mapping when we go out of SSA form. */
|
29 |
|
|
typedef struct _var_map
|
30 |
|
|
{
|
31 |
|
|
/* The partition of all variables. */
|
32 |
|
|
partition var_partition;
|
33 |
|
|
|
34 |
|
|
/* Vector for compacting partitions. */
|
35 |
|
|
int *partition_to_compact;
|
36 |
|
|
int *compact_to_partition;
|
37 |
|
|
|
38 |
|
|
/* Mapping of partition numbers to vars. */
|
39 |
|
|
tree *partition_to_var;
|
40 |
|
|
|
41 |
|
|
/* Current number of partitions. */
|
42 |
|
|
unsigned int num_partitions;
|
43 |
|
|
|
44 |
|
|
/* Original partition size. */
|
45 |
|
|
unsigned int partition_size;
|
46 |
|
|
|
47 |
|
|
/* Reference count, if required. */
|
48 |
|
|
int *ref_count;
|
49 |
|
|
} *var_map;
|
50 |
|
|
|
51 |
|
|
#define VAR_ANN_PARTITION(ann) (ann->partition)
|
52 |
|
|
#define VAR_ANN_ROOT_INDEX(ann) (ann->root_index)
|
53 |
|
|
|
54 |
|
|
#define NO_PARTITION -1
|
55 |
|
|
|
56 |
|
|
/* Flags to pass to compact_var_map */
|
57 |
|
|
|
58 |
|
|
#define VARMAP_NORMAL 0
|
59 |
|
|
#define VARMAP_NO_SINGLE_DEFS 1
|
60 |
|
|
|
61 |
|
|
extern var_map init_var_map (int);
|
62 |
|
|
extern void delete_var_map (var_map);
|
63 |
|
|
extern void dump_var_map (FILE *, var_map);
|
64 |
|
|
extern int var_union (var_map, tree, tree);
|
65 |
|
|
extern void change_partition_var (var_map, tree, int);
|
66 |
|
|
extern void compact_var_map (var_map, int);
|
67 |
|
|
#ifdef ENABLE_CHECKING
|
68 |
|
|
extern void register_ssa_partition_check (tree ssa_var);
|
69 |
|
|
#endif
|
70 |
|
|
|
71 |
|
|
static inline unsigned num_var_partitions (var_map);
|
72 |
|
|
static inline tree var_to_partition_to_var (var_map, tree);
|
73 |
|
|
static inline tree partition_to_var (var_map, int);
|
74 |
|
|
static inline int var_to_partition (var_map, tree);
|
75 |
|
|
static inline tree version_to_var (var_map, int);
|
76 |
|
|
static inline int version_ref_count (var_map, tree);
|
77 |
|
|
static inline void register_ssa_partition (var_map, tree, bool);
|
78 |
|
|
|
79 |
|
|
#define SSA_VAR_MAP_REF_COUNT 0x01
|
80 |
|
|
extern var_map create_ssa_var_map (int);
|
81 |
|
|
|
82 |
|
|
/* Number of partitions in MAP. */
|
83 |
|
|
|
84 |
|
|
static inline unsigned
|
85 |
|
|
num_var_partitions (var_map map)
|
86 |
|
|
{
|
87 |
|
|
return map->num_partitions;
|
88 |
|
|
}
|
89 |
|
|
|
90 |
|
|
|
91 |
|
|
/* Return the reference count for SSA_VAR's partition in MAP. */
|
92 |
|
|
|
93 |
|
|
static inline int
|
94 |
|
|
version_ref_count (var_map map, tree ssa_var)
|
95 |
|
|
{
|
96 |
|
|
int version = SSA_NAME_VERSION (ssa_var);
|
97 |
|
|
gcc_assert (map->ref_count);
|
98 |
|
|
return map->ref_count[version];
|
99 |
|
|
}
|
100 |
|
|
|
101 |
|
|
|
102 |
|
|
/* Given partition index I from MAP, return the variable which represents that
|
103 |
|
|
partition. */
|
104 |
|
|
|
105 |
|
|
static inline tree
|
106 |
|
|
partition_to_var (var_map map, int i)
|
107 |
|
|
{
|
108 |
|
|
if (map->compact_to_partition)
|
109 |
|
|
i = map->compact_to_partition[i];
|
110 |
|
|
i = partition_find (map->var_partition, i);
|
111 |
|
|
return map->partition_to_var[i];
|
112 |
|
|
}
|
113 |
|
|
|
114 |
|
|
|
115 |
|
|
/* Given ssa_name VERSION, if it has a partition in MAP, return the var it
|
116 |
|
|
is associated with. Otherwise return NULL. */
|
117 |
|
|
|
118 |
|
|
static inline tree version_to_var (var_map map, int version)
|
119 |
|
|
{
|
120 |
|
|
int part;
|
121 |
|
|
part = partition_find (map->var_partition, version);
|
122 |
|
|
if (map->partition_to_compact)
|
123 |
|
|
part = map->partition_to_compact[part];
|
124 |
|
|
if (part == NO_PARTITION)
|
125 |
|
|
return NULL_TREE;
|
126 |
|
|
|
127 |
|
|
return partition_to_var (map, part);
|
128 |
|
|
}
|
129 |
|
|
|
130 |
|
|
|
131 |
|
|
/* Given VAR, return the partition number in MAP which contains it.
|
132 |
|
|
NO_PARTITION is returned if it's not in any partition. */
|
133 |
|
|
|
134 |
|
|
static inline int
|
135 |
|
|
var_to_partition (var_map map, tree var)
|
136 |
|
|
{
|
137 |
|
|
var_ann_t ann;
|
138 |
|
|
int part;
|
139 |
|
|
|
140 |
|
|
if (TREE_CODE (var) == SSA_NAME)
|
141 |
|
|
{
|
142 |
|
|
part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
|
143 |
|
|
if (map->partition_to_compact)
|
144 |
|
|
part = map->partition_to_compact[part];
|
145 |
|
|
}
|
146 |
|
|
else
|
147 |
|
|
{
|
148 |
|
|
ann = var_ann (var);
|
149 |
|
|
if (ann->out_of_ssa_tag)
|
150 |
|
|
part = VAR_ANN_PARTITION (ann);
|
151 |
|
|
else
|
152 |
|
|
part = NO_PARTITION;
|
153 |
|
|
}
|
154 |
|
|
return part;
|
155 |
|
|
}
|
156 |
|
|
|
157 |
|
|
|
158 |
|
|
/* Given VAR, return the variable which represents the entire partition
|
159 |
|
|
it is a member of in MAP. NULL is returned if it is not in a partition. */
|
160 |
|
|
|
161 |
|
|
static inline tree
|
162 |
|
|
var_to_partition_to_var (var_map map, tree var)
|
163 |
|
|
{
|
164 |
|
|
int part;
|
165 |
|
|
|
166 |
|
|
part = var_to_partition (map, var);
|
167 |
|
|
if (part == NO_PARTITION)
|
168 |
|
|
return NULL_TREE;
|
169 |
|
|
return partition_to_var (map, part);
|
170 |
|
|
}
|
171 |
|
|
|
172 |
|
|
|
173 |
|
|
/* This routine registers a partition for SSA_VAR with MAP. IS_USE is used
|
174 |
|
|
to count references. Any unregistered partitions may be compacted out
|
175 |
|
|
later. */
|
176 |
|
|
|
177 |
|
|
static inline void
|
178 |
|
|
register_ssa_partition (var_map map, tree ssa_var, bool is_use)
|
179 |
|
|
{
|
180 |
|
|
int version;
|
181 |
|
|
|
182 |
|
|
#if defined ENABLE_CHECKING
|
183 |
|
|
register_ssa_partition_check (ssa_var);
|
184 |
|
|
#endif
|
185 |
|
|
|
186 |
|
|
version = SSA_NAME_VERSION (ssa_var);
|
187 |
|
|
if (is_use && map->ref_count)
|
188 |
|
|
map->ref_count[version]++;
|
189 |
|
|
|
190 |
|
|
if (map->partition_to_var[version] == NULL_TREE)
|
191 |
|
|
map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var;
|
192 |
|
|
}
|
193 |
|
|
|
194 |
|
|
|
195 |
|
|
/* ---------------- live on entry/exit info ------------------------------
|
196 |
|
|
|
197 |
|
|
This structure is used to represent live range information on SSA based
|
198 |
|
|
trees. A partition map must be provided, and based on the active partitions,
|
199 |
|
|
live-on-entry information and live-on-exit information can be calculated.
|
200 |
|
|
As well, partitions are marked as to whether they are global (live
|
201 |
|
|
outside the basic block they are defined in).
|
202 |
|
|
|
203 |
|
|
The live-on-entry information is per variable. It provide a bitmap for
|
204 |
|
|
each variable which has a bit set for each basic block that the variable
|
205 |
|
|
is live on entry to that block.
|
206 |
|
|
|
207 |
|
|
The live-on-exit information is per block. It provides a bitmap for each
|
208 |
|
|
block indicating which partitions are live on exit from the block.
|
209 |
|
|
|
210 |
|
|
For the purposes of this implementation, we treat the elements of a PHI
|
211 |
|
|
as follows:
|
212 |
|
|
|
213 |
|
|
Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
|
214 |
|
|
originate. They are *NOT* considered live on entry to the block
|
215 |
|
|
containing the PHI node.
|
216 |
|
|
|
217 |
|
|
The Def of a PHI node is *not* considered live on entry to the block.
|
218 |
|
|
It is considered to be "define early" in the block. Picture it as each
|
219 |
|
|
block having a stmt (or block-preheader) before the first real stmt in
|
220 |
|
|
the block which defines all the variables that are defined by PHIs.
|
221 |
|
|
|
222 |
|
|
----------------------------------------------------------------------- */
|
223 |
|
|
|
224 |
|
|
|
225 |
|
|
typedef struct tree_live_info_d
|
226 |
|
|
{
|
227 |
|
|
/* Var map this relates to. */
|
228 |
|
|
var_map map;
|
229 |
|
|
|
230 |
|
|
/* Bitmap indicating which partitions are global. */
|
231 |
|
|
bitmap global;
|
232 |
|
|
|
233 |
|
|
/* Bitmap of live on entry blocks for partition elements. */
|
234 |
|
|
bitmap *livein;
|
235 |
|
|
|
236 |
|
|
/* Number of basic blocks when live on exit calculated. */
|
237 |
|
|
int num_blocks;
|
238 |
|
|
|
239 |
|
|
/* Bitmap of what variables are live on exit for a basic blocks. */
|
240 |
|
|
bitmap *liveout;
|
241 |
|
|
} *tree_live_info_p;
|
242 |
|
|
|
243 |
|
|
|
244 |
|
|
extern tree_live_info_p calculate_live_on_entry (var_map);
|
245 |
|
|
extern void calculate_live_on_exit (tree_live_info_p);
|
246 |
|
|
extern void delete_tree_live_info (tree_live_info_p);
|
247 |
|
|
|
248 |
|
|
#define LIVEDUMP_ENTRY 0x01
|
249 |
|
|
#define LIVEDUMP_EXIT 0x02
|
250 |
|
|
#define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
|
251 |
|
|
extern void dump_live_info (FILE *, tree_live_info_p, int);
|
252 |
|
|
|
253 |
|
|
static inline int partition_is_global (tree_live_info_p, int);
|
254 |
|
|
static inline bitmap live_entry_blocks (tree_live_info_p, int);
|
255 |
|
|
static inline bitmap live_on_exit (tree_live_info_p, basic_block);
|
256 |
|
|
static inline var_map live_var_map (tree_live_info_p);
|
257 |
|
|
static inline void live_merge_and_clear (tree_live_info_p, int, int);
|
258 |
|
|
static inline void make_live_on_entry (tree_live_info_p, basic_block, int);
|
259 |
|
|
|
260 |
|
|
|
261 |
|
|
/* Return TRUE if P is marked as a global in LIVE. */
|
262 |
|
|
|
263 |
|
|
static inline int
|
264 |
|
|
partition_is_global (tree_live_info_p live, int p)
|
265 |
|
|
{
|
266 |
|
|
gcc_assert (live->global);
|
267 |
|
|
return bitmap_bit_p (live->global, p);
|
268 |
|
|
}
|
269 |
|
|
|
270 |
|
|
|
271 |
|
|
/* Return the bitmap from LIVE representing the live on entry blocks for
|
272 |
|
|
partition P. */
|
273 |
|
|
|
274 |
|
|
static inline bitmap
|
275 |
|
|
live_entry_blocks (tree_live_info_p live, int p)
|
276 |
|
|
{
|
277 |
|
|
gcc_assert (live->livein);
|
278 |
|
|
return live->livein[p];
|
279 |
|
|
}
|
280 |
|
|
|
281 |
|
|
|
282 |
|
|
/* Return the bitmap from LIVE representing the live on exit partitions from
|
283 |
|
|
block BB. */
|
284 |
|
|
|
285 |
|
|
static inline bitmap
|
286 |
|
|
live_on_exit (tree_live_info_p live, basic_block bb)
|
287 |
|
|
{
|
288 |
|
|
gcc_assert (live->liveout);
|
289 |
|
|
gcc_assert (bb != ENTRY_BLOCK_PTR);
|
290 |
|
|
gcc_assert (bb != EXIT_BLOCK_PTR);
|
291 |
|
|
|
292 |
|
|
return live->liveout[bb->index];
|
293 |
|
|
}
|
294 |
|
|
|
295 |
|
|
|
296 |
|
|
/* Return the partition map which the information in LIVE utilizes. */
|
297 |
|
|
|
298 |
|
|
static inline var_map
|
299 |
|
|
live_var_map (tree_live_info_p live)
|
300 |
|
|
{
|
301 |
|
|
return live->map;
|
302 |
|
|
}
|
303 |
|
|
|
304 |
|
|
|
305 |
|
|
/* Merge the live on entry information in LIVE for partitions P1 and P2. Place
|
306 |
|
|
the result into P1. Clear P2. */
|
307 |
|
|
|
308 |
|
|
static inline void
|
309 |
|
|
live_merge_and_clear (tree_live_info_p live, int p1, int p2)
|
310 |
|
|
{
|
311 |
|
|
bitmap_ior_into (live->livein[p1], live->livein[p2]);
|
312 |
|
|
bitmap_zero (live->livein[p2]);
|
313 |
|
|
}
|
314 |
|
|
|
315 |
|
|
|
316 |
|
|
/* Mark partition P as live on entry to basic block BB in LIVE. */
|
317 |
|
|
|
318 |
|
|
static inline void
|
319 |
|
|
make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
|
320 |
|
|
{
|
321 |
|
|
bitmap_set_bit (live->livein[p], bb->index);
|
322 |
|
|
bitmap_set_bit (live->global, p);
|
323 |
|
|
}
|
324 |
|
|
|
325 |
|
|
|
326 |
|
|
/* A tree_partition_associator (TPA)object is a base structure which allows
|
327 |
|
|
partitions to be associated with a tree object.
|
328 |
|
|
|
329 |
|
|
A varray of tree elements represent each distinct tree item.
|
330 |
|
|
A parallel int array represents the first partition number associated with
|
331 |
|
|
the tree.
|
332 |
|
|
This partition number is then used as in index into the next_partition
|
333 |
|
|
array, which returns the index of the next partition which is associated
|
334 |
|
|
with the tree. TPA_NONE indicates the end of the list.
|
335 |
|
|
A varray paralleling the partition list 'partition_to_tree_map' is used
|
336 |
|
|
to indicate which tree index the partition is in. */
|
337 |
|
|
|
338 |
|
|
typedef struct tree_partition_associator_d
|
339 |
|
|
{
|
340 |
|
|
VEC(tree,heap) *trees;
|
341 |
|
|
varray_type first_partition;
|
342 |
|
|
int *next_partition;
|
343 |
|
|
int *partition_to_tree_map;
|
344 |
|
|
int num_trees;
|
345 |
|
|
int uncompressed_num;
|
346 |
|
|
var_map map;
|
347 |
|
|
} *tpa_p;
|
348 |
|
|
|
349 |
|
|
/* Value returned when there are no more partitions associated with a tree. */
|
350 |
|
|
#define TPA_NONE -1
|
351 |
|
|
|
352 |
|
|
static inline tree tpa_tree (tpa_p, int);
|
353 |
|
|
static inline int tpa_first_partition (tpa_p, int);
|
354 |
|
|
static inline int tpa_next_partition (tpa_p, int);
|
355 |
|
|
static inline int tpa_num_trees (tpa_p);
|
356 |
|
|
static inline int tpa_find_tree (tpa_p, int);
|
357 |
|
|
static inline void tpa_decompact (tpa_p);
|
358 |
|
|
extern void tpa_delete (tpa_p);
|
359 |
|
|
extern void tpa_dump (FILE *, tpa_p);
|
360 |
|
|
extern void tpa_remove_partition (tpa_p, int, int);
|
361 |
|
|
extern int tpa_compact (tpa_p);
|
362 |
|
|
|
363 |
|
|
|
364 |
|
|
/* Return the number of distinct tree nodes in TPA. */
|
365 |
|
|
|
366 |
|
|
static inline int
|
367 |
|
|
tpa_num_trees (tpa_p tpa)
|
368 |
|
|
{
|
369 |
|
|
return tpa->num_trees;
|
370 |
|
|
}
|
371 |
|
|
|
372 |
|
|
|
373 |
|
|
/* Return the tree node for index I in TPA. */
|
374 |
|
|
|
375 |
|
|
static inline tree
|
376 |
|
|
tpa_tree (tpa_p tpa, int i)
|
377 |
|
|
{
|
378 |
|
|
return VEC_index (tree, tpa->trees, i);
|
379 |
|
|
}
|
380 |
|
|
|
381 |
|
|
|
382 |
|
|
/* Return the first partition associated with tree list I in TPA. */
|
383 |
|
|
|
384 |
|
|
static inline int
|
385 |
|
|
tpa_first_partition (tpa_p tpa, int i)
|
386 |
|
|
{
|
387 |
|
|
return VARRAY_INT (tpa->first_partition, i);
|
388 |
|
|
}
|
389 |
|
|
|
390 |
|
|
|
391 |
|
|
/* Return the next partition after partition I in TPA's list. */
|
392 |
|
|
|
393 |
|
|
static inline int
|
394 |
|
|
tpa_next_partition (tpa_p tpa, int i)
|
395 |
|
|
{
|
396 |
|
|
return tpa->next_partition[i];
|
397 |
|
|
}
|
398 |
|
|
|
399 |
|
|
|
400 |
|
|
/* Return the tree index from TPA whose list contains partition I.
|
401 |
|
|
TPA_NONE is returned if I is not associated with any list. */
|
402 |
|
|
|
403 |
|
|
static inline int
|
404 |
|
|
tpa_find_tree (tpa_p tpa, int i)
|
405 |
|
|
{
|
406 |
|
|
int index;
|
407 |
|
|
|
408 |
|
|
index = tpa->partition_to_tree_map[i];
|
409 |
|
|
/* When compressed, any index higher than the number of tree elements is
|
410 |
|
|
a compressed element, so return TPA_NONE. */
|
411 |
|
|
if (index != TPA_NONE && index >= tpa_num_trees (tpa))
|
412 |
|
|
{
|
413 |
|
|
gcc_assert (tpa->uncompressed_num != -1);
|
414 |
|
|
index = TPA_NONE;
|
415 |
|
|
}
|
416 |
|
|
|
417 |
|
|
return index;
|
418 |
|
|
}
|
419 |
|
|
|
420 |
|
|
|
421 |
|
|
/* This function removes any compaction which was performed on TPA. */
|
422 |
|
|
|
423 |
|
|
static inline void
|
424 |
|
|
tpa_decompact(tpa_p tpa)
|
425 |
|
|
{
|
426 |
|
|
gcc_assert (tpa->uncompressed_num != -1);
|
427 |
|
|
tpa->num_trees = tpa->uncompressed_num;
|
428 |
|
|
}
|
429 |
|
|
|
430 |
|
|
|
431 |
|
|
/* Once a var_map has been created and compressed, a complementary root_var
|
432 |
|
|
object can be built. This creates a list of all the root variables from
|
433 |
|
|
which ssa version names are derived. Each root variable has a list of
|
434 |
|
|
which partitions are versions of that root.
|
435 |
|
|
|
436 |
|
|
This is implemented using the tree_partition_associator.
|
437 |
|
|
|
438 |
|
|
The tree vector is used to represent the root variable.
|
439 |
|
|
The list of partitions represent SSA versions of the root variable. */
|
440 |
|
|
|
441 |
|
|
typedef tpa_p root_var_p;
|
442 |
|
|
|
443 |
|
|
static inline tree root_var (root_var_p, int);
|
444 |
|
|
static inline int root_var_first_partition (root_var_p, int);
|
445 |
|
|
static inline int root_var_next_partition (root_var_p, int);
|
446 |
|
|
static inline int root_var_num (root_var_p);
|
447 |
|
|
static inline void root_var_dump (FILE *, root_var_p);
|
448 |
|
|
static inline void root_var_remove_partition (root_var_p, int, int);
|
449 |
|
|
static inline void root_var_delete (root_var_p);
|
450 |
|
|
static inline int root_var_find (root_var_p, int);
|
451 |
|
|
static inline int root_var_compact (root_var_p);
|
452 |
|
|
static inline void root_var_decompact (tpa_p);
|
453 |
|
|
|
454 |
|
|
extern root_var_p root_var_init (var_map);
|
455 |
|
|
|
456 |
|
|
/* Value returned when there are no more partitions associated with a root
|
457 |
|
|
variable. */
|
458 |
|
|
#define ROOT_VAR_NONE TPA_NONE
|
459 |
|
|
|
460 |
|
|
|
461 |
|
|
/* Return the number of distinct root variables in RV. */
|
462 |
|
|
|
463 |
|
|
static inline int
|
464 |
|
|
root_var_num (root_var_p rv)
|
465 |
|
|
{
|
466 |
|
|
return tpa_num_trees (rv);
|
467 |
|
|
}
|
468 |
|
|
|
469 |
|
|
|
470 |
|
|
/* Return root variable I from RV. */
|
471 |
|
|
|
472 |
|
|
static inline tree
|
473 |
|
|
root_var (root_var_p rv, int i)
|
474 |
|
|
{
|
475 |
|
|
return tpa_tree (rv, i);
|
476 |
|
|
}
|
477 |
|
|
|
478 |
|
|
|
479 |
|
|
/* Return the first partition in RV belonging to root variable list I. */
|
480 |
|
|
|
481 |
|
|
static inline int
|
482 |
|
|
root_var_first_partition (root_var_p rv, int i)
|
483 |
|
|
{
|
484 |
|
|
return tpa_first_partition (rv, i);
|
485 |
|
|
}
|
486 |
|
|
|
487 |
|
|
|
488 |
|
|
/* Return the next partition after partition I in a root list from RV. */
|
489 |
|
|
|
490 |
|
|
static inline int
|
491 |
|
|
root_var_next_partition (root_var_p rv, int i)
|
492 |
|
|
{
|
493 |
|
|
return tpa_next_partition (rv, i);
|
494 |
|
|
}
|
495 |
|
|
|
496 |
|
|
|
497 |
|
|
/* Send debug info for root_var list RV to file F. */
|
498 |
|
|
|
499 |
|
|
static inline void
|
500 |
|
|
root_var_dump (FILE *f, root_var_p rv)
|
501 |
|
|
{
|
502 |
|
|
fprintf (f, "\nRoot Var dump\n");
|
503 |
|
|
tpa_dump (f, rv);
|
504 |
|
|
fprintf (f, "\n");
|
505 |
|
|
}
|
506 |
|
|
|
507 |
|
|
|
508 |
|
|
/* Destroy root_var object RV. */
|
509 |
|
|
|
510 |
|
|
static inline void
|
511 |
|
|
root_var_delete (root_var_p rv)
|
512 |
|
|
{
|
513 |
|
|
tpa_delete (rv);
|
514 |
|
|
}
|
515 |
|
|
|
516 |
|
|
|
517 |
|
|
/* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV. */
|
518 |
|
|
|
519 |
|
|
static inline void
|
520 |
|
|
root_var_remove_partition (root_var_p rv, int root_index, int partition_index)
|
521 |
|
|
{
|
522 |
|
|
tpa_remove_partition (rv, root_index, partition_index);
|
523 |
|
|
}
|
524 |
|
|
|
525 |
|
|
|
526 |
|
|
/* Return the root_var list index for partition I in RV. */
|
527 |
|
|
|
528 |
|
|
static inline int
|
529 |
|
|
root_var_find (root_var_p rv, int i)
|
530 |
|
|
{
|
531 |
|
|
return tpa_find_tree (rv, i);
|
532 |
|
|
}
|
533 |
|
|
|
534 |
|
|
|
535 |
|
|
/* Hide single element lists in RV. */
|
536 |
|
|
|
537 |
|
|
static inline int
|
538 |
|
|
root_var_compact (root_var_p rv)
|
539 |
|
|
{
|
540 |
|
|
return tpa_compact (rv);
|
541 |
|
|
}
|
542 |
|
|
|
543 |
|
|
|
544 |
|
|
/* Expose the single element lists in RV. */
|
545 |
|
|
|
546 |
|
|
static inline void
|
547 |
|
|
root_var_decompact (root_var_p rv)
|
548 |
|
|
{
|
549 |
|
|
tpa_decompact (rv);
|
550 |
|
|
}
|
551 |
|
|
|
552 |
|
|
|
553 |
|
|
/* A TYPE_VAR object is similar to a root_var object, except this associates
|
554 |
|
|
partitions with their type rather than their root variable. This is used to
|
555 |
|
|
coalesce memory locations based on type. */
|
556 |
|
|
|
557 |
|
|
typedef tpa_p type_var_p;
|
558 |
|
|
|
559 |
|
|
static inline tree type_var (type_var_p, int);
|
560 |
|
|
static inline int type_var_first_partition (type_var_p, int);
|
561 |
|
|
static inline int type_var_next_partition (type_var_p, int);
|
562 |
|
|
static inline int type_var_num (type_var_p);
|
563 |
|
|
static inline void type_var_dump (FILE *, type_var_p);
|
564 |
|
|
static inline void type_var_remove_partition (type_var_p, int, int);
|
565 |
|
|
static inline void type_var_delete (type_var_p);
|
566 |
|
|
static inline int type_var_find (type_var_p, int);
|
567 |
|
|
static inline int type_var_compact (type_var_p);
|
568 |
|
|
static inline void type_var_decompact (type_var_p);
|
569 |
|
|
|
570 |
|
|
extern type_var_p type_var_init (var_map);
|
571 |
|
|
|
572 |
|
|
/* Value returned when there is no partitions associated with a list. */
|
573 |
|
|
#define TYPE_VAR_NONE TPA_NONE
|
574 |
|
|
|
575 |
|
|
|
576 |
|
|
/* Return the number of distinct type lists in TV. */
|
577 |
|
|
|
578 |
|
|
static inline int
|
579 |
|
|
type_var_num (type_var_p tv)
|
580 |
|
|
{
|
581 |
|
|
return tpa_num_trees (tv);
|
582 |
|
|
}
|
583 |
|
|
|
584 |
|
|
|
585 |
|
|
/* Return the type of list I in TV. */
|
586 |
|
|
|
587 |
|
|
static inline tree
|
588 |
|
|
type_var (type_var_p tv, int i)
|
589 |
|
|
{
|
590 |
|
|
return tpa_tree (tv, i);
|
591 |
|
|
}
|
592 |
|
|
|
593 |
|
|
|
594 |
|
|
/* Return the first partition belonging to type list I in TV. */
|
595 |
|
|
|
596 |
|
|
static inline int
|
597 |
|
|
type_var_first_partition (type_var_p tv, int i)
|
598 |
|
|
{
|
599 |
|
|
return tpa_first_partition (tv, i);
|
600 |
|
|
}
|
601 |
|
|
|
602 |
|
|
|
603 |
|
|
/* Return the next partition after partition I in a type list within TV. */
|
604 |
|
|
|
605 |
|
|
static inline int
|
606 |
|
|
type_var_next_partition (type_var_p tv, int i)
|
607 |
|
|
{
|
608 |
|
|
return tpa_next_partition (tv, i);
|
609 |
|
|
}
|
610 |
|
|
|
611 |
|
|
|
612 |
|
|
/* Send debug info for type_var object TV to file F. */
|
613 |
|
|
|
614 |
|
|
static inline void
|
615 |
|
|
type_var_dump (FILE *f, type_var_p tv)
|
616 |
|
|
{
|
617 |
|
|
fprintf (f, "\nType Var dump\n");
|
618 |
|
|
tpa_dump (f, tv);
|
619 |
|
|
fprintf (f, "\n");
|
620 |
|
|
}
|
621 |
|
|
|
622 |
|
|
|
623 |
|
|
/* Delete type_var object TV. */
|
624 |
|
|
|
625 |
|
|
static inline void
|
626 |
|
|
type_var_delete (type_var_p tv)
|
627 |
|
|
{
|
628 |
|
|
tpa_delete (tv);
|
629 |
|
|
}
|
630 |
|
|
|
631 |
|
|
|
632 |
|
|
/* Remove partition PARTITION_INDEX from type list TYPE_INDEX in TV. */
|
633 |
|
|
|
634 |
|
|
static inline void
|
635 |
|
|
type_var_remove_partition (type_var_p tv, int type_index, int partition_index)
|
636 |
|
|
{
|
637 |
|
|
tpa_remove_partition (tv, type_index, partition_index);
|
638 |
|
|
}
|
639 |
|
|
|
640 |
|
|
|
641 |
|
|
/* Return the type index in TV for the list partition I is in. */
|
642 |
|
|
|
643 |
|
|
static inline int
|
644 |
|
|
type_var_find (type_var_p tv, int i)
|
645 |
|
|
{
|
646 |
|
|
return tpa_find_tree (tv, i);
|
647 |
|
|
}
|
648 |
|
|
|
649 |
|
|
|
650 |
|
|
/* Hide single element lists in TV. */
|
651 |
|
|
|
652 |
|
|
static inline int
|
653 |
|
|
type_var_compact (type_var_p tv)
|
654 |
|
|
{
|
655 |
|
|
return tpa_compact (tv);
|
656 |
|
|
}
|
657 |
|
|
|
658 |
|
|
|
659 |
|
|
/* Expose single element lists in TV. */
|
660 |
|
|
|
661 |
|
|
static inline void
|
662 |
|
|
type_var_decompact (type_var_p tv)
|
663 |
|
|
{
|
664 |
|
|
tpa_decompact (tv);
|
665 |
|
|
}
|
666 |
|
|
|
667 |
|
|
/* This set of routines implements a coalesce_list. This is an object which
|
668 |
|
|
is used to track pairs of partitions which are desirable to coalesce
|
669 |
|
|
together at some point. Costs are associated with each pair, and when
|
670 |
|
|
all desired information has been collected, the object can be used to
|
671 |
|
|
order the pairs for processing. */
|
672 |
|
|
|
673 |
|
|
/* This structure defines a pair for coalescing. */
|
674 |
|
|
|
675 |
|
|
typedef struct partition_pair_d
|
676 |
|
|
{
|
677 |
|
|
int first_partition;
|
678 |
|
|
int second_partition;
|
679 |
|
|
int cost;
|
680 |
|
|
struct partition_pair_d *next;
|
681 |
|
|
} *partition_pair_p;
|
682 |
|
|
|
683 |
|
|
/* This structure maintains the list of coalesce pairs.
|
684 |
|
|
When add_mode is true, list is a triangular shaped list of coalesce pairs.
|
685 |
|
|
The smaller partition number is used to index the list, and the larger is
|
686 |
|
|
index is located in a partition_pair_p object. These lists are sorted from
|
687 |
|
|
smallest to largest by 'second_partition'. New coalesce pairs are allowed
|
688 |
|
|
to be added in this mode.
|
689 |
|
|
When add_mode is false, the lists have all been merged into list[0]. The
|
690 |
|
|
rest of the lists are not used. list[0] is ordered from most desirable
|
691 |
|
|
coalesce to least desirable. pop_best_coalesce() retrieves the pairs
|
692 |
|
|
one at a time. */
|
693 |
|
|
|
694 |
|
|
typedef struct coalesce_list_d
|
695 |
|
|
{
|
696 |
|
|
var_map map;
|
697 |
|
|
partition_pair_p *list;
|
698 |
|
|
bool add_mode;
|
699 |
|
|
} *coalesce_list_p;
|
700 |
|
|
|
701 |
|
|
extern coalesce_list_p create_coalesce_list (var_map);
|
702 |
|
|
extern void add_coalesce (coalesce_list_p, int, int, int);
|
703 |
|
|
extern int coalesce_cost (int, bool, bool);
|
704 |
|
|
extern void sort_coalesce_list (coalesce_list_p);
|
705 |
|
|
extern void dump_coalesce_list (FILE *, coalesce_list_p);
|
706 |
|
|
extern void delete_coalesce_list (coalesce_list_p);
|
707 |
|
|
|
708 |
|
|
#define NO_BEST_COALESCE -1
|
709 |
|
|
|
710 |
|
|
extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p,
|
711 |
|
|
coalesce_list_p);
|
712 |
|
|
extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
|
713 |
|
|
coalesce_list_p cl, FILE *);
|
714 |
|
|
|
715 |
|
|
|
716 |
|
|
#endif /* _TREE_SSA_LIVE_H */
|