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