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"
39 #ifdef ENABLE_CHECKING
40 static void verify_live_on_entry (tree_live_info_p
);
44 /* VARMAP maintains a mapping from SSA version number to real variables.
46 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
47 only member of it's own partition. Coalescing will attempt to group any
48 ssa_names which occur in a copy or in a PHI node into the same partition.
50 At the end of out-of-ssa, each partition becomes a "real" variable and is
51 rewritten as a compiler variable.
53 The var_map data structure is used to manage these partitions. It allows
54 partitions to be combined, and determines which partition belongs to what
55 ssa_name or variable, and vice versa. */
58 /* This routine will initialize the basevar fields of MAP. */
61 var_map_base_init (var_map map
)
68 num_part
= num_var_partitions (map
);
70 /* If a base table already exists, clear it, otherwise create it. */
71 if (map
->partition_to_base_index
!= NULL
)
73 free (map
->partition_to_base_index
);
74 VEC_truncate (tree
, map
->basevars
, 0);
77 map
->basevars
= VEC_alloc (tree
, heap
, MAX (40, (num_part
/ 10)));
79 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
81 /* Build the base variable list, and point partitions at their bases. */
82 for (x
= 0; x
< num_part
; x
++)
84 var
= partition_to_var (map
, x
);
85 if (TREE_CODE (var
) == SSA_NAME
)
86 var
= SSA_NAME_VAR (var
);
88 /* If base variable hasn't been seen, set it up. */
89 if (!ann
->base_var_processed
)
91 ann
->base_var_processed
= 1;
92 VAR_ANN_BASE_INDEX (ann
) = num
++;
93 VEC_safe_push (tree
, heap
, map
->basevars
, var
);
95 map
->partition_to_base_index
[x
] = VAR_ANN_BASE_INDEX (ann
);
98 map
->num_basevars
= num
;
100 /* Now clear the processed bit. */
101 for (x
= 0; x
< num
; x
++)
103 var
= VEC_index (tree
, map
->basevars
, x
);
104 var_ann (var
)->base_var_processed
= 0;
107 #ifdef ENABLE_CHECKING
108 for (x
= 0; x
< num_part
; x
++)
111 var
= SSA_NAME_VAR (partition_to_var (map
, x
));
112 var2
= VEC_index (tree
, map
->basevars
, basevar_index (map
, x
));
113 gcc_assert (var
== var2
);
119 /* Remove the base table in MAP. */
122 var_map_base_fini (var_map map
)
124 /* Free the basevar info if it is present. */
125 if (map
->partition_to_base_index
!= NULL
)
127 VEC_free (tree
, heap
, map
->basevars
);
128 free (map
->partition_to_base_index
);
129 map
->partition_to_base_index
= NULL
;
130 map
->num_basevars
= 0;
133 /* Create a variable partition map of SIZE, initialize and return it. */
136 init_var_map (int size
)
140 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
141 map
->var_partition
= partition_new (size
);
143 map
->partition_to_view
= NULL
;
144 map
->view_to_partition
= NULL
;
145 map
->num_partitions
= size
;
146 map
->partition_size
= size
;
147 map
->num_basevars
= 0;
148 map
->partition_to_base_index
= NULL
;
149 map
->basevars
= NULL
;
154 /* Free memory associated with MAP. */
157 delete_var_map (var_map map
)
159 var_map_base_fini (map
);
160 partition_delete (map
->var_partition
);
161 if (map
->partition_to_view
)
162 free (map
->partition_to_view
);
163 if (map
->view_to_partition
)
164 free (map
->view_to_partition
);
169 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
170 Returns the partition which represents the new partition. If the two
171 partitions cannot be combined, NO_PARTITION is returned. */
174 var_union (var_map map
, tree var1
, tree var2
)
178 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
179 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
181 /* This is independent of partition_to_view. If partition_to_view is
182 on, then whichever one of these partitions is absorbed will never have a
183 dereference into the partition_to_view array any more. */
185 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
186 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
188 gcc_assert (p1
!= NO_PARTITION
);
189 gcc_assert (p2
!= NO_PARTITION
);
194 p3
= partition_union (map
->var_partition
, p1
, p2
);
196 if (map
->partition_to_view
)
197 p3
= map
->partition_to_view
[p3
];
203 /* Compress the partition numbers in MAP such that they fall in the range
204 0..(num_partitions-1) instead of wherever they turned out during
205 the partitioning exercise. This removes any references to unused
206 partitions, thereby allowing bitmaps and other vectors to be much
209 This is implemented such that compaction doesn't affect partitioning.
210 Ie., once partitions are created and possibly merged, running one
211 or more different kind of compaction will not affect the partitions
212 themselves. Their index might change, but all the same variables will
213 still be members of the same partition group. This allows work on reduced
214 sets, and no loss of information when a larger set is later desired.
216 In particular, coalescing can work on partitions which have 2 or more
217 definitions, and then 'recompact' later to include all the single
218 definitions for assignment to program variables. */
221 /* Set MAP back to the initial state of having no partition view. Return a
222 bitmap which has a bit set for each partition number which is in use in the
226 partition_view_init (var_map map
)
232 used
= BITMAP_ALLOC (NULL
);
234 /* Already in a view? Abandon the old one. */
235 if (map
->partition_to_view
)
237 free (map
->partition_to_view
);
238 map
->partition_to_view
= NULL
;
240 if (map
->view_to_partition
)
242 free (map
->view_to_partition
);
243 map
->view_to_partition
= NULL
;
246 /* Find out which partitions are actually referenced. */
247 for (x
= 0; x
< map
->partition_size
; x
++)
249 tmp
= partition_find (map
->var_partition
, x
);
250 if (ssa_name (tmp
) != NULL_TREE
&& is_gimple_reg (ssa_name (tmp
))
251 && (!has_zero_uses (ssa_name (tmp
))
252 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
253 bitmap_set_bit (used
, tmp
);
256 map
->num_partitions
= map
->partition_size
;
261 /* This routine will finalize the view data for MAP based on the partitions
262 set in SELECTED. This is either the same bitmap returned from
263 partition_view_init, or a trimmed down version if some of those partitions
264 were not desired in this view. SELECTED is freed before returning. */
267 partition_view_fini (var_map map
, bitmap selected
)
270 unsigned count
, i
, x
, limit
;
272 gcc_assert (selected
);
274 count
= bitmap_count_bits (selected
);
275 limit
= map
->partition_size
;
277 /* If its a one-to-one ratio, we don't need any view compaction. */
280 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
281 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
282 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
285 /* Give each selected partition an index. */
286 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
288 map
->partition_to_view
[x
] = i
;
289 map
->view_to_partition
[i
] = x
;
292 gcc_assert (i
== count
);
293 map
->num_partitions
= i
;
296 BITMAP_FREE (selected
);
300 /* Create a partition view which includes all the used partitions in MAP. If
301 WANT_BASES is true, create the base variable map as well. */
304 partition_view_normal (var_map map
, bool want_bases
)
308 used
= partition_view_init (map
);
309 partition_view_fini (map
, used
);
312 var_map_base_init (map
);
314 var_map_base_fini (map
);
318 /* Create a partition view in MAP which includes just partitions which occur in
319 the bitmap ONLY. If WANT_BASES is true, create the base variable map
323 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
326 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
330 used
= partition_view_init (map
);
331 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
333 p
= partition_find (map
->var_partition
, x
);
334 gcc_assert (bitmap_bit_p (used
, p
));
335 bitmap_set_bit (new_partitions
, p
);
337 partition_view_fini (map
, new_partitions
);
341 var_map_base_init (map
);
343 var_map_base_fini (map
);
347 static inline void mark_all_vars_used (tree
*, void *data
);
349 /* Helper function for mark_all_vars_used, called via walk_tree. */
352 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data
)
355 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
358 if (TREE_CODE (t
) == SSA_NAME
)
359 t
= SSA_NAME_VAR (t
);
361 if (IS_EXPR_CODE_CLASS (c
)
362 && (b
= TREE_BLOCK (t
)) != NULL
)
363 TREE_USED (b
) = true;
365 /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
366 fields that do not contain vars. */
367 if (TREE_CODE (t
) == TARGET_MEM_REF
)
369 mark_all_vars_used (&TMR_SYMBOL (t
), data
);
370 mark_all_vars_used (&TMR_BASE (t
), data
);
371 mark_all_vars_used (&TMR_INDEX (t
), data
);
376 /* Only need to mark VAR_DECLS; parameters and return results are not
377 eliminated as unused. */
378 if (TREE_CODE (t
) == VAR_DECL
)
380 if (data
!= NULL
&& bitmap_bit_p ((bitmap
) data
, DECL_UID (t
)))
382 bitmap_clear_bit ((bitmap
) data
, DECL_UID (t
));
383 mark_all_vars_used (&DECL_INITIAL (t
), data
);
387 /* remove_unused_scope_block_p requires information about labels
388 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
389 if (TREE_CODE (t
) == LABEL_DECL
)
390 /* Although the TREE_USED values that the frontend uses would be
391 acceptable (albeit slightly over-conservative) for our purposes,
392 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
393 must re-compute it here. */
396 if (IS_TYPE_OR_DECL_P (t
))
402 /* Mark the scope block SCOPE and its subblocks unused when they can be
403 possibly eliminated if dead. */
406 mark_scope_block_unused (tree scope
)
409 TREE_USED (scope
) = false;
410 if (!(*debug_hooks
->ignore_block
) (scope
))
411 TREE_USED (scope
) = true;
412 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
413 mark_scope_block_unused (t
);
416 /* Look if the block is dead (by possibly eliminating its dead subblocks)
417 and return true if so.
418 Block is declared dead if:
419 1) No statements are associated with it.
420 2) Declares no live variables
421 3) All subblocks are dead
422 or there is precisely one subblocks and the block
423 has same abstract origin as outer block and declares
424 no variables, so it is pure wrapper.
425 When we are not outputting full debug info, we also eliminate dead variables
426 out of scope blocks to let them to be recycled by GGC and to save copying work
427 done by the inliner. */
430 remove_unused_scope_block_p (tree scope
)
433 bool unused
= !TREE_USED (scope
);
437 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
439 next
= &DECL_CHAIN (*t
);
441 /* Debug info of nested function refers to the block of the
442 function. We might stil call it even if all statements
443 of function it was nested into was elliminated.
445 TODO: We can actually look into cgraph to see if function
446 will be output to file. */
447 if (TREE_CODE (*t
) == FUNCTION_DECL
)
450 /* If a decl has a value expr, we need to instantiate it
451 regardless of debug info generation, to avoid codegen
452 differences in memory overlap tests. update_equiv_regs() may
453 indirectly call validate_equiv_mem() to test whether a
454 SET_DEST overlaps with others, and if the value expr changes
455 by virtual register instantiation, we may get end up with
456 different results. */
457 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
460 /* Remove everything we don't generate debug info for. */
461 else if (DECL_IGNORED_P (*t
))
463 *t
= DECL_CHAIN (*t
);
467 /* When we are outputting debug info, we usually want to output
468 info about optimized-out variables in the scope blocks.
469 Exception are the scope blocks not containing any instructions
470 at all so user can't get into the scopes at first place. */
471 else if ((ann
= var_ann (*t
)) != NULL
474 else if (TREE_CODE (*t
) == LABEL_DECL
&& TREE_USED (*t
))
475 /* For labels that are still used in the IL, the decision to
476 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
477 risk having different ordering in debug vs. non-debug builds
478 during inlining or versioning.
479 A label appearing here (we have already checked DECL_IGNORED_P)
480 should not be used in the IL unless it has been explicitly used
481 before, so we use TREE_USED as an approximation. */
482 /* In principle, we should do the same here as for the debug case
483 below, however, when debugging, there might be additional nested
484 levels that keep an upper level with a label live, so we have to
485 force this block to be considered used, too. */
488 /* When we are not doing full debug info, we however can keep around
489 only the used variables for cfgexpand's memory packing saving quite
492 For sake of -g3, we keep around those vars but we don't count this as
493 use of block, so innermost block with no used vars and no instructions
494 can be considered dead. We only want to keep around blocks user can
495 breakpoint into and ask about value of optimized out variables.
497 Similarly we need to keep around types at least until all variables of
498 all nested blocks are gone. We track no information on whether given
499 type is used or not. */
501 else if (debug_info_level
== DINFO_LEVEL_NORMAL
502 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
506 *t
= DECL_CHAIN (*t
);
511 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
512 if (remove_unused_scope_block_p (*t
))
514 if (BLOCK_SUBBLOCKS (*t
))
516 tree next
= BLOCK_CHAIN (*t
);
517 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
519 *t
= BLOCK_SUBBLOCKS (*t
);
520 while (BLOCK_CHAIN (*t
))
522 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
523 t
= &BLOCK_CHAIN (*t
);
525 BLOCK_CHAIN (*t
) = next
;
526 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
527 t
= &BLOCK_CHAIN (*t
);
531 *t
= BLOCK_CHAIN (*t
);
535 t
= &BLOCK_CHAIN (*t
);
542 /* Outer scope is always used. */
543 else if (!BLOCK_SUPERCONTEXT (scope
)
544 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
546 /* Innermost blocks with no live variables nor statements can be always
548 else if (!nsubblocks
)
550 /* For terse debug info we can eliminate info on unused variables. */
551 else if (debug_info_level
== DINFO_LEVEL_NONE
552 || debug_info_level
== DINFO_LEVEL_TERSE
)
554 /* Even for -g0/-g1 don't prune outer scopes from artificial
555 functions, otherwise diagnostics using tree_nonartificial_location
556 will not be emitted properly. */
557 if (inlined_function_outer_scope_p (scope
))
562 && TREE_CODE (ao
) == BLOCK
563 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
564 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
566 && TREE_CODE (ao
) == FUNCTION_DECL
567 && DECL_DECLARED_INLINE_P (ao
)
568 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
572 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
574 /* See if this block is important for representation of inlined function.
575 Inlined functions are always represented by block with
576 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
578 else if (inlined_function_outer_scope_p (scope
))
581 /* Verfify that only blocks with source location set
582 are entry points to the inlined functions. */
583 gcc_assert (BLOCK_SOURCE_LOCATION (scope
) == UNKNOWN_LOCATION
);
585 TREE_USED (scope
) = !unused
;
589 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
590 eliminated during the tree->rtl conversion process. */
593 mark_all_vars_used (tree
*expr_p
, void *data
)
595 walk_tree (expr_p
, mark_all_vars_used_1
, data
, NULL
);
599 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
600 indentation level and FLAGS is as in print_generic_expr. */
603 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
608 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
609 TREE_USED (scope
) ? "" : " (unused)",
610 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
611 if (BLOCK_SOURCE_LOCATION (scope
) != UNKNOWN_LOCATION
)
613 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
614 fprintf (file
, " %s:%i", s
.file
, s
.line
);
616 if (BLOCK_ABSTRACT_ORIGIN (scope
))
618 tree origin
= block_ultimate_origin (scope
);
621 fprintf (file
, " Originating from :");
623 print_generic_decl (file
, origin
, flags
);
625 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
628 fprintf (file
, " \n");
629 for (var
= BLOCK_VARS (scope
); var
; var
= DECL_CHAIN (var
))
634 if ((ann
= var_ann (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
;
692 bitmap global_unused_vars
= NULL
;
693 unsigned srcidx
, dstidx
, num
;
695 /* Removing declarations from lexical blocks when not optimizing is
696 not only a waste of time, it actually causes differences in stack
701 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
703 /* Assume all locals are unused. */
704 FOR_EACH_REFERENCED_VAR (t
, rvi
)
705 var_ann (t
)->used
= false;
707 /* Walk the CFG marking all referenced symbols. */
710 gimple_stmt_iterator gsi
;
715 /* Walk the statements. */
716 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
718 gimple stmt
= gsi_stmt (gsi
);
719 tree b
= gimple_block (stmt
);
721 if (is_gimple_debug (stmt
))
725 TREE_USED (b
) = true;
727 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
728 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
), NULL
);
731 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
736 gimple phi
= gsi_stmt (gsi
);
738 /* No point processing globals. */
739 if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi
))))
742 def
= gimple_phi_result (phi
);
743 mark_all_vars_used (&def
, NULL
);
745 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
747 tree arg
= USE_FROM_PTR (arg_p
);
748 mark_all_vars_used (&arg
, NULL
);
752 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
754 TREE_USED (e
->goto_block
) = true;
757 cfun
->has_local_explicit_reg_vars
= false;
759 /* Remove unmarked local vars from local_decls. */
760 num
= VEC_length (tree
, cfun
->local_decls
);
761 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
763 var
= VEC_index (tree
, cfun
->local_decls
, srcidx
);
764 if (TREE_CODE (var
) != FUNCTION_DECL
765 && (!(ann
= var_ann (var
))
768 if (is_global_var (var
))
770 if (global_unused_vars
== NULL
)
771 global_unused_vars
= BITMAP_ALLOC (NULL
);
772 bitmap_set_bit (global_unused_vars
, DECL_UID (var
));
777 else if (TREE_CODE (var
) == VAR_DECL
778 && DECL_HARD_REGISTER (var
)
779 && !is_global_var (var
))
780 cfun
->has_local_explicit_reg_vars
= true;
782 if (srcidx
!= dstidx
)
783 VEC_replace (tree
, cfun
->local_decls
, dstidx
, var
);
787 VEC_truncate (tree
, cfun
->local_decls
, dstidx
);
789 /* Remove unmarked global vars from local_decls. */
790 if (global_unused_vars
!= NULL
)
794 FOR_EACH_LOCAL_DECL (cfun
, ix
, var
)
795 if (TREE_CODE (var
) == VAR_DECL
796 && is_global_var (var
)
797 && (ann
= var_ann (var
)) != NULL
799 mark_all_vars_used (&DECL_INITIAL (var
), global_unused_vars
);
801 num
= VEC_length (tree
, cfun
->local_decls
);
802 for (srcidx
= 0, dstidx
= 0; srcidx
< num
; srcidx
++)
804 var
= VEC_index (tree
, cfun
->local_decls
, srcidx
);
805 if (TREE_CODE (var
) == VAR_DECL
806 && is_global_var (var
)
807 && bitmap_bit_p (global_unused_vars
, DECL_UID (var
)))
810 if (srcidx
!= dstidx
)
811 VEC_replace (tree
, cfun
->local_decls
, dstidx
, var
);
815 VEC_truncate (tree
, cfun
->local_decls
, dstidx
);
816 BITMAP_FREE (global_unused_vars
);
819 /* Remove unused variables from REFERENCED_VARs. As a special
820 exception keep the variables that are believed to be aliased.
821 Those can't be easily removed from the alias sets and operand
822 caches. They will be removed shortly after the next may_alias
823 pass is performed. */
824 FOR_EACH_REFERENCED_VAR (t
, rvi
)
825 if (!is_global_var (t
)
826 && TREE_CODE (t
) != PARM_DECL
827 && TREE_CODE (t
) != RESULT_DECL
828 && !(ann
= var_ann (t
))->used
830 && !TREE_ADDRESSABLE (t
))
831 remove_referenced_var (t
);
832 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
));
833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
835 fprintf (dump_file
, "Scope blocks after cleanups:\n");
836 dump_scope_blocks (dump_file
, dump_flags
);
841 /* Allocate and return a new live range information object base on MAP. */
843 static tree_live_info_p
844 new_tree_live_info (var_map map
)
846 tree_live_info_p live
;
849 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
851 live
->num_blocks
= last_basic_block
;
853 live
->livein
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
854 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
855 live
->livein
[x
] = BITMAP_ALLOC (NULL
);
857 live
->liveout
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
858 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
859 live
->liveout
[x
] = BITMAP_ALLOC (NULL
);
861 live
->work_stack
= XNEWVEC (int, last_basic_block
);
862 live
->stack_top
= live
->work_stack
;
864 live
->global
= BITMAP_ALLOC (NULL
);
869 /* Free storage for live range info object LIVE. */
872 delete_tree_live_info (tree_live_info_p live
)
876 BITMAP_FREE (live
->global
);
877 free (live
->work_stack
);
879 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
880 BITMAP_FREE (live
->liveout
[x
]);
881 free (live
->liveout
);
883 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
884 BITMAP_FREE (live
->livein
[x
]);
891 /* Visit basic block BB and propagate any required live on entry bits from
892 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
893 TMP is a temporary work bitmap which is passed in to avoid reallocating
897 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
905 gcc_assert (!TEST_BIT (visited
, bb
->index
));
907 SET_BIT (visited
, bb
->index
);
908 loe
= live_on_entry (live
, bb
);
910 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
913 if (pred_bb
== ENTRY_BLOCK_PTR
)
915 /* TMP is variables live-on-entry from BB that aren't defined in the
916 predecessor block. This should be the live on entry vars to pred.
917 Note that liveout is the DEFs in a block while live on entry is
919 bitmap_and_compl (tmp
, loe
, live
->liveout
[pred_bb
->index
]);
921 /* Add these bits to live-on-entry for the pred. if there are any
922 changes, and pred_bb has been visited already, add it to the
924 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
925 if (TEST_BIT (visited
, pred_bb
->index
) && change
)
927 RESET_BIT (visited
, pred_bb
->index
);
928 *(live
->stack_top
)++ = pred_bb
->index
;
934 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
935 of all the variables. */
938 live_worklist (tree_live_info_p live
)
942 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
943 bitmap tmp
= BITMAP_ALLOC (NULL
);
945 sbitmap_zero (visited
);
947 /* Visit all the blocks in reverse order and propagate live on entry values
948 into the predecessors blocks. */
949 FOR_EACH_BB_REVERSE (bb
)
950 loe_visit_block (live
, bb
, visited
, tmp
);
952 /* Process any blocks which require further iteration. */
953 while (live
->stack_top
!= live
->work_stack
)
955 b
= *--(live
->stack_top
);
956 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
960 sbitmap_free (visited
);
964 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
965 links. Set the live on entry fields in LIVE. Def's are marked temporarily
966 in the liveout vector. */
969 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
974 basic_block def_bb
= NULL
;
975 imm_use_iterator imm_iter
;
978 p
= var_to_partition (live
->map
, ssa_name
);
979 if (p
== NO_PARTITION
)
982 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
985 def_bb
= gimple_bb (stmt
);
986 /* Mark defs in liveout bitmap temporarily. */
988 bitmap_set_bit (live
->liveout
[def_bb
->index
], p
);
991 def_bb
= ENTRY_BLOCK_PTR
;
993 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
994 add it to the list of live on entry blocks. */
995 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
997 gimple use_stmt
= USE_STMT (use
);
998 basic_block add_block
= NULL
;
1000 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1002 /* Uses in PHI's are considered to be live at exit of the SRC block
1003 as this is where a copy would be inserted. Check to see if it is
1004 defined in that block, or whether its live on entry. */
1005 int index
= PHI_ARG_INDEX_FROM_USE (use
);
1006 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
1007 if (e
->src
!= ENTRY_BLOCK_PTR
)
1009 if (e
->src
!= def_bb
)
1013 else if (is_gimple_debug (use_stmt
))
1017 /* If its not defined in this block, its live on entry. */
1018 basic_block use_bb
= gimple_bb (use_stmt
);
1019 if (use_bb
!= def_bb
)
1023 /* If there was a live on entry use, set the bit. */
1027 bitmap_set_bit (live
->livein
[add_block
->index
], p
);
1031 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1032 on entry blocks between the def and all the uses. */
1034 bitmap_set_bit (live
->global
, p
);
1038 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1041 calculate_live_on_exit (tree_live_info_p liveinfo
)
1047 /* live on entry calculations used liveout vectors for defs, clear them. */
1049 bitmap_clear (liveinfo
->liveout
[bb
->index
]);
1051 /* Set all the live-on-exit bits for uses in PHIs. */
1054 gimple_stmt_iterator gsi
;
1057 /* Mark the PHI arguments which are live on exit to the pred block. */
1058 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1060 gimple phi
= gsi_stmt (gsi
);
1061 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1063 tree t
= PHI_ARG_DEF (phi
, i
);
1066 if (TREE_CODE (t
) != SSA_NAME
)
1069 p
= var_to_partition (liveinfo
->map
, t
);
1070 if (p
== NO_PARTITION
)
1072 e
= gimple_phi_arg_edge (phi
, i
);
1073 if (e
->src
!= ENTRY_BLOCK_PTR
)
1074 bitmap_set_bit (liveinfo
->liveout
[e
->src
->index
], p
);
1078 /* Add each successors live on entry to this bock live on exit. */
1079 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1080 if (e
->dest
!= EXIT_BLOCK_PTR
)
1081 bitmap_ior_into (liveinfo
->liveout
[bb
->index
],
1082 live_on_entry (liveinfo
, e
->dest
));
1087 /* Given partition map MAP, calculate all the live on entry bitmaps for
1088 each partition. Return a new live info object. */
1091 calculate_live_ranges (var_map map
)
1095 tree_live_info_p live
;
1097 live
= new_tree_live_info (map
);
1098 for (i
= 0; i
< num_var_partitions (map
); i
++)
1100 var
= partition_to_var (map
, i
);
1101 if (var
!= NULL_TREE
)
1102 set_var_live_on_entry (var
, live
);
1105 live_worklist (live
);
1107 #ifdef ENABLE_CHECKING
1108 verify_live_on_entry (live
);
1111 calculate_live_on_exit (live
);
1116 /* Output partition map MAP to file F. */
1119 dump_var_map (FILE *f
, var_map map
)
1125 fprintf (f
, "\nPartition map \n\n");
1127 for (x
= 0; x
< map
->num_partitions
; x
++)
1129 if (map
->view_to_partition
!= NULL
)
1130 p
= map
->view_to_partition
[x
];
1134 if (ssa_name (p
) == NULL_TREE
)
1138 for (y
= 1; y
< num_ssa_names
; y
++)
1140 p
= partition_find (map
->var_partition
, y
);
1141 if (map
->partition_to_view
)
1142 p
= map
->partition_to_view
[p
];
1147 fprintf(f
, "Partition %d (", x
);
1148 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1151 fprintf (f
, "%d ", y
);
1161 /* Output live range info LIVE to file F, controlled by FLAG. */
1164 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1168 var_map map
= live
->map
;
1171 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1175 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1176 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[bb
->index
], 0, i
, bi
)
1178 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1185 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1189 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1190 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
, bi
)
1192 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1200 struct GTY(()) numbered_tree_d
1205 typedef struct numbered_tree_d numbered_tree
;
1207 DEF_VEC_O (numbered_tree
);
1208 DEF_VEC_ALLOC_O (numbered_tree
, heap
);
1210 /* Compare two declarations references by their DECL_UID / sequence number.
1211 Called via qsort. */
1214 compare_decls_by_uid (const void *pa
, const void *pb
)
1216 const numbered_tree
*nt_a
= ((const numbered_tree
*)pa
);
1217 const numbered_tree
*nt_b
= ((const numbered_tree
*)pb
);
1219 if (DECL_UID (nt_a
->t
) != DECL_UID (nt_b
->t
))
1220 return DECL_UID (nt_a
->t
) - DECL_UID (nt_b
->t
);
1221 return nt_a
->num
- nt_b
->num
;
1224 /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls. */
1226 dump_enumerated_decls_push (tree
*tp
, int *walk_subtrees
, void *data
)
1228 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
1229 VEC (numbered_tree
, heap
) **list
= (VEC (numbered_tree
, heap
) **) &wi
->info
;
1235 nt
.num
= VEC_length (numbered_tree
, *list
);
1236 VEC_safe_push (numbered_tree
, heap
, *list
, &nt
);
1241 /* Find all the declarations used by the current function, sort them by uid,
1242 and emit the sorted list. Each declaration is tagged with a sequence
1243 number indicating when it was found during statement / tree walking,
1244 so that TDF_NOUID comparisons of anonymous declarations are still
1245 meaningful. Where a declaration was encountered more than once, we
1246 emit only the sequence number of the first encounter.
1247 FILE is the dump file where to output the list and FLAGS is as in
1248 print_generic_expr. */
1250 dump_enumerated_decls (FILE *file
, int flags
)
1253 struct walk_stmt_info wi
;
1254 VEC (numbered_tree
, heap
) *decl_list
= VEC_alloc (numbered_tree
, heap
, 40);
1256 wi
.info
= (void*) decl_list
;
1260 gimple_stmt_iterator gsi
;
1262 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1263 if (!is_gimple_debug (gsi_stmt (gsi
)))
1264 walk_gimple_stmt (&gsi
, NULL
, dump_enumerated_decls_push
, &wi
);
1266 decl_list
= (VEC (numbered_tree
, heap
) *) wi
.info
;
1267 qsort (VEC_address (numbered_tree
, decl_list
),
1268 VEC_length (numbered_tree
, decl_list
),
1269 sizeof (numbered_tree
), compare_decls_by_uid
);
1270 if (VEC_length (numbered_tree
, decl_list
))
1274 tree last
= NULL_TREE
;
1276 fprintf (file
, "Declarations used by %s, sorted by DECL_UID:\n",
1277 current_function_name ());
1278 for (ix
= 0; VEC_iterate (numbered_tree
, decl_list
, ix
, ntp
); ix
++)
1282 fprintf (file
, "%d: ", ntp
->num
);
1283 print_generic_decl (file
, ntp
->t
, flags
);
1284 fprintf (file
, "\n");
1288 VEC_free (numbered_tree
, heap
, decl_list
);
1291 #ifdef ENABLE_CHECKING
1292 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1295 register_ssa_partition_check (tree ssa_var
)
1297 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1298 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
1300 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1301 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1302 fprintf (stderr
, " in the SSA->Normal phase.\n");
1303 internal_error ("SSA corruption");
1308 /* Verify that the info in LIVE matches the current cfg. */
1311 verify_live_on_entry (tree_live_info_p live
)
1320 var_map map
= live
->map
;
1322 /* Check for live on entry partitions and report those with a DEF in
1323 the program. This will typically mean an optimization has done
1325 bb
= ENTRY_BLOCK_PTR
;
1327 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1329 int entry_block
= e
->dest
->index
;
1330 if (e
->dest
== EXIT_BLOCK_PTR
)
1332 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1337 var
= partition_to_var (map
, i
);
1338 stmt
= SSA_NAME_DEF_STMT (var
);
1339 tmp
= gimple_bb (stmt
);
1340 d
= gimple_default_def (cfun
, SSA_NAME_VAR (var
));
1342 loe
= live_on_entry (live
, e
->dest
);
1343 if (loe
&& bitmap_bit_p (loe
, i
))
1345 if (!gimple_nop_p (stmt
))
1348 print_generic_expr (stderr
, var
, TDF_SLIM
);
1349 fprintf (stderr
, " is defined ");
1351 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1352 fprintf (stderr
, "by:\n");
1353 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1354 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1356 fprintf (stderr
, " So it appears to have multiple defs.\n");
1363 print_generic_expr (stderr
, var
, TDF_SLIM
);
1364 fprintf (stderr
, " is live-on-entry to BB%d ",
1368 fprintf (stderr
, " but is not the default def of ");
1369 print_generic_expr (stderr
, d
, TDF_SLIM
);
1370 fprintf (stderr
, "\n");
1373 fprintf (stderr
, " and there is no default def.\n");
1380 /* The only way this var shouldn't be marked live on entry is
1381 if it occurs in a PHI argument of the block. */
1384 gimple_stmt_iterator gsi
;
1385 for (gsi
= gsi_start_phis (e
->dest
);
1386 !gsi_end_p (gsi
) && !ok
;
1389 gimple phi
= gsi_stmt (gsi
);
1390 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1391 if (var
== gimple_phi_arg_def (phi
, z
))
1400 print_generic_expr (stderr
, var
, TDF_SLIM
);
1401 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1403 fprintf (stderr
, "but it is a default def so it should be.\n");
1407 gcc_assert (num
<= 0);