* g++.dg/cpp0x/constexpr-53094-2.C: Ignore non-standard ABI
[official-gcc.git] / gcc / tree-ssa-live.c
blob9055d91ddb3da0fc17824f102f1d945b2ff0f929
1 /* Liveness for SSA trees.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "gimple-pretty-print.h"
27 #include "bitmap.h"
28 #include "tree-flow.h"
29 #include "timevar.h"
30 #include "dumpfile.h"
31 #include "tree-ssa-live.h"
32 #include "diagnostic-core.h"
33 #include "debug.h"
34 #include "flags.h"
35 #include "gimple.h"
37 #ifdef ENABLE_CHECKING
38 static void verify_live_on_entry (tree_live_info_p);
39 #endif
42 /* VARMAP maintains a mapping from SSA version number to real variables.
44 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
45 only member of it's own partition. Coalescing will attempt to group any
46 ssa_names which occur in a copy or in a PHI node into the same partition.
48 At the end of out-of-ssa, each partition becomes a "real" variable and is
49 rewritten as a compiler variable.
51 The var_map data structure is used to manage these partitions. It allows
52 partitions to be combined, and determines which partition belongs to what
53 ssa_name or variable, and vice versa. */
56 /* This routine will initialize the basevar fields of MAP. */
58 static void
59 var_map_base_init (var_map map)
61 int x, num_part;
62 tree var;
63 htab_t tree_to_index;
64 struct tree_int_map *m, *mapstorage;
66 num_part = num_var_partitions (map);
67 tree_to_index = htab_create (num_part, tree_map_base_hash,
68 tree_int_map_eq, NULL);
69 /* We can have at most num_part entries in the hash tables, so it's
70 enough to allocate so many map elements once, saving some malloc
71 calls. */
72 mapstorage = m = XNEWVEC (struct tree_int_map, num_part);
74 /* If a base table already exists, clear it, otherwise create it. */
75 free (map->partition_to_base_index);
76 map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
78 /* Build the base variable list, and point partitions at their bases. */
79 for (x = 0; x < num_part; x++)
81 struct tree_int_map **slot;
82 unsigned baseindex;
83 var = partition_to_var (map, x);
84 if (SSA_NAME_VAR (var))
85 m->base.from = SSA_NAME_VAR (var);
86 else
87 /* This restricts what anonymous SSA names we can coalesce
88 as it restricts the sets we compute conflicts for.
89 Using TREE_TYPE to generate sets is the easies as
90 type equivalency also holds for SSA names with the same
91 underlying decl. */
92 m->base.from = TREE_TYPE (var);
93 /* If base variable hasn't been seen, set it up. */
94 slot = (struct tree_int_map **) htab_find_slot (tree_to_index,
95 m, INSERT);
96 if (!*slot)
98 baseindex = m - mapstorage;
99 m->to = baseindex;
100 *slot = m;
101 m++;
103 else
104 baseindex = (*slot)->to;
105 map->partition_to_base_index[x] = baseindex;
108 map->num_basevars = m - mapstorage;
110 free (mapstorage);
111 htab_delete (tree_to_index);
115 /* Remove the base table in MAP. */
117 static void
118 var_map_base_fini (var_map map)
120 /* Free the basevar info if it is present. */
121 if (map->partition_to_base_index != NULL)
123 free (map->partition_to_base_index);
124 map->partition_to_base_index = NULL;
125 map->num_basevars = 0;
128 /* Create a variable partition map of SIZE, initialize and return it. */
130 var_map
131 init_var_map (int size)
133 var_map map;
135 map = (var_map) xmalloc (sizeof (struct _var_map));
136 map->var_partition = partition_new (size);
138 map->partition_to_view = NULL;
139 map->view_to_partition = NULL;
140 map->num_partitions = size;
141 map->partition_size = size;
142 map->num_basevars = 0;
143 map->partition_to_base_index = NULL;
144 return map;
148 /* Free memory associated with MAP. */
150 void
151 delete_var_map (var_map map)
153 var_map_base_fini (map);
154 partition_delete (map->var_partition);
155 free (map->partition_to_view);
156 free (map->view_to_partition);
157 free (map);
161 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
162 Returns the partition which represents the new partition. If the two
163 partitions cannot be combined, NO_PARTITION is returned. */
166 var_union (var_map map, tree var1, tree var2)
168 int p1, p2, p3;
170 gcc_assert (TREE_CODE (var1) == SSA_NAME);
171 gcc_assert (TREE_CODE (var2) == SSA_NAME);
173 /* This is independent of partition_to_view. If partition_to_view is
174 on, then whichever one of these partitions is absorbed will never have a
175 dereference into the partition_to_view array any more. */
177 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
178 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
180 gcc_assert (p1 != NO_PARTITION);
181 gcc_assert (p2 != NO_PARTITION);
183 if (p1 == p2)
184 p3 = p1;
185 else
186 p3 = partition_union (map->var_partition, p1, p2);
188 if (map->partition_to_view)
189 p3 = map->partition_to_view[p3];
191 return p3;
195 /* Compress the partition numbers in MAP such that they fall in the range
196 0..(num_partitions-1) instead of wherever they turned out during
197 the partitioning exercise. This removes any references to unused
198 partitions, thereby allowing bitmaps and other vectors to be much
199 denser.
201 This is implemented such that compaction doesn't affect partitioning.
202 Ie., once partitions are created and possibly merged, running one
203 or more different kind of compaction will not affect the partitions
204 themselves. Their index might change, but all the same variables will
205 still be members of the same partition group. This allows work on reduced
206 sets, and no loss of information when a larger set is later desired.
208 In particular, coalescing can work on partitions which have 2 or more
209 definitions, and then 'recompact' later to include all the single
210 definitions for assignment to program variables. */
213 /* Set MAP back to the initial state of having no partition view. Return a
214 bitmap which has a bit set for each partition number which is in use in the
215 varmap. */
217 static bitmap
218 partition_view_init (var_map map)
220 bitmap used;
221 int tmp;
222 unsigned int x;
224 used = BITMAP_ALLOC (NULL);
226 /* Already in a view? Abandon the old one. */
227 if (map->partition_to_view)
229 free (map->partition_to_view);
230 map->partition_to_view = NULL;
232 if (map->view_to_partition)
234 free (map->view_to_partition);
235 map->view_to_partition = NULL;
238 /* Find out which partitions are actually referenced. */
239 for (x = 0; x < map->partition_size; x++)
241 tmp = partition_find (map->var_partition, x);
242 if (ssa_name (tmp) != NULL_TREE && !virtual_operand_p (ssa_name (tmp))
243 && (!has_zero_uses (ssa_name (tmp))
244 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp))))
245 bitmap_set_bit (used, tmp);
248 map->num_partitions = map->partition_size;
249 return used;
253 /* This routine will finalize the view data for MAP based on the partitions
254 set in SELECTED. This is either the same bitmap returned from
255 partition_view_init, or a trimmed down version if some of those partitions
256 were not desired in this view. SELECTED is freed before returning. */
258 static void
259 partition_view_fini (var_map map, bitmap selected)
261 bitmap_iterator bi;
262 unsigned count, i, x, limit;
264 gcc_assert (selected);
266 count = bitmap_count_bits (selected);
267 limit = map->partition_size;
269 /* If its a one-to-one ratio, we don't need any view compaction. */
270 if (count < limit)
272 map->partition_to_view = (int *)xmalloc (limit * sizeof (int));
273 memset (map->partition_to_view, 0xff, (limit * sizeof (int)));
274 map->view_to_partition = (int *)xmalloc (count * sizeof (int));
276 i = 0;
277 /* Give each selected partition an index. */
278 EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)
280 map->partition_to_view[x] = i;
281 map->view_to_partition[i] = x;
282 i++;
284 gcc_assert (i == count);
285 map->num_partitions = i;
288 BITMAP_FREE (selected);
292 /* Create a partition view which includes all the used partitions in MAP. If
293 WANT_BASES is true, create the base variable map as well. */
295 void
296 partition_view_normal (var_map map, bool want_bases)
298 bitmap used;
300 used = partition_view_init (map);
301 partition_view_fini (map, used);
303 if (want_bases)
304 var_map_base_init (map);
305 else
306 var_map_base_fini (map);
310 /* Create a partition view in MAP which includes just partitions which occur in
311 the bitmap ONLY. If WANT_BASES is true, create the base variable map
312 as well. */
314 void
315 partition_view_bitmap (var_map map, bitmap only, bool want_bases)
317 bitmap used;
318 bitmap new_partitions = BITMAP_ALLOC (NULL);
319 unsigned x, p;
320 bitmap_iterator bi;
322 used = partition_view_init (map);
323 EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)
325 p = partition_find (map->var_partition, x);
326 gcc_assert (bitmap_bit_p (used, p));
327 bitmap_set_bit (new_partitions, p);
329 partition_view_fini (map, new_partitions);
331 if (want_bases)
332 var_map_base_init (map);
333 else
334 var_map_base_fini (map);
338 static bitmap usedvars;
340 /* Mark VAR as used, so that it'll be preserved during rtl expansion.
341 Returns true if VAR wasn't marked before. */
343 static inline bool
344 set_is_used (tree var)
346 return bitmap_set_bit (usedvars, DECL_UID (var));
349 /* Return true if VAR is marked as used. */
351 static inline bool
352 is_used_p (tree var)
354 return bitmap_bit_p (usedvars, DECL_UID (var));
357 static inline void mark_all_vars_used (tree *);
359 /* Helper function for mark_all_vars_used, called via walk_tree. */
361 static tree
362 mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
364 tree t = *tp;
365 enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));
366 tree b;
368 if (TREE_CODE (t) == SSA_NAME)
370 *walk_subtrees = 0;
371 t = SSA_NAME_VAR (t);
372 if (!t)
373 return NULL;
376 if (IS_EXPR_CODE_CLASS (c)
377 && (b = TREE_BLOCK (t)) != NULL)
378 TREE_USED (b) = true;
380 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
381 fields do not contain vars. */
382 if (TREE_CODE (t) == TARGET_MEM_REF)
384 mark_all_vars_used (&TMR_BASE (t));
385 mark_all_vars_used (&TMR_INDEX (t));
386 mark_all_vars_used (&TMR_INDEX2 (t));
387 *walk_subtrees = 0;
388 return NULL;
391 /* Only need to mark VAR_DECLS; parameters and return results are not
392 eliminated as unused. */
393 if (TREE_CODE (t) == VAR_DECL)
395 /* When a global var becomes used for the first time also walk its
396 initializer (non global ones don't have any). */
397 if (set_is_used (t) && is_global_var (t))
398 mark_all_vars_used (&DECL_INITIAL (t));
400 /* remove_unused_scope_block_p requires information about labels
401 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
402 else if (TREE_CODE (t) == LABEL_DECL)
403 /* Although the TREE_USED values that the frontend uses would be
404 acceptable (albeit slightly over-conservative) for our purposes,
405 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
406 must re-compute it here. */
407 TREE_USED (t) = 1;
409 if (IS_TYPE_OR_DECL_P (t))
410 *walk_subtrees = 0;
412 return NULL;
415 /* Mark the scope block SCOPE and its subblocks unused when they can be
416 possibly eliminated if dead. */
418 static void
419 mark_scope_block_unused (tree scope)
421 tree t;
422 TREE_USED (scope) = false;
423 if (!(*debug_hooks->ignore_block) (scope))
424 TREE_USED (scope) = true;
425 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
426 mark_scope_block_unused (t);
429 /* Look if the block is dead (by possibly eliminating its dead subblocks)
430 and return true if so.
431 Block is declared dead if:
432 1) No statements are associated with it.
433 2) Declares no live variables
434 3) All subblocks are dead
435 or there is precisely one subblocks and the block
436 has same abstract origin as outer block and declares
437 no variables, so it is pure wrapper.
438 When we are not outputting full debug info, we also eliminate dead variables
439 out of scope blocks to let them to be recycled by GGC and to save copying work
440 done by the inliner. */
442 static bool
443 remove_unused_scope_block_p (tree scope)
445 tree *t, *next;
446 bool unused = !TREE_USED (scope);
447 int nsubblocks = 0;
449 for (t = &BLOCK_VARS (scope); *t; t = next)
451 next = &DECL_CHAIN (*t);
453 /* Debug info of nested function refers to the block of the
454 function. We might stil call it even if all statements
455 of function it was nested into was elliminated.
457 TODO: We can actually look into cgraph to see if function
458 will be output to file. */
459 if (TREE_CODE (*t) == FUNCTION_DECL)
460 unused = false;
462 /* If a decl has a value expr, we need to instantiate it
463 regardless of debug info generation, to avoid codegen
464 differences in memory overlap tests. update_equiv_regs() may
465 indirectly call validate_equiv_mem() to test whether a
466 SET_DEST overlaps with others, and if the value expr changes
467 by virtual register instantiation, we may get end up with
468 different results. */
469 else if (TREE_CODE (*t) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*t))
470 unused = false;
472 /* Remove everything we don't generate debug info for. */
473 else if (DECL_IGNORED_P (*t))
475 *t = DECL_CHAIN (*t);
476 next = t;
479 /* When we are outputting debug info, we usually want to output
480 info about optimized-out variables in the scope blocks.
481 Exception are the scope blocks not containing any instructions
482 at all so user can't get into the scopes at first place. */
483 else if (is_used_p (*t))
484 unused = false;
485 else if (TREE_CODE (*t) == LABEL_DECL && TREE_USED (*t))
486 /* For labels that are still used in the IL, the decision to
487 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
488 risk having different ordering in debug vs. non-debug builds
489 during inlining or versioning.
490 A label appearing here (we have already checked DECL_IGNORED_P)
491 should not be used in the IL unless it has been explicitly used
492 before, so we use TREE_USED as an approximation. */
493 /* In principle, we should do the same here as for the debug case
494 below, however, when debugging, there might be additional nested
495 levels that keep an upper level with a label live, so we have to
496 force this block to be considered used, too. */
497 unused = false;
499 /* When we are not doing full debug info, we however can keep around
500 only the used variables for cfgexpand's memory packing saving quite
501 a lot of memory.
503 For sake of -g3, we keep around those vars but we don't count this as
504 use of block, so innermost block with no used vars and no instructions
505 can be considered dead. We only want to keep around blocks user can
506 breakpoint into and ask about value of optimized out variables.
508 Similarly we need to keep around types at least until all
509 variables of all nested blocks are gone. We track no
510 information on whether given type is used or not, so we have
511 to keep them even when not emitting debug information,
512 otherwise we may end up remapping variables and their (local)
513 types in different orders depending on whether debug
514 information is being generated. */
516 else if (TREE_CODE (*t) == TYPE_DECL
517 || debug_info_level == DINFO_LEVEL_NORMAL
518 || debug_info_level == DINFO_LEVEL_VERBOSE)
520 else
522 *t = DECL_CHAIN (*t);
523 next = t;
527 for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
528 if (remove_unused_scope_block_p (*t))
530 if (BLOCK_SUBBLOCKS (*t))
532 tree next = BLOCK_CHAIN (*t);
533 tree supercontext = BLOCK_SUPERCONTEXT (*t);
535 *t = BLOCK_SUBBLOCKS (*t);
536 while (BLOCK_CHAIN (*t))
538 BLOCK_SUPERCONTEXT (*t) = supercontext;
539 t = &BLOCK_CHAIN (*t);
541 BLOCK_CHAIN (*t) = next;
542 BLOCK_SUPERCONTEXT (*t) = supercontext;
543 t = &BLOCK_CHAIN (*t);
544 nsubblocks ++;
546 else
547 *t = BLOCK_CHAIN (*t);
549 else
551 t = &BLOCK_CHAIN (*t);
552 nsubblocks ++;
556 if (!unused)
558 /* Outer scope is always used. */
559 else if (!BLOCK_SUPERCONTEXT (scope)
560 || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)
561 unused = false;
562 /* Innermost blocks with no live variables nor statements can be always
563 eliminated. */
564 else if (!nsubblocks)
566 /* For terse debug info we can eliminate info on unused variables. */
567 else if (debug_info_level == DINFO_LEVEL_NONE
568 || debug_info_level == DINFO_LEVEL_TERSE)
570 /* Even for -g0/-g1 don't prune outer scopes from artificial
571 functions, otherwise diagnostics using tree_nonartificial_location
572 will not be emitted properly. */
573 if (inlined_function_outer_scope_p (scope))
575 tree ao = scope;
577 while (ao
578 && TREE_CODE (ao) == BLOCK
579 && BLOCK_ABSTRACT_ORIGIN (ao) != ao)
580 ao = BLOCK_ABSTRACT_ORIGIN (ao);
581 if (ao
582 && TREE_CODE (ao) == FUNCTION_DECL
583 && DECL_DECLARED_INLINE_P (ao)
584 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao)))
585 unused = false;
588 else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope))
589 unused = false;
590 /* See if this block is important for representation of inlined function.
591 Inlined functions are always represented by block with
592 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
593 set... */
594 else if (inlined_function_outer_scope_p (scope))
595 unused = false;
596 else
597 /* Verfify that only blocks with source location set
598 are entry points to the inlined functions. */
599 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope))
600 == UNKNOWN_LOCATION);
602 TREE_USED (scope) = !unused;
603 return unused;
606 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
607 eliminated during the tree->rtl conversion process. */
609 static inline void
610 mark_all_vars_used (tree *expr_p)
612 walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
615 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
617 static tree
618 clear_unused_block_pointer_1 (tree *tp, int *, void *)
620 if (EXPR_P (*tp) && TREE_BLOCK (*tp)
621 && !TREE_USED (TREE_BLOCK (*tp)))
622 TREE_SET_BLOCK (*tp, NULL);
623 if (TREE_CODE (*tp) == VAR_DECL && DECL_DEBUG_EXPR_IS_FROM (*tp))
625 tree debug_expr = DECL_DEBUG_EXPR (*tp);
626 walk_tree (&debug_expr, clear_unused_block_pointer_1, NULL, NULL);
628 return NULL_TREE;
631 /* Set all block pointer in debug stmt to NULL if the block is unused,
632 so that they will not be streamed out. */
634 static void
635 clear_unused_block_pointer (void)
637 basic_block bb;
638 gimple_stmt_iterator gsi;
639 tree t;
640 unsigned i;
642 FOR_EACH_LOCAL_DECL (cfun, i, t)
643 if (TREE_CODE (t) == VAR_DECL && DECL_DEBUG_EXPR_IS_FROM (t))
645 tree debug_expr = DECL_DEBUG_EXPR (t);
646 walk_tree (&debug_expr, clear_unused_block_pointer_1, NULL, NULL);
649 FOR_EACH_BB (bb)
650 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
652 unsigned i;
653 tree b;
654 gimple stmt = gsi_stmt (gsi);
656 if (!is_gimple_debug (stmt))
657 continue;
658 b = gimple_block (stmt);
659 if (b && !TREE_USED (b))
660 gimple_set_block (stmt, NULL);
661 for (i = 0; i < gimple_num_ops (stmt); i++)
662 walk_tree (gimple_op_ptr (stmt, i), clear_unused_block_pointer_1,
663 NULL, NULL);
667 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
668 indentation level and FLAGS is as in print_generic_expr. */
670 static void
671 dump_scope_block (FILE *file, int indent, tree scope, int flags)
673 tree var, t;
674 unsigned int i;
676 fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope),
677 TREE_USED (scope) ? "" : " (unused)",
678 BLOCK_ABSTRACT (scope) ? " (abstract)": "");
679 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope)) != UNKNOWN_LOCATION)
681 expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope));
682 fprintf (file, " %s:%i", s.file, s.line);
684 if (BLOCK_ABSTRACT_ORIGIN (scope))
686 tree origin = block_ultimate_origin (scope);
687 if (origin)
689 fprintf (file, " Originating from :");
690 if (DECL_P (origin))
691 print_generic_decl (file, origin, flags);
692 else
693 fprintf (file, "#%i", BLOCK_NUMBER (origin));
696 fprintf (file, " \n");
697 for (var = BLOCK_VARS (scope); var; var = DECL_CHAIN (var))
699 fprintf (file, "%*s", indent, "");
700 print_generic_decl (file, var, flags);
701 fprintf (file, "\n");
703 for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++)
705 fprintf (file, "%*s",indent, "");
706 print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i),
707 flags);
708 fprintf (file, " (nonlocalized)\n");
710 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
711 dump_scope_block (file, indent + 2, t, flags);
712 fprintf (file, "\n%*s}\n",indent, "");
715 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
716 is as in print_generic_expr. */
718 DEBUG_FUNCTION void
719 debug_scope_block (tree scope, int flags)
721 dump_scope_block (stderr, 0, scope, flags);
725 /* Dump the tree of lexical scopes of current_function_decl to FILE.
726 FLAGS is as in print_generic_expr. */
728 void
729 dump_scope_blocks (FILE *file, int flags)
731 dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags);
735 /* Dump the tree of lexical scopes of current_function_decl to stderr.
736 FLAGS is as in print_generic_expr. */
738 DEBUG_FUNCTION void
739 debug_scope_blocks (int flags)
741 dump_scope_blocks (stderr, flags);
744 /* Remove local variables that are not referenced in the IL. */
746 void
747 remove_unused_locals (void)
749 basic_block bb;
750 tree var;
751 unsigned srcidx, dstidx, num;
752 bool have_local_clobbers = false;
754 /* Removing declarations from lexical blocks when not optimizing is
755 not only a waste of time, it actually causes differences in stack
756 layout. */
757 if (!optimize)
758 return;
760 timevar_push (TV_REMOVE_UNUSED);
762 mark_scope_block_unused (DECL_INITIAL (current_function_decl));
764 usedvars = BITMAP_ALLOC (NULL);
766 /* Walk the CFG marking all referenced symbols. */
767 FOR_EACH_BB (bb)
769 gimple_stmt_iterator gsi;
770 size_t i;
771 edge_iterator ei;
772 edge e;
774 /* Walk the statements. */
775 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
777 gimple stmt = gsi_stmt (gsi);
778 tree b = gimple_block (stmt);
780 if (is_gimple_debug (stmt))
781 continue;
783 if (gimple_clobber_p (stmt))
785 have_local_clobbers = true;
786 continue;
789 if (b)
790 TREE_USED (b) = true;
792 for (i = 0; i < gimple_num_ops (stmt); i++)
793 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i));
796 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
798 use_operand_p arg_p;
799 ssa_op_iter i;
800 tree def;
801 gimple phi = gsi_stmt (gsi);
803 if (virtual_operand_p (gimple_phi_result (phi)))
804 continue;
806 def = gimple_phi_result (phi);
807 mark_all_vars_used (&def);
809 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
811 tree arg = USE_FROM_PTR (arg_p);
812 int index = PHI_ARG_INDEX_FROM_USE (arg_p);
813 tree block =
814 LOCATION_BLOCK (gimple_phi_arg_location (phi, index));
815 if (block != NULL)
816 TREE_USED (block) = true;
817 mark_all_vars_used (&arg);
821 FOR_EACH_EDGE (e, ei, bb->succs)
822 if (LOCATION_BLOCK (e->goto_locus) != NULL)
823 TREE_USED (LOCATION_BLOCK (e->goto_locus)) = true;
826 /* We do a two-pass approach about the out-of-scope clobbers. We want
827 to remove them if they are the only references to a local variable,
828 but we want to retain them when there's any other. So the first pass
829 ignores them, and the second pass (if there were any) tries to remove
830 them. */
831 if (have_local_clobbers)
832 FOR_EACH_BB (bb)
834 gimple_stmt_iterator gsi;
836 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
838 gimple stmt = gsi_stmt (gsi);
839 tree b = gimple_block (stmt);
841 if (gimple_clobber_p (stmt))
843 tree lhs = gimple_assign_lhs (stmt);
844 if (TREE_CODE (lhs) == VAR_DECL && !is_used_p (lhs))
846 unlink_stmt_vdef (stmt);
847 gsi_remove (&gsi, true);
848 release_defs (stmt);
849 continue;
851 if (b)
852 TREE_USED (b) = true;
854 gsi_next (&gsi);
858 cfun->has_local_explicit_reg_vars = false;
860 /* Remove unmarked local and global vars from local_decls. */
861 num = vec_safe_length (cfun->local_decls);
862 for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++)
864 var = (*cfun->local_decls)[srcidx];
865 if (TREE_CODE (var) == VAR_DECL)
867 if (!is_used_p (var))
869 tree def;
870 if (cfun->nonlocal_goto_save_area
871 && TREE_OPERAND (cfun->nonlocal_goto_save_area, 0) == var)
872 cfun->nonlocal_goto_save_area = NULL;
873 /* Release any default def associated with var. */
874 if ((def = ssa_default_def (cfun, var)) != NULL_TREE)
876 set_ssa_default_def (cfun, var, NULL_TREE);
877 release_ssa_name (def);
879 continue;
882 if (TREE_CODE (var) == VAR_DECL
883 && DECL_HARD_REGISTER (var)
884 && !is_global_var (var))
885 cfun->has_local_explicit_reg_vars = true;
887 if (srcidx != dstidx)
888 (*cfun->local_decls)[dstidx] = var;
889 dstidx++;
891 if (dstidx != num)
892 cfun->local_decls->truncate (dstidx);
894 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl));
895 clear_unused_block_pointer ();
897 BITMAP_FREE (usedvars);
899 if (dump_file && (dump_flags & TDF_DETAILS))
901 fprintf (dump_file, "Scope blocks after cleanups:\n");
902 dump_scope_blocks (dump_file, dump_flags);
905 timevar_pop (TV_REMOVE_UNUSED);
908 /* Obstack for globale liveness info bitmaps. We don't want to put these
909 on the default obstack because these bitmaps can grow quite large and
910 we'll hold on to all that memory until the end of the compiler run.
911 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
912 releasing the whole obstack. */
913 static bitmap_obstack liveness_bitmap_obstack;
915 /* Allocate and return a new live range information object base on MAP. */
917 static tree_live_info_p
918 new_tree_live_info (var_map map)
920 tree_live_info_p live;
921 basic_block bb;
923 live = XNEW (struct tree_live_info_d);
924 live->map = map;
925 live->num_blocks = last_basic_block;
927 live->livein = XNEWVEC (bitmap_head, last_basic_block);
928 FOR_EACH_BB (bb)
929 bitmap_initialize (&live->livein[bb->index], &liveness_bitmap_obstack);
931 live->liveout = XNEWVEC (bitmap_head, last_basic_block);
932 FOR_EACH_BB (bb)
933 bitmap_initialize (&live->liveout[bb->index], &liveness_bitmap_obstack);
935 live->work_stack = XNEWVEC (int, last_basic_block);
936 live->stack_top = live->work_stack;
938 live->global = BITMAP_ALLOC (&liveness_bitmap_obstack);
939 return live;
943 /* Free storage for live range info object LIVE. */
945 void
946 delete_tree_live_info (tree_live_info_p live)
948 bitmap_obstack_release (&liveness_bitmap_obstack);
949 free (live->work_stack);
950 free (live->liveout);
951 free (live->livein);
952 free (live);
956 /* Visit basic block BB and propagate any required live on entry bits from
957 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
958 TMP is a temporary work bitmap which is passed in to avoid reallocating
959 it each time. */
961 static void
962 loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
963 bitmap tmp)
965 edge e;
966 bool change;
967 edge_iterator ei;
968 basic_block pred_bb;
969 bitmap loe;
970 gcc_assert (!bitmap_bit_p (visited, bb->index));
972 bitmap_set_bit (visited, bb->index);
973 loe = live_on_entry (live, bb);
975 FOR_EACH_EDGE (e, ei, bb->preds)
977 pred_bb = e->src;
978 if (pred_bb == ENTRY_BLOCK_PTR)
979 continue;
980 /* TMP is variables live-on-entry from BB that aren't defined in the
981 predecessor block. This should be the live on entry vars to pred.
982 Note that liveout is the DEFs in a block while live on entry is
983 being calculated. */
984 bitmap_and_compl (tmp, loe, &live->liveout[pred_bb->index]);
986 /* Add these bits to live-on-entry for the pred. if there are any
987 changes, and pred_bb has been visited already, add it to the
988 revisit stack. */
989 change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
990 if (bitmap_bit_p (visited, pred_bb->index) && change)
992 bitmap_clear_bit (visited, pred_bb->index);
993 *(live->stack_top)++ = pred_bb->index;
999 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
1000 of all the variables. */
1002 static void
1003 live_worklist (tree_live_info_p live)
1005 unsigned b;
1006 basic_block bb;
1007 sbitmap visited = sbitmap_alloc (last_basic_block + 1);
1008 bitmap tmp = BITMAP_ALLOC (&liveness_bitmap_obstack);
1010 bitmap_clear (visited);
1012 /* Visit all the blocks in reverse order and propagate live on entry values
1013 into the predecessors blocks. */
1014 FOR_EACH_BB_REVERSE (bb)
1015 loe_visit_block (live, bb, visited, tmp);
1017 /* Process any blocks which require further iteration. */
1018 while (live->stack_top != live->work_stack)
1020 b = *--(live->stack_top);
1021 loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
1024 BITMAP_FREE (tmp);
1025 sbitmap_free (visited);
1029 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1030 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1031 in the liveout vector. */
1033 static void
1034 set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
1036 int p;
1037 gimple stmt;
1038 use_operand_p use;
1039 basic_block def_bb = NULL;
1040 imm_use_iterator imm_iter;
1041 bool global = false;
1043 p = var_to_partition (live->map, ssa_name);
1044 if (p == NO_PARTITION)
1045 return;
1047 stmt = SSA_NAME_DEF_STMT (ssa_name);
1048 if (stmt)
1050 def_bb = gimple_bb (stmt);
1051 /* Mark defs in liveout bitmap temporarily. */
1052 if (def_bb)
1053 bitmap_set_bit (&live->liveout[def_bb->index], p);
1055 else
1056 def_bb = ENTRY_BLOCK_PTR;
1058 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1059 add it to the list of live on entry blocks. */
1060 FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
1062 gimple use_stmt = USE_STMT (use);
1063 basic_block add_block = NULL;
1065 if (gimple_code (use_stmt) == GIMPLE_PHI)
1067 /* Uses in PHI's are considered to be live at exit of the SRC block
1068 as this is where a copy would be inserted. Check to see if it is
1069 defined in that block, or whether its live on entry. */
1070 int index = PHI_ARG_INDEX_FROM_USE (use);
1071 edge e = gimple_phi_arg_edge (use_stmt, index);
1072 if (e->src != ENTRY_BLOCK_PTR)
1074 if (e->src != def_bb)
1075 add_block = e->src;
1078 else if (is_gimple_debug (use_stmt))
1079 continue;
1080 else
1082 /* If its not defined in this block, its live on entry. */
1083 basic_block use_bb = gimple_bb (use_stmt);
1084 if (use_bb != def_bb)
1085 add_block = use_bb;
1088 /* If there was a live on entry use, set the bit. */
1089 if (add_block)
1091 global = true;
1092 bitmap_set_bit (&live->livein[add_block->index], p);
1096 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1097 on entry blocks between the def and all the uses. */
1098 if (global)
1099 bitmap_set_bit (live->global, p);
1103 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1105 void
1106 calculate_live_on_exit (tree_live_info_p liveinfo)
1108 basic_block bb;
1109 edge e;
1110 edge_iterator ei;
1112 /* live on entry calculations used liveout vectors for defs, clear them. */
1113 FOR_EACH_BB (bb)
1114 bitmap_clear (&liveinfo->liveout[bb->index]);
1116 /* Set all the live-on-exit bits for uses in PHIs. */
1117 FOR_EACH_BB (bb)
1119 gimple_stmt_iterator gsi;
1120 size_t i;
1122 /* Mark the PHI arguments which are live on exit to the pred block. */
1123 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1125 gimple phi = gsi_stmt (gsi);
1126 for (i = 0; i < gimple_phi_num_args (phi); i++)
1128 tree t = PHI_ARG_DEF (phi, i);
1129 int p;
1131 if (TREE_CODE (t) != SSA_NAME)
1132 continue;
1134 p = var_to_partition (liveinfo->map, t);
1135 if (p == NO_PARTITION)
1136 continue;
1137 e = gimple_phi_arg_edge (phi, i);
1138 if (e->src != ENTRY_BLOCK_PTR)
1139 bitmap_set_bit (&liveinfo->liveout[e->src->index], p);
1143 /* Add each successors live on entry to this bock live on exit. */
1144 FOR_EACH_EDGE (e, ei, bb->succs)
1145 if (e->dest != EXIT_BLOCK_PTR)
1146 bitmap_ior_into (&liveinfo->liveout[bb->index],
1147 live_on_entry (liveinfo, e->dest));
1152 /* Given partition map MAP, calculate all the live on entry bitmaps for
1153 each partition. Return a new live info object. */
1155 tree_live_info_p
1156 calculate_live_ranges (var_map map)
1158 tree var;
1159 unsigned i;
1160 tree_live_info_p live;
1162 bitmap_obstack_initialize (&liveness_bitmap_obstack);
1163 live = new_tree_live_info (map);
1164 for (i = 0; i < num_var_partitions (map); i++)
1166 var = partition_to_var (map, i);
1167 if (var != NULL_TREE)
1168 set_var_live_on_entry (var, live);
1171 live_worklist (live);
1173 #ifdef ENABLE_CHECKING
1174 verify_live_on_entry (live);
1175 #endif
1177 calculate_live_on_exit (live);
1178 return live;
1182 /* Output partition map MAP to file F. */
1184 void
1185 dump_var_map (FILE *f, var_map map)
1187 int t;
1188 unsigned x, y;
1189 int p;
1191 fprintf (f, "\nPartition map \n\n");
1193 for (x = 0; x < map->num_partitions; x++)
1195 if (map->view_to_partition != NULL)
1196 p = map->view_to_partition[x];
1197 else
1198 p = x;
1200 if (ssa_name (p) == NULL_TREE
1201 || virtual_operand_p (ssa_name (p)))
1202 continue;
1204 t = 0;
1205 for (y = 1; y < num_ssa_names; y++)
1207 p = partition_find (map->var_partition, y);
1208 if (map->partition_to_view)
1209 p = map->partition_to_view[p];
1210 if (p == (int)x)
1212 if (t++ == 0)
1214 fprintf(f, "Partition %d (", x);
1215 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1216 fprintf (f, " - ");
1218 fprintf (f, "%d ", y);
1221 if (t != 0)
1222 fprintf (f, ")\n");
1224 fprintf (f, "\n");
1228 /* Output live range info LIVE to file F, controlled by FLAG. */
1230 void
1231 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1233 basic_block bb;
1234 unsigned i;
1235 var_map map = live->map;
1236 bitmap_iterator bi;
1238 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1240 FOR_EACH_BB (bb)
1242 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1243 EXECUTE_IF_SET_IN_BITMAP (&live->livein[bb->index], 0, i, bi)
1245 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1246 fprintf (f, " ");
1248 fprintf (f, "\n");
1252 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1254 FOR_EACH_BB (bb)
1256 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1257 EXECUTE_IF_SET_IN_BITMAP (&live->liveout[bb->index], 0, i, bi)
1259 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1260 fprintf (f, " ");
1262 fprintf (f, "\n");
1267 #ifdef ENABLE_CHECKING
1268 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1270 void
1271 register_ssa_partition_check (tree ssa_var)
1273 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1274 if (virtual_operand_p (ssa_var))
1276 fprintf (stderr, "Illegally registering a virtual SSA name :");
1277 print_generic_expr (stderr, ssa_var, TDF_SLIM);
1278 fprintf (stderr, " in the SSA->Normal phase.\n");
1279 internal_error ("SSA corruption");
1284 /* Verify that the info in LIVE matches the current cfg. */
1286 static void
1287 verify_live_on_entry (tree_live_info_p live)
1289 unsigned i;
1290 tree var;
1291 gimple stmt;
1292 basic_block bb;
1293 edge e;
1294 int num;
1295 edge_iterator ei;
1296 var_map map = live->map;
1298 /* Check for live on entry partitions and report those with a DEF in
1299 the program. This will typically mean an optimization has done
1300 something wrong. */
1301 bb = ENTRY_BLOCK_PTR;
1302 num = 0;
1303 FOR_EACH_EDGE (e, ei, bb->succs)
1305 int entry_block = e->dest->index;
1306 if (e->dest == EXIT_BLOCK_PTR)
1307 continue;
1308 for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1310 basic_block tmp;
1311 tree d = NULL_TREE;
1312 bitmap loe;
1313 var = partition_to_var (map, i);
1314 stmt = SSA_NAME_DEF_STMT (var);
1315 tmp = gimple_bb (stmt);
1316 if (SSA_NAME_VAR (var))
1317 d = ssa_default_def (cfun, SSA_NAME_VAR (var));
1319 loe = live_on_entry (live, e->dest);
1320 if (loe && bitmap_bit_p (loe, i))
1322 if (!gimple_nop_p (stmt))
1324 num++;
1325 print_generic_expr (stderr, var, TDF_SLIM);
1326 fprintf (stderr, " is defined ");
1327 if (tmp)
1328 fprintf (stderr, " in BB%d, ", tmp->index);
1329 fprintf (stderr, "by:\n");
1330 print_gimple_stmt (stderr, stmt, 0, TDF_SLIM);
1331 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1332 entry_block);
1333 fprintf (stderr, " So it appears to have multiple defs.\n");
1335 else
1337 if (d != var)
1339 num++;
1340 print_generic_expr (stderr, var, TDF_SLIM);
1341 fprintf (stderr, " is live-on-entry to BB%d ",
1342 entry_block);
1343 if (d)
1345 fprintf (stderr, " but is not the default def of ");
1346 print_generic_expr (stderr, d, TDF_SLIM);
1347 fprintf (stderr, "\n");
1349 else
1350 fprintf (stderr, " and there is no default def.\n");
1354 else
1355 if (d == var)
1357 /* The only way this var shouldn't be marked live on entry is
1358 if it occurs in a PHI argument of the block. */
1359 size_t z;
1360 bool ok = false;
1361 gimple_stmt_iterator gsi;
1362 for (gsi = gsi_start_phis (e->dest);
1363 !gsi_end_p (gsi) && !ok;
1364 gsi_next (&gsi))
1366 gimple phi = gsi_stmt (gsi);
1367 for (z = 0; z < gimple_phi_num_args (phi); z++)
1368 if (var == gimple_phi_arg_def (phi, z))
1370 ok = true;
1371 break;
1374 if (ok)
1375 continue;
1376 num++;
1377 print_generic_expr (stderr, var, TDF_SLIM);
1378 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1379 entry_block);
1380 fprintf (stderr, "but it is a default def so it should be.\n");
1384 gcc_assert (num <= 0);
1386 #endif