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
)
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
)
351 bitmap global_unused_vars
= (bitmap
)data
;
353 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
356 if (TREE_CODE (t
) == SSA_NAME
)
357 t
= SSA_NAME_VAR (t
);
359 if (IS_EXPR_CODE_CLASS (c
)
360 && (b
= TREE_BLOCK (t
)) != NULL
)
361 TREE_USED (b
) = true;
363 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
364 fields do not contain vars. */
365 if (TREE_CODE (t
) == TARGET_MEM_REF
)
367 mark_all_vars_used (&TMR_BASE (t
), data
);
368 mark_all_vars_used (&TMR_INDEX (t
), data
);
369 mark_all_vars_used (&TMR_INDEX2 (t
), data
);
374 /* Only need to mark VAR_DECLS; parameters and return results are not
375 eliminated as unused. */
376 if (TREE_CODE (t
) == VAR_DECL
)
378 /* Global vars do not have a var-annotation so their use is tracked
379 with the global_unused_vars bitmap. Also walk their initializer
380 when they are first recognized as used. */
381 if (is_global_var (t
))
383 if (bitmap_clear_bit (global_unused_vars
, DECL_UID (t
)))
384 mark_all_vars_used (&DECL_INITIAL (t
), data
);
389 /* remove_unused_scope_block_p requires information about labels
390 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
391 else if (TREE_CODE (t
) == LABEL_DECL
)
392 /* Although the TREE_USED values that the frontend uses would be
393 acceptable (albeit slightly over-conservative) for our purposes,
394 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
395 must re-compute it here. */
398 if (IS_TYPE_OR_DECL_P (t
))
404 /* Mark the scope block SCOPE and its subblocks unused when they can be
405 possibly eliminated if dead. */
408 mark_scope_block_unused (tree scope
)
411 TREE_USED (scope
) = false;
412 if (!(*debug_hooks
->ignore_block
) (scope
))
413 TREE_USED (scope
) = true;
414 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
415 mark_scope_block_unused (t
);
418 /* Look if the block is dead (by possibly eliminating its dead subblocks)
419 and return true if so.
420 Block is declared dead if:
421 1) No statements are associated with it.
422 2) Declares no live variables
423 3) All subblocks are dead
424 or there is precisely one subblocks and the block
425 has same abstract origin as outer block and declares
426 no variables, so it is pure wrapper.
427 When we are not outputting full debug info, we also eliminate dead variables
428 out of scope blocks to let them to be recycled by GGC and to save copying work
429 done by the inliner. */
432 remove_unused_scope_block_p (tree scope
, bitmap global_unused_vars
)
435 bool unused
= !TREE_USED (scope
);
438 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
440 next
= &DECL_CHAIN (*t
);
442 /* Debug info of nested function refers to the block of the
443 function. We might stil call it even if all statements
444 of function it was nested into was elliminated.
446 TODO: We can actually look into cgraph to see if function
447 will be output to file. */
448 if (TREE_CODE (*t
) == FUNCTION_DECL
)
451 /* If a decl has a value expr, we need to instantiate it
452 regardless of debug info generation, to avoid codegen
453 differences in memory overlap tests. update_equiv_regs() may
454 indirectly call validate_equiv_mem() to test whether a
455 SET_DEST overlaps with others, and if the value expr changes
456 by virtual register instantiation, we may get end up with
457 different results. */
458 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
461 /* Remove everything we don't generate debug info for. */
462 else if (DECL_IGNORED_P (*t
))
464 *t
= DECL_CHAIN (*t
);
468 /* When we are outputting debug info, we usually want to output
469 info about optimized-out variables in the scope blocks.
470 Exception are the scope blocks not containing any instructions
471 at all so user can't get into the scopes at first place. */
472 else if ((is_global_var (*t
)
473 && !bitmap_bit_p (global_unused_vars
, DECL_UID (*t
)))
474 || (var_ann (*t
) != NULL
&& is_used_p (*t
)))
476 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
477 /* For labels that are still used in the IL, the decision to
478 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
479 risk having different ordering in debug vs. non-debug builds
480 during inlining or versioning.
481 A label appearing here (we have already checked DECL_IGNORED_P)
482 should not be used in the IL unless it has been explicitly used
483 before, so we use TREE_USED as an approximation. */
484 /* In principle, we should do the same here as for the debug case
485 below, however, when debugging, there might be additional nested
486 levels that keep an upper level with a label live, so we have to
487 force this block to be considered used, too. */
490 /* When we are not doing full debug info, we however can keep around
491 only the used variables for cfgexpand's memory packing saving quite
494 For sake of -g3, we keep around those vars but we don't count this as
495 use of block, so innermost block with no used vars and no instructions
496 can be considered dead. We only want to keep around blocks user can
497 breakpoint into and ask about value of optimized out variables.
499 Similarly we need to keep around types at least until all
500 variables of all nested blocks are gone. We track no
501 information on whether given type is used or not, so we have
502 to keep them even when not emitting debug information,
503 otherwise we may end up remapping variables and their (local)
504 types in different orders depending on whether debug
505 information is being generated. */
507 else if (TREE_CODE (*t
) == TYPE_DECL
508 || debug_info_level
== DINFO_LEVEL_NORMAL
509 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
513 *t
= DECL_CHAIN (*t
);
518 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
519 if (remove_unused_scope_block_p (*t
, global_unused_vars
))
521 if (BLOCK_SUBBLOCKS (*t
))
523 tree next
= BLOCK_CHAIN (*t
);
524 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
526 *t
= BLOCK_SUBBLOCKS (*t
);
527 while (BLOCK_CHAIN (*t
))
529 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
530 t
= &BLOCK_CHAIN (*t
);
532 BLOCK_CHAIN (*t
) = next
;
533 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
534 t
= &BLOCK_CHAIN (*t
);
538 *t
= BLOCK_CHAIN (*t
);
542 t
= &BLOCK_CHAIN (*t
);
549 /* Outer scope is always used. */
550 else if (!BLOCK_SUPERCONTEXT (scope
)
551 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
553 /* Innermost blocks with no live variables nor statements can be always
555 else if (!nsubblocks
)
557 /* For terse debug info we can eliminate info on unused variables. */
558 else if (debug_info_level
== DINFO_LEVEL_NONE
559 || debug_info_level
== DINFO_LEVEL_TERSE
)
561 /* Even for -g0/-g1 don't prune outer scopes from artificial
562 functions, otherwise diagnostics using tree_nonartificial_location
563 will not be emitted properly. */
564 if (inlined_function_outer_scope_p (scope
))
569 && TREE_CODE (ao
) == BLOCK
570 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
571 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
573 && TREE_CODE (ao
) == FUNCTION_DECL
574 && DECL_DECLARED_INLINE_P (ao
)
575 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
579 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
581 /* See if this block is important for representation of inlined function.
582 Inlined functions are always represented by block with
583 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
585 else if (inlined_function_outer_scope_p (scope
))
588 /* Verfify that only blocks with source location set
589 are entry points to the inlined functions. */
590 gcc_assert (BLOCK_SOURCE_LOCATION (scope
) == UNKNOWN_LOCATION
);
592 TREE_USED (scope
) = !unused
;
596 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
597 eliminated during the tree->rtl conversion process. */
600 mark_all_vars_used (tree
*expr_p
, void *data
)
602 walk_tree (expr_p
, mark_all_vars_used_1
, data
, NULL
);
606 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
607 indentation level and FLAGS is as in print_generic_expr. */
610 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
615 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
616 TREE_USED (scope
) ? "" : " (unused)",
617 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
618 if (BLOCK_SOURCE_LOCATION (scope
) != UNKNOWN_LOCATION
)
620 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
621 fprintf (file
, " %s:%i", s
.file
, s
.line
);
623 if (BLOCK_ABSTRACT_ORIGIN (scope
))
625 tree origin
= block_ultimate_origin (scope
);
628 fprintf (file
, " Originating from :");
630 print_generic_decl (file
, origin
, flags
);
632 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
635 fprintf (file
, " \n");
636 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
641 used
= is_used_p (var
);
643 fprintf (file
, "%*s", indent
, "");
644 print_generic_decl (file
, var
, flags
);
645 fprintf (file
, "%s\n", used
? "" : " (unused)");
647 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
649 fprintf (file
, "%*s",indent
, "");
650 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
652 fprintf (file
, " (nonlocalized)\n");
654 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
655 dump_scope_block (file
, indent
+ 2, t
, flags
);
656 fprintf (file
, "\n%*s}\n",indent
, "");
659 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
660 is as in print_generic_expr. */
663 debug_scope_block (tree scope
, int flags
)
665 dump_scope_block (stderr
, 0, scope
, flags
);
669 /* Dump the tree of lexical scopes of current_function_decl to FILE.
670 FLAGS is as in print_generic_expr. */
673 dump_scope_blocks (FILE *file
, int flags
)
675 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
679 /* Dump the tree of lexical scopes of current_function_decl to stderr.
680 FLAGS is as in print_generic_expr. */
683 debug_scope_blocks (int flags
)
685 dump_scope_blocks (stderr
, flags
);
688 /* Remove local variables that are not referenced in the IL. */
691 remove_unused_locals (void)
695 referenced_var_iterator rvi
;
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 /* Assume all locals are unused. */
711 FOR_EACH_REFERENCED_VAR (cfun
, t
, rvi
)
714 /* Assume all globals in local decls are unused. */
715 global_unused_vars
= BITMAP_ALLOC (NULL
);
716 FOR_EACH_LOCAL_DECL (cfun
, ix
, var
)
717 if (TREE_CODE (var
) == VAR_DECL
718 && is_global_var (var
))
719 bitmap_set_bit (global_unused_vars
, DECL_UID (var
));
721 /* Walk the CFG marking all referenced symbols. */
724 gimple_stmt_iterator gsi
;
729 /* Walk the statements. */
730 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
732 gimple stmt
= gsi_stmt (gsi
);
733 tree b
= gimple_block (stmt
);
735 if (is_gimple_debug (stmt
))
738 if (gimple_clobber_p (stmt
))
740 have_local_clobbers
= true;
745 TREE_USED (b
) = true;
747 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
748 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
),
752 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
757 gimple phi
= gsi_stmt (gsi
);
759 if (!is_gimple_reg (gimple_phi_result (phi
)))
762 def
= gimple_phi_result (phi
);
763 mark_all_vars_used (&def
, global_unused_vars
);
765 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
767 tree arg
= USE_FROM_PTR (arg_p
);
768 mark_all_vars_used (&arg
, global_unused_vars
);
772 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
774 TREE_USED (e
->goto_block
) = true;
777 /* We do a two-pass approach about the out-of-scope clobbers. We want
778 to remove them if they are the only references to a local variable,
779 but we want to retain them when there's any other. So the first pass
780 ignores them, and the second pass (if there were any) tries to remove
782 if (have_local_clobbers
)
785 gimple_stmt_iterator gsi
;
787 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
789 gimple stmt
= gsi_stmt (gsi
);
790 tree b
= gimple_block (stmt
);
792 if (gimple_clobber_p (stmt
))
794 tree lhs
= gimple_assign_lhs (stmt
);
795 lhs
= get_base_address (lhs
);
796 if (TREE_CODE (lhs
) == SSA_NAME
)
797 lhs
= SSA_NAME_VAR (lhs
);
798 if (TREE_CODE (lhs
) == VAR_DECL
799 && ((is_global_var (lhs
)
800 && bitmap_bit_p (global_unused_vars
, DECL_UID (lhs
)))
801 || (!is_global_var (lhs
) && !is_used_p (lhs
))))
803 unlink_stmt_vdef (stmt
);
804 gsi_remove (&gsi
, true);
809 TREE_USED (b
) = true;
815 cfun
->has_local_explicit_reg_vars
= false;
817 /* Remove unmarked local and global vars from local_decls
818 and referenced vars. */
819 num
= VEC_length (tree
, cfun
->local_decls
);
820 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
822 var
= VEC_index (tree
, cfun
->local_decls
, srcidx
);
823 if (TREE_CODE (var
) == VAR_DECL
)
825 if (is_global_var (var
))
827 if (bitmap_bit_p (global_unused_vars
, DECL_UID (var
)))
830 else if (var_ann (var
) == NULL
834 remove_referenced_var (var
);
835 if (cfun
->nonlocal_goto_save_area
836 && TREE_OPERAND (cfun
->nonlocal_goto_save_area
, 0) == var
)
837 cfun
->nonlocal_goto_save_area
= NULL
;
841 if (TREE_CODE (var
) == VAR_DECL
842 && DECL_HARD_REGISTER (var
)
843 && !is_global_var (var
))
844 cfun
->has_local_explicit_reg_vars
= true;
846 if (srcidx
!= dstidx
)
847 VEC_replace (tree
, cfun
->local_decls
, dstidx
, var
);
851 VEC_truncate (tree
, cfun
->local_decls
, dstidx
);
853 /* ??? We end up with decls in referenced-vars that are not in
855 FOR_EACH_REFERENCED_VAR (cfun
, t
, rvi
)
856 if (TREE_CODE (t
) == VAR_DECL
857 && !VAR_DECL_IS_VIRTUAL_OPERAND (t
)
859 remove_referenced_var (t
);
861 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
),
864 BITMAP_FREE (global_unused_vars
);
866 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
868 fprintf (dump_file
, "Scope blocks after cleanups:\n");
869 dump_scope_blocks (dump_file
, dump_flags
);
872 timevar_pop (TV_REMOVE_UNUSED
);
876 /* Allocate and return a new live range information object base on MAP. */
878 static tree_live_info_p
879 new_tree_live_info (var_map map
)
881 tree_live_info_p live
;
884 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
886 live
->num_blocks
= last_basic_block
;
888 live
->livein
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
889 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
890 live
->livein
[x
] = BITMAP_ALLOC (NULL
);
892 live
->liveout
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
893 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
894 live
->liveout
[x
] = BITMAP_ALLOC (NULL
);
896 live
->work_stack
= XNEWVEC (int, last_basic_block
);
897 live
->stack_top
= live
->work_stack
;
899 live
->global
= BITMAP_ALLOC (NULL
);
904 /* Free storage for live range info object LIVE. */
907 delete_tree_live_info (tree_live_info_p live
)
911 BITMAP_FREE (live
->global
);
912 free (live
->work_stack
);
914 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
915 BITMAP_FREE (live
->liveout
[x
]);
916 free (live
->liveout
);
918 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
919 BITMAP_FREE (live
->livein
[x
]);
926 /* Visit basic block BB and propagate any required live on entry bits from
927 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
928 TMP is a temporary work bitmap which is passed in to avoid reallocating
932 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
940 gcc_assert (!TEST_BIT (visited
, bb
->index
));
942 SET_BIT (visited
, bb
->index
);
943 loe
= live_on_entry (live
, bb
);
945 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
948 if (pred_bb
== ENTRY_BLOCK_PTR
)
950 /* TMP is variables live-on-entry from BB that aren't defined in the
951 predecessor block. This should be the live on entry vars to pred.
952 Note that liveout is the DEFs in a block while live on entry is
954 bitmap_and_compl (tmp
, loe
, live
->liveout
[pred_bb
->index
]);
956 /* Add these bits to live-on-entry for the pred. if there are any
957 changes, and pred_bb has been visited already, add it to the
959 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
960 if (TEST_BIT (visited
, pred_bb
->index
) && change
)
962 RESET_BIT (visited
, pred_bb
->index
);
963 *(live
->stack_top
)++ = pred_bb
->index
;
969 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
970 of all the variables. */
973 live_worklist (tree_live_info_p live
)
977 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
978 bitmap tmp
= BITMAP_ALLOC (NULL
);
980 sbitmap_zero (visited
);
982 /* Visit all the blocks in reverse order and propagate live on entry values
983 into the predecessors blocks. */
984 FOR_EACH_BB_REVERSE (bb
)
985 loe_visit_block (live
, bb
, visited
, tmp
);
987 /* Process any blocks which require further iteration. */
988 while (live
->stack_top
!= live
->work_stack
)
990 b
= *--(live
->stack_top
);
991 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
995 sbitmap_free (visited
);
999 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1000 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1001 in the liveout vector. */
1004 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
1009 basic_block def_bb
= NULL
;
1010 imm_use_iterator imm_iter
;
1011 bool global
= false;
1013 p
= var_to_partition (live
->map
, ssa_name
);
1014 if (p
== NO_PARTITION
)
1017 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
1020 def_bb
= gimple_bb (stmt
);
1021 /* Mark defs in liveout bitmap temporarily. */
1023 bitmap_set_bit (live
->liveout
[def_bb
->index
], p
);
1026 def_bb
= ENTRY_BLOCK_PTR
;
1028 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1029 add it to the list of live on entry blocks. */
1030 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
1032 gimple use_stmt
= USE_STMT (use
);
1033 basic_block add_block
= NULL
;
1035 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1037 /* Uses in PHI's are considered to be live at exit of the SRC block
1038 as this is where a copy would be inserted. Check to see if it is
1039 defined in that block, or whether its live on entry. */
1040 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1041 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
1042 if (e
->src
!= ENTRY_BLOCK_PTR
)
1044 if (e
->src
!= def_bb
)
1048 else if (is_gimple_debug (use_stmt
))
1052 /* If its not defined in this block, its live on entry. */
1053 basic_block use_bb
= gimple_bb (use_stmt
);
1054 if (use_bb
!= def_bb
)
1058 /* If there was a live on entry use, set the bit. */
1062 bitmap_set_bit (live
->livein
[add_block
->index
], p
);
1066 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1067 on entry blocks between the def and all the uses. */
1069 bitmap_set_bit (live
->global
, p
);
1073 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1076 calculate_live_on_exit (tree_live_info_p liveinfo
)
1082 /* live on entry calculations used liveout vectors for defs, clear them. */
1084 bitmap_clear (liveinfo
->liveout
[bb
->index
]);
1086 /* Set all the live-on-exit bits for uses in PHIs. */
1089 gimple_stmt_iterator gsi
;
1092 /* Mark the PHI arguments which are live on exit to the pred block. */
1093 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1095 gimple phi
= gsi_stmt (gsi
);
1096 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1098 tree t
= PHI_ARG_DEF (phi
, i
);
1101 if (TREE_CODE (t
) != SSA_NAME
)
1104 p
= var_to_partition (liveinfo
->map
, t
);
1105 if (p
== NO_PARTITION
)
1107 e
= gimple_phi_arg_edge (phi
, i
);
1108 if (e
->src
!= ENTRY_BLOCK_PTR
)
1109 bitmap_set_bit (liveinfo
->liveout
[e
->src
->index
], p
);
1113 /* Add each successors live on entry to this bock live on exit. */
1114 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1115 if (e
->dest
!= EXIT_BLOCK_PTR
)
1116 bitmap_ior_into (liveinfo
->liveout
[bb
->index
],
1117 live_on_entry (liveinfo
, e
->dest
));
1122 /* Given partition map MAP, calculate all the live on entry bitmaps for
1123 each partition. Return a new live info object. */
1126 calculate_live_ranges (var_map map
)
1130 tree_live_info_p live
;
1132 live
= new_tree_live_info (map
);
1133 for (i
= 0; i
< num_var_partitions (map
); i
++)
1135 var
= partition_to_var (map
, i
);
1136 if (var
!= NULL_TREE
)
1137 set_var_live_on_entry (var
, live
);
1140 live_worklist (live
);
1142 #ifdef ENABLE_CHECKING
1143 verify_live_on_entry (live
);
1146 calculate_live_on_exit (live
);
1151 /* Output partition map MAP to file F. */
1154 dump_var_map (FILE *f
, var_map map
)
1160 fprintf (f
, "\nPartition map \n\n");
1162 for (x
= 0; x
< map
->num_partitions
; x
++)
1164 if (map
->view_to_partition
!= NULL
)
1165 p
= map
->view_to_partition
[x
];
1169 if (ssa_name (p
) == NULL_TREE
)
1173 for (y
= 1; y
< num_ssa_names
; y
++)
1175 p
= partition_find (map
->var_partition
, y
);
1176 if (map
->partition_to_view
)
1177 p
= map
->partition_to_view
[p
];
1182 fprintf(f
, "Partition %d (", x
);
1183 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1186 fprintf (f
, "%d ", y
);
1196 /* Output live range info LIVE to file F, controlled by FLAG. */
1199 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1203 var_map map
= live
->map
;
1206 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1210 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1211 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[bb
->index
], 0, i
, bi
)
1213 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1220 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1224 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1225 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
, bi
)
1227 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1235 #ifdef ENABLE_CHECKING
1236 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1239 register_ssa_partition_check (tree ssa_var
)
1241 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1242 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
1244 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1245 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1246 fprintf (stderr
, " in the SSA->Normal phase.\n");
1247 internal_error ("SSA corruption");
1252 /* Verify that the info in LIVE matches the current cfg. */
1255 verify_live_on_entry (tree_live_info_p live
)
1264 var_map map
= live
->map
;
1266 /* Check for live on entry partitions and report those with a DEF in
1267 the program. This will typically mean an optimization has done
1269 bb
= ENTRY_BLOCK_PTR
;
1271 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1273 int entry_block
= e
->dest
->index
;
1274 if (e
->dest
== EXIT_BLOCK_PTR
)
1276 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1281 var
= partition_to_var (map
, i
);
1282 stmt
= SSA_NAME_DEF_STMT (var
);
1283 tmp
= gimple_bb (stmt
);
1284 d
= gimple_default_def (cfun
, SSA_NAME_VAR (var
));
1286 loe
= live_on_entry (live
, e
->dest
);
1287 if (loe
&& bitmap_bit_p (loe
, i
))
1289 if (!gimple_nop_p (stmt
))
1292 print_generic_expr (stderr
, var
, TDF_SLIM
);
1293 fprintf (stderr
, " is defined ");
1295 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1296 fprintf (stderr
, "by:\n");
1297 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1298 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1300 fprintf (stderr
, " So it appears to have multiple defs.\n");
1307 print_generic_expr (stderr
, var
, TDF_SLIM
);
1308 fprintf (stderr
, " is live-on-entry to BB%d ",
1312 fprintf (stderr
, " but is not the default def of ");
1313 print_generic_expr (stderr
, d
, TDF_SLIM
);
1314 fprintf (stderr
, "\n");
1317 fprintf (stderr
, " and there is no default def.\n");
1324 /* The only way this var shouldn't be marked live on entry is
1325 if it occurs in a PHI argument of the block. */
1328 gimple_stmt_iterator gsi
;
1329 for (gsi
= gsi_start_phis (e
->dest
);
1330 !gsi_end_p (gsi
) && !ok
;
1333 gimple phi
= gsi_stmt (gsi
);
1334 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1335 if (var
== gimple_phi_arg_def (phi
, z
))
1344 print_generic_expr (stderr
, var
, TDF_SLIM
);
1345 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1347 fprintf (stderr
, "but it is a default def so it should be.\n");
1351 gcc_assert (num
<= 0);