Factor uses of build_pairwise_scheduling.
[official-gcc/Ramakrishna.git] / gcc / tree-ssa-live.h
blobf49f065d69d5d450079aef9e8c9603181cc4f3ae
1 /* 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>
5 This file is part of GCC.
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.
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.
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/>. */
22 #ifndef _TREE_SSA_LIVE_H
23 #define _TREE_SSA_LIVE_H 1
25 #include "partition.h"
26 #include "vecprim.h"
30 /* Used to create the variable mapping when we go out of SSA form.
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.
39 Non-ssa_names maintain their partition index in the variable annotation.
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)
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.
52 Note that members of a partition MUST all have the same base variable. */
54 typedef struct _var_map
56 /* The partition manager of all variables. */
57 partition var_partition;
59 /* Vector for managing partitions views. */
60 int *partition_to_view;
61 int *view_to_partition;
63 /* Current number of partitions in var_map based on the current view. */
64 unsigned int num_partitions;
66 /* Original full partition size. */
67 unsigned int partition_size;
69 /* Number of base variables in the base var list. */
70 int num_basevars;
72 /* Map of partitions numbers to base variable table indexes. */
73 int *partition_to_base_index;
75 /* Table of base variable's. */
76 VEC (tree, heap) *basevars;
77 } *var_map;
80 /* Index to the basevar table of a non ssa-name variable. */
81 #define VAR_ANN_BASE_INDEX(ann) (ann->base_index)
84 /* Value used to represent no partition number. */
85 #define NO_PARTITION -1
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
98 /* Return number of partitions in MAP. */
100 static inline unsigned
101 num_var_partitions (var_map map)
103 return map->num_partitions;
107 /* Given partition index I from MAP, return the variable which represents that
108 partition. */
110 static inline tree
111 partition_to_var (var_map map, int i)
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;
122 /* Given ssa_name VERSION, if it has a partition in MAP, return the var it
123 is associated with. Otherwise return NULL. */
125 static inline tree
126 version_to_var (var_map map, int version)
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;
135 return partition_to_var (map, part);
139 /* Given VAR, return the partition number in MAP which contains it.
140 NO_PARTITION is returned if it's not in any partition. */
142 static inline int
143 var_to_partition (var_map map, tree var)
145 int part;
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;
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. */
158 static inline tree
159 var_to_partition_to_var (var_map map, tree var)
161 int part;
163 part = var_to_partition (map, var);
164 if (part == NO_PARTITION)
165 return NULL_TREE;
166 return partition_to_var (map, part);
170 /* Return the index into the basevar table for PARTITION's base in MAP. */
172 static inline int
173 basevar_index (var_map map, int partition)
175 gcc_assert (partition >= 0
176 && partition <= (int) num_var_partitions (map));
177 return map->partition_to_base_index[partition];
181 /* Return the number of different base variables in MAP. */
183 static inline int
184 num_basevars (var_map map)
186 return map->num_basevars;
191 /* This routine registers a partition for SSA_VAR with MAP. Any unregistered
192 partitions may be filtered out by a view later. */
194 static inline void
195 register_ssa_partition (var_map map ATTRIBUTE_UNUSED,
196 tree ssa_var ATTRIBUTE_UNUSED)
198 #if defined ENABLE_CHECKING
199 register_ssa_partition_check (ssa_var);
200 #endif
204 /* ---------------- live on entry/exit info ------------------------------
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).
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.
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.
219 For the purposes of this implementation, we treat the elements of a PHI
220 as follows:
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.
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.
231 ----------------------------------------------------------------------- */
234 typedef struct tree_live_info_d
236 /* Var map this relates to. */
237 var_map map;
239 /* Bitmap indicating which partitions are global. */
240 bitmap global;
242 /* Bitmap of live on entry blocks for partition elements. */
243 bitmap *livein;
245 /* Number of basic blocks when live on exit calculated. */
246 int num_blocks;
248 /* Vector used when creating live ranges as a visited stack. */
249 int *work_stack;
251 /* Top of workstack. */
252 int *stack_top;
254 /* Bitmap of what variables are live on exit for a basic blocks. */
255 bitmap *liveout;
256 } *tree_live_info_p;
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);
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);
269 /* Return TRUE if P is marked as a global in LIVE. */
271 static inline int
272 partition_is_global (tree_live_info_p live, int p)
274 gcc_assert (live->global);
275 return bitmap_bit_p (live->global, p);
279 /* Return the bitmap from LIVE representing the live on entry blocks for
280 partition P. */
282 static inline bitmap
283 live_on_entry (tree_live_info_p live, basic_block bb)
285 gcc_assert (live->livein);
286 gcc_assert (bb != ENTRY_BLOCK_PTR);
287 gcc_assert (bb != EXIT_BLOCK_PTR);
289 return live->livein[bb->index];
293 /* Return the bitmap from LIVE representing the live on exit partitions from
294 block BB. */
296 static inline bitmap
297 live_on_exit (tree_live_info_p live, basic_block bb)
299 gcc_assert (live->liveout);
300 gcc_assert (bb != ENTRY_BLOCK_PTR);
301 gcc_assert (bb != EXIT_BLOCK_PTR);
303 return live->liveout[bb->index];
307 /* Return the partition map which the information in LIVE utilizes. */
309 static inline var_map
310 live_var_map (tree_live_info_p live)
312 return live->map;
316 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
317 the result into P1. Clear P2. */
319 static inline void
320 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
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]);
329 /* Mark partition P as live on entry to basic block BB in LIVE. */
331 static inline void
332 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
334 bitmap_set_bit (live->livein[bb->index], p);
335 bitmap_set_bit (live->global, p);
339 /* From tree-ssa-coalesce.c */
340 extern var_map coalesce_ssa_name (void);
343 /* From tree-ssa-ter.c */
344 extern bitmap find_replaceable_exprs (var_map);
345 extern void dump_replaceable_exprs (FILE *, bitmap);
348 #endif /* _TREE_SSA_LIVE_H */