1 /* Liveness for SSA trees.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
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 if (map
->partition_to_view
)
161 free (map
->partition_to_view
);
162 if (map
->view_to_partition
)
163 free (map
->view_to_partition
);
168 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
169 Returns the partition which represents the new partition. If the two
170 partitions cannot be combined, NO_PARTITION is returned. */
173 var_union (var_map map
, tree var1
, tree var2
)
177 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
178 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
180 /* This is independent of partition_to_view. If partition_to_view is
181 on, then whichever one of these partitions is absorbed will never have a
182 dereference into the partition_to_view array any more. */
184 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
185 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
187 gcc_assert (p1
!= NO_PARTITION
);
188 gcc_assert (p2
!= NO_PARTITION
);
193 p3
= partition_union (map
->var_partition
, p1
, p2
);
195 if (map
->partition_to_view
)
196 p3
= map
->partition_to_view
[p3
];
202 /* Compress the partition numbers in MAP such that they fall in the range
203 0..(num_partitions-1) instead of wherever they turned out during
204 the partitioning exercise. This removes any references to unused
205 partitions, thereby allowing bitmaps and other vectors to be much
208 This is implemented such that compaction doesn't affect partitioning.
209 Ie., once partitions are created and possibly merged, running one
210 or more different kind of compaction will not affect the partitions
211 themselves. Their index might change, but all the same variables will
212 still be members of the same partition group. This allows work on reduced
213 sets, and no loss of information when a larger set is later desired.
215 In particular, coalescing can work on partitions which have 2 or more
216 definitions, and then 'recompact' later to include all the single
217 definitions for assignment to program variables. */
220 /* Set MAP back to the initial state of having no partition view. Return a
221 bitmap which has a bit set for each partition number which is in use in the
225 partition_view_init (var_map map
)
231 used
= BITMAP_ALLOC (NULL
);
233 /* Already in a view? Abandon the old one. */
234 if (map
->partition_to_view
)
236 free (map
->partition_to_view
);
237 map
->partition_to_view
= NULL
;
239 if (map
->view_to_partition
)
241 free (map
->view_to_partition
);
242 map
->view_to_partition
= NULL
;
245 /* Find out which partitions are actually referenced. */
246 for (x
= 0; x
< map
->partition_size
; x
++)
248 tmp
= partition_find (map
->var_partition
, x
);
249 if (ssa_name (tmp
) != NULL_TREE
&& is_gimple_reg (ssa_name (tmp
))
250 && (!has_zero_uses (ssa_name (tmp
))
251 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
252 bitmap_set_bit (used
, tmp
);
255 map
->num_partitions
= map
->partition_size
;
260 /* This routine will finalize the view data for MAP based on the partitions
261 set in SELECTED. This is either the same bitmap returned from
262 partition_view_init, or a trimmed down version if some of those partitions
263 were not desired in this view. SELECTED is freed before returning. */
266 partition_view_fini (var_map map
, bitmap selected
)
269 unsigned count
, i
, x
, limit
;
271 gcc_assert (selected
);
273 count
= bitmap_count_bits (selected
);
274 limit
= map
->partition_size
;
276 /* If its a one-to-one ratio, we don't need any view compaction. */
279 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
280 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
281 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
284 /* Give each selected partition an index. */
285 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
287 map
->partition_to_view
[x
] = i
;
288 map
->view_to_partition
[i
] = x
;
291 gcc_assert (i
== count
);
292 map
->num_partitions
= i
;
295 BITMAP_FREE (selected
);
299 /* Create a partition view which includes all the used partitions in MAP. If
300 WANT_BASES is true, create the base variable map as well. */
303 partition_view_normal (var_map map
, bool want_bases
)
307 used
= partition_view_init (map
);
308 partition_view_fini (map
, used
);
311 var_map_base_init (map
);
313 var_map_base_fini (map
);
317 /* Create a partition view in MAP which includes just partitions which occur in
318 the bitmap ONLY. If WANT_BASES is true, create the base variable map
322 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
325 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
329 used
= partition_view_init (map
);
330 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
332 p
= partition_find (map
->var_partition
, x
);
333 gcc_assert (bitmap_bit_p (used
, p
));
334 bitmap_set_bit (new_partitions
, p
);
336 partition_view_fini (map
, new_partitions
);
340 var_map_base_init (map
);
342 var_map_base_fini (map
);
346 static inline void mark_all_vars_used (tree
*, void *data
);
348 /* Helper function for mark_all_vars_used, called via walk_tree. */
351 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data
)
354 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
357 if (TREE_CODE (t
) == SSA_NAME
)
358 t
= SSA_NAME_VAR (t
);
360 if (IS_EXPR_CODE_CLASS (c
)
361 && (b
= TREE_BLOCK (t
)) != NULL
)
362 TREE_USED (b
) = true;
364 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
365 fields do not contain vars. */
366 if (TREE_CODE (t
) == TARGET_MEM_REF
)
368 mark_all_vars_used (&TMR_BASE (t
), data
);
369 mark_all_vars_used (&TMR_INDEX (t
), data
);
370 mark_all_vars_used (&TMR_INDEX2 (t
), data
);
375 /* Only need to mark VAR_DECLS; parameters and return results are not
376 eliminated as unused. */
377 if (TREE_CODE (t
) == VAR_DECL
)
379 if (data
!= NULL
&& bitmap_clear_bit ((bitmap
) data
, DECL_UID (t
)))
380 mark_all_vars_used (&DECL_INITIAL (t
), data
);
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
);
433 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
435 next
= &DECL_CHAIN (*t
);
437 /* Debug info of nested function refers to the block of the
438 function. We might stil call it even if all statements
439 of function it was nested into was elliminated.
441 TODO: We can actually look into cgraph to see if function
442 will be output to file. */
443 if (TREE_CODE (*t
) == FUNCTION_DECL
)
446 /* If a decl has a value expr, we need to instantiate it
447 regardless of debug info generation, to avoid codegen
448 differences in memory overlap tests. update_equiv_regs() may
449 indirectly call validate_equiv_mem() to test whether a
450 SET_DEST overlaps with others, and if the value expr changes
451 by virtual register instantiation, we may get end up with
452 different results. */
453 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
456 /* Remove everything we don't generate debug info for. */
457 else if (DECL_IGNORED_P (*t
))
459 *t
= DECL_CHAIN (*t
);
463 /* When we are outputting debug info, we usually want to output
464 info about optimized-out variables in the scope blocks.
465 Exception are the scope blocks not containing any instructions
466 at all so user can't get into the scopes at first place. */
467 else if ((ann
= var_ann (*t
)) != NULL
470 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
471 /* For labels that are still used in the IL, the decision to
472 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
473 risk having different ordering in debug vs. non-debug builds
474 during inlining or versioning.
475 A label appearing here (we have already checked DECL_IGNORED_P)
476 should not be used in the IL unless it has been explicitly used
477 before, so we use TREE_USED as an approximation. */
478 /* In principle, we should do the same here as for the debug case
479 below, however, when debugging, there might be additional nested
480 levels that keep an upper level with a label live, so we have to
481 force this block to be considered used, too. */
484 /* When we are not doing full debug info, we however can keep around
485 only the used variables for cfgexpand's memory packing saving quite
488 For sake of -g3, we keep around those vars but we don't count this as
489 use of block, so innermost block with no used vars and no instructions
490 can be considered dead. We only want to keep around blocks user can
491 breakpoint into and ask about value of optimized out variables.
493 Similarly we need to keep around types at least until all variables of
494 all nested blocks are gone. We track no information on whether given
495 type is used or not. */
497 else if (debug_info_level
== DINFO_LEVEL_NORMAL
498 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
502 *t
= DECL_CHAIN (*t
);
507 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
508 if (remove_unused_scope_block_p (*t
))
510 if (BLOCK_SUBBLOCKS (*t
))
512 tree next
= BLOCK_CHAIN (*t
);
513 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
515 *t
= BLOCK_SUBBLOCKS (*t
);
516 while (BLOCK_CHAIN (*t
))
518 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
519 t
= &BLOCK_CHAIN (*t
);
521 BLOCK_CHAIN (*t
) = next
;
522 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
523 t
= &BLOCK_CHAIN (*t
);
527 *t
= BLOCK_CHAIN (*t
);
531 t
= &BLOCK_CHAIN (*t
);
538 /* Outer scope is always used. */
539 else if (!BLOCK_SUPERCONTEXT (scope
)
540 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
542 /* Innermost blocks with no live variables nor statements can be always
544 else if (!nsubblocks
)
546 /* For terse debug info we can eliminate info on unused variables. */
547 else if (debug_info_level
== DINFO_LEVEL_NONE
548 || debug_info_level
== DINFO_LEVEL_TERSE
)
550 /* Even for -g0/-g1 don't prune outer scopes from artificial
551 functions, otherwise diagnostics using tree_nonartificial_location
552 will not be emitted properly. */
553 if (inlined_function_outer_scope_p (scope
))
558 && TREE_CODE (ao
) == BLOCK
559 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
560 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
562 && TREE_CODE (ao
) == FUNCTION_DECL
563 && DECL_DECLARED_INLINE_P (ao
)
564 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
568 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
570 /* See if this block is important for representation of inlined function.
571 Inlined functions are always represented by block with
572 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
574 else if (inlined_function_outer_scope_p (scope
))
577 /* Verfify that only blocks with source location set
578 are entry points to the inlined functions. */
579 gcc_assert (BLOCK_SOURCE_LOCATION (scope
) == UNKNOWN_LOCATION
);
581 TREE_USED (scope
) = !unused
;
585 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
586 eliminated during the tree->rtl conversion process. */
589 mark_all_vars_used (tree
*expr_p
, void *data
)
591 walk_tree (expr_p
, mark_all_vars_used_1
, data
, NULL
);
595 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
596 indentation level and FLAGS is as in print_generic_expr. */
599 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
604 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
605 TREE_USED (scope
) ? "" : " (unused)",
606 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
607 if (BLOCK_SOURCE_LOCATION (scope
) != UNKNOWN_LOCATION
)
609 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
610 fprintf (file
, " %s:%i", s
.file
, s
.line
);
612 if (BLOCK_ABSTRACT_ORIGIN (scope
))
614 tree origin
= block_ultimate_origin (scope
);
617 fprintf (file
, " Originating from :");
619 print_generic_decl (file
, origin
, flags
);
621 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
624 fprintf (file
, " \n");
625 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
630 if ((ann
= var_ann (var
))
634 fprintf (file
, "%*s",indent
, "");
635 print_generic_decl (file
, var
, flags
);
636 fprintf (file
, "%s\n", used
? "" : " (unused)");
638 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
640 fprintf (file
, "%*s",indent
, "");
641 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
643 fprintf (file
, " (nonlocalized)\n");
645 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
646 dump_scope_block (file
, indent
+ 2, t
, flags
);
647 fprintf (file
, "\n%*s}\n",indent
, "");
650 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
651 is as in print_generic_expr. */
654 debug_scope_block (tree scope
, int flags
)
656 dump_scope_block (stderr
, 0, scope
, flags
);
660 /* Dump the tree of lexical scopes of current_function_decl to FILE.
661 FLAGS is as in print_generic_expr. */
664 dump_scope_blocks (FILE *file
, int flags
)
666 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
670 /* Dump the tree of lexical scopes of current_function_decl to stderr.
671 FLAGS is as in print_generic_expr. */
674 debug_scope_blocks (int flags
)
676 dump_scope_blocks (stderr
, flags
);
679 /* Remove local variables that are not referenced in the IL. */
682 remove_unused_locals (void)
686 referenced_var_iterator rvi
;
688 bitmap global_unused_vars
= NULL
;
689 unsigned srcidx
, dstidx
, num
;
691 /* Removing declarations from lexical blocks when not optimizing is
692 not only a waste of time, it actually causes differences in stack
697 timevar_push (TV_REMOVE_UNUSED
);
699 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
701 /* Assume all locals are unused. */
702 FOR_EACH_REFERENCED_VAR (t
, rvi
)
703 var_ann (t
)->used
= false;
705 /* Walk the CFG marking all referenced symbols. */
708 gimple_stmt_iterator gsi
;
713 /* Walk the statements. */
714 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
716 gimple stmt
= gsi_stmt (gsi
);
717 tree b
= gimple_block (stmt
);
719 if (is_gimple_debug (stmt
))
723 TREE_USED (b
) = true;
725 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
726 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
), NULL
);
729 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
734 gimple phi
= gsi_stmt (gsi
);
736 /* No point processing globals. */
737 if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi
))))
740 def
= gimple_phi_result (phi
);
741 mark_all_vars_used (&def
, NULL
);
743 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
745 tree arg
= USE_FROM_PTR (arg_p
);
746 mark_all_vars_used (&arg
, NULL
);
750 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
752 TREE_USED (e
->goto_block
) = true;
755 cfun
->has_local_explicit_reg_vars
= false;
757 /* Remove unmarked local vars from local_decls. */
758 num
= VEC_length (tree
, cfun
->local_decls
);
759 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
761 var
= VEC_index (tree
, cfun
->local_decls
, srcidx
);
762 if (TREE_CODE (var
) != FUNCTION_DECL
763 && (!(ann
= var_ann (var
))
766 if (is_global_var (var
))
768 if (global_unused_vars
== NULL
)
769 global_unused_vars
= BITMAP_ALLOC (NULL
);
770 bitmap_set_bit (global_unused_vars
, DECL_UID (var
));
775 else if (TREE_CODE (var
) == VAR_DECL
776 && DECL_HARD_REGISTER (var
)
777 && !is_global_var (var
))
778 cfun
->has_local_explicit_reg_vars
= true;
780 if (srcidx
!= dstidx
)
781 VEC_replace (tree
, cfun
->local_decls
, dstidx
, var
);
785 VEC_truncate (tree
, cfun
->local_decls
, dstidx
);
787 /* Remove unmarked global vars from local_decls. */
788 if (global_unused_vars
!= NULL
)
792 FOR_EACH_LOCAL_DECL (cfun
, ix
, var
)
793 if (TREE_CODE (var
) == VAR_DECL
794 && is_global_var (var
)
795 && (ann
= var_ann (var
)) != NULL
797 mark_all_vars_used (&DECL_INITIAL (var
), global_unused_vars
);
799 num
= VEC_length (tree
, cfun
->local_decls
);
800 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
802 var
= VEC_index (tree
, cfun
->local_decls
, srcidx
);
803 if (TREE_CODE (var
) == VAR_DECL
804 && is_global_var (var
)
805 && bitmap_bit_p (global_unused_vars
, DECL_UID (var
)))
808 if (srcidx
!= dstidx
)
809 VEC_replace (tree
, cfun
->local_decls
, dstidx
, var
);
813 VEC_truncate (tree
, cfun
->local_decls
, dstidx
);
814 BITMAP_FREE (global_unused_vars
);
817 /* Remove unused variables from REFERENCED_VARs. */
818 FOR_EACH_REFERENCED_VAR (t
, rvi
)
819 if (!is_global_var (t
)
820 && TREE_CODE (t
) != PARM_DECL
821 && TREE_CODE (t
) != RESULT_DECL
822 && !(ann
= var_ann (t
))->used
824 remove_referenced_var (t
);
825 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
));
826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
828 fprintf (dump_file
, "Scope blocks after cleanups:\n");
829 dump_scope_blocks (dump_file
, dump_flags
);
832 timevar_pop (TV_REMOVE_UNUSED
);
836 /* Allocate and return a new live range information object base on MAP. */
838 static tree_live_info_p
839 new_tree_live_info (var_map map
)
841 tree_live_info_p live
;
844 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
846 live
->num_blocks
= last_basic_block
;
848 live
->livein
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
849 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
850 live
->livein
[x
] = BITMAP_ALLOC (NULL
);
852 live
->liveout
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
853 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
854 live
->liveout
[x
] = BITMAP_ALLOC (NULL
);
856 live
->work_stack
= XNEWVEC (int, last_basic_block
);
857 live
->stack_top
= live
->work_stack
;
859 live
->global
= BITMAP_ALLOC (NULL
);
864 /* Free storage for live range info object LIVE. */
867 delete_tree_live_info (tree_live_info_p live
)
871 BITMAP_FREE (live
->global
);
872 free (live
->work_stack
);
874 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
875 BITMAP_FREE (live
->liveout
[x
]);
876 free (live
->liveout
);
878 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
879 BITMAP_FREE (live
->livein
[x
]);
886 /* Visit basic block BB and propagate any required live on entry bits from
887 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
888 TMP is a temporary work bitmap which is passed in to avoid reallocating
892 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
900 gcc_assert (!TEST_BIT (visited
, bb
->index
));
902 SET_BIT (visited
, bb
->index
);
903 loe
= live_on_entry (live
, bb
);
905 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
908 if (pred_bb
== ENTRY_BLOCK_PTR
)
910 /* TMP is variables live-on-entry from BB that aren't defined in the
911 predecessor block. This should be the live on entry vars to pred.
912 Note that liveout is the DEFs in a block while live on entry is
914 bitmap_and_compl (tmp
, loe
, live
->liveout
[pred_bb
->index
]);
916 /* Add these bits to live-on-entry for the pred. if there are any
917 changes, and pred_bb has been visited already, add it to the
919 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
920 if (TEST_BIT (visited
, pred_bb
->index
) && change
)
922 RESET_BIT (visited
, pred_bb
->index
);
923 *(live
->stack_top
)++ = pred_bb
->index
;
929 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
930 of all the variables. */
933 live_worklist (tree_live_info_p live
)
937 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
938 bitmap tmp
= BITMAP_ALLOC (NULL
);
940 sbitmap_zero (visited
);
942 /* Visit all the blocks in reverse order and propagate live on entry values
943 into the predecessors blocks. */
944 FOR_EACH_BB_REVERSE (bb
)
945 loe_visit_block (live
, bb
, visited
, tmp
);
947 /* Process any blocks which require further iteration. */
948 while (live
->stack_top
!= live
->work_stack
)
950 b
= *--(live
->stack_top
);
951 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
955 sbitmap_free (visited
);
959 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
960 links. Set the live on entry fields in LIVE. Def's are marked temporarily
961 in the liveout vector. */
964 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
969 basic_block def_bb
= NULL
;
970 imm_use_iterator imm_iter
;
973 p
= var_to_partition (live
->map
, ssa_name
);
974 if (p
== NO_PARTITION
)
977 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
980 def_bb
= gimple_bb (stmt
);
981 /* Mark defs in liveout bitmap temporarily. */
983 bitmap_set_bit (live
->liveout
[def_bb
->index
], p
);
986 def_bb
= ENTRY_BLOCK_PTR
;
988 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
989 add it to the list of live on entry blocks. */
990 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
992 gimple use_stmt
= USE_STMT (use
);
993 basic_block add_block
= NULL
;
995 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
997 /* Uses in PHI's are considered to be live at exit of the SRC block
998 as this is where a copy would be inserted. Check to see if it is
999 defined in that block, or whether its live on entry. */
1000 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1001 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
1002 if (e
->src
!= ENTRY_BLOCK_PTR
)
1004 if (e
->src
!= def_bb
)
1008 else if (is_gimple_debug (use_stmt
))
1012 /* If its not defined in this block, its live on entry. */
1013 basic_block use_bb
= gimple_bb (use_stmt
);
1014 if (use_bb
!= def_bb
)
1018 /* If there was a live on entry use, set the bit. */
1022 bitmap_set_bit (live
->livein
[add_block
->index
], p
);
1026 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1027 on entry blocks between the def and all the uses. */
1029 bitmap_set_bit (live
->global
, p
);
1033 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1036 calculate_live_on_exit (tree_live_info_p liveinfo
)
1042 /* live on entry calculations used liveout vectors for defs, clear them. */
1044 bitmap_clear (liveinfo
->liveout
[bb
->index
]);
1046 /* Set all the live-on-exit bits for uses in PHIs. */
1049 gimple_stmt_iterator gsi
;
1052 /* Mark the PHI arguments which are live on exit to the pred block. */
1053 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1055 gimple phi
= gsi_stmt (gsi
);
1056 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1058 tree t
= PHI_ARG_DEF (phi
, i
);
1061 if (TREE_CODE (t
) != SSA_NAME
)
1064 p
= var_to_partition (liveinfo
->map
, t
);
1065 if (p
== NO_PARTITION
)
1067 e
= gimple_phi_arg_edge (phi
, i
);
1068 if (e
->src
!= ENTRY_BLOCK_PTR
)
1069 bitmap_set_bit (liveinfo
->liveout
[e
->src
->index
], p
);
1073 /* Add each successors live on entry to this bock live on exit. */
1074 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1075 if (e
->dest
!= EXIT_BLOCK_PTR
)
1076 bitmap_ior_into (liveinfo
->liveout
[bb
->index
],
1077 live_on_entry (liveinfo
, e
->dest
));
1082 /* Given partition map MAP, calculate all the live on entry bitmaps for
1083 each partition. Return a new live info object. */
1086 calculate_live_ranges (var_map map
)
1090 tree_live_info_p live
;
1092 live
= new_tree_live_info (map
);
1093 for (i
= 0; i
< num_var_partitions (map
); i
++)
1095 var
= partition_to_var (map
, i
);
1096 if (var
!= NULL_TREE
)
1097 set_var_live_on_entry (var
, live
);
1100 live_worklist (live
);
1102 #ifdef ENABLE_CHECKING
1103 verify_live_on_entry (live
);
1106 calculate_live_on_exit (live
);
1111 /* Output partition map MAP to file F. */
1114 dump_var_map (FILE *f
, var_map map
)
1120 fprintf (f
, "\nPartition map \n\n");
1122 for (x
= 0; x
< map
->num_partitions
; x
++)
1124 if (map
->view_to_partition
!= NULL
)
1125 p
= map
->view_to_partition
[x
];
1129 if (ssa_name (p
) == NULL_TREE
)
1133 for (y
= 1; y
< num_ssa_names
; y
++)
1135 p
= partition_find (map
->var_partition
, y
);
1136 if (map
->partition_to_view
)
1137 p
= map
->partition_to_view
[p
];
1142 fprintf(f
, "Partition %d (", x
);
1143 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1146 fprintf (f
, "%d ", y
);
1156 /* Output live range info LIVE to file F, controlled by FLAG. */
1159 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1163 var_map map
= live
->map
;
1166 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1170 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1171 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[bb
->index
], 0, i
, bi
)
1173 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1180 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1184 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1185 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
, bi
)
1187 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1195 struct GTY(()) numbered_tree_d
1200 typedef struct numbered_tree_d numbered_tree
;
1202 DEF_VEC_O (numbered_tree
);
1203 DEF_VEC_ALLOC_O (numbered_tree
, heap
);
1205 /* Compare two declarations references by their DECL_UID / sequence number.
1206 Called via qsort. */
1209 compare_decls_by_uid (const void *pa
, const void *pb
)
1211 const numbered_tree
*nt_a
= ((const numbered_tree
*)pa
);
1212 const numbered_tree
*nt_b
= ((const numbered_tree
*)pb
);
1214 if (DECL_UID (nt_a
->t
) != DECL_UID (nt_b
->t
))
1215 return DECL_UID (nt_a
->t
) - DECL_UID (nt_b
->t
);
1216 return nt_a
->num
- nt_b
->num
;
1219 /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls. */
1221 dump_enumerated_decls_push (tree
*tp
, int *walk_subtrees
, void *data
)
1223 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
1224 VEC (numbered_tree
, heap
) **list
= (VEC (numbered_tree
, heap
) **) &wi
->info
;
1230 nt
.num
= VEC_length (numbered_tree
, *list
);
1231 VEC_safe_push (numbered_tree
, heap
, *list
, &nt
);
1236 /* Find all the declarations used by the current function, sort them by uid,
1237 and emit the sorted list. Each declaration is tagged with a sequence
1238 number indicating when it was found during statement / tree walking,
1239 so that TDF_NOUID comparisons of anonymous declarations are still
1240 meaningful. Where a declaration was encountered more than once, we
1241 emit only the sequence number of the first encounter.
1242 FILE is the dump file where to output the list and FLAGS is as in
1243 print_generic_expr. */
1245 dump_enumerated_decls (FILE *file
, int flags
)
1248 struct walk_stmt_info wi
;
1249 VEC (numbered_tree
, heap
) *decl_list
= VEC_alloc (numbered_tree
, heap
, 40);
1251 memset (&wi
, '\0', sizeof (wi
));
1252 wi
.info
= (void*) decl_list
;
1255 gimple_stmt_iterator gsi
;
1257 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1258 if (!is_gimple_debug (gsi_stmt (gsi
)))
1259 walk_gimple_stmt (&gsi
, NULL
, dump_enumerated_decls_push
, &wi
);
1261 decl_list
= (VEC (numbered_tree
, heap
) *) wi
.info
;
1262 VEC_qsort (numbered_tree
, decl_list
, compare_decls_by_uid
);
1263 if (VEC_length (numbered_tree
, decl_list
))
1267 tree last
= NULL_TREE
;
1269 fprintf (file
, "Declarations used by %s, sorted by DECL_UID:\n",
1270 current_function_name ());
1271 FOR_EACH_VEC_ELT (numbered_tree
, decl_list
, ix
, ntp
)
1275 fprintf (file
, "%d: ", ntp
->num
);
1276 print_generic_decl (file
, ntp
->t
, flags
);
1277 fprintf (file
, "\n");
1281 VEC_free (numbered_tree
, heap
, decl_list
);
1284 #ifdef ENABLE_CHECKING
1285 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1288 register_ssa_partition_check (tree ssa_var
)
1290 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1291 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
1293 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1294 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1295 fprintf (stderr
, " in the SSA->Normal phase.\n");
1296 internal_error ("SSA corruption");
1301 /* Verify that the info in LIVE matches the current cfg. */
1304 verify_live_on_entry (tree_live_info_p live
)
1313 var_map map
= live
->map
;
1315 /* Check for live on entry partitions and report those with a DEF in
1316 the program. This will typically mean an optimization has done
1318 bb
= ENTRY_BLOCK_PTR
;
1320 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1322 int entry_block
= e
->dest
->index
;
1323 if (e
->dest
== EXIT_BLOCK_PTR
)
1325 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1330 var
= partition_to_var (map
, i
);
1331 stmt
= SSA_NAME_DEF_STMT (var
);
1332 tmp
= gimple_bb (stmt
);
1333 d
= gimple_default_def (cfun
, SSA_NAME_VAR (var
));
1335 loe
= live_on_entry (live
, e
->dest
);
1336 if (loe
&& bitmap_bit_p (loe
, i
))
1338 if (!gimple_nop_p (stmt
))
1341 print_generic_expr (stderr
, var
, TDF_SLIM
);
1342 fprintf (stderr
, " is defined ");
1344 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1345 fprintf (stderr
, "by:\n");
1346 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1347 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1349 fprintf (stderr
, " So it appears to have multiple defs.\n");
1356 print_generic_expr (stderr
, var
, TDF_SLIM
);
1357 fprintf (stderr
, " is live-on-entry to BB%d ",
1361 fprintf (stderr
, " but is not the default def of ");
1362 print_generic_expr (stderr
, d
, TDF_SLIM
);
1363 fprintf (stderr
, "\n");
1366 fprintf (stderr
, " and there is no default def.\n");
1373 /* The only way this var shouldn't be marked live on entry is
1374 if it occurs in a PHI argument of the block. */
1377 gimple_stmt_iterator gsi
;
1378 for (gsi
= gsi_start_phis (e
->dest
);
1379 !gsi_end_p (gsi
) && !ok
;
1382 gimple phi
= gsi_stmt (gsi
);
1383 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1384 if (var
== gimple_phi_arg_def (phi
, z
))
1393 print_generic_expr (stderr
, var
, TDF_SLIM
);
1394 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1396 fprintf (stderr
, "but it is a default def so it should be.\n");
1400 gcc_assert (num
<= 0);