summaryrefslogtreecommitdiff
path: root/gcc/tree-ssa-live.h
blob: 46135ee16ac59f65c03168ccd9438317d3cfbf42 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
/* Routines for liveness in SSA trees.
   Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
   Contributed by Andrew MacLeod  <amacleod@redhat.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */


#ifndef _TREE_SSA_LIVE_H
#define _TREE_SSA_LIVE_H 1

#include "partition.h"
#include "vecprim.h"



/* Used to create the variable mapping when we go out of SSA form.  

   Mapping from an ssa_name to a partition number is maintained, as well as
   partition number to back to ssa_name. A partition can also be represented
   by a non-ssa_name variable.  This allows ssa_names and their partition to 
   be coalesced with live on entry compiler variables, as well as eventually
   having real compiler variables assigned to each partition as part of the 
   final stage of going of of ssa.  

   Non-ssa_names maintain their partition index in the variable annotation.

   This data structure also supports "views", which work on a subset of all
   partitions.  This allows the coalescer to decide what partitions are 
   interesting to it, and only work with those partitions.  Whenever the view
   is changed, the partition numbers change, but none of the partition groupings
   change. (ie, it is truly a view since it doesn't change anything)

   The final component of the data structure is the basevar map.  This provides
   a list of all the different base variables which occur in a partition view,
   and a unique index for each one. Routines are provided to quickly produce
   the base variable of a partition.

   Note that members of a partition MUST all have the same base variable.  */

typedef struct _var_map
{
  /* The partition manager of all variables.  */
  partition var_partition;

  /* Vector for managing partitions views.  */
  int *partition_to_view;
  int *view_to_partition;

  /* Mapping of partition numbers to variables.  */
  tree *partition_to_var;

  /* Current number of partitions in var_map based on the current view.  */
  unsigned int num_partitions;

  /* Original full partition size.  */
  unsigned int partition_size;

  /* Number of base variables in the base var list.  */
  int num_basevars;

  /* Map of partitions numbers to base variable table indexes.  */
  int *partition_to_base_index;

  /* Table of base variable's.  */
  VEC (tree, heap) *basevars;
} *var_map;


/* Partition number of a  non ssa-name variable.  */
#define VAR_ANN_PARTITION(ann) (ann->partition)
/* Index iot the basevar table of a non ssa-name variable.  */
#define VAR_ANN_BASE_INDEX(ann) (ann->base_index)


/* Value used to represent no partition number.  */
#define NO_PARTITION		-1

extern var_map init_var_map (int);
extern void delete_var_map (var_map);
extern void dump_var_map (FILE *, var_map);
extern int var_union (var_map, tree, tree);
extern void change_partition_var (var_map, tree, int);
extern void partition_view_normal (var_map, bool);
extern void partition_view_bitmap (var_map, bitmap, bool);
#ifdef ENABLE_CHECKING
extern void register_ssa_partition_check (tree ssa_var);
#endif


/* Return number of partitions in MAP.  */

static inline unsigned
num_var_partitions (var_map map)
{
  return map->num_partitions;
}


/* Given partition index I from MAP, return the variable which represents that 
   partition.  */
 
static inline tree
partition_to_var (var_map map, int i)
{
  if (map->view_to_partition)
    i = map->view_to_partition[i];
  i = partition_find (map->var_partition, i);
  return map->partition_to_var[i];
}


/* Given ssa_name VERSION, if it has a partition in MAP,  return the var it 
   is associated with.  Otherwise return NULL.  */

static inline tree 
version_to_var (var_map map, int version)
{
  int part;
  part = partition_find (map->var_partition, version);
  if (map->partition_to_view)
    part = map->partition_to_view[part];
  if (part == NO_PARTITION)
    return NULL_TREE;
  
  return partition_to_var (map, part);
}
 

/* Given VAR, return the partition number in MAP which contains it.  
   NO_PARTITION is returned if it's not in any partition.  */

static inline int
var_to_partition (var_map map, tree var)
{
  var_ann_t ann;
  int part;

  if (TREE_CODE (var) == SSA_NAME)
    {
      part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
      if (map->partition_to_view)
	part = map->partition_to_view[part];
    }
  else
    {
      ann = var_ann (var);
      if (ann && ann->out_of_ssa_tag)
	part = VAR_ANN_PARTITION (ann);
      else
        part = NO_PARTITION;
    }
  return part;
}


/* Given VAR, return the variable which represents the entire partition
   it is a member of in MAP.  NULL is returned if it is not in a partition.  */

static inline tree
var_to_partition_to_var (var_map map, tree var)
{
  int part;

  part = var_to_partition (map, var);
  if (part == NO_PARTITION)
    return NULL_TREE;
  return partition_to_var (map, part);
}


/* Return the index into the basevar table for PARTITION's base in MAP.  */

static inline int
basevar_index (var_map map, int partition)
{
  gcc_assert (partition >= 0 
	      && partition <= (int) num_var_partitions (map));
  return map->partition_to_base_index[partition];
}


/* Return the number of different base variables in MAP.  */

static inline int
num_basevars (var_map map)
{
  return map->num_basevars;
}



/* This routine registers a partition for SSA_VAR with MAP.  Any unregistered 
   partitions may be filtered out by a view later.  */ 

static inline void
register_ssa_partition (var_map map, tree ssa_var)
{
  int version;

#if defined ENABLE_CHECKING
  register_ssa_partition_check (ssa_var);
#endif

  version = SSA_NAME_VERSION (ssa_var);
  if (map->partition_to_var[version] == NULL_TREE)
    map->partition_to_var[version] = ssa_var;
}


/*  ---------------- live on entry/exit info ------------------------------  

    This structure is used to represent live range information on SSA based
    trees. A partition map must be provided, and based on the active partitions,
    live-on-entry information and live-on-exit information can be calculated.
    As well, partitions are marked as to whether they are global (live 
    outside the basic block they are defined in).

    The live-on-entry information is per block.  It provide a bitmap for 
    each block which has a bit set for each partition that is live on entry to 
    that block.

    The live-on-exit information is per block.  It provides a bitmap for each
    block indicating which partitions are live on exit from the block.

    For the purposes of this implementation, we treat the elements of a PHI 
    as follows:

       Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
       originate. They are *NOT* considered live on entry to the block
       containing the PHI node.

       The Def of a PHI node is *not* considered live on entry to the block.
       It is considered to be "define early" in the block. Picture it as each
       block having a stmt (or block-preheader) before the first real stmt in 
       the block which defines all the variables that are defined by PHIs.
   
    -----------------------------------------------------------------------  */


typedef struct tree_live_info_d
{
  /* Var map this relates to.  */
  var_map map;

  /* Bitmap indicating which partitions are global.  */
  bitmap global;

  /* Bitmap of live on entry blocks for partition elements.  */
  bitmap *livein;

  /* Number of basic blocks when live on exit calculated.  */
  int num_blocks;

  /* Vector used when creating live ranges as a visited stack.  */
  int *work_stack;

  /* Top of workstack.  */
  int *stack_top;

  /* Bitmap of what variables are live on exit for a basic blocks.  */
  bitmap *liveout;
} *tree_live_info_p;


extern tree_live_info_p calculate_live_ranges (var_map);
extern void calculate_live_on_exit (tree_live_info_p);
extern void delete_tree_live_info (tree_live_info_p);

#define LIVEDUMP_ENTRY	0x01
#define LIVEDUMP_EXIT	0x02
#define LIVEDUMP_ALL	(LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
extern void dump_live_info (FILE *, tree_live_info_p, int);


/*  Return TRUE if P is marked as a global in LIVE.  */

static inline int
partition_is_global (tree_live_info_p live, int p)
{
  gcc_assert (live->global);
  return bitmap_bit_p (live->global, p);
}


/* Return the bitmap from LIVE representing the live on entry blocks for 
   partition P.  */

static inline bitmap
live_on_entry (tree_live_info_p live, basic_block bb)
{
  gcc_assert (live->livein);
  gcc_assert (bb != ENTRY_BLOCK_PTR);
  gcc_assert (bb != EXIT_BLOCK_PTR);

  return live->livein[bb->index];
}


/* Return the bitmap from LIVE representing the live on exit partitions from
   block BB.  */

static inline bitmap
live_on_exit (tree_live_info_p live, basic_block bb)
{
  gcc_assert (live->liveout);
  gcc_assert (bb != ENTRY_BLOCK_PTR);
  gcc_assert (bb != EXIT_BLOCK_PTR);

  return live->liveout[bb->index];
}


/* Return the partition map which the information in LIVE utilizes.  */

static inline var_map 
live_var_map (tree_live_info_p live)
{
  return live->map;
}


/* Merge the live on entry information in LIVE for partitions P1 and P2. Place
   the result into P1.  Clear P2.  */

static inline void 
live_merge_and_clear (tree_live_info_p live, int p1, int p2)
{
  gcc_assert (live->livein[p1]);
  gcc_assert (live->livein[p2]);
  bitmap_ior_into (live->livein[p1], live->livein[p2]);
  bitmap_zero (live->livein[p2]);
}


/* Mark partition P as live on entry to basic block BB in LIVE.  */

static inline void 
make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
{
  bitmap_set_bit (live->livein[bb->index], p);
  bitmap_set_bit (live->global, p);
}


/* From tree-ssa-coalesce.c  */
extern var_map coalesce_ssa_name (void);


/* From tree-ssa-ter.c  */
extern tree *find_replaceable_exprs (var_map);
extern void dump_replaceable_exprs (FILE *, tree *);


#endif /* _TREE_SSA_LIVE_H  */