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"
31 #include "gimple-iterator.h"
32 #include "gimple-ssa.h"
33 #include "tree-phinodes.h"
34 #include "ssa-iterators.h"
35 #include "stringpool.h"
36 #include "tree-ssanames.h"
41 #include "tree-ssa-live.h"
42 #include "diagnostic-core.h"
46 #ifdef ENABLE_CHECKING
47 static void verify_live_on_entry (tree_live_info_p
);
51 /* VARMAP maintains a mapping from SSA version number to real variables.
53 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
54 only member of it's own partition. Coalescing will attempt to group any
55 ssa_names which occur in a copy or in a PHI node into the same partition.
57 At the end of out-of-ssa, each partition becomes a "real" variable and is
58 rewritten as a compiler variable.
60 The var_map data structure is used to manage these partitions. It allows
61 partitions to be combined, and determines which partition belongs to what
62 ssa_name or variable, and vice versa. */
65 /* Hashtable helpers. */
67 struct tree_int_map_hasher
: typed_noop_remove
<tree_int_map
>
69 typedef tree_int_map value_type
;
70 typedef tree_int_map compare_type
;
71 static inline hashval_t
hash (const value_type
*);
72 static inline bool equal (const value_type
*, const compare_type
*);
76 tree_int_map_hasher::hash (const value_type
*v
)
78 return tree_map_base_hash (v
);
82 tree_int_map_hasher::equal (const value_type
*v
, const compare_type
*c
)
84 return tree_int_map_eq (v
, c
);
88 /* This routine will initialize the basevar fields of MAP. */
91 var_map_base_init (var_map map
)
95 hash_table
<tree_int_map_hasher
> tree_to_index
;
96 struct tree_int_map
*m
, *mapstorage
;
98 num_part
= num_var_partitions (map
);
99 tree_to_index
.create (num_part
);
100 /* We can have at most num_part entries in the hash tables, so it's
101 enough to allocate so many map elements once, saving some malloc
103 mapstorage
= m
= XNEWVEC (struct tree_int_map
, num_part
);
105 /* If a base table already exists, clear it, otherwise create it. */
106 free (map
->partition_to_base_index
);
107 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
109 /* Build the base variable list, and point partitions at their bases. */
110 for (x
= 0; x
< num_part
; x
++)
112 struct tree_int_map
**slot
;
114 var
= partition_to_var (map
, x
);
115 if (SSA_NAME_VAR (var
)
116 && (!VAR_P (SSA_NAME_VAR (var
))
117 || !DECL_IGNORED_P (SSA_NAME_VAR (var
))))
118 m
->base
.from
= SSA_NAME_VAR (var
);
120 /* This restricts what anonymous SSA names we can coalesce
121 as it restricts the sets we compute conflicts for.
122 Using TREE_TYPE to generate sets is the easies as
123 type equivalency also holds for SSA names with the same
126 Check gimple_can_coalesce_p when changing this code. */
127 m
->base
.from
= (TYPE_CANONICAL (TREE_TYPE (var
))
128 ? TYPE_CANONICAL (TREE_TYPE (var
))
130 /* If base variable hasn't been seen, set it up. */
131 slot
= tree_to_index
.find_slot (m
, INSERT
);
134 baseindex
= m
- mapstorage
;
140 baseindex
= (*slot
)->to
;
141 map
->partition_to_base_index
[x
] = baseindex
;
144 map
->num_basevars
= m
- mapstorage
;
147 tree_to_index
. dispose ();
151 /* Remove the base table in MAP. */
154 var_map_base_fini (var_map map
)
156 /* Free the basevar info if it is present. */
157 if (map
->partition_to_base_index
!= NULL
)
159 free (map
->partition_to_base_index
);
160 map
->partition_to_base_index
= NULL
;
161 map
->num_basevars
= 0;
164 /* Create a variable partition map of SIZE, initialize and return it. */
167 init_var_map (int size
)
171 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
172 map
->var_partition
= partition_new (size
);
174 map
->partition_to_view
= NULL
;
175 map
->view_to_partition
= NULL
;
176 map
->num_partitions
= size
;
177 map
->partition_size
= size
;
178 map
->num_basevars
= 0;
179 map
->partition_to_base_index
= NULL
;
184 /* Free memory associated with MAP. */
187 delete_var_map (var_map map
)
189 var_map_base_fini (map
);
190 partition_delete (map
->var_partition
);
191 free (map
->partition_to_view
);
192 free (map
->view_to_partition
);
197 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
198 Returns the partition which represents the new partition. If the two
199 partitions cannot be combined, NO_PARTITION is returned. */
202 var_union (var_map map
, tree var1
, tree var2
)
206 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
207 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
209 /* This is independent of partition_to_view. If partition_to_view is
210 on, then whichever one of these partitions is absorbed will never have a
211 dereference into the partition_to_view array any more. */
213 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
214 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
216 gcc_assert (p1
!= NO_PARTITION
);
217 gcc_assert (p2
!= NO_PARTITION
);
222 p3
= partition_union (map
->var_partition
, p1
, p2
);
224 if (map
->partition_to_view
)
225 p3
= map
->partition_to_view
[p3
];
231 /* Compress the partition numbers in MAP such that they fall in the range
232 0..(num_partitions-1) instead of wherever they turned out during
233 the partitioning exercise. This removes any references to unused
234 partitions, thereby allowing bitmaps and other vectors to be much
237 This is implemented such that compaction doesn't affect partitioning.
238 Ie., once partitions are created and possibly merged, running one
239 or more different kind of compaction will not affect the partitions
240 themselves. Their index might change, but all the same variables will
241 still be members of the same partition group. This allows work on reduced
242 sets, and no loss of information when a larger set is later desired.
244 In particular, coalescing can work on partitions which have 2 or more
245 definitions, and then 'recompact' later to include all the single
246 definitions for assignment to program variables. */
249 /* Set MAP back to the initial state of having no partition view. Return a
250 bitmap which has a bit set for each partition number which is in use in the
254 partition_view_init (var_map map
)
260 used
= BITMAP_ALLOC (NULL
);
262 /* Already in a view? Abandon the old one. */
263 if (map
->partition_to_view
)
265 free (map
->partition_to_view
);
266 map
->partition_to_view
= NULL
;
268 if (map
->view_to_partition
)
270 free (map
->view_to_partition
);
271 map
->view_to_partition
= NULL
;
274 /* Find out which partitions are actually referenced. */
275 for (x
= 0; x
< map
->partition_size
; x
++)
277 tmp
= partition_find (map
->var_partition
, x
);
278 if (ssa_name (tmp
) != NULL_TREE
&& !virtual_operand_p (ssa_name (tmp
))
279 && (!has_zero_uses (ssa_name (tmp
))
280 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
281 bitmap_set_bit (used
, tmp
);
284 map
->num_partitions
= map
->partition_size
;
289 /* This routine will finalize the view data for MAP based on the partitions
290 set in SELECTED. This is either the same bitmap returned from
291 partition_view_init, or a trimmed down version if some of those partitions
292 were not desired in this view. SELECTED is freed before returning. */
295 partition_view_fini (var_map map
, bitmap selected
)
298 unsigned count
, i
, x
, limit
;
300 gcc_assert (selected
);
302 count
= bitmap_count_bits (selected
);
303 limit
= map
->partition_size
;
305 /* If its a one-to-one ratio, we don't need any view compaction. */
308 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
309 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
310 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
313 /* Give each selected partition an index. */
314 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
316 map
->partition_to_view
[x
] = i
;
317 map
->view_to_partition
[i
] = x
;
320 gcc_assert (i
== count
);
321 map
->num_partitions
= i
;
324 BITMAP_FREE (selected
);
328 /* Create a partition view which includes all the used partitions in MAP. If
329 WANT_BASES is true, create the base variable map as well. */
332 partition_view_normal (var_map map
, bool want_bases
)
336 used
= partition_view_init (map
);
337 partition_view_fini (map
, used
);
340 var_map_base_init (map
);
342 var_map_base_fini (map
);
346 /* Create a partition view in MAP which includes just partitions which occur in
347 the bitmap ONLY. If WANT_BASES is true, create the base variable map
351 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
354 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
358 used
= partition_view_init (map
);
359 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
361 p
= partition_find (map
->var_partition
, x
);
362 gcc_assert (bitmap_bit_p (used
, p
));
363 bitmap_set_bit (new_partitions
, p
);
365 partition_view_fini (map
, new_partitions
);
368 var_map_base_init (map
);
370 var_map_base_fini (map
);
374 static bitmap usedvars
;
376 /* Mark VAR as used, so that it'll be preserved during rtl expansion.
377 Returns true if VAR wasn't marked before. */
380 set_is_used (tree var
)
382 return bitmap_set_bit (usedvars
, DECL_UID (var
));
385 /* Return true if VAR is marked as used. */
390 return bitmap_bit_p (usedvars
, DECL_UID (var
));
393 static inline void mark_all_vars_used (tree
*);
395 /* Helper function for mark_all_vars_used, called via walk_tree. */
398 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
401 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
404 if (TREE_CODE (t
) == SSA_NAME
)
407 t
= SSA_NAME_VAR (t
);
412 if (IS_EXPR_CODE_CLASS (c
)
413 && (b
= TREE_BLOCK (t
)) != NULL
)
414 TREE_USED (b
) = true;
416 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
417 fields do not contain vars. */
418 if (TREE_CODE (t
) == TARGET_MEM_REF
)
420 mark_all_vars_used (&TMR_BASE (t
));
421 mark_all_vars_used (&TMR_INDEX (t
));
422 mark_all_vars_used (&TMR_INDEX2 (t
));
427 /* Only need to mark VAR_DECLS; parameters and return results are not
428 eliminated as unused. */
429 if (TREE_CODE (t
) == VAR_DECL
)
431 /* When a global var becomes used for the first time also walk its
432 initializer (non global ones don't have any). */
433 if (set_is_used (t
) && is_global_var (t
))
434 mark_all_vars_used (&DECL_INITIAL (t
));
436 /* remove_unused_scope_block_p requires information about labels
437 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
438 else if (TREE_CODE (t
) == LABEL_DECL
)
439 /* Although the TREE_USED values that the frontend uses would be
440 acceptable (albeit slightly over-conservative) for our purposes,
441 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
442 must re-compute it here. */
445 if (IS_TYPE_OR_DECL_P (t
))
451 /* Mark the scope block SCOPE and its subblocks unused when they can be
452 possibly eliminated if dead. */
455 mark_scope_block_unused (tree scope
)
458 TREE_USED (scope
) = false;
459 if (!(*debug_hooks
->ignore_block
) (scope
))
460 TREE_USED (scope
) = true;
461 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
462 mark_scope_block_unused (t
);
465 /* Look if the block is dead (by possibly eliminating its dead subblocks)
466 and return true if so.
467 Block is declared dead if:
468 1) No statements are associated with it.
469 2) Declares no live variables
470 3) All subblocks are dead
471 or there is precisely one subblocks and the block
472 has same abstract origin as outer block and declares
473 no variables, so it is pure wrapper.
474 When we are not outputting full debug info, we also eliminate dead variables
475 out of scope blocks to let them to be recycled by GGC and to save copying work
476 done by the inliner. */
479 remove_unused_scope_block_p (tree scope
)
482 bool unused
= !TREE_USED (scope
);
485 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
487 next
= &DECL_CHAIN (*t
);
489 /* Debug info of nested function refers to the block of the
490 function. We might stil call it even if all statements
491 of function it was nested into was elliminated.
493 TODO: We can actually look into cgraph to see if function
494 will be output to file. */
495 if (TREE_CODE (*t
) == FUNCTION_DECL
)
498 /* If a decl has a value expr, we need to instantiate it
499 regardless of debug info generation, to avoid codegen
500 differences in memory overlap tests. update_equiv_regs() may
501 indirectly call validate_equiv_mem() to test whether a
502 SET_DEST overlaps with others, and if the value expr changes
503 by virtual register instantiation, we may get end up with
504 different results. */
505 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
508 /* Remove everything we don't generate debug info for. */
509 else if (DECL_IGNORED_P (*t
))
511 *t
= DECL_CHAIN (*t
);
515 /* When we are outputting debug info, we usually want to output
516 info about optimized-out variables in the scope blocks.
517 Exception are the scope blocks not containing any instructions
518 at all so user can't get into the scopes at first place. */
519 else if (is_used_p (*t
))
521 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
522 /* For labels that are still used in the IL, the decision to
523 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
524 risk having different ordering in debug vs. non-debug builds
525 during inlining or versioning.
526 A label appearing here (we have already checked DECL_IGNORED_P)
527 should not be used in the IL unless it has been explicitly used
528 before, so we use TREE_USED as an approximation. */
529 /* In principle, we should do the same here as for the debug case
530 below, however, when debugging, there might be additional nested
531 levels that keep an upper level with a label live, so we have to
532 force this block to be considered used, too. */
535 /* When we are not doing full debug info, we however can keep around
536 only the used variables for cfgexpand's memory packing saving quite
539 For sake of -g3, we keep around those vars but we don't count this as
540 use of block, so innermost block with no used vars and no instructions
541 can be considered dead. We only want to keep around blocks user can
542 breakpoint into and ask about value of optimized out variables.
544 Similarly we need to keep around types at least until all
545 variables of all nested blocks are gone. We track no
546 information on whether given type is used or not, so we have
547 to keep them even when not emitting debug information,
548 otherwise we may end up remapping variables and their (local)
549 types in different orders depending on whether debug
550 information is being generated. */
552 else if (TREE_CODE (*t
) == TYPE_DECL
553 || debug_info_level
== DINFO_LEVEL_NORMAL
554 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
558 *t
= DECL_CHAIN (*t
);
563 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
564 if (remove_unused_scope_block_p (*t
))
566 if (BLOCK_SUBBLOCKS (*t
))
568 tree next
= BLOCK_CHAIN (*t
);
569 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
571 *t
= BLOCK_SUBBLOCKS (*t
);
572 while (BLOCK_CHAIN (*t
))
574 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
575 t
= &BLOCK_CHAIN (*t
);
577 BLOCK_CHAIN (*t
) = next
;
578 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
579 t
= &BLOCK_CHAIN (*t
);
583 *t
= BLOCK_CHAIN (*t
);
587 t
= &BLOCK_CHAIN (*t
);
594 /* Outer scope is always used. */
595 else if (!BLOCK_SUPERCONTEXT (scope
)
596 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
598 /* Innermost blocks with no live variables nor statements can be always
600 else if (!nsubblocks
)
602 /* For terse debug info we can eliminate info on unused variables. */
603 else if (debug_info_level
== DINFO_LEVEL_NONE
604 || debug_info_level
== DINFO_LEVEL_TERSE
)
606 /* Even for -g0/-g1 don't prune outer scopes from artificial
607 functions, otherwise diagnostics using tree_nonartificial_location
608 will not be emitted properly. */
609 if (inlined_function_outer_scope_p (scope
))
614 && TREE_CODE (ao
) == BLOCK
615 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
616 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
618 && TREE_CODE (ao
) == FUNCTION_DECL
619 && DECL_DECLARED_INLINE_P (ao
)
620 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
624 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
626 /* See if this block is important for representation of inlined function.
627 Inlined functions are always represented by block with
628 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
630 else if (inlined_function_outer_scope_p (scope
))
633 /* Verfify that only blocks with source location set
634 are entry points to the inlined functions. */
635 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
))
636 == UNKNOWN_LOCATION
);
638 TREE_USED (scope
) = !unused
;
642 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
643 eliminated during the tree->rtl conversion process. */
646 mark_all_vars_used (tree
*expr_p
)
648 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
651 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
654 clear_unused_block_pointer_1 (tree
*tp
, int *, void *)
656 if (EXPR_P (*tp
) && TREE_BLOCK (*tp
)
657 && !TREE_USED (TREE_BLOCK (*tp
)))
658 TREE_SET_BLOCK (*tp
, NULL
);
662 /* Set all block pointer in debug or clobber stmt to NULL if the block
663 is unused, so that they will not be streamed out. */
666 clear_unused_block_pointer (void)
669 gimple_stmt_iterator gsi
;
672 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
676 gimple stmt
= gsi_stmt (gsi
);
678 if (!is_gimple_debug (stmt
) && !gimple_clobber_p (stmt
))
680 b
= gimple_block (stmt
);
681 if (b
&& !TREE_USED (b
))
682 gimple_set_block (stmt
, NULL
);
683 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
684 walk_tree (gimple_op_ptr (stmt
, i
), clear_unused_block_pointer_1
,
689 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
690 indentation level and FLAGS is as in print_generic_expr. */
693 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
698 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
699 TREE_USED (scope
) ? "" : " (unused)",
700 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
701 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope
)) != UNKNOWN_LOCATION
)
703 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
704 fprintf (file
, " %s:%i", s
.file
, s
.line
);
706 if (BLOCK_ABSTRACT_ORIGIN (scope
))
708 tree origin
= block_ultimate_origin (scope
);
711 fprintf (file
, " Originating from :");
713 print_generic_decl (file
, origin
, flags
);
715 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
718 fprintf (file
, " \n");
719 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
721 fprintf (file
, "%*s", indent
, "");
722 print_generic_decl (file
, var
, flags
);
723 fprintf (file
, "\n");
725 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
727 fprintf (file
, "%*s",indent
, "");
728 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
730 fprintf (file
, " (nonlocalized)\n");
732 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
733 dump_scope_block (file
, indent
+ 2, t
, flags
);
734 fprintf (file
, "\n%*s}\n",indent
, "");
737 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
738 is as in print_generic_expr. */
741 debug_scope_block (tree scope
, int flags
)
743 dump_scope_block (stderr
, 0, scope
, flags
);
747 /* Dump the tree of lexical scopes of current_function_decl to FILE.
748 FLAGS is as in print_generic_expr. */
751 dump_scope_blocks (FILE *file
, int flags
)
753 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
757 /* Dump the tree of lexical scopes of current_function_decl to stderr.
758 FLAGS is as in print_generic_expr. */
761 debug_scope_blocks (int flags
)
763 dump_scope_blocks (stderr
, flags
);
766 /* Remove local variables that are not referenced in the IL. */
769 remove_unused_locals (void)
773 unsigned srcidx
, dstidx
, num
;
774 bool have_local_clobbers
= false;
776 /* Removing declarations from lexical blocks when not optimizing is
777 not only a waste of time, it actually causes differences in stack
782 timevar_push (TV_REMOVE_UNUSED
);
784 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
786 usedvars
= BITMAP_ALLOC (NULL
);
788 /* Walk the CFG marking all referenced symbols. */
791 gimple_stmt_iterator gsi
;
796 /* Walk the statements. */
797 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
799 gimple stmt
= gsi_stmt (gsi
);
800 tree b
= gimple_block (stmt
);
802 if (is_gimple_debug (stmt
))
805 if (gimple_clobber_p (stmt
))
807 have_local_clobbers
= true;
812 TREE_USED (b
) = true;
814 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
815 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
));
818 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
823 gimple phi
= gsi_stmt (gsi
);
825 if (virtual_operand_p (gimple_phi_result (phi
)))
828 def
= gimple_phi_result (phi
);
829 mark_all_vars_used (&def
);
831 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
833 tree arg
= USE_FROM_PTR (arg_p
);
834 int index
= PHI_ARG_INDEX_FROM_USE (arg_p
);
836 LOCATION_BLOCK (gimple_phi_arg_location (phi
, index
));
838 TREE_USED (block
) = true;
839 mark_all_vars_used (&arg
);
843 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
844 if (LOCATION_BLOCK (e
->goto_locus
) != NULL
)
845 TREE_USED (LOCATION_BLOCK (e
->goto_locus
)) = true;
848 /* We do a two-pass approach about the out-of-scope clobbers. We want
849 to remove them if they are the only references to a local variable,
850 but we want to retain them when there's any other. So the first pass
851 ignores them, and the second pass (if there were any) tries to remove
853 if (have_local_clobbers
)
856 gimple_stmt_iterator gsi
;
858 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
860 gimple stmt
= gsi_stmt (gsi
);
861 tree b
= gimple_block (stmt
);
863 if (gimple_clobber_p (stmt
))
865 tree lhs
= gimple_assign_lhs (stmt
);
866 tree base
= get_base_address (lhs
);
867 /* Remove clobbers referencing unused vars, or clobbers
868 with MEM_REF lhs referencing uninitialized pointers. */
869 if ((TREE_CODE (base
) == VAR_DECL
&& !is_used_p (base
))
870 || (TREE_CODE (lhs
) == MEM_REF
871 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
872 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs
, 0))
873 && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs
, 0)))
876 unlink_stmt_vdef (stmt
);
877 gsi_remove (&gsi
, true);
882 TREE_USED (b
) = true;
888 cfun
->has_local_explicit_reg_vars
= false;
890 /* Remove unmarked local and global vars from local_decls. */
891 num
= vec_safe_length (cfun
->local_decls
);
892 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
894 var
= (*cfun
->local_decls
)[srcidx
];
895 if (TREE_CODE (var
) == VAR_DECL
)
897 if (!is_used_p (var
))
900 if (cfun
->nonlocal_goto_save_area
901 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
902 cfun
->nonlocal_goto_save_area
= NULL
;
903 /* Release any default def associated with var. */
904 if ((def
= ssa_default_def (cfun
, var
)) != NULL_TREE
)
906 set_ssa_default_def (cfun
, var
, NULL_TREE
);
907 release_ssa_name (def
);
912 if (TREE_CODE (var
) == VAR_DECL
913 && DECL_HARD_REGISTER (var
)
914 && !is_global_var (var
))
915 cfun
->has_local_explicit_reg_vars
= true;
917 if (srcidx
!= dstidx
)
918 (*cfun
->local_decls
)[dstidx
] = var
;
923 statistics_counter_event (cfun
, "unused VAR_DECLs removed", num
- dstidx
);
924 cfun
->local_decls
->truncate (dstidx
);
927 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
));
928 clear_unused_block_pointer ();
930 BITMAP_FREE (usedvars
);
932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
934 fprintf (dump_file
, "Scope blocks after cleanups:\n");
935 dump_scope_blocks (dump_file
, dump_flags
);
938 timevar_pop (TV_REMOVE_UNUSED
);
941 /* Obstack for globale liveness info bitmaps. We don't want to put these
942 on the default obstack because these bitmaps can grow quite large and
943 we'll hold on to all that memory until the end of the compiler run.
944 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
945 releasing the whole obstack. */
946 static bitmap_obstack liveness_bitmap_obstack
;
948 /* Allocate and return a new live range information object base on MAP. */
950 static tree_live_info_p
951 new_tree_live_info (var_map map
)
953 tree_live_info_p live
;
956 live
= XNEW (struct tree_live_info_d
);
958 live
->num_blocks
= last_basic_block
;
960 live
->livein
= XNEWVEC (bitmap_head
, last_basic_block
);
962 bitmap_initialize (&live
->livein
[bb
->index
], &liveness_bitmap_obstack
);
964 live
->liveout
= XNEWVEC (bitmap_head
, last_basic_block
);
966 bitmap_initialize (&live
->liveout
[bb
->index
], &liveness_bitmap_obstack
);
968 live
->work_stack
= XNEWVEC (int, last_basic_block
);
969 live
->stack_top
= live
->work_stack
;
971 live
->global
= BITMAP_ALLOC (&liveness_bitmap_obstack
);
976 /* Free storage for live range info object LIVE. */
979 delete_tree_live_info (tree_live_info_p live
)
981 bitmap_obstack_release (&liveness_bitmap_obstack
);
982 free (live
->work_stack
);
983 free (live
->liveout
);
989 /* Visit basic block BB and propagate any required live on entry bits from
990 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
991 TMP is a temporary work bitmap which is passed in to avoid reallocating
995 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
1001 basic_block pred_bb
;
1004 gcc_checking_assert (!bitmap_bit_p (visited
, bb
->index
));
1005 bitmap_set_bit (visited
, bb
->index
);
1007 loe
= live_on_entry (live
, bb
);
1009 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1012 if (pred_bb
== ENTRY_BLOCK_PTR
)
1014 /* TMP is variables live-on-entry from BB that aren't defined in the
1015 predecessor block. This should be the live on entry vars to pred.
1016 Note that liveout is the DEFs in a block while live on entry is
1017 being calculated. */
1018 bitmap_and_compl (tmp
, loe
, &live
->liveout
[pred_bb
->index
]);
1020 /* Add these bits to live-on-entry for the pred. if there are any
1021 changes, and pred_bb has been visited already, add it to the
1023 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
1024 if (bitmap_bit_p (visited
, pred_bb
->index
) && change
)
1026 bitmap_clear_bit (visited
, pred_bb
->index
);
1027 *(live
->stack_top
)++ = pred_bb
->index
;
1033 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
1034 of all the variables. */
1037 live_worklist (tree_live_info_p live
)
1041 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
1042 bitmap tmp
= BITMAP_ALLOC (&liveness_bitmap_obstack
);
1044 bitmap_clear (visited
);
1046 /* Visit all the blocks in reverse order and propagate live on entry values
1047 into the predecessors blocks. */
1048 FOR_EACH_BB_REVERSE (bb
)
1049 loe_visit_block (live
, bb
, visited
, tmp
);
1051 /* Process any blocks which require further iteration. */
1052 while (live
->stack_top
!= live
->work_stack
)
1054 b
= *--(live
->stack_top
);
1055 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
1059 sbitmap_free (visited
);
1063 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1064 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1065 in the liveout vector. */
1068 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1073 basic_block def_bb
= NULL
;
1074 imm_use_iterator imm_iter
;
1075 bool global
= false;
1077 p
= var_to_partition (live
->map
, ssa_name
);
1078 if (p
== NO_PARTITION
)
1081 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1084 def_bb
= gimple_bb (stmt
);
1085 /* Mark defs in liveout bitmap temporarily. */
1087 bitmap_set_bit (&live
->liveout
[def_bb
->index
], p
);
1090 def_bb
= ENTRY_BLOCK_PTR
;
1092 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1093 add it to the list of live on entry blocks. */
1094 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1096 gimple use_stmt
= USE_STMT (use
);
1097 basic_block add_block
= NULL
;
1099 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1101 /* Uses in PHI's are considered to be live at exit of the SRC block
1102 as this is where a copy would be inserted. Check to see if it is
1103 defined in that block, or whether its live on entry. */
1104 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1105 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
1106 if (e
->src
!= ENTRY_BLOCK_PTR
)
1108 if (e
->src
!= def_bb
)
1112 else if (is_gimple_debug (use_stmt
))
1116 /* If its not defined in this block, its live on entry. */
1117 basic_block use_bb
= gimple_bb (use_stmt
);
1118 if (use_bb
!= def_bb
)
1122 /* If there was a live on entry use, set the bit. */
1126 bitmap_set_bit (&live
->livein
[add_block
->index
], p
);
1130 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1131 on entry blocks between the def and all the uses. */
1133 bitmap_set_bit (live
->global
, p
);
1137 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1140 calculate_live_on_exit (tree_live_info_p liveinfo
)
1146 /* live on entry calculations used liveout vectors for defs, clear them. */
1148 bitmap_clear (&liveinfo
->liveout
[bb
->index
]);
1150 /* Set all the live-on-exit bits for uses in PHIs. */
1153 gimple_stmt_iterator gsi
;
1156 /* Mark the PHI arguments which are live on exit to the pred block. */
1157 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1159 gimple phi
= gsi_stmt (gsi
);
1160 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1162 tree t
= PHI_ARG_DEF (phi
, i
);
1165 if (TREE_CODE (t
) != SSA_NAME
)
1168 p
= var_to_partition (liveinfo
->map
, t
);
1169 if (p
== NO_PARTITION
)
1171 e
= gimple_phi_arg_edge (phi
, i
);
1172 if (e
->src
!= ENTRY_BLOCK_PTR
)
1173 bitmap_set_bit (&liveinfo
->liveout
[e
->src
->index
], p
);
1177 /* Add each successors live on entry to this bock live on exit. */
1178 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1179 if (e
->dest
!= EXIT_BLOCK_PTR
)
1180 bitmap_ior_into (&liveinfo
->liveout
[bb
->index
],
1181 live_on_entry (liveinfo
, e
->dest
));
1186 /* Given partition map MAP, calculate all the live on entry bitmaps for
1187 each partition. Return a new live info object. */
1190 calculate_live_ranges (var_map map
)
1194 tree_live_info_p live
;
1196 bitmap_obstack_initialize (&liveness_bitmap_obstack
);
1197 live
= new_tree_live_info (map
);
1198 for (i
= 0; i
< num_var_partitions (map
); i
++)
1200 var
= partition_to_var (map
, i
);
1201 if (var
!= NULL_TREE
)
1202 set_var_live_on_entry (var
, live
);
1205 live_worklist (live
);
1207 #ifdef ENABLE_CHECKING
1208 verify_live_on_entry (live
);
1211 calculate_live_on_exit (live
);
1216 /* Output partition map MAP to file F. */
1219 dump_var_map (FILE *f
, var_map map
)
1225 fprintf (f
, "\nPartition map \n\n");
1227 for (x
= 0; x
< map
->num_partitions
; x
++)
1229 if (map
->view_to_partition
!= NULL
)
1230 p
= map
->view_to_partition
[x
];
1234 if (ssa_name (p
) == NULL_TREE
1235 || virtual_operand_p (ssa_name (p
)))
1239 for (y
= 1; y
< num_ssa_names
; y
++)
1241 p
= partition_find (map
->var_partition
, y
);
1242 if (map
->partition_to_view
)
1243 p
= map
->partition_to_view
[p
];
1248 fprintf (f
, "Partition %d (", x
);
1249 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1252 fprintf (f
, "%d ", y
);
1262 /* Generic dump for the above. */
1265 debug (_var_map
&ref
)
1267 dump_var_map (stderr
, &ref
);
1271 debug (_var_map
*ptr
)
1276 fprintf (stderr
, "<nil>\n");
1280 /* Output live range info LIVE to file F, controlled by FLAG. */
1283 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1287 var_map map
= live
->map
;
1290 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1294 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1295 EXECUTE_IF_SET_IN_BITMAP (&live
->livein
[bb
->index
], 0, i
, bi
)
1297 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1304 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1308 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1309 EXECUTE_IF_SET_IN_BITMAP (&live
->liveout
[bb
->index
], 0, i
, bi
)
1311 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1320 /* Generic dump for the above. */
1323 debug (tree_live_info_d
&ref
)
1325 dump_live_info (stderr
, &ref
, 0);
1329 debug (tree_live_info_d
*ptr
)
1334 fprintf (stderr
, "<nil>\n");
1338 #ifdef ENABLE_CHECKING
1339 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1342 register_ssa_partition_check (tree ssa_var
)
1344 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1345 if (virtual_operand_p (ssa_var
))
1347 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1348 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1349 fprintf (stderr
, " in the SSA->Normal phase.\n");
1350 internal_error ("SSA corruption");
1355 /* Verify that the info in LIVE matches the current cfg. */
1358 verify_live_on_entry (tree_live_info_p live
)
1367 var_map map
= live
->map
;
1369 /* Check for live on entry partitions and report those with a DEF in
1370 the program. This will typically mean an optimization has done
1372 bb
= ENTRY_BLOCK_PTR
;
1374 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1376 int entry_block
= e
->dest
->index
;
1377 if (e
->dest
== EXIT_BLOCK_PTR
)
1379 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1384 var
= partition_to_var (map
, i
);
1385 stmt
= SSA_NAME_DEF_STMT (var
);
1386 tmp
= gimple_bb (stmt
);
1387 if (SSA_NAME_VAR (var
))
1388 d
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1390 loe
= live_on_entry (live
, e
->dest
);
1391 if (loe
&& bitmap_bit_p (loe
, i
))
1393 if (!gimple_nop_p (stmt
))
1396 print_generic_expr (stderr
, var
, TDF_SLIM
);
1397 fprintf (stderr
, " is defined ");
1399 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1400 fprintf (stderr
, "by:\n");
1401 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1402 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1404 fprintf (stderr
, " So it appears to have multiple defs.\n");
1411 print_generic_expr (stderr
, var
, TDF_SLIM
);
1412 fprintf (stderr
, " is live-on-entry to BB%d ",
1416 fprintf (stderr
, " but is not the default def of ");
1417 print_generic_expr (stderr
, d
, TDF_SLIM
);
1418 fprintf (stderr
, "\n");
1421 fprintf (stderr
, " and there is no default def.\n");
1428 /* The only way this var shouldn't be marked live on entry is
1429 if it occurs in a PHI argument of the block. */
1432 gimple_stmt_iterator gsi
;
1433 for (gsi
= gsi_start_phis (e
->dest
);
1434 !gsi_end_p (gsi
) && !ok
;
1437 gimple phi
= gsi_stmt (gsi
);
1438 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1439 if (var
== gimple_phi_arg_def (phi
, z
))
1448 print_generic_expr (stderr
, var
, TDF_SLIM
);
1449 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1451 fprintf (stderr
, "but it is a default def so it should be.\n");
1455 gcc_assert (num
<= 0);