1 /* Liveness for SSA trees.
2 Copyright (C) 2003-2020 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 #include "gimple-walk.h"
47 static void verify_live_on_entry (tree_live_info_p
);
50 /* VARMAP maintains a mapping from SSA version number to real variables.
52 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
53 only member of it's own partition. Coalescing will attempt to group any
54 ssa_names which occur in a copy or in a PHI node into the same partition.
56 At the end of out-of-ssa, each partition becomes a "real" variable and is
57 rewritten as a compiler variable.
59 The var_map data structure is used to manage these partitions. It allows
60 partitions to be combined, and determines which partition belongs to what
61 ssa_name or variable, and vice versa. */
64 /* Remove the base table in MAP. */
67 var_map_base_fini (var_map map
)
69 /* Free the basevar info if it is present. */
70 if (map
->partition_to_base_index
!= NULL
)
72 free (map
->partition_to_base_index
);
73 map
->partition_to_base_index
= NULL
;
74 map
->num_basevars
= 0;
77 /* Create a variable partition map of SIZE for region, initialize and return
78 it. Region is a loop if LOOP is non-NULL, otherwise is the current
82 init_var_map (int size
, class loop
*loop
)
86 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
87 map
->var_partition
= partition_new (size
);
89 map
->partition_to_view
= NULL
;
90 map
->view_to_partition
= NULL
;
91 map
->num_partitions
= size
;
92 map
->partition_size
= size
;
93 map
->num_basevars
= 0;
94 map
->partition_to_base_index
= NULL
;
98 map
->bmp_bbs
= BITMAP_ALLOC (NULL
);
99 map
->outofssa_p
= false;
100 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
101 for (unsigned i
= 0; i
< loop
->num_nodes
; ++i
)
103 bitmap_set_bit (map
->bmp_bbs
, bbs
[i
]->index
);
104 map
->vec_bbs
.safe_push (bbs
[i
]);
111 map
->outofssa_p
= true;
113 FOR_EACH_BB_FN (bb
, cfun
)
114 map
->vec_bbs
.safe_push (bb
);
120 /* Free memory associated with MAP. */
123 delete_var_map (var_map map
)
125 var_map_base_fini (map
);
126 partition_delete (map
->var_partition
);
127 free (map
->partition_to_view
);
128 free (map
->view_to_partition
);
130 BITMAP_FREE (map
->bmp_bbs
);
131 map
->vec_bbs
.release ();
136 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
137 Returns the partition which represents the new partition. If the two
138 partitions cannot be combined, NO_PARTITION is returned. */
141 var_union (var_map map
, tree var1
, tree var2
)
145 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
146 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
148 /* This is independent of partition_to_view. If partition_to_view is
149 on, then whichever one of these partitions is absorbed will never have a
150 dereference into the partition_to_view array any more. */
152 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
153 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
155 gcc_assert (p1
!= NO_PARTITION
);
156 gcc_assert (p2
!= NO_PARTITION
);
161 p3
= partition_union (map
->var_partition
, p1
, p2
);
163 if (map
->partition_to_view
)
164 p3
= map
->partition_to_view
[p3
];
170 /* Compress the partition numbers in MAP such that they fall in the range
171 0..(num_partitions-1) instead of wherever they turned out during
172 the partitioning exercise. This removes any references to unused
173 partitions, thereby allowing bitmaps and other vectors to be much
176 This is implemented such that compaction doesn't affect partitioning.
177 Ie., once partitions are created and possibly merged, running one
178 or more different kind of compaction will not affect the partitions
179 themselves. Their index might change, but all the same variables will
180 still be members of the same partition group. This allows work on reduced
181 sets, and no loss of information when a larger set is later desired.
183 In particular, coalescing can work on partitions which have 2 or more
184 definitions, and then 'recompact' later to include all the single
185 definitions for assignment to program variables. */
188 /* Set MAP back to the initial state of having no partition view. Return a
189 bitmap which has a bit set for each partition number which is in use in the
193 partition_view_init (var_map map
)
199 used
= BITMAP_ALLOC (NULL
);
201 /* Already in a view? Abandon the old one. */
202 if (map
->partition_to_view
)
204 free (map
->partition_to_view
);
205 map
->partition_to_view
= NULL
;
207 if (map
->view_to_partition
)
209 free (map
->view_to_partition
);
210 map
->view_to_partition
= NULL
;
213 /* Find out which partitions are actually referenced. */
214 for (x
= 0; x
< map
->partition_size
; x
++)
216 tmp
= partition_find (map
->var_partition
, x
);
217 if (ssa_name (tmp
) != NULL_TREE
&& !virtual_operand_p (ssa_name (tmp
))
218 && (!has_zero_uses (ssa_name (tmp
))
219 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))
220 || (SSA_NAME_VAR (ssa_name (tmp
))
221 && !VAR_P (SSA_NAME_VAR (ssa_name (tmp
))))))
222 bitmap_set_bit (used
, tmp
);
225 map
->num_partitions
= map
->partition_size
;
230 /* This routine will finalize the view data for MAP based on the partitions
231 set in SELECTED. This is either the same bitmap returned from
232 partition_view_init, or a trimmed down version if some of those partitions
233 were not desired in this view. SELECTED is freed before returning. */
236 partition_view_fini (var_map map
, bitmap selected
)
239 unsigned count
, i
, x
, limit
;
241 gcc_assert (selected
);
243 count
= bitmap_count_bits (selected
);
244 limit
= map
->partition_size
;
246 /* If its a one-to-one ratio, we don't need any view compaction. */
249 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
250 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
251 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
254 /* Give each selected partition an index. */
255 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
257 map
->partition_to_view
[x
] = i
;
258 map
->view_to_partition
[i
] = x
;
261 gcc_assert (i
== count
);
262 map
->num_partitions
= i
;
265 BITMAP_FREE (selected
);
269 /* Create a partition view which includes all the used partitions in MAP. */
272 partition_view_normal (var_map map
)
276 used
= partition_view_init (map
);
277 partition_view_fini (map
, used
);
279 var_map_base_fini (map
);
283 /* Create a partition view in MAP which includes just partitions which occur in
284 the bitmap ONLY. If WANT_BASES is true, create the base variable map
288 partition_view_bitmap (var_map map
, bitmap only
)
291 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
295 used
= partition_view_init (map
);
296 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
298 p
= partition_find (map
->var_partition
, x
);
299 gcc_assert (bitmap_bit_p (used
, p
));
300 bitmap_set_bit (new_partitions
, p
);
302 partition_view_fini (map
, new_partitions
);
304 var_map_base_fini (map
);
308 static bitmap usedvars
;
310 /* Mark VAR as used, so that it'll be preserved during rtl expansion.
311 Returns true if VAR wasn't marked before. */
314 set_is_used (tree var
)
316 return bitmap_set_bit (usedvars
, DECL_UID (var
));
319 /* Return true if VAR is marked as used. */
324 return bitmap_bit_p (usedvars
, DECL_UID (var
));
327 static inline void mark_all_vars_used (tree
*);
329 /* Helper function for mark_all_vars_used, called via walk_tree. */
332 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
335 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
338 if (TREE_CODE (t
) == SSA_NAME
)
341 t
= SSA_NAME_VAR (t
);
346 if (IS_EXPR_CODE_CLASS (c
)
347 && (b
= TREE_BLOCK (t
)) != NULL
)
348 TREE_USED (b
) = true;
350 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
351 fields do not contain vars. */
352 if (TREE_CODE (t
) == TARGET_MEM_REF
)
354 mark_all_vars_used (&TMR_BASE (t
));
355 mark_all_vars_used (&TMR_INDEX (t
));
356 mark_all_vars_used (&TMR_INDEX2 (t
));
361 /* Only need to mark VAR_DECLS; parameters and return results are not
362 eliminated as unused. */
365 /* When a global var becomes used for the first time also walk its
366 initializer (non global ones don't have any). */
367 if (set_is_used (t
) && is_global_var (t
)
368 && DECL_CONTEXT (t
) == current_function_decl
)
369 mark_all_vars_used (&DECL_INITIAL (t
));
371 /* remove_unused_scope_block_p requires information about labels
372 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
373 else if (TREE_CODE (t
) == LABEL_DECL
)
374 /* Although the TREE_USED values that the frontend uses would be
375 acceptable (albeit slightly over-conservative) for our purposes,
376 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
377 must re-compute it here. */
380 if (IS_TYPE_OR_DECL_P (t
))
386 /* Mark the scope block SCOPE and its subblocks unused when they can be
387 possibly eliminated if dead. */
390 mark_scope_block_unused (tree scope
)
393 TREE_USED (scope
) = false;
394 if (!(*debug_hooks
->ignore_block
) (scope
))
395 TREE_USED (scope
) = true;
396 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
397 mark_scope_block_unused (t
);
400 /* Look if the block is dead (by possibly eliminating its dead subblocks)
401 and return true if so.
402 Block is declared dead if:
403 1) No statements are associated with it.
404 2) Declares no live variables
405 3) All subblocks are dead
406 or there is precisely one subblocks and the block
407 has same abstract origin as outer block and declares
408 no variables, so it is pure wrapper.
409 When we are not outputting full debug info, we also eliminate dead variables
410 out of scope blocks to let them to be recycled by GGC and to save copying work
411 done by the inliner. */
414 remove_unused_scope_block_p (tree scope
, bool in_ctor_dtor_block
)
417 bool unused
= !TREE_USED (scope
);
420 /* For ipa-polymorphic-call.c purposes, preserve blocks:
421 1) with BLOCK_ABSTRACT_ORIGIN of a ctor/dtor or their clones */
422 if (inlined_polymorphic_ctor_dtor_block_p (scope
, true))
424 in_ctor_dtor_block
= true;
427 /* 2) inside such blocks, the outermost block with block_ultimate_origin
428 being a FUNCTION_DECL. */
429 else if (in_ctor_dtor_block
)
431 tree fn
= block_ultimate_origin (scope
);
432 if (fn
&& TREE_CODE (fn
) == FUNCTION_DECL
)
434 in_ctor_dtor_block
= false;
439 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
441 next
= &DECL_CHAIN (*t
);
443 /* Debug info of nested function refers to the block of the
444 function. We might stil call it even if all statements
445 of function it was nested into was elliminated.
447 TODO: We can actually look into cgraph to see if function
448 will be output to file. */
449 if (TREE_CODE (*t
) == FUNCTION_DECL
)
452 /* If a decl has a value expr, we need to instantiate it
453 regardless of debug info generation, to avoid codegen
454 differences in memory overlap tests. update_equiv_regs() may
455 indirectly call validate_equiv_mem() to test whether a
456 SET_DEST overlaps with others, and if the value expr changes
457 by virtual register instantiation, we may get end up with
458 different results. */
459 else if (VAR_P (*t
) && DECL_HAS_VALUE_EXPR_P (*t
))
462 /* Remove everything we don't generate debug info for. */
463 else if (DECL_IGNORED_P (*t
))
465 *t
= DECL_CHAIN (*t
);
469 /* When we are outputting debug info, we usually want to output
470 info about optimized-out variables in the scope blocks.
471 Exception are the scope blocks not containing any instructions
472 at all so user can't get into the scopes at first place. */
473 else if (is_used_p (*t
))
475 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
476 /* For labels that are still used in the IL, the decision to
477 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
478 risk having different ordering in debug vs. non-debug builds
479 during inlining or versioning.
480 A label appearing here (we have already checked DECL_IGNORED_P)
481 should not be used in the IL unless it has been explicitly used
482 before, so we use TREE_USED as an approximation. */
483 /* In principle, we should do the same here as for the debug case
484 below, however, when debugging, there might be additional nested
485 levels that keep an upper level with a label live, so we have to
486 force this block to be considered used, too. */
489 /* When we are not doing full debug info, we however can keep around
490 only the used variables for cfgexpand's memory packing saving quite
493 For sake of -g3, we keep around those vars but we don't count this as
494 use of block, so innermost block with no used vars and no instructions
495 can be considered dead. We only want to keep around blocks user can
496 breakpoint into and ask about value of optimized out variables.
498 Similarly we need to keep around types at least until all
499 variables of all nested blocks are gone. We track no
500 information on whether given type is used or not, so we have
501 to keep them even when not emitting debug information,
502 otherwise we may end up remapping variables and their (local)
503 types in different orders depending on whether debug
504 information is being generated. */
506 else if (TREE_CODE (*t
) == TYPE_DECL
507 || debug_info_level
== DINFO_LEVEL_NORMAL
508 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
512 *t
= DECL_CHAIN (*t
);
517 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
518 if (remove_unused_scope_block_p (*t
, in_ctor_dtor_block
))
520 if (BLOCK_SUBBLOCKS (*t
))
522 tree next
= BLOCK_CHAIN (*t
);
523 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
525 *t
= BLOCK_SUBBLOCKS (*t
);
526 while (BLOCK_CHAIN (*t
))
528 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
529 t
= &BLOCK_CHAIN (*t
);
531 BLOCK_CHAIN (*t
) = next
;
532 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
533 t
= &BLOCK_CHAIN (*t
);
537 *t
= BLOCK_CHAIN (*t
);
541 t
= &BLOCK_CHAIN (*t
);
548 /* Outer scope is always used. */
549 else if (!BLOCK_SUPERCONTEXT (scope
)
550 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
552 /* Innermost blocks with no live variables nor statements can be always
554 else if (!nsubblocks
)
556 /* When not generating debug info we can eliminate info on unused
558 else if (!flag_auto_profile
&& debug_info_level
== DINFO_LEVEL_NONE
559 && !optinfo_wants_inlining_info_p ())
561 /* Even for -g0 don't prune outer scopes from artificial
562 functions, otherwise diagnostics using tree_nonartificial_location
563 will not be emitted properly. */
564 if (inlined_function_outer_scope_p (scope
))
566 tree ao
= BLOCK_ORIGIN (scope
);
568 && TREE_CODE (ao
) == FUNCTION_DECL
569 && DECL_DECLARED_INLINE_P (ao
)
570 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
574 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
576 /* See if this block is important for representation of inlined
577 function. Inlined functions are always represented by block
578 with block_ultimate_origin being set to FUNCTION_DECL and
579 DECL_SOURCE_LOCATION set, unless they expand to nothing... */
580 else if (inlined_function_outer_scope_p (scope
))
583 /* Verfify that only blocks with source location set
584 are entry points to the inlined functions. */
585 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
))
586 == UNKNOWN_LOCATION
);
588 TREE_USED (scope
) = !unused
;
592 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
593 eliminated during the tree->rtl conversion process. */
596 mark_all_vars_used (tree
*expr_p
)
598 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
601 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
604 clear_unused_block_pointer_1 (tree
*tp
, int *, void *)
606 if (EXPR_P (*tp
) && TREE_BLOCK (*tp
)
607 && !TREE_USED (TREE_BLOCK (*tp
)))
608 TREE_SET_BLOCK (*tp
, NULL
);
612 /* Set all block pointer in debug or clobber stmt to NULL if the block
613 is unused, so that they will not be streamed out. */
616 clear_unused_block_pointer (void)
619 gimple_stmt_iterator gsi
;
621 FOR_EACH_BB_FN (bb
, cfun
)
622 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
629 stmt
= gsi_stmt (gsi
);
630 if (!is_gimple_debug (stmt
) && !gimple_clobber_p (stmt
))
632 b
= gimple_block (stmt
);
633 if (b
&& !TREE_USED (b
))
635 /* Elide debug marker stmts that have an associated BLOCK from an
636 inline instance removed with also the outermost scope BLOCK of
637 said inline instance removed. If the outermost scope BLOCK of
638 said inline instance is preserved use that in place of the
639 removed BLOCK. That keeps the marker associated to the correct
640 inline instance (or no inline instance in case it was not from
641 an inline instance). */
642 if (gimple_debug_nonbind_marker_p (stmt
)
643 && BLOCK_ABSTRACT_ORIGIN (b
))
645 while (TREE_CODE (b
) == BLOCK
646 && !inlined_function_outer_scope_p (b
))
647 b
= BLOCK_SUPERCONTEXT (b
);
648 if (TREE_CODE (b
) == BLOCK
)
652 gimple_set_block (stmt
, b
);
655 gsi_remove (&gsi
, true);
661 gimple_set_block (stmt
, NULL
);
663 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
664 walk_tree (gimple_op_ptr (stmt
, i
), clear_unused_block_pointer_1
,
669 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
670 indentation level and FLAGS is as in print_generic_expr. */
673 dump_scope_block (FILE *file
, int indent
, tree scope
, dump_flags_t flags
)
678 fprintf (file
, "\n%*s{ Scope block #%i%s",indent
, "" , BLOCK_NUMBER (scope
),
679 TREE_USED (scope
) ? "" : " (unused)");
680 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
)) != UNKNOWN_LOCATION
)
682 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
683 fprintf (file
, " %s:%i", s
.file
, s
.line
);
685 if (BLOCK_ABSTRACT_ORIGIN (scope
))
687 tree origin
= block_ultimate_origin (scope
);
690 fprintf (file
, " Originating from :");
692 print_generic_decl (file
, origin
, flags
);
694 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
697 if (BLOCK_FRAGMENT_ORIGIN (scope
))
698 fprintf (file
, " Fragment of : #%i",
699 BLOCK_NUMBER (BLOCK_FRAGMENT_ORIGIN (scope
)));
700 else if (BLOCK_FRAGMENT_CHAIN (scope
))
702 fprintf (file
, " Fragment chain :");
703 for (t
= BLOCK_FRAGMENT_CHAIN (scope
); t
;
704 t
= BLOCK_FRAGMENT_CHAIN (t
))
705 fprintf (file
, " #%i", BLOCK_NUMBER (t
));
707 fprintf (file
, " \n");
708 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
710 fprintf (file
, "%*s", indent
, "");
711 print_generic_decl (file
, var
, flags
);
712 fprintf (file
, "\n");
714 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
716 fprintf (file
, "%*s",indent
, "");
717 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
719 fprintf (file
, " (nonlocalized)\n");
721 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
722 dump_scope_block (file
, indent
+ 2, t
, flags
);
723 fprintf (file
, "\n%*s}\n",indent
, "");
726 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
727 is as in print_generic_expr. */
730 debug_scope_block (tree scope
, dump_flags_t flags
)
732 dump_scope_block (stderr
, 0, scope
, flags
);
736 /* Dump the tree of lexical scopes of current_function_decl to FILE.
737 FLAGS is as in print_generic_expr. */
740 dump_scope_blocks (FILE *file
, dump_flags_t flags
)
742 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
746 /* Dump the tree of lexical scopes of current_function_decl to stderr.
747 FLAGS is as in print_generic_expr. */
750 debug_scope_blocks (dump_flags_t flags
)
752 dump_scope_blocks (stderr
, flags
);
755 /* Remove local variables that are not referenced in the IL. */
758 remove_unused_locals (void)
762 unsigned srcidx
, dstidx
, num
;
763 bool have_local_clobbers
= false;
765 /* Removing declarations from lexical blocks when not optimizing is
766 not only a waste of time, it actually causes differences in stack
771 timevar_push (TV_REMOVE_UNUSED
);
773 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
775 usedvars
= BITMAP_ALLOC (NULL
);
776 auto_bitmap useddebug
;
778 /* Walk the CFG marking all referenced symbols. */
779 FOR_EACH_BB_FN (bb
, cfun
)
781 gimple_stmt_iterator gsi
;
786 /* Walk the statements. */
787 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
789 gimple
*stmt
= gsi_stmt (gsi
);
790 tree b
= gimple_block (stmt
);
792 /* If we wanted to mark the block referenced by the inline
793 entry point marker as used, this would be a good spot to
794 do it. If the block is not otherwise used, the stmt will
795 be cleaned up in clean_unused_block_pointer. */
796 if (is_gimple_debug (stmt
))
798 if (gimple_debug_bind_p (stmt
))
800 tree var
= gimple_debug_bind_get_var (stmt
);
803 if (!gimple_debug_bind_get_value (stmt
))
804 /* Run the 2nd phase. */
805 have_local_clobbers
= true;
807 bitmap_set_bit (useddebug
, DECL_UID (var
));
813 if (gimple_clobber_p (stmt
))
815 have_local_clobbers
= true;
820 TREE_USED (b
) = true;
822 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
823 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
));
826 for (gphi_iterator gpi
= gsi_start_phis (bb
);
833 gphi
*phi
= gpi
.phi ();
835 if (virtual_operand_p (gimple_phi_result (phi
)))
838 def
= gimple_phi_result (phi
);
839 mark_all_vars_used (&def
);
841 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
843 tree arg
= USE_FROM_PTR (arg_p
);
844 int index
= PHI_ARG_INDEX_FROM_USE (arg_p
);
846 LOCATION_BLOCK (gimple_phi_arg_location (phi
, index
));
848 TREE_USED (block
) = true;
849 mark_all_vars_used (&arg
);
853 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
854 if (LOCATION_BLOCK (e
->goto_locus
) != NULL
)
855 TREE_USED (LOCATION_BLOCK (e
->goto_locus
)) = true;
858 /* We do a two-pass approach about the out-of-scope clobbers. We want
859 to remove them if they are the only references to a local variable,
860 but we want to retain them when there's any other. So the first pass
861 ignores them, and the second pass (if there were any) tries to remove
863 if (have_local_clobbers
)
864 FOR_EACH_BB_FN (bb
, cfun
)
866 gimple_stmt_iterator gsi
;
868 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
870 gimple
*stmt
= gsi_stmt (gsi
);
871 tree b
= gimple_block (stmt
);
873 if (gimple_clobber_p (stmt
))
875 tree lhs
= gimple_assign_lhs (stmt
);
876 tree base
= get_base_address (lhs
);
877 /* Remove clobbers referencing unused vars, or clobbers
878 with MEM_REF lhs referencing uninitialized pointers. */
879 if ((VAR_P (base
) && !is_used_p (base
))
880 || (TREE_CODE (lhs
) == MEM_REF
881 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
882 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs
, 0))
883 && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs
, 0)))
886 unlink_stmt_vdef (stmt
);
887 gsi_remove (&gsi
, true);
892 TREE_USED (b
) = true;
894 else if (gimple_debug_bind_p (stmt
))
896 tree var
= gimple_debug_bind_get_var (stmt
);
898 && !bitmap_bit_p (useddebug
, DECL_UID (var
))
901 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
902 fprintf (dump_file
, "Dead debug bind reset to %u\n",
904 gsi_remove (&gsi
, true);
912 if (cfun
->has_simduid_loops
)
915 FOR_EACH_LOOP (loop
, 0)
916 if (loop
->simduid
&& !is_used_p (loop
->simduid
))
917 loop
->simduid
= NULL_TREE
;
920 cfun
->has_local_explicit_reg_vars
= false;
922 /* Remove unmarked local and global vars from local_decls. */
923 num
= vec_safe_length (cfun
->local_decls
);
924 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
926 var
= (*cfun
->local_decls
)[srcidx
];
929 if (!is_used_p (var
))
932 if (cfun
->nonlocal_goto_save_area
933 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
934 cfun
->nonlocal_goto_save_area
= NULL
;
935 /* Release any default def associated with var. */
936 if ((def
= ssa_default_def (cfun
, var
)) != NULL_TREE
)
938 set_ssa_default_def (cfun
, var
, NULL_TREE
);
939 release_ssa_name (def
);
944 if (VAR_P (var
) && DECL_HARD_REGISTER (var
) && !is_global_var (var
))
945 cfun
->has_local_explicit_reg_vars
= true;
947 if (srcidx
!= dstidx
)
948 (*cfun
->local_decls
)[dstidx
] = var
;
953 statistics_counter_event (cfun
, "unused VAR_DECLs removed", num
- dstidx
);
954 cfun
->local_decls
->truncate (dstidx
);
957 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
),
958 polymorphic_ctor_dtor_p (current_function_decl
,
960 clear_unused_block_pointer ();
962 BITMAP_FREE (usedvars
);
964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
966 fprintf (dump_file
, "Scope blocks after cleanups:\n");
967 dump_scope_blocks (dump_file
, dump_flags
);
970 timevar_pop (TV_REMOVE_UNUSED
);
973 /* Allocate and return a new live range information object base on MAP. */
975 static tree_live_info_p
976 new_tree_live_info (var_map map
)
978 tree_live_info_p live
;
981 live
= XNEW (struct tree_live_info_d
);
983 live
->num_blocks
= last_basic_block_for_fn (cfun
);
985 bitmap_obstack_initialize (&live
->livein_obstack
);
986 bitmap_obstack_initialize (&live
->liveout_obstack
);
988 live
->livein
= XCNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
989 live
->liveout
= XCNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
990 for (unsigned i
= 0; map
->vec_bbs
.iterate (i
, &bb
); ++i
)
992 bitmap_initialize (&live
->livein
[bb
->index
], &live
->livein_obstack
);
993 bitmap_initialize (&live
->liveout
[bb
->index
], &live
->liveout_obstack
);
996 live
->work_stack
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
997 live
->stack_top
= live
->work_stack
;
999 live
->global
= BITMAP_ALLOC (NULL
);
1004 /* Free storage for live range info object LIVE. */
1007 delete_tree_live_info (tree_live_info_p live
)
1011 bitmap_obstack_release (&live
->livein_obstack
);
1012 free (live
->livein
);
1016 bitmap_obstack_release (&live
->liveout_obstack
);
1017 free (live
->liveout
);
1019 BITMAP_FREE (live
->global
);
1020 free (live
->work_stack
);
1025 /* Visit basic block BB and propagate any required live on entry bits from
1026 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
1027 TMP is a temporary work bitmap which is passed in to avoid reallocating
1031 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
)
1036 basic_block pred_bb
;
1039 gcc_checking_assert (!bitmap_bit_p (visited
, bb
->index
));
1040 bitmap_set_bit (visited
, bb
->index
);
1042 loe
= live_on_entry (live
, bb
);
1044 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1047 if (!region_contains_p (live
->map
, pred_bb
))
1049 /* Variables live-on-entry from BB that aren't defined in the
1050 predecessor block. This should be the live on entry vars to pred.
1051 Note that liveout is the DEFs in a block while live on entry is
1053 Add these bits to live-on-entry for the pred. if there are any
1054 changes, and pred_bb has been visited already, add it to the
1056 change
= bitmap_ior_and_compl_into (live_on_entry (live
, pred_bb
),
1057 loe
, &live
->liveout
[pred_bb
->index
]);
1059 && bitmap_bit_p (visited
, pred_bb
->index
))
1061 bitmap_clear_bit (visited
, pred_bb
->index
);
1062 *(live
->stack_top
)++ = pred_bb
->index
;
1068 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
1069 of all the variables. */
1072 live_worklist (tree_live_info_p live
)
1076 auto_sbitmap
visited (last_basic_block_for_fn (cfun
) + 1);
1078 bitmap_clear (visited
);
1080 /* Visit region's blocks in reverse order and propagate live on entry values
1081 into the predecessors blocks. */
1082 for (unsigned i
= live
->map
->vec_bbs
.length () - 1;
1083 live
->map
->vec_bbs
.iterate (i
, &bb
); --i
)
1084 loe_visit_block (live
, bb
, visited
);
1086 /* Process any blocks which require further iteration. */
1087 while (live
->stack_top
!= live
->work_stack
)
1089 b
= *--(live
->stack_top
);
1090 loe_visit_block (live
, BASIC_BLOCK_FOR_FN (cfun
, b
), visited
);
1095 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1096 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1097 in the liveout vector. */
1100 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1105 basic_block def_bb
= NULL
;
1106 imm_use_iterator imm_iter
;
1107 bool global
= false;
1109 p
= var_to_partition (live
->map
, ssa_name
);
1110 if (p
== NO_PARTITION
)
1113 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1116 def_bb
= gimple_bb (stmt
);
1117 /* Mark defs in liveout bitmap temporarily. */
1118 if (def_bb
&& region_contains_p (live
->map
, def_bb
))
1119 bitmap_set_bit (&live
->liveout
[def_bb
->index
], p
);
1122 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1124 /* An undefined local variable does not need to be very alive. */
1125 if (ssa_undefined_value_p (ssa_name
, false))
1128 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1129 add it to the list of live on entry blocks. */
1130 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1132 gimple
*use_stmt
= USE_STMT (use
);
1133 basic_block add_block
= NULL
;
1135 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1137 /* Uses in PHI's are considered to be live at exit of the SRC block
1138 as this is where a copy would be inserted. Check to see if it is
1139 defined in that block, or whether its live on entry. */
1140 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1141 edge e
= gimple_phi_arg_edge (as_a
<gphi
*> (use_stmt
), index
);
1142 if (e
->src
!= def_bb
&& region_contains_p (live
->map
, e
->src
))
1145 else if (is_gimple_debug (use_stmt
))
1149 /* If its not defined in this block, its live on entry. */
1150 basic_block use_bb
= gimple_bb (use_stmt
);
1151 if (use_bb
!= def_bb
&& region_contains_p (live
->map
, use_bb
))
1155 /* If there was a live on entry use, set the bit. */
1159 bitmap_set_bit (&live
->livein
[add_block
->index
], p
);
1163 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1164 on entry blocks between the def and all the uses. */
1166 bitmap_set_bit (live
->global
, p
);
1170 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1173 calculate_live_on_exit (tree_live_info_p liveinfo
)
1179 /* live on entry calculations used liveout vectors for defs, clear them. */
1180 for (unsigned i
= 0; liveinfo
->map
->vec_bbs
.iterate (i
, &bb
); ++i
)
1181 bitmap_clear (&liveinfo
->liveout
[bb
->index
]);
1183 /* Set all the live-on-exit bits for uses in PHIs. */
1184 FOR_EACH_BB_FN (bb
, cfun
)
1189 /* Mark the PHI arguments which are live on exit to the pred block. */
1190 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1192 gphi
*phi
= gsi
.phi ();
1193 if (virtual_operand_p (gimple_phi_result (phi
)))
1195 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1197 tree t
= PHI_ARG_DEF (phi
, i
);
1200 if (TREE_CODE (t
) != SSA_NAME
)
1203 p
= var_to_partition (liveinfo
->map
, t
);
1204 if (p
== NO_PARTITION
)
1206 e
= gimple_phi_arg_edge (phi
, i
);
1207 if (region_contains_p (liveinfo
->map
, e
->src
))
1208 bitmap_set_bit (&liveinfo
->liveout
[e
->src
->index
], p
);
1212 if (!region_contains_p (liveinfo
->map
, bb
))
1215 /* Add each successors live on entry to this bock live on exit. */
1216 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1217 if (region_contains_p (liveinfo
->map
, e
->dest
))
1218 bitmap_ior_into (&liveinfo
->liveout
[bb
->index
],
1219 live_on_entry (liveinfo
, e
->dest
));
1224 /* Given partition map MAP, calculate all the live on entry bitmaps for
1225 each partition. Return a new live info object. */
1228 calculate_live_ranges (var_map map
, bool want_livein
)
1232 tree_live_info_p live
;
1234 live
= new_tree_live_info (map
);
1235 for (i
= 0; i
< num_var_partitions (map
); i
++)
1237 var
= partition_to_var (map
, i
);
1238 if (var
!= NULL_TREE
)
1239 set_var_live_on_entry (var
, live
);
1242 live_worklist (live
);
1245 verify_live_on_entry (live
);
1247 calculate_live_on_exit (live
);
1251 bitmap_obstack_release (&live
->livein_obstack
);
1252 free (live
->livein
);
1253 live
->livein
= NULL
;
1259 /* Data structure for compute_live_vars* functions. */
1261 struct compute_live_vars_data
{
1262 /* Vector of bitmaps for live vars indices at the end of basic blocks,
1263 indexed by bb->index. ACTIVE[ENTRY_BLOCK] must be empty bitmap,
1264 ACTIVE[EXIT_BLOCK] is used for STOP_AFTER. */
1265 vec
<bitmap_head
> active
;
1266 /* Work bitmap of currently live variables. */
1268 /* Set of interesting variables. Variables with uids not in this
1269 hash_map are not tracked. */
1270 live_vars_map
*vars
;
1273 /* Callback for walk_stmt_load_store_addr_ops. If OP is a VAR_DECL with
1274 uid set in DATA->vars, enter its corresponding index into bitmap
1278 compute_live_vars_visit (gimple
*, tree op
, tree
, void *pdata
)
1280 compute_live_vars_data
*data
= (compute_live_vars_data
*) pdata
;
1281 op
= get_base_address (op
);
1282 if (op
&& VAR_P (op
))
1283 if (unsigned int *v
= data
->vars
->get (DECL_UID (op
)))
1284 bitmap_set_bit (data
->work
, *v
);
1288 /* Helper routine for compute_live_vars, calculating the sets of live
1289 variables at the end of BB, leaving the result in DATA->work.
1290 If STOP_AFTER is non-NULL, stop processing after that stmt. */
1293 compute_live_vars_1 (basic_block bb
, compute_live_vars_data
*data
,
1298 gimple_stmt_iterator gsi
;
1299 walk_stmt_load_store_addr_fn visit
= compute_live_vars_visit
;
1301 bitmap_clear (data
->work
);
1302 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1303 bitmap_ior_into (data
->work
, &data
->active
[e
->src
->index
]);
1305 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1306 walk_stmt_load_store_addr_ops (gsi_stmt (gsi
), data
, NULL
, NULL
, visit
);
1307 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1309 gimple
*stmt
= gsi_stmt (gsi
);
1311 if (gimple_clobber_p (stmt
))
1313 tree lhs
= gimple_assign_lhs (stmt
);
1315 if (unsigned int *v
= data
->vars
->get (DECL_UID (lhs
)))
1316 bitmap_clear_bit (data
->work
, *v
);
1318 else if (!is_gimple_debug (stmt
))
1319 walk_stmt_load_store_addr_ops (stmt
, data
, visit
, visit
, visit
);
1320 if (stmt
== stop_after
)
1325 /* For function FN and live_vars_map (hash map from DECL_UIDs to a dense set of
1326 indexes of automatic variables VARS, compute which of those variables are
1327 (might be) live at the end of each basic block. */
1330 compute_live_vars (struct function
*fn
, live_vars_map
*vars
)
1332 vec
<bitmap_head
> active
;
1334 /* We approximate the live range of a stack variable by taking the first
1335 mention of its name as starting point(s), and by the end-of-scope
1336 death clobber added by gimplify as ending point(s) of the range.
1337 This overapproximates in the case we for instance moved an address-taken
1338 operation upward, without also moving a dereference to it upwards.
1339 But it's conservatively correct as a variable never can hold values
1340 before its name is mentioned at least once.
1342 We then do a mostly classical bitmap liveness algorithm. */
1344 active
.create (last_basic_block_for_fn (fn
));
1345 active
.quick_grow (last_basic_block_for_fn (fn
));
1346 for (int i
= 0; i
< last_basic_block_for_fn (fn
); i
++)
1347 bitmap_initialize (&active
[i
], &bitmap_default_obstack
);
1349 bitmap work
= BITMAP_ALLOC (NULL
);
1351 int *rpo
= XNEWVEC (int, last_basic_block_for_fn (fn
));
1352 int n_bbs
= pre_and_rev_post_order_compute_fn (fn
, NULL
, rpo
, false);
1354 bool changed
= true;
1355 compute_live_vars_data data
= { active
, work
, vars
};
1360 for (i
= 0; i
< n_bbs
; i
++)
1362 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
1363 compute_live_vars_1 (bb
, &data
, NULL
);
1364 if (bitmap_ior_into (&active
[bb
->index
], work
))
1375 /* For ACTIVE computed by compute_live_vars, compute a bitmap of variables
1376 live after the STOP_AFTER statement and return that bitmap. */
1379 live_vars_at_stmt (vec
<bitmap_head
> &active
, live_vars_map
*vars
,
1382 bitmap work
= BITMAP_ALLOC (NULL
);
1383 compute_live_vars_data data
= { active
, work
, vars
};
1384 basic_block bb
= gimple_bb (stop_after
);
1385 compute_live_vars_1 (bb
, &data
, stop_after
);
1389 /* Destroy what compute_live_vars has returned when it is no longer needed. */
1392 destroy_live_vars (vec
<bitmap_head
> &active
)
1394 unsigned len
= active
.length ();
1395 for (unsigned i
= 0; i
< len
; i
++)
1396 bitmap_clear (&active
[i
]);
1401 /* Output partition map MAP to file F. */
1404 dump_var_map (FILE *f
, var_map map
)
1410 fprintf (f
, "\nPartition map \n\n");
1412 for (x
= 0; x
< map
->num_partitions
; x
++)
1414 if (map
->view_to_partition
!= NULL
)
1415 p
= map
->view_to_partition
[x
];
1419 if (ssa_name (p
) == NULL_TREE
1420 || virtual_operand_p (ssa_name (p
)))
1424 for (y
= 1; y
< num_ssa_names
; y
++)
1426 p
= partition_find (map
->var_partition
, y
);
1427 if (map
->partition_to_view
)
1428 p
= map
->partition_to_view
[p
];
1433 fprintf (f
, "Partition %d (", x
);
1434 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1437 fprintf (f
, "%d ", y
);
1447 /* Generic dump for the above. */
1450 debug (_var_map
&ref
)
1452 dump_var_map (stderr
, &ref
);
1456 debug (_var_map
*ptr
)
1461 fprintf (stderr
, "<nil>\n");
1465 /* Output live range info LIVE to file F, controlled by FLAG. */
1468 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1472 var_map map
= live
->map
;
1475 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1477 FOR_EACH_BB_FN (bb
, cfun
)
1479 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1480 EXECUTE_IF_SET_IN_BITMAP (&live
->livein
[bb
->index
], 0, i
, bi
)
1482 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1489 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1491 FOR_EACH_BB_FN (bb
, cfun
)
1493 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1494 EXECUTE_IF_SET_IN_BITMAP (&live
->liveout
[bb
->index
], 0, i
, bi
)
1496 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1505 /* Generic dump for the above. */
1508 debug (tree_live_info_d
&ref
)
1510 dump_live_info (stderr
, &ref
, 0);
1514 debug (tree_live_info_d
*ptr
)
1519 fprintf (stderr
, "<nil>\n");
1523 /* Verify that the info in LIVE matches the current cfg. */
1526 verify_live_on_entry (tree_live_info_p live
)
1535 var_map map
= live
->map
;
1537 /* Check for live on entry partitions and report those with a DEF in
1538 the program. This will typically mean an optimization has done
1540 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1542 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1544 int entry_block
= e
->dest
->index
;
1545 if (!region_contains_p (live
->map
, e
->dest
))
1547 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1552 var
= partition_to_var (map
, i
);
1553 stmt
= SSA_NAME_DEF_STMT (var
);
1554 tmp
= gimple_bb (stmt
);
1555 if (SSA_NAME_VAR (var
))
1556 d
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1558 loe
= live_on_entry (live
, e
->dest
);
1559 if (loe
&& bitmap_bit_p (loe
, i
))
1561 if (!gimple_nop_p (stmt
))
1564 print_generic_expr (stderr
, var
, TDF_SLIM
);
1565 fprintf (stderr
, " is defined ");
1567 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1568 fprintf (stderr
, "by:\n");
1569 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1570 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1572 fprintf (stderr
, " So it appears to have multiple defs.\n");
1579 print_generic_expr (stderr
, var
, TDF_SLIM
);
1580 fprintf (stderr
, " is live-on-entry to BB%d ",
1584 fprintf (stderr
, " but is not the default def of ");
1585 print_generic_expr (stderr
, d
, TDF_SLIM
);
1586 fprintf (stderr
, "\n");
1589 fprintf (stderr
, " and there is no default def.\n");
1596 /* An undefined local variable does not need to be very
1598 if (ssa_undefined_value_p (var
, false))
1601 /* The only way this var shouldn't be marked live on entry is
1602 if it occurs in a PHI argument of the block. */
1606 for (gsi
= gsi_start_phis (e
->dest
);
1607 !gsi_end_p (gsi
) && !ok
;
1610 gphi
*phi
= gsi
.phi ();
1611 if (virtual_operand_p (gimple_phi_result (phi
)))
1613 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1614 if (var
== gimple_phi_arg_def (phi
, z
))
1622 /* Expand adds unused default defs for PARM_DECLs and
1623 RESULT_DECLs. They're ok. */
1624 if (has_zero_uses (var
)
1625 && SSA_NAME_VAR (var
)
1626 && !VAR_P (SSA_NAME_VAR (var
)))
1629 print_generic_expr (stderr
, var
, TDF_SLIM
);
1630 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1632 fprintf (stderr
, "but it is a default def so it should be.\n");
1636 gcc_assert (num
<= 0);