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"
30 #include "fold-const.h"
31 #include "gimple-pretty-print.h"
32 #include "internal-fn.h"
33 #include "gimple-iterator.h"
35 #include "insn-config.h"
47 #include "tree-ssa-live.h"
48 #include "diagnostic-core.h"
52 #include "ipa-utils.h"
54 #ifdef ENABLE_CHECKING
55 static void verify_live_on_entry (tree_live_info_p
);
59 /* VARMAP maintains a mapping from SSA version number to real variables.
61 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
62 only member of it's own partition. Coalescing will attempt to group any
63 ssa_names which occur in a copy or in a PHI node into the same partition.
65 At the end of out-of-ssa, each partition becomes a "real" variable and is
66 rewritten as a compiler variable.
68 The var_map data structure is used to manage these partitions. It allows
69 partitions to be combined, and determines which partition belongs to what
70 ssa_name or variable, and vice versa. */
73 /* Remove the base table in MAP. */
76 var_map_base_fini (var_map map
)
78 /* Free the basevar info if it is present. */
79 if (map
->partition_to_base_index
!= NULL
)
81 free (map
->partition_to_base_index
);
82 map
->partition_to_base_index
= NULL
;
83 map
->num_basevars
= 0;
86 /* Create a variable partition map of SIZE, initialize and return it. */
89 init_var_map (int size
)
93 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
94 map
->var_partition
= partition_new (size
);
96 map
->partition_to_view
= NULL
;
97 map
->view_to_partition
= NULL
;
98 map
->num_partitions
= size
;
99 map
->partition_size
= size
;
100 map
->num_basevars
= 0;
101 map
->partition_to_base_index
= NULL
;
106 /* Free memory associated with MAP. */
109 delete_var_map (var_map map
)
111 var_map_base_fini (map
);
112 partition_delete (map
->var_partition
);
113 free (map
->partition_to_view
);
114 free (map
->view_to_partition
);
119 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
120 Returns the partition which represents the new partition. If the two
121 partitions cannot be combined, NO_PARTITION is returned. */
124 var_union (var_map map
, tree var1
, tree var2
)
128 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
129 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
131 /* This is independent of partition_to_view. If partition_to_view is
132 on, then whichever one of these partitions is absorbed will never have a
133 dereference into the partition_to_view array any more. */
135 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
136 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
138 gcc_assert (p1
!= NO_PARTITION
);
139 gcc_assert (p2
!= NO_PARTITION
);
144 p3
= partition_union (map
->var_partition
, p1
, p2
);
146 if (map
->partition_to_view
)
147 p3
= map
->partition_to_view
[p3
];
153 /* Compress the partition numbers in MAP such that they fall in the range
154 0..(num_partitions-1) instead of wherever they turned out during
155 the partitioning exercise. This removes any references to unused
156 partitions, thereby allowing bitmaps and other vectors to be much
159 This is implemented such that compaction doesn't affect partitioning.
160 Ie., once partitions are created and possibly merged, running one
161 or more different kind of compaction will not affect the partitions
162 themselves. Their index might change, but all the same variables will
163 still be members of the same partition group. This allows work on reduced
164 sets, and no loss of information when a larger set is later desired.
166 In particular, coalescing can work on partitions which have 2 or more
167 definitions, and then 'recompact' later to include all the single
168 definitions for assignment to program variables. */
171 /* Set MAP back to the initial state of having no partition view. Return a
172 bitmap which has a bit set for each partition number which is in use in the
176 partition_view_init (var_map map
)
182 used
= BITMAP_ALLOC (NULL
);
184 /* Already in a view? Abandon the old one. */
185 if (map
->partition_to_view
)
187 free (map
->partition_to_view
);
188 map
->partition_to_view
= NULL
;
190 if (map
->view_to_partition
)
192 free (map
->view_to_partition
);
193 map
->view_to_partition
= NULL
;
196 /* Find out which partitions are actually referenced. */
197 for (x
= 0; x
< map
->partition_size
; x
++)
199 tmp
= partition_find (map
->var_partition
, x
);
200 if (ssa_name (tmp
) != NULL_TREE
&& !virtual_operand_p (ssa_name (tmp
))
201 && (!has_zero_uses (ssa_name (tmp
))
202 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
203 bitmap_set_bit (used
, tmp
);
206 map
->num_partitions
= map
->partition_size
;
211 /* This routine will finalize the view data for MAP based on the partitions
212 set in SELECTED. This is either the same bitmap returned from
213 partition_view_init, or a trimmed down version if some of those partitions
214 were not desired in this view. SELECTED is freed before returning. */
217 partition_view_fini (var_map map
, bitmap selected
)
220 unsigned count
, i
, x
, limit
;
222 gcc_assert (selected
);
224 count
= bitmap_count_bits (selected
);
225 limit
= map
->partition_size
;
227 /* If its a one-to-one ratio, we don't need any view compaction. */
230 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
231 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
232 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
235 /* Give each selected partition an index. */
236 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
238 map
->partition_to_view
[x
] = i
;
239 map
->view_to_partition
[i
] = x
;
242 gcc_assert (i
== count
);
243 map
->num_partitions
= i
;
246 BITMAP_FREE (selected
);
250 /* Create a partition view which includes all the used partitions in MAP. */
253 partition_view_normal (var_map map
)
257 used
= partition_view_init (map
);
258 partition_view_fini (map
, used
);
260 var_map_base_fini (map
);
264 /* Create a partition view in MAP which includes just partitions which occur in
265 the bitmap ONLY. If WANT_BASES is true, create the base variable map
269 partition_view_bitmap (var_map map
, bitmap only
)
272 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
276 used
= partition_view_init (map
);
277 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
279 p
= partition_find (map
->var_partition
, x
);
280 gcc_assert (bitmap_bit_p (used
, p
));
281 bitmap_set_bit (new_partitions
, p
);
283 partition_view_fini (map
, new_partitions
);
285 var_map_base_fini (map
);
289 static bitmap usedvars
;
291 /* Mark VAR as used, so that it'll be preserved during rtl expansion.
292 Returns true if VAR wasn't marked before. */
295 set_is_used (tree var
)
297 return bitmap_set_bit (usedvars
, DECL_UID (var
));
300 /* Return true if VAR is marked as used. */
305 return bitmap_bit_p (usedvars
, DECL_UID (var
));
308 static inline void mark_all_vars_used (tree
*);
310 /* Helper function for mark_all_vars_used, called via walk_tree. */
313 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
316 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
319 if (TREE_CODE (t
) == SSA_NAME
)
322 t
= SSA_NAME_VAR (t
);
327 if (IS_EXPR_CODE_CLASS (c
)
328 && (b
= TREE_BLOCK (t
)) != NULL
)
329 TREE_USED (b
) = true;
331 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
332 fields do not contain vars. */
333 if (TREE_CODE (t
) == TARGET_MEM_REF
)
335 mark_all_vars_used (&TMR_BASE (t
));
336 mark_all_vars_used (&TMR_INDEX (t
));
337 mark_all_vars_used (&TMR_INDEX2 (t
));
342 /* Only need to mark VAR_DECLS; parameters and return results are not
343 eliminated as unused. */
344 if (TREE_CODE (t
) == VAR_DECL
)
346 /* When a global var becomes used for the first time also walk its
347 initializer (non global ones don't have any). */
348 if (set_is_used (t
) && is_global_var (t
)
349 && DECL_CONTEXT (t
) == current_function_decl
)
350 mark_all_vars_used (&DECL_INITIAL (t
));
352 /* remove_unused_scope_block_p requires information about labels
353 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
354 else if (TREE_CODE (t
) == LABEL_DECL
)
355 /* Although the TREE_USED values that the frontend uses would be
356 acceptable (albeit slightly over-conservative) for our purposes,
357 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
358 must re-compute it here. */
361 if (IS_TYPE_OR_DECL_P (t
))
367 /* Mark the scope block SCOPE and its subblocks unused when they can be
368 possibly eliminated if dead. */
371 mark_scope_block_unused (tree scope
)
374 TREE_USED (scope
) = false;
375 if (!(*debug_hooks
->ignore_block
) (scope
))
376 TREE_USED (scope
) = true;
377 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
378 mark_scope_block_unused (t
);
381 /* Look if the block is dead (by possibly eliminating its dead subblocks)
382 and return true if so.
383 Block is declared dead if:
384 1) No statements are associated with it.
385 2) Declares no live variables
386 3) All subblocks are dead
387 or there is precisely one subblocks and the block
388 has same abstract origin as outer block and declares
389 no variables, so it is pure wrapper.
390 When we are not outputting full debug info, we also eliminate dead variables
391 out of scope blocks to let them to be recycled by GGC and to save copying work
392 done by the inliner. */
395 remove_unused_scope_block_p (tree scope
, bool in_ctor_dtor_block
)
398 bool unused
= !TREE_USED (scope
);
401 /* For ipa-polymorphic-call.c purposes, preserve blocks:
402 1) with BLOCK_ABSTRACT_ORIGIN of a ctor/dtor or their clones */
403 if (inlined_polymorphic_ctor_dtor_block_p (scope
, true))
405 in_ctor_dtor_block
= true;
408 /* 2) inside such blocks, the outermost block with BLOCK_ABSTRACT_ORIGIN
409 being a FUNCTION_DECL. */
410 else if (in_ctor_dtor_block
411 && BLOCK_ABSTRACT_ORIGIN (scope
)
412 && TREE_CODE (BLOCK_ABSTRACT_ORIGIN (scope
)) == FUNCTION_DECL
)
414 in_ctor_dtor_block
= false;
418 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
420 next
= &DECL_CHAIN (*t
);
422 /* Debug info of nested function refers to the block of the
423 function. We might stil call it even if all statements
424 of function it was nested into was elliminated.
426 TODO: We can actually look into cgraph to see if function
427 will be output to file. */
428 if (TREE_CODE (*t
) == FUNCTION_DECL
)
431 /* If a decl has a value expr, we need to instantiate it
432 regardless of debug info generation, to avoid codegen
433 differences in memory overlap tests. update_equiv_regs() may
434 indirectly call validate_equiv_mem() to test whether a
435 SET_DEST overlaps with others, and if the value expr changes
436 by virtual register instantiation, we may get end up with
437 different results. */
438 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
441 /* Remove everything we don't generate debug info for. */
442 else if (DECL_IGNORED_P (*t
))
444 *t
= DECL_CHAIN (*t
);
448 /* When we are outputting debug info, we usually want to output
449 info about optimized-out variables in the scope blocks.
450 Exception are the scope blocks not containing any instructions
451 at all so user can't get into the scopes at first place. */
452 else if (is_used_p (*t
))
454 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
455 /* For labels that are still used in the IL, the decision to
456 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
457 risk having different ordering in debug vs. non-debug builds
458 during inlining or versioning.
459 A label appearing here (we have already checked DECL_IGNORED_P)
460 should not be used in the IL unless it has been explicitly used
461 before, so we use TREE_USED as an approximation. */
462 /* In principle, we should do the same here as for the debug case
463 below, however, when debugging, there might be additional nested
464 levels that keep an upper level with a label live, so we have to
465 force this block to be considered used, too. */
468 /* When we are not doing full debug info, we however can keep around
469 only the used variables for cfgexpand's memory packing saving quite
472 For sake of -g3, we keep around those vars but we don't count this as
473 use of block, so innermost block with no used vars and no instructions
474 can be considered dead. We only want to keep around blocks user can
475 breakpoint into and ask about value of optimized out variables.
477 Similarly we need to keep around types at least until all
478 variables of all nested blocks are gone. We track no
479 information on whether given type is used or not, so we have
480 to keep them even when not emitting debug information,
481 otherwise we may end up remapping variables and their (local)
482 types in different orders depending on whether debug
483 information is being generated. */
485 else if (TREE_CODE (*t
) == TYPE_DECL
486 || debug_info_level
== DINFO_LEVEL_NORMAL
487 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
491 *t
= DECL_CHAIN (*t
);
496 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
497 if (remove_unused_scope_block_p (*t
, in_ctor_dtor_block
))
499 if (BLOCK_SUBBLOCKS (*t
))
501 tree next
= BLOCK_CHAIN (*t
);
502 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
504 *t
= BLOCK_SUBBLOCKS (*t
);
505 while (BLOCK_CHAIN (*t
))
507 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
508 t
= &BLOCK_CHAIN (*t
);
510 BLOCK_CHAIN (*t
) = next
;
511 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
512 t
= &BLOCK_CHAIN (*t
);
516 *t
= BLOCK_CHAIN (*t
);
520 t
= &BLOCK_CHAIN (*t
);
527 /* Outer scope is always used. */
528 else if (!BLOCK_SUPERCONTEXT (scope
)
529 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
531 /* Innermost blocks with no live variables nor statements can be always
533 else if (!nsubblocks
)
535 /* When not generating debug info we can eliminate info on unused
537 else if (!flag_auto_profile
&& debug_info_level
== DINFO_LEVEL_NONE
)
539 /* Even for -g0 don't prune outer scopes from artificial
540 functions, otherwise diagnostics using tree_nonartificial_location
541 will not be emitted properly. */
542 if (inlined_function_outer_scope_p (scope
))
547 && TREE_CODE (ao
) == BLOCK
548 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
549 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
551 && TREE_CODE (ao
) == FUNCTION_DECL
552 && DECL_DECLARED_INLINE_P (ao
)
553 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
557 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
559 /* See if this block is important for representation of inlined function.
560 Inlined functions are always represented by block with
561 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
563 else if (inlined_function_outer_scope_p (scope
))
566 /* Verfify that only blocks with source location set
567 are entry points to the inlined functions. */
568 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
))
569 == UNKNOWN_LOCATION
);
571 TREE_USED (scope
) = !unused
;
575 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
576 eliminated during the tree->rtl conversion process. */
579 mark_all_vars_used (tree
*expr_p
)
581 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
584 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
587 clear_unused_block_pointer_1 (tree
*tp
, int *, void *)
589 if (EXPR_P (*tp
) && TREE_BLOCK (*tp
)
590 && !TREE_USED (TREE_BLOCK (*tp
)))
591 TREE_SET_BLOCK (*tp
, NULL
);
595 /* Set all block pointer in debug or clobber stmt to NULL if the block
596 is unused, so that they will not be streamed out. */
599 clear_unused_block_pointer (void)
602 gimple_stmt_iterator gsi
;
604 FOR_EACH_BB_FN (bb
, cfun
)
605 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
609 gimple stmt
= gsi_stmt (gsi
);
611 if (!is_gimple_debug (stmt
) && !gimple_clobber_p (stmt
))
613 b
= gimple_block (stmt
);
614 if (b
&& !TREE_USED (b
))
615 gimple_set_block (stmt
, NULL
);
616 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
617 walk_tree (gimple_op_ptr (stmt
, i
), clear_unused_block_pointer_1
,
622 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
623 indentation level and FLAGS is as in print_generic_expr. */
626 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
631 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
632 TREE_USED (scope
) ? "" : " (unused)",
633 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
634 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
)) != UNKNOWN_LOCATION
)
636 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
637 fprintf (file
, " %s:%i", s
.file
, s
.line
);
639 if (BLOCK_ABSTRACT_ORIGIN (scope
))
641 tree origin
= block_ultimate_origin (scope
);
644 fprintf (file
, " Originating from :");
646 print_generic_decl (file
, origin
, flags
);
648 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
651 fprintf (file
, " \n");
652 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
654 fprintf (file
, "%*s", indent
, "");
655 print_generic_decl (file
, var
, flags
);
656 fprintf (file
, "\n");
658 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
660 fprintf (file
, "%*s",indent
, "");
661 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
663 fprintf (file
, " (nonlocalized)\n");
665 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
666 dump_scope_block (file
, indent
+ 2, t
, flags
);
667 fprintf (file
, "\n%*s}\n",indent
, "");
670 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
671 is as in print_generic_expr. */
674 debug_scope_block (tree scope
, int flags
)
676 dump_scope_block (stderr
, 0, scope
, flags
);
680 /* Dump the tree of lexical scopes of current_function_decl to FILE.
681 FLAGS is as in print_generic_expr. */
684 dump_scope_blocks (FILE *file
, int flags
)
686 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
690 /* Dump the tree of lexical scopes of current_function_decl to stderr.
691 FLAGS is as in print_generic_expr. */
694 debug_scope_blocks (int flags
)
696 dump_scope_blocks (stderr
, flags
);
699 /* Remove local variables that are not referenced in the IL. */
702 remove_unused_locals (void)
706 unsigned srcidx
, dstidx
, num
;
707 bool have_local_clobbers
= false;
709 /* Removing declarations from lexical blocks when not optimizing is
710 not only a waste of time, it actually causes differences in stack
715 timevar_push (TV_REMOVE_UNUSED
);
717 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
719 usedvars
= BITMAP_ALLOC (NULL
);
721 /* Walk the CFG marking all referenced symbols. */
722 FOR_EACH_BB_FN (bb
, cfun
)
724 gimple_stmt_iterator gsi
;
729 /* Walk the statements. */
730 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
732 gimple stmt
= gsi_stmt (gsi
);
733 tree b
= gimple_block (stmt
);
735 if (is_gimple_debug (stmt
))
738 if (gimple_clobber_p (stmt
))
740 have_local_clobbers
= true;
745 TREE_USED (b
) = true;
747 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
748 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
));
751 for (gphi_iterator gpi
= gsi_start_phis (bb
);
758 gphi
*phi
= gpi
.phi ();
760 if (virtual_operand_p (gimple_phi_result (phi
)))
763 def
= gimple_phi_result (phi
);
764 mark_all_vars_used (&def
);
766 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
768 tree arg
= USE_FROM_PTR (arg_p
);
769 int index
= PHI_ARG_INDEX_FROM_USE (arg_p
);
771 LOCATION_BLOCK (gimple_phi_arg_location (phi
, index
));
773 TREE_USED (block
) = true;
774 mark_all_vars_used (&arg
);
778 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
779 if (LOCATION_BLOCK (e
->goto_locus
) != NULL
)
780 TREE_USED (LOCATION_BLOCK (e
->goto_locus
)) = true;
783 /* We do a two-pass approach about the out-of-scope clobbers. We want
784 to remove them if they are the only references to a local variable,
785 but we want to retain them when there's any other. So the first pass
786 ignores them, and the second pass (if there were any) tries to remove
788 if (have_local_clobbers
)
789 FOR_EACH_BB_FN (bb
, cfun
)
791 gimple_stmt_iterator gsi
;
793 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
795 gimple stmt
= gsi_stmt (gsi
);
796 tree b
= gimple_block (stmt
);
798 if (gimple_clobber_p (stmt
))
800 tree lhs
= gimple_assign_lhs (stmt
);
801 tree base
= get_base_address (lhs
);
802 /* Remove clobbers referencing unused vars, or clobbers
803 with MEM_REF lhs referencing uninitialized pointers. */
804 if ((TREE_CODE (base
) == VAR_DECL
&& !is_used_p (base
))
805 || (TREE_CODE (lhs
) == MEM_REF
806 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
807 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs
, 0))
808 && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs
, 0)))
811 unlink_stmt_vdef (stmt
);
812 gsi_remove (&gsi
, true);
817 TREE_USED (b
) = true;
823 cfun
->has_local_explicit_reg_vars
= false;
825 /* Remove unmarked local and global vars from local_decls. */
826 num
= vec_safe_length (cfun
->local_decls
);
827 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
829 var
= (*cfun
->local_decls
)[srcidx
];
830 if (TREE_CODE (var
) == VAR_DECL
)
832 if (!is_used_p (var
))
835 if (cfun
->nonlocal_goto_save_area
836 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
837 cfun
->nonlocal_goto_save_area
= NULL
;
838 /* Release any default def associated with var. */
839 if ((def
= ssa_default_def (cfun
, var
)) != NULL_TREE
)
841 set_ssa_default_def (cfun
, var
, NULL_TREE
);
842 release_ssa_name (def
);
847 if (TREE_CODE (var
) == VAR_DECL
848 && DECL_HARD_REGISTER (var
)
849 && !is_global_var (var
))
850 cfun
->has_local_explicit_reg_vars
= true;
852 if (srcidx
!= dstidx
)
853 (*cfun
->local_decls
)[dstidx
] = var
;
858 statistics_counter_event (cfun
, "unused VAR_DECLs removed", num
- dstidx
);
859 cfun
->local_decls
->truncate (dstidx
);
862 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
), false);
863 clear_unused_block_pointer ();
865 BITMAP_FREE (usedvars
);
867 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
869 fprintf (dump_file
, "Scope blocks after cleanups:\n");
870 dump_scope_blocks (dump_file
, dump_flags
);
873 timevar_pop (TV_REMOVE_UNUSED
);
876 /* Allocate and return a new live range information object base on MAP. */
878 static tree_live_info_p
879 new_tree_live_info (var_map map
)
881 tree_live_info_p live
;
884 live
= XNEW (struct tree_live_info_d
);
886 live
->num_blocks
= last_basic_block_for_fn (cfun
);
888 bitmap_obstack_initialize (&live
->livein_obstack
);
889 bitmap_obstack_initialize (&live
->liveout_obstack
);
890 live
->livein
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
891 FOR_EACH_BB_FN (bb
, cfun
)
892 bitmap_initialize (&live
->livein
[bb
->index
], &live
->livein_obstack
);
894 live
->liveout
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
895 FOR_EACH_BB_FN (bb
, cfun
)
896 bitmap_initialize (&live
->liveout
[bb
->index
], &live
->liveout_obstack
);
898 live
->work_stack
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
899 live
->stack_top
= live
->work_stack
;
901 live
->global
= BITMAP_ALLOC (NULL
);
906 /* Free storage for live range info object LIVE. */
909 delete_tree_live_info (tree_live_info_p live
)
913 bitmap_obstack_release (&live
->livein_obstack
);
918 bitmap_obstack_release (&live
->liveout_obstack
);
919 free (live
->liveout
);
921 BITMAP_FREE (live
->global
);
922 free (live
->work_stack
);
927 /* Visit basic block BB and propagate any required live on entry bits from
928 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
929 TMP is a temporary work bitmap which is passed in to avoid reallocating
933 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
)
941 gcc_checking_assert (!bitmap_bit_p (visited
, bb
->index
));
942 bitmap_set_bit (visited
, bb
->index
);
944 loe
= live_on_entry (live
, bb
);
946 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
949 if (pred_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
951 /* Variables live-on-entry from BB that aren't defined in the
952 predecessor block. This should be the live on entry vars to pred.
953 Note that liveout is the DEFs in a block while live on entry is
955 Add these bits to live-on-entry for the pred. if there are any
956 changes, and pred_bb has been visited already, add it to the
958 change
= bitmap_ior_and_compl_into (live_on_entry (live
, pred_bb
),
959 loe
, &live
->liveout
[pred_bb
->index
]);
961 && bitmap_bit_p (visited
, pred_bb
->index
))
963 bitmap_clear_bit (visited
, pred_bb
->index
);
964 *(live
->stack_top
)++ = pred_bb
->index
;
970 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
971 of all the variables. */
974 live_worklist (tree_live_info_p live
)
978 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
) + 1);
980 bitmap_clear (visited
);
982 /* Visit all the blocks in reverse order and propagate live on entry values
983 into the predecessors blocks. */
984 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
985 loe_visit_block (live
, bb
, visited
);
987 /* Process any blocks which require further iteration. */
988 while (live
->stack_top
!= live
->work_stack
)
990 b
= *--(live
->stack_top
);
991 loe_visit_block (live
, BASIC_BLOCK_FOR_FN (cfun
, b
), visited
);
994 sbitmap_free (visited
);
998 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
999 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1000 in the liveout vector. */
1003 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1008 basic_block def_bb
= NULL
;
1009 imm_use_iterator imm_iter
;
1010 bool global
= false;
1012 p
= var_to_partition (live
->map
, ssa_name
);
1013 if (p
== NO_PARTITION
)
1016 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1019 def_bb
= gimple_bb (stmt
);
1020 /* Mark defs in liveout bitmap temporarily. */
1022 bitmap_set_bit (&live
->liveout
[def_bb
->index
], p
);
1025 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1027 /* An undefined local variable does not need to be very alive. */
1028 if (ssa_undefined_value_p (ssa_name
, false))
1031 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1032 add it to the list of live on entry blocks. */
1033 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1035 gimple use_stmt
= USE_STMT (use
);
1036 basic_block add_block
= NULL
;
1038 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1040 /* Uses in PHI's are considered to be live at exit of the SRC block
1041 as this is where a copy would be inserted. Check to see if it is
1042 defined in that block, or whether its live on entry. */
1043 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1044 edge e
= gimple_phi_arg_edge (as_a
<gphi
*> (use_stmt
), index
);
1045 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1047 if (e
->src
!= def_bb
)
1051 else if (is_gimple_debug (use_stmt
))
1055 /* If its not defined in this block, its live on entry. */
1056 basic_block use_bb
= gimple_bb (use_stmt
);
1057 if (use_bb
!= def_bb
)
1061 /* If there was a live on entry use, set the bit. */
1065 bitmap_set_bit (&live
->livein
[add_block
->index
], p
);
1069 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1070 on entry blocks between the def and all the uses. */
1072 bitmap_set_bit (live
->global
, p
);
1076 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1079 calculate_live_on_exit (tree_live_info_p liveinfo
)
1085 /* live on entry calculations used liveout vectors for defs, clear them. */
1086 FOR_EACH_BB_FN (bb
, cfun
)
1087 bitmap_clear (&liveinfo
->liveout
[bb
->index
]);
1089 /* Set all the live-on-exit bits for uses in PHIs. */
1090 FOR_EACH_BB_FN (bb
, cfun
)
1095 /* Mark the PHI arguments which are live on exit to the pred block. */
1096 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1098 gphi
*phi
= gsi
.phi ();
1099 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1101 tree t
= PHI_ARG_DEF (phi
, i
);
1104 if (TREE_CODE (t
) != SSA_NAME
)
1107 p
= var_to_partition (liveinfo
->map
, t
);
1108 if (p
== NO_PARTITION
)
1110 e
= gimple_phi_arg_edge (phi
, i
);
1111 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1112 bitmap_set_bit (&liveinfo
->liveout
[e
->src
->index
], p
);
1116 /* Add each successors live on entry to this bock live on exit. */
1117 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1118 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1119 bitmap_ior_into (&liveinfo
->liveout
[bb
->index
],
1120 live_on_entry (liveinfo
, e
->dest
));
1125 /* Given partition map MAP, calculate all the live on entry bitmaps for
1126 each partition. Return a new live info object. */
1129 calculate_live_ranges (var_map map
, bool want_livein
)
1133 tree_live_info_p live
;
1135 live
= new_tree_live_info (map
);
1136 for (i
= 0; i
< num_var_partitions (map
); i
++)
1138 var
= partition_to_var (map
, i
);
1139 if (var
!= NULL_TREE
)
1140 set_var_live_on_entry (var
, live
);
1143 live_worklist (live
);
1145 #ifdef ENABLE_CHECKING
1146 verify_live_on_entry (live
);
1149 calculate_live_on_exit (live
);
1153 bitmap_obstack_release (&live
->livein_obstack
);
1154 free (live
->livein
);
1155 live
->livein
= NULL
;
1162 /* Output partition map MAP to file F. */
1165 dump_var_map (FILE *f
, var_map map
)
1171 fprintf (f
, "\nPartition map \n\n");
1173 for (x
= 0; x
< map
->num_partitions
; x
++)
1175 if (map
->view_to_partition
!= NULL
)
1176 p
= map
->view_to_partition
[x
];
1180 if (ssa_name (p
) == NULL_TREE
1181 || virtual_operand_p (ssa_name (p
)))
1185 for (y
= 1; y
< num_ssa_names
; y
++)
1187 p
= partition_find (map
->var_partition
, y
);
1188 if (map
->partition_to_view
)
1189 p
= map
->partition_to_view
[p
];
1194 fprintf (f
, "Partition %d (", x
);
1195 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1198 fprintf (f
, "%d ", y
);
1208 /* Generic dump for the above. */
1211 debug (_var_map
&ref
)
1213 dump_var_map (stderr
, &ref
);
1217 debug (_var_map
*ptr
)
1222 fprintf (stderr
, "<nil>\n");
1226 /* Output live range info LIVE to file F, controlled by FLAG. */
1229 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1233 var_map map
= live
->map
;
1236 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1238 FOR_EACH_BB_FN (bb
, cfun
)
1240 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1241 EXECUTE_IF_SET_IN_BITMAP (&live
->livein
[bb
->index
], 0, i
, bi
)
1243 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1250 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1252 FOR_EACH_BB_FN (bb
, cfun
)
1254 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1255 EXECUTE_IF_SET_IN_BITMAP (&live
->liveout
[bb
->index
], 0, i
, bi
)
1257 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1266 /* Generic dump for the above. */
1269 debug (tree_live_info_d
&ref
)
1271 dump_live_info (stderr
, &ref
, 0);
1275 debug (tree_live_info_d
*ptr
)
1280 fprintf (stderr
, "<nil>\n");
1284 #ifdef ENABLE_CHECKING
1285 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1288 register_ssa_partition_check (tree ssa_var
)
1290 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1291 if (virtual_operand_p (ssa_var
))
1293 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1294 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1295 fprintf (stderr
, " in the SSA->Normal phase.\n");
1296 internal_error ("SSA corruption");
1301 /* Verify that the info in LIVE matches the current cfg. */
1304 verify_live_on_entry (tree_live_info_p live
)
1313 var_map map
= live
->map
;
1315 /* Check for live on entry partitions and report those with a DEF in
1316 the program. This will typically mean an optimization has done
1318 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1320 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1322 int entry_block
= e
->dest
->index
;
1323 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1325 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1330 var
= partition_to_var (map
, i
);
1331 stmt
= SSA_NAME_DEF_STMT (var
);
1332 tmp
= gimple_bb (stmt
);
1333 if (SSA_NAME_VAR (var
))
1334 d
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1336 loe
= live_on_entry (live
, e
->dest
);
1337 if (loe
&& bitmap_bit_p (loe
, i
))
1339 if (!gimple_nop_p (stmt
))
1342 print_generic_expr (stderr
, var
, TDF_SLIM
);
1343 fprintf (stderr
, " is defined ");
1345 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1346 fprintf (stderr
, "by:\n");
1347 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1348 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1350 fprintf (stderr
, " So it appears to have multiple defs.\n");
1357 print_generic_expr (stderr
, var
, TDF_SLIM
);
1358 fprintf (stderr
, " is live-on-entry to BB%d ",
1362 fprintf (stderr
, " but is not the default def of ");
1363 print_generic_expr (stderr
, d
, TDF_SLIM
);
1364 fprintf (stderr
, "\n");
1367 fprintf (stderr
, " and there is no default def.\n");
1374 /* An undefined local variable does not need to be very
1376 if (ssa_undefined_value_p (var
, false))
1379 /* The only way this var shouldn't be marked live on entry is
1380 if it occurs in a PHI argument of the block. */
1384 for (gsi
= gsi_start_phis (e
->dest
);
1385 !gsi_end_p (gsi
) && !ok
;
1388 gphi
*phi
= gsi
.phi ();
1389 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1390 if (var
== gimple_phi_arg_def (phi
, z
))
1399 print_generic_expr (stderr
, var
, TDF_SLIM
);
1400 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1402 fprintf (stderr
, "but it is a default def so it should be.\n");
1406 gcc_assert (num
<= 0);