1 /* Liveness for SSA trees.
2 Copyright (C) 2003-2018 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"
31 #include "gimple-pretty-print.h"
32 #include "diagnostic-core.h"
33 #include "gimple-iterator.h"
36 #include "tree-ssa-live.h"
39 #include "ipa-utils.h"
41 #include "stringpool.h"
44 static void verify_live_on_entry (tree_live_info_p
);
47 /* VARMAP maintains a mapping from SSA version number to real variables.
49 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
50 only member of it's own partition. Coalescing will attempt to group any
51 ssa_names which occur in a copy or in a PHI node into the same partition.
53 At the end of out-of-ssa, each partition becomes a "real" variable and is
54 rewritten as a compiler variable.
56 The var_map data structure is used to manage these partitions. It allows
57 partitions to be combined, and determines which partition belongs to what
58 ssa_name or variable, and vice versa. */
61 /* Remove the base table in MAP. */
64 var_map_base_fini (var_map map
)
66 /* Free the basevar info if it is present. */
67 if (map
->partition_to_base_index
!= NULL
)
69 free (map
->partition_to_base_index
);
70 map
->partition_to_base_index
= NULL
;
71 map
->num_basevars
= 0;
74 /* Create a variable partition map of SIZE, initialize and return it. */
77 init_var_map (int size
)
81 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
82 map
->var_partition
= partition_new (size
);
84 map
->partition_to_view
= NULL
;
85 map
->view_to_partition
= NULL
;
86 map
->num_partitions
= size
;
87 map
->partition_size
= size
;
88 map
->num_basevars
= 0;
89 map
->partition_to_base_index
= NULL
;
94 /* Free memory associated with MAP. */
97 delete_var_map (var_map map
)
99 var_map_base_fini (map
);
100 partition_delete (map
->var_partition
);
101 free (map
->partition_to_view
);
102 free (map
->view_to_partition
);
107 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
108 Returns the partition which represents the new partition. If the two
109 partitions cannot be combined, NO_PARTITION is returned. */
112 var_union (var_map map
, tree var1
, tree var2
)
116 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
117 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
119 /* This is independent of partition_to_view. If partition_to_view is
120 on, then whichever one of these partitions is absorbed will never have a
121 dereference into the partition_to_view array any more. */
123 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
124 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
126 gcc_assert (p1
!= NO_PARTITION
);
127 gcc_assert (p2
!= NO_PARTITION
);
132 p3
= partition_union (map
->var_partition
, p1
, p2
);
134 if (map
->partition_to_view
)
135 p3
= map
->partition_to_view
[p3
];
141 /* Compress the partition numbers in MAP such that they fall in the range
142 0..(num_partitions-1) instead of wherever they turned out during
143 the partitioning exercise. This removes any references to unused
144 partitions, thereby allowing bitmaps and other vectors to be much
147 This is implemented such that compaction doesn't affect partitioning.
148 Ie., once partitions are created and possibly merged, running one
149 or more different kind of compaction will not affect the partitions
150 themselves. Their index might change, but all the same variables will
151 still be members of the same partition group. This allows work on reduced
152 sets, and no loss of information when a larger set is later desired.
154 In particular, coalescing can work on partitions which have 2 or more
155 definitions, and then 'recompact' later to include all the single
156 definitions for assignment to program variables. */
159 /* Set MAP back to the initial state of having no partition view. Return a
160 bitmap which has a bit set for each partition number which is in use in the
164 partition_view_init (var_map map
)
170 used
= BITMAP_ALLOC (NULL
);
172 /* Already in a view? Abandon the old one. */
173 if (map
->partition_to_view
)
175 free (map
->partition_to_view
);
176 map
->partition_to_view
= NULL
;
178 if (map
->view_to_partition
)
180 free (map
->view_to_partition
);
181 map
->view_to_partition
= NULL
;
184 /* Find out which partitions are actually referenced. */
185 for (x
= 0; x
< map
->partition_size
; x
++)
187 tmp
= partition_find (map
->var_partition
, x
);
188 if (ssa_name (tmp
) != NULL_TREE
&& !virtual_operand_p (ssa_name (tmp
))
189 && (!has_zero_uses (ssa_name (tmp
))
190 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))
191 || (SSA_NAME_VAR (ssa_name (tmp
))
192 && !VAR_P (SSA_NAME_VAR (ssa_name (tmp
))))))
193 bitmap_set_bit (used
, tmp
);
196 map
->num_partitions
= map
->partition_size
;
201 /* This routine will finalize the view data for MAP based on the partitions
202 set in SELECTED. This is either the same bitmap returned from
203 partition_view_init, or a trimmed down version if some of those partitions
204 were not desired in this view. SELECTED is freed before returning. */
207 partition_view_fini (var_map map
, bitmap selected
)
210 unsigned count
, i
, x
, limit
;
212 gcc_assert (selected
);
214 count
= bitmap_count_bits (selected
);
215 limit
= map
->partition_size
;
217 /* If its a one-to-one ratio, we don't need any view compaction. */
220 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
221 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
222 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
225 /* Give each selected partition an index. */
226 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
228 map
->partition_to_view
[x
] = i
;
229 map
->view_to_partition
[i
] = x
;
232 gcc_assert (i
== count
);
233 map
->num_partitions
= i
;
236 BITMAP_FREE (selected
);
240 /* Create a partition view which includes all the used partitions in MAP. */
243 partition_view_normal (var_map map
)
247 used
= partition_view_init (map
);
248 partition_view_fini (map
, used
);
250 var_map_base_fini (map
);
254 /* Create a partition view in MAP which includes just partitions which occur in
255 the bitmap ONLY. If WANT_BASES is true, create the base variable map
259 partition_view_bitmap (var_map map
, bitmap only
)
262 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
266 used
= partition_view_init (map
);
267 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
269 p
= partition_find (map
->var_partition
, x
);
270 gcc_assert (bitmap_bit_p (used
, p
));
271 bitmap_set_bit (new_partitions
, p
);
273 partition_view_fini (map
, new_partitions
);
275 var_map_base_fini (map
);
279 static bitmap usedvars
;
281 /* Mark VAR as used, so that it'll be preserved during rtl expansion.
282 Returns true if VAR wasn't marked before. */
285 set_is_used (tree var
)
287 return bitmap_set_bit (usedvars
, DECL_UID (var
));
290 /* Return true if VAR is marked as used. */
295 return bitmap_bit_p (usedvars
, DECL_UID (var
));
298 static inline void mark_all_vars_used (tree
*);
300 /* Helper function for mark_all_vars_used, called via walk_tree. */
303 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
306 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
309 if (TREE_CODE (t
) == SSA_NAME
)
312 t
= SSA_NAME_VAR (t
);
317 if (IS_EXPR_CODE_CLASS (c
)
318 && (b
= TREE_BLOCK (t
)) != NULL
)
319 TREE_USED (b
) = true;
321 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
322 fields do not contain vars. */
323 if (TREE_CODE (t
) == TARGET_MEM_REF
)
325 mark_all_vars_used (&TMR_BASE (t
));
326 mark_all_vars_used (&TMR_INDEX (t
));
327 mark_all_vars_used (&TMR_INDEX2 (t
));
332 /* Only need to mark VAR_DECLS; parameters and return results are not
333 eliminated as unused. */
336 /* When a global var becomes used for the first time also walk its
337 initializer (non global ones don't have any). */
338 if (set_is_used (t
) && is_global_var (t
)
339 && DECL_CONTEXT (t
) == current_function_decl
)
340 mark_all_vars_used (&DECL_INITIAL (t
));
342 /* remove_unused_scope_block_p requires information about labels
343 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
344 else if (TREE_CODE (t
) == LABEL_DECL
)
345 /* Although the TREE_USED values that the frontend uses would be
346 acceptable (albeit slightly over-conservative) for our purposes,
347 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
348 must re-compute it here. */
351 if (IS_TYPE_OR_DECL_P (t
))
357 /* Mark the scope block SCOPE and its subblocks unused when they can be
358 possibly eliminated if dead. */
361 mark_scope_block_unused (tree scope
)
364 TREE_USED (scope
) = false;
365 if (!(*debug_hooks
->ignore_block
) (scope
))
366 TREE_USED (scope
) = true;
367 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
368 mark_scope_block_unused (t
);
371 /* Look if the block is dead (by possibly eliminating its dead subblocks)
372 and return true if so.
373 Block is declared dead if:
374 1) No statements are associated with it.
375 2) Declares no live variables
376 3) All subblocks are dead
377 or there is precisely one subblocks and the block
378 has same abstract origin as outer block and declares
379 no variables, so it is pure wrapper.
380 When we are not outputting full debug info, we also eliminate dead variables
381 out of scope blocks to let them to be recycled by GGC and to save copying work
382 done by the inliner. */
385 remove_unused_scope_block_p (tree scope
, bool in_ctor_dtor_block
)
388 bool unused
= !TREE_USED (scope
);
391 /* For ipa-polymorphic-call.c purposes, preserve blocks:
392 1) with BLOCK_ABSTRACT_ORIGIN of a ctor/dtor or their clones */
393 if (inlined_polymorphic_ctor_dtor_block_p (scope
, true))
395 in_ctor_dtor_block
= true;
398 /* 2) inside such blocks, the outermost block with block_ultimate_origin
399 being a FUNCTION_DECL. */
400 else if (in_ctor_dtor_block
)
402 tree fn
= block_ultimate_origin (scope
);
403 if (fn
&& TREE_CODE (fn
) == FUNCTION_DECL
)
405 in_ctor_dtor_block
= false;
410 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
412 next
= &DECL_CHAIN (*t
);
414 /* Debug info of nested function refers to the block of the
415 function. We might stil call it even if all statements
416 of function it was nested into was elliminated.
418 TODO: We can actually look into cgraph to see if function
419 will be output to file. */
420 if (TREE_CODE (*t
) == FUNCTION_DECL
)
423 /* If a decl has a value expr, we need to instantiate it
424 regardless of debug info generation, to avoid codegen
425 differences in memory overlap tests. update_equiv_regs() may
426 indirectly call validate_equiv_mem() to test whether a
427 SET_DEST overlaps with others, and if the value expr changes
428 by virtual register instantiation, we may get end up with
429 different results. */
430 else if (VAR_P (*t
) && DECL_HAS_VALUE_EXPR_P (*t
))
433 /* Remove everything we don't generate debug info for. */
434 else if (DECL_IGNORED_P (*t
))
436 *t
= DECL_CHAIN (*t
);
440 /* When we are outputting debug info, we usually want to output
441 info about optimized-out variables in the scope blocks.
442 Exception are the scope blocks not containing any instructions
443 at all so user can't get into the scopes at first place. */
444 else if (is_used_p (*t
))
446 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
447 /* For labels that are still used in the IL, the decision to
448 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
449 risk having different ordering in debug vs. non-debug builds
450 during inlining or versioning.
451 A label appearing here (we have already checked DECL_IGNORED_P)
452 should not be used in the IL unless it has been explicitly used
453 before, so we use TREE_USED as an approximation. */
454 /* In principle, we should do the same here as for the debug case
455 below, however, when debugging, there might be additional nested
456 levels that keep an upper level with a label live, so we have to
457 force this block to be considered used, too. */
460 /* When we are not doing full debug info, we however can keep around
461 only the used variables for cfgexpand's memory packing saving quite
464 For sake of -g3, we keep around those vars but we don't count this as
465 use of block, so innermost block with no used vars and no instructions
466 can be considered dead. We only want to keep around blocks user can
467 breakpoint into and ask about value of optimized out variables.
469 Similarly we need to keep around types at least until all
470 variables of all nested blocks are gone. We track no
471 information on whether given type is used or not, so we have
472 to keep them even when not emitting debug information,
473 otherwise we may end up remapping variables and their (local)
474 types in different orders depending on whether debug
475 information is being generated. */
477 else if (TREE_CODE (*t
) == TYPE_DECL
478 || debug_info_level
== DINFO_LEVEL_NORMAL
479 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
483 *t
= DECL_CHAIN (*t
);
488 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
489 if (remove_unused_scope_block_p (*t
, in_ctor_dtor_block
))
491 if (BLOCK_SUBBLOCKS (*t
))
493 tree next
= BLOCK_CHAIN (*t
);
494 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
496 *t
= BLOCK_SUBBLOCKS (*t
);
497 while (BLOCK_CHAIN (*t
))
499 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
500 t
= &BLOCK_CHAIN (*t
);
502 BLOCK_CHAIN (*t
) = next
;
503 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
504 t
= &BLOCK_CHAIN (*t
);
508 *t
= BLOCK_CHAIN (*t
);
512 t
= &BLOCK_CHAIN (*t
);
519 /* Outer scope is always used. */
520 else if (!BLOCK_SUPERCONTEXT (scope
)
521 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
523 /* Preserve the block, it is referenced by at least the inline
524 entry point marker. */
525 else if (debug_inline_points
526 && inlined_function_outer_scope_p (scope
))
528 /* Innermost blocks with no live variables nor statements can be always
530 else if (!nsubblocks
)
532 /* When not generating debug info we can eliminate info on unused
534 else if (!flag_auto_profile
&& debug_info_level
== DINFO_LEVEL_NONE
)
536 /* Even for -g0 don't prune outer scopes from artificial
537 functions, otherwise diagnostics using tree_nonartificial_location
538 will not be emitted properly. */
539 if (inlined_function_outer_scope_p (scope
))
544 && TREE_CODE (ao
) == BLOCK
545 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
546 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
548 && TREE_CODE (ao
) == FUNCTION_DECL
549 && DECL_DECLARED_INLINE_P (ao
)
550 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
554 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
556 /* See if this block is important for representation of inlined
557 function. Inlined functions are always represented by block
558 with block_ultimate_origin being set to FUNCTION_DECL and
559 DECL_SOURCE_LOCATION set, unless they expand to nothing... But
560 see above for the case of statement frontiers. */
561 else if (!debug_inline_points
562 && inlined_function_outer_scope_p (scope
))
565 /* Verfify that only blocks with source location set
566 are entry points to the inlined functions. */
567 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
))
568 == UNKNOWN_LOCATION
);
570 TREE_USED (scope
) = !unused
;
574 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
575 eliminated during the tree->rtl conversion process. */
578 mark_all_vars_used (tree
*expr_p
)
580 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
583 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
586 clear_unused_block_pointer_1 (tree
*tp
, int *, void *)
588 if (EXPR_P (*tp
) && TREE_BLOCK (*tp
)
589 && !TREE_USED (TREE_BLOCK (*tp
)))
590 TREE_SET_BLOCK (*tp
, NULL
);
594 /* Set all block pointer in debug or clobber stmt to NULL if the block
595 is unused, so that they will not be streamed out. */
598 clear_unused_block_pointer (void)
601 gimple_stmt_iterator gsi
;
603 FOR_EACH_BB_FN (bb
, cfun
)
604 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
608 gimple
*stmt
= gsi_stmt (gsi
);
610 if (!is_gimple_debug (stmt
) && !gimple_clobber_p (stmt
))
612 b
= gimple_block (stmt
);
613 if (b
&& !TREE_USED (b
))
614 gimple_set_block (stmt
, NULL
);
615 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
616 walk_tree (gimple_op_ptr (stmt
, i
), clear_unused_block_pointer_1
,
621 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
622 indentation level and FLAGS is as in print_generic_expr. */
625 dump_scope_block (FILE *file
, int indent
, tree scope
, dump_flags_t flags
)
630 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
631 TREE_USED (scope
) ? "" : " (unused)",
632 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
633 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
)) != UNKNOWN_LOCATION
)
635 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
636 fprintf (file
, " %s:%i", s
.file
, s
.line
);
638 if (BLOCK_ABSTRACT_ORIGIN (scope
))
640 tree origin
= block_ultimate_origin (scope
);
643 fprintf (file
, " Originating from :");
645 print_generic_decl (file
, origin
, flags
);
647 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
650 if (BLOCK_FRAGMENT_ORIGIN (scope
))
651 fprintf (file
, " Fragment of : #%i",
652 BLOCK_NUMBER (BLOCK_FRAGMENT_ORIGIN (scope
)));
653 else if (BLOCK_FRAGMENT_CHAIN (scope
))
655 fprintf (file
, " Fragment chain :");
656 for (t
= BLOCK_FRAGMENT_CHAIN (scope
); t
;
657 t
= BLOCK_FRAGMENT_CHAIN (t
))
658 fprintf (file
, " #%i", BLOCK_NUMBER (t
));
660 fprintf (file
, " \n");
661 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
663 fprintf (file
, "%*s", indent
, "");
664 print_generic_decl (file
, var
, flags
);
665 fprintf (file
, "\n");
667 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
669 fprintf (file
, "%*s",indent
, "");
670 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
672 fprintf (file
, " (nonlocalized)\n");
674 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
675 dump_scope_block (file
, indent
+ 2, t
, flags
);
676 fprintf (file
, "\n%*s}\n",indent
, "");
679 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
680 is as in print_generic_expr. */
683 debug_scope_block (tree scope
, dump_flags_t flags
)
685 dump_scope_block (stderr
, 0, scope
, flags
);
689 /* Dump the tree of lexical scopes of current_function_decl to FILE.
690 FLAGS is as in print_generic_expr. */
693 dump_scope_blocks (FILE *file
, dump_flags_t flags
)
695 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
699 /* Dump the tree of lexical scopes of current_function_decl to stderr.
700 FLAGS is as in print_generic_expr. */
703 debug_scope_blocks (dump_flags_t flags
)
705 dump_scope_blocks (stderr
, flags
);
708 /* Remove local variables that are not referenced in the IL. */
711 remove_unused_locals (void)
715 unsigned srcidx
, dstidx
, num
;
716 bool have_local_clobbers
= false;
718 /* Removing declarations from lexical blocks when not optimizing is
719 not only a waste of time, it actually causes differences in stack
724 timevar_push (TV_REMOVE_UNUSED
);
726 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
728 usedvars
= BITMAP_ALLOC (NULL
);
730 /* Walk the CFG marking all referenced symbols. */
731 FOR_EACH_BB_FN (bb
, cfun
)
733 gimple_stmt_iterator gsi
;
738 /* Walk the statements. */
739 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
741 gimple
*stmt
= gsi_stmt (gsi
);
742 tree b
= gimple_block (stmt
);
744 if (is_gimple_debug (stmt
))
747 if (gimple_clobber_p (stmt
))
749 have_local_clobbers
= true;
754 TREE_USED (b
) = true;
756 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
757 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
));
760 for (gphi_iterator gpi
= gsi_start_phis (bb
);
767 gphi
*phi
= gpi
.phi ();
769 if (virtual_operand_p (gimple_phi_result (phi
)))
772 def
= gimple_phi_result (phi
);
773 mark_all_vars_used (&def
);
775 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
777 tree arg
= USE_FROM_PTR (arg_p
);
778 int index
= PHI_ARG_INDEX_FROM_USE (arg_p
);
780 LOCATION_BLOCK (gimple_phi_arg_location (phi
, index
));
782 TREE_USED (block
) = true;
783 mark_all_vars_used (&arg
);
787 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
788 if (LOCATION_BLOCK (e
->goto_locus
) != NULL
)
789 TREE_USED (LOCATION_BLOCK (e
->goto_locus
)) = true;
792 /* We do a two-pass approach about the out-of-scope clobbers. We want
793 to remove them if they are the only references to a local variable,
794 but we want to retain them when there's any other. So the first pass
795 ignores them, and the second pass (if there were any) tries to remove
797 if (have_local_clobbers
)
798 FOR_EACH_BB_FN (bb
, cfun
)
800 gimple_stmt_iterator gsi
;
802 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
804 gimple
*stmt
= gsi_stmt (gsi
);
805 tree b
= gimple_block (stmt
);
807 if (gimple_clobber_p (stmt
))
809 tree lhs
= gimple_assign_lhs (stmt
);
810 tree base
= get_base_address (lhs
);
811 /* Remove clobbers referencing unused vars, or clobbers
812 with MEM_REF lhs referencing uninitialized pointers. */
813 if ((VAR_P (base
) && !is_used_p (base
))
814 || (TREE_CODE (lhs
) == MEM_REF
815 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
816 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs
, 0))
817 && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs
, 0)))
820 unlink_stmt_vdef (stmt
);
821 gsi_remove (&gsi
, true);
826 TREE_USED (b
) = true;
832 if (cfun
->has_simduid_loops
)
835 FOR_EACH_LOOP (loop
, 0)
836 if (loop
->simduid
&& !is_used_p (loop
->simduid
))
837 loop
->simduid
= NULL_TREE
;
840 cfun
->has_local_explicit_reg_vars
= false;
842 /* Remove unmarked local and global vars from local_decls. */
843 num
= vec_safe_length (cfun
->local_decls
);
844 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
846 var
= (*cfun
->local_decls
)[srcidx
];
849 if (!is_used_p (var
))
852 if (cfun
->nonlocal_goto_save_area
853 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
854 cfun
->nonlocal_goto_save_area
= NULL
;
855 /* Release any default def associated with var. */
856 if ((def
= ssa_default_def (cfun
, var
)) != NULL_TREE
)
858 set_ssa_default_def (cfun
, var
, NULL_TREE
);
859 release_ssa_name (def
);
864 if (VAR_P (var
) && DECL_HARD_REGISTER (var
) && !is_global_var (var
))
865 cfun
->has_local_explicit_reg_vars
= true;
867 if (srcidx
!= dstidx
)
868 (*cfun
->local_decls
)[dstidx
] = var
;
873 statistics_counter_event (cfun
, "unused VAR_DECLs removed", num
- dstidx
);
874 cfun
->local_decls
->truncate (dstidx
);
877 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
),
878 polymorphic_ctor_dtor_p (current_function_decl
,
880 clear_unused_block_pointer ();
882 BITMAP_FREE (usedvars
);
884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
886 fprintf (dump_file
, "Scope blocks after cleanups:\n");
887 dump_scope_blocks (dump_file
, dump_flags
);
890 timevar_pop (TV_REMOVE_UNUSED
);
893 /* Allocate and return a new live range information object base on MAP. */
895 static tree_live_info_p
896 new_tree_live_info (var_map map
)
898 tree_live_info_p live
;
901 live
= XNEW (struct tree_live_info_d
);
903 live
->num_blocks
= last_basic_block_for_fn (cfun
);
905 bitmap_obstack_initialize (&live
->livein_obstack
);
906 bitmap_obstack_initialize (&live
->liveout_obstack
);
907 live
->livein
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
908 FOR_EACH_BB_FN (bb
, cfun
)
909 bitmap_initialize (&live
->livein
[bb
->index
], &live
->livein_obstack
);
911 live
->liveout
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
912 FOR_EACH_BB_FN (bb
, cfun
)
913 bitmap_initialize (&live
->liveout
[bb
->index
], &live
->liveout_obstack
);
915 live
->work_stack
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
916 live
->stack_top
= live
->work_stack
;
918 live
->global
= BITMAP_ALLOC (NULL
);
923 /* Free storage for live range info object LIVE. */
926 delete_tree_live_info (tree_live_info_p live
)
930 bitmap_obstack_release (&live
->livein_obstack
);
935 bitmap_obstack_release (&live
->liveout_obstack
);
936 free (live
->liveout
);
938 BITMAP_FREE (live
->global
);
939 free (live
->work_stack
);
944 /* Visit basic block BB and propagate any required live on entry bits from
945 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
946 TMP is a temporary work bitmap which is passed in to avoid reallocating
950 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
)
958 gcc_checking_assert (!bitmap_bit_p (visited
, bb
->index
));
959 bitmap_set_bit (visited
, bb
->index
);
961 loe
= live_on_entry (live
, bb
);
963 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
966 if (pred_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
968 /* Variables live-on-entry from BB that aren't defined in the
969 predecessor block. This should be the live on entry vars to pred.
970 Note that liveout is the DEFs in a block while live on entry is
972 Add these bits to live-on-entry for the pred. if there are any
973 changes, and pred_bb has been visited already, add it to the
975 change
= bitmap_ior_and_compl_into (live_on_entry (live
, pred_bb
),
976 loe
, &live
->liveout
[pred_bb
->index
]);
978 && bitmap_bit_p (visited
, pred_bb
->index
))
980 bitmap_clear_bit (visited
, pred_bb
->index
);
981 *(live
->stack_top
)++ = pred_bb
->index
;
987 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
988 of all the variables. */
991 live_worklist (tree_live_info_p live
)
995 auto_sbitmap
visited (last_basic_block_for_fn (cfun
) + 1);
997 bitmap_clear (visited
);
999 /* Visit all the blocks in reverse order and propagate live on entry values
1000 into the predecessors blocks. */
1001 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
1002 loe_visit_block (live
, bb
, visited
);
1004 /* Process any blocks which require further iteration. */
1005 while (live
->stack_top
!= live
->work_stack
)
1007 b
= *--(live
->stack_top
);
1008 loe_visit_block (live
, BASIC_BLOCK_FOR_FN (cfun
, b
), visited
);
1013 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1014 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1015 in the liveout vector. */
1018 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1023 basic_block def_bb
= NULL
;
1024 imm_use_iterator imm_iter
;
1025 bool global
= false;
1027 p
= var_to_partition (live
->map
, ssa_name
);
1028 if (p
== NO_PARTITION
)
1031 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1034 def_bb
= gimple_bb (stmt
);
1035 /* Mark defs in liveout bitmap temporarily. */
1037 bitmap_set_bit (&live
->liveout
[def_bb
->index
], p
);
1040 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1042 /* An undefined local variable does not need to be very alive. */
1043 if (ssa_undefined_value_p (ssa_name
, false))
1046 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1047 add it to the list of live on entry blocks. */
1048 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1050 gimple
*use_stmt
= USE_STMT (use
);
1051 basic_block add_block
= NULL
;
1053 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1055 /* Uses in PHI's are considered to be live at exit of the SRC block
1056 as this is where a copy would be inserted. Check to see if it is
1057 defined in that block, or whether its live on entry. */
1058 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1059 edge e
= gimple_phi_arg_edge (as_a
<gphi
*> (use_stmt
), index
);
1060 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1062 if (e
->src
!= def_bb
)
1066 else if (is_gimple_debug (use_stmt
))
1070 /* If its not defined in this block, its live on entry. */
1071 basic_block use_bb
= gimple_bb (use_stmt
);
1072 if (use_bb
!= def_bb
)
1076 /* If there was a live on entry use, set the bit. */
1080 bitmap_set_bit (&live
->livein
[add_block
->index
], p
);
1084 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1085 on entry blocks between the def and all the uses. */
1087 bitmap_set_bit (live
->global
, p
);
1091 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1094 calculate_live_on_exit (tree_live_info_p liveinfo
)
1100 /* live on entry calculations used liveout vectors for defs, clear them. */
1101 FOR_EACH_BB_FN (bb
, cfun
)
1102 bitmap_clear (&liveinfo
->liveout
[bb
->index
]);
1104 /* Set all the live-on-exit bits for uses in PHIs. */
1105 FOR_EACH_BB_FN (bb
, cfun
)
1110 /* Mark the PHI arguments which are live on exit to the pred block. */
1111 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1113 gphi
*phi
= gsi
.phi ();
1114 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1116 tree t
= PHI_ARG_DEF (phi
, i
);
1119 if (TREE_CODE (t
) != SSA_NAME
)
1122 p
= var_to_partition (liveinfo
->map
, t
);
1123 if (p
== NO_PARTITION
)
1125 e
= gimple_phi_arg_edge (phi
, i
);
1126 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1127 bitmap_set_bit (&liveinfo
->liveout
[e
->src
->index
], p
);
1131 /* Add each successors live on entry to this bock live on exit. */
1132 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1133 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1134 bitmap_ior_into (&liveinfo
->liveout
[bb
->index
],
1135 live_on_entry (liveinfo
, e
->dest
));
1140 /* Given partition map MAP, calculate all the live on entry bitmaps for
1141 each partition. Return a new live info object. */
1144 calculate_live_ranges (var_map map
, bool want_livein
)
1148 tree_live_info_p live
;
1150 live
= new_tree_live_info (map
);
1151 for (i
= 0; i
< num_var_partitions (map
); i
++)
1153 var
= partition_to_var (map
, i
);
1154 if (var
!= NULL_TREE
)
1155 set_var_live_on_entry (var
, live
);
1158 live_worklist (live
);
1161 verify_live_on_entry (live
);
1163 calculate_live_on_exit (live
);
1167 bitmap_obstack_release (&live
->livein_obstack
);
1168 free (live
->livein
);
1169 live
->livein
= NULL
;
1176 /* Output partition map MAP to file F. */
1179 dump_var_map (FILE *f
, var_map map
)
1185 fprintf (f
, "\nPartition map \n\n");
1187 for (x
= 0; x
< map
->num_partitions
; x
++)
1189 if (map
->view_to_partition
!= NULL
)
1190 p
= map
->view_to_partition
[x
];
1194 if (ssa_name (p
) == NULL_TREE
1195 || virtual_operand_p (ssa_name (p
)))
1199 for (y
= 1; y
< num_ssa_names
; y
++)
1201 p
= partition_find (map
->var_partition
, y
);
1202 if (map
->partition_to_view
)
1203 p
= map
->partition_to_view
[p
];
1208 fprintf (f
, "Partition %d (", x
);
1209 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1212 fprintf (f
, "%d ", y
);
1222 /* Generic dump for the above. */
1225 debug (_var_map
&ref
)
1227 dump_var_map (stderr
, &ref
);
1231 debug (_var_map
*ptr
)
1236 fprintf (stderr
, "<nil>\n");
1240 /* Output live range info LIVE to file F, controlled by FLAG. */
1243 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1247 var_map map
= live
->map
;
1250 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1252 FOR_EACH_BB_FN (bb
, cfun
)
1254 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1255 EXECUTE_IF_SET_IN_BITMAP (&live
->livein
[bb
->index
], 0, i
, bi
)
1257 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1264 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1266 FOR_EACH_BB_FN (bb
, cfun
)
1268 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1269 EXECUTE_IF_SET_IN_BITMAP (&live
->liveout
[bb
->index
], 0, i
, bi
)
1271 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1280 /* Generic dump for the above. */
1283 debug (tree_live_info_d
&ref
)
1285 dump_live_info (stderr
, &ref
, 0);
1289 debug (tree_live_info_d
*ptr
)
1294 fprintf (stderr
, "<nil>\n");
1298 /* Verify that the info in LIVE matches the current cfg. */
1301 verify_live_on_entry (tree_live_info_p live
)
1310 var_map map
= live
->map
;
1312 /* Check for live on entry partitions and report those with a DEF in
1313 the program. This will typically mean an optimization has done
1315 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1317 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1319 int entry_block
= e
->dest
->index
;
1320 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1322 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1327 var
= partition_to_var (map
, i
);
1328 stmt
= SSA_NAME_DEF_STMT (var
);
1329 tmp
= gimple_bb (stmt
);
1330 if (SSA_NAME_VAR (var
))
1331 d
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1333 loe
= live_on_entry (live
, e
->dest
);
1334 if (loe
&& bitmap_bit_p (loe
, i
))
1336 if (!gimple_nop_p (stmt
))
1339 print_generic_expr (stderr
, var
, TDF_SLIM
);
1340 fprintf (stderr
, " is defined ");
1342 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1343 fprintf (stderr
, "by:\n");
1344 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1345 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1347 fprintf (stderr
, " So it appears to have multiple defs.\n");
1354 print_generic_expr (stderr
, var
, TDF_SLIM
);
1355 fprintf (stderr
, " is live-on-entry to BB%d ",
1359 fprintf (stderr
, " but is not the default def of ");
1360 print_generic_expr (stderr
, d
, TDF_SLIM
);
1361 fprintf (stderr
, "\n");
1364 fprintf (stderr
, " and there is no default def.\n");
1371 /* An undefined local variable does not need to be very
1373 if (ssa_undefined_value_p (var
, false))
1376 /* The only way this var shouldn't be marked live on entry is
1377 if it occurs in a PHI argument of the block. */
1381 for (gsi
= gsi_start_phis (e
->dest
);
1382 !gsi_end_p (gsi
) && !ok
;
1385 gphi
*phi
= gsi
.phi ();
1386 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1387 if (var
== gimple_phi_arg_def (phi
, z
))
1395 /* Expand adds unused default defs for PARM_DECLs and
1396 RESULT_DECLs. They're ok. */
1397 if (has_zero_uses (var
)
1398 && SSA_NAME_VAR (var
)
1399 && !VAR_P (SSA_NAME_VAR (var
)))
1402 print_generic_expr (stderr
, var
, TDF_SLIM
);
1403 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1405 fprintf (stderr
, "but it is a default def so it should be.\n");
1409 gcc_assert (num
<= 0);