OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-live.h
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
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 extern tree make_ssa_temp (tree);
68 #ifdef ENABLE_CHECKING
69 extern void register_ssa_partition_check (tree ssa_var);
70 #endif
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
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);
98   gcc_assert (map->ref_count);
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
184   register_ssa_partition_check (ssa_var);
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 {
267   gcc_assert (live->global);
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 {
278   gcc_assert (live->livein);
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 {
289   gcc_assert (live->liveout);
290   gcc_assert (bb != ENTRY_BLOCK_PTR);
291   gcc_assert (bb != EXIT_BLOCK_PTR);
292
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
307    the result into P1.  Clear P2.  */
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     {
415       gcc_assert (tpa->uncompressed_num != -1);
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 {
428   gcc_assert (tpa->uncompressed_num != -1);
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  */