]>
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); | |
571325db | 67 | extern tree make_ssa_temp (tree); |
1e128c5f GB |
68 | #ifdef ENABLE_CHECKING |
69 | extern void register_ssa_partition_check (tree ssa_var); | |
70 | #endif | |
6de9cd9a DN |
71 | |
72 | static inline int num_var_partitions (var_map); | |
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 | ||
85 | static inline int | |
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. | |
133 | NO_PARTITION is returned if its not in any partition. */ | |
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 | { | |
312 | bitmap_a_or_b (live->livein[p1], live->livein[p1], live->livein[p2]); | |
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 | { | |
341 | varray_type trees; | |
342 | varray_type first_partition; | |
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); | |
359 | extern tpa_p tpa_init (var_map); | |
360 | extern void tpa_delete (tpa_p); | |
361 | extern void tpa_dump (FILE *, tpa_p); | |
362 | extern void tpa_remove_partition (tpa_p, int, int); | |
363 | extern int tpa_compact (tpa_p); | |
364 | ||
365 | ||
366 | /* Return the number of distinct tree nodes in TPA. */ | |
367 | ||
368 | static inline int | |
369 | tpa_num_trees (tpa_p tpa) | |
370 | { | |
371 | return tpa->num_trees; | |
372 | } | |
373 | ||
374 | ||
375 | /* Return the tree node for index I in TPA. */ | |
376 | ||
377 | static inline tree | |
378 | tpa_tree (tpa_p tpa, int i) | |
379 | { | |
380 | return VARRAY_TREE (tpa->trees, i); | |
381 | } | |
382 | ||
383 | ||
384 | /* Return the first partition associated with tree list I in TPA. */ | |
385 | ||
386 | static inline int | |
387 | tpa_first_partition (tpa_p tpa, int i) | |
388 | { | |
389 | return VARRAY_INT (tpa->first_partition, i); | |
390 | } | |
391 | ||
392 | ||
393 | /* Return the next partition after partition I in TPA's list. */ | |
394 | ||
395 | static inline int | |
396 | tpa_next_partition (tpa_p tpa, int i) | |
397 | { | |
398 | return tpa->next_partition[i]; | |
399 | } | |
400 | ||
401 | ||
402 | /* Return the tree index from TPA whose list contains partition I. | |
403 | TPA_NONE is returned if I is not associated with any list. */ | |
404 | ||
405 | static inline int | |
406 | tpa_find_tree (tpa_p tpa, int i) | |
407 | { | |
408 | int index; | |
409 | ||
410 | index = tpa->partition_to_tree_map[i]; | |
411 | /* When compressed, any index higher than the number of tree elements is | |
412 | a compressed element, so return TPA_NONE. */ | |
413 | if (index != TPA_NONE && index >= tpa_num_trees (tpa)) | |
414 | { | |
1e128c5f | 415 | gcc_assert (tpa->uncompressed_num != -1); |
6de9cd9a DN |
416 | index = TPA_NONE; |
417 | } | |
418 | ||
419 | return index; | |
420 | } | |
421 | ||
422 | ||
423 | /* This function removes any compaction which was performed on TPA. */ | |
424 | ||
425 | static inline void | |
426 | tpa_decompact(tpa_p tpa) | |
427 | { | |
1e128c5f | 428 | gcc_assert (tpa->uncompressed_num != -1); |
6de9cd9a DN |
429 | tpa->num_trees = tpa->uncompressed_num; |
430 | } | |
431 | ||
432 | ||
433 | /* Once a var_map has been created and compressed, a complimentary root_var | |
434 | object can be built. This creates a list of all the root variables from | |
435 | which ssa version names are derived. Each root variable has a list of | |
436 | which partitions are versions of that root. | |
437 | ||
438 | This is implemented using the tree_partition_associator. | |
439 | ||
440 | The tree vector is used to represent the root variable. | |
441 | The list of partitions represent SSA versions of the root variable. */ | |
442 | ||
443 | typedef tpa_p root_var_p; | |
444 | ||
445 | static inline tree root_var (root_var_p, int); | |
446 | static inline int root_var_first_partition (root_var_p, int); | |
447 | static inline int root_var_next_partition (root_var_p, int); | |
448 | static inline int root_var_num (root_var_p); | |
449 | static inline void root_var_dump (FILE *, root_var_p); | |
450 | static inline void root_var_remove_partition (root_var_p, int, int); | |
451 | static inline void root_var_delete (root_var_p); | |
452 | static inline int root_var_find (root_var_p, int); | |
453 | static inline int root_var_compact (root_var_p); | |
454 | static inline void root_var_decompact (tpa_p); | |
455 | ||
456 | extern root_var_p root_var_init (var_map); | |
457 | ||
458 | /* Value returned when there are no more partitions associated with a root | |
459 | variable. */ | |
460 | #define ROOT_VAR_NONE TPA_NONE | |
461 | ||
462 | ||
463 | /* Return the number of distinct root variables in RV. */ | |
464 | ||
465 | static inline int | |
466 | root_var_num (root_var_p rv) | |
467 | { | |
468 | return tpa_num_trees (rv); | |
469 | } | |
470 | ||
471 | ||
472 | /* Return root variable I from RV. */ | |
473 | ||
474 | static inline tree | |
475 | root_var (root_var_p rv, int i) | |
476 | { | |
477 | return tpa_tree (rv, i); | |
478 | } | |
479 | ||
480 | ||
481 | /* Return the first partition in RV belonging to root variable list I. */ | |
482 | ||
483 | static inline int | |
484 | root_var_first_partition (root_var_p rv, int i) | |
485 | { | |
486 | return tpa_first_partition (rv, i); | |
487 | } | |
488 | ||
489 | ||
490 | /* Return the next partition after partition I in a root list from RV. */ | |
491 | ||
492 | static inline int | |
493 | root_var_next_partition (root_var_p rv, int i) | |
494 | { | |
495 | return tpa_next_partition (rv, i); | |
496 | } | |
497 | ||
498 | ||
499 | /* Send debug info for root_var list RV to file F. */ | |
500 | ||
501 | static inline void | |
502 | root_var_dump (FILE *f, root_var_p rv) | |
503 | { | |
504 | fprintf (f, "\nRoot Var dump\n"); | |
505 | tpa_dump (f, rv); | |
506 | fprintf (f, "\n"); | |
507 | } | |
508 | ||
509 | ||
510 | /* Destroy root_var object RV. */ | |
511 | ||
512 | static inline void | |
513 | root_var_delete (root_var_p rv) | |
514 | { | |
515 | tpa_delete (rv); | |
516 | } | |
517 | ||
518 | ||
519 | /* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV. */ | |
520 | ||
521 | static inline void | |
522 | root_var_remove_partition (root_var_p rv, int root_index, int partition_index) | |
523 | { | |
524 | tpa_remove_partition (rv, root_index, partition_index); | |
525 | } | |
526 | ||
527 | ||
528 | /* Return the root_var list index for partition I in RV. */ | |
529 | ||
530 | static inline int | |
531 | root_var_find (root_var_p rv, int i) | |
532 | { | |
533 | return tpa_find_tree (rv, i); | |
534 | } | |
535 | ||
536 | ||
537 | /* Hide single element lists in RV. */ | |
538 | ||
539 | static inline int | |
540 | root_var_compact (root_var_p rv) | |
541 | { | |
542 | return tpa_compact (rv); | |
543 | } | |
544 | ||
545 | ||
546 | /* Expose the single element lists in RV. */ | |
547 | ||
548 | static inline void | |
549 | root_var_decompact (root_var_p rv) | |
550 | { | |
551 | tpa_decompact (rv); | |
552 | } | |
553 | ||
554 | ||
555 | /* A TYPE_VAR object is similar to a root_var object, except this associates | |
556 | partitions with their type rather than their root variable. This is used to | |
557 | coalesce memory locations based on type. */ | |
558 | ||
559 | typedef tpa_p type_var_p; | |
560 | ||
561 | static inline tree type_var (type_var_p, int); | |
562 | static inline int type_var_first_partition (type_var_p, int); | |
563 | static inline int type_var_next_partition (type_var_p, int); | |
564 | static inline int type_var_num (type_var_p); | |
565 | static inline void type_var_dump (FILE *, type_var_p); | |
566 | static inline void type_var_remove_partition (type_var_p, int, int); | |
567 | static inline void type_var_delete (type_var_p); | |
568 | static inline int type_var_find (type_var_p, int); | |
569 | static inline int type_var_compact (type_var_p); | |
570 | static inline void type_var_decompact (type_var_p); | |
571 | ||
572 | extern type_var_p type_var_init (var_map); | |
573 | ||
574 | /* Value returned when there is no partitions associated with a list. */ | |
575 | #define TYPE_VAR_NONE TPA_NONE | |
576 | ||
577 | ||
578 | /* Return the number of distinct type lists in TV. */ | |
579 | ||
580 | static inline int | |
581 | type_var_num (type_var_p tv) | |
582 | { | |
583 | return tpa_num_trees (tv); | |
584 | } | |
585 | ||
586 | ||
587 | /* Return the type of list I in TV. */ | |
588 | ||
589 | static inline tree | |
590 | type_var (type_var_p tv, int i) | |
591 | { | |
592 | return tpa_tree (tv, i); | |
593 | } | |
594 | ||
595 | ||
596 | /* Return the first partition belonging to type list I in TV. */ | |
597 | ||
598 | static inline int | |
599 | type_var_first_partition (type_var_p tv, int i) | |
600 | { | |
601 | return tpa_first_partition (tv, i); | |
602 | } | |
603 | ||
604 | ||
605 | /* Return the next partition after partition I in a type list within TV. */ | |
606 | ||
607 | static inline int | |
608 | type_var_next_partition (type_var_p tv, int i) | |
609 | { | |
610 | return tpa_next_partition (tv, i); | |
611 | } | |
612 | ||
613 | ||
614 | /* Send debug info for type_var object TV to file F. */ | |
615 | ||
616 | static inline void | |
617 | type_var_dump (FILE *f, type_var_p tv) | |
618 | { | |
619 | fprintf (f, "\nType Var dump\n"); | |
620 | tpa_dump (f, tv); | |
621 | fprintf (f, "\n"); | |
622 | } | |
623 | ||
624 | ||
625 | /* Delete type_var object TV. */ | |
626 | ||
627 | static inline void | |
628 | type_var_delete (type_var_p tv) | |
629 | { | |
630 | tpa_delete (tv); | |
631 | } | |
632 | ||
633 | ||
634 | /* Remove partition PARTITION_INDEX from type list TYPE_INDEX in TV. */ | |
635 | ||
636 | static inline void | |
637 | type_var_remove_partition (type_var_p tv, int type_index, int partition_index) | |
638 | { | |
639 | tpa_remove_partition (tv, type_index, partition_index); | |
640 | } | |
641 | ||
642 | ||
643 | /* Return the type index in TV for the list partition I is in. */ | |
644 | ||
645 | static inline int | |
646 | type_var_find (type_var_p tv, int i) | |
647 | { | |
648 | return tpa_find_tree (tv, i); | |
649 | } | |
650 | ||
651 | ||
652 | /* Hide single element lists in TV. */ | |
653 | ||
654 | static inline int | |
655 | type_var_compact (type_var_p tv) | |
656 | { | |
657 | return tpa_compact (tv); | |
658 | } | |
659 | ||
660 | ||
661 | /* Expose single element lists in TV. */ | |
662 | ||
663 | static inline void | |
664 | type_var_decompact (type_var_p tv) | |
665 | { | |
666 | tpa_decompact (tv); | |
667 | } | |
668 | ||
669 | /* This set of routines implements a coalesce_list. This is an object which | |
670 | is used to track pairs of partitions which are desirable to coalesce | |
671 | together at some point. Costs are associated with each pair, and when | |
672 | all desired information has been collected, the object can be used to | |
673 | order the pairs for processing. */ | |
674 | ||
675 | /* This structure defines a pair for coalescing. */ | |
676 | ||
677 | typedef struct partition_pair_d | |
678 | { | |
679 | int first_partition; | |
680 | int second_partition; | |
681 | int cost; | |
682 | struct partition_pair_d *next; | |
683 | } *partition_pair_p; | |
684 | ||
685 | /* This structure maintains the list of coalesce pairs. | |
686 | When add_mode is true, list is a triangular shaped list of coalesce pairs. | |
687 | The smaller partition number is used to index the list, and the larger is | |
688 | index is located in a partition_pair_p object. These lists are sorted from | |
689 | smallest to largest by 'second_partition'. New coalesce pairs are allowed | |
690 | to be added in this mode. | |
691 | When add_mode is false, the lists have all been merged into list[0]. The | |
692 | rest of the lists are not used. list[0] is ordered from most desirable | |
693 | coalesce to least desirable. pop_best_coalesce() retrieves the pairs | |
694 | one at a time. */ | |
695 | ||
696 | typedef struct coalesce_list_d | |
697 | { | |
698 | var_map map; | |
699 | partition_pair_p *list; | |
700 | bool add_mode; | |
701 | } *coalesce_list_p; | |
702 | ||
703 | extern coalesce_list_p create_coalesce_list (var_map); | |
704 | extern void add_coalesce (coalesce_list_p, int, int, int); | |
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 | |
710 | extern int pop_best_coalesce (coalesce_list_p, int *, int *); | |
711 | ||
712 | extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p, | |
713 | coalesce_list_p); | |
714 | extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, | |
715 | coalesce_list_p cl, FILE *); | |
716 | ||
717 | ||
718 | #endif /* _TREE_SSA_LIVE_H */ |