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