OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-ssa-live.h] - Blame information for rev 831

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.