1 /* Liveness for SSA trees.
2 Copyright (C) 2003-2013 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"
26 #include "gimple-pretty-print.h"
28 #include "tree-flow.h"
31 #include "tree-ssa-live.h"
32 #include "diagnostic-core.h"
37 #ifdef ENABLE_CHECKING
38 static void verify_live_on_entry (tree_live_info_p
);
42 /* VARMAP maintains a mapping from SSA version number to real variables.
44 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
45 only member of it's own partition. Coalescing will attempt to group any
46 ssa_names which occur in a copy or in a PHI node into the same partition.
48 At the end of out-of-ssa, each partition becomes a "real" variable and is
49 rewritten as a compiler variable.
51 The var_map data structure is used to manage these partitions. It allows
52 partitions to be combined, and determines which partition belongs to what
53 ssa_name or variable, and vice versa. */
56 /* This routine will initialize the basevar fields of MAP. */
59 var_map_base_init (var_map map
)
64 struct tree_int_map
*m
, *mapstorage
;
66 num_part
= num_var_partitions (map
);
67 tree_to_index
= htab_create (num_part
, tree_map_base_hash
,
68 tree_int_map_eq
, NULL
);
69 /* We can have at most num_part entries in the hash tables, so it's
70 enough to allocate so many map elements once, saving some malloc
72 mapstorage
= m
= XNEWVEC (struct tree_int_map
, num_part
);
74 /* If a base table already exists, clear it, otherwise create it. */
75 free (map
->partition_to_base_index
);
76 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
78 /* Build the base variable list, and point partitions at their bases. */
79 for (x
= 0; x
< num_part
; x
++)
81 struct tree_int_map
**slot
;
83 var
= partition_to_var (map
, x
);
84 if (SSA_NAME_VAR (var
))
85 m
->base
.from
= SSA_NAME_VAR (var
);
87 /* This restricts what anonymous SSA names we can coalesce
88 as it restricts the sets we compute conflicts for.
89 Using TREE_TYPE to generate sets is the easies as
90 type equivalency also holds for SSA names with the same
92 m
->base
.from
= TREE_TYPE (var
);
93 /* If base variable hasn't been seen, set it up. */
94 slot
= (struct tree_int_map
**) htab_find_slot (tree_to_index
,
98 baseindex
= m
- mapstorage
;
104 baseindex
= (*slot
)->to
;
105 map
->partition_to_base_index
[x
] = baseindex
;
108 map
->num_basevars
= m
- mapstorage
;
111 htab_delete (tree_to_index
);
115 /* Remove the base table in MAP. */
118 var_map_base_fini (var_map map
)
120 /* Free the basevar info if it is present. */
121 if (map
->partition_to_base_index
!= NULL
)
123 free (map
->partition_to_base_index
);
124 map
->partition_to_base_index
= NULL
;
125 map
->num_basevars
= 0;
128 /* Create a variable partition map of SIZE, initialize and return it. */
131 init_var_map (int size
)
135 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
136 map
->var_partition
= partition_new (size
);
138 map
->partition_to_view
= NULL
;
139 map
->view_to_partition
= NULL
;
140 map
->num_partitions
= size
;
141 map
->partition_size
= size
;
142 map
->num_basevars
= 0;
143 map
->partition_to_base_index
= NULL
;
148 /* Free memory associated with MAP. */
151 delete_var_map (var_map map
)
153 var_map_base_fini (map
);
154 partition_delete (map
->var_partition
);
155 free (map
->partition_to_view
);
156 free (map
->view_to_partition
);
161 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
162 Returns the partition which represents the new partition. If the two
163 partitions cannot be combined, NO_PARTITION is returned. */
166 var_union (var_map map
, tree var1
, tree var2
)
170 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
171 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
173 /* This is independent of partition_to_view. If partition_to_view is
174 on, then whichever one of these partitions is absorbed will never have a
175 dereference into the partition_to_view array any more. */
177 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
178 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
180 gcc_assert (p1
!= NO_PARTITION
);
181 gcc_assert (p2
!= NO_PARTITION
);
186 p3
= partition_union (map
->var_partition
, p1
, p2
);
188 if (map
->partition_to_view
)
189 p3
= map
->partition_to_view
[p3
];
195 /* Compress the partition numbers in MAP such that they fall in the range
196 0..(num_partitions-1) instead of wherever they turned out during
197 the partitioning exercise. This removes any references to unused
198 partitions, thereby allowing bitmaps and other vectors to be much
201 This is implemented such that compaction doesn't affect partitioning.
202 Ie., once partitions are created and possibly merged, running one
203 or more different kind of compaction will not affect the partitions
204 themselves. Their index might change, but all the same variables will
205 still be members of the same partition group. This allows work on reduced
206 sets, and no loss of information when a larger set is later desired.
208 In particular, coalescing can work on partitions which have 2 or more
209 definitions, and then 'recompact' later to include all the single
210 definitions for assignment to program variables. */
213 /* Set MAP back to the initial state of having no partition view. Return a
214 bitmap which has a bit set for each partition number which is in use in the
218 partition_view_init (var_map map
)
224 used
= BITMAP_ALLOC (NULL
);
226 /* Already in a view? Abandon the old one. */
227 if (map
->partition_to_view
)
229 free (map
->partition_to_view
);
230 map
->partition_to_view
= NULL
;
232 if (map
->view_to_partition
)
234 free (map
->view_to_partition
);
235 map
->view_to_partition
= NULL
;
238 /* Find out which partitions are actually referenced. */
239 for (x
= 0; x
< map
->partition_size
; x
++)
241 tmp
= partition_find (map
->var_partition
, x
);
242 if (ssa_name (tmp
) != NULL_TREE
&& !virtual_operand_p (ssa_name (tmp
))
243 && (!has_zero_uses (ssa_name (tmp
))
244 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
245 bitmap_set_bit (used
, tmp
);
248 map
->num_partitions
= map
->partition_size
;
253 /* This routine will finalize the view data for MAP based on the partitions
254 set in SELECTED. This is either the same bitmap returned from
255 partition_view_init, or a trimmed down version if some of those partitions
256 were not desired in this view. SELECTED is freed before returning. */
259 partition_view_fini (var_map map
, bitmap selected
)
262 unsigned count
, i
, x
, limit
;
264 gcc_assert (selected
);
266 count
= bitmap_count_bits (selected
);
267 limit
= map
->partition_size
;
269 /* If its a one-to-one ratio, we don't need any view compaction. */
272 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
273 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
274 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
277 /* Give each selected partition an index. */
278 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
280 map
->partition_to_view
[x
] = i
;
281 map
->view_to_partition
[i
] = x
;
284 gcc_assert (i
== count
);
285 map
->num_partitions
= i
;
288 BITMAP_FREE (selected
);
292 /* Create a partition view which includes all the used partitions in MAP. If
293 WANT_BASES is true, create the base variable map as well. */
296 partition_view_normal (var_map map
, bool want_bases
)
300 used
= partition_view_init (map
);
301 partition_view_fini (map
, used
);
304 var_map_base_init (map
);
306 var_map_base_fini (map
);
310 /* Create a partition view in MAP which includes just partitions which occur in
311 the bitmap ONLY. If WANT_BASES is true, create the base variable map
315 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
318 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
322 used
= partition_view_init (map
);
323 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
325 p
= partition_find (map
->var_partition
, x
);
326 gcc_assert (bitmap_bit_p (used
, p
));
327 bitmap_set_bit (new_partitions
, p
);
329 partition_view_fini (map
, new_partitions
);
332 var_map_base_init (map
);
334 var_map_base_fini (map
);
338 static bitmap usedvars
;
340 /* Mark VAR as used, so that it'll be preserved during rtl expansion.
341 Returns true if VAR wasn't marked before. */
344 set_is_used (tree var
)
346 return bitmap_set_bit (usedvars
, DECL_UID (var
));
349 /* Return true if VAR is marked as used. */
354 return bitmap_bit_p (usedvars
, DECL_UID (var
));
357 static inline void mark_all_vars_used (tree
*);
359 /* Helper function for mark_all_vars_used, called via walk_tree. */
362 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
365 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
368 if (TREE_CODE (t
) == SSA_NAME
)
371 t
= SSA_NAME_VAR (t
);
376 if (IS_EXPR_CODE_CLASS (c
)
377 && (b
= TREE_BLOCK (t
)) != NULL
)
378 TREE_USED (b
) = true;
380 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
381 fields do not contain vars. */
382 if (TREE_CODE (t
) == TARGET_MEM_REF
)
384 mark_all_vars_used (&TMR_BASE (t
));
385 mark_all_vars_used (&TMR_INDEX (t
));
386 mark_all_vars_used (&TMR_INDEX2 (t
));
391 /* Only need to mark VAR_DECLS; parameters and return results are not
392 eliminated as unused. */
393 if (TREE_CODE (t
) == VAR_DECL
)
395 /* When a global var becomes used for the first time also walk its
396 initializer (non global ones don't have any). */
397 if (set_is_used (t
) && is_global_var (t
)
398 && DECL_CONTEXT (t
) == current_function_decl
)
399 mark_all_vars_used (&DECL_INITIAL (t
));
401 /* remove_unused_scope_block_p requires information about labels
402 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
403 else if (TREE_CODE (t
) == LABEL_DECL
)
404 /* Although the TREE_USED values that the frontend uses would be
405 acceptable (albeit slightly over-conservative) for our purposes,
406 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
407 must re-compute it here. */
410 if (IS_TYPE_OR_DECL_P (t
))
416 /* Mark the scope block SCOPE and its subblocks unused when they can be
417 possibly eliminated if dead. */
420 mark_scope_block_unused (tree scope
)
423 TREE_USED (scope
) = false;
424 if (!(*debug_hooks
->ignore_block
) (scope
))
425 TREE_USED (scope
) = true;
426 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
427 mark_scope_block_unused (t
);
430 /* Look if the block is dead (by possibly eliminating its dead subblocks)
431 and return true if so.
432 Block is declared dead if:
433 1) No statements are associated with it.
434 2) Declares no live variables
435 3) All subblocks are dead
436 or there is precisely one subblocks and the block
437 has same abstract origin as outer block and declares
438 no variables, so it is pure wrapper.
439 When we are not outputting full debug info, we also eliminate dead variables
440 out of scope blocks to let them to be recycled by GGC and to save copying work
441 done by the inliner. */
444 remove_unused_scope_block_p (tree scope
)
447 bool unused
= !TREE_USED (scope
);
450 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
452 next
= &DECL_CHAIN (*t
);
454 /* Debug info of nested function refers to the block of the
455 function. We might stil call it even if all statements
456 of function it was nested into was elliminated.
458 TODO: We can actually look into cgraph to see if function
459 will be output to file. */
460 if (TREE_CODE (*t
) == FUNCTION_DECL
)
463 /* If a decl has a value expr, we need to instantiate it
464 regardless of debug info generation, to avoid codegen
465 differences in memory overlap tests. update_equiv_regs() may
466 indirectly call validate_equiv_mem() to test whether a
467 SET_DEST overlaps with others, and if the value expr changes
468 by virtual register instantiation, we may get end up with
469 different results. */
470 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
473 /* Remove everything we don't generate debug info for. */
474 else if (DECL_IGNORED_P (*t
))
476 *t
= DECL_CHAIN (*t
);
480 /* When we are outputting debug info, we usually want to output
481 info about optimized-out variables in the scope blocks.
482 Exception are the scope blocks not containing any instructions
483 at all so user can't get into the scopes at first place. */
484 else if (is_used_p (*t
))
486 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
487 /* For labels that are still used in the IL, the decision to
488 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
489 risk having different ordering in debug vs. non-debug builds
490 during inlining or versioning.
491 A label appearing here (we have already checked DECL_IGNORED_P)
492 should not be used in the IL unless it has been explicitly used
493 before, so we use TREE_USED as an approximation. */
494 /* In principle, we should do the same here as for the debug case
495 below, however, when debugging, there might be additional nested
496 levels that keep an upper level with a label live, so we have to
497 force this block to be considered used, too. */
500 /* When we are not doing full debug info, we however can keep around
501 only the used variables for cfgexpand's memory packing saving quite
504 For sake of -g3, we keep around those vars but we don't count this as
505 use of block, so innermost block with no used vars and no instructions
506 can be considered dead. We only want to keep around blocks user can
507 breakpoint into and ask about value of optimized out variables.
509 Similarly we need to keep around types at least until all
510 variables of all nested blocks are gone. We track no
511 information on whether given type is used or not, so we have
512 to keep them even when not emitting debug information,
513 otherwise we may end up remapping variables and their (local)
514 types in different orders depending on whether debug
515 information is being generated. */
517 else if (TREE_CODE (*t
) == TYPE_DECL
518 || debug_info_level
== DINFO_LEVEL_NORMAL
519 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
523 *t
= DECL_CHAIN (*t
);
528 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
529 if (remove_unused_scope_block_p (*t
))
531 if (BLOCK_SUBBLOCKS (*t
))
533 tree next
= BLOCK_CHAIN (*t
);
534 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
536 *t
= BLOCK_SUBBLOCKS (*t
);
537 while (BLOCK_CHAIN (*t
))
539 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
540 t
= &BLOCK_CHAIN (*t
);
542 BLOCK_CHAIN (*t
) = next
;
543 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
544 t
= &BLOCK_CHAIN (*t
);
548 *t
= BLOCK_CHAIN (*t
);
552 t
= &BLOCK_CHAIN (*t
);
559 /* Outer scope is always used. */
560 else if (!BLOCK_SUPERCONTEXT (scope
)
561 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
563 /* Innermost blocks with no live variables nor statements can be always
565 else if (!nsubblocks
)
567 /* For terse debug info we can eliminate info on unused variables. */
568 else if (debug_info_level
== DINFO_LEVEL_NONE
569 || debug_info_level
== DINFO_LEVEL_TERSE
)
571 /* Even for -g0/-g1 don't prune outer scopes from artificial
572 functions, otherwise diagnostics using tree_nonartificial_location
573 will not be emitted properly. */
574 if (inlined_function_outer_scope_p (scope
))
579 && TREE_CODE (ao
) == BLOCK
580 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
581 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
583 && TREE_CODE (ao
) == FUNCTION_DECL
584 && DECL_DECLARED_INLINE_P (ao
)
585 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
589 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
591 /* See if this block is important for representation of inlined function.
592 Inlined functions are always represented by block with
593 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
595 else if (inlined_function_outer_scope_p (scope
))
598 /* Verfify that only blocks with source location set
599 are entry points to the inlined functions. */
600 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
))
601 == UNKNOWN_LOCATION
);
603 TREE_USED (scope
) = !unused
;
607 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
608 eliminated during the tree->rtl conversion process. */
611 mark_all_vars_used (tree
*expr_p
)
613 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
616 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
619 clear_unused_block_pointer_1 (tree
*tp
, int *, void *)
621 if (EXPR_P (*tp
) && TREE_BLOCK (*tp
)
622 && !TREE_USED (TREE_BLOCK (*tp
)))
623 TREE_SET_BLOCK (*tp
, NULL
);
624 if (TREE_CODE (*tp
) == VAR_DECL
&& DECL_DEBUG_EXPR_IS_FROM (*tp
))
626 tree debug_expr
= DECL_DEBUG_EXPR (*tp
);
627 walk_tree (&debug_expr
, clear_unused_block_pointer_1
, NULL
, NULL
);
632 /* Set all block pointer in debug stmt to NULL if the block is unused,
633 so that they will not be streamed out. */
636 clear_unused_block_pointer (void)
639 gimple_stmt_iterator gsi
;
643 FOR_EACH_LOCAL_DECL (cfun
, i
, t
)
644 if (TREE_CODE (t
) == VAR_DECL
&& DECL_DEBUG_EXPR_IS_FROM (t
))
646 tree debug_expr
= DECL_DEBUG_EXPR (t
);
647 walk_tree (&debug_expr
, clear_unused_block_pointer_1
, NULL
, NULL
);
651 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
655 gimple stmt
= gsi_stmt (gsi
);
657 if (!is_gimple_debug (stmt
))
659 b
= gimple_block (stmt
);
660 if (b
&& !TREE_USED (b
))
661 gimple_set_block (stmt
, NULL
);
662 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
663 walk_tree (gimple_op_ptr (stmt
, i
), clear_unused_block_pointer_1
,
668 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
669 indentation level and FLAGS is as in print_generic_expr. */
672 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
677 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
678 TREE_USED (scope
) ? "" : " (unused)",
679 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
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 fprintf (file
, " \n");
698 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
700 fprintf (file
, "%*s", indent
, "");
701 print_generic_decl (file
, var
, flags
);
702 fprintf (file
, "\n");
704 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
706 fprintf (file
, "%*s",indent
, "");
707 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
709 fprintf (file
, " (nonlocalized)\n");
711 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
712 dump_scope_block (file
, indent
+ 2, t
, flags
);
713 fprintf (file
, "\n%*s}\n",indent
, "");
716 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
717 is as in print_generic_expr. */
720 debug_scope_block (tree scope
, int flags
)
722 dump_scope_block (stderr
, 0, scope
, flags
);
726 /* Dump the tree of lexical scopes of current_function_decl to FILE.
727 FLAGS is as in print_generic_expr. */
730 dump_scope_blocks (FILE *file
, int flags
)
732 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
736 /* Dump the tree of lexical scopes of current_function_decl to stderr.
737 FLAGS is as in print_generic_expr. */
740 debug_scope_blocks (int flags
)
742 dump_scope_blocks (stderr
, flags
);
745 /* Remove local variables that are not referenced in the IL. */
748 remove_unused_locals (void)
752 unsigned srcidx
, dstidx
, num
;
753 bool have_local_clobbers
= false;
755 /* Removing declarations from lexical blocks when not optimizing is
756 not only a waste of time, it actually causes differences in stack
761 timevar_push (TV_REMOVE_UNUSED
);
763 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
765 usedvars
= BITMAP_ALLOC (NULL
);
767 /* Walk the CFG marking all referenced symbols. */
770 gimple_stmt_iterator gsi
;
775 /* Walk the statements. */
776 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
778 gimple stmt
= gsi_stmt (gsi
);
779 tree b
= gimple_block (stmt
);
781 if (is_gimple_debug (stmt
))
784 if (gimple_clobber_p (stmt
))
786 have_local_clobbers
= true;
791 TREE_USED (b
) = true;
793 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
794 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
));
797 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
802 gimple phi
= gsi_stmt (gsi
);
804 if (virtual_operand_p (gimple_phi_result (phi
)))
807 def
= gimple_phi_result (phi
);
808 mark_all_vars_used (&def
);
810 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
812 tree arg
= USE_FROM_PTR (arg_p
);
813 int index
= PHI_ARG_INDEX_FROM_USE (arg_p
);
815 LOCATION_BLOCK (gimple_phi_arg_location (phi
, index
));
817 TREE_USED (block
) = true;
818 mark_all_vars_used (&arg
);
822 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
823 if (LOCATION_BLOCK (e
->goto_locus
) != NULL
)
824 TREE_USED (LOCATION_BLOCK (e
->goto_locus
)) = true;
827 /* We do a two-pass approach about the out-of-scope clobbers. We want
828 to remove them if they are the only references to a local variable,
829 but we want to retain them when there's any other. So the first pass
830 ignores them, and the second pass (if there were any) tries to remove
832 if (have_local_clobbers
)
835 gimple_stmt_iterator gsi
;
837 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
839 gimple stmt
= gsi_stmt (gsi
);
840 tree b
= gimple_block (stmt
);
842 if (gimple_clobber_p (stmt
))
844 tree lhs
= gimple_assign_lhs (stmt
);
845 if (TREE_CODE (lhs
) == VAR_DECL
&& !is_used_p (lhs
))
847 unlink_stmt_vdef (stmt
);
848 gsi_remove (&gsi
, true);
853 TREE_USED (b
) = true;
859 cfun
->has_local_explicit_reg_vars
= false;
861 /* Remove unmarked local and global vars from local_decls. */
862 num
= vec_safe_length (cfun
->local_decls
);
863 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
865 var
= (*cfun
->local_decls
)[srcidx
];
866 if (TREE_CODE (var
) == VAR_DECL
)
868 if (!is_used_p (var
))
871 if (cfun
->nonlocal_goto_save_area
872 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
873 cfun
->nonlocal_goto_save_area
= NULL
;
874 /* Release any default def associated with var. */
875 if ((def
= ssa_default_def (cfun
, var
)) != NULL_TREE
)
877 set_ssa_default_def (cfun
, var
, NULL_TREE
);
878 release_ssa_name (def
);
883 if (TREE_CODE (var
) == VAR_DECL
884 && DECL_HARD_REGISTER (var
)
885 && !is_global_var (var
))
886 cfun
->has_local_explicit_reg_vars
= true;
888 if (srcidx
!= dstidx
)
889 (*cfun
->local_decls
)[dstidx
] = var
;
894 statistics_counter_event (cfun
, "unused VAR_DECLs removed", num
- dstidx
);
895 cfun
->local_decls
->truncate (dstidx
);
898 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
));
899 clear_unused_block_pointer ();
901 BITMAP_FREE (usedvars
);
903 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
905 fprintf (dump_file
, "Scope blocks after cleanups:\n");
906 dump_scope_blocks (dump_file
, dump_flags
);
909 timevar_pop (TV_REMOVE_UNUSED
);
912 /* Obstack for globale liveness info bitmaps. We don't want to put these
913 on the default obstack because these bitmaps can grow quite large and
914 we'll hold on to all that memory until the end of the compiler run.
915 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
916 releasing the whole obstack. */
917 static bitmap_obstack liveness_bitmap_obstack
;
919 /* Allocate and return a new live range information object base on MAP. */
921 static tree_live_info_p
922 new_tree_live_info (var_map map
)
924 tree_live_info_p live
;
927 live
= XNEW (struct tree_live_info_d
);
929 live
->num_blocks
= last_basic_block
;
931 live
->livein
= XNEWVEC (bitmap_head
, last_basic_block
);
933 bitmap_initialize (&live
->livein
[bb
->index
], &liveness_bitmap_obstack
);
935 live
->liveout
= XNEWVEC (bitmap_head
, last_basic_block
);
937 bitmap_initialize (&live
->liveout
[bb
->index
], &liveness_bitmap_obstack
);
939 live
->work_stack
= XNEWVEC (int, last_basic_block
);
940 live
->stack_top
= live
->work_stack
;
942 live
->global
= BITMAP_ALLOC (&liveness_bitmap_obstack
);
947 /* Free storage for live range info object LIVE. */
950 delete_tree_live_info (tree_live_info_p live
)
952 bitmap_obstack_release (&liveness_bitmap_obstack
);
953 free (live
->work_stack
);
954 free (live
->liveout
);
960 /* Visit basic block BB and propagate any required live on entry bits from
961 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
962 TMP is a temporary work bitmap which is passed in to avoid reallocating
966 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
974 gcc_assert (!bitmap_bit_p (visited
, bb
->index
));
976 bitmap_set_bit (visited
, bb
->index
);
977 loe
= live_on_entry (live
, bb
);
979 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
982 if (pred_bb
== ENTRY_BLOCK_PTR
)
984 /* TMP is variables live-on-entry from BB that aren't defined in the
985 predecessor block. This should be the live on entry vars to pred.
986 Note that liveout is the DEFs in a block while live on entry is
988 bitmap_and_compl (tmp
, loe
, &live
->liveout
[pred_bb
->index
]);
990 /* Add these bits to live-on-entry for the pred. if there are any
991 changes, and pred_bb has been visited already, add it to the
993 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
994 if (bitmap_bit_p (visited
, pred_bb
->index
) && change
)
996 bitmap_clear_bit (visited
, pred_bb
->index
);
997 *(live
->stack_top
)++ = pred_bb
->index
;
1003 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
1004 of all the variables. */
1007 live_worklist (tree_live_info_p live
)
1011 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
1012 bitmap tmp
= BITMAP_ALLOC (&liveness_bitmap_obstack
);
1014 bitmap_clear (visited
);
1016 /* Visit all the blocks in reverse order and propagate live on entry values
1017 into the predecessors blocks. */
1018 FOR_EACH_BB_REVERSE (bb
)
1019 loe_visit_block (live
, bb
, visited
, tmp
);
1021 /* Process any blocks which require further iteration. */
1022 while (live
->stack_top
!= live
->work_stack
)
1024 b
= *--(live
->stack_top
);
1025 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
1029 sbitmap_free (visited
);
1033 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1034 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1035 in the liveout vector. */
1038 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1043 basic_block def_bb
= NULL
;
1044 imm_use_iterator imm_iter
;
1045 bool global
= false;
1047 p
= var_to_partition (live
->map
, ssa_name
);
1048 if (p
== NO_PARTITION
)
1051 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1054 def_bb
= gimple_bb (stmt
);
1055 /* Mark defs in liveout bitmap temporarily. */
1057 bitmap_set_bit (&live
->liveout
[def_bb
->index
], p
);
1060 def_bb
= ENTRY_BLOCK_PTR
;
1062 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1063 add it to the list of live on entry blocks. */
1064 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1066 gimple use_stmt
= USE_STMT (use
);
1067 basic_block add_block
= NULL
;
1069 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1071 /* Uses in PHI's are considered to be live at exit of the SRC block
1072 as this is where a copy would be inserted. Check to see if it is
1073 defined in that block, or whether its live on entry. */
1074 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1075 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
1076 if (e
->src
!= ENTRY_BLOCK_PTR
)
1078 if (e
->src
!= def_bb
)
1082 else if (is_gimple_debug (use_stmt
))
1086 /* If its not defined in this block, its live on entry. */
1087 basic_block use_bb
= gimple_bb (use_stmt
);
1088 if (use_bb
!= def_bb
)
1092 /* If there was a live on entry use, set the bit. */
1096 bitmap_set_bit (&live
->livein
[add_block
->index
], p
);
1100 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1101 on entry blocks between the def and all the uses. */
1103 bitmap_set_bit (live
->global
, p
);
1107 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1110 calculate_live_on_exit (tree_live_info_p liveinfo
)
1116 /* live on entry calculations used liveout vectors for defs, clear them. */
1118 bitmap_clear (&liveinfo
->liveout
[bb
->index
]);
1120 /* Set all the live-on-exit bits for uses in PHIs. */
1123 gimple_stmt_iterator gsi
;
1126 /* Mark the PHI arguments which are live on exit to the pred block. */
1127 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1129 gimple phi
= gsi_stmt (gsi
);
1130 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1132 tree t
= PHI_ARG_DEF (phi
, i
);
1135 if (TREE_CODE (t
) != SSA_NAME
)
1138 p
= var_to_partition (liveinfo
->map
, t
);
1139 if (p
== NO_PARTITION
)
1141 e
= gimple_phi_arg_edge (phi
, i
);
1142 if (e
->src
!= ENTRY_BLOCK_PTR
)
1143 bitmap_set_bit (&liveinfo
->liveout
[e
->src
->index
], p
);
1147 /* Add each successors live on entry to this bock live on exit. */
1148 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1149 if (e
->dest
!= EXIT_BLOCK_PTR
)
1150 bitmap_ior_into (&liveinfo
->liveout
[bb
->index
],
1151 live_on_entry (liveinfo
, e
->dest
));
1156 /* Given partition map MAP, calculate all the live on entry bitmaps for
1157 each partition. Return a new live info object. */
1160 calculate_live_ranges (var_map map
)
1164 tree_live_info_p live
;
1166 bitmap_obstack_initialize (&liveness_bitmap_obstack
);
1167 live
= new_tree_live_info (map
);
1168 for (i
= 0; i
< num_var_partitions (map
); i
++)
1170 var
= partition_to_var (map
, i
);
1171 if (var
!= NULL_TREE
)
1172 set_var_live_on_entry (var
, live
);
1175 live_worklist (live
);
1177 #ifdef ENABLE_CHECKING
1178 verify_live_on_entry (live
);
1181 calculate_live_on_exit (live
);
1186 /* Output partition map MAP to file F. */
1189 dump_var_map (FILE *f
, var_map map
)
1195 fprintf (f
, "\nPartition map \n\n");
1197 for (x
= 0; x
< map
->num_partitions
; x
++)
1199 if (map
->view_to_partition
!= NULL
)
1200 p
= map
->view_to_partition
[x
];
1204 if (ssa_name (p
) == NULL_TREE
1205 || virtual_operand_p (ssa_name (p
)))
1209 for (y
= 1; y
< num_ssa_names
; y
++)
1211 p
= partition_find (map
->var_partition
, y
);
1212 if (map
->partition_to_view
)
1213 p
= map
->partition_to_view
[p
];
1218 fprintf(f
, "Partition %d (", x
);
1219 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1222 fprintf (f
, "%d ", y
);
1232 /* Output live range info LIVE to file F, controlled by FLAG. */
1235 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1239 var_map map
= live
->map
;
1242 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1246 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1247 EXECUTE_IF_SET_IN_BITMAP (&live
->livein
[bb
->index
], 0, i
, bi
)
1249 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1256 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1260 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1261 EXECUTE_IF_SET_IN_BITMAP (&live
->liveout
[bb
->index
], 0, i
, bi
)
1263 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1271 #ifdef ENABLE_CHECKING
1272 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1275 register_ssa_partition_check (tree ssa_var
)
1277 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1278 if (virtual_operand_p (ssa_var
))
1280 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1281 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1282 fprintf (stderr
, " in the SSA->Normal phase.\n");
1283 internal_error ("SSA corruption");
1288 /* Verify that the info in LIVE matches the current cfg. */
1291 verify_live_on_entry (tree_live_info_p live
)
1300 var_map map
= live
->map
;
1302 /* Check for live on entry partitions and report those with a DEF in
1303 the program. This will typically mean an optimization has done
1305 bb
= ENTRY_BLOCK_PTR
;
1307 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1309 int entry_block
= e
->dest
->index
;
1310 if (e
->dest
== EXIT_BLOCK_PTR
)
1312 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1317 var
= partition_to_var (map
, i
);
1318 stmt
= SSA_NAME_DEF_STMT (var
);
1319 tmp
= gimple_bb (stmt
);
1320 if (SSA_NAME_VAR (var
))
1321 d
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1323 loe
= live_on_entry (live
, e
->dest
);
1324 if (loe
&& bitmap_bit_p (loe
, i
))
1326 if (!gimple_nop_p (stmt
))
1329 print_generic_expr (stderr
, var
, TDF_SLIM
);
1330 fprintf (stderr
, " is defined ");
1332 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1333 fprintf (stderr
, "by:\n");
1334 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1335 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1337 fprintf (stderr
, " So it appears to have multiple defs.\n");
1344 print_generic_expr (stderr
, var
, TDF_SLIM
);
1345 fprintf (stderr
, " is live-on-entry to BB%d ",
1349 fprintf (stderr
, " but is not the default def of ");
1350 print_generic_expr (stderr
, d
, TDF_SLIM
);
1351 fprintf (stderr
, "\n");
1354 fprintf (stderr
, " and there is no default def.\n");
1361 /* The only way this var shouldn't be marked live on entry is
1362 if it occurs in a PHI argument of the block. */
1365 gimple_stmt_iterator gsi
;
1366 for (gsi
= gsi_start_phis (e
->dest
);
1367 !gsi_end_p (gsi
) && !ok
;
1370 gimple phi
= gsi_stmt (gsi
);
1371 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1372 if (var
== gimple_phi_arg_def (phi
, z
))
1381 print_generic_expr (stderr
, var
, TDF_SLIM
);
1382 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1384 fprintf (stderr
, "but it is a default def so it should be.\n");
1388 gcc_assert (num
<= 0);