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"
24 #include "hash-table.h"
27 #include "gimple-pretty-print.h"
30 #include "basic-block.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "gimple-expr.h"
36 #include "gimple-iterator.h"
37 #include "gimple-ssa.h"
38 #include "tree-phinodes.h"
39 #include "ssa-iterators.h"
40 #include "stringpool.h"
41 #include "tree-ssanames.h"
46 #include "tree-ssa-live.h"
47 #include "diagnostic-core.h"
51 #ifdef ENABLE_CHECKING
52 static void verify_live_on_entry (tree_live_info_p
);
56 /* VARMAP maintains a mapping from SSA version number to real variables.
58 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
59 only member of it's own partition. Coalescing will attempt to group any
60 ssa_names which occur in a copy or in a PHI node into the same partition.
62 At the end of out-of-ssa, each partition becomes a "real" variable and is
63 rewritten as a compiler variable.
65 The var_map data structure is used to manage these partitions. It allows
66 partitions to be combined, and determines which partition belongs to what
67 ssa_name or variable, and vice versa. */
70 /* Hashtable helpers. */
72 struct tree_int_map_hasher
: typed_noop_remove
<tree_int_map
>
74 typedef tree_int_map value_type
;
75 typedef tree_int_map compare_type
;
76 static inline hashval_t
hash (const value_type
*);
77 static inline bool equal (const value_type
*, const compare_type
*);
81 tree_int_map_hasher::hash (const value_type
*v
)
83 return tree_map_base_hash (v
);
87 tree_int_map_hasher::equal (const value_type
*v
, const compare_type
*c
)
89 return tree_int_map_eq (v
, c
);
93 /* This routine will initialize the basevar fields of MAP. */
96 var_map_base_init (var_map map
)
100 hash_table
<tree_int_map_hasher
> tree_to_index
;
101 struct tree_int_map
*m
, *mapstorage
;
103 num_part
= num_var_partitions (map
);
104 tree_to_index
.create (num_part
);
105 /* We can have at most num_part entries in the hash tables, so it's
106 enough to allocate so many map elements once, saving some malloc
108 mapstorage
= m
= XNEWVEC (struct tree_int_map
, num_part
);
110 /* If a base table already exists, clear it, otherwise create it. */
111 free (map
->partition_to_base_index
);
112 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
114 /* Build the base variable list, and point partitions at their bases. */
115 for (x
= 0; x
< num_part
; x
++)
117 struct tree_int_map
**slot
;
119 var
= partition_to_var (map
, x
);
120 if (SSA_NAME_VAR (var
)
121 && (!VAR_P (SSA_NAME_VAR (var
))
122 || !DECL_IGNORED_P (SSA_NAME_VAR (var
))))
123 m
->base
.from
= SSA_NAME_VAR (var
);
125 /* This restricts what anonymous SSA names we can coalesce
126 as it restricts the sets we compute conflicts for.
127 Using TREE_TYPE to generate sets is the easies as
128 type equivalency also holds for SSA names with the same
131 Check gimple_can_coalesce_p when changing this code. */
132 m
->base
.from
= (TYPE_CANONICAL (TREE_TYPE (var
))
133 ? TYPE_CANONICAL (TREE_TYPE (var
))
135 /* If base variable hasn't been seen, set it up. */
136 slot
= tree_to_index
.find_slot (m
, INSERT
);
139 baseindex
= m
- mapstorage
;
145 baseindex
= (*slot
)->to
;
146 map
->partition_to_base_index
[x
] = baseindex
;
149 map
->num_basevars
= m
- mapstorage
;
152 tree_to_index
. dispose ();
156 /* Remove the base table in MAP. */
159 var_map_base_fini (var_map map
)
161 /* Free the basevar info if it is present. */
162 if (map
->partition_to_base_index
!= NULL
)
164 free (map
->partition_to_base_index
);
165 map
->partition_to_base_index
= NULL
;
166 map
->num_basevars
= 0;
169 /* Create a variable partition map of SIZE, initialize and return it. */
172 init_var_map (int size
)
176 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
177 map
->var_partition
= partition_new (size
);
179 map
->partition_to_view
= NULL
;
180 map
->view_to_partition
= NULL
;
181 map
->num_partitions
= size
;
182 map
->partition_size
= size
;
183 map
->num_basevars
= 0;
184 map
->partition_to_base_index
= NULL
;
189 /* Free memory associated with MAP. */
192 delete_var_map (var_map map
)
194 var_map_base_fini (map
);
195 partition_delete (map
->var_partition
);
196 free (map
->partition_to_view
);
197 free (map
->view_to_partition
);
202 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
203 Returns the partition which represents the new partition. If the two
204 partitions cannot be combined, NO_PARTITION is returned. */
207 var_union (var_map map
, tree var1
, tree var2
)
211 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
212 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
214 /* This is independent of partition_to_view. If partition_to_view is
215 on, then whichever one of these partitions is absorbed will never have a
216 dereference into the partition_to_view array any more. */
218 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
219 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
221 gcc_assert (p1
!= NO_PARTITION
);
222 gcc_assert (p2
!= NO_PARTITION
);
227 p3
= partition_union (map
->var_partition
, p1
, p2
);
229 if (map
->partition_to_view
)
230 p3
= map
->partition_to_view
[p3
];
236 /* Compress the partition numbers in MAP such that they fall in the range
237 0..(num_partitions-1) instead of wherever they turned out during
238 the partitioning exercise. This removes any references to unused
239 partitions, thereby allowing bitmaps and other vectors to be much
242 This is implemented such that compaction doesn't affect partitioning.
243 Ie., once partitions are created and possibly merged, running one
244 or more different kind of compaction will not affect the partitions
245 themselves. Their index might change, but all the same variables will
246 still be members of the same partition group. This allows work on reduced
247 sets, and no loss of information when a larger set is later desired.
249 In particular, coalescing can work on partitions which have 2 or more
250 definitions, and then 'recompact' later to include all the single
251 definitions for assignment to program variables. */
254 /* Set MAP back to the initial state of having no partition view. Return a
255 bitmap which has a bit set for each partition number which is in use in the
259 partition_view_init (var_map map
)
265 used
= BITMAP_ALLOC (NULL
);
267 /* Already in a view? Abandon the old one. */
268 if (map
->partition_to_view
)
270 free (map
->partition_to_view
);
271 map
->partition_to_view
= NULL
;
273 if (map
->view_to_partition
)
275 free (map
->view_to_partition
);
276 map
->view_to_partition
= NULL
;
279 /* Find out which partitions are actually referenced. */
280 for (x
= 0; x
< map
->partition_size
; x
++)
282 tmp
= partition_find (map
->var_partition
, x
);
283 if (ssa_name (tmp
) != NULL_TREE
&& !virtual_operand_p (ssa_name (tmp
))
284 && (!has_zero_uses (ssa_name (tmp
))
285 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
286 bitmap_set_bit (used
, tmp
);
289 map
->num_partitions
= map
->partition_size
;
294 /* This routine will finalize the view data for MAP based on the partitions
295 set in SELECTED. This is either the same bitmap returned from
296 partition_view_init, or a trimmed down version if some of those partitions
297 were not desired in this view. SELECTED is freed before returning. */
300 partition_view_fini (var_map map
, bitmap selected
)
303 unsigned count
, i
, x
, limit
;
305 gcc_assert (selected
);
307 count
= bitmap_count_bits (selected
);
308 limit
= map
->partition_size
;
310 /* If its a one-to-one ratio, we don't need any view compaction. */
313 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
314 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
315 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
318 /* Give each selected partition an index. */
319 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
321 map
->partition_to_view
[x
] = i
;
322 map
->view_to_partition
[i
] = x
;
325 gcc_assert (i
== count
);
326 map
->num_partitions
= i
;
329 BITMAP_FREE (selected
);
333 /* Create a partition view which includes all the used partitions in MAP. If
334 WANT_BASES is true, create the base variable map as well. */
337 partition_view_normal (var_map map
, bool want_bases
)
341 used
= partition_view_init (map
);
342 partition_view_fini (map
, used
);
345 var_map_base_init (map
);
347 var_map_base_fini (map
);
351 /* Create a partition view in MAP which includes just partitions which occur in
352 the bitmap ONLY. If WANT_BASES is true, create the base variable map
356 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
359 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
363 used
= partition_view_init (map
);
364 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
366 p
= partition_find (map
->var_partition
, x
);
367 gcc_assert (bitmap_bit_p (used
, p
));
368 bitmap_set_bit (new_partitions
, p
);
370 partition_view_fini (map
, new_partitions
);
373 var_map_base_init (map
);
375 var_map_base_fini (map
);
379 static bitmap usedvars
;
381 /* Mark VAR as used, so that it'll be preserved during rtl expansion.
382 Returns true if VAR wasn't marked before. */
385 set_is_used (tree var
)
387 return bitmap_set_bit (usedvars
, DECL_UID (var
));
390 /* Return true if VAR is marked as used. */
395 return bitmap_bit_p (usedvars
, DECL_UID (var
));
398 static inline void mark_all_vars_used (tree
*);
400 /* Helper function for mark_all_vars_used, called via walk_tree. */
403 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
406 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
409 if (TREE_CODE (t
) == SSA_NAME
)
412 t
= SSA_NAME_VAR (t
);
417 if (IS_EXPR_CODE_CLASS (c
)
418 && (b
= TREE_BLOCK (t
)) != NULL
)
419 TREE_USED (b
) = true;
421 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
422 fields do not contain vars. */
423 if (TREE_CODE (t
) == TARGET_MEM_REF
)
425 mark_all_vars_used (&TMR_BASE (t
));
426 mark_all_vars_used (&TMR_INDEX (t
));
427 mark_all_vars_used (&TMR_INDEX2 (t
));
432 /* Only need to mark VAR_DECLS; parameters and return results are not
433 eliminated as unused. */
434 if (TREE_CODE (t
) == VAR_DECL
)
436 /* When a global var becomes used for the first time also walk its
437 initializer (non global ones don't have any). */
438 if (set_is_used (t
) && is_global_var (t
))
439 mark_all_vars_used (&DECL_INITIAL (t
));
441 /* remove_unused_scope_block_p requires information about labels
442 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
443 else if (TREE_CODE (t
) == LABEL_DECL
)
444 /* Although the TREE_USED values that the frontend uses would be
445 acceptable (albeit slightly over-conservative) for our purposes,
446 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
447 must re-compute it here. */
450 if (IS_TYPE_OR_DECL_P (t
))
456 /* Mark the scope block SCOPE and its subblocks unused when they can be
457 possibly eliminated if dead. */
460 mark_scope_block_unused (tree scope
)
463 TREE_USED (scope
) = false;
464 if (!(*debug_hooks
->ignore_block
) (scope
))
465 TREE_USED (scope
) = true;
466 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
467 mark_scope_block_unused (t
);
470 /* Look if the block is dead (by possibly eliminating its dead subblocks)
471 and return true if so.
472 Block is declared dead if:
473 1) No statements are associated with it.
474 2) Declares no live variables
475 3) All subblocks are dead
476 or there is precisely one subblocks and the block
477 has same abstract origin as outer block and declares
478 no variables, so it is pure wrapper.
479 When we are not outputting full debug info, we also eliminate dead variables
480 out of scope blocks to let them to be recycled by GGC and to save copying work
481 done by the inliner. */
484 remove_unused_scope_block_p (tree scope
)
487 bool unused
= !TREE_USED (scope
);
490 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
492 next
= &DECL_CHAIN (*t
);
494 /* Debug info of nested function refers to the block of the
495 function. We might stil call it even if all statements
496 of function it was nested into was elliminated.
498 TODO: We can actually look into cgraph to see if function
499 will be output to file. */
500 if (TREE_CODE (*t
) == FUNCTION_DECL
)
503 /* If a decl has a value expr, we need to instantiate it
504 regardless of debug info generation, to avoid codegen
505 differences in memory overlap tests. update_equiv_regs() may
506 indirectly call validate_equiv_mem() to test whether a
507 SET_DEST overlaps with others, and if the value expr changes
508 by virtual register instantiation, we may get end up with
509 different results. */
510 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
513 /* Remove everything we don't generate debug info for. */
514 else if (DECL_IGNORED_P (*t
))
516 *t
= DECL_CHAIN (*t
);
520 /* When we are outputting debug info, we usually want to output
521 info about optimized-out variables in the scope blocks.
522 Exception are the scope blocks not containing any instructions
523 at all so user can't get into the scopes at first place. */
524 else if (is_used_p (*t
))
526 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
527 /* For labels that are still used in the IL, the decision to
528 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
529 risk having different ordering in debug vs. non-debug builds
530 during inlining or versioning.
531 A label appearing here (we have already checked DECL_IGNORED_P)
532 should not be used in the IL unless it has been explicitly used
533 before, so we use TREE_USED as an approximation. */
534 /* In principle, we should do the same here as for the debug case
535 below, however, when debugging, there might be additional nested
536 levels that keep an upper level with a label live, so we have to
537 force this block to be considered used, too. */
540 /* When we are not doing full debug info, we however can keep around
541 only the used variables for cfgexpand's memory packing saving quite
544 For sake of -g3, we keep around those vars but we don't count this as
545 use of block, so innermost block with no used vars and no instructions
546 can be considered dead. We only want to keep around blocks user can
547 breakpoint into and ask about value of optimized out variables.
549 Similarly we need to keep around types at least until all
550 variables of all nested blocks are gone. We track no
551 information on whether given type is used or not, so we have
552 to keep them even when not emitting debug information,
553 otherwise we may end up remapping variables and their (local)
554 types in different orders depending on whether debug
555 information is being generated. */
557 else if (TREE_CODE (*t
) == TYPE_DECL
558 || debug_info_level
== DINFO_LEVEL_NORMAL
559 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
563 *t
= DECL_CHAIN (*t
);
568 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
569 if (remove_unused_scope_block_p (*t
))
571 if (BLOCK_SUBBLOCKS (*t
))
573 tree next
= BLOCK_CHAIN (*t
);
574 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
576 *t
= BLOCK_SUBBLOCKS (*t
);
577 while (BLOCK_CHAIN (*t
))
579 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
580 t
= &BLOCK_CHAIN (*t
);
582 BLOCK_CHAIN (*t
) = next
;
583 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
584 t
= &BLOCK_CHAIN (*t
);
588 *t
= BLOCK_CHAIN (*t
);
592 t
= &BLOCK_CHAIN (*t
);
599 /* Outer scope is always used. */
600 else if (!BLOCK_SUPERCONTEXT (scope
)
601 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
603 /* Innermost blocks with no live variables nor statements can be always
605 else if (!nsubblocks
)
607 /* When not generating debug info we can eliminate info on unused
609 else if (debug_info_level
== DINFO_LEVEL_NONE
)
611 /* Even for -g0 don't prune outer scopes from artificial
612 functions, otherwise diagnostics using tree_nonartificial_location
613 will not be emitted properly. */
614 if (inlined_function_outer_scope_p (scope
))
619 && TREE_CODE (ao
) == BLOCK
620 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
621 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
623 && TREE_CODE (ao
) == FUNCTION_DECL
624 && DECL_DECLARED_INLINE_P (ao
)
625 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
629 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
631 /* See if this block is important for representation of inlined function.
632 Inlined functions are always represented by block with
633 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
635 else if (inlined_function_outer_scope_p (scope
))
638 /* Verfify that only blocks with source location set
639 are entry points to the inlined functions. */
640 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
))
641 == UNKNOWN_LOCATION
);
643 TREE_USED (scope
) = !unused
;
647 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
648 eliminated during the tree->rtl conversion process. */
651 mark_all_vars_used (tree
*expr_p
)
653 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
656 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
659 clear_unused_block_pointer_1 (tree
*tp
, int *, void *)
661 if (EXPR_P (*tp
) && TREE_BLOCK (*tp
)
662 && !TREE_USED (TREE_BLOCK (*tp
)))
663 TREE_SET_BLOCK (*tp
, NULL
);
667 /* Set all block pointer in debug or clobber stmt to NULL if the block
668 is unused, so that they will not be streamed out. */
671 clear_unused_block_pointer (void)
674 gimple_stmt_iterator gsi
;
677 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
681 gimple stmt
= gsi_stmt (gsi
);
683 if (!is_gimple_debug (stmt
) && !gimple_clobber_p (stmt
))
685 b
= gimple_block (stmt
);
686 if (b
&& !TREE_USED (b
))
687 gimple_set_block (stmt
, NULL
);
688 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
689 walk_tree (gimple_op_ptr (stmt
, i
), clear_unused_block_pointer_1
,
694 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
695 indentation level and FLAGS is as in print_generic_expr. */
698 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
703 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
704 TREE_USED (scope
) ? "" : " (unused)",
705 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
706 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
)) != UNKNOWN_LOCATION
)
708 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
709 fprintf (file
, " %s:%i", s
.file
, s
.line
);
711 if (BLOCK_ABSTRACT_ORIGIN (scope
))
713 tree origin
= block_ultimate_origin (scope
);
716 fprintf (file
, " Originating from :");
718 print_generic_decl (file
, origin
, flags
);
720 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
723 fprintf (file
, " \n");
724 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
726 fprintf (file
, "%*s", indent
, "");
727 print_generic_decl (file
, var
, flags
);
728 fprintf (file
, "\n");
730 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
732 fprintf (file
, "%*s",indent
, "");
733 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
735 fprintf (file
, " (nonlocalized)\n");
737 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
738 dump_scope_block (file
, indent
+ 2, t
, flags
);
739 fprintf (file
, "\n%*s}\n",indent
, "");
742 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
743 is as in print_generic_expr. */
746 debug_scope_block (tree scope
, int flags
)
748 dump_scope_block (stderr
, 0, scope
, flags
);
752 /* Dump the tree of lexical scopes of current_function_decl to FILE.
753 FLAGS is as in print_generic_expr. */
756 dump_scope_blocks (FILE *file
, int flags
)
758 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
762 /* Dump the tree of lexical scopes of current_function_decl to stderr.
763 FLAGS is as in print_generic_expr. */
766 debug_scope_blocks (int flags
)
768 dump_scope_blocks (stderr
, flags
);
771 /* Remove local variables that are not referenced in the IL. */
774 remove_unused_locals (void)
778 unsigned srcidx
, dstidx
, num
;
779 bool have_local_clobbers
= false;
781 /* Removing declarations from lexical blocks when not optimizing is
782 not only a waste of time, it actually causes differences in stack
787 timevar_push (TV_REMOVE_UNUSED
);
789 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
791 usedvars
= BITMAP_ALLOC (NULL
);
793 /* Walk the CFG marking all referenced symbols. */
796 gimple_stmt_iterator gsi
;
801 /* Walk the statements. */
802 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
804 gimple stmt
= gsi_stmt (gsi
);
805 tree b
= gimple_block (stmt
);
807 if (is_gimple_debug (stmt
))
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 (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
828 gimple phi
= gsi_stmt (gsi
);
830 if (virtual_operand_p (gimple_phi_result (phi
)))
833 def
= gimple_phi_result (phi
);
834 mark_all_vars_used (&def
);
836 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
838 tree arg
= USE_FROM_PTR (arg_p
);
839 int index
= PHI_ARG_INDEX_FROM_USE (arg_p
);
841 LOCATION_BLOCK (gimple_phi_arg_location (phi
, index
));
843 TREE_USED (block
) = true;
844 mark_all_vars_used (&arg
);
848 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
849 if (LOCATION_BLOCK (e
->goto_locus
) != NULL
)
850 TREE_USED (LOCATION_BLOCK (e
->goto_locus
)) = true;
853 /* We do a two-pass approach about the out-of-scope clobbers. We want
854 to remove them if they are the only references to a local variable,
855 but we want to retain them when there's any other. So the first pass
856 ignores them, and the second pass (if there were any) tries to remove
858 if (have_local_clobbers
)
861 gimple_stmt_iterator gsi
;
863 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
865 gimple stmt
= gsi_stmt (gsi
);
866 tree b
= gimple_block (stmt
);
868 if (gimple_clobber_p (stmt
))
870 tree lhs
= gimple_assign_lhs (stmt
);
871 tree base
= get_base_address (lhs
);
872 /* Remove clobbers referencing unused vars, or clobbers
873 with MEM_REF lhs referencing uninitialized pointers. */
874 if ((TREE_CODE (base
) == VAR_DECL
&& !is_used_p (base
))
875 || (TREE_CODE (lhs
) == MEM_REF
876 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
877 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs
, 0))
878 && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs
, 0)))
881 unlink_stmt_vdef (stmt
);
882 gsi_remove (&gsi
, true);
887 TREE_USED (b
) = true;
893 cfun
->has_local_explicit_reg_vars
= false;
895 /* Remove unmarked local and global vars from local_decls. */
896 num
= vec_safe_length (cfun
->local_decls
);
897 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
899 var
= (*cfun
->local_decls
)[srcidx
];
900 if (TREE_CODE (var
) == VAR_DECL
)
902 if (!is_used_p (var
))
905 if (cfun
->nonlocal_goto_save_area
906 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
907 cfun
->nonlocal_goto_save_area
= NULL
;
908 /* Release any default def associated with var. */
909 if ((def
= ssa_default_def (cfun
, var
)) != NULL_TREE
)
911 set_ssa_default_def (cfun
, var
, NULL_TREE
);
912 release_ssa_name (def
);
917 if (TREE_CODE (var
) == VAR_DECL
918 && DECL_HARD_REGISTER (var
)
919 && !is_global_var (var
))
920 cfun
->has_local_explicit_reg_vars
= true;
922 if (srcidx
!= dstidx
)
923 (*cfun
->local_decls
)[dstidx
] = var
;
928 statistics_counter_event (cfun
, "unused VAR_DECLs removed", num
- dstidx
);
929 cfun
->local_decls
->truncate (dstidx
);
932 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
));
933 clear_unused_block_pointer ();
935 BITMAP_FREE (usedvars
);
937 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
939 fprintf (dump_file
, "Scope blocks after cleanups:\n");
940 dump_scope_blocks (dump_file
, dump_flags
);
943 timevar_pop (TV_REMOVE_UNUSED
);
946 /* Obstack for globale liveness info bitmaps. We don't want to put these
947 on the default obstack because these bitmaps can grow quite large and
948 we'll hold on to all that memory until the end of the compiler run.
949 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
950 releasing the whole obstack. */
951 static bitmap_obstack liveness_bitmap_obstack
;
953 /* Allocate and return a new live range information object base on MAP. */
955 static tree_live_info_p
956 new_tree_live_info (var_map map
)
958 tree_live_info_p live
;
961 live
= XNEW (struct tree_live_info_d
);
963 live
->num_blocks
= last_basic_block
;
965 live
->livein
= XNEWVEC (bitmap_head
, last_basic_block
);
967 bitmap_initialize (&live
->livein
[bb
->index
], &liveness_bitmap_obstack
);
969 live
->liveout
= XNEWVEC (bitmap_head
, last_basic_block
);
971 bitmap_initialize (&live
->liveout
[bb
->index
], &liveness_bitmap_obstack
);
973 live
->work_stack
= XNEWVEC (int, last_basic_block
);
974 live
->stack_top
= live
->work_stack
;
976 live
->global
= BITMAP_ALLOC (&liveness_bitmap_obstack
);
981 /* Free storage for live range info object LIVE. */
984 delete_tree_live_info (tree_live_info_p live
)
986 bitmap_obstack_release (&liveness_bitmap_obstack
);
987 free (live
->work_stack
);
988 free (live
->liveout
);
994 /* Visit basic block BB and propagate any required live on entry bits from
995 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
996 TMP is a temporary work bitmap which is passed in to avoid reallocating
1000 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
1006 basic_block pred_bb
;
1009 gcc_checking_assert (!bitmap_bit_p (visited
, bb
->index
));
1010 bitmap_set_bit (visited
, bb
->index
);
1012 loe
= live_on_entry (live
, bb
);
1014 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1017 if (pred_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1019 /* TMP is variables live-on-entry from BB that aren't defined in the
1020 predecessor block. This should be the live on entry vars to pred.
1021 Note that liveout is the DEFs in a block while live on entry is
1022 being calculated. */
1023 bitmap_and_compl (tmp
, loe
, &live
->liveout
[pred_bb
->index
]);
1025 /* Add these bits to live-on-entry for the pred. if there are any
1026 changes, and pred_bb has been visited already, add it to the
1028 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
1029 if (bitmap_bit_p (visited
, pred_bb
->index
) && change
)
1031 bitmap_clear_bit (visited
, pred_bb
->index
);
1032 *(live
->stack_top
)++ = pred_bb
->index
;
1038 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
1039 of all the variables. */
1042 live_worklist (tree_live_info_p live
)
1046 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
1047 bitmap tmp
= BITMAP_ALLOC (&liveness_bitmap_obstack
);
1049 bitmap_clear (visited
);
1051 /* Visit all the blocks in reverse order and propagate live on entry values
1052 into the predecessors blocks. */
1053 FOR_EACH_BB_REVERSE (bb
)
1054 loe_visit_block (live
, bb
, visited
, tmp
);
1056 /* Process any blocks which require further iteration. */
1057 while (live
->stack_top
!= live
->work_stack
)
1059 b
= *--(live
->stack_top
);
1060 loe_visit_block (live
, BASIC_BLOCK_FOR_FN (cfun
, b
), visited
, tmp
);
1064 sbitmap_free (visited
);
1068 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1069 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1070 in the liveout vector. */
1073 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1078 basic_block def_bb
= NULL
;
1079 imm_use_iterator imm_iter
;
1080 bool global
= false;
1082 p
= var_to_partition (live
->map
, ssa_name
);
1083 if (p
== NO_PARTITION
)
1086 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1089 def_bb
= gimple_bb (stmt
);
1090 /* Mark defs in liveout bitmap temporarily. */
1092 bitmap_set_bit (&live
->liveout
[def_bb
->index
], p
);
1095 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1097 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1098 add it to the list of live on entry blocks. */
1099 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1101 gimple use_stmt
= USE_STMT (use
);
1102 basic_block add_block
= NULL
;
1104 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1106 /* Uses in PHI's are considered to be live at exit of the SRC block
1107 as this is where a copy would be inserted. Check to see if it is
1108 defined in that block, or whether its live on entry. */
1109 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1110 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
1111 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1113 if (e
->src
!= def_bb
)
1117 else if (is_gimple_debug (use_stmt
))
1121 /* If its not defined in this block, its live on entry. */
1122 basic_block use_bb
= gimple_bb (use_stmt
);
1123 if (use_bb
!= def_bb
)
1127 /* If there was a live on entry use, set the bit. */
1131 bitmap_set_bit (&live
->livein
[add_block
->index
], p
);
1135 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1136 on entry blocks between the def and all the uses. */
1138 bitmap_set_bit (live
->global
, p
);
1142 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1145 calculate_live_on_exit (tree_live_info_p liveinfo
)
1151 /* live on entry calculations used liveout vectors for defs, clear them. */
1153 bitmap_clear (&liveinfo
->liveout
[bb
->index
]);
1155 /* Set all the live-on-exit bits for uses in PHIs. */
1158 gimple_stmt_iterator gsi
;
1161 /* Mark the PHI arguments which are live on exit to the pred block. */
1162 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1164 gimple phi
= gsi_stmt (gsi
);
1165 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1167 tree t
= PHI_ARG_DEF (phi
, i
);
1170 if (TREE_CODE (t
) != SSA_NAME
)
1173 p
= var_to_partition (liveinfo
->map
, t
);
1174 if (p
== NO_PARTITION
)
1176 e
= gimple_phi_arg_edge (phi
, i
);
1177 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1178 bitmap_set_bit (&liveinfo
->liveout
[e
->src
->index
], p
);
1182 /* Add each successors live on entry to this bock live on exit. */
1183 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1184 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1185 bitmap_ior_into (&liveinfo
->liveout
[bb
->index
],
1186 live_on_entry (liveinfo
, e
->dest
));
1191 /* Given partition map MAP, calculate all the live on entry bitmaps for
1192 each partition. Return a new live info object. */
1195 calculate_live_ranges (var_map map
)
1199 tree_live_info_p live
;
1201 bitmap_obstack_initialize (&liveness_bitmap_obstack
);
1202 live
= new_tree_live_info (map
);
1203 for (i
= 0; i
< num_var_partitions (map
); i
++)
1205 var
= partition_to_var (map
, i
);
1206 if (var
!= NULL_TREE
)
1207 set_var_live_on_entry (var
, live
);
1210 live_worklist (live
);
1212 #ifdef ENABLE_CHECKING
1213 verify_live_on_entry (live
);
1216 calculate_live_on_exit (live
);
1221 /* Output partition map MAP to file F. */
1224 dump_var_map (FILE *f
, var_map map
)
1230 fprintf (f
, "\nPartition map \n\n");
1232 for (x
= 0; x
< map
->num_partitions
; x
++)
1234 if (map
->view_to_partition
!= NULL
)
1235 p
= map
->view_to_partition
[x
];
1239 if (ssa_name (p
) == NULL_TREE
1240 || virtual_operand_p (ssa_name (p
)))
1244 for (y
= 1; y
< num_ssa_names
; y
++)
1246 p
= partition_find (map
->var_partition
, y
);
1247 if (map
->partition_to_view
)
1248 p
= map
->partition_to_view
[p
];
1253 fprintf (f
, "Partition %d (", x
);
1254 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1257 fprintf (f
, "%d ", y
);
1267 /* Generic dump for the above. */
1270 debug (_var_map
&ref
)
1272 dump_var_map (stderr
, &ref
);
1276 debug (_var_map
*ptr
)
1281 fprintf (stderr
, "<nil>\n");
1285 /* Output live range info LIVE to file F, controlled by FLAG. */
1288 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1292 var_map map
= live
->map
;
1295 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1299 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1300 EXECUTE_IF_SET_IN_BITMAP (&live
->livein
[bb
->index
], 0, i
, bi
)
1302 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1309 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1313 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1314 EXECUTE_IF_SET_IN_BITMAP (&live
->liveout
[bb
->index
], 0, i
, bi
)
1316 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1325 /* Generic dump for the above. */
1328 debug (tree_live_info_d
&ref
)
1330 dump_live_info (stderr
, &ref
, 0);
1334 debug (tree_live_info_d
*ptr
)
1339 fprintf (stderr
, "<nil>\n");
1343 #ifdef ENABLE_CHECKING
1344 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1347 register_ssa_partition_check (tree ssa_var
)
1349 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1350 if (virtual_operand_p (ssa_var
))
1352 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1353 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1354 fprintf (stderr
, " in the SSA->Normal phase.\n");
1355 internal_error ("SSA corruption");
1360 /* Verify that the info in LIVE matches the current cfg. */
1363 verify_live_on_entry (tree_live_info_p live
)
1372 var_map map
= live
->map
;
1374 /* Check for live on entry partitions and report those with a DEF in
1375 the program. This will typically mean an optimization has done
1377 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1379 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1381 int entry_block
= e
->dest
->index
;
1382 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1384 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1389 var
= partition_to_var (map
, i
);
1390 stmt
= SSA_NAME_DEF_STMT (var
);
1391 tmp
= gimple_bb (stmt
);
1392 if (SSA_NAME_VAR (var
))
1393 d
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1395 loe
= live_on_entry (live
, e
->dest
);
1396 if (loe
&& bitmap_bit_p (loe
, i
))
1398 if (!gimple_nop_p (stmt
))
1401 print_generic_expr (stderr
, var
, TDF_SLIM
);
1402 fprintf (stderr
, " is defined ");
1404 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1405 fprintf (stderr
, "by:\n");
1406 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1407 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1409 fprintf (stderr
, " So it appears to have multiple defs.\n");
1416 print_generic_expr (stderr
, var
, TDF_SLIM
);
1417 fprintf (stderr
, " is live-on-entry to BB%d ",
1421 fprintf (stderr
, " but is not the default def of ");
1422 print_generic_expr (stderr
, d
, TDF_SLIM
);
1423 fprintf (stderr
, "\n");
1426 fprintf (stderr
, " and there is no default def.\n");
1433 /* The only way this var shouldn't be marked live on entry is
1434 if it occurs in a PHI argument of the block. */
1437 gimple_stmt_iterator gsi
;
1438 for (gsi
= gsi_start_phis (e
->dest
);
1439 !gsi_end_p (gsi
) && !ok
;
1442 gimple phi
= gsi_stmt (gsi
);
1443 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1444 if (var
== gimple_phi_arg_def (phi
, z
))
1453 print_generic_expr (stderr
, var
, TDF_SLIM
);
1454 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1456 fprintf (stderr
, "but it is a default def so it should be.\n");
1460 gcc_assert (num
<= 0);