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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [tree-ssa-live.h] - Blame information for rev 859

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

Line No. Rev Author Line
1 280 jeremybenn
/* Routines for liveness in SSA trees.
2
   Copyright (C) 2003, 2004, 2005, 2007, 2008 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
 
29
 
30
/* Used to create the variable mapping when we go out of SSA form.
31
 
32
   Mapping from an ssa_name to a partition number is maintained, as well as
33
   partition number to back to ssa_name. A partition can also be represented
34
   by a non-ssa_name variable.  This allows ssa_names and their partition to
35
   be coalesced with live on entry compiler variables, as well as eventually
36
   having real compiler variables assigned to each partition as part of the
37
   final stage of going of of ssa.
38
 
39
   Non-ssa_names maintain their partition index in the variable annotation.
40
 
41
   This data structure also supports "views", which work on a subset of all
42
   partitions.  This allows the coalescer to decide what partitions are
43
   interesting to it, and only work with those partitions.  Whenever the view
44
   is changed, the partition numbers change, but none of the partition groupings
45
   change. (ie, it is truly a view since it doesn't change anything)
46
 
47
   The final component of the data structure is the basevar map.  This provides
48
   a list of all the different base variables which occur in a partition view,
49
   and a unique index for each one. Routines are provided to quickly produce
50
   the base variable of a partition.
51
 
52
   Note that members of a partition MUST all have the same base variable.  */
53
 
54
typedef struct _var_map
55
{
56
  /* The partition manager of all variables.  */
57
  partition var_partition;
58
 
59
  /* Vector for managing partitions views.  */
60
  int *partition_to_view;
61
  int *view_to_partition;
62
 
63
  /* Current number of partitions in var_map based on the current view.  */
64
  unsigned int num_partitions;
65
 
66
  /* Original full partition size.  */
67
  unsigned int partition_size;
68
 
69
  /* Number of base variables in the base var list.  */
70
  int num_basevars;
71
 
72
  /* Map of partitions numbers to base variable table indexes.  */
73
  int *partition_to_base_index;
74
 
75
  /* Table of base variable's.  */
76
  VEC (tree, heap) *basevars;
77
} *var_map;
78
 
79
 
80
/* Index to the basevar table of a non ssa-name variable.  */
81
#define VAR_ANN_BASE_INDEX(ann) (ann->base_index)
82
 
83
 
84
/* Value used to represent no partition number.  */
85
#define NO_PARTITION            -1
86
 
87
extern var_map init_var_map (int);
88
extern void delete_var_map (var_map);
89
extern void dump_var_map (FILE *, var_map);
90
extern int var_union (var_map, tree, tree);
91
extern void partition_view_normal (var_map, bool);
92
extern void partition_view_bitmap (var_map, bitmap, bool);
93
#ifdef ENABLE_CHECKING
94
extern void register_ssa_partition_check (tree ssa_var);
95
#endif
96
 
97
 
98
/* Return number of partitions in MAP.  */
99
 
100
static inline unsigned
101
num_var_partitions (var_map map)
102
{
103
  return map->num_partitions;
104
}
105
 
106
 
107
/* Given partition index I from MAP, return the variable which represents that
108
   partition.  */
109
 
110
static inline tree
111
partition_to_var (var_map map, int i)
112
{
113
  tree name;
114
  if (map->view_to_partition)
115
    i = map->view_to_partition[i];
116
  i = partition_find (map->var_partition, i);
117
  name = ssa_name (i);
118
  return name;
119
}
120
 
121
 
122
/* Given ssa_name VERSION, if it has a partition in MAP,  return the var it
123
   is associated with.  Otherwise return NULL.  */
124
 
125
static inline tree
126
version_to_var (var_map map, int version)
127
{
128
  int part;
129
  part = partition_find (map->var_partition, version);
130
  if (map->partition_to_view)
131
    part = map->partition_to_view[part];
132
  if (part == NO_PARTITION)
133
    return NULL_TREE;
134
 
135
  return partition_to_var (map, part);
136
}
137
 
138
 
139
/* Given VAR, return the partition number in MAP which contains it.
140
   NO_PARTITION is returned if it's not in any partition.  */
141
 
142
static inline int
143
var_to_partition (var_map map, tree var)
144
{
145
  int part;
146
 
147
  gcc_assert (TREE_CODE (var) == SSA_NAME);
148
  part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
149
  if (map->partition_to_view)
150
    part = map->partition_to_view[part];
151
  return part;
152
}
153
 
154
 
155
/* Given VAR, return the variable which represents the entire partition
156
   it is a member of in MAP.  NULL is returned if it is not in a partition.  */
157
 
158
static inline tree
159
var_to_partition_to_var (var_map map, tree var)
160
{
161
  int part;
162
 
163
  part = var_to_partition (map, var);
164
  if (part == NO_PARTITION)
165
    return NULL_TREE;
166
  return partition_to_var (map, part);
167
}
168
 
169
 
170
/* Return the index into the basevar table for PARTITION's base in MAP.  */
171
 
172
static inline int
173
basevar_index (var_map map, int partition)
174
{
175
  gcc_assert (partition >= 0
176
              && partition <= (int) num_var_partitions (map));
177
  return map->partition_to_base_index[partition];
178
}
179
 
180
 
181
/* Return the number of different base variables in MAP.  */
182
 
183
static inline int
184
num_basevars (var_map map)
185
{
186
  return map->num_basevars;
187
}
188
 
189
 
190
 
191
/* This routine registers a partition for SSA_VAR with MAP.  Any unregistered
192
   partitions may be filtered out by a view later.  */
193
 
194
static inline void
195
register_ssa_partition (var_map map ATTRIBUTE_UNUSED,
196
                        tree ssa_var ATTRIBUTE_UNUSED)
197
{
198
#if defined ENABLE_CHECKING
199
  register_ssa_partition_check (ssa_var);
200
#endif
201
}
202
 
203
 
204
/*  ---------------- live on entry/exit info ------------------------------
205
 
206
    This structure is used to represent live range information on SSA based
207
    trees. A partition map must be provided, and based on the active partitions,
208
    live-on-entry information and live-on-exit information can be calculated.
209
    As well, partitions are marked as to whether they are global (live
210
    outside the basic block they are defined in).
211
 
212
    The live-on-entry information is per block.  It provide a bitmap for
213
    each block which has a bit set for each partition that is live on entry to
214
    that block.
215
 
216
    The live-on-exit information is per block.  It provides a bitmap for each
217
    block indicating which partitions are live on exit from the block.
218
 
219
    For the purposes of this implementation, we treat the elements of a PHI
220
    as follows:
221
 
222
       Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
223
       originate. They are *NOT* considered live on entry to the block
224
       containing the PHI node.
225
 
226
       The Def of a PHI node is *not* considered live on entry to the block.
227
       It is considered to be "define early" in the block. Picture it as each
228
       block having a stmt (or block-preheader) before the first real stmt in
229
       the block which defines all the variables that are defined by PHIs.
230
 
231
    -----------------------------------------------------------------------  */
232
 
233
 
234
typedef struct tree_live_info_d
235
{
236
  /* Var map this relates to.  */
237
  var_map map;
238
 
239
  /* Bitmap indicating which partitions are global.  */
240
  bitmap global;
241
 
242
  /* Bitmap of live on entry blocks for partition elements.  */
243
  bitmap *livein;
244
 
245
  /* Number of basic blocks when live on exit calculated.  */
246
  int num_blocks;
247
 
248
  /* Vector used when creating live ranges as a visited stack.  */
249
  int *work_stack;
250
 
251
  /* Top of workstack.  */
252
  int *stack_top;
253
 
254
  /* Bitmap of what variables are live on exit for a basic blocks.  */
255
  bitmap *liveout;
256
} *tree_live_info_p;
257
 
258
 
259
extern tree_live_info_p calculate_live_ranges (var_map);
260
extern void calculate_live_on_exit (tree_live_info_p);
261
extern void delete_tree_live_info (tree_live_info_p);
262
 
263
#define LIVEDUMP_ENTRY  0x01
264
#define LIVEDUMP_EXIT   0x02
265
#define LIVEDUMP_ALL    (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
266
extern void dump_live_info (FILE *, tree_live_info_p, int);
267
 
268
 
269
/*  Return TRUE if P is marked as a global in LIVE.  */
270
 
271
static inline int
272
partition_is_global (tree_live_info_p live, int p)
273
{
274
  gcc_assert (live->global);
275
  return bitmap_bit_p (live->global, p);
276
}
277
 
278
 
279
/* Return the bitmap from LIVE representing the live on entry blocks for
280
   partition P.  */
281
 
282
static inline bitmap
283
live_on_entry (tree_live_info_p live, basic_block bb)
284
{
285
  gcc_assert (live->livein);
286
  gcc_assert (bb != ENTRY_BLOCK_PTR);
287
  gcc_assert (bb != EXIT_BLOCK_PTR);
288
 
289
  return live->livein[bb->index];
290
}
291
 
292
 
293
/* Return the bitmap from LIVE representing the live on exit partitions from
294
   block BB.  */
295
 
296
static inline bitmap
297
live_on_exit (tree_live_info_p live, basic_block bb)
298
{
299
  gcc_assert (live->liveout);
300
  gcc_assert (bb != ENTRY_BLOCK_PTR);
301
  gcc_assert (bb != EXIT_BLOCK_PTR);
302
 
303
  return live->liveout[bb->index];
304
}
305
 
306
 
307
/* Return the partition map which the information in LIVE utilizes.  */
308
 
309
static inline var_map
310
live_var_map (tree_live_info_p live)
311
{
312
  return live->map;
313
}
314
 
315
 
316
/* Merge the live on entry information in LIVE for partitions P1 and P2. Place
317
   the result into P1.  Clear P2.  */
318
 
319
static inline void
320
live_merge_and_clear (tree_live_info_p live, int p1, int p2)
321
{
322
  gcc_assert (live->livein[p1]);
323
  gcc_assert (live->livein[p2]);
324
  bitmap_ior_into (live->livein[p1], live->livein[p2]);
325
  bitmap_zero (live->livein[p2]);
326
}
327
 
328
 
329
/* Mark partition P as live on entry to basic block BB in LIVE.  */
330
 
331
static inline void
332
make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
333
{
334
  bitmap_set_bit (live->livein[bb->index], p);
335
  bitmap_set_bit (live->global, p);
336
}
337
 
338
 
339
/* From tree-ssa-coalesce.c  */
340
extern var_map coalesce_ssa_name (void);
341
 
342
 
343
/* From tree-ssa-ter.c  */
344
extern bitmap find_replaceable_exprs (var_map);
345
extern void dump_replaceable_exprs (FILE *, bitmap);
346
 
347
 
348
#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.