]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Liveness for SSA trees. |
ec8c1492 | 2 | Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011 |
cf835838 | 3 | Free Software Foundation, Inc. |
6de9cd9a DN |
4 | Contributed by Andrew MacLeod <amacleod@redhat.com> |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
9dcd6f09 | 10 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
11 | any later version. |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
21 | |
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "tree.h" | |
cf835838 | 27 | #include "gimple-pretty-print.h" |
6de9cd9a DN |
28 | #include "bitmap.h" |
29 | #include "tree-flow.h" | |
7ee2468b SB |
30 | #include "timevar.h" |
31 | #include "dumpfile.h" | |
6de9cd9a | 32 | #include "tree-ssa-live.h" |
718f9c0f | 33 | #include "diagnostic-core.h" |
aee46bbd JH |
34 | #include "debug.h" |
35 | #include "flags.h" | |
c31c32f9 | 36 | #include "gimple.h" |
7290d709 | 37 | |
32ace6e2 AM |
38 | #ifdef ENABLE_CHECKING |
39 | static void verify_live_on_entry (tree_live_info_p); | |
40 | #endif | |
6de9cd9a | 41 | |
6de9cd9a | 42 | |
7290d709 AM |
43 | /* VARMAP maintains a mapping from SSA version number to real variables. |
44 | ||
45 | All SSA_NAMES are divided into partitions. Initially each ssa_name is the | |
46 | only member of it's own partition. Coalescing will attempt to group any | |
47 | ssa_names which occur in a copy or in a PHI node into the same partition. | |
48 | ||
49 | At the end of out-of-ssa, each partition becomes a "real" variable and is | |
50 | rewritten as a compiler variable. | |
51 | ||
fa10beec | 52 | The var_map data structure is used to manage these partitions. It allows |
7290d709 AM |
53 | partitions to be combined, and determines which partition belongs to what |
54 | ssa_name or variable, and vice versa. */ | |
55 | ||
56 | ||
57 | /* This routine will initialize the basevar fields of MAP. */ | |
58 | ||
59 | static void | |
60 | var_map_base_init (var_map map) | |
61 | { | |
5f564b8f | 62 | int x, num_part; |
7290d709 | 63 | tree var; |
5f564b8f MM |
64 | htab_t decl_to_index; |
65 | struct tree_int_map *m, *mapstorage; | |
b8698a0f | 66 | |
7290d709 | 67 | num_part = num_var_partitions (map); |
5f564b8f MM |
68 | decl_to_index = htab_create (num_part, tree_decl_map_hash, |
69 | tree_int_map_eq, NULL); | |
70 | /* We can have at most num_part entries in the hash tables, so it's | |
71 | enough to allocate so many map elements once, saving some malloc | |
72 | calls. */ | |
73 | mapstorage = m = XNEWVEC (struct tree_int_map, num_part); | |
7290d709 AM |
74 | |
75 | /* If a base table already exists, clear it, otherwise create it. */ | |
5f564b8f | 76 | free (map->partition_to_base_index); |
7290d709 AM |
77 | map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part); |
78 | ||
79 | /* Build the base variable list, and point partitions at their bases. */ | |
80 | for (x = 0; x < num_part; x++) | |
81 | { | |
5f564b8f MM |
82 | struct tree_int_map **slot; |
83 | unsigned baseindex; | |
7290d709 | 84 | var = partition_to_var (map, x); |
5f564b8f | 85 | var = SSA_NAME_VAR (var); |
7290d709 | 86 | /* If base variable hasn't been seen, set it up. */ |
5f564b8f MM |
87 | m->base.from = var; |
88 | slot = (struct tree_int_map **) htab_find_slot (decl_to_index, m, INSERT); | |
89 | if (!*slot) | |
90 | { | |
91 | baseindex = m - mapstorage; | |
92 | m->to = baseindex; | |
93 | *slot = m; | |
94 | m++; | |
7290d709 | 95 | } |
5f564b8f MM |
96 | else |
97 | baseindex = (*slot)->to; | |
98 | map->partition_to_base_index[x] = baseindex; | |
7290d709 AM |
99 | } |
100 | ||
5f564b8f | 101 | map->num_basevars = m - mapstorage; |
7290d709 | 102 | |
5f564b8f MM |
103 | free (mapstorage); |
104 | htab_delete (decl_to_index); | |
7290d709 AM |
105 | } |
106 | ||
6de9cd9a | 107 | |
7290d709 | 108 | /* Remove the base table in MAP. */ |
6de9cd9a | 109 | |
7290d709 AM |
110 | static void |
111 | var_map_base_fini (var_map map) | |
112 | { | |
113 | /* Free the basevar info if it is present. */ | |
114 | if (map->partition_to_base_index != NULL) | |
115 | { | |
7290d709 AM |
116 | free (map->partition_to_base_index); |
117 | map->partition_to_base_index = NULL; | |
118 | map->num_basevars = 0; | |
119 | } | |
120 | } | |
6de9cd9a DN |
121 | /* Create a variable partition map of SIZE, initialize and return it. */ |
122 | ||
123 | var_map | |
124 | init_var_map (int size) | |
125 | { | |
126 | var_map map; | |
127 | ||
128 | map = (var_map) xmalloc (sizeof (struct _var_map)); | |
129 | map->var_partition = partition_new (size); | |
6de9cd9a | 130 | |
7290d709 AM |
131 | map->partition_to_view = NULL; |
132 | map->view_to_partition = NULL; | |
6de9cd9a DN |
133 | map->num_partitions = size; |
134 | map->partition_size = size; | |
7290d709 AM |
135 | map->num_basevars = 0; |
136 | map->partition_to_base_index = NULL; | |
6de9cd9a DN |
137 | return map; |
138 | } | |
139 | ||
140 | ||
141 | /* Free memory associated with MAP. */ | |
142 | ||
143 | void | |
144 | delete_var_map (var_map map) | |
145 | { | |
7290d709 | 146 | var_map_base_fini (map); |
6de9cd9a | 147 | partition_delete (map->var_partition); |
04695783 JM |
148 | free (map->partition_to_view); |
149 | free (map->view_to_partition); | |
6de9cd9a DN |
150 | free (map); |
151 | } | |
152 | ||
153 | ||
b8698a0f L |
154 | /* This function will combine the partitions in MAP for VAR1 and VAR2. It |
155 | Returns the partition which represents the new partition. If the two | |
9cf737f8 | 156 | partitions cannot be combined, NO_PARTITION is returned. */ |
6de9cd9a DN |
157 | |
158 | int | |
159 | var_union (var_map map, tree var1, tree var2) | |
160 | { | |
161 | int p1, p2, p3; | |
4e3825db MM |
162 | |
163 | gcc_assert (TREE_CODE (var1) == SSA_NAME); | |
164 | gcc_assert (TREE_CODE (var2) == SSA_NAME); | |
6de9cd9a | 165 | |
b8698a0f | 166 | /* This is independent of partition_to_view. If partition_to_view is |
6de9cd9a | 167 | on, then whichever one of these partitions is absorbed will never have a |
7290d709 | 168 | dereference into the partition_to_view array any more. */ |
6de9cd9a | 169 | |
4e3825db MM |
170 | p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); |
171 | p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); | |
6de9cd9a | 172 | |
1e128c5f GB |
173 | gcc_assert (p1 != NO_PARTITION); |
174 | gcc_assert (p2 != NO_PARTITION); | |
6de9cd9a DN |
175 | |
176 | if (p1 == p2) | |
177 | p3 = p1; | |
178 | else | |
179 | p3 = partition_union (map->var_partition, p1, p2); | |
180 | ||
7290d709 AM |
181 | if (map->partition_to_view) |
182 | p3 = map->partition_to_view[p3]; | |
6de9cd9a | 183 | |
6de9cd9a DN |
184 | return p3; |
185 | } | |
186 | ||
b8698a0f L |
187 | |
188 | /* Compress the partition numbers in MAP such that they fall in the range | |
6de9cd9a DN |
189 | 0..(num_partitions-1) instead of wherever they turned out during |
190 | the partitioning exercise. This removes any references to unused | |
191 | partitions, thereby allowing bitmaps and other vectors to be much | |
b8698a0f | 192 | denser. |
6de9cd9a DN |
193 | |
194 | This is implemented such that compaction doesn't affect partitioning. | |
195 | Ie., once partitions are created and possibly merged, running one | |
196 | or more different kind of compaction will not affect the partitions | |
197 | themselves. Their index might change, but all the same variables will | |
198 | still be members of the same partition group. This allows work on reduced | |
199 | sets, and no loss of information when a larger set is later desired. | |
200 | ||
201 | In particular, coalescing can work on partitions which have 2 or more | |
202 | definitions, and then 'recompact' later to include all the single | |
203 | definitions for assignment to program variables. */ | |
204 | ||
7290d709 | 205 | |
b8698a0f L |
206 | /* Set MAP back to the initial state of having no partition view. Return a |
207 | bitmap which has a bit set for each partition number which is in use in the | |
7290d709 AM |
208 | varmap. */ |
209 | ||
210 | static bitmap | |
211 | partition_view_init (var_map map) | |
6de9cd9a | 212 | { |
7290d709 AM |
213 | bitmap used; |
214 | int tmp; | |
215 | unsigned int x; | |
6de9cd9a | 216 | |
7290d709 | 217 | used = BITMAP_ALLOC (NULL); |
6de9cd9a | 218 | |
7290d709 AM |
219 | /* Already in a view? Abandon the old one. */ |
220 | if (map->partition_to_view) | |
6de9cd9a | 221 | { |
7290d709 AM |
222 | free (map->partition_to_view); |
223 | map->partition_to_view = NULL; | |
6de9cd9a | 224 | } |
7290d709 | 225 | if (map->view_to_partition) |
6de9cd9a | 226 | { |
7290d709 AM |
227 | free (map->view_to_partition); |
228 | map->view_to_partition = NULL; | |
6de9cd9a DN |
229 | } |
230 | ||
6de9cd9a | 231 | /* Find out which partitions are actually referenced. */ |
7290d709 | 232 | for (x = 0; x < map->partition_size; x++) |
6de9cd9a DN |
233 | { |
234 | tmp = partition_find (map->var_partition, x); | |
4e3825db MM |
235 | if (ssa_name (tmp) != NULL_TREE && is_gimple_reg (ssa_name (tmp)) |
236 | && (!has_zero_uses (ssa_name (tmp)) | |
237 | || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp)))) | |
7290d709 | 238 | bitmap_set_bit (used, tmp); |
6de9cd9a DN |
239 | } |
240 | ||
7290d709 AM |
241 | map->num_partitions = map->partition_size; |
242 | return used; | |
243 | } | |
244 | ||
245 | ||
246 | /* This routine will finalize the view data for MAP based on the partitions | |
b8698a0f | 247 | set in SELECTED. This is either the same bitmap returned from |
7290d709 AM |
248 | partition_view_init, or a trimmed down version if some of those partitions |
249 | were not desired in this view. SELECTED is freed before returning. */ | |
250 | ||
b8698a0f | 251 | static void |
7290d709 AM |
252 | partition_view_fini (var_map map, bitmap selected) |
253 | { | |
254 | bitmap_iterator bi; | |
255 | unsigned count, i, x, limit; | |
7290d709 AM |
256 | |
257 | gcc_assert (selected); | |
258 | ||
259 | count = bitmap_count_bits (selected); | |
260 | limit = map->partition_size; | |
261 | ||
262 | /* If its a one-to-one ratio, we don't need any view compaction. */ | |
263 | if (count < limit) | |
6de9cd9a | 264 | { |
7290d709 AM |
265 | map->partition_to_view = (int *)xmalloc (limit * sizeof (int)); |
266 | memset (map->partition_to_view, 0xff, (limit * sizeof (int))); | |
267 | map->view_to_partition = (int *)xmalloc (count * sizeof (int)); | |
b6e7e9af | 268 | |
7290d709 AM |
269 | i = 0; |
270 | /* Give each selected partition an index. */ | |
271 | EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi) | |
6de9cd9a | 272 | { |
7290d709 AM |
273 | map->partition_to_view[x] = i; |
274 | map->view_to_partition[i] = x; | |
7290d709 | 275 | i++; |
b6e7e9af | 276 | } |
7290d709 AM |
277 | gcc_assert (i == count); |
278 | map->num_partitions = i; | |
6de9cd9a | 279 | } |
7290d709 AM |
280 | |
281 | BITMAP_FREE (selected); | |
282 | } | |
283 | ||
284 | ||
b8698a0f | 285 | /* Create a partition view which includes all the used partitions in MAP. If |
7290d709 AM |
286 | WANT_BASES is true, create the base variable map as well. */ |
287 | ||
288 | extern void | |
289 | partition_view_normal (var_map map, bool want_bases) | |
290 | { | |
291 | bitmap used; | |
292 | ||
293 | used = partition_view_init (map); | |
294 | partition_view_fini (map, used); | |
295 | ||
296 | if (want_bases) | |
297 | var_map_base_init (map); | |
6de9cd9a | 298 | else |
7290d709 AM |
299 | var_map_base_fini (map); |
300 | } | |
301 | ||
302 | ||
b8698a0f L |
303 | /* Create a partition view in MAP which includes just partitions which occur in |
304 | the bitmap ONLY. If WANT_BASES is true, create the base variable map | |
7290d709 AM |
305 | as well. */ |
306 | ||
307 | extern void | |
308 | partition_view_bitmap (var_map map, bitmap only, bool want_bases) | |
309 | { | |
310 | bitmap used; | |
311 | bitmap new_partitions = BITMAP_ALLOC (NULL); | |
312 | unsigned x, p; | |
313 | bitmap_iterator bi; | |
314 | ||
315 | used = partition_view_init (map); | |
316 | EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi) | |
6de9cd9a | 317 | { |
7290d709 AM |
318 | p = partition_find (map->var_partition, x); |
319 | gcc_assert (bitmap_bit_p (used, p)); | |
320 | bitmap_set_bit (new_partitions, p); | |
6de9cd9a | 321 | } |
7290d709 | 322 | partition_view_fini (map, new_partitions); |
6de9cd9a | 323 | |
7290d709 AM |
324 | BITMAP_FREE (used); |
325 | if (want_bases) | |
326 | var_map_base_init (map); | |
327 | else | |
328 | var_map_base_fini (map); | |
6de9cd9a DN |
329 | } |
330 | ||
331 | ||
5f564b8f MM |
332 | static bitmap usedvars; |
333 | ||
334 | /* Mark VAR as used, so that it'll be preserved during rtl expansion. */ | |
335 | ||
336 | static inline void | |
337 | set_is_used (tree var) | |
338 | { | |
339 | bitmap_set_bit (usedvars, DECL_UID (var)); | |
340 | } | |
341 | ||
342 | /* Return true if VAR is marked as used. */ | |
343 | ||
344 | static inline bool | |
345 | is_used_p (tree var) | |
346 | { | |
347 | return bitmap_bit_p (usedvars, DECL_UID (var)); | |
348 | } | |
349 | ||
900461f3 | 350 | static inline void mark_all_vars_used (tree *, void *data); |
6de9cd9a | 351 | |
727a31fa RH |
352 | /* Helper function for mark_all_vars_used, called via walk_tree. */ |
353 | ||
354 | static tree | |
726a989a | 355 | mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data) |
727a31fa | 356 | { |
9c09f152 | 357 | bitmap global_unused_vars = (bitmap)data; |
727a31fa | 358 | tree t = *tp; |
aee46bbd JH |
359 | enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t)); |
360 | tree b; | |
727a31fa | 361 | |
3f519b35 RG |
362 | if (TREE_CODE (t) == SSA_NAME) |
363 | t = SSA_NAME_VAR (t); | |
726a989a RB |
364 | |
365 | if (IS_EXPR_CODE_CLASS (c) | |
aee46bbd JH |
366 | && (b = TREE_BLOCK (t)) != NULL) |
367 | TREE_USED (b) = true; | |
3f519b35 | 368 | |
4d948885 RG |
369 | /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those |
370 | fields do not contain vars. */ | |
89632019 ZD |
371 | if (TREE_CODE (t) == TARGET_MEM_REF) |
372 | { | |
900461f3 JJ |
373 | mark_all_vars_used (&TMR_BASE (t), data); |
374 | mark_all_vars_used (&TMR_INDEX (t), data); | |
4d948885 | 375 | mark_all_vars_used (&TMR_INDEX2 (t), data); |
89632019 ZD |
376 | *walk_subtrees = 0; |
377 | return NULL; | |
378 | } | |
379 | ||
727a31fa RH |
380 | /* Only need to mark VAR_DECLS; parameters and return results are not |
381 | eliminated as unused. */ | |
382 | if (TREE_CODE (t) == VAR_DECL) | |
900461f3 | 383 | { |
9c09f152 RB |
384 | /* Global vars do not have a var-annotation so their use is tracked |
385 | with the global_unused_vars bitmap. Also walk their initializer | |
386 | when they are first recognized as used. */ | |
387 | if (is_global_var (t)) | |
388 | { | |
389 | if (bitmap_clear_bit (global_unused_vars, DECL_UID (t))) | |
390 | mark_all_vars_used (&DECL_INITIAL (t), data); | |
391 | } | |
392 | else | |
cb0c9fc3 | 393 | set_is_used (t); |
900461f3 | 394 | } |
ccf134c7 RG |
395 | /* remove_unused_scope_block_p requires information about labels |
396 | which are not DECL_IGNORED_P to tell if they might be used in the IL. */ | |
9c09f152 | 397 | else if (TREE_CODE (t) == LABEL_DECL) |
ccf134c7 RG |
398 | /* Although the TREE_USED values that the frontend uses would be |
399 | acceptable (albeit slightly over-conservative) for our purposes, | |
400 | init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we | |
401 | must re-compute it here. */ | |
402 | TREE_USED (t) = 1; | |
727a31fa | 403 | |
6615c446 | 404 | if (IS_TYPE_OR_DECL_P (t)) |
727a31fa RH |
405 | *walk_subtrees = 0; |
406 | ||
407 | return NULL; | |
408 | } | |
409 | ||
aee46bbd JH |
410 | /* Mark the scope block SCOPE and its subblocks unused when they can be |
411 | possibly eliminated if dead. */ | |
412 | ||
413 | static void | |
414 | mark_scope_block_unused (tree scope) | |
415 | { | |
416 | tree t; | |
417 | TREE_USED (scope) = false; | |
418 | if (!(*debug_hooks->ignore_block) (scope)) | |
419 | TREE_USED (scope) = true; | |
420 | for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t)) | |
421 | mark_scope_block_unused (t); | |
422 | } | |
423 | ||
424 | /* Look if the block is dead (by possibly eliminating its dead subblocks) | |
b8698a0f | 425 | and return true if so. |
aee46bbd JH |
426 | Block is declared dead if: |
427 | 1) No statements are associated with it. | |
428 | 2) Declares no live variables | |
429 | 3) All subblocks are dead | |
430 | or there is precisely one subblocks and the block | |
431 | has same abstract origin as outer block and declares | |
432 | no variables, so it is pure wrapper. | |
cea618ac | 433 | When we are not outputting full debug info, we also eliminate dead variables |
aee46bbd JH |
434 | out of scope blocks to let them to be recycled by GGC and to save copying work |
435 | done by the inliner. */ | |
436 | ||
437 | static bool | |
1431ce01 | 438 | remove_unused_scope_block_p (tree scope, bitmap global_unused_vars) |
aee46bbd | 439 | { |
d1aed86b | 440 | tree *t, *next; |
aee46bbd | 441 | bool unused = !TREE_USED (scope); |
aee46bbd JH |
442 | int nsubblocks = 0; |
443 | ||
d1aed86b AO |
444 | for (t = &BLOCK_VARS (scope); *t; t = next) |
445 | { | |
910ad8de | 446 | next = &DECL_CHAIN (*t); |
d1aed86b AO |
447 | |
448 | /* Debug info of nested function refers to the block of the | |
61e04322 JH |
449 | function. We might stil call it even if all statements |
450 | of function it was nested into was elliminated. | |
b8698a0f | 451 | |
61e04322 JH |
452 | TODO: We can actually look into cgraph to see if function |
453 | will be output to file. */ | |
d1aed86b AO |
454 | if (TREE_CODE (*t) == FUNCTION_DECL) |
455 | unused = false; | |
2ce59df7 AO |
456 | |
457 | /* If a decl has a value expr, we need to instantiate it | |
458 | regardless of debug info generation, to avoid codegen | |
459 | differences in memory overlap tests. update_equiv_regs() may | |
460 | indirectly call validate_equiv_mem() to test whether a | |
461 | SET_DEST overlaps with others, and if the value expr changes | |
462 | by virtual register instantiation, we may get end up with | |
463 | different results. */ | |
464 | else if (TREE_CODE (*t) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*t)) | |
465 | unused = false; | |
466 | ||
a300e459 EB |
467 | /* Remove everything we don't generate debug info for. */ |
468 | else if (DECL_IGNORED_P (*t)) | |
b91bc349 | 469 | { |
910ad8de | 470 | *t = DECL_CHAIN (*t); |
b91bc349 JH |
471 | next = t; |
472 | } | |
473 | ||
d1aed86b AO |
474 | /* When we are outputting debug info, we usually want to output |
475 | info about optimized-out variables in the scope blocks. | |
476 | Exception are the scope blocks not containing any instructions | |
477 | at all so user can't get into the scopes at first place. */ | |
1431ce01 RG |
478 | else if ((is_global_var (*t) |
479 | && !bitmap_bit_p (global_unused_vars, DECL_UID (*t))) | |
5f564b8f | 480 | || is_used_p (*t)) |
d1aed86b | 481 | unused = false; |
ccf134c7 RG |
482 | else if (TREE_CODE (*t) == LABEL_DECL && TREE_USED (*t)) |
483 | /* For labels that are still used in the IL, the decision to | |
484 | preserve them must not depend DEBUG_INFO_LEVEL, otherwise we | |
485 | risk having different ordering in debug vs. non-debug builds | |
486 | during inlining or versioning. | |
487 | A label appearing here (we have already checked DECL_IGNORED_P) | |
488 | should not be used in the IL unless it has been explicitly used | |
489 | before, so we use TREE_USED as an approximation. */ | |
490 | /* In principle, we should do the same here as for the debug case | |
491 | below, however, when debugging, there might be additional nested | |
492 | levels that keep an upper level with a label live, so we have to | |
493 | force this block to be considered used, too. */ | |
494 | unused = false; | |
d1aed86b AO |
495 | |
496 | /* When we are not doing full debug info, we however can keep around | |
497 | only the used variables for cfgexpand's memory packing saving quite | |
b8698a0f | 498 | a lot of memory. |
61e04322 JH |
499 | |
500 | For sake of -g3, we keep around those vars but we don't count this as | |
501 | use of block, so innermost block with no used vars and no instructions | |
502 | can be considered dead. We only want to keep around blocks user can | |
b8698a0f | 503 | breakpoint into and ask about value of optimized out variables. |
61e04322 | 504 | |
427f6cec AO |
505 | Similarly we need to keep around types at least until all |
506 | variables of all nested blocks are gone. We track no | |
507 | information on whether given type is used or not, so we have | |
508 | to keep them even when not emitting debug information, | |
509 | otherwise we may end up remapping variables and their (local) | |
510 | types in different orders depending on whether debug | |
511 | information is being generated. */ | |
512 | ||
513 | else if (TREE_CODE (*t) == TYPE_DECL | |
514 | || debug_info_level == DINFO_LEVEL_NORMAL | |
c7ba0cfb | 515 | || debug_info_level == DINFO_LEVEL_VERBOSE) |
61e04322 | 516 | ; |
3c8da8a5 | 517 | else |
d1aed86b | 518 | { |
910ad8de | 519 | *t = DECL_CHAIN (*t); |
d1aed86b AO |
520 | next = t; |
521 | } | |
522 | } | |
523 | ||
aee46bbd | 524 | for (t = &BLOCK_SUBBLOCKS (scope); *t ;) |
1431ce01 | 525 | if (remove_unused_scope_block_p (*t, global_unused_vars)) |
aee46bbd JH |
526 | { |
527 | if (BLOCK_SUBBLOCKS (*t)) | |
528 | { | |
529 | tree next = BLOCK_CHAIN (*t); | |
530 | tree supercontext = BLOCK_SUPERCONTEXT (*t); | |
cff7525f | 531 | |
aee46bbd | 532 | *t = BLOCK_SUBBLOCKS (*t); |
cff7525f JH |
533 | while (BLOCK_CHAIN (*t)) |
534 | { | |
535 | BLOCK_SUPERCONTEXT (*t) = supercontext; | |
536 | t = &BLOCK_CHAIN (*t); | |
537 | } | |
aee46bbd JH |
538 | BLOCK_CHAIN (*t) = next; |
539 | BLOCK_SUPERCONTEXT (*t) = supercontext; | |
540 | t = &BLOCK_CHAIN (*t); | |
541 | nsubblocks ++; | |
542 | } | |
543 | else | |
61e04322 | 544 | *t = BLOCK_CHAIN (*t); |
aee46bbd JH |
545 | } |
546 | else | |
547 | { | |
548 | t = &BLOCK_CHAIN (*t); | |
549 | nsubblocks ++; | |
550 | } | |
cff7525f JH |
551 | |
552 | ||
553 | if (!unused) | |
554 | ; | |
aee46bbd | 555 | /* Outer scope is always used. */ |
cff7525f JH |
556 | else if (!BLOCK_SUPERCONTEXT (scope) |
557 | || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL) | |
aee46bbd | 558 | unused = false; |
cff7525f JH |
559 | /* Innermost blocks with no live variables nor statements can be always |
560 | eliminated. */ | |
561 | else if (!nsubblocks) | |
562 | ; | |
cff7525f JH |
563 | /* For terse debug info we can eliminate info on unused variables. */ |
564 | else if (debug_info_level == DINFO_LEVEL_NONE | |
565 | || debug_info_level == DINFO_LEVEL_TERSE) | |
9f706f23 JJ |
566 | { |
567 | /* Even for -g0/-g1 don't prune outer scopes from artificial | |
568 | functions, otherwise diagnostics using tree_nonartificial_location | |
569 | will not be emitted properly. */ | |
570 | if (inlined_function_outer_scope_p (scope)) | |
571 | { | |
572 | tree ao = scope; | |
573 | ||
574 | while (ao | |
575 | && TREE_CODE (ao) == BLOCK | |
576 | && BLOCK_ABSTRACT_ORIGIN (ao) != ao) | |
577 | ao = BLOCK_ABSTRACT_ORIGIN (ao); | |
578 | if (ao | |
579 | && TREE_CODE (ao) == FUNCTION_DECL | |
580 | && DECL_DECLARED_INLINE_P (ao) | |
581 | && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao))) | |
582 | unused = false; | |
583 | } | |
584 | } | |
526d73ab | 585 | else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope)) |
aee46bbd | 586 | unused = false; |
cff7525f JH |
587 | /* See if this block is important for representation of inlined function. |
588 | Inlined functions are always represented by block with | |
589 | block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION | |
590 | set... */ | |
591 | else if (inlined_function_outer_scope_p (scope)) | |
592 | unused = false; | |
593 | else | |
594 | /* Verfify that only blocks with source location set | |
595 | are entry points to the inlined functions. */ | |
596 | gcc_assert (BLOCK_SOURCE_LOCATION (scope) == UNKNOWN_LOCATION); | |
5b4c43d7 EB |
597 | |
598 | TREE_USED (scope) = !unused; | |
aee46bbd JH |
599 | return unused; |
600 | } | |
7290d709 | 601 | |
b8698a0f | 602 | /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be |
727a31fa RH |
603 | eliminated during the tree->rtl conversion process. */ |
604 | ||
605 | static inline void | |
900461f3 | 606 | mark_all_vars_used (tree *expr_p, void *data) |
727a31fa | 607 | { |
900461f3 | 608 | walk_tree (expr_p, mark_all_vars_used_1, data, NULL); |
727a31fa RH |
609 | } |
610 | ||
ac80ba07 DN |
611 | |
612 | /* Dump scope blocks starting at SCOPE to FILE. INDENT is the | |
613 | indentation level and FLAGS is as in print_generic_expr. */ | |
61e04322 JH |
614 | |
615 | static void | |
616 | dump_scope_block (FILE *file, int indent, tree scope, int flags) | |
617 | { | |
618 | tree var, t; | |
526d73ab | 619 | unsigned int i; |
61e04322 | 620 | |
cff7525f JH |
621 | fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope), |
622 | TREE_USED (scope) ? "" : " (unused)", | |
623 | BLOCK_ABSTRACT (scope) ? " (abstract)": ""); | |
624 | if (BLOCK_SOURCE_LOCATION (scope) != UNKNOWN_LOCATION) | |
625 | { | |
626 | expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope)); | |
627 | fprintf (file, " %s:%i", s.file, s.line); | |
628 | } | |
629 | if (BLOCK_ABSTRACT_ORIGIN (scope)) | |
61e04322 | 630 | { |
cff7525f JH |
631 | tree origin = block_ultimate_origin (scope); |
632 | if (origin) | |
633 | { | |
634 | fprintf (file, " Originating from :"); | |
635 | if (DECL_P (origin)) | |
636 | print_generic_decl (file, origin, flags); | |
637 | else | |
638 | fprintf (file, "#%i", BLOCK_NUMBER (origin)); | |
639 | } | |
61e04322 | 640 | } |
cff7525f | 641 | fprintf (file, " \n"); |
910ad8de | 642 | for (var = BLOCK_VARS (scope); var; var = DECL_CHAIN (var)) |
61e04322 | 643 | { |
83d70792 | 644 | fprintf (file, "%*s", indent, ""); |
61e04322 | 645 | print_generic_decl (file, var, flags); |
5f564b8f | 646 | fprintf (file, "\n"); |
61e04322 | 647 | } |
526d73ab JH |
648 | for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++) |
649 | { | |
650 | fprintf (file, "%*s",indent, ""); | |
651 | print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i), | |
652 | flags); | |
653 | fprintf (file, " (nonlocalized)\n"); | |
654 | } | |
61e04322 JH |
655 | for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t)) |
656 | dump_scope_block (file, indent + 2, t, flags); | |
cff7525f | 657 | fprintf (file, "\n%*s}\n",indent, ""); |
61e04322 JH |
658 | } |
659 | ||
c6a21142 RG |
660 | /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS |
661 | is as in print_generic_expr. */ | |
662 | ||
24e47c76 | 663 | DEBUG_FUNCTION void |
c6a21142 RG |
664 | debug_scope_block (tree scope, int flags) |
665 | { | |
666 | dump_scope_block (stderr, 0, scope, flags); | |
667 | } | |
668 | ||
ac80ba07 DN |
669 | |
670 | /* Dump the tree of lexical scopes of current_function_decl to FILE. | |
671 | FLAGS is as in print_generic_expr. */ | |
672 | ||
cff7525f JH |
673 | void |
674 | dump_scope_blocks (FILE *file, int flags) | |
675 | { | |
676 | dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags); | |
677 | } | |
3f519b35 | 678 | |
ac80ba07 DN |
679 | |
680 | /* Dump the tree of lexical scopes of current_function_decl to stderr. | |
681 | FLAGS is as in print_generic_expr. */ | |
682 | ||
24e47c76 | 683 | DEBUG_FUNCTION void |
ac80ba07 DN |
684 | debug_scope_blocks (int flags) |
685 | { | |
686 | dump_scope_blocks (stderr, flags); | |
687 | } | |
688 | ||
3f519b35 RG |
689 | /* Remove local variables that are not referenced in the IL. */ |
690 | ||
691 | void | |
692 | remove_unused_locals (void) | |
693 | { | |
694 | basic_block bb; | |
46eb666a | 695 | tree var; |
900461f3 | 696 | bitmap global_unused_vars = NULL; |
9c09f152 | 697 | unsigned srcidx, dstidx, num, ix; |
47598145 | 698 | bool have_local_clobbers = false; |
3f519b35 | 699 | |
89fbbe4e AO |
700 | /* Removing declarations from lexical blocks when not optimizing is |
701 | not only a waste of time, it actually causes differences in stack | |
702 | layout. */ | |
703 | if (!optimize) | |
704 | return; | |
705 | ||
a222c01a MM |
706 | timevar_push (TV_REMOVE_UNUSED); |
707 | ||
61e04322 | 708 | mark_scope_block_unused (DECL_INITIAL (current_function_decl)); |
726a989a | 709 | |
5f564b8f | 710 | usedvars = BITMAP_ALLOC (NULL); |
3f519b35 | 711 | |
9c09f152 RB |
712 | /* Assume all globals in local decls are unused. */ |
713 | global_unused_vars = BITMAP_ALLOC (NULL); | |
714 | FOR_EACH_LOCAL_DECL (cfun, ix, var) | |
715 | if (TREE_CODE (var) == VAR_DECL | |
716 | && is_global_var (var)) | |
717 | bitmap_set_bit (global_unused_vars, DECL_UID (var)); | |
718 | ||
3f519b35 RG |
719 | /* Walk the CFG marking all referenced symbols. */ |
720 | FOR_EACH_BB (bb) | |
721 | { | |
726a989a RB |
722 | gimple_stmt_iterator gsi; |
723 | size_t i; | |
cc2a64dd JJ |
724 | edge_iterator ei; |
725 | edge e; | |
3f519b35 RG |
726 | |
727 | /* Walk the statements. */ | |
726a989a RB |
728 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
729 | { | |
730 | gimple stmt = gsi_stmt (gsi); | |
731 | tree b = gimple_block (stmt); | |
732 | ||
b5b8b0ac AO |
733 | if (is_gimple_debug (stmt)) |
734 | continue; | |
735 | ||
47598145 MM |
736 | if (gimple_clobber_p (stmt)) |
737 | { | |
738 | have_local_clobbers = true; | |
739 | continue; | |
740 | } | |
741 | ||
726a989a RB |
742 | if (b) |
743 | TREE_USED (b) = true; | |
3f519b35 | 744 | |
726a989a | 745 | for (i = 0; i < gimple_num_ops (stmt); i++) |
9c09f152 RB |
746 | mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i), |
747 | global_unused_vars); | |
726a989a RB |
748 | } |
749 | ||
750 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
3f519b35 RG |
751 | { |
752 | use_operand_p arg_p; | |
753 | ssa_op_iter i; | |
726a989a RB |
754 | tree def; |
755 | gimple phi = gsi_stmt (gsi); | |
3f519b35 | 756 | |
9c09f152 | 757 | if (!is_gimple_reg (gimple_phi_result (phi))) |
3f519b35 RG |
758 | continue; |
759 | ||
726a989a | 760 | def = gimple_phi_result (phi); |
9c09f152 | 761 | mark_all_vars_used (&def, global_unused_vars); |
3f519b35 RG |
762 | |
763 | FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES) | |
764 | { | |
765 | tree arg = USE_FROM_PTR (arg_p); | |
9c09f152 | 766 | mark_all_vars_used (&arg, global_unused_vars); |
3f519b35 RG |
767 | } |
768 | } | |
cc2a64dd JJ |
769 | |
770 | FOR_EACH_EDGE (e, ei, bb->succs) | |
771 | if (e->goto_locus) | |
772 | TREE_USED (e->goto_block) = true; | |
3f519b35 RG |
773 | } |
774 | ||
47598145 MM |
775 | /* We do a two-pass approach about the out-of-scope clobbers. We want |
776 | to remove them if they are the only references to a local variable, | |
777 | but we want to retain them when there's any other. So the first pass | |
778 | ignores them, and the second pass (if there were any) tries to remove | |
779 | them. */ | |
780 | if (have_local_clobbers) | |
781 | FOR_EACH_BB (bb) | |
782 | { | |
783 | gimple_stmt_iterator gsi; | |
784 | ||
785 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) | |
786 | { | |
787 | gimple stmt = gsi_stmt (gsi); | |
788 | tree b = gimple_block (stmt); | |
789 | ||
790 | if (gimple_clobber_p (stmt)) | |
791 | { | |
792 | tree lhs = gimple_assign_lhs (stmt); | |
793 | lhs = get_base_address (lhs); | |
794 | if (TREE_CODE (lhs) == SSA_NAME) | |
795 | lhs = SSA_NAME_VAR (lhs); | |
9c09f152 RB |
796 | if (TREE_CODE (lhs) == VAR_DECL |
797 | && ((is_global_var (lhs) | |
798 | && bitmap_bit_p (global_unused_vars, DECL_UID (lhs))) | |
799 | || (!is_global_var (lhs) && !is_used_p (lhs)))) | |
47598145 MM |
800 | { |
801 | unlink_stmt_vdef (stmt); | |
802 | gsi_remove (&gsi, true); | |
803 | release_defs (stmt); | |
804 | continue; | |
805 | } | |
806 | if (b) | |
807 | TREE_USED (b) = true; | |
808 | } | |
809 | gsi_next (&gsi); | |
810 | } | |
811 | } | |
812 | ||
fc3103e7 JJ |
813 | cfun->has_local_explicit_reg_vars = false; |
814 | ||
9c09f152 RB |
815 | /* Remove unmarked local and global vars from local_decls |
816 | and referenced vars. */ | |
2fed2012 JJ |
817 | num = VEC_length (tree, cfun->local_decls); |
818 | for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++) | |
3f519b35 | 819 | { |
2fed2012 | 820 | var = VEC_index (tree, cfun->local_decls, srcidx); |
9c09f152 | 821 | if (TREE_CODE (var) == VAR_DECL) |
3f519b35 | 822 | { |
900461f3 JJ |
823 | if (is_global_var (var)) |
824 | { | |
9c09f152 RB |
825 | if (bitmap_bit_p (global_unused_vars, DECL_UID (var))) |
826 | continue; | |
827 | } | |
5f564b8f | 828 | else if (!is_used_p (var)) |
9c09f152 | 829 | { |
ca5f4331 MM |
830 | if (cfun->nonlocal_goto_save_area |
831 | && TREE_OPERAND (cfun->nonlocal_goto_save_area, 0) == var) | |
832 | cfun->nonlocal_goto_save_area = NULL; | |
9c09f152 | 833 | continue; |
900461f3 | 834 | } |
3f519b35 | 835 | } |
9c09f152 RB |
836 | if (TREE_CODE (var) == VAR_DECL |
837 | && DECL_HARD_REGISTER (var) | |
838 | && !is_global_var (var)) | |
fc3103e7 | 839 | cfun->has_local_explicit_reg_vars = true; |
c021f10b | 840 | |
2fed2012 JJ |
841 | if (srcidx != dstidx) |
842 | VEC_replace (tree, cfun->local_decls, dstidx, var); | |
843 | dstidx++; | |
3f519b35 | 844 | } |
2fed2012 JJ |
845 | if (dstidx != num) |
846 | VEC_truncate (tree, cfun->local_decls, dstidx); | |
1431ce01 | 847 | |
1431ce01 RG |
848 | remove_unused_scope_block_p (DECL_INITIAL (current_function_decl), |
849 | global_unused_vars); | |
850 | ||
9c09f152 | 851 | BITMAP_FREE (global_unused_vars); |
5f564b8f | 852 | BITMAP_FREE (usedvars); |
326648f1 | 853 | |
61e04322 JH |
854 | if (dump_file && (dump_flags & TDF_DETAILS)) |
855 | { | |
856 | fprintf (dump_file, "Scope blocks after cleanups:\n"); | |
cff7525f | 857 | dump_scope_blocks (dump_file, dump_flags); |
61e04322 | 858 | } |
a222c01a MM |
859 | |
860 | timevar_pop (TV_REMOVE_UNUSED); | |
3f519b35 RG |
861 | } |
862 | ||
6de9cd9a DN |
863 | |
864 | /* Allocate and return a new live range information object base on MAP. */ | |
865 | ||
866 | static tree_live_info_p | |
867 | new_tree_live_info (var_map map) | |
868 | { | |
869 | tree_live_info_p live; | |
3cd8c58a | 870 | unsigned x; |
6de9cd9a DN |
871 | |
872 | live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d)); | |
873 | live->map = map; | |
874 | live->num_blocks = last_basic_block; | |
875 | ||
32ace6e2 AM |
876 | live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); |
877 | for (x = 0; x < (unsigned)last_basic_block; x++) | |
8bdbfff5 | 878 | live->livein[x] = BITMAP_ALLOC (NULL); |
6de9cd9a | 879 | |
32ace6e2 AM |
880 | live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); |
881 | for (x = 0; x < (unsigned)last_basic_block; x++) | |
882 | live->liveout[x] = BITMAP_ALLOC (NULL); | |
883 | ||
884 | live->work_stack = XNEWVEC (int, last_basic_block); | |
885 | live->stack_top = live->work_stack; | |
886 | ||
887 | live->global = BITMAP_ALLOC (NULL); | |
6de9cd9a DN |
888 | return live; |
889 | } | |
890 | ||
891 | ||
892 | /* Free storage for live range info object LIVE. */ | |
893 | ||
b8698a0f | 894 | void |
6de9cd9a DN |
895 | delete_tree_live_info (tree_live_info_p live) |
896 | { | |
897 | int x; | |
6de9cd9a | 898 | |
32ace6e2 AM |
899 | BITMAP_FREE (live->global); |
900 | free (live->work_stack); | |
6de9cd9a | 901 | |
32ace6e2 AM |
902 | for (x = live->num_blocks - 1; x >= 0; x--) |
903 | BITMAP_FREE (live->liveout[x]); | |
904 | free (live->liveout); | |
6de9cd9a | 905 | |
32ace6e2 AM |
906 | for (x = live->num_blocks - 1; x >= 0; x--) |
907 | BITMAP_FREE (live->livein[x]); | |
908 | free (live->livein); | |
6de9cd9a | 909 | |
32ace6e2 | 910 | free (live); |
6de9cd9a DN |
911 | } |
912 | ||
913 | ||
b8698a0f L |
914 | /* Visit basic block BB and propagate any required live on entry bits from |
915 | LIVE into the predecessors. VISITED is the bitmap of visited blocks. | |
2e226e66 | 916 | TMP is a temporary work bitmap which is passed in to avoid reallocating |
32ace6e2 | 917 | it each time. */ |
6de9cd9a | 918 | |
b8698a0f | 919 | static void |
32ace6e2 AM |
920 | loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited, |
921 | bitmap tmp) | |
6de9cd9a | 922 | { |
32ace6e2 AM |
923 | edge e; |
924 | bool change; | |
925 | edge_iterator ei; | |
926 | basic_block pred_bb; | |
927 | bitmap loe; | |
928 | gcc_assert (!TEST_BIT (visited, bb->index)); | |
6de9cd9a | 929 | |
32ace6e2 AM |
930 | SET_BIT (visited, bb->index); |
931 | loe = live_on_entry (live, bb); | |
6de9cd9a | 932 | |
32ace6e2 | 933 | FOR_EACH_EDGE (e, ei, bb->preds) |
6de9cd9a | 934 | { |
32ace6e2 AM |
935 | pred_bb = e->src; |
936 | if (pred_bb == ENTRY_BLOCK_PTR) | |
937 | continue; | |
7290d709 | 938 | /* TMP is variables live-on-entry from BB that aren't defined in the |
b8698a0f | 939 | predecessor block. This should be the live on entry vars to pred. |
32ace6e2 AM |
940 | Note that liveout is the DEFs in a block while live on entry is |
941 | being calculated. */ | |
942 | bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]); | |
943 | ||
b8698a0f | 944 | /* Add these bits to live-on-entry for the pred. if there are any |
32ace6e2 AM |
945 | changes, and pred_bb has been visited already, add it to the |
946 | revisit stack. */ | |
947 | change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp); | |
948 | if (TEST_BIT (visited, pred_bb->index) && change) | |
949 | { | |
950 | RESET_BIT (visited, pred_bb->index); | |
951 | *(live->stack_top)++ = pred_bb->index; | |
952 | } | |
6de9cd9a DN |
953 | } |
954 | } | |
955 | ||
956 | ||
b8698a0f | 957 | /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses |
2e226e66 | 958 | of all the variables. */ |
6de9cd9a | 959 | |
32ace6e2 AM |
960 | static void |
961 | live_worklist (tree_live_info_p live) | |
6de9cd9a | 962 | { |
32ace6e2 | 963 | unsigned b; |
6de9cd9a | 964 | basic_block bb; |
32ace6e2 AM |
965 | sbitmap visited = sbitmap_alloc (last_basic_block + 1); |
966 | bitmap tmp = BITMAP_ALLOC (NULL); | |
6de9cd9a | 967 | |
32ace6e2 | 968 | sbitmap_zero (visited); |
6de9cd9a | 969 | |
110abdbc | 970 | /* Visit all the blocks in reverse order and propagate live on entry values |
32ace6e2 AM |
971 | into the predecessors blocks. */ |
972 | FOR_EACH_BB_REVERSE (bb) | |
973 | loe_visit_block (live, bb, visited, tmp); | |
6de9cd9a | 974 | |
32ace6e2 AM |
975 | /* Process any blocks which require further iteration. */ |
976 | while (live->stack_top != live->work_stack) | |
6de9cd9a | 977 | { |
32ace6e2 AM |
978 | b = *--(live->stack_top); |
979 | loe_visit_block (live, BASIC_BLOCK (b), visited, tmp); | |
980 | } | |
6de9cd9a | 981 | |
32ace6e2 AM |
982 | BITMAP_FREE (tmp); |
983 | sbitmap_free (visited); | |
984 | } | |
6de9cd9a | 985 | |
6de9cd9a | 986 | |
2e226e66 | 987 | /* Calculate the initial live on entry vector for SSA_NAME using immediate_use |
32ace6e2 AM |
988 | links. Set the live on entry fields in LIVE. Def's are marked temporarily |
989 | in the liveout vector. */ | |
6de9cd9a | 990 | |
32ace6e2 AM |
991 | static void |
992 | set_var_live_on_entry (tree ssa_name, tree_live_info_p live) | |
993 | { | |
994 | int p; | |
726a989a | 995 | gimple stmt; |
32ace6e2 AM |
996 | use_operand_p use; |
997 | basic_block def_bb = NULL; | |
998 | imm_use_iterator imm_iter; | |
999 | bool global = false; | |
6de9cd9a | 1000 | |
32ace6e2 AM |
1001 | p = var_to_partition (live->map, ssa_name); |
1002 | if (p == NO_PARTITION) | |
1003 | return; | |
6de9cd9a | 1004 | |
32ace6e2 AM |
1005 | stmt = SSA_NAME_DEF_STMT (ssa_name); |
1006 | if (stmt) | |
6de9cd9a | 1007 | { |
726a989a | 1008 | def_bb = gimple_bb (stmt); |
7290d709 | 1009 | /* Mark defs in liveout bitmap temporarily. */ |
32ace6e2 AM |
1010 | if (def_bb) |
1011 | bitmap_set_bit (live->liveout[def_bb->index], p); | |
87c476a2 | 1012 | } |
32ace6e2 AM |
1013 | else |
1014 | def_bb = ENTRY_BLOCK_PTR; | |
6de9cd9a | 1015 | |
32ace6e2 AM |
1016 | /* Visit each use of SSA_NAME and if it isn't in the same block as the def, |
1017 | add it to the list of live on entry blocks. */ | |
1018 | FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name) | |
6de9cd9a | 1019 | { |
726a989a | 1020 | gimple use_stmt = USE_STMT (use); |
32ace6e2 | 1021 | basic_block add_block = NULL; |
6de9cd9a | 1022 | |
726a989a | 1023 | if (gimple_code (use_stmt) == GIMPLE_PHI) |
32ace6e2 AM |
1024 | { |
1025 | /* Uses in PHI's are considered to be live at exit of the SRC block | |
1026 | as this is where a copy would be inserted. Check to see if it is | |
1027 | defined in that block, or whether its live on entry. */ | |
1028 | int index = PHI_ARG_INDEX_FROM_USE (use); | |
726a989a | 1029 | edge e = gimple_phi_arg_edge (use_stmt, index); |
32ace6e2 | 1030 | if (e->src != ENTRY_BLOCK_PTR) |
6de9cd9a | 1031 | { |
32ace6e2 AM |
1032 | if (e->src != def_bb) |
1033 | add_block = e->src; | |
6de9cd9a | 1034 | } |
32ace6e2 | 1035 | } |
b5b8b0ac AO |
1036 | else if (is_gimple_debug (use_stmt)) |
1037 | continue; | |
32ace6e2 AM |
1038 | else |
1039 | { | |
1040 | /* If its not defined in this block, its live on entry. */ | |
726a989a | 1041 | basic_block use_bb = gimple_bb (use_stmt); |
32ace6e2 AM |
1042 | if (use_bb != def_bb) |
1043 | add_block = use_bb; | |
b8698a0f | 1044 | } |
32ace6e2 AM |
1045 | |
1046 | /* If there was a live on entry use, set the bit. */ | |
1047 | if (add_block) | |
1048 | { | |
1049 | global = true; | |
1050 | bitmap_set_bit (live->livein[add_block->index], p); | |
6de9cd9a DN |
1051 | } |
1052 | } | |
6de9cd9a | 1053 | |
32ace6e2 AM |
1054 | /* If SSA_NAME is live on entry to at least one block, fill in all the live |
1055 | on entry blocks between the def and all the uses. */ | |
1056 | if (global) | |
1057 | bitmap_set_bit (live->global, p); | |
6de9cd9a DN |
1058 | } |
1059 | ||
1060 | ||
1061 | /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */ | |
1062 | ||
1063 | void | |
1064 | calculate_live_on_exit (tree_live_info_p liveinfo) | |
1065 | { | |
6de9cd9a DN |
1066 | basic_block bb; |
1067 | edge e; | |
32ace6e2 | 1068 | edge_iterator ei; |
6de9cd9a | 1069 | |
7290d709 | 1070 | /* live on entry calculations used liveout vectors for defs, clear them. */ |
32ace6e2 AM |
1071 | FOR_EACH_BB (bb) |
1072 | bitmap_clear (liveinfo->liveout[bb->index]); | |
6de9cd9a DN |
1073 | |
1074 | /* Set all the live-on-exit bits for uses in PHIs. */ | |
1075 | FOR_EACH_BB (bb) | |
1076 | { | |
726a989a RB |
1077 | gimple_stmt_iterator gsi; |
1078 | size_t i; | |
1079 | ||
32ace6e2 | 1080 | /* Mark the PHI arguments which are live on exit to the pred block. */ |
726a989a RB |
1081 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
1082 | { | |
1083 | gimple phi = gsi_stmt (gsi); | |
1084 | for (i = 0; i < gimple_phi_num_args (phi); i++) | |
b8698a0f | 1085 | { |
726a989a RB |
1086 | tree t = PHI_ARG_DEF (phi, i); |
1087 | int p; | |
1088 | ||
1089 | if (TREE_CODE (t) != SSA_NAME) | |
1090 | continue; | |
1091 | ||
1092 | p = var_to_partition (liveinfo->map, t); | |
1093 | if (p == NO_PARTITION) | |
1094 | continue; | |
1095 | e = gimple_phi_arg_edge (phi, i); | |
1096 | if (e->src != ENTRY_BLOCK_PTR) | |
1097 | bitmap_set_bit (liveinfo->liveout[e->src->index], p); | |
1098 | } | |
1099 | } | |
32ace6e2 | 1100 | |
7290d709 | 1101 | /* Add each successors live on entry to this bock live on exit. */ |
32ace6e2 AM |
1102 | FOR_EACH_EDGE (e, ei, bb->succs) |
1103 | if (e->dest != EXIT_BLOCK_PTR) | |
1104 | bitmap_ior_into (liveinfo->liveout[bb->index], | |
1105 | live_on_entry (liveinfo, e->dest)); | |
6de9cd9a | 1106 | } |
32ace6e2 AM |
1107 | } |
1108 | ||
7290d709 | 1109 | |
b8698a0f | 1110 | /* Given partition map MAP, calculate all the live on entry bitmaps for |
32ace6e2 AM |
1111 | each partition. Return a new live info object. */ |
1112 | ||
b8698a0f | 1113 | tree_live_info_p |
32ace6e2 AM |
1114 | calculate_live_ranges (var_map map) |
1115 | { | |
1116 | tree var; | |
1117 | unsigned i; | |
1118 | tree_live_info_p live; | |
6de9cd9a | 1119 | |
32ace6e2 | 1120 | live = new_tree_live_info (map); |
6de9cd9a DN |
1121 | for (i = 0; i < num_var_partitions (map); i++) |
1122 | { | |
32ace6e2 AM |
1123 | var = partition_to_var (map, i); |
1124 | if (var != NULL_TREE) | |
1125 | set_var_live_on_entry (var, live); | |
6de9cd9a DN |
1126 | } |
1127 | ||
32ace6e2 AM |
1128 | live_worklist (live); |
1129 | ||
1130 | #ifdef ENABLE_CHECKING | |
1131 | verify_live_on_entry (live); | |
1132 | #endif | |
1133 | ||
1134 | calculate_live_on_exit (live); | |
1135 | return live; | |
6de9cd9a DN |
1136 | } |
1137 | ||
1138 | ||
6de9cd9a DN |
1139 | /* Output partition map MAP to file F. */ |
1140 | ||
1141 | void | |
1142 | dump_var_map (FILE *f, var_map map) | |
1143 | { | |
1144 | int t; | |
1145 | unsigned x, y; | |
1146 | int p; | |
1147 | ||
1148 | fprintf (f, "\nPartition map \n\n"); | |
1149 | ||
1150 | for (x = 0; x < map->num_partitions; x++) | |
1151 | { | |
7290d709 AM |
1152 | if (map->view_to_partition != NULL) |
1153 | p = map->view_to_partition[x]; | |
6de9cd9a DN |
1154 | else |
1155 | p = x; | |
1156 | ||
4e3825db | 1157 | if (ssa_name (p) == NULL_TREE) |
6de9cd9a DN |
1158 | continue; |
1159 | ||
1160 | t = 0; | |
95a3742c | 1161 | for (y = 1; y < num_ssa_names; y++) |
6de9cd9a DN |
1162 | { |
1163 | p = partition_find (map->var_partition, y); | |
7290d709 AM |
1164 | if (map->partition_to_view) |
1165 | p = map->partition_to_view[p]; | |
6de9cd9a DN |
1166 | if (p == (int)x) |
1167 | { | |
1168 | if (t++ == 0) | |
1169 | { | |
1170 | fprintf(f, "Partition %d (", x); | |
1171 | print_generic_expr (f, partition_to_var (map, p), TDF_SLIM); | |
1172 | fprintf (f, " - "); | |
1173 | } | |
1174 | fprintf (f, "%d ", y); | |
1175 | } | |
1176 | } | |
1177 | if (t != 0) | |
1178 | fprintf (f, ")\n"); | |
1179 | } | |
1180 | fprintf (f, "\n"); | |
1181 | } | |
1182 | ||
1183 | ||
1184 | /* Output live range info LIVE to file F, controlled by FLAG. */ | |
1185 | ||
1186 | void | |
1187 | dump_live_info (FILE *f, tree_live_info_p live, int flag) | |
1188 | { | |
1189 | basic_block bb; | |
3cd8c58a | 1190 | unsigned i; |
6de9cd9a | 1191 | var_map map = live->map; |
87c476a2 | 1192 | bitmap_iterator bi; |
6de9cd9a DN |
1193 | |
1194 | if ((flag & LIVEDUMP_ENTRY) && live->livein) | |
1195 | { | |
1196 | FOR_EACH_BB (bb) | |
1197 | { | |
1198 | fprintf (f, "\nLive on entry to BB%d : ", bb->index); | |
32ace6e2 | 1199 | EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi) |
6de9cd9a | 1200 | { |
32ace6e2 AM |
1201 | print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); |
1202 | fprintf (f, " "); | |
6de9cd9a DN |
1203 | } |
1204 | fprintf (f, "\n"); | |
1205 | } | |
1206 | } | |
1207 | ||
1208 | if ((flag & LIVEDUMP_EXIT) && live->liveout) | |
1209 | { | |
1210 | FOR_EACH_BB (bb) | |
1211 | { | |
1212 | fprintf (f, "\nLive on exit from BB%d : ", bb->index); | |
87c476a2 | 1213 | EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi) |
6de9cd9a DN |
1214 | { |
1215 | print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); | |
1216 | fprintf (f, " "); | |
87c476a2 | 1217 | } |
6de9cd9a DN |
1218 | fprintf (f, "\n"); |
1219 | } | |
1220 | } | |
1221 | } | |
1e128c5f GB |
1222 | |
1223 | #ifdef ENABLE_CHECKING | |
7290d709 AM |
1224 | /* Verify that SSA_VAR is a non-virtual SSA_NAME. */ |
1225 | ||
1e128c5f GB |
1226 | void |
1227 | register_ssa_partition_check (tree ssa_var) | |
1228 | { | |
1229 | gcc_assert (TREE_CODE (ssa_var) == SSA_NAME); | |
1230 | if (!is_gimple_reg (SSA_NAME_VAR (ssa_var))) | |
1231 | { | |
1232 | fprintf (stderr, "Illegally registering a virtual SSA name :"); | |
1233 | print_generic_expr (stderr, ssa_var, TDF_SLIM); | |
1234 | fprintf (stderr, " in the SSA->Normal phase.\n"); | |
1235 | internal_error ("SSA corruption"); | |
1236 | } | |
1237 | } | |
32ace6e2 AM |
1238 | |
1239 | ||
1240 | /* Verify that the info in LIVE matches the current cfg. */ | |
7290d709 | 1241 | |
32ace6e2 AM |
1242 | static void |
1243 | verify_live_on_entry (tree_live_info_p live) | |
1244 | { | |
1245 | unsigned i; | |
1246 | tree var; | |
726a989a | 1247 | gimple stmt; |
32ace6e2 AM |
1248 | basic_block bb; |
1249 | edge e; | |
1250 | int num; | |
1251 | edge_iterator ei; | |
1252 | var_map map = live->map; | |
1253 | ||
1254 | /* Check for live on entry partitions and report those with a DEF in | |
1255 | the program. This will typically mean an optimization has done | |
1256 | something wrong. */ | |
32ace6e2 AM |
1257 | bb = ENTRY_BLOCK_PTR; |
1258 | num = 0; | |
1259 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1260 | { | |
1261 | int entry_block = e->dest->index; | |
1262 | if (e->dest == EXIT_BLOCK_PTR) | |
1263 | continue; | |
1264 | for (i = 0; i < (unsigned)num_var_partitions (map); i++) | |
1265 | { | |
1266 | basic_block tmp; | |
1267 | tree d; | |
1268 | bitmap loe; | |
1269 | var = partition_to_var (map, i); | |
1270 | stmt = SSA_NAME_DEF_STMT (var); | |
726a989a | 1271 | tmp = gimple_bb (stmt); |
32244553 | 1272 | d = ssa_default_def (cfun, SSA_NAME_VAR (var)); |
32ace6e2 AM |
1273 | |
1274 | loe = live_on_entry (live, e->dest); | |
1275 | if (loe && bitmap_bit_p (loe, i)) | |
1276 | { | |
726a989a | 1277 | if (!gimple_nop_p (stmt)) |
32ace6e2 AM |
1278 | { |
1279 | num++; | |
1280 | print_generic_expr (stderr, var, TDF_SLIM); | |
1281 | fprintf (stderr, " is defined "); | |
1282 | if (tmp) | |
1283 | fprintf (stderr, " in BB%d, ", tmp->index); | |
1284 | fprintf (stderr, "by:\n"); | |
726a989a | 1285 | print_gimple_stmt (stderr, stmt, 0, TDF_SLIM); |
b8698a0f | 1286 | fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", |
32ace6e2 AM |
1287 | entry_block); |
1288 | fprintf (stderr, " So it appears to have multiple defs.\n"); | |
1289 | } | |
1290 | else | |
1291 | { | |
1292 | if (d != var) | |
1293 | { | |
1294 | num++; | |
1295 | print_generic_expr (stderr, var, TDF_SLIM); | |
726a989a RB |
1296 | fprintf (stderr, " is live-on-entry to BB%d ", |
1297 | entry_block); | |
32ace6e2 AM |
1298 | if (d) |
1299 | { | |
1300 | fprintf (stderr, " but is not the default def of "); | |
1301 | print_generic_expr (stderr, d, TDF_SLIM); | |
1302 | fprintf (stderr, "\n"); | |
1303 | } | |
1304 | else | |
1305 | fprintf (stderr, " and there is no default def.\n"); | |
1306 | } | |
1307 | } | |
1308 | } | |
1309 | else | |
1310 | if (d == var) | |
1311 | { | |
b8698a0f | 1312 | /* The only way this var shouldn't be marked live on entry is |
32ace6e2 | 1313 | if it occurs in a PHI argument of the block. */ |
726a989a RB |
1314 | size_t z; |
1315 | bool ok = false; | |
1316 | gimple_stmt_iterator gsi; | |
1317 | for (gsi = gsi_start_phis (e->dest); | |
1318 | !gsi_end_p (gsi) && !ok; | |
1319 | gsi_next (&gsi)) | |
32ace6e2 | 1320 | { |
726a989a RB |
1321 | gimple phi = gsi_stmt (gsi); |
1322 | for (z = 0; z < gimple_phi_num_args (phi); z++) | |
1323 | if (var == gimple_phi_arg_def (phi, z)) | |
32ace6e2 | 1324 | { |
726a989a | 1325 | ok = true; |
32ace6e2 AM |
1326 | break; |
1327 | } | |
1328 | } | |
1329 | if (ok) | |
1330 | continue; | |
1331 | num++; | |
1332 | print_generic_expr (stderr, var, TDF_SLIM); | |
b8698a0f | 1333 | fprintf (stderr, " is not marked live-on-entry to entry BB%d ", |
32ace6e2 AM |
1334 | entry_block); |
1335 | fprintf (stderr, "but it is a default def so it should be.\n"); | |
1336 | } | |
1337 | } | |
1338 | } | |
1339 | gcc_assert (num <= 0); | |
1340 | } | |
1e128c5f | 1341 | #endif |