1 /* Liveness for SSA trees.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Andrew MacLeod <amacleod@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
27 #include "gimple-pretty-print.h"
29 #include "tree-flow.h"
32 #include "tree-ssa-live.h"
33 #include "diagnostic-core.h"
38 #ifdef ENABLE_CHECKING
39 static void verify_live_on_entry (tree_live_info_p
);
43 /* VARMAP maintains a mapping from SSA version number to real variables.
45 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
46 only member of it's own partition. Coalescing will attempt to group any
47 ssa_names which occur in a copy or in a PHI node into the same partition.
49 At the end of out-of-ssa, each partition becomes a "real" variable and is
50 rewritten as a compiler variable.
52 The var_map data structure is used to manage these partitions. It allows
53 partitions to be combined, and determines which partition belongs to what
54 ssa_name or variable, and vice versa. */
57 /* This routine will initialize the basevar fields of MAP. */
60 var_map_base_init (var_map map
)
65 struct tree_int_map
*m
, *mapstorage
;
67 num_part
= num_var_partitions (map
);
68 decl_to_index
= htab_create (num_part
, tree_decl_map_hash
,
69 tree_int_map_eq
, NULL
);
70 /* We can have at most num_part entries in the hash tables, so it's
71 enough to allocate so many map elements once, saving some malloc
73 mapstorage
= m
= XNEWVEC (struct tree_int_map
, num_part
);
75 /* If a base table already exists, clear it, otherwise create it. */
76 free (map
->partition_to_base_index
);
77 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
79 /* Build the base variable list, and point partitions at their bases. */
80 for (x
= 0; x
< num_part
; x
++)
82 struct tree_int_map
**slot
;
84 var
= partition_to_var (map
, x
);
85 var
= SSA_NAME_VAR (var
);
86 /* If base variable hasn't been seen, set it up. */
88 slot
= (struct tree_int_map
**) htab_find_slot (decl_to_index
, m
, INSERT
);
91 baseindex
= m
- mapstorage
;
97 baseindex
= (*slot
)->to
;
98 map
->partition_to_base_index
[x
] = baseindex
;
101 map
->num_basevars
= m
- mapstorage
;
104 htab_delete (decl_to_index
);
108 /* Remove the base table in MAP. */
111 var_map_base_fini (var_map map
)
113 /* Free the basevar info if it is present. */
114 if (map
->partition_to_base_index
!= NULL
)
116 free (map
->partition_to_base_index
);
117 map
->partition_to_base_index
= NULL
;
118 map
->num_basevars
= 0;
121 /* Create a variable partition map of SIZE, initialize and return it. */
124 init_var_map (int size
)
128 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
129 map
->var_partition
= partition_new (size
);
131 map
->partition_to_view
= NULL
;
132 map
->view_to_partition
= NULL
;
133 map
->num_partitions
= size
;
134 map
->partition_size
= size
;
135 map
->num_basevars
= 0;
136 map
->partition_to_base_index
= NULL
;
141 /* Free memory associated with MAP. */
144 delete_var_map (var_map map
)
146 var_map_base_fini (map
);
147 partition_delete (map
->var_partition
);
148 free (map
->partition_to_view
);
149 free (map
->view_to_partition
);
154 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
155 Returns the partition which represents the new partition. If the two
156 partitions cannot be combined, NO_PARTITION is returned. */
159 var_union (var_map map
, tree var1
, tree var2
)
163 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
164 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
166 /* This is independent of partition_to_view. If partition_to_view is
167 on, then whichever one of these partitions is absorbed will never have a
168 dereference into the partition_to_view array any more. */
170 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
171 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
173 gcc_assert (p1
!= NO_PARTITION
);
174 gcc_assert (p2
!= NO_PARTITION
);
179 p3
= partition_union (map
->var_partition
, p1
, p2
);
181 if (map
->partition_to_view
)
182 p3
= map
->partition_to_view
[p3
];
188 /* Compress the partition numbers in MAP such that they fall in the range
189 0..(num_partitions-1) instead of wherever they turned out during
190 the partitioning exercise. This removes any references to unused
191 partitions, thereby allowing bitmaps and other vectors to be much
194 This is implemented such that compaction doesn't affect partitioning.
195 Ie., once partitions are created and possibly merged, running one
196 or more different kind of compaction will not affect the partitions
197 themselves. Their index might change, but all the same variables will
198 still be members of the same partition group. This allows work on reduced
199 sets, and no loss of information when a larger set is later desired.
201 In particular, coalescing can work on partitions which have 2 or more
202 definitions, and then 'recompact' later to include all the single
203 definitions for assignment to program variables. */
206 /* Set MAP back to the initial state of having no partition view. Return a
207 bitmap which has a bit set for each partition number which is in use in the
211 partition_view_init (var_map map
)
217 used
= BITMAP_ALLOC (NULL
);
219 /* Already in a view? Abandon the old one. */
220 if (map
->partition_to_view
)
222 free (map
->partition_to_view
);
223 map
->partition_to_view
= NULL
;
225 if (map
->view_to_partition
)
227 free (map
->view_to_partition
);
228 map
->view_to_partition
= NULL
;
231 /* Find out which partitions are actually referenced. */
232 for (x
= 0; x
< map
->partition_size
; x
++)
234 tmp
= partition_find (map
->var_partition
, x
);
235 if (ssa_name (tmp
) != NULL_TREE
&& is_gimple_reg (ssa_name (tmp
))
236 && (!has_zero_uses (ssa_name (tmp
))
237 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
238 bitmap_set_bit (used
, tmp
);
241 map
->num_partitions
= map
->partition_size
;
246 /* This routine will finalize the view data for MAP based on the partitions
247 set in SELECTED. This is either the same bitmap returned from
248 partition_view_init, or a trimmed down version if some of those partitions
249 were not desired in this view. SELECTED is freed before returning. */
252 partition_view_fini (var_map map
, bitmap selected
)
255 unsigned count
, i
, x
, limit
;
257 gcc_assert (selected
);
259 count
= bitmap_count_bits (selected
);
260 limit
= map
->partition_size
;
262 /* If its a one-to-one ratio, we don't need any view compaction. */
265 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
266 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
267 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
270 /* Give each selected partition an index. */
271 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
273 map
->partition_to_view
[x
] = i
;
274 map
->view_to_partition
[i
] = x
;
277 gcc_assert (i
== count
);
278 map
->num_partitions
= i
;
281 BITMAP_FREE (selected
);
285 /* Create a partition view which includes all the used partitions in MAP. If
286 WANT_BASES is true, create the base variable map as well. */
289 partition_view_normal (var_map map
, bool want_bases
)
293 used
= partition_view_init (map
);
294 partition_view_fini (map
, used
);
297 var_map_base_init (map
);
299 var_map_base_fini (map
);
303 /* Create a partition view in MAP which includes just partitions which occur in
304 the bitmap ONLY. If WANT_BASES is true, create the base variable map
308 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
311 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
315 used
= partition_view_init (map
);
316 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
318 p
= partition_find (map
->var_partition
, x
);
319 gcc_assert (bitmap_bit_p (used
, p
));
320 bitmap_set_bit (new_partitions
, p
);
322 partition_view_fini (map
, new_partitions
);
326 var_map_base_init (map
);
328 var_map_base_fini (map
);
332 static bitmap usedvars
;
334 /* Mark VAR as used, so that it'll be preserved during rtl expansion. */
337 set_is_used (tree var
)
339 bitmap_set_bit (usedvars
, DECL_UID (var
));
342 /* Return true if VAR is marked as used. */
347 return bitmap_bit_p (usedvars
, DECL_UID (var
));
350 static inline void mark_all_vars_used (tree
*, void *data
);
352 /* Helper function for mark_all_vars_used, called via walk_tree. */
355 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data
)
357 bitmap global_unused_vars
= (bitmap
)data
;
359 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
362 if (TREE_CODE (t
) == SSA_NAME
)
363 t
= SSA_NAME_VAR (t
);
365 if (IS_EXPR_CODE_CLASS (c
)
366 && (b
= TREE_BLOCK (t
)) != NULL
)
367 TREE_USED (b
) = true;
369 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
370 fields do not contain vars. */
371 if (TREE_CODE (t
) == TARGET_MEM_REF
)
373 mark_all_vars_used (&TMR_BASE (t
), data
);
374 mark_all_vars_used (&TMR_INDEX (t
), data
);
375 mark_all_vars_used (&TMR_INDEX2 (t
), data
);
380 /* Only need to mark VAR_DECLS; parameters and return results are not
381 eliminated as unused. */
382 if (TREE_CODE (t
) == VAR_DECL
)
384 /* Global vars do not have a var-annotation so their use is tracked
385 with the global_unused_vars bitmap. Also walk their initializer
386 when they are first recognized as used. */
387 if (is_global_var (t
))
389 if (bitmap_clear_bit (global_unused_vars
, DECL_UID (t
)))
390 mark_all_vars_used (&DECL_INITIAL (t
), data
);
395 /* remove_unused_scope_block_p requires information about labels
396 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
397 else if (TREE_CODE (t
) == LABEL_DECL
)
398 /* Although the TREE_USED values that the frontend uses would be
399 acceptable (albeit slightly over-conservative) for our purposes,
400 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
401 must re-compute it here. */
404 if (IS_TYPE_OR_DECL_P (t
))
410 /* Mark the scope block SCOPE and its subblocks unused when they can be
411 possibly eliminated if dead. */
414 mark_scope_block_unused (tree scope
)
417 TREE_USED (scope
) = false;
418 if (!(*debug_hooks
->ignore_block
) (scope
))
419 TREE_USED (scope
) = true;
420 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
421 mark_scope_block_unused (t
);
424 /* Look if the block is dead (by possibly eliminating its dead subblocks)
425 and return true if so.
426 Block is declared dead if:
427 1) No statements are associated with it.
428 2) Declares no live variables
429 3) All subblocks are dead
430 or there is precisely one subblocks and the block
431 has same abstract origin as outer block and declares
432 no variables, so it is pure wrapper.
433 When we are not outputting full debug info, we also eliminate dead variables
434 out of scope blocks to let them to be recycled by GGC and to save copying work
435 done by the inliner. */
438 remove_unused_scope_block_p (tree scope
, bitmap global_unused_vars
)
441 bool unused
= !TREE_USED (scope
);
444 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
446 next
= &DECL_CHAIN (*t
);
448 /* Debug info of nested function refers to the block of the
449 function. We might stil call it even if all statements
450 of function it was nested into was elliminated.
452 TODO: We can actually look into cgraph to see if function
453 will be output to file. */
454 if (TREE_CODE (*t
) == FUNCTION_DECL
)
457 /* If a decl has a value expr, we need to instantiate it
458 regardless of debug info generation, to avoid codegen
459 differences in memory overlap tests. update_equiv_regs() may
460 indirectly call validate_equiv_mem() to test whether a
461 SET_DEST overlaps with others, and if the value expr changes
462 by virtual register instantiation, we may get end up with
463 different results. */
464 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
467 /* Remove everything we don't generate debug info for. */
468 else if (DECL_IGNORED_P (*t
))
470 *t
= DECL_CHAIN (*t
);
474 /* When we are outputting debug info, we usually want to output
475 info about optimized-out variables in the scope blocks.
476 Exception are the scope blocks not containing any instructions
477 at all so user can't get into the scopes at first place. */
478 else if ((is_global_var (*t
)
479 && !bitmap_bit_p (global_unused_vars
, DECL_UID (*t
)))
482 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
483 /* For labels that are still used in the IL, the decision to
484 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
485 risk having different ordering in debug vs. non-debug builds
486 during inlining or versioning.
487 A label appearing here (we have already checked DECL_IGNORED_P)
488 should not be used in the IL unless it has been explicitly used
489 before, so we use TREE_USED as an approximation. */
490 /* In principle, we should do the same here as for the debug case
491 below, however, when debugging, there might be additional nested
492 levels that keep an upper level with a label live, so we have to
493 force this block to be considered used, too. */
496 /* When we are not doing full debug info, we however can keep around
497 only the used variables for cfgexpand's memory packing saving quite
500 For sake of -g3, we keep around those vars but we don't count this as
501 use of block, so innermost block with no used vars and no instructions
502 can be considered dead. We only want to keep around blocks user can
503 breakpoint into and ask about value of optimized out variables.
505 Similarly we need to keep around types at least until all
506 variables of all nested blocks are gone. We track no
507 information on whether given type is used or not, so we have
508 to keep them even when not emitting debug information,
509 otherwise we may end up remapping variables and their (local)
510 types in different orders depending on whether debug
511 information is being generated. */
513 else if (TREE_CODE (*t
) == TYPE_DECL
514 || debug_info_level
== DINFO_LEVEL_NORMAL
515 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
519 *t
= DECL_CHAIN (*t
);
524 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
525 if (remove_unused_scope_block_p (*t
, global_unused_vars
))
527 if (BLOCK_SUBBLOCKS (*t
))
529 tree next
= BLOCK_CHAIN (*t
);
530 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
532 *t
= BLOCK_SUBBLOCKS (*t
);
533 while (BLOCK_CHAIN (*t
))
535 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
536 t
= &BLOCK_CHAIN (*t
);
538 BLOCK_CHAIN (*t
) = next
;
539 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
540 t
= &BLOCK_CHAIN (*t
);
544 *t
= BLOCK_CHAIN (*t
);
548 t
= &BLOCK_CHAIN (*t
);
555 /* Outer scope is always used. */
556 else if (!BLOCK_SUPERCONTEXT (scope
)
557 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
559 /* Innermost blocks with no live variables nor statements can be always
561 else if (!nsubblocks
)
563 /* For terse debug info we can eliminate info on unused variables. */
564 else if (debug_info_level
== DINFO_LEVEL_NONE
565 || debug_info_level
== DINFO_LEVEL_TERSE
)
567 /* Even for -g0/-g1 don't prune outer scopes from artificial
568 functions, otherwise diagnostics using tree_nonartificial_location
569 will not be emitted properly. */
570 if (inlined_function_outer_scope_p (scope
))
575 && TREE_CODE (ao
) == BLOCK
576 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
577 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
579 && TREE_CODE (ao
) == FUNCTION_DECL
580 && DECL_DECLARED_INLINE_P (ao
)
581 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
585 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
587 /* See if this block is important for representation of inlined function.
588 Inlined functions are always represented by block with
589 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
591 else if (inlined_function_outer_scope_p (scope
))
594 /* Verfify that only blocks with source location set
595 are entry points to the inlined functions. */
596 gcc_assert (BLOCK_SOURCE_LOCATION (scope
) == UNKNOWN_LOCATION
);
598 TREE_USED (scope
) = !unused
;
602 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
603 eliminated during the tree->rtl conversion process. */
606 mark_all_vars_used (tree
*expr_p
, void *data
)
608 walk_tree (expr_p
, mark_all_vars_used_1
, data
, NULL
);
612 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
613 indentation level and FLAGS is as in print_generic_expr. */
616 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
621 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
622 TREE_USED (scope
) ? "" : " (unused)",
623 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
624 if (BLOCK_SOURCE_LOCATION (scope
) != UNKNOWN_LOCATION
)
626 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
627 fprintf (file
, " %s:%i", s
.file
, s
.line
);
629 if (BLOCK_ABSTRACT_ORIGIN (scope
))
631 tree origin
= block_ultimate_origin (scope
);
634 fprintf (file
, " Originating from :");
636 print_generic_decl (file
, origin
, flags
);
638 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
641 fprintf (file
, " \n");
642 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
644 fprintf (file
, "%*s", indent
, "");
645 print_generic_decl (file
, var
, flags
);
646 fprintf (file
, "\n");
648 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
650 fprintf (file
, "%*s",indent
, "");
651 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
653 fprintf (file
, " (nonlocalized)\n");
655 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
656 dump_scope_block (file
, indent
+ 2, t
, flags
);
657 fprintf (file
, "\n%*s}\n",indent
, "");
660 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
661 is as in print_generic_expr. */
664 debug_scope_block (tree scope
, int flags
)
666 dump_scope_block (stderr
, 0, scope
, flags
);
670 /* Dump the tree of lexical scopes of current_function_decl to FILE.
671 FLAGS is as in print_generic_expr. */
674 dump_scope_blocks (FILE *file
, int flags
)
676 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
680 /* Dump the tree of lexical scopes of current_function_decl to stderr.
681 FLAGS is as in print_generic_expr. */
684 debug_scope_blocks (int flags
)
686 dump_scope_blocks (stderr
, flags
);
689 /* Remove local variables that are not referenced in the IL. */
692 remove_unused_locals (void)
696 bitmap global_unused_vars
= NULL
;
697 unsigned srcidx
, dstidx
, num
, ix
;
698 bool have_local_clobbers
= false;
700 /* Removing declarations from lexical blocks when not optimizing is
701 not only a waste of time, it actually causes differences in stack
706 timevar_push (TV_REMOVE_UNUSED
);
708 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
710 usedvars
= BITMAP_ALLOC (NULL
);
712 /* Assume all globals in local decls are unused. */
713 global_unused_vars
= BITMAP_ALLOC (NULL
);
714 FOR_EACH_LOCAL_DECL (cfun
, ix
, var
)
715 if (TREE_CODE (var
) == VAR_DECL
716 && is_global_var (var
))
717 bitmap_set_bit (global_unused_vars
, DECL_UID (var
));
719 /* Walk the CFG marking all referenced symbols. */
722 gimple_stmt_iterator gsi
;
727 /* Walk the statements. */
728 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
730 gimple stmt
= gsi_stmt (gsi
);
731 tree b
= gimple_block (stmt
);
733 if (is_gimple_debug (stmt
))
736 if (gimple_clobber_p (stmt
))
738 have_local_clobbers
= true;
743 TREE_USED (b
) = true;
745 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
746 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
),
750 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
755 gimple phi
= gsi_stmt (gsi
);
757 if (!is_gimple_reg (gimple_phi_result (phi
)))
760 def
= gimple_phi_result (phi
);
761 mark_all_vars_used (&def
, global_unused_vars
);
763 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
765 tree arg
= USE_FROM_PTR (arg_p
);
766 mark_all_vars_used (&arg
, global_unused_vars
);
770 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
772 TREE_USED (e
->goto_block
) = true;
775 /* We do a two-pass approach about the out-of-scope clobbers. We want
776 to remove them if they are the only references to a local variable,
777 but we want to retain them when there's any other. So the first pass
778 ignores them, and the second pass (if there were any) tries to remove
780 if (have_local_clobbers
)
783 gimple_stmt_iterator gsi
;
785 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
787 gimple stmt
= gsi_stmt (gsi
);
788 tree b
= gimple_block (stmt
);
790 if (gimple_clobber_p (stmt
))
792 tree lhs
= gimple_assign_lhs (stmt
);
793 lhs
= get_base_address (lhs
);
794 if (TREE_CODE (lhs
) == SSA_NAME
)
795 lhs
= SSA_NAME_VAR (lhs
);
796 if (TREE_CODE (lhs
) == VAR_DECL
797 && ((is_global_var (lhs
)
798 && bitmap_bit_p (global_unused_vars
, DECL_UID (lhs
)))
799 || (!is_global_var (lhs
) && !is_used_p (lhs
))))
801 unlink_stmt_vdef (stmt
);
802 gsi_remove (&gsi
, true);
807 TREE_USED (b
) = true;
813 cfun
->has_local_explicit_reg_vars
= false;
815 /* Remove unmarked local and global vars from local_decls
816 and referenced vars. */
817 num
= VEC_length (tree
, cfun
->local_decls
);
818 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
820 var
= VEC_index (tree
, cfun
->local_decls
, srcidx
);
821 if (TREE_CODE (var
) == VAR_DECL
)
823 if (is_global_var (var
))
825 if (bitmap_bit_p (global_unused_vars
, DECL_UID (var
)))
828 else if (!is_used_p (var
))
830 if (cfun
->nonlocal_goto_save_area
831 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
832 cfun
->nonlocal_goto_save_area
= NULL
;
836 if (TREE_CODE (var
) == VAR_DECL
837 && DECL_HARD_REGISTER (var
)
838 && !is_global_var (var
))
839 cfun
->has_local_explicit_reg_vars
= true;
841 if (srcidx
!= dstidx
)
842 VEC_replace (tree
, cfun
->local_decls
, dstidx
, var
);
846 VEC_truncate (tree
, cfun
->local_decls
, dstidx
);
848 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
),
851 BITMAP_FREE (global_unused_vars
);
852 BITMAP_FREE (usedvars
);
854 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
856 fprintf (dump_file
, "Scope blocks after cleanups:\n");
857 dump_scope_blocks (dump_file
, dump_flags
);
860 timevar_pop (TV_REMOVE_UNUSED
);
864 /* Allocate and return a new live range information object base on MAP. */
866 static tree_live_info_p
867 new_tree_live_info (var_map map
)
869 tree_live_info_p live
;
872 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
874 live
->num_blocks
= last_basic_block
;
876 live
->livein
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
877 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
878 live
->livein
[x
] = BITMAP_ALLOC (NULL
);
880 live
->liveout
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
881 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
882 live
->liveout
[x
] = BITMAP_ALLOC (NULL
);
884 live
->work_stack
= XNEWVEC (int, last_basic_block
);
885 live
->stack_top
= live
->work_stack
;
887 live
->global
= BITMAP_ALLOC (NULL
);
892 /* Free storage for live range info object LIVE. */
895 delete_tree_live_info (tree_live_info_p live
)
899 BITMAP_FREE (live
->global
);
900 free (live
->work_stack
);
902 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
903 BITMAP_FREE (live
->liveout
[x
]);
904 free (live
->liveout
);
906 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
907 BITMAP_FREE (live
->livein
[x
]);
914 /* Visit basic block BB and propagate any required live on entry bits from
915 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
916 TMP is a temporary work bitmap which is passed in to avoid reallocating
920 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
928 gcc_assert (!TEST_BIT (visited
, bb
->index
));
930 SET_BIT (visited
, bb
->index
);
931 loe
= live_on_entry (live
, bb
);
933 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
936 if (pred_bb
== ENTRY_BLOCK_PTR
)
938 /* TMP is variables live-on-entry from BB that aren't defined in the
939 predecessor block. This should be the live on entry vars to pred.
940 Note that liveout is the DEFs in a block while live on entry is
942 bitmap_and_compl (tmp
, loe
, live
->liveout
[pred_bb
->index
]);
944 /* Add these bits to live-on-entry for the pred. if there are any
945 changes, and pred_bb has been visited already, add it to the
947 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
948 if (TEST_BIT (visited
, pred_bb
->index
) && change
)
950 RESET_BIT (visited
, pred_bb
->index
);
951 *(live
->stack_top
)++ = pred_bb
->index
;
957 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
958 of all the variables. */
961 live_worklist (tree_live_info_p live
)
965 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
966 bitmap tmp
= BITMAP_ALLOC (NULL
);
968 sbitmap_zero (visited
);
970 /* Visit all the blocks in reverse order and propagate live on entry values
971 into the predecessors blocks. */
972 FOR_EACH_BB_REVERSE (bb
)
973 loe_visit_block (live
, bb
, visited
, tmp
);
975 /* Process any blocks which require further iteration. */
976 while (live
->stack_top
!= live
->work_stack
)
978 b
= *--(live
->stack_top
);
979 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
983 sbitmap_free (visited
);
987 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
988 links. Set the live on entry fields in LIVE. Def's are marked temporarily
989 in the liveout vector. */
992 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
997 basic_block def_bb
= NULL
;
998 imm_use_iterator imm_iter
;
1001 p
= var_to_partition (live
->map
, ssa_name
);
1002 if (p
== NO_PARTITION
)
1005 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1008 def_bb
= gimple_bb (stmt
);
1009 /* Mark defs in liveout bitmap temporarily. */
1011 bitmap_set_bit (live
->liveout
[def_bb
->index
], p
);
1014 def_bb
= ENTRY_BLOCK_PTR
;
1016 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1017 add it to the list of live on entry blocks. */
1018 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1020 gimple use_stmt
= USE_STMT (use
);
1021 basic_block add_block
= NULL
;
1023 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1025 /* Uses in PHI's are considered to be live at exit of the SRC block
1026 as this is where a copy would be inserted. Check to see if it is
1027 defined in that block, or whether its live on entry. */
1028 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1029 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
1030 if (e
->src
!= ENTRY_BLOCK_PTR
)
1032 if (e
->src
!= def_bb
)
1036 else if (is_gimple_debug (use_stmt
))
1040 /* If its not defined in this block, its live on entry. */
1041 basic_block use_bb
= gimple_bb (use_stmt
);
1042 if (use_bb
!= def_bb
)
1046 /* If there was a live on entry use, set the bit. */
1050 bitmap_set_bit (live
->livein
[add_block
->index
], p
);
1054 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1055 on entry blocks between the def and all the uses. */
1057 bitmap_set_bit (live
->global
, p
);
1061 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1064 calculate_live_on_exit (tree_live_info_p liveinfo
)
1070 /* live on entry calculations used liveout vectors for defs, clear them. */
1072 bitmap_clear (liveinfo
->liveout
[bb
->index
]);
1074 /* Set all the live-on-exit bits for uses in PHIs. */
1077 gimple_stmt_iterator gsi
;
1080 /* Mark the PHI arguments which are live on exit to the pred block. */
1081 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1083 gimple phi
= gsi_stmt (gsi
);
1084 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1086 tree t
= PHI_ARG_DEF (phi
, i
);
1089 if (TREE_CODE (t
) != SSA_NAME
)
1092 p
= var_to_partition (liveinfo
->map
, t
);
1093 if (p
== NO_PARTITION
)
1095 e
= gimple_phi_arg_edge (phi
, i
);
1096 if (e
->src
!= ENTRY_BLOCK_PTR
)
1097 bitmap_set_bit (liveinfo
->liveout
[e
->src
->index
], p
);
1101 /* Add each successors live on entry to this bock live on exit. */
1102 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1103 if (e
->dest
!= EXIT_BLOCK_PTR
)
1104 bitmap_ior_into (liveinfo
->liveout
[bb
->index
],
1105 live_on_entry (liveinfo
, e
->dest
));
1110 /* Given partition map MAP, calculate all the live on entry bitmaps for
1111 each partition. Return a new live info object. */
1114 calculate_live_ranges (var_map map
)
1118 tree_live_info_p live
;
1120 live
= new_tree_live_info (map
);
1121 for (i
= 0; i
< num_var_partitions (map
); i
++)
1123 var
= partition_to_var (map
, i
);
1124 if (var
!= NULL_TREE
)
1125 set_var_live_on_entry (var
, live
);
1128 live_worklist (live
);
1130 #ifdef ENABLE_CHECKING
1131 verify_live_on_entry (live
);
1134 calculate_live_on_exit (live
);
1139 /* Output partition map MAP to file F. */
1142 dump_var_map (FILE *f
, var_map map
)
1148 fprintf (f
, "\nPartition map \n\n");
1150 for (x
= 0; x
< map
->num_partitions
; x
++)
1152 if (map
->view_to_partition
!= NULL
)
1153 p
= map
->view_to_partition
[x
];
1157 if (ssa_name (p
) == NULL_TREE
)
1161 for (y
= 1; y
< num_ssa_names
; y
++)
1163 p
= partition_find (map
->var_partition
, y
);
1164 if (map
->partition_to_view
)
1165 p
= map
->partition_to_view
[p
];
1170 fprintf(f
, "Partition %d (", x
);
1171 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1174 fprintf (f
, "%d ", y
);
1184 /* Output live range info LIVE to file F, controlled by FLAG. */
1187 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1191 var_map map
= live
->map
;
1194 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1198 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1199 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[bb
->index
], 0, i
, bi
)
1201 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1208 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1212 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1213 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
, bi
)
1215 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1223 #ifdef ENABLE_CHECKING
1224 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1227 register_ssa_partition_check (tree ssa_var
)
1229 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1230 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
1232 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1233 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1234 fprintf (stderr
, " in the SSA->Normal phase.\n");
1235 internal_error ("SSA corruption");
1240 /* Verify that the info in LIVE matches the current cfg. */
1243 verify_live_on_entry (tree_live_info_p live
)
1252 var_map map
= live
->map
;
1254 /* Check for live on entry partitions and report those with a DEF in
1255 the program. This will typically mean an optimization has done
1257 bb
= ENTRY_BLOCK_PTR
;
1259 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1261 int entry_block
= e
->dest
->index
;
1262 if (e
->dest
== EXIT_BLOCK_PTR
)
1264 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1269 var
= partition_to_var (map
, i
);
1270 stmt
= SSA_NAME_DEF_STMT (var
);
1271 tmp
= gimple_bb (stmt
);
1272 d
= gimple_default_def (cfun
, SSA_NAME_VAR (var
));
1274 loe
= live_on_entry (live
, e
->dest
);
1275 if (loe
&& bitmap_bit_p (loe
, i
))
1277 if (!gimple_nop_p (stmt
))
1280 print_generic_expr (stderr
, var
, TDF_SLIM
);
1281 fprintf (stderr
, " is defined ");
1283 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1284 fprintf (stderr
, "by:\n");
1285 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1286 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1288 fprintf (stderr
, " So it appears to have multiple defs.\n");
1295 print_generic_expr (stderr
, var
, TDF_SLIM
);
1296 fprintf (stderr
, " is live-on-entry to BB%d ",
1300 fprintf (stderr
, " but is not the default def of ");
1301 print_generic_expr (stderr
, d
, TDF_SLIM
);
1302 fprintf (stderr
, "\n");
1305 fprintf (stderr
, " and there is no default def.\n");
1312 /* The only way this var shouldn't be marked live on entry is
1313 if it occurs in a PHI argument of the block. */
1316 gimple_stmt_iterator gsi
;
1317 for (gsi
= gsi_start_phis (e
->dest
);
1318 !gsi_end_p (gsi
) && !ok
;
1321 gimple phi
= gsi_stmt (gsi
);
1322 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1323 if (var
== gimple_phi_arg_def (phi
, z
))
1332 print_generic_expr (stderr
, var
, TDF_SLIM
);
1333 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1335 fprintf (stderr
, "but it is a default def so it should be.\n");
1339 gcc_assert (num
<= 0);