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"
37 #ifdef ENABLE_CHECKING
38 static void verify_live_on_entry (tree_live_info_p
);
42 /* VARMAP maintains a mapping from SSA version number to real variables.
44 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
45 only member of it's own partition. Coalescing will attempt to group any
46 ssa_names which occur in a copy or in a PHI node into the same partition.
48 At the end of out-of-ssa, each partition becomes a "real" variable and is
49 rewritten as a compiler variable.
51 The var_map data structure is used to manage these partitions. It allows
52 partitions to be combined, and determines which partition belongs to what
53 ssa_name or variable, and vice versa. */
56 /* This routine will initialize the basevar fields of MAP. */
59 var_map_base_init (var_map map
)
66 num_part
= num_var_partitions (map
);
68 /* If a base table already exists, clear it, otherwise create it. */
69 if (map
->partition_to_base_index
!= NULL
)
71 free (map
->partition_to_base_index
);
72 VEC_truncate (tree
, map
->basevars
, 0);
75 map
->basevars
= VEC_alloc (tree
, heap
, MAX (40, (num_part
/ 10)));
77 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
79 /* Build the base variable list, and point partitions at their bases. */
80 for (x
= 0; x
< num_part
; x
++)
82 var
= partition_to_var (map
, x
);
83 if (TREE_CODE (var
) == SSA_NAME
)
84 var
= SSA_NAME_VAR (var
);
86 /* If base variable hasn't been seen, set it up. */
87 if (!ann
->base_var_processed
)
89 ann
->base_var_processed
= 1;
90 VAR_ANN_BASE_INDEX (ann
) = num
++;
91 VEC_safe_push (tree
, heap
, map
->basevars
, var
);
93 map
->partition_to_base_index
[x
] = VAR_ANN_BASE_INDEX (ann
);
96 map
->num_basevars
= num
;
98 /* Now clear the processed bit. */
99 for (x
= 0; x
< num
; x
++)
101 var
= VEC_index (tree
, map
->basevars
, x
);
102 var_ann (var
)->base_var_processed
= 0;
105 #ifdef ENABLE_CHECKING
106 for (x
= 0; x
< num_part
; x
++)
109 var
= SSA_NAME_VAR (partition_to_var (map
, x
));
110 var2
= VEC_index (tree
, map
->basevars
, basevar_index (map
, x
));
111 gcc_assert (var
== var2
);
117 /* Remove the base table in MAP. */
120 var_map_base_fini (var_map map
)
122 /* Free the basevar info if it is present. */
123 if (map
->partition_to_base_index
!= NULL
)
125 VEC_free (tree
, heap
, map
->basevars
);
126 free (map
->partition_to_base_index
);
127 map
->partition_to_base_index
= NULL
;
128 map
->num_basevars
= 0;
131 /* Create a variable partition map of SIZE, initialize and return it. */
134 init_var_map (int size
)
138 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
139 map
->var_partition
= partition_new (size
);
141 map
->partition_to_view
= NULL
;
142 map
->view_to_partition
= NULL
;
143 map
->num_partitions
= size
;
144 map
->partition_size
= size
;
145 map
->num_basevars
= 0;
146 map
->partition_to_base_index
= NULL
;
147 map
->basevars
= NULL
;
152 /* Free memory associated with MAP. */
155 delete_var_map (var_map map
)
157 var_map_base_fini (map
);
158 partition_delete (map
->var_partition
);
159 if (map
->partition_to_view
)
160 free (map
->partition_to_view
);
161 if (map
->view_to_partition
)
162 free (map
->view_to_partition
);
167 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
168 Returns the partition which represents the new partition. If the two
169 partitions cannot be combined, NO_PARTITION is returned. */
172 var_union (var_map map
, tree var1
, tree var2
)
176 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
177 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
179 /* This is independent of partition_to_view. If partition_to_view is
180 on, then whichever one of these partitions is absorbed will never have a
181 dereference into the partition_to_view array any more. */
183 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
184 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
186 gcc_assert (p1
!= NO_PARTITION
);
187 gcc_assert (p2
!= NO_PARTITION
);
192 p3
= partition_union (map
->var_partition
, p1
, p2
);
194 if (map
->partition_to_view
)
195 p3
= map
->partition_to_view
[p3
];
201 /* Compress the partition numbers in MAP such that they fall in the range
202 0..(num_partitions-1) instead of wherever they turned out during
203 the partitioning exercise. This removes any references to unused
204 partitions, thereby allowing bitmaps and other vectors to be much
207 This is implemented such that compaction doesn't affect partitioning.
208 Ie., once partitions are created and possibly merged, running one
209 or more different kind of compaction will not affect the partitions
210 themselves. Their index might change, but all the same variables will
211 still be members of the same partition group. This allows work on reduced
212 sets, and no loss of information when a larger set is later desired.
214 In particular, coalescing can work on partitions which have 2 or more
215 definitions, and then 'recompact' later to include all the single
216 definitions for assignment to program variables. */
219 /* Set MAP back to the initial state of having no partition view. Return a
220 bitmap which has a bit set for each partition number which is in use in the
224 partition_view_init (var_map map
)
230 used
= BITMAP_ALLOC (NULL
);
232 /* Already in a view? Abandon the old one. */
233 if (map
->partition_to_view
)
235 free (map
->partition_to_view
);
236 map
->partition_to_view
= NULL
;
238 if (map
->view_to_partition
)
240 free (map
->view_to_partition
);
241 map
->view_to_partition
= NULL
;
244 /* Find out which partitions are actually referenced. */
245 for (x
= 0; x
< map
->partition_size
; x
++)
247 tmp
= partition_find (map
->var_partition
, x
);
248 if (ssa_name (tmp
) != NULL_TREE
&& is_gimple_reg (ssa_name (tmp
))
249 && (!has_zero_uses (ssa_name (tmp
))
250 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
251 bitmap_set_bit (used
, tmp
);
254 map
->num_partitions
= map
->partition_size
;
259 /* This routine will finalize the view data for MAP based on the partitions
260 set in SELECTED. This is either the same bitmap returned from
261 partition_view_init, or a trimmed down version if some of those partitions
262 were not desired in this view. SELECTED is freed before returning. */
265 partition_view_fini (var_map map
, bitmap selected
)
268 unsigned count
, i
, x
, limit
;
270 gcc_assert (selected
);
272 count
= bitmap_count_bits (selected
);
273 limit
= map
->partition_size
;
275 /* If its a one-to-one ratio, we don't need any view compaction. */
278 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
279 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
280 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
283 /* Give each selected partition an index. */
284 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
286 map
->partition_to_view
[x
] = i
;
287 map
->view_to_partition
[i
] = x
;
290 gcc_assert (i
== count
);
291 map
->num_partitions
= i
;
294 BITMAP_FREE (selected
);
298 /* Create a partition view which includes all the used partitions in MAP. If
299 WANT_BASES is true, create the base variable map as well. */
302 partition_view_normal (var_map map
, bool want_bases
)
306 used
= partition_view_init (map
);
307 partition_view_fini (map
, used
);
310 var_map_base_init (map
);
312 var_map_base_fini (map
);
316 /* Create a partition view in MAP which includes just partitions which occur in
317 the bitmap ONLY. If WANT_BASES is true, create the base variable map
321 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
324 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
328 used
= partition_view_init (map
);
329 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
331 p
= partition_find (map
->var_partition
, x
);
332 gcc_assert (bitmap_bit_p (used
, p
));
333 bitmap_set_bit (new_partitions
, p
);
335 partition_view_fini (map
, new_partitions
);
339 var_map_base_init (map
);
341 var_map_base_fini (map
);
345 static inline void mark_all_vars_used (tree
*, void *data
);
347 /* Helper function for mark_all_vars_used, called via walk_tree. */
350 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *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 TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
364 fields that do not contain vars. */
365 if (TREE_CODE (t
) == TARGET_MEM_REF
)
367 mark_all_vars_used (&TMR_SYMBOL (t
), data
);
368 mark_all_vars_used (&TMR_BASE (t
), data
);
369 mark_all_vars_used (&TMR_INDEX (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 if (data
!= NULL
&& bitmap_bit_p ((bitmap
) data
, DECL_UID (t
)))
380 bitmap_clear_bit ((bitmap
) data
, DECL_UID (t
));
381 mark_all_vars_used (&DECL_INITIAL (t
), data
);
386 if (IS_TYPE_OR_DECL_P (t
))
392 /* Mark the scope block SCOPE and its subblocks unused when they can be
393 possibly eliminated if dead. */
396 mark_scope_block_unused (tree scope
)
399 TREE_USED (scope
) = false;
400 if (!(*debug_hooks
->ignore_block
) (scope
))
401 TREE_USED (scope
) = true;
402 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
403 mark_scope_block_unused (t
);
406 /* Look if the block is dead (by possibly eliminating its dead subblocks)
407 and return true if so.
408 Block is declared dead if:
409 1) No statements are associated with it.
410 2) Declares no live variables
411 3) All subblocks are dead
412 or there is precisely one subblocks and the block
413 has same abstract origin as outer block and declares
414 no variables, so it is pure wrapper.
415 When we are not outputting full debug info, we also eliminate dead variables
416 out of scope blocks to let them to be recycled by GGC and to save copying work
417 done by the inliner. */
420 remove_unused_scope_block_p (tree scope
)
423 bool unused
= !TREE_USED (scope
);
427 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
429 next
= &TREE_CHAIN (*t
);
431 /* Debug info of nested function refers to the block of the
432 function. We might stil call it even if all statements
433 of function it was nested into was elliminated.
435 TODO: We can actually look into cgraph to see if function
436 will be output to file. */
437 if (TREE_CODE (*t
) == FUNCTION_DECL
)
440 /* If a decl has a value expr, we need to instantiate it
441 regardless of debug info generation, to avoid codegen
442 differences in memory overlap tests. update_equiv_regs() may
443 indirectly call validate_equiv_mem() to test whether a
444 SET_DEST overlaps with others, and if the value expr changes
445 by virtual register instantiation, we may get end up with
446 different results. */
447 else if (TREE_CODE (*t
) == VAR_DECL
&& DECL_HAS_VALUE_EXPR_P (*t
))
450 /* Remove everything we don't generate debug info for. */
451 else if (DECL_IGNORED_P (*t
))
453 *t
= TREE_CHAIN (*t
);
457 /* When we are outputting debug info, we usually want to output
458 info about optimized-out variables in the scope blocks.
459 Exception are the scope blocks not containing any instructions
460 at all so user can't get into the scopes at first place. */
461 else if ((ann
= var_ann (*t
)) != NULL
465 /* When we are not doing full debug info, we however can keep around
466 only the used variables for cfgexpand's memory packing saving quite
469 For sake of -g3, we keep around those vars but we don't count this as
470 use of block, so innermost block with no used vars and no instructions
471 can be considered dead. We only want to keep around blocks user can
472 breakpoint into and ask about value of optimized out variables.
474 Similarly we need to keep around types at least until all variables of
475 all nested blocks are gone. We track no information on whether given
476 type is used or not. */
478 else if (debug_info_level
== DINFO_LEVEL_NORMAL
479 || debug_info_level
== DINFO_LEVEL_VERBOSE
)
483 *t
= TREE_CHAIN (*t
);
488 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
489 if (remove_unused_scope_block_p (*t
))
491 if (BLOCK_SUBBLOCKS (*t
))
493 tree next
= BLOCK_CHAIN (*t
);
494 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
496 *t
= BLOCK_SUBBLOCKS (*t
);
497 while (BLOCK_CHAIN (*t
))
499 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
500 t
= &BLOCK_CHAIN (*t
);
502 BLOCK_CHAIN (*t
) = next
;
503 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
504 t
= &BLOCK_CHAIN (*t
);
508 *t
= BLOCK_CHAIN (*t
);
512 t
= &BLOCK_CHAIN (*t
);
519 /* Outer scope is always used. */
520 else if (!BLOCK_SUPERCONTEXT (scope
)
521 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
523 /* Innermost blocks with no live variables nor statements can be always
525 else if (!nsubblocks
)
527 /* For terse debug info we can eliminate info on unused variables. */
528 else if (debug_info_level
== DINFO_LEVEL_NONE
529 || debug_info_level
== DINFO_LEVEL_TERSE
)
531 /* Even for -g0/-g1 don't prune outer scopes from artificial
532 functions, otherwise diagnostics using tree_nonartificial_location
533 will not be emitted properly. */
534 if (inlined_function_outer_scope_p (scope
))
539 && TREE_CODE (ao
) == BLOCK
540 && BLOCK_ABSTRACT_ORIGIN (ao
) != ao
)
541 ao
= BLOCK_ABSTRACT_ORIGIN (ao
);
543 && TREE_CODE (ao
) == FUNCTION_DECL
544 && DECL_DECLARED_INLINE_P (ao
)
545 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao
)))
549 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
551 /* See if this block is important for representation of inlined function.
552 Inlined functions are always represented by block with
553 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
555 else if (inlined_function_outer_scope_p (scope
))
558 /* Verfify that only blocks with source location set
559 are entry points to the inlined functions. */
560 gcc_assert (BLOCK_SOURCE_LOCATION (scope
) == UNKNOWN_LOCATION
);
562 TREE_USED (scope
) = !unused
;
566 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
567 eliminated during the tree->rtl conversion process. */
570 mark_all_vars_used (tree
*expr_p
, void *data
)
572 walk_tree (expr_p
, mark_all_vars_used_1
, data
, NULL
);
576 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
577 indentation level and FLAGS is as in print_generic_expr. */
580 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
585 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
586 TREE_USED (scope
) ? "" : " (unused)",
587 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
588 if (BLOCK_SOURCE_LOCATION (scope
) != UNKNOWN_LOCATION
)
590 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
591 fprintf (file
, " %s:%i", s
.file
, s
.line
);
593 if (BLOCK_ABSTRACT_ORIGIN (scope
))
595 tree origin
= block_ultimate_origin (scope
);
598 fprintf (file
, " Originating from :");
600 print_generic_decl (file
, origin
, flags
);
602 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
605 fprintf (file
, " \n");
606 for (var
= BLOCK_VARS (scope
); var
; var
= TREE_CHAIN (var
))
611 if ((ann
= var_ann (var
))
615 fprintf (file
, "%*s",indent
, "");
616 print_generic_decl (file
, var
, flags
);
617 fprintf (file
, "%s\n", used
? "" : " (unused)");
619 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
621 fprintf (file
, "%*s",indent
, "");
622 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
624 fprintf (file
, " (nonlocalized)\n");
626 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
627 dump_scope_block (file
, indent
+ 2, t
, flags
);
628 fprintf (file
, "\n%*s}\n",indent
, "");
631 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
632 is as in print_generic_expr. */
635 debug_scope_block (tree scope
, int flags
)
637 dump_scope_block (stderr
, 0, scope
, flags
);
641 /* Dump the tree of lexical scopes of current_function_decl to FILE.
642 FLAGS is as in print_generic_expr. */
645 dump_scope_blocks (FILE *file
, int flags
)
647 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
651 /* Dump the tree of lexical scopes of current_function_decl to stderr.
652 FLAGS is as in print_generic_expr. */
655 debug_scope_blocks (int flags
)
657 dump_scope_blocks (stderr
, flags
);
660 /* Remove local variables that are not referenced in the IL. */
663 remove_unused_locals (void)
667 referenced_var_iterator rvi
;
669 bitmap global_unused_vars
= NULL
;
672 /* Removing declarations from lexical blocks when not optimizing is
673 not only a waste of time, it actually causes differences in stack
678 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
680 /* Assume all locals are unused. */
681 FOR_EACH_REFERENCED_VAR (t
, rvi
)
682 var_ann (t
)->used
= false;
684 /* Walk the CFG marking all referenced symbols. */
687 gimple_stmt_iterator gsi
;
692 /* Walk the statements. */
693 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
695 gimple stmt
= gsi_stmt (gsi
);
696 tree b
= gimple_block (stmt
);
698 if (is_gimple_debug (stmt
))
702 TREE_USED (b
) = true;
704 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
705 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
), NULL
);
708 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
713 gimple phi
= gsi_stmt (gsi
);
715 /* No point processing globals. */
716 if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi
))))
719 def
= gimple_phi_result (phi
);
720 mark_all_vars_used (&def
, NULL
);
722 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
724 tree arg
= USE_FROM_PTR (arg_p
);
725 mark_all_vars_used (&arg
, NULL
);
729 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
731 TREE_USED (e
->goto_block
) = true;
734 cfun
->has_local_explicit_reg_vars
= false;
736 /* Remove unmarked local vars from local_decls. */
737 for (ix
= 0; VEC_iterate (tree
, cfun
->local_decls
, ix
, var
); )
739 if (TREE_CODE (var
) != FUNCTION_DECL
740 && (!(ann
= var_ann (var
))
743 if (is_global_var (var
))
745 if (global_unused_vars
== NULL
)
746 global_unused_vars
= BITMAP_ALLOC (NULL
);
747 bitmap_set_bit (global_unused_vars
, DECL_UID (var
));
751 VEC_unordered_remove (tree
, cfun
->local_decls
, ix
);
755 else if (TREE_CODE (var
) == VAR_DECL
756 && DECL_HARD_REGISTER (var
)
757 && !is_global_var (var
))
758 cfun
->has_local_explicit_reg_vars
= true;
763 /* Remove unmarked global vars from local_decls. */
764 if (global_unused_vars
!= NULL
)
768 FOR_EACH_LOCAL_DECL (cfun
, ix
, var
)
769 if (TREE_CODE (var
) == VAR_DECL
770 && is_global_var (var
)
771 && (ann
= var_ann (var
)) != NULL
773 mark_all_vars_used (&DECL_INITIAL (var
), global_unused_vars
);
775 for (ix
= 0; VEC_iterate (tree
, cfun
->local_decls
, ix
, var
); )
776 if (TREE_CODE (var
) == VAR_DECL
777 && is_global_var (var
)
778 && bitmap_bit_p (global_unused_vars
, DECL_UID (var
)))
779 VEC_unordered_remove (tree
, cfun
->local_decls
, ix
);
782 BITMAP_FREE (global_unused_vars
);
785 /* Remove unused variables from REFERENCED_VARs. As a special
786 exception keep the variables that are believed to be aliased.
787 Those can't be easily removed from the alias sets and operand
788 caches. They will be removed shortly after the next may_alias
789 pass is performed. */
790 FOR_EACH_REFERENCED_VAR (t
, rvi
)
791 if (!is_global_var (t
)
792 && TREE_CODE (t
) != PARM_DECL
793 && TREE_CODE (t
) != RESULT_DECL
794 && !(ann
= var_ann (t
))->used
796 && !TREE_ADDRESSABLE (t
))
797 remove_referenced_var (t
);
798 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
));
799 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
801 fprintf (dump_file
, "Scope blocks after cleanups:\n");
802 dump_scope_blocks (dump_file
, dump_flags
);
807 /* Allocate and return a new live range information object base on MAP. */
809 static tree_live_info_p
810 new_tree_live_info (var_map map
)
812 tree_live_info_p live
;
815 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
817 live
->num_blocks
= last_basic_block
;
819 live
->livein
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
820 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
821 live
->livein
[x
] = BITMAP_ALLOC (NULL
);
823 live
->liveout
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
824 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
825 live
->liveout
[x
] = BITMAP_ALLOC (NULL
);
827 live
->work_stack
= XNEWVEC (int, last_basic_block
);
828 live
->stack_top
= live
->work_stack
;
830 live
->global
= BITMAP_ALLOC (NULL
);
835 /* Free storage for live range info object LIVE. */
838 delete_tree_live_info (tree_live_info_p live
)
842 BITMAP_FREE (live
->global
);
843 free (live
->work_stack
);
845 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
846 BITMAP_FREE (live
->liveout
[x
]);
847 free (live
->liveout
);
849 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
850 BITMAP_FREE (live
->livein
[x
]);
857 /* Visit basic block BB and propagate any required live on entry bits from
858 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
859 TMP is a temporary work bitmap which is passed in to avoid reallocating
863 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
871 gcc_assert (!TEST_BIT (visited
, bb
->index
));
873 SET_BIT (visited
, bb
->index
);
874 loe
= live_on_entry (live
, bb
);
876 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
879 if (pred_bb
== ENTRY_BLOCK_PTR
)
881 /* TMP is variables live-on-entry from BB that aren't defined in the
882 predecessor block. This should be the live on entry vars to pred.
883 Note that liveout is the DEFs in a block while live on entry is
885 bitmap_and_compl (tmp
, loe
, live
->liveout
[pred_bb
->index
]);
887 /* Add these bits to live-on-entry for the pred. if there are any
888 changes, and pred_bb has been visited already, add it to the
890 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
891 if (TEST_BIT (visited
, pred_bb
->index
) && change
)
893 RESET_BIT (visited
, pred_bb
->index
);
894 *(live
->stack_top
)++ = pred_bb
->index
;
900 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
901 of all the variables. */
904 live_worklist (tree_live_info_p live
)
908 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
909 bitmap tmp
= BITMAP_ALLOC (NULL
);
911 sbitmap_zero (visited
);
913 /* Visit all the blocks in reverse order and propagate live on entry values
914 into the predecessors blocks. */
915 FOR_EACH_BB_REVERSE (bb
)
916 loe_visit_block (live
, bb
, visited
, tmp
);
918 /* Process any blocks which require further iteration. */
919 while (live
->stack_top
!= live
->work_stack
)
921 b
= *--(live
->stack_top
);
922 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
926 sbitmap_free (visited
);
930 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
931 links. Set the live on entry fields in LIVE. Def's are marked temporarily
932 in the liveout vector. */
935 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
940 basic_block def_bb
= NULL
;
941 imm_use_iterator imm_iter
;
944 p
= var_to_partition (live
->map
, ssa_name
);
945 if (p
== NO_PARTITION
)
948 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
951 def_bb
= gimple_bb (stmt
);
952 /* Mark defs in liveout bitmap temporarily. */
954 bitmap_set_bit (live
->liveout
[def_bb
->index
], p
);
957 def_bb
= ENTRY_BLOCK_PTR
;
959 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
960 add it to the list of live on entry blocks. */
961 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
963 gimple use_stmt
= USE_STMT (use
);
964 basic_block add_block
= NULL
;
966 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
968 /* Uses in PHI's are considered to be live at exit of the SRC block
969 as this is where a copy would be inserted. Check to see if it is
970 defined in that block, or whether its live on entry. */
971 int index
= PHI_ARG_INDEX_FROM_USE (use
);
972 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
973 if (e
->src
!= ENTRY_BLOCK_PTR
)
975 if (e
->src
!= def_bb
)
979 else if (is_gimple_debug (use_stmt
))
983 /* If its not defined in this block, its live on entry. */
984 basic_block use_bb
= gimple_bb (use_stmt
);
985 if (use_bb
!= def_bb
)
989 /* If there was a live on entry use, set the bit. */
993 bitmap_set_bit (live
->livein
[add_block
->index
], p
);
997 /* If SSA_NAME is live on entry to at least one block, fill in all the live
998 on entry blocks between the def and all the uses. */
1000 bitmap_set_bit (live
->global
, p
);
1004 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1007 calculate_live_on_exit (tree_live_info_p liveinfo
)
1013 /* live on entry calculations used liveout vectors for defs, clear them. */
1015 bitmap_clear (liveinfo
->liveout
[bb
->index
]);
1017 /* Set all the live-on-exit bits for uses in PHIs. */
1020 gimple_stmt_iterator gsi
;
1023 /* Mark the PHI arguments which are live on exit to the pred block. */
1024 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1026 gimple phi
= gsi_stmt (gsi
);
1027 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1029 tree t
= PHI_ARG_DEF (phi
, i
);
1032 if (TREE_CODE (t
) != SSA_NAME
)
1035 p
= var_to_partition (liveinfo
->map
, t
);
1036 if (p
== NO_PARTITION
)
1038 e
= gimple_phi_arg_edge (phi
, i
);
1039 if (e
->src
!= ENTRY_BLOCK_PTR
)
1040 bitmap_set_bit (liveinfo
->liveout
[e
->src
->index
], p
);
1044 /* Add each successors live on entry to this bock live on exit. */
1045 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1046 if (e
->dest
!= EXIT_BLOCK_PTR
)
1047 bitmap_ior_into (liveinfo
->liveout
[bb
->index
],
1048 live_on_entry (liveinfo
, e
->dest
));
1053 /* Given partition map MAP, calculate all the live on entry bitmaps for
1054 each partition. Return a new live info object. */
1057 calculate_live_ranges (var_map map
)
1061 tree_live_info_p live
;
1063 live
= new_tree_live_info (map
);
1064 for (i
= 0; i
< num_var_partitions (map
); i
++)
1066 var
= partition_to_var (map
, i
);
1067 if (var
!= NULL_TREE
)
1068 set_var_live_on_entry (var
, live
);
1071 live_worklist (live
);
1073 #ifdef ENABLE_CHECKING
1074 verify_live_on_entry (live
);
1077 calculate_live_on_exit (live
);
1082 /* Output partition map MAP to file F. */
1085 dump_var_map (FILE *f
, var_map map
)
1091 fprintf (f
, "\nPartition map \n\n");
1093 for (x
= 0; x
< map
->num_partitions
; x
++)
1095 if (map
->view_to_partition
!= NULL
)
1096 p
= map
->view_to_partition
[x
];
1100 if (ssa_name (p
) == NULL_TREE
)
1104 for (y
= 1; y
< num_ssa_names
; y
++)
1106 p
= partition_find (map
->var_partition
, y
);
1107 if (map
->partition_to_view
)
1108 p
= map
->partition_to_view
[p
];
1113 fprintf(f
, "Partition %d (", x
);
1114 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1117 fprintf (f
, "%d ", y
);
1127 /* Output live range info LIVE to file F, controlled by FLAG. */
1130 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1134 var_map map
= live
->map
;
1137 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1141 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1142 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[bb
->index
], 0, i
, bi
)
1144 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1151 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1155 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1156 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
, bi
)
1158 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1167 #ifdef ENABLE_CHECKING
1168 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1171 register_ssa_partition_check (tree ssa_var
)
1173 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1174 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
1176 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1177 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1178 fprintf (stderr
, " in the SSA->Normal phase.\n");
1179 internal_error ("SSA corruption");
1184 /* Verify that the info in LIVE matches the current cfg. */
1187 verify_live_on_entry (tree_live_info_p live
)
1196 var_map map
= live
->map
;
1198 /* Check for live on entry partitions and report those with a DEF in
1199 the program. This will typically mean an optimization has done
1201 bb
= ENTRY_BLOCK_PTR
;
1203 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1205 int entry_block
= e
->dest
->index
;
1206 if (e
->dest
== EXIT_BLOCK_PTR
)
1208 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1213 var
= partition_to_var (map
, i
);
1214 stmt
= SSA_NAME_DEF_STMT (var
);
1215 tmp
= gimple_bb (stmt
);
1216 d
= gimple_default_def (cfun
, SSA_NAME_VAR (var
));
1218 loe
= live_on_entry (live
, e
->dest
);
1219 if (loe
&& bitmap_bit_p (loe
, i
))
1221 if (!gimple_nop_p (stmt
))
1224 print_generic_expr (stderr
, var
, TDF_SLIM
);
1225 fprintf (stderr
, " is defined ");
1227 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1228 fprintf (stderr
, "by:\n");
1229 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1230 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1232 fprintf (stderr
, " So it appears to have multiple defs.\n");
1239 print_generic_expr (stderr
, var
, TDF_SLIM
);
1240 fprintf (stderr
, " is live-on-entry to BB%d ",
1244 fprintf (stderr
, " but is not the default def of ");
1245 print_generic_expr (stderr
, d
, TDF_SLIM
);
1246 fprintf (stderr
, "\n");
1249 fprintf (stderr
, " and there is no default def.\n");
1256 /* The only way this var shouldn't be marked live on entry is
1257 if it occurs in a PHI argument of the block. */
1260 gimple_stmt_iterator gsi
;
1261 for (gsi
= gsi_start_phis (e
->dest
);
1262 !gsi_end_p (gsi
) && !ok
;
1265 gimple phi
= gsi_stmt (gsi
);
1266 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1267 if (var
== gimple_phi_arg_def (phi
, z
))
1276 print_generic_expr (stderr
, var
, TDF_SLIM
);
1277 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1279 fprintf (stderr
, "but it is a default def so it should be.\n");
1283 gcc_assert (num
<= 0);