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 "tree-pretty-print.h"
28 #include "gimple-pretty-print.h"
30 #include "tree-flow.h"
31 #include "tree-dump.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
)
67 num_part
= num_var_partitions (map
);
69 /* If a base table already exists, clear it, otherwise create it. */
70 if (map
->partition_to_base_index
!= NULL
)
72 free (map
->partition_to_base_index
);
73 VEC_truncate (tree
, map
->basevars
, 0);
76 map
->basevars
= VEC_alloc (tree
, heap
, MAX (40, (num_part
/ 10)));
78 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
80 /* Build the base variable list, and point partitions at their bases. */
81 for (x
= 0; x
< num_part
; x
++)
83 var
= partition_to_var (map
, x
);
84 if (TREE_CODE (var
) == SSA_NAME
)
85 var
= SSA_NAME_VAR (var
);
87 /* If base variable hasn't been seen, set it up. */
88 if (!ann
->base_var_processed
)
90 ann
->base_var_processed
= 1;
91 VAR_ANN_BASE_INDEX (ann
) = num
++;
92 VEC_safe_push (tree
, heap
, map
->basevars
, var
);
94 map
->partition_to_base_index
[x
] = VAR_ANN_BASE_INDEX (ann
);
97 map
->num_basevars
= num
;
99 /* Now clear the processed bit. */
100 for (x
= 0; x
< num
; x
++)
102 var
= VEC_index (tree
, map
->basevars
, x
);
103 var_ann (var
)->base_var_processed
= 0;
106 #ifdef ENABLE_CHECKING
107 for (x
= 0; x
< num_part
; x
++)
110 var
= SSA_NAME_VAR (partition_to_var (map
, x
));
111 var2
= VEC_index (tree
, map
->basevars
, basevar_index (map
, x
));
112 gcc_assert (var
== var2
);
118 /* Remove the base table in MAP. */
121 var_map_base_fini (var_map map
)
123 /* Free the basevar info if it is present. */
124 if (map
->partition_to_base_index
!= NULL
)
126 VEC_free (tree
, heap
, map
->basevars
);
127 free (map
->partition_to_base_index
);
128 map
->partition_to_base_index
= NULL
;
129 map
->num_basevars
= 0;
132 /* Create a variable partition map of SIZE, initialize and return it. */
135 init_var_map (int size
)
139 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
140 map
->var_partition
= partition_new (size
);
142 map
->partition_to_view
= NULL
;
143 map
->view_to_partition
= NULL
;
144 map
->num_partitions
= size
;
145 map
->partition_size
= size
;
146 map
->num_basevars
= 0;
147 map
->partition_to_base_index
= NULL
;
148 map
->basevars
= NULL
;
153 /* Free memory associated with MAP. */
156 delete_var_map (var_map map
)
158 var_map_base_fini (map
);
159 partition_delete (map
->var_partition
);
160 free (map
->partition_to_view
);
161 free (map
->view_to_partition
);
166 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
167 Returns the partition which represents the new partition. If the two
168 partitions cannot be combined, NO_PARTITION is returned. */
171 var_union (var_map map
, tree var1
, tree var2
)
175 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
176 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
178 /* This is independent of partition_to_view. If partition_to_view is
179 on, then whichever one of these partitions is absorbed will never have a
180 dereference into the partition_to_view array any more. */
182 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
183 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
185 gcc_assert (p1
!= NO_PARTITION
);
186 gcc_assert (p2
!= NO_PARTITION
);
191 p3
= partition_union (map
->var_partition
, p1
, p2
);
193 if (map
->partition_to_view
)
194 p3
= map
->partition_to_view
[p3
];
200 /* Compress the partition numbers in MAP such that they fall in the range
201 0..(num_partitions-1) instead of wherever they turned out during
202 the partitioning exercise. This removes any references to unused
203 partitions, thereby allowing bitmaps and other vectors to be much
206 This is implemented such that compaction doesn't affect partitioning.
207 Ie., once partitions are created and possibly merged, running one
208 or more different kind of compaction will not affect the partitions
209 themselves. Their index might change, but all the same variables will
210 still be members of the same partition group. This allows work on reduced
211 sets, and no loss of information when a larger set is later desired.
213 In particular, coalescing can work on partitions which have 2 or more
214 definitions, and then 'recompact' later to include all the single
215 definitions for assignment to program variables. */
218 /* Set MAP back to the initial state of having no partition view. Return a
219 bitmap which has a bit set for each partition number which is in use in the
223 partition_view_init (var_map map
)
229 used
= BITMAP_ALLOC (NULL
);
231 /* Already in a view? Abandon the old one. */
232 if (map
->partition_to_view
)
234 free (map
->partition_to_view
);
235 map
->partition_to_view
= NULL
;
237 if (map
->view_to_partition
)
239 free (map
->view_to_partition
);
240 map
->view_to_partition
= NULL
;
243 /* Find out which partitions are actually referenced. */
244 for (x
= 0; x
< map
->partition_size
; x
++)
246 tmp
= partition_find (map
->var_partition
, x
);
247 if (ssa_name (tmp
) != NULL_TREE
&& is_gimple_reg (ssa_name (tmp
))
248 && (!has_zero_uses (ssa_name (tmp
))
249 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
250 bitmap_set_bit (used
, tmp
);
253 map
->num_partitions
= map
->partition_size
;
258 /* This routine will finalize the view data for MAP based on the partitions
259 set in SELECTED. This is either the same bitmap returned from
260 partition_view_init, or a trimmed down version if some of those partitions
261 were not desired in this view. SELECTED is freed before returning. */
264 partition_view_fini (var_map map
, bitmap selected
)
267 unsigned count
, i
, x
, limit
;
269 gcc_assert (selected
);
271 count
= bitmap_count_bits (selected
);
272 limit
= map
->partition_size
;
274 /* If its a one-to-one ratio, we don't need any view compaction. */
277 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
278 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
279 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
282 /* Give each selected partition an index. */
283 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
285 map
->partition_to_view
[x
] = i
;
286 map
->view_to_partition
[i
] = x
;
289 gcc_assert (i
== count
);
290 map
->num_partitions
= i
;
293 BITMAP_FREE (selected
);
297 /* Create a partition view which includes all the used partitions in MAP. If
298 WANT_BASES is true, create the base variable map as well. */
301 partition_view_normal (var_map map
, bool want_bases
)
305 used
= partition_view_init (map
);
306 partition_view_fini (map
, used
);
309 var_map_base_init (map
);
311 var_map_base_fini (map
);
315 /* Create a partition view in MAP which includes just partitions which occur in
316 the bitmap ONLY. If WANT_BASES is true, create the base variable map
320 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
323 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
327 used
= partition_view_init (map
);
328 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
330 p
= partition_find (map
->var_partition
, x
);
331 gcc_assert (bitmap_bit_p (used
, p
));
332 bitmap_set_bit (new_partitions
, p
);
334 partition_view_fini (map
, new_partitions
);
338 var_map_base_init (map
);
340 var_map_base_fini (map
);
344 static inline void mark_all_vars_used (tree
*, void *data
);
346 /* Helper function for mark_all_vars_used, called via walk_tree. */
349 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data
)
352 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
355 if (TREE_CODE (t
) == SSA_NAME
)
356 t
= SSA_NAME_VAR (t
);
358 if (IS_EXPR_CODE_CLASS (c
)
359 && (b
= TREE_BLOCK (t
)) != NULL
)
360 TREE_USED (b
) = true;
362 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
363 fields do not contain vars. */
364 if (TREE_CODE (t
) == TARGET_MEM_REF
)
366 mark_all_vars_used (&TMR_BASE (t
), data
);
367 mark_all_vars_used (&TMR_INDEX (t
), data
);
368 mark_all_vars_used (&TMR_INDEX2 (t
), data
);
373 /* Only need to mark VAR_DECLS; parameters and return results are not
374 eliminated as unused. */
375 if (TREE_CODE (t
) == VAR_DECL
)
377 if (data
!= NULL
&& bitmap_clear_bit ((bitmap
) data
, DECL_UID (t
))
378 && DECL_CONTEXT (t
) == current_function_decl
)
379 mark_all_vars_used (&DECL_INITIAL (t
), data
);
380 if (var_ann (t
) != NULL
)
383 /* remove_unused_scope_block_p requires information about labels
384 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
385 if (TREE_CODE (t
) == LABEL_DECL
)
386 /* Although the TREE_USED values that the frontend uses would be
387 acceptable (albeit slightly over-conservative) for our purposes,
388 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
389 must re-compute it here. */
392 if (IS_TYPE_OR_DECL_P (t
))
398 /* Mark the scope block SCOPE and its subblocks unused when they can be
399 possibly eliminated if dead. */
402 mark_scope_block_unused (tree scope
)
405 TREE_USED (scope
) = false;
406 if (!(*debug_hooks
->ignore_block
) (scope
))
407 TREE_USED (scope
) = true;
408 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
409 mark_scope_block_unused (t
);
412 /* Look if the block is dead (by possibly eliminating its dead subblocks)
413 and return true if so.
414 Block is declared dead if:
415 1) No statements are associated with it.
416 2) Declares no live variables
417 3) All subblocks are dead
418 or there is precisely one subblocks and the block
419 has same abstract origin as outer block and declares
420 no variables, so it is pure wrapper.
421 When we are not outputting full debug info, we also eliminate dead variables
422 out of scope blocks to let them to be recycled by GGC and to save copying work
423 done by the inliner. */
426 remove_unused_scope_block_p (tree scope
)
429 bool unused
= !TREE_USED (scope
);
432 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
434 next
= &DECL_CHAIN (*t
);
436 /* Debug info of nested function refers to the block of the
437 function. We might stil call it even if all statements
438 of function it was nested into was elliminated.
440 TODO: We can actually look into cgraph to see if function
441 will be output to file. */
442 if (TREE_CODE (*t
) == FUNCTION_DECL
)
445 /* If a decl has a value expr, we need to instantiate it
446 regardless of debug info generation, to avoid codegen
447 differences in memory overlap tests. update_equiv_regs() may
448 indirectly call validate_equiv_mem() to test whether a
449 SET_DEST overlaps with others, and if the value expr changes
450 by virtual register instantiation, we may get end up with
451 different results. */
452 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
455 /* Remove everything we don't generate debug info for.
456 Don't remove larger vars though, because BLOCK_VARS are
457 used also during expansion to determine which variables
458 might share stack space. */
459 else if (DECL_IGNORED_P (*t
) && is_gimple_reg (*t
))
461 *t
= DECL_CHAIN (*t
);
465 /* When we are outputting debug info, we usually want to output
466 info about optimized-out variables in the scope blocks.
467 Exception are the scope blocks not containing any instructions
468 at all so user can't get into the scopes at first place. */
469 else if (var_ann (*t
) != NULL
&& is_used_p (*t
))
471 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
472 /* For labels that are still used in the IL, the decision to
473 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
474 risk having different ordering in debug vs. non-debug builds
475 during inlining or versioning.
476 A label appearing here (we have already checked DECL_IGNORED_P)
477 should not be used in the IL unless it has been explicitly used
478 before, so we use TREE_USED as an approximation. */
479 /* In principle, we should do the same here as for the debug case
480 below, however, when debugging, there might be additional nested
481 levels that keep an upper level with a label live, so we have to
482 force this block to be considered used, too. */
485 /* When we are not doing full debug info, we however can keep around
486 only the used variables for cfgexpand's memory packing saving quite
489 For sake of -g3, we keep around those vars but we don't count this as
490 use of block, so innermost block with no used vars and no instructions
491 can be considered dead. We only want to keep around blocks user can
492 breakpoint into and ask about value of optimized out variables.
494 Similarly we need to keep around types at least until all
495 variables of all nested blocks are gone. We track no
496 information on whether given type is used or not, so we have
497 to keep them even when not emitting debug information,
498 otherwise we may end up remapping variables and their (local)
499 types in different orders depending on whether debug
500 information is being generated. */
502 else if (TREE_CODE (*t
) == TYPE_DECL
503 || debug_info_level
== DINFO_LEVEL_NORMAL
504 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
508 *t
= DECL_CHAIN (*t
);
513 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
514 if (remove_unused_scope_block_p (*t
))
516 if (BLOCK_SUBBLOCKS (*t
))
518 tree next
= BLOCK_CHAIN (*t
);
519 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
521 *t
= BLOCK_SUBBLOCKS (*t
);
522 while (BLOCK_CHAIN (*t
))
524 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
525 t
= &BLOCK_CHAIN (*t
);
527 BLOCK_CHAIN (*t
) = next
;
528 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
529 t
= &BLOCK_CHAIN (*t
);
533 *t
= BLOCK_CHAIN (*t
);
537 t
= &BLOCK_CHAIN (*t
);
544 /* Outer scope is always used. */
545 else if (!BLOCK_SUPERCONTEXT (scope
)
546 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
548 /* Innermost blocks with no live variables nor statements can be always
550 else if (!nsubblocks
)
552 /* For terse debug info we can eliminate info on unused variables. */
553 else if (debug_info_level
== DINFO_LEVEL_NONE
554 || debug_info_level
== DINFO_LEVEL_TERSE
)
556 /* Even for -g0/-g1 don't prune outer scopes from artificial
557 functions, otherwise diagnostics using tree_nonartificial_location
558 will not be emitted properly. */
559 if (inlined_function_outer_scope_p (scope
))
564 && TREE_CODE (ao
) == BLOCK
565 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
566 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
568 && TREE_CODE (ao
) == FUNCTION_DECL
569 && DECL_DECLARED_INLINE_P (ao
)
570 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
574 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
576 /* See if this block is important for representation of inlined function.
577 Inlined functions are always represented by block with
578 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
580 else if (inlined_function_outer_scope_p (scope
))
583 /* Verfify that only blocks with source location set
584 are entry points to the inlined functions. */
585 gcc_assert (BLOCK_SOURCE_LOCATION (scope
) == UNKNOWN_LOCATION
);
587 TREE_USED (scope
) = !unused
;
591 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
592 eliminated during the tree->rtl conversion process. */
595 mark_all_vars_used (tree
*expr_p
, void *data
)
597 walk_tree (expr_p
, mark_all_vars_used_1
, data
, NULL
);
601 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
602 indentation level and FLAGS is as in print_generic_expr. */
605 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
610 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
611 TREE_USED (scope
) ? "" : " (unused)",
612 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
613 if (BLOCK_SOURCE_LOCATION (scope
) != UNKNOWN_LOCATION
)
615 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
616 fprintf (file
, " %s:%i", s
.file
, s
.line
);
618 if (BLOCK_ABSTRACT_ORIGIN (scope
))
620 tree origin
= block_ultimate_origin (scope
);
623 fprintf (file
, " Originating from :");
625 print_generic_decl (file
, origin
, flags
);
627 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
630 fprintf (file
, " \n");
631 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
636 used
= is_used_p (var
);
638 fprintf (file
, "%*s", indent
, "");
639 print_generic_decl (file
, var
, flags
);
640 fprintf (file
, "%s\n", used
? "" : " (unused)");
642 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
644 fprintf (file
, "%*s",indent
, "");
645 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
647 fprintf (file
, " (nonlocalized)\n");
649 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
650 dump_scope_block (file
, indent
+ 2, t
, flags
);
651 fprintf (file
, "\n%*s}\n",indent
, "");
654 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
655 is as in print_generic_expr. */
658 debug_scope_block (tree scope
, int flags
)
660 dump_scope_block (stderr
, 0, scope
, flags
);
664 /* Dump the tree of lexical scopes of current_function_decl to FILE.
665 FLAGS is as in print_generic_expr. */
668 dump_scope_blocks (FILE *file
, int flags
)
670 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
674 /* Dump the tree of lexical scopes of current_function_decl to stderr.
675 FLAGS is as in print_generic_expr. */
678 debug_scope_blocks (int flags
)
680 dump_scope_blocks (stderr
, flags
);
683 /* Remove local variables that are not referenced in the IL. */
686 remove_unused_locals (void)
690 referenced_var_iterator rvi
;
691 bitmap global_unused_vars
= NULL
;
692 unsigned srcidx
, dstidx
, num
;
693 bool have_local_clobbers
= false;
695 /* Removing declarations from lexical blocks when not optimizing is
696 not only a waste of time, it actually causes differences in stack
701 timevar_push (TV_REMOVE_UNUSED
);
703 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
705 /* Assume all locals are unused. */
706 FOR_EACH_REFERENCED_VAR (cfun
, t
, rvi
)
709 /* Walk the CFG marking all referenced symbols. */
712 gimple_stmt_iterator gsi
;
717 /* Walk the statements. */
718 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
720 gimple stmt
= gsi_stmt (gsi
);
721 tree b
= gimple_block (stmt
);
723 if (is_gimple_debug (stmt
))
726 if (gimple_clobber_p (stmt
))
728 have_local_clobbers
= true;
733 TREE_USED (b
) = true;
735 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
736 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
), NULL
);
739 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
744 gimple phi
= gsi_stmt (gsi
);
746 /* No point processing globals. */
747 if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi
))))
750 def
= gimple_phi_result (phi
);
751 mark_all_vars_used (&def
, NULL
);
753 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
755 tree arg
= USE_FROM_PTR (arg_p
);
756 mark_all_vars_used (&arg
, NULL
);
760 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
762 TREE_USED (e
->goto_block
) = true;
765 /* We do a two-pass approach about the out-of-scope clobbers. We want
766 to remove them if they are the only references to a local variable,
767 but we want to retain them when there's any other. So the first pass
768 ignores them, and the second pass (if there were any) tries to remove
770 if (have_local_clobbers
)
773 gimple_stmt_iterator gsi
;
775 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
777 gimple stmt
= gsi_stmt (gsi
);
778 tree b
= gimple_block (stmt
);
780 if (gimple_clobber_p (stmt
))
782 tree lhs
= gimple_assign_lhs (stmt
);
783 lhs
= get_base_address (lhs
);
784 if (TREE_CODE (lhs
) == SSA_NAME
)
785 lhs
= SSA_NAME_VAR (lhs
);
786 if (DECL_P (lhs
) && (!var_ann (lhs
) || !is_used_p (lhs
)))
788 unlink_stmt_vdef (stmt
);
789 gsi_remove (&gsi
, true);
794 TREE_USED (b
) = true;
800 cfun
->has_local_explicit_reg_vars
= false;
802 /* Remove unmarked local vars from local_decls. */
803 num
= VEC_length (tree
, cfun
->local_decls
);
804 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
806 var
= VEC_index (tree
, cfun
->local_decls
, srcidx
);
807 if (TREE_CODE (var
) != FUNCTION_DECL
809 || !is_used_p (var
)))
811 if (is_global_var (var
))
813 if (global_unused_vars
== NULL
)
814 global_unused_vars
= BITMAP_ALLOC (NULL
);
815 bitmap_set_bit (global_unused_vars
, DECL_UID (var
));
820 else if (TREE_CODE (var
) == VAR_DECL
821 && DECL_HARD_REGISTER (var
)
822 && !is_global_var (var
))
823 cfun
->has_local_explicit_reg_vars
= true;
825 if (srcidx
!= dstidx
)
826 VEC_replace (tree
, cfun
->local_decls
, dstidx
, var
);
830 VEC_truncate (tree
, cfun
->local_decls
, dstidx
);
832 /* Remove unmarked global vars from local_decls. */
833 if (global_unused_vars
!= NULL
)
837 FOR_EACH_LOCAL_DECL (cfun
, ix
, var
)
838 if (TREE_CODE (var
) == VAR_DECL
839 && is_global_var (var
)
840 && var_ann (var
) != NULL
842 && DECL_CONTEXT (var
) == current_function_decl
)
843 mark_all_vars_used (&DECL_INITIAL (var
), global_unused_vars
);
845 num
= VEC_length (tree
, cfun
->local_decls
);
846 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
848 var
= VEC_index (tree
, cfun
->local_decls
, srcidx
);
849 if (TREE_CODE (var
) == VAR_DECL
850 && is_global_var (var
)
851 && bitmap_bit_p (global_unused_vars
, DECL_UID (var
)))
854 if (srcidx
!= dstidx
)
855 VEC_replace (tree
, cfun
->local_decls
, dstidx
, var
);
859 VEC_truncate (tree
, cfun
->local_decls
, dstidx
);
860 BITMAP_FREE (global_unused_vars
);
863 /* Remove unused variables from REFERENCED_VARs. */
864 FOR_EACH_REFERENCED_VAR (cfun
, t
, rvi
)
865 if (!is_global_var (t
)
866 && TREE_CODE (t
) != PARM_DECL
867 && TREE_CODE (t
) != RESULT_DECL
869 remove_referenced_var (t
);
870 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
));
871 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
873 fprintf (dump_file
, "Scope blocks after cleanups:\n");
874 dump_scope_blocks (dump_file
, dump_flags
);
877 timevar_pop (TV_REMOVE_UNUSED
);
881 /* Allocate and return a new live range information object base on MAP. */
883 static tree_live_info_p
884 new_tree_live_info (var_map map
)
886 tree_live_info_p live
;
889 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
891 live
->num_blocks
= last_basic_block
;
893 live
->livein
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
894 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
895 live
->livein
[x
] = BITMAP_ALLOC (NULL
);
897 live
->liveout
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
898 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
899 live
->liveout
[x
] = BITMAP_ALLOC (NULL
);
901 live
->work_stack
= XNEWVEC (int, last_basic_block
);
902 live
->stack_top
= live
->work_stack
;
904 live
->global
= BITMAP_ALLOC (NULL
);
909 /* Free storage for live range info object LIVE. */
912 delete_tree_live_info (tree_live_info_p live
)
916 BITMAP_FREE (live
->global
);
917 free (live
->work_stack
);
919 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
920 BITMAP_FREE (live
->liveout
[x
]);
921 free (live
->liveout
);
923 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
924 BITMAP_FREE (live
->livein
[x
]);
931 /* Visit basic block BB and propagate any required live on entry bits from
932 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
933 TMP is a temporary work bitmap which is passed in to avoid reallocating
937 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
945 gcc_assert (!TEST_BIT (visited
, bb
->index
));
947 SET_BIT (visited
, bb
->index
);
948 loe
= live_on_entry (live
, bb
);
950 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
953 if (pred_bb
== ENTRY_BLOCK_PTR
)
955 /* TMP is variables live-on-entry from BB that aren't defined in the
956 predecessor block. This should be the live on entry vars to pred.
957 Note that liveout is the DEFs in a block while live on entry is
959 bitmap_and_compl (tmp
, loe
, live
->liveout
[pred_bb
->index
]);
961 /* Add these bits to live-on-entry for the pred. if there are any
962 changes, and pred_bb has been visited already, add it to the
964 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
965 if (TEST_BIT (visited
, pred_bb
->index
) && change
)
967 RESET_BIT (visited
, pred_bb
->index
);
968 *(live
->stack_top
)++ = pred_bb
->index
;
974 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
975 of all the variables. */
978 live_worklist (tree_live_info_p live
)
982 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
983 bitmap tmp
= BITMAP_ALLOC (NULL
);
985 sbitmap_zero (visited
);
987 /* Visit all the blocks in reverse order and propagate live on entry values
988 into the predecessors blocks. */
989 FOR_EACH_BB_REVERSE (bb
)
990 loe_visit_block (live
, bb
, visited
, tmp
);
992 /* Process any blocks which require further iteration. */
993 while (live
->stack_top
!= live
->work_stack
)
995 b
= *--(live
->stack_top
);
996 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
1000 sbitmap_free (visited
);
1004 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1005 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1006 in the liveout vector. */
1009 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1014 basic_block def_bb
= NULL
;
1015 imm_use_iterator imm_iter
;
1016 bool global
= false;
1018 p
= var_to_partition (live
->map
, ssa_name
);
1019 if (p
== NO_PARTITION
)
1022 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1025 def_bb
= gimple_bb (stmt
);
1026 /* Mark defs in liveout bitmap temporarily. */
1028 bitmap_set_bit (live
->liveout
[def_bb
->index
], p
);
1031 def_bb
= ENTRY_BLOCK_PTR
;
1033 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1034 add it to the list of live on entry blocks. */
1035 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1037 gimple use_stmt
= USE_STMT (use
);
1038 basic_block add_block
= NULL
;
1040 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1042 /* Uses in PHI's are considered to be live at exit of the SRC block
1043 as this is where a copy would be inserted. Check to see if it is
1044 defined in that block, or whether its live on entry. */
1045 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1046 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
1047 if (e
->src
!= ENTRY_BLOCK_PTR
)
1049 if (e
->src
!= def_bb
)
1053 else if (is_gimple_debug (use_stmt
))
1057 /* If its not defined in this block, its live on entry. */
1058 basic_block use_bb
= gimple_bb (use_stmt
);
1059 if (use_bb
!= def_bb
)
1063 /* If there was a live on entry use, set the bit. */
1067 bitmap_set_bit (live
->livein
[add_block
->index
], p
);
1071 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1072 on entry blocks between the def and all the uses. */
1074 bitmap_set_bit (live
->global
, p
);
1078 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1081 calculate_live_on_exit (tree_live_info_p liveinfo
)
1087 /* live on entry calculations used liveout vectors for defs, clear them. */
1089 bitmap_clear (liveinfo
->liveout
[bb
->index
]);
1091 /* Set all the live-on-exit bits for uses in PHIs. */
1094 gimple_stmt_iterator gsi
;
1097 /* Mark the PHI arguments which are live on exit to the pred block. */
1098 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1100 gimple phi
= gsi_stmt (gsi
);
1101 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1103 tree t
= PHI_ARG_DEF (phi
, i
);
1106 if (TREE_CODE (t
) != SSA_NAME
)
1109 p
= var_to_partition (liveinfo
->map
, t
);
1110 if (p
== NO_PARTITION
)
1112 e
= gimple_phi_arg_edge (phi
, i
);
1113 if (e
->src
!= ENTRY_BLOCK_PTR
)
1114 bitmap_set_bit (liveinfo
->liveout
[e
->src
->index
], p
);
1118 /* Add each successors live on entry to this bock live on exit. */
1119 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1120 if (e
->dest
!= EXIT_BLOCK_PTR
)
1121 bitmap_ior_into (liveinfo
->liveout
[bb
->index
],
1122 live_on_entry (liveinfo
, e
->dest
));
1127 /* Given partition map MAP, calculate all the live on entry bitmaps for
1128 each partition. Return a new live info object. */
1131 calculate_live_ranges (var_map map
)
1135 tree_live_info_p live
;
1137 live
= new_tree_live_info (map
);
1138 for (i
= 0; i
< num_var_partitions (map
); i
++)
1140 var
= partition_to_var (map
, i
);
1141 if (var
!= NULL_TREE
)
1142 set_var_live_on_entry (var
, live
);
1145 live_worklist (live
);
1147 #ifdef ENABLE_CHECKING
1148 verify_live_on_entry (live
);
1151 calculate_live_on_exit (live
);
1156 /* Output partition map MAP to file F. */
1159 dump_var_map (FILE *f
, var_map map
)
1165 fprintf (f
, "\nPartition map \n\n");
1167 for (x
= 0; x
< map
->num_partitions
; x
++)
1169 if (map
->view_to_partition
!= NULL
)
1170 p
= map
->view_to_partition
[x
];
1174 if (ssa_name (p
) == NULL_TREE
)
1178 for (y
= 1; y
< num_ssa_names
; y
++)
1180 p
= partition_find (map
->var_partition
, y
);
1181 if (map
->partition_to_view
)
1182 p
= map
->partition_to_view
[p
];
1187 fprintf(f
, "Partition %d (", x
);
1188 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1191 fprintf (f
, "%d ", y
);
1201 /* Output live range info LIVE to file F, controlled by FLAG. */
1204 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1208 var_map map
= live
->map
;
1211 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1215 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1216 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[bb
->index
], 0, i
, bi
)
1218 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1225 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1229 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1230 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
, bi
)
1232 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1240 struct GTY(()) numbered_tree_d
1245 typedef struct numbered_tree_d numbered_tree
;
1247 DEF_VEC_O (numbered_tree
);
1248 DEF_VEC_ALLOC_O (numbered_tree
, heap
);
1250 /* Compare two declarations references by their DECL_UID / sequence number.
1251 Called via qsort. */
1254 compare_decls_by_uid (const void *pa
, const void *pb
)
1256 const numbered_tree
*nt_a
= ((const numbered_tree
*)pa
);
1257 const numbered_tree
*nt_b
= ((const numbered_tree
*)pb
);
1259 if (DECL_UID (nt_a
->t
) != DECL_UID (nt_b
->t
))
1260 return DECL_UID (nt_a
->t
) - DECL_UID (nt_b
->t
);
1261 return nt_a
->num
- nt_b
->num
;
1264 /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls. */
1266 dump_enumerated_decls_push (tree
*tp
, int *walk_subtrees
, void *data
)
1268 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
1269 VEC (numbered_tree
, heap
) **list
= (VEC (numbered_tree
, heap
) **) &wi
->info
;
1275 nt
.num
= VEC_length (numbered_tree
, *list
);
1276 VEC_safe_push (numbered_tree
, heap
, *list
, &nt
);
1281 /* Find all the declarations used by the current function, sort them by uid,
1282 and emit the sorted list. Each declaration is tagged with a sequence
1283 number indicating when it was found during statement / tree walking,
1284 so that TDF_NOUID comparisons of anonymous declarations are still
1285 meaningful. Where a declaration was encountered more than once, we
1286 emit only the sequence number of the first encounter.
1287 FILE is the dump file where to output the list and FLAGS is as in
1288 print_generic_expr. */
1290 dump_enumerated_decls (FILE *file
, int flags
)
1293 struct walk_stmt_info wi
;
1294 VEC (numbered_tree
, heap
) *decl_list
= VEC_alloc (numbered_tree
, heap
, 40);
1296 memset (&wi
, '\0', sizeof (wi
));
1297 wi
.info
= (void*) decl_list
;
1300 gimple_stmt_iterator gsi
;
1302 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1303 if (!is_gimple_debug (gsi_stmt (gsi
)))
1304 walk_gimple_stmt (&gsi
, NULL
, dump_enumerated_decls_push
, &wi
);
1306 decl_list
= (VEC (numbered_tree
, heap
) *) wi
.info
;
1307 VEC_qsort (numbered_tree
, decl_list
, compare_decls_by_uid
);
1308 if (VEC_length (numbered_tree
, decl_list
))
1312 tree last
= NULL_TREE
;
1314 fprintf (file
, "Declarations used by %s, sorted by DECL_UID:\n",
1315 current_function_name ());
1316 FOR_EACH_VEC_ELT (numbered_tree
, decl_list
, ix
, ntp
)
1320 fprintf (file
, "%d: ", ntp
->num
);
1321 print_generic_decl (file
, ntp
->t
, flags
);
1322 fprintf (file
, "\n");
1326 VEC_free (numbered_tree
, heap
, decl_list
);
1329 #ifdef ENABLE_CHECKING
1330 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1333 register_ssa_partition_check (tree ssa_var
)
1335 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1336 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
1338 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1339 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1340 fprintf (stderr
, " in the SSA->Normal phase.\n");
1341 internal_error ("SSA corruption");
1346 /* Verify that the info in LIVE matches the current cfg. */
1349 verify_live_on_entry (tree_live_info_p live
)
1358 var_map map
= live
->map
;
1360 /* Check for live on entry partitions and report those with a DEF in
1361 the program. This will typically mean an optimization has done
1363 bb
= ENTRY_BLOCK_PTR
;
1365 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1367 int entry_block
= e
->dest
->index
;
1368 if (e
->dest
== EXIT_BLOCK_PTR
)
1370 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1375 var
= partition_to_var (map
, i
);
1376 stmt
= SSA_NAME_DEF_STMT (var
);
1377 tmp
= gimple_bb (stmt
);
1378 d
= gimple_default_def (cfun
, SSA_NAME_VAR (var
));
1380 loe
= live_on_entry (live
, e
->dest
);
1381 if (loe
&& bitmap_bit_p (loe
, i
))
1383 if (!gimple_nop_p (stmt
))
1386 print_generic_expr (stderr
, var
, TDF_SLIM
);
1387 fprintf (stderr
, " is defined ");
1389 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1390 fprintf (stderr
, "by:\n");
1391 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1392 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1394 fprintf (stderr
, " So it appears to have multiple defs.\n");
1401 print_generic_expr (stderr
, var
, TDF_SLIM
);
1402 fprintf (stderr
, " is live-on-entry to BB%d ",
1406 fprintf (stderr
, " but is not the default def of ");
1407 print_generic_expr (stderr
, d
, TDF_SLIM
);
1408 fprintf (stderr
, "\n");
1411 fprintf (stderr
, " and there is no default def.\n");
1418 /* The only way this var shouldn't be marked live on entry is
1419 if it occurs in a PHI argument of the block. */
1422 gimple_stmt_iterator gsi
;
1423 for (gsi
= gsi_start_phis (e
->dest
);
1424 !gsi_end_p (gsi
) && !ok
;
1427 gimple phi
= gsi_stmt (gsi
);
1428 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1429 if (var
== gimple_phi_arg_def (phi
, z
))
1438 print_generic_expr (stderr
, var
, TDF_SLIM
);
1439 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1441 fprintf (stderr
, "but it is a default def so it should be.\n");
1445 gcc_assert (num
<= 0);