1 /* Liveness for SSA trees.
2 Copyright (C) 2003-2021 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
559 && debug_info_level
== DINFO_LEVEL_NONE
560 && !optinfo_wants_inlining_info_p ())
562 /* Even for -g0 don't prune outer scopes from inlined functions,
563 otherwise late diagnostics from such functions will not be
564 emitted or suppressed properly. */
565 if (inlined_function_outer_scope_p (scope
))
567 gcc_assert (TREE_CODE (BLOCK_ORIGIN (scope
)) == FUNCTION_DECL
);
571 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
573 /* See if this block is important for representation of inlined
574 function. Inlined functions are always represented by block
575 with block_ultimate_origin being set to FUNCTION_DECL and
576 DECL_SOURCE_LOCATION set, unless they expand to nothing... */
577 else if (inlined_function_outer_scope_p (scope
))
580 /* Verfify that only blocks with source location set
581 are entry points to the inlined functions. */
582 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
))
583 == UNKNOWN_LOCATION
);
585 TREE_USED (scope
) = !unused
;
589 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
590 eliminated during the tree->rtl conversion process. */
593 mark_all_vars_used (tree
*expr_p
)
595 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
598 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
601 clear_unused_block_pointer_1 (tree
*tp
, int *, void *)
603 if (EXPR_P (*tp
) && TREE_BLOCK (*tp
)
604 && !TREE_USED (TREE_BLOCK (*tp
)))
605 TREE_SET_BLOCK (*tp
, NULL
);
609 /* Set all block pointer in debug or clobber stmt to NULL if the block
610 is unused, so that they will not be streamed out. */
613 clear_unused_block_pointer (void)
616 gimple_stmt_iterator gsi
;
618 FOR_EACH_BB_FN (bb
, cfun
)
619 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
626 stmt
= gsi_stmt (gsi
);
627 if (!is_gimple_debug (stmt
) && !gimple_clobber_p (stmt
))
629 b
= gimple_block (stmt
);
630 if (b
&& !TREE_USED (b
))
632 /* Elide debug marker stmts that have an associated BLOCK from an
633 inline instance removed with also the outermost scope BLOCK of
634 said inline instance removed. If the outermost scope BLOCK of
635 said inline instance is preserved use that in place of the
636 removed BLOCK. That keeps the marker associated to the correct
637 inline instance (or no inline instance in case it was not from
638 an inline instance). */
639 if (gimple_debug_nonbind_marker_p (stmt
)
640 && BLOCK_ABSTRACT_ORIGIN (b
))
642 while (TREE_CODE (b
) == BLOCK
643 && !inlined_function_outer_scope_p (b
))
644 b
= BLOCK_SUPERCONTEXT (b
);
645 if (TREE_CODE (b
) == BLOCK
)
649 gimple_set_block (stmt
, b
);
652 gsi_remove (&gsi
, true);
658 gimple_set_block (stmt
, NULL
);
660 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
661 walk_tree (gimple_op_ptr (stmt
, i
), clear_unused_block_pointer_1
,
666 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
667 indentation level and FLAGS is as in print_generic_expr. */
670 dump_scope_block (FILE *file
, int indent
, tree scope
, dump_flags_t flags
)
675 fprintf (file
, "\n%*s{ Scope block #%i%s",indent
, "" , BLOCK_NUMBER (scope
),
676 TREE_USED (scope
) ? "" : " (unused)");
677 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
)) != UNKNOWN_LOCATION
)
679 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
680 fprintf (file
, " %s:%i", s
.file
, s
.line
);
682 if (BLOCK_ABSTRACT_ORIGIN (scope
))
684 tree origin
= block_ultimate_origin (scope
);
687 fprintf (file
, " Originating from :");
689 print_generic_decl (file
, origin
, flags
);
691 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
694 if (BLOCK_FRAGMENT_ORIGIN (scope
))
695 fprintf (file
, " Fragment of : #%i",
696 BLOCK_NUMBER (BLOCK_FRAGMENT_ORIGIN (scope
)));
697 else if (BLOCK_FRAGMENT_CHAIN (scope
))
699 fprintf (file
, " Fragment chain :");
700 for (t
= BLOCK_FRAGMENT_CHAIN (scope
); t
;
701 t
= BLOCK_FRAGMENT_CHAIN (t
))
702 fprintf (file
, " #%i", BLOCK_NUMBER (t
));
704 fprintf (file
, " \n");
705 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
707 fprintf (file
, "%*s", indent
, "");
708 print_generic_decl (file
, var
, flags
);
709 fprintf (file
, "\n");
711 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
713 fprintf (file
, "%*s",indent
, "");
714 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
716 fprintf (file
, " (nonlocalized)\n");
718 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
719 dump_scope_block (file
, indent
+ 2, t
, flags
);
720 fprintf (file
, "\n%*s}\n",indent
, "");
723 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
724 is as in print_generic_expr. */
727 debug_scope_block (tree scope
, dump_flags_t flags
)
729 dump_scope_block (stderr
, 0, scope
, flags
);
733 /* Dump the tree of lexical scopes of current_function_decl to FILE.
734 FLAGS is as in print_generic_expr. */
737 dump_scope_blocks (FILE *file
, dump_flags_t flags
)
739 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
743 /* Dump the tree of lexical scopes of current_function_decl to stderr.
744 FLAGS is as in print_generic_expr. */
747 debug_scope_blocks (dump_flags_t flags
)
749 dump_scope_blocks (stderr
, flags
);
752 /* Remove local variables that are not referenced in the IL. */
755 remove_unused_locals (void)
759 unsigned srcidx
, dstidx
, num
;
760 bool have_local_clobbers
= false;
762 /* Removing declarations from lexical blocks when not optimizing is
763 not only a waste of time, it actually causes differences in stack
768 timevar_push (TV_REMOVE_UNUSED
);
770 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
772 usedvars
= BITMAP_ALLOC (NULL
);
773 auto_bitmap useddebug
;
775 /* Walk the CFG marking all referenced symbols. */
776 FOR_EACH_BB_FN (bb
, cfun
)
778 gimple_stmt_iterator gsi
;
783 /* Walk the statements. */
784 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
786 gimple
*stmt
= gsi_stmt (gsi
);
787 tree b
= gimple_block (stmt
);
789 /* If we wanted to mark the block referenced by the inline
790 entry point marker as used, this would be a good spot to
791 do it. If the block is not otherwise used, the stmt will
792 be cleaned up in clean_unused_block_pointer. */
793 if (is_gimple_debug (stmt
))
795 if (gimple_debug_bind_p (stmt
))
797 tree var
= gimple_debug_bind_get_var (stmt
);
800 if (!gimple_debug_bind_get_value (stmt
))
801 /* Run the 2nd phase. */
802 have_local_clobbers
= true;
804 bitmap_set_bit (useddebug
, DECL_UID (var
));
810 if (gimple_clobber_p (stmt
))
812 have_local_clobbers
= true;
817 TREE_USED (b
) = true;
819 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
820 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
));
823 for (gphi_iterator gpi
= gsi_start_phis (bb
);
830 gphi
*phi
= gpi
.phi ();
832 if (virtual_operand_p (gimple_phi_result (phi
)))
835 def
= gimple_phi_result (phi
);
836 mark_all_vars_used (&def
);
838 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
840 tree arg
= USE_FROM_PTR (arg_p
);
841 int index
= PHI_ARG_INDEX_FROM_USE (arg_p
);
843 LOCATION_BLOCK (gimple_phi_arg_location (phi
, index
));
845 TREE_USED (block
) = true;
846 mark_all_vars_used (&arg
);
850 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
851 if (LOCATION_BLOCK (e
->goto_locus
) != NULL
)
852 TREE_USED (LOCATION_BLOCK (e
->goto_locus
)) = true;
855 /* We do a two-pass approach about the out-of-scope clobbers. We want
856 to remove them if they are the only references to a local variable,
857 but we want to retain them when there's any other. So the first pass
858 ignores them, and the second pass (if there were any) tries to remove
860 if (have_local_clobbers
)
861 FOR_EACH_BB_FN (bb
, cfun
)
863 gimple_stmt_iterator gsi
;
865 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
867 gimple
*stmt
= gsi_stmt (gsi
);
868 tree b
= gimple_block (stmt
);
870 if (gimple_clobber_p (stmt
))
872 tree lhs
= gimple_assign_lhs (stmt
);
873 tree base
= get_base_address (lhs
);
874 /* Remove clobbers referencing unused vars, or clobbers
875 with MEM_REF lhs referencing uninitialized pointers. */
876 if ((VAR_P (base
) && !is_used_p (base
))
877 || (TREE_CODE (lhs
) == MEM_REF
878 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
879 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs
, 0))
880 && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs
, 0)))
883 unlink_stmt_vdef (stmt
);
884 gsi_remove (&gsi
, true);
889 TREE_USED (b
) = true;
891 else if (gimple_debug_bind_p (stmt
))
893 tree var
= gimple_debug_bind_get_var (stmt
);
895 && !bitmap_bit_p (useddebug
, DECL_UID (var
))
898 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
899 fprintf (dump_file
, "Dead debug bind reset to %u\n",
901 gsi_remove (&gsi
, true);
909 if (cfun
->has_simduid_loops
)
912 FOR_EACH_LOOP (loop
, 0)
913 if (loop
->simduid
&& !is_used_p (loop
->simduid
))
914 loop
->simduid
= NULL_TREE
;
917 cfun
->has_local_explicit_reg_vars
= false;
919 /* Remove unmarked local and global vars from local_decls. */
920 num
= vec_safe_length (cfun
->local_decls
);
921 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
923 var
= (*cfun
->local_decls
)[srcidx
];
926 if (!is_used_p (var
))
929 if (cfun
->nonlocal_goto_save_area
930 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
931 cfun
->nonlocal_goto_save_area
= NULL
;
932 /* Release any default def associated with var. */
933 if ((def
= ssa_default_def (cfun
, var
)) != NULL_TREE
)
935 set_ssa_default_def (cfun
, var
, NULL_TREE
);
936 release_ssa_name (def
);
941 if (VAR_P (var
) && DECL_HARD_REGISTER (var
) && !is_global_var (var
))
942 cfun
->has_local_explicit_reg_vars
= true;
944 if (srcidx
!= dstidx
)
945 (*cfun
->local_decls
)[dstidx
] = var
;
950 statistics_counter_event (cfun
, "unused VAR_DECLs removed", num
- dstidx
);
951 cfun
->local_decls
->truncate (dstidx
);
954 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
),
955 polymorphic_ctor_dtor_p (current_function_decl
,
957 clear_unused_block_pointer ();
959 BITMAP_FREE (usedvars
);
961 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
963 fprintf (dump_file
, "Scope blocks after cleanups:\n");
964 dump_scope_blocks (dump_file
, dump_flags
);
967 timevar_pop (TV_REMOVE_UNUSED
);
970 /* Allocate and return a new live range information object base on MAP. */
972 static tree_live_info_p
973 new_tree_live_info (var_map map
)
975 tree_live_info_p live
;
978 live
= XNEW (struct tree_live_info_d
);
980 live
->num_blocks
= last_basic_block_for_fn (cfun
);
982 bitmap_obstack_initialize (&live
->livein_obstack
);
983 bitmap_obstack_initialize (&live
->liveout_obstack
);
985 live
->livein
= XCNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
986 live
->liveout
= XCNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
987 for (unsigned i
= 0; map
->vec_bbs
.iterate (i
, &bb
); ++i
)
989 bitmap_initialize (&live
->livein
[bb
->index
], &live
->livein_obstack
);
990 bitmap_initialize (&live
->liveout
[bb
->index
], &live
->liveout_obstack
);
993 live
->work_stack
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
994 live
->stack_top
= live
->work_stack
;
996 live
->global
= BITMAP_ALLOC (NULL
);
1001 /* Free storage for live range info object LIVE. */
1004 delete_tree_live_info (tree_live_info_p live
)
1008 bitmap_obstack_release (&live
->livein_obstack
);
1009 free (live
->livein
);
1013 bitmap_obstack_release (&live
->liveout_obstack
);
1014 free (live
->liveout
);
1016 BITMAP_FREE (live
->global
);
1017 free (live
->work_stack
);
1022 /* Visit basic block BB and propagate any required live on entry bits from
1023 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
1024 TMP is a temporary work bitmap which is passed in to avoid reallocating
1028 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
)
1033 basic_block pred_bb
;
1036 gcc_checking_assert (!bitmap_bit_p (visited
, bb
->index
));
1037 bitmap_set_bit (visited
, bb
->index
);
1039 loe
= live_on_entry (live
, bb
);
1041 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1044 if (!region_contains_p (live
->map
, pred_bb
))
1046 /* Variables live-on-entry from BB that aren't defined in the
1047 predecessor block. This should be the live on entry vars to pred.
1048 Note that liveout is the DEFs in a block while live on entry is
1050 Add these bits to live-on-entry for the pred. if there are any
1051 changes, and pred_bb has been visited already, add it to the
1053 change
= bitmap_ior_and_compl_into (live_on_entry (live
, pred_bb
),
1054 loe
, &live
->liveout
[pred_bb
->index
]);
1056 && bitmap_bit_p (visited
, pred_bb
->index
))
1058 bitmap_clear_bit (visited
, pred_bb
->index
);
1059 *(live
->stack_top
)++ = pred_bb
->index
;
1065 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
1066 of all the variables. */
1069 live_worklist (tree_live_info_p live
)
1073 auto_sbitmap
visited (last_basic_block_for_fn (cfun
) + 1);
1075 bitmap_clear (visited
);
1077 /* Visit region's blocks in reverse order and propagate live on entry values
1078 into the predecessors blocks. */
1079 for (unsigned i
= live
->map
->vec_bbs
.length () - 1;
1080 live
->map
->vec_bbs
.iterate (i
, &bb
); --i
)
1081 loe_visit_block (live
, bb
, visited
);
1083 /* Process any blocks which require further iteration. */
1084 while (live
->stack_top
!= live
->work_stack
)
1086 b
= *--(live
->stack_top
);
1087 loe_visit_block (live
, BASIC_BLOCK_FOR_FN (cfun
, b
), visited
);
1092 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1093 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1094 in the liveout vector. */
1097 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1102 basic_block def_bb
= NULL
;
1103 imm_use_iterator imm_iter
;
1104 bool global
= false;
1106 p
= var_to_partition (live
->map
, ssa_name
);
1107 if (p
== NO_PARTITION
)
1110 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1113 def_bb
= gimple_bb (stmt
);
1114 /* Mark defs in liveout bitmap temporarily. */
1115 if (def_bb
&& region_contains_p (live
->map
, def_bb
))
1116 bitmap_set_bit (&live
->liveout
[def_bb
->index
], p
);
1119 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1121 /* An undefined local variable does not need to be very alive. */
1122 if (ssa_undefined_value_p (ssa_name
, false))
1125 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1126 add it to the list of live on entry blocks. */
1127 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1129 gimple
*use_stmt
= USE_STMT (use
);
1130 basic_block add_block
= NULL
;
1132 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1134 /* Uses in PHI's are considered to be live at exit of the SRC block
1135 as this is where a copy would be inserted. Check to see if it is
1136 defined in that block, or whether its live on entry. */
1137 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1138 edge e
= gimple_phi_arg_edge (as_a
<gphi
*> (use_stmt
), index
);
1139 if (e
->src
!= def_bb
&& region_contains_p (live
->map
, e
->src
))
1142 else if (is_gimple_debug (use_stmt
))
1146 /* If its not defined in this block, its live on entry. */
1147 basic_block use_bb
= gimple_bb (use_stmt
);
1148 if (use_bb
!= def_bb
&& region_contains_p (live
->map
, use_bb
))
1152 /* If there was a live on entry use, set the bit. */
1156 bitmap_set_bit (&live
->livein
[add_block
->index
], p
);
1160 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1161 on entry blocks between the def and all the uses. */
1163 bitmap_set_bit (live
->global
, p
);
1167 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1170 calculate_live_on_exit (tree_live_info_p liveinfo
)
1176 /* live on entry calculations used liveout vectors for defs, clear them. */
1177 for (unsigned i
= 0; liveinfo
->map
->vec_bbs
.iterate (i
, &bb
); ++i
)
1178 bitmap_clear (&liveinfo
->liveout
[bb
->index
]);
1180 /* Set all the live-on-exit bits for uses in PHIs. */
1181 FOR_EACH_BB_FN (bb
, cfun
)
1186 /* Mark the PHI arguments which are live on exit to the pred block. */
1187 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1189 gphi
*phi
= gsi
.phi ();
1190 if (virtual_operand_p (gimple_phi_result (phi
)))
1192 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1194 tree t
= PHI_ARG_DEF (phi
, i
);
1197 if (TREE_CODE (t
) != SSA_NAME
)
1200 p
= var_to_partition (liveinfo
->map
, t
);
1201 if (p
== NO_PARTITION
)
1203 e
= gimple_phi_arg_edge (phi
, i
);
1204 if (region_contains_p (liveinfo
->map
, e
->src
))
1205 bitmap_set_bit (&liveinfo
->liveout
[e
->src
->index
], p
);
1209 if (!region_contains_p (liveinfo
->map
, bb
))
1212 /* Add each successors live on entry to this bock live on exit. */
1213 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1214 if (region_contains_p (liveinfo
->map
, e
->dest
))
1215 bitmap_ior_into (&liveinfo
->liveout
[bb
->index
],
1216 live_on_entry (liveinfo
, e
->dest
));
1221 /* Given partition map MAP, calculate all the live on entry bitmaps for
1222 each partition. Return a new live info object. */
1225 calculate_live_ranges (var_map map
, bool want_livein
)
1229 tree_live_info_p live
;
1231 live
= new_tree_live_info (map
);
1232 for (i
= 0; i
< num_var_partitions (map
); i
++)
1234 var
= partition_to_var (map
, i
);
1235 if (var
!= NULL_TREE
)
1236 set_var_live_on_entry (var
, live
);
1239 live_worklist (live
);
1242 verify_live_on_entry (live
);
1244 calculate_live_on_exit (live
);
1248 bitmap_obstack_release (&live
->livein_obstack
);
1249 free (live
->livein
);
1250 live
->livein
= NULL
;
1256 /* Data structure for compute_live_vars* functions. */
1258 struct compute_live_vars_data
{
1259 /* Vector of bitmaps for live vars indices at the end of basic blocks,
1260 indexed by bb->index. ACTIVE[ENTRY_BLOCK] must be empty bitmap,
1261 ACTIVE[EXIT_BLOCK] is used for STOP_AFTER. */
1262 vec
<bitmap_head
> active
;
1263 /* Work bitmap of currently live variables. */
1265 /* Set of interesting variables. Variables with uids not in this
1266 hash_map are not tracked. */
1267 live_vars_map
*vars
;
1270 /* Callback for walk_stmt_load_store_addr_ops. If OP is a VAR_DECL with
1271 uid set in DATA->vars, enter its corresponding index into bitmap
1275 compute_live_vars_visit (gimple
*, tree op
, tree
, void *pdata
)
1277 compute_live_vars_data
*data
= (compute_live_vars_data
*) pdata
;
1278 op
= get_base_address (op
);
1279 if (op
&& VAR_P (op
))
1280 if (unsigned int *v
= data
->vars
->get (DECL_UID (op
)))
1281 bitmap_set_bit (data
->work
, *v
);
1285 /* Helper routine for compute_live_vars, calculating the sets of live
1286 variables at the end of BB, leaving the result in DATA->work.
1287 If STOP_AFTER is non-NULL, stop processing after that stmt. */
1290 compute_live_vars_1 (basic_block bb
, compute_live_vars_data
*data
,
1295 gimple_stmt_iterator gsi
;
1296 walk_stmt_load_store_addr_fn visit
= compute_live_vars_visit
;
1298 bitmap_clear (data
->work
);
1299 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1300 bitmap_ior_into (data
->work
, &data
->active
[e
->src
->index
]);
1302 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1303 walk_stmt_load_store_addr_ops (gsi_stmt (gsi
), data
, NULL
, NULL
, visit
);
1304 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1306 gimple
*stmt
= gsi_stmt (gsi
);
1308 if (gimple_clobber_p (stmt
))
1310 tree lhs
= gimple_assign_lhs (stmt
);
1312 if (unsigned int *v
= data
->vars
->get (DECL_UID (lhs
)))
1313 bitmap_clear_bit (data
->work
, *v
);
1315 else if (!is_gimple_debug (stmt
))
1316 walk_stmt_load_store_addr_ops (stmt
, data
, visit
, visit
, visit
);
1317 if (stmt
== stop_after
)
1322 /* For function FN and live_vars_map (hash map from DECL_UIDs to a dense set of
1323 indexes of automatic variables VARS, compute which of those variables are
1324 (might be) live at the end of each basic block. */
1327 compute_live_vars (struct function
*fn
, live_vars_map
*vars
)
1329 vec
<bitmap_head
> active
;
1331 /* We approximate the live range of a stack variable by taking the first
1332 mention of its name as starting point(s), and by the end-of-scope
1333 death clobber added by gimplify as ending point(s) of the range.
1334 This overapproximates in the case we for instance moved an address-taken
1335 operation upward, without also moving a dereference to it upwards.
1336 But it's conservatively correct as a variable never can hold values
1337 before its name is mentioned at least once.
1339 We then do a mostly classical bitmap liveness algorithm. */
1341 active
.create (last_basic_block_for_fn (fn
));
1342 active
.quick_grow (last_basic_block_for_fn (fn
));
1343 for (int i
= 0; i
< last_basic_block_for_fn (fn
); i
++)
1344 bitmap_initialize (&active
[i
], &bitmap_default_obstack
);
1346 bitmap work
= BITMAP_ALLOC (NULL
);
1348 int *rpo
= XNEWVEC (int, last_basic_block_for_fn (fn
));
1349 int n_bbs
= pre_and_rev_post_order_compute_fn (fn
, NULL
, rpo
, false);
1351 bool changed
= true;
1352 compute_live_vars_data data
= { active
, work
, vars
};
1357 for (i
= 0; i
< n_bbs
; i
++)
1359 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
1360 compute_live_vars_1 (bb
, &data
, NULL
);
1361 if (bitmap_ior_into (&active
[bb
->index
], work
))
1372 /* For ACTIVE computed by compute_live_vars, compute a bitmap of variables
1373 live after the STOP_AFTER statement and return that bitmap. */
1376 live_vars_at_stmt (vec
<bitmap_head
> &active
, live_vars_map
*vars
,
1379 bitmap work
= BITMAP_ALLOC (NULL
);
1380 compute_live_vars_data data
= { active
, work
, vars
};
1381 basic_block bb
= gimple_bb (stop_after
);
1382 compute_live_vars_1 (bb
, &data
, stop_after
);
1386 /* Destroy what compute_live_vars has returned when it is no longer needed. */
1389 destroy_live_vars (vec
<bitmap_head
> &active
)
1391 unsigned len
= active
.length ();
1392 for (unsigned i
= 0; i
< len
; i
++)
1393 bitmap_clear (&active
[i
]);
1398 /* Output partition map MAP to file F. */
1401 dump_var_map (FILE *f
, var_map map
)
1407 fprintf (f
, "\nPartition map \n\n");
1409 for (x
= 0; x
< map
->num_partitions
; x
++)
1411 if (map
->view_to_partition
!= NULL
)
1412 p
= map
->view_to_partition
[x
];
1416 if (ssa_name (p
) == NULL_TREE
1417 || virtual_operand_p (ssa_name (p
)))
1421 for (y
= 1; y
< num_ssa_names
; y
++)
1423 p
= partition_find (map
->var_partition
, y
);
1424 if (map
->partition_to_view
)
1425 p
= map
->partition_to_view
[p
];
1430 fprintf (f
, "Partition %d (", x
);
1431 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1434 fprintf (f
, "%d ", y
);
1444 /* Generic dump for the above. */
1447 debug (_var_map
&ref
)
1449 dump_var_map (stderr
, &ref
);
1453 debug (_var_map
*ptr
)
1458 fprintf (stderr
, "<nil>\n");
1462 /* Output live range info LIVE to file F, controlled by FLAG. */
1465 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1469 var_map map
= live
->map
;
1472 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1474 FOR_EACH_BB_FN (bb
, cfun
)
1476 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1477 EXECUTE_IF_SET_IN_BITMAP (&live
->livein
[bb
->index
], 0, i
, bi
)
1479 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1486 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1488 FOR_EACH_BB_FN (bb
, cfun
)
1490 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1491 EXECUTE_IF_SET_IN_BITMAP (&live
->liveout
[bb
->index
], 0, i
, bi
)
1493 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1502 /* Generic dump for the above. */
1505 debug (tree_live_info_d
&ref
)
1507 dump_live_info (stderr
, &ref
, 0);
1511 debug (tree_live_info_d
*ptr
)
1516 fprintf (stderr
, "<nil>\n");
1520 /* Verify that the info in LIVE matches the current cfg. */
1523 verify_live_on_entry (tree_live_info_p live
)
1532 var_map map
= live
->map
;
1534 /* Check for live on entry partitions and report those with a DEF in
1535 the program. This will typically mean an optimization has done
1537 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1539 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1541 int entry_block
= e
->dest
->index
;
1542 if (!region_contains_p (live
->map
, e
->dest
))
1544 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1549 var
= partition_to_var (map
, i
);
1550 stmt
= SSA_NAME_DEF_STMT (var
);
1551 tmp
= gimple_bb (stmt
);
1552 if (SSA_NAME_VAR (var
))
1553 d
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1555 loe
= live_on_entry (live
, e
->dest
);
1556 if (loe
&& bitmap_bit_p (loe
, i
))
1558 if (!gimple_nop_p (stmt
))
1561 print_generic_expr (stderr
, var
, TDF_SLIM
);
1562 fprintf (stderr
, " is defined ");
1564 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1565 fprintf (stderr
, "by:\n");
1566 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1567 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1569 fprintf (stderr
, " So it appears to have multiple defs.\n");
1576 print_generic_expr (stderr
, var
, TDF_SLIM
);
1577 fprintf (stderr
, " is live-on-entry to BB%d ",
1581 fprintf (stderr
, " but is not the default def of ");
1582 print_generic_expr (stderr
, d
, TDF_SLIM
);
1583 fprintf (stderr
, "\n");
1586 fprintf (stderr
, " and there is no default def.\n");
1593 /* An undefined local variable does not need to be very
1595 if (ssa_undefined_value_p (var
, false))
1598 /* The only way this var shouldn't be marked live on entry is
1599 if it occurs in a PHI argument of the block. */
1603 for (gsi
= gsi_start_phis (e
->dest
);
1604 !gsi_end_p (gsi
) && !ok
;
1607 gphi
*phi
= gsi
.phi ();
1608 if (virtual_operand_p (gimple_phi_result (phi
)))
1610 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1611 if (var
== gimple_phi_arg_def (phi
, z
))
1619 /* Expand adds unused default defs for PARM_DECLs and
1620 RESULT_DECLs. They're ok. */
1621 if (has_zero_uses (var
)
1622 && SSA_NAME_VAR (var
)
1623 && !VAR_P (SSA_NAME_VAR (var
)))
1626 print_generic_expr (stderr
, var
, TDF_SLIM
);
1627 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1629 fprintf (stderr
, "but it is a default def so it should be.\n");
1633 gcc_assert (num
<= 0);