]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Routines for liveness in SSA trees. |
5624e564 | 2 | Copyright (C) 2003-2015 Free Software Foundation, Inc. |
6de9cd9a DN |
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 | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
20 | |
21 | ||
22 | #ifndef _TREE_SSA_LIVE_H | |
23 | #define _TREE_SSA_LIVE_H 1 | |
24 | ||
59587b18 | 25 | #include "partition.h" |
7290d709 | 26 | |
b8698a0f | 27 | /* Used to create the variable mapping when we go out of SSA form. |
7290d709 AM |
28 | |
29 | Mapping from an ssa_name to a partition number is maintained, as well as | |
5f564b8f | 30 | partition number back to ssa_name. |
7290d709 AM |
31 | |
32 | This data structure also supports "views", which work on a subset of all | |
b8698a0f | 33 | partitions. This allows the coalescer to decide what partitions are |
7290d709 AM |
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 | |
2e226e66 | 36 | change. (ie, it is truly a view since it doesn't change anything) |
7290d709 AM |
37 | |
38 | The final component of the data structure is the basevar map. This provides | |
9f5ed61a | 39 | a list of all the different base variables which occur in a partition view, |
7290d709 AM |
40 | and a unique index for each one. Routines are provided to quickly produce |
41 | the base variable of a partition. | |
42 | ||
43 | Note that members of a partition MUST all have the same base variable. */ | |
44 | ||
6de9cd9a DN |
45 | typedef struct _var_map |
46 | { | |
7290d709 | 47 | /* The partition manager of all variables. */ |
6de9cd9a DN |
48 | partition var_partition; |
49 | ||
7290d709 AM |
50 | /* Vector for managing partitions views. */ |
51 | int *partition_to_view; | |
52 | int *view_to_partition; | |
6de9cd9a | 53 | |
7290d709 | 54 | /* Current number of partitions in var_map based on the current view. */ |
6de9cd9a DN |
55 | unsigned int num_partitions; |
56 | ||
7290d709 | 57 | /* Original full partition size. */ |
6de9cd9a | 58 | unsigned int partition_size; |
7290d709 AM |
59 | |
60 | /* Number of base variables in the base var list. */ | |
61 | int num_basevars; | |
62 | ||
63 | /* Map of partitions numbers to base variable table indexes. */ | |
64 | int *partition_to_base_index; | |
6de9cd9a DN |
65 | } *var_map; |
66 | ||
6de9cd9a | 67 | |
7290d709 AM |
68 | /* Value used to represent no partition number. */ |
69 | #define NO_PARTITION -1 | |
6de9cd9a | 70 | |
6de9cd9a DN |
71 | extern var_map init_var_map (int); |
72 | extern void delete_var_map (var_map); | |
6de9cd9a | 73 | extern int var_union (var_map, tree, tree); |
0f9f9784 AO |
74 | extern void partition_view_normal (var_map, bool); |
75 | extern void partition_view_bitmap (var_map, bitmap, bool); | |
c1bf2a39 AM |
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); | |
1e128c5f GB |
83 | #ifdef ENABLE_CHECKING |
84 | extern void register_ssa_partition_check (tree ssa_var); | |
85 | #endif | |
6de9cd9a | 86 | |
6de9cd9a | 87 | |
7290d709 | 88 | /* Return number of partitions in MAP. */ |
6de9cd9a | 89 | |
3cd8c58a | 90 | static inline unsigned |
6de9cd9a DN |
91 | num_var_partitions (var_map map) |
92 | { | |
93 | return map->num_partitions; | |
94 | } | |
95 | ||
96 | ||
b8698a0f | 97 | /* Given partition index I from MAP, return the variable which represents that |
6de9cd9a | 98 | partition. */ |
b8698a0f | 99 | |
6de9cd9a DN |
100 | static inline tree |
101 | partition_to_var (var_map map, int i) | |
102 | { | |
4e3825db | 103 | tree name; |
7290d709 AM |
104 | if (map->view_to_partition) |
105 | i = map->view_to_partition[i]; | |
6de9cd9a | 106 | i = partition_find (map->var_partition, i); |
4e3825db MM |
107 | name = ssa_name (i); |
108 | return name; | |
6de9cd9a DN |
109 | } |
110 | ||
111 | ||
b8698a0f | 112 | /* Given ssa_name VERSION, if it has a partition in MAP, return the var it |
6de9cd9a DN |
113 | is associated with. Otherwise return NULL. */ |
114 | ||
b8698a0f | 115 | static inline tree |
7290d709 | 116 | version_to_var (var_map map, int version) |
6de9cd9a DN |
117 | { |
118 | int part; | |
119 | part = partition_find (map->var_partition, version); | |
7290d709 AM |
120 | if (map->partition_to_view) |
121 | part = map->partition_to_view[part]; | |
6de9cd9a DN |
122 | if (part == NO_PARTITION) |
123 | return NULL_TREE; | |
b8698a0f | 124 | |
6de9cd9a DN |
125 | return partition_to_var (map, part); |
126 | } | |
6de9cd9a | 127 | |
b8698a0f L |
128 | |
129 | /* Given VAR, return the partition number in MAP which contains it. | |
89dbed81 | 130 | NO_PARTITION is returned if it's not in any partition. */ |
6de9cd9a DN |
131 | |
132 | static inline int | |
133 | var_to_partition (var_map map, tree var) | |
134 | { | |
6de9cd9a DN |
135 | int part; |
136 | ||
4e3825db MM |
137 | part = partition_find (map->var_partition, SSA_NAME_VERSION (var)); |
138 | if (map->partition_to_view) | |
139 | part = map->partition_to_view[part]; | |
6de9cd9a DN |
140 | return part; |
141 | } | |
142 | ||
143 | ||
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. */ | |
146 | ||
147 | static inline tree | |
148 | var_to_partition_to_var (var_map map, tree var) | |
149 | { | |
150 | int part; | |
151 | ||
152 | part = var_to_partition (map, var); | |
153 | if (part == NO_PARTITION) | |
154 | return NULL_TREE; | |
155 | return partition_to_var (map, part); | |
156 | } | |
157 | ||
158 | ||
7290d709 AM |
159 | /* Return the index into the basevar table for PARTITION's base in MAP. */ |
160 | ||
161 | static inline int | |
162 | basevar_index (var_map map, int partition) | |
163 | { | |
06795261 JH |
164 | gcc_checking_assert (partition >= 0 |
165 | && partition <= (int) num_var_partitions (map)); | |
7290d709 AM |
166 | return map->partition_to_base_index[partition]; |
167 | } | |
168 | ||
169 | ||
170 | /* Return the number of different base variables in MAP. */ | |
171 | ||
172 | static inline int | |
173 | num_basevars (var_map map) | |
174 | { | |
175 | return map->num_basevars; | |
176 | } | |
177 | ||
178 | ||
179 | ||
b8698a0f L |
180 | /* This routine registers a partition for SSA_VAR with MAP. Any unregistered |
181 | partitions may be filtered out by a view later. */ | |
6de9cd9a DN |
182 | |
183 | static inline void | |
b8698a0f | 184 | register_ssa_partition (var_map map ATTRIBUTE_UNUSED, |
1fec7ed4 | 185 | tree ssa_var ATTRIBUTE_UNUSED) |
6de9cd9a | 186 | { |
6de9cd9a | 187 | #if defined ENABLE_CHECKING |
1e128c5f | 188 | register_ssa_partition_check (ssa_var); |
6de9cd9a | 189 | #endif |
6de9cd9a DN |
190 | } |
191 | ||
192 | ||
b8698a0f | 193 | /* ---------------- live on entry/exit info ------------------------------ |
6de9cd9a DN |
194 | |
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. | |
b8698a0f | 198 | As well, partitions are marked as to whether they are global (live |
6de9cd9a DN |
199 | outside the basic block they are defined in). |
200 | ||
b8698a0f L |
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 | |
32ace6e2 | 203 | that block. |
6de9cd9a | 204 | |
32ace6e2 | 205 | The live-on-exit information is per block. It provides a bitmap for each |
6de9cd9a DN |
206 | block indicating which partitions are live on exit from the block. |
207 | ||
b8698a0f | 208 | For the purposes of this implementation, we treat the elements of a PHI |
6de9cd9a DN |
209 | as follows: |
210 | ||
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. | |
214 | ||
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 | |
b8698a0f | 217 | block having a stmt (or block-preheader) before the first real stmt in |
6de9cd9a | 218 | the block which defines all the variables that are defined by PHIs. |
b8698a0f | 219 | |
6de9cd9a DN |
220 | ----------------------------------------------------------------------- */ |
221 | ||
222 | ||
223 | typedef struct tree_live_info_d | |
224 | { | |
225 | /* Var map this relates to. */ | |
226 | var_map map; | |
227 | ||
228 | /* Bitmap indicating which partitions are global. */ | |
229 | bitmap global; | |
230 | ||
3f9b14ff SB |
231 | /* Bitmaps of live on entry blocks for partition elements. */ |
232 | bitmap_head *livein; | |
233 | ||
234 | /* Bitmaps of what variables are live on exit for a basic blocks. */ | |
235 | bitmap_head *liveout; | |
6de9cd9a DN |
236 | |
237 | /* Number of basic blocks when live on exit calculated. */ | |
238 | int num_blocks; | |
239 | ||
32ace6e2 AM |
240 | /* Vector used when creating live ranges as a visited stack. */ |
241 | int *work_stack; | |
242 | ||
243 | /* Top of workstack. */ | |
244 | int *stack_top; | |
87d0d6c4 RB |
245 | |
246 | /* Obstacks to allocate the bitmaps on. */ | |
247 | bitmap_obstack livein_obstack; | |
248 | bitmap_obstack liveout_obstack; | |
6de9cd9a DN |
249 | } *tree_live_info_p; |
250 | ||
251 | ||
6de9cd9a DN |
252 | #define LIVEDUMP_ENTRY 0x01 |
253 | #define LIVEDUMP_EXIT 0x02 | |
254 | #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT) | |
c1bf2a39 | 255 | extern void delete_tree_live_info (tree_live_info_p); |
87d0d6c4 | 256 | extern tree_live_info_p calculate_live_ranges (var_map, bool); |
7b3b6ae4 LC |
257 | extern void debug (tree_live_info_d &ref); |
258 | extern void debug (tree_live_info_d *ptr); | |
c1bf2a39 | 259 | extern void dump_live_info (FILE *, tree_live_info_p, int); |
6de9cd9a | 260 | |
6de9cd9a DN |
261 | |
262 | /* Return TRUE if P is marked as a global in LIVE. */ | |
263 | ||
264 | static inline int | |
265 | partition_is_global (tree_live_info_p live, int p) | |
266 | { | |
06795261 | 267 | gcc_checking_assert (live->global); |
6de9cd9a DN |
268 | return bitmap_bit_p (live->global, p); |
269 | } | |
270 | ||
271 | ||
b8698a0f | 272 | /* Return the bitmap from LIVE representing the live on entry blocks for |
6de9cd9a DN |
273 | partition P. */ |
274 | ||
275 | static inline bitmap | |
32ace6e2 | 276 | live_on_entry (tree_live_info_p live, basic_block bb) |
6de9cd9a | 277 | { |
06795261 | 278 | gcc_checking_assert (live->livein |
fefa31b5 DM |
279 | && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
280 | && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
32ace6e2 | 281 | |
3f9b14ff | 282 | return &live->livein[bb->index]; |
6de9cd9a DN |
283 | } |
284 | ||
285 | ||
286 | /* Return the bitmap from LIVE representing the live on exit partitions from | |
287 | block BB. */ | |
288 | ||
289 | static inline bitmap | |
290 | live_on_exit (tree_live_info_p live, basic_block bb) | |
291 | { | |
06795261 | 292 | gcc_checking_assert (live->liveout |
fefa31b5 DM |
293 | && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
294 | && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
6de9cd9a | 295 | |
3f9b14ff | 296 | return &live->liveout[bb->index]; |
6de9cd9a DN |
297 | } |
298 | ||
299 | ||
300 | /* Return the partition map which the information in LIVE utilizes. */ | |
301 | ||
b8698a0f | 302 | static inline var_map |
6de9cd9a DN |
303 | live_var_map (tree_live_info_p live) |
304 | { | |
305 | return live->map; | |
306 | } | |
307 | ||
308 | ||
309 | /* Merge the live on entry information in LIVE for partitions P1 and P2. Place | |
9cf737f8 | 310 | the result into P1. Clear P2. */ |
6de9cd9a | 311 | |
b8698a0f | 312 | static inline void |
6de9cd9a DN |
313 | live_merge_and_clear (tree_live_info_p live, int p1, int p2) |
314 | { | |
3f9b14ff SB |
315 | gcc_checking_assert (&live->livein[p1] && &live->livein[p2]); |
316 | bitmap_ior_into (&live->livein[p1], &live->livein[p2]); | |
f61e445a | 317 | bitmap_clear (&live->livein[p2]); |
6de9cd9a DN |
318 | } |
319 | ||
320 | ||
321 | /* Mark partition P as live on entry to basic block BB in LIVE. */ | |
322 | ||
b8698a0f | 323 | static inline void |
6de9cd9a DN |
324 | make_live_on_entry (tree_live_info_p live, basic_block bb , int p) |
325 | { | |
3f9b14ff | 326 | bitmap_set_bit (&live->livein[bb->index], p); |
6de9cd9a DN |
327 | bitmap_set_bit (live->global, p); |
328 | } | |
329 | ||
6de9cd9a | 330 | #endif /* _TREE_SSA_LIVE_H */ |