1 /* Liveness for SSA trees.
2 Copyright (C) 2003-2015 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)
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/>. */
23 #include "coretypes.h"
24 #include "hash-table.h"
29 #include "double-int.h"
36 #include "fold-const.h"
37 #include "gimple-pretty-print.h"
41 #include "hard-reg-set.h"
43 #include "dominance.h"
45 #include "basic-block.h"
46 #include "tree-ssa-alias.h"
47 #include "internal-fn.h"
48 #include "gimple-expr.h"
51 #include "gimple-iterator.h"
52 #include "gimple-ssa.h"
53 #include "tree-phinodes.h"
54 #include "ssa-iterators.h"
55 #include "stringpool.h"
56 #include "tree-ssanames.h"
60 #include "statistics.h"
62 #include "fixed-value.h"
63 #include "insn-config.h"
75 #include "tree-ssa-live.h"
76 #include "diagnostic-core.h"
79 #include "lto-streamer.h"
82 #include "ipa-utils.h"
84 #ifdef ENABLE_CHECKING
85 static void verify_live_on_entry (tree_live_info_p
);
89 /* VARMAP maintains a mapping from SSA version number to real variables.
91 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
92 only member of it's own partition. Coalescing will attempt to group any
93 ssa_names which occur in a copy or in a PHI node into the same partition.
95 At the end of out-of-ssa, each partition becomes a "real" variable and is
96 rewritten as a compiler variable.
98 The var_map data structure is used to manage these partitions. It allows
99 partitions to be combined, and determines which partition belongs to what
100 ssa_name or variable, and vice versa. */
103 /* Hashtable helpers. */
105 struct tree_int_map_hasher
: typed_noop_remove
<tree_int_map
>
107 typedef tree_int_map value_type
;
108 typedef tree_int_map compare_type
;
109 static inline hashval_t
hash (const value_type
*);
110 static inline bool equal (const value_type
*, const compare_type
*);
114 tree_int_map_hasher::hash (const value_type
*v
)
116 return tree_map_base_hash (v
);
120 tree_int_map_hasher::equal (const value_type
*v
, const compare_type
*c
)
122 return tree_int_map_eq (v
, c
);
126 /* This routine will initialize the basevar fields of MAP. */
129 var_map_base_init (var_map map
)
133 struct tree_int_map
*m
, *mapstorage
;
135 num_part
= num_var_partitions (map
);
136 hash_table
<tree_int_map_hasher
> tree_to_index (num_part
);
137 /* We can have at most num_part entries in the hash tables, so it's
138 enough to allocate so many map elements once, saving some malloc
140 mapstorage
= m
= XNEWVEC (struct tree_int_map
, num_part
);
142 /* If a base table already exists, clear it, otherwise create it. */
143 free (map
->partition_to_base_index
);
144 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
146 /* Build the base variable list, and point partitions at their bases. */
147 for (x
= 0; x
< num_part
; x
++)
149 struct tree_int_map
**slot
;
151 var
= partition_to_var (map
, x
);
152 if (SSA_NAME_VAR (var
)
153 && (!VAR_P (SSA_NAME_VAR (var
))
154 || !DECL_IGNORED_P (SSA_NAME_VAR (var
))))
155 m
->base
.from
= SSA_NAME_VAR (var
);
157 /* This restricts what anonymous SSA names we can coalesce
158 as it restricts the sets we compute conflicts for.
159 Using TREE_TYPE to generate sets is the easies as
160 type equivalency also holds for SSA names with the same
163 Check gimple_can_coalesce_p when changing this code. */
164 m
->base
.from
= (TYPE_CANONICAL (TREE_TYPE (var
))
165 ? TYPE_CANONICAL (TREE_TYPE (var
))
167 /* If base variable hasn't been seen, set it up. */
168 slot
= tree_to_index
.find_slot (m
, INSERT
);
171 baseindex
= m
- mapstorage
;
177 baseindex
= (*slot
)->to
;
178 map
->partition_to_base_index
[x
] = baseindex
;
181 map
->num_basevars
= m
- mapstorage
;
187 /* Remove the base table in MAP. */
190 var_map_base_fini (var_map map
)
192 /* Free the basevar info if it is present. */
193 if (map
->partition_to_base_index
!= NULL
)
195 free (map
->partition_to_base_index
);
196 map
->partition_to_base_index
= NULL
;
197 map
->num_basevars
= 0;
200 /* Create a variable partition map of SIZE, initialize and return it. */
203 init_var_map (int size
)
207 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
208 map
->var_partition
= partition_new (size
);
210 map
->partition_to_view
= NULL
;
211 map
->view_to_partition
= NULL
;
212 map
->num_partitions
= size
;
213 map
->partition_size
= size
;
214 map
->num_basevars
= 0;
215 map
->partition_to_base_index
= NULL
;
220 /* Free memory associated with MAP. */
223 delete_var_map (var_map map
)
225 var_map_base_fini (map
);
226 partition_delete (map
->var_partition
);
227 free (map
->partition_to_view
);
228 free (map
->view_to_partition
);
233 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
234 Returns the partition which represents the new partition. If the two
235 partitions cannot be combined, NO_PARTITION is returned. */
238 var_union (var_map map
, tree var1
, tree var2
)
242 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
243 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
245 /* This is independent of partition_to_view. If partition_to_view is
246 on, then whichever one of these partitions is absorbed will never have a
247 dereference into the partition_to_view array any more. */
249 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
250 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
252 gcc_assert (p1
!= NO_PARTITION
);
253 gcc_assert (p2
!= NO_PARTITION
);
258 p3
= partition_union (map
->var_partition
, p1
, p2
);
260 if (map
->partition_to_view
)
261 p3
= map
->partition_to_view
[p3
];
267 /* Compress the partition numbers in MAP such that they fall in the range
268 0..(num_partitions-1) instead of wherever they turned out during
269 the partitioning exercise. This removes any references to unused
270 partitions, thereby allowing bitmaps and other vectors to be much
273 This is implemented such that compaction doesn't affect partitioning.
274 Ie., once partitions are created and possibly merged, running one
275 or more different kind of compaction will not affect the partitions
276 themselves. Their index might change, but all the same variables will
277 still be members of the same partition group. This allows work on reduced
278 sets, and no loss of information when a larger set is later desired.
280 In particular, coalescing can work on partitions which have 2 or more
281 definitions, and then 'recompact' later to include all the single
282 definitions for assignment to program variables. */
285 /* Set MAP back to the initial state of having no partition view. Return a
286 bitmap which has a bit set for each partition number which is in use in the
290 partition_view_init (var_map map
)
296 used
= BITMAP_ALLOC (NULL
);
298 /* Already in a view? Abandon the old one. */
299 if (map
->partition_to_view
)
301 free (map
->partition_to_view
);
302 map
->partition_to_view
= NULL
;
304 if (map
->view_to_partition
)
306 free (map
->view_to_partition
);
307 map
->view_to_partition
= NULL
;
310 /* Find out which partitions are actually referenced. */
311 for (x
= 0; x
< map
->partition_size
; x
++)
313 tmp
= partition_find (map
->var_partition
, x
);
314 if (ssa_name (tmp
) != NULL_TREE
&& !virtual_operand_p (ssa_name (tmp
))
315 && (!has_zero_uses (ssa_name (tmp
))
316 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
317 bitmap_set_bit (used
, tmp
);
320 map
->num_partitions
= map
->partition_size
;
325 /* This routine will finalize the view data for MAP based on the partitions
326 set in SELECTED. This is either the same bitmap returned from
327 partition_view_init, or a trimmed down version if some of those partitions
328 were not desired in this view. SELECTED is freed before returning. */
331 partition_view_fini (var_map map
, bitmap selected
)
334 unsigned count
, i
, x
, limit
;
336 gcc_assert (selected
);
338 count
= bitmap_count_bits (selected
);
339 limit
= map
->partition_size
;
341 /* If its a one-to-one ratio, we don't need any view compaction. */
344 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
345 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
346 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
349 /* Give each selected partition an index. */
350 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
352 map
->partition_to_view
[x
] = i
;
353 map
->view_to_partition
[i
] = x
;
356 gcc_assert (i
== count
);
357 map
->num_partitions
= i
;
360 BITMAP_FREE (selected
);
364 /* Create a partition view which includes all the used partitions in MAP. If
365 WANT_BASES is true, create the base variable map as well. */
368 partition_view_normal (var_map map
, bool want_bases
)
372 used
= partition_view_init (map
);
373 partition_view_fini (map
, used
);
376 var_map_base_init (map
);
378 var_map_base_fini (map
);
382 /* Create a partition view in MAP which includes just partitions which occur in
383 the bitmap ONLY. If WANT_BASES is true, create the base variable map
387 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
390 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
394 used
= partition_view_init (map
);
395 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
397 p
= partition_find (map
->var_partition
, x
);
398 gcc_assert (bitmap_bit_p (used
, p
));
399 bitmap_set_bit (new_partitions
, p
);
401 partition_view_fini (map
, new_partitions
);
404 var_map_base_init (map
);
406 var_map_base_fini (map
);
410 static bitmap usedvars
;
412 /* Mark VAR as used, so that it'll be preserved during rtl expansion.
413 Returns true if VAR wasn't marked before. */
416 set_is_used (tree var
)
418 return bitmap_set_bit (usedvars
, DECL_UID (var
));
421 /* Return true if VAR is marked as used. */
426 return bitmap_bit_p (usedvars
, DECL_UID (var
));
429 static inline void mark_all_vars_used (tree
*);
431 /* Helper function for mark_all_vars_used, called via walk_tree. */
434 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
437 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
440 if (TREE_CODE (t
) == SSA_NAME
)
443 t
= SSA_NAME_VAR (t
);
448 if (IS_EXPR_CODE_CLASS (c
)
449 && (b
= TREE_BLOCK (t
)) != NULL
)
450 TREE_USED (b
) = true;
452 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
453 fields do not contain vars. */
454 if (TREE_CODE (t
) == TARGET_MEM_REF
)
456 mark_all_vars_used (&TMR_BASE (t
));
457 mark_all_vars_used (&TMR_INDEX (t
));
458 mark_all_vars_used (&TMR_INDEX2 (t
));
463 /* Only need to mark VAR_DECLS; parameters and return results are not
464 eliminated as unused. */
465 if (TREE_CODE (t
) == VAR_DECL
)
467 /* When a global var becomes used for the first time also walk its
468 initializer (non global ones don't have any). */
469 if (set_is_used (t
) && is_global_var (t
)
470 && DECL_CONTEXT (t
) == current_function_decl
)
471 mark_all_vars_used (&DECL_INITIAL (t
));
473 /* remove_unused_scope_block_p requires information about labels
474 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
475 else if (TREE_CODE (t
) == LABEL_DECL
)
476 /* Although the TREE_USED values that the frontend uses would be
477 acceptable (albeit slightly over-conservative) for our purposes,
478 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
479 must re-compute it here. */
482 if (IS_TYPE_OR_DECL_P (t
))
488 /* Mark the scope block SCOPE and its subblocks unused when they can be
489 possibly eliminated if dead. */
492 mark_scope_block_unused (tree scope
)
495 TREE_USED (scope
) = false;
496 if (!(*debug_hooks
->ignore_block
) (scope
))
497 TREE_USED (scope
) = true;
498 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
499 mark_scope_block_unused (t
);
502 /* Look if the block is dead (by possibly eliminating its dead subblocks)
503 and return true if so.
504 Block is declared dead if:
505 1) No statements are associated with it.
506 2) Declares no live variables
507 3) All subblocks are dead
508 or there is precisely one subblocks and the block
509 has same abstract origin as outer block and declares
510 no variables, so it is pure wrapper.
511 When we are not outputting full debug info, we also eliminate dead variables
512 out of scope blocks to let them to be recycled by GGC and to save copying work
513 done by the inliner. */
516 remove_unused_scope_block_p (tree scope
, bool in_ctor_dtor_block
)
519 bool unused
= !TREE_USED (scope
);
522 /* For ipa-polymorphic-call.c purposes, preserve blocks:
523 1) with BLOCK_ABSTRACT_ORIGIN of a ctor/dtor or their clones */
524 if (inlined_polymorphic_ctor_dtor_block_p (scope
, true))
526 in_ctor_dtor_block
= true;
529 /* 2) inside such blocks, the outermost block with BLOCK_ABSTRACT_ORIGIN
530 being a FUNCTION_DECL. */
531 else if (in_ctor_dtor_block
532 && BLOCK_ABSTRACT_ORIGIN (scope
)
533 && TREE_CODE (BLOCK_ABSTRACT_ORIGIN (scope
)) == FUNCTION_DECL
)
535 in_ctor_dtor_block
= false;
539 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
541 next
= &DECL_CHAIN (*t
);
543 /* Debug info of nested function refers to the block of the
544 function. We might stil call it even if all statements
545 of function it was nested into was elliminated.
547 TODO: We can actually look into cgraph to see if function
548 will be output to file. */
549 if (TREE_CODE (*t
) == FUNCTION_DECL
)
552 /* If a decl has a value expr, we need to instantiate it
553 regardless of debug info generation, to avoid codegen
554 differences in memory overlap tests. update_equiv_regs() may
555 indirectly call validate_equiv_mem() to test whether a
556 SET_DEST overlaps with others, and if the value expr changes
557 by virtual register instantiation, we may get end up with
558 different results. */
559 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
562 /* Remove everything we don't generate debug info for. */
563 else if (DECL_IGNORED_P (*t
))
565 *t
= DECL_CHAIN (*t
);
569 /* When we are outputting debug info, we usually want to output
570 info about optimized-out variables in the scope blocks.
571 Exception are the scope blocks not containing any instructions
572 at all so user can't get into the scopes at first place. */
573 else if (is_used_p (*t
))
575 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
576 /* For labels that are still used in the IL, the decision to
577 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
578 risk having different ordering in debug vs. non-debug builds
579 during inlining or versioning.
580 A label appearing here (we have already checked DECL_IGNORED_P)
581 should not be used in the IL unless it has been explicitly used
582 before, so we use TREE_USED as an approximation. */
583 /* In principle, we should do the same here as for the debug case
584 below, however, when debugging, there might be additional nested
585 levels that keep an upper level with a label live, so we have to
586 force this block to be considered used, too. */
589 /* When we are not doing full debug info, we however can keep around
590 only the used variables for cfgexpand's memory packing saving quite
593 For sake of -g3, we keep around those vars but we don't count this as
594 use of block, so innermost block with no used vars and no instructions
595 can be considered dead. We only want to keep around blocks user can
596 breakpoint into and ask about value of optimized out variables.
598 Similarly we need to keep around types at least until all
599 variables of all nested blocks are gone. We track no
600 information on whether given type is used or not, so we have
601 to keep them even when not emitting debug information,
602 otherwise we may end up remapping variables and their (local)
603 types in different orders depending on whether debug
604 information is being generated. */
606 else if (TREE_CODE (*t
) == TYPE_DECL
607 || debug_info_level
== DINFO_LEVEL_NORMAL
608 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
612 *t
= DECL_CHAIN (*t
);
617 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
618 if (remove_unused_scope_block_p (*t
, in_ctor_dtor_block
))
620 if (BLOCK_SUBBLOCKS (*t
))
622 tree next
= BLOCK_CHAIN (*t
);
623 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
625 *t
= BLOCK_SUBBLOCKS (*t
);
626 while (BLOCK_CHAIN (*t
))
628 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
629 t
= &BLOCK_CHAIN (*t
);
631 BLOCK_CHAIN (*t
) = next
;
632 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
633 t
= &BLOCK_CHAIN (*t
);
637 *t
= BLOCK_CHAIN (*t
);
641 t
= &BLOCK_CHAIN (*t
);
648 /* Outer scope is always used. */
649 else if (!BLOCK_SUPERCONTEXT (scope
)
650 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
652 /* Innermost blocks with no live variables nor statements can be always
654 else if (!nsubblocks
)
656 /* When not generating debug info we can eliminate info on unused
658 else if (!flag_auto_profile
&& debug_info_level
== DINFO_LEVEL_NONE
)
660 /* Even for -g0 don't prune outer scopes from artificial
661 functions, otherwise diagnostics using tree_nonartificial_location
662 will not be emitted properly. */
663 if (inlined_function_outer_scope_p (scope
))
668 && TREE_CODE (ao
) == BLOCK
669 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
670 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
672 && TREE_CODE (ao
) == FUNCTION_DECL
673 && DECL_DECLARED_INLINE_P (ao
)
674 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
678 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
680 /* See if this block is important for representation of inlined function.
681 Inlined functions are always represented by block with
682 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
684 else if (inlined_function_outer_scope_p (scope
))
687 /* Verfify that only blocks with source location set
688 are entry points to the inlined functions. */
689 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
))
690 == UNKNOWN_LOCATION
);
692 TREE_USED (scope
) = !unused
;
696 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
697 eliminated during the tree->rtl conversion process. */
700 mark_all_vars_used (tree
*expr_p
)
702 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
705 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
708 clear_unused_block_pointer_1 (tree
*tp
, int *, void *)
710 if (EXPR_P (*tp
) && TREE_BLOCK (*tp
)
711 && !TREE_USED (TREE_BLOCK (*tp
)))
712 TREE_SET_BLOCK (*tp
, NULL
);
716 /* Set all block pointer in debug or clobber stmt to NULL if the block
717 is unused, so that they will not be streamed out. */
720 clear_unused_block_pointer (void)
723 gimple_stmt_iterator gsi
;
725 FOR_EACH_BB_FN (bb
, cfun
)
726 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
730 gimple stmt
= gsi_stmt (gsi
);
732 if (!is_gimple_debug (stmt
) && !gimple_clobber_p (stmt
))
734 b
= gimple_block (stmt
);
735 if (b
&& !TREE_USED (b
))
736 gimple_set_block (stmt
, NULL
);
737 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
738 walk_tree (gimple_op_ptr (stmt
, i
), clear_unused_block_pointer_1
,
743 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
744 indentation level and FLAGS is as in print_generic_expr. */
747 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
752 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
753 TREE_USED (scope
) ? "" : " (unused)",
754 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
755 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
)) != UNKNOWN_LOCATION
)
757 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
758 fprintf (file
, " %s:%i", s
.file
, s
.line
);
760 if (BLOCK_ABSTRACT_ORIGIN (scope
))
762 tree origin
= block_ultimate_origin (scope
);
765 fprintf (file
, " Originating from :");
767 print_generic_decl (file
, origin
, flags
);
769 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
772 fprintf (file
, " \n");
773 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
775 fprintf (file
, "%*s", indent
, "");
776 print_generic_decl (file
, var
, flags
);
777 fprintf (file
, "\n");
779 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
781 fprintf (file
, "%*s",indent
, "");
782 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
784 fprintf (file
, " (nonlocalized)\n");
786 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
787 dump_scope_block (file
, indent
+ 2, t
, flags
);
788 fprintf (file
, "\n%*s}\n",indent
, "");
791 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
792 is as in print_generic_expr. */
795 debug_scope_block (tree scope
, int flags
)
797 dump_scope_block (stderr
, 0, scope
, flags
);
801 /* Dump the tree of lexical scopes of current_function_decl to FILE.
802 FLAGS is as in print_generic_expr. */
805 dump_scope_blocks (FILE *file
, int flags
)
807 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
811 /* Dump the tree of lexical scopes of current_function_decl to stderr.
812 FLAGS is as in print_generic_expr. */
815 debug_scope_blocks (int flags
)
817 dump_scope_blocks (stderr
, flags
);
820 /* Remove local variables that are not referenced in the IL. */
823 remove_unused_locals (void)
827 unsigned srcidx
, dstidx
, num
;
828 bool have_local_clobbers
= false;
830 /* Removing declarations from lexical blocks when not optimizing is
831 not only a waste of time, it actually causes differences in stack
836 timevar_push (TV_REMOVE_UNUSED
);
838 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
840 usedvars
= BITMAP_ALLOC (NULL
);
842 /* Walk the CFG marking all referenced symbols. */
843 FOR_EACH_BB_FN (bb
, cfun
)
845 gimple_stmt_iterator gsi
;
850 /* Walk the statements. */
851 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
853 gimple stmt
= gsi_stmt (gsi
);
854 tree b
= gimple_block (stmt
);
856 if (is_gimple_debug (stmt
))
859 if (gimple_clobber_p (stmt
))
861 have_local_clobbers
= true;
866 TREE_USED (b
) = true;
868 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
869 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
));
872 for (gphi_iterator gpi
= gsi_start_phis (bb
);
879 gphi
*phi
= gpi
.phi ();
881 if (virtual_operand_p (gimple_phi_result (phi
)))
884 def
= gimple_phi_result (phi
);
885 mark_all_vars_used (&def
);
887 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
889 tree arg
= USE_FROM_PTR (arg_p
);
890 int index
= PHI_ARG_INDEX_FROM_USE (arg_p
);
892 LOCATION_BLOCK (gimple_phi_arg_location (phi
, index
));
894 TREE_USED (block
) = true;
895 mark_all_vars_used (&arg
);
899 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
900 if (LOCATION_BLOCK (e
->goto_locus
) != NULL
)
901 TREE_USED (LOCATION_BLOCK (e
->goto_locus
)) = true;
904 /* We do a two-pass approach about the out-of-scope clobbers. We want
905 to remove them if they are the only references to a local variable,
906 but we want to retain them when there's any other. So the first pass
907 ignores them, and the second pass (if there were any) tries to remove
909 if (have_local_clobbers
)
910 FOR_EACH_BB_FN (bb
, cfun
)
912 gimple_stmt_iterator gsi
;
914 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
916 gimple stmt
= gsi_stmt (gsi
);
917 tree b
= gimple_block (stmt
);
919 if (gimple_clobber_p (stmt
))
921 tree lhs
= gimple_assign_lhs (stmt
);
922 tree base
= get_base_address (lhs
);
923 /* Remove clobbers referencing unused vars, or clobbers
924 with MEM_REF lhs referencing uninitialized pointers. */
925 if ((TREE_CODE (base
) == VAR_DECL
&& !is_used_p (base
))
926 || (TREE_CODE (lhs
) == MEM_REF
927 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
928 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs
, 0))
929 && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs
, 0)))
932 unlink_stmt_vdef (stmt
);
933 gsi_remove (&gsi
, true);
938 TREE_USED (b
) = true;
944 cfun
->has_local_explicit_reg_vars
= false;
946 /* Remove unmarked local and global vars from local_decls. */
947 num
= vec_safe_length (cfun
->local_decls
);
948 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
950 var
= (*cfun
->local_decls
)[srcidx
];
951 if (TREE_CODE (var
) == VAR_DECL
)
953 if (!is_used_p (var
))
956 if (cfun
->nonlocal_goto_save_area
957 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
958 cfun
->nonlocal_goto_save_area
= NULL
;
959 /* Release any default def associated with var. */
960 if ((def
= ssa_default_def (cfun
, var
)) != NULL_TREE
)
962 set_ssa_default_def (cfun
, var
, NULL_TREE
);
963 release_ssa_name (def
);
968 if (TREE_CODE (var
) == VAR_DECL
969 && DECL_HARD_REGISTER (var
)
970 && !is_global_var (var
))
971 cfun
->has_local_explicit_reg_vars
= true;
973 if (srcidx
!= dstidx
)
974 (*cfun
->local_decls
)[dstidx
] = var
;
979 statistics_counter_event (cfun
, "unused VAR_DECLs removed", num
- dstidx
);
980 cfun
->local_decls
->truncate (dstidx
);
983 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
), false);
984 clear_unused_block_pointer ();
986 BITMAP_FREE (usedvars
);
988 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
990 fprintf (dump_file
, "Scope blocks after cleanups:\n");
991 dump_scope_blocks (dump_file
, dump_flags
);
994 timevar_pop (TV_REMOVE_UNUSED
);
997 /* Allocate and return a new live range information object base on MAP. */
999 static tree_live_info_p
1000 new_tree_live_info (var_map map
)
1002 tree_live_info_p live
;
1005 live
= XNEW (struct tree_live_info_d
);
1007 live
->num_blocks
= last_basic_block_for_fn (cfun
);
1009 bitmap_obstack_initialize (&live
->livein_obstack
);
1010 bitmap_obstack_initialize (&live
->liveout_obstack
);
1011 live
->livein
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1012 FOR_EACH_BB_FN (bb
, cfun
)
1013 bitmap_initialize (&live
->livein
[bb
->index
], &live
->livein_obstack
);
1015 live
->liveout
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1016 FOR_EACH_BB_FN (bb
, cfun
)
1017 bitmap_initialize (&live
->liveout
[bb
->index
], &live
->liveout_obstack
);
1019 live
->work_stack
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1020 live
->stack_top
= live
->work_stack
;
1022 live
->global
= BITMAP_ALLOC (NULL
);
1027 /* Free storage for live range info object LIVE. */
1030 delete_tree_live_info (tree_live_info_p live
)
1034 bitmap_obstack_release (&live
->livein_obstack
);
1035 free (live
->livein
);
1039 bitmap_obstack_release (&live
->liveout_obstack
);
1040 free (live
->liveout
);
1042 BITMAP_FREE (live
->global
);
1043 free (live
->work_stack
);
1048 /* Visit basic block BB and propagate any required live on entry bits from
1049 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
1050 TMP is a temporary work bitmap which is passed in to avoid reallocating
1054 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
)
1059 basic_block pred_bb
;
1062 gcc_checking_assert (!bitmap_bit_p (visited
, bb
->index
));
1063 bitmap_set_bit (visited
, bb
->index
);
1065 loe
= live_on_entry (live
, bb
);
1067 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1070 if (pred_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1072 /* Variables live-on-entry from BB that aren't defined in the
1073 predecessor block. This should be the live on entry vars to pred.
1074 Note that liveout is the DEFs in a block while live on entry is
1076 Add these bits to live-on-entry for the pred. if there are any
1077 changes, and pred_bb has been visited already, add it to the
1079 change
= bitmap_ior_and_compl_into (live_on_entry (live
, pred_bb
),
1080 loe
, &live
->liveout
[pred_bb
->index
]);
1082 && bitmap_bit_p (visited
, pred_bb
->index
))
1084 bitmap_clear_bit (visited
, pred_bb
->index
);
1085 *(live
->stack_top
)++ = pred_bb
->index
;
1091 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
1092 of all the variables. */
1095 live_worklist (tree_live_info_p live
)
1099 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
) + 1);
1101 bitmap_clear (visited
);
1103 /* Visit all the blocks in reverse order and propagate live on entry values
1104 into the predecessors blocks. */
1105 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
1106 loe_visit_block (live
, bb
, visited
);
1108 /* Process any blocks which require further iteration. */
1109 while (live
->stack_top
!= live
->work_stack
)
1111 b
= *--(live
->stack_top
);
1112 loe_visit_block (live
, BASIC_BLOCK_FOR_FN (cfun
, b
), visited
);
1115 sbitmap_free (visited
);
1119 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1120 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1121 in the liveout vector. */
1124 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1129 basic_block def_bb
= NULL
;
1130 imm_use_iterator imm_iter
;
1131 bool global
= false;
1133 p
= var_to_partition (live
->map
, ssa_name
);
1134 if (p
== NO_PARTITION
)
1137 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1140 def_bb
= gimple_bb (stmt
);
1141 /* Mark defs in liveout bitmap temporarily. */
1143 bitmap_set_bit (&live
->liveout
[def_bb
->index
], p
);
1146 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1148 /* An undefined local variable does not need to be very alive. */
1149 if (ssa_undefined_value_p (ssa_name
, false))
1152 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1153 add it to the list of live on entry blocks. */
1154 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1156 gimple use_stmt
= USE_STMT (use
);
1157 basic_block add_block
= NULL
;
1159 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1161 /* Uses in PHI's are considered to be live at exit of the SRC block
1162 as this is where a copy would be inserted. Check to see if it is
1163 defined in that block, or whether its live on entry. */
1164 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1165 edge e
= gimple_phi_arg_edge (as_a
<gphi
*> (use_stmt
), index
);
1166 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1168 if (e
->src
!= def_bb
)
1172 else if (is_gimple_debug (use_stmt
))
1176 /* If its not defined in this block, its live on entry. */
1177 basic_block use_bb
= gimple_bb (use_stmt
);
1178 if (use_bb
!= def_bb
)
1182 /* If there was a live on entry use, set the bit. */
1186 bitmap_set_bit (&live
->livein
[add_block
->index
], p
);
1190 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1191 on entry blocks between the def and all the uses. */
1193 bitmap_set_bit (live
->global
, p
);
1197 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1200 calculate_live_on_exit (tree_live_info_p liveinfo
)
1206 /* live on entry calculations used liveout vectors for defs, clear them. */
1207 FOR_EACH_BB_FN (bb
, cfun
)
1208 bitmap_clear (&liveinfo
->liveout
[bb
->index
]);
1210 /* Set all the live-on-exit bits for uses in PHIs. */
1211 FOR_EACH_BB_FN (bb
, cfun
)
1216 /* Mark the PHI arguments which are live on exit to the pred block. */
1217 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1219 gphi
*phi
= gsi
.phi ();
1220 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1222 tree t
= PHI_ARG_DEF (phi
, i
);
1225 if (TREE_CODE (t
) != SSA_NAME
)
1228 p
= var_to_partition (liveinfo
->map
, t
);
1229 if (p
== NO_PARTITION
)
1231 e
= gimple_phi_arg_edge (phi
, i
);
1232 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1233 bitmap_set_bit (&liveinfo
->liveout
[e
->src
->index
], p
);
1237 /* Add each successors live on entry to this bock live on exit. */
1238 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1239 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1240 bitmap_ior_into (&liveinfo
->liveout
[bb
->index
],
1241 live_on_entry (liveinfo
, e
->dest
));
1246 /* Given partition map MAP, calculate all the live on entry bitmaps for
1247 each partition. Return a new live info object. */
1250 calculate_live_ranges (var_map map
, bool want_livein
)
1254 tree_live_info_p live
;
1256 live
= new_tree_live_info (map
);
1257 for (i
= 0; i
< num_var_partitions (map
); i
++)
1259 var
= partition_to_var (map
, i
);
1260 if (var
!= NULL_TREE
)
1261 set_var_live_on_entry (var
, live
);
1264 live_worklist (live
);
1266 #ifdef ENABLE_CHECKING
1267 verify_live_on_entry (live
);
1270 calculate_live_on_exit (live
);
1274 bitmap_obstack_release (&live
->livein_obstack
);
1275 free (live
->livein
);
1276 live
->livein
= NULL
;
1283 /* Output partition map MAP to file F. */
1286 dump_var_map (FILE *f
, var_map map
)
1292 fprintf (f
, "\nPartition map \n\n");
1294 for (x
= 0; x
< map
->num_partitions
; x
++)
1296 if (map
->view_to_partition
!= NULL
)
1297 p
= map
->view_to_partition
[x
];
1301 if (ssa_name (p
) == NULL_TREE
1302 || virtual_operand_p (ssa_name (p
)))
1306 for (y
= 1; y
< num_ssa_names
; y
++)
1308 p
= partition_find (map
->var_partition
, y
);
1309 if (map
->partition_to_view
)
1310 p
= map
->partition_to_view
[p
];
1315 fprintf (f
, "Partition %d (", x
);
1316 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1319 fprintf (f
, "%d ", y
);
1329 /* Generic dump for the above. */
1332 debug (_var_map
&ref
)
1334 dump_var_map (stderr
, &ref
);
1338 debug (_var_map
*ptr
)
1343 fprintf (stderr
, "<nil>\n");
1347 /* Output live range info LIVE to file F, controlled by FLAG. */
1350 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1354 var_map map
= live
->map
;
1357 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1359 FOR_EACH_BB_FN (bb
, cfun
)
1361 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1362 EXECUTE_IF_SET_IN_BITMAP (&live
->livein
[bb
->index
], 0, i
, bi
)
1364 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1371 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1373 FOR_EACH_BB_FN (bb
, cfun
)
1375 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1376 EXECUTE_IF_SET_IN_BITMAP (&live
->liveout
[bb
->index
], 0, i
, bi
)
1378 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1387 /* Generic dump for the above. */
1390 debug (tree_live_info_d
&ref
)
1392 dump_live_info (stderr
, &ref
, 0);
1396 debug (tree_live_info_d
*ptr
)
1401 fprintf (stderr
, "<nil>\n");
1405 #ifdef ENABLE_CHECKING
1406 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1409 register_ssa_partition_check (tree ssa_var
)
1411 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1412 if (virtual_operand_p (ssa_var
))
1414 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1415 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1416 fprintf (stderr
, " in the SSA->Normal phase.\n");
1417 internal_error ("SSA corruption");
1422 /* Verify that the info in LIVE matches the current cfg. */
1425 verify_live_on_entry (tree_live_info_p live
)
1434 var_map map
= live
->map
;
1436 /* Check for live on entry partitions and report those with a DEF in
1437 the program. This will typically mean an optimization has done
1439 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1441 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1443 int entry_block
= e
->dest
->index
;
1444 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1446 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1451 var
= partition_to_var (map
, i
);
1452 stmt
= SSA_NAME_DEF_STMT (var
);
1453 tmp
= gimple_bb (stmt
);
1454 if (SSA_NAME_VAR (var
))
1455 d
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1457 loe
= live_on_entry (live
, e
->dest
);
1458 if (loe
&& bitmap_bit_p (loe
, i
))
1460 if (!gimple_nop_p (stmt
))
1463 print_generic_expr (stderr
, var
, TDF_SLIM
);
1464 fprintf (stderr
, " is defined ");
1466 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1467 fprintf (stderr
, "by:\n");
1468 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1469 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1471 fprintf (stderr
, " So it appears to have multiple defs.\n");
1478 print_generic_expr (stderr
, var
, TDF_SLIM
);
1479 fprintf (stderr
, " is live-on-entry to BB%d ",
1483 fprintf (stderr
, " but is not the default def of ");
1484 print_generic_expr (stderr
, d
, TDF_SLIM
);
1485 fprintf (stderr
, "\n");
1488 fprintf (stderr
, " and there is no default def.\n");
1495 /* An undefined local variable does not need to be very
1497 if (ssa_undefined_value_p (var
, false))
1500 /* The only way this var shouldn't be marked live on entry is
1501 if it occurs in a PHI argument of the block. */
1505 for (gsi
= gsi_start_phis (e
->dest
);
1506 !gsi_end_p (gsi
) && !ok
;
1509 gphi
*phi
= gsi
.phi ();
1510 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1511 if (var
== gimple_phi_arg_def (phi
, z
))
1520 print_generic_expr (stderr
, var
, TDF_SLIM
);
1521 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1523 fprintf (stderr
, "but it is a default def so it should be.\n");
1527 gcc_assert (num
<= 0);