* gcc.dg/store-motion-fgcse-sm.c (dg-final): Cleanup
[official-gcc.git] / gcc / tree-ssa-live.h
blob70024817c1c919a647369619508885d5a6eaeb07
1 /* Routines for liveness in SSA trees.
2 Copyright (C) 2003-2014 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"
27 /* Used to create the variable mapping when we go out of SSA form.
29 Mapping from an ssa_name to a partition number is maintained, as well as
30 partition number back to ssa_name.
32 This data structure also supports "views", which work on a subset of all
33 partitions. This allows the coalescer to decide what partitions are
34 interesting to it, and only work with those partitions. Whenever the view
35 is changed, the partition numbers change, but none of the partition groupings
36 change. (ie, it is truly a view since it doesn't change anything)
38 The final component of the data structure is the basevar map. This provides
39 a list of all the different base variables which occur in a partition view,
40 and a unique index for each one. Routines are provided to quickly produce
41 the base variable of a partition.
43 Note that members of a partition MUST all have the same base variable. */
45 typedef struct _var_map
47 /* The partition manager of all variables. */
48 partition var_partition;
50 /* Vector for managing partitions views. */
51 int *partition_to_view;
52 int *view_to_partition;
54 /* Current number of partitions in var_map based on the current view. */
55 unsigned int num_partitions;
57 /* Original full partition size. */
58 unsigned int partition_size;
60 /* Number of base variables in the base var list. */
61 int num_basevars;
63 /* Map of partitions numbers to base variable table indexes. */
64 int *partition_to_base_index;
65 } *var_map;
68 /* Value used to represent no partition number. */
69 #define NO_PARTITION -1
71 extern var_map init_var_map (int);
72 extern void delete_var_map (var_map);
73 extern int var_union (var_map, tree, tree);
74 extern void partition_view_normal (var_map, bool);
75 extern void partition_view_bitmap (var_map, bitmap, bool);
76 extern void dump_scope_blocks (FILE *, int);
77 extern void debug_scope_block (tree, int);
78 extern void debug_scope_blocks (int);
79 extern void remove_unused_locals (void);
80 extern void dump_var_map (FILE *, var_map);
81 extern void debug (_var_map &ref);
82 extern void debug (_var_map *ptr);
83 #ifdef ENABLE_CHECKING
84 extern void register_ssa_partition_check (tree ssa_var);
85 #endif
88 /* Return number of partitions in MAP. */
90 static inline unsigned
91 num_var_partitions (var_map map)
93 return map->num_partitions;
97 /* Given partition index I from MAP, return the variable which represents that
98 partition. */
100 static inline tree
101 partition_to_var (var_map map, int i)
103 tree name;
104 if (map->view_to_partition)
105 i = map->view_to_partition[i];
106 i = partition_find (map->var_partition, i);
107 name = ssa_name (i);
108 return name;
112 /* Given ssa_name VERSION, if it has a partition in MAP, return the var it
113 is associated with. Otherwise return NULL. */
115 static inline tree
116 version_to_var (var_map map, int version)
118 int part;
119 part = partition_find (map->var_partition, version);
120 if (map->partition_to_view)
121 part = map->partition_to_view[part];
122 if (part == NO_PARTITION)
123 return NULL_TREE;
125 return partition_to_var (map, part);
129 /* Given VAR, return the partition number in MAP which contains it.
130 NO_PARTITION is returned if it's not in any partition. */
132 static inline int
133 var_to_partition (var_map map, tree var)
135 int part;
137 part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
138 if (map->partition_to_view)
139 part = map->partition_to_view[part];
140 return part;
144 /* Given VAR, return the variable which represents the entire partition
145 it is a member of in MAP. NULL is returned if it is not in a partition. */
147 static inline tree
148 var_to_partition_to_var (var_map map, tree var)
150 int part;
152 part = var_to_partition (map, var);
153 if (part == NO_PARTITION)
154 return NULL_TREE;
155 return partition_to_var (map, part);
159 /* Return the index into the basevar table for PARTITION's base in MAP. */
161 static inline int
162 basevar_index (var_map map, int partition)
164 gcc_checking_assert (partition >= 0
165 && partition <= (int) num_var_partitions (map));
166 return map->partition_to_base_index[partition];
170 /* Return the number of different base variables in MAP. */
172 static inline int
173 num_basevars (var_map map)
175 return map->num_basevars;
180 /* This routine registers a partition for SSA_VAR with MAP. Any unregistered
181 partitions may be filtered out by a view later. */
183 static inline void
184 register_ssa_partition (var_map map ATTRIBUTE_UNUSED,
185 tree ssa_var ATTRIBUTE_UNUSED)
187 #if defined ENABLE_CHECKING
188 register_ssa_partition_check (ssa_var);
189 #endif
193 /* ---------------- live on entry/exit info ------------------------------
195 This structure is used to represent live range information on SSA based
196 trees. A partition map must be provided, and based on the active partitions,
197 live-on-entry information and live-on-exit information can be calculated.
198 As well, partitions are marked as to whether they are global (live
199 outside the basic block they are defined in).
201 The live-on-entry information is per block. It provide a bitmap for
202 each block which has a bit set for each partition that is live on entry to
203 that block.
205 The live-on-exit information is per block. It provides a bitmap for each
206 block indicating which partitions are live on exit from the block.
208 For the purposes of this implementation, we treat the elements of a PHI
209 as follows:
211 Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
212 originate. They are *NOT* considered live on entry to the block
213 containing the PHI node.
215 The Def of a PHI node is *not* considered live on entry to the block.
216 It is considered to be "define early" in the block. Picture it as each
217 block having a stmt (or block-preheader) before the first real stmt in
218 the block which defines all the variables that are defined by PHIs.
220 ----------------------------------------------------------------------- */
223 typedef struct tree_live_info_d
225 /* Var map this relates to. */
226 var_map map;
228 /* Bitmap indicating which partitions are global. */
229 bitmap global;
231 /* Bitmaps of live on entry blocks for partition elements. */
232 bitmap_head *livein;
234 /* Bitmaps of what variables are live on exit for a basic blocks. */
235 bitmap_head *liveout;
237 /* Number of basic blocks when live on exit calculated. */
238 int num_blocks;
240 /* Vector used when creating live ranges as a visited stack. */
241 int *work_stack;
243 /* Top of workstack. */
244 int *stack_top;
245 } *tree_live_info_p;
248 #define LIVEDUMP_ENTRY 0x01
249 #define LIVEDUMP_EXIT 0x02
250 #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
251 extern void delete_tree_live_info (tree_live_info_p);
252 extern void calculate_live_on_exit (tree_live_info_p);
253 extern tree_live_info_p calculate_live_ranges (var_map);
254 extern void debug (tree_live_info_d &ref);
255 extern void debug (tree_live_info_d *ptr);
256 extern void dump_live_info (FILE *, tree_live_info_p, int);
259 /* Return TRUE if P is marked as a global in LIVE. */
261 static inline int
262 partition_is_global (tree_live_info_p live, int p)
264 gcc_checking_assert (live->global);
265 return bitmap_bit_p (live->global, p);
269 /* Return the bitmap from LIVE representing the live on entry blocks for
270 partition P. */
272 static inline bitmap
273 live_on_entry (tree_live_info_p live, basic_block bb)
275 gcc_checking_assert (live->livein
276 && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
277 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
279 return &live->livein[bb->index];
283 /* Return the bitmap from LIVE representing the live on exit partitions from
284 block BB. */
286 static inline bitmap
287 live_on_exit (tree_live_info_p live, basic_block bb)
289 gcc_checking_assert (live->liveout
290 && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
291 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
293 return &live->liveout[bb->index];
297 /* Return the partition map which the information in LIVE utilizes. */
299 static inline var_map
300 live_var_map (tree_live_info_p live)
302 return live->map;
306 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
307 the result into P1. Clear P2. */
309 static inline void
310 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
312 gcc_checking_assert (&live->livein[p1] && &live->livein[p2]);
313 bitmap_ior_into (&live->livein[p1], &live->livein[p2]);
314 bitmap_clear (&live->livein[p2]);
318 /* Mark partition P as live on entry to basic block BB in LIVE. */
320 static inline void
321 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
323 bitmap_set_bit (&live->livein[bb->index], p);
324 bitmap_set_bit (live->global, p);
327 #endif /* _TREE_SSA_LIVE_H */