]>
Commit | Line | Data |
---|---|---|
6de9cd9a DN |
1 | /* Routines for liveness in SSA trees. |
2 | Copyright (C) 2003, 2004 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, 59 Temple Place - Suite 330, | |
20 | Boston, MA 02111-1307, USA. */ | |
21 | ||
22 | ||
23 | #ifndef _TREE_SSA_LIVE_H | |
24 | #define _TREE_SSA_LIVE_H 1 | |
25 | ||
59587b18 JQ |
26 | #include "partition.h" |
27 | ||
6de9cd9a DN |
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 | ||
6de9cd9a DN |
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); | |
1e128c5f GB |
67 | #ifdef ENABLE_CHECKING |
68 | extern void register_ssa_partition_check (tree ssa_var); | |
69 | #endif | |
6de9cd9a | 70 | |
3cd8c58a | 71 | static inline unsigned num_var_partitions (var_map); |
6de9cd9a DN |
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 | ||
6de9cd9a DN |
82 | /* Number of partitions in MAP. */ |
83 | ||
3cd8c58a | 84 | static inline unsigned |
6de9cd9a DN |
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); | |
1e128c5f | 97 | gcc_assert (map->ref_count); |
6de9cd9a DN |
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. | |
89dbed81 | 132 | NO_PARTITION is returned if it's not in any partition. */ |
6de9cd9a DN |
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 | |
1e128c5f | 183 | register_ssa_partition_check (ssa_var); |
6de9cd9a DN |
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 | { | |
1e128c5f | 266 | gcc_assert (live->global); |
6de9cd9a DN |
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 | { | |
1e128c5f | 277 | gcc_assert (live->livein); |
6de9cd9a DN |
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 | { | |
1e128c5f GB |
288 | gcc_assert (live->liveout); |
289 | gcc_assert (bb != ENTRY_BLOCK_PTR); | |
290 | gcc_assert (bb != EXIT_BLOCK_PTR); | |
6de9cd9a | 291 | |
6de9cd9a DN |
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 | |
9cf737f8 | 306 | the result into P1. Clear P2. */ |
6de9cd9a DN |
307 | |
308 | static inline void | |
309 | live_merge_and_clear (tree_live_info_p live, int p1, int p2) | |
310 | { | |
67299d91 | 311 | bitmap_ior_into (live->livein[p1], live->livein[p2]); |
6de9cd9a DN |
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 | varray_type 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); | |
6de9cd9a DN |
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 VARRAY_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 | { | |
1e128c5f | 413 | gcc_assert (tpa->uncompressed_num != -1); |
6de9cd9a DN |
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 | { | |
1e128c5f | 426 | gcc_assert (tpa->uncompressed_num != -1); |
6de9cd9a DN |
427 | tpa->num_trees = tpa->uncompressed_num; |
428 | } | |
429 | ||
430 | ||
431 | /* Once a var_map has been created and compressed, a complimentary 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 void sort_coalesce_list (coalesce_list_p); | |
704 | extern void dump_coalesce_list (FILE *, coalesce_list_p); | |
705 | extern void delete_coalesce_list (coalesce_list_p); | |
706 | ||
707 | #define NO_BEST_COALESCE -1 | |
6de9cd9a DN |
708 | |
709 | extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p, | |
710 | coalesce_list_p); | |
711 | extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, | |
712 | coalesce_list_p cl, FILE *); | |
713 | ||
714 | ||
715 | #endif /* _TREE_SSA_LIVE_H */ |