1 /* Liveness for SSA trees.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009 Free Software Foundation,
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 "diagnostic.h"
29 #include "tree-flow.h"
30 #include "tree-dump.h"
31 #include "tree-ssa-live.h"
36 #ifdef ENABLE_CHECKING
37 static void verify_live_on_entry (tree_live_info_p
);
41 /* VARMAP maintains a mapping from SSA version number to real variables.
43 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
44 only member of it's own partition. Coalescing will attempt to group any
45 ssa_names which occur in a copy or in a PHI node into the same partition.
47 At the end of out-of-ssa, each partition becomes a "real" variable and is
48 rewritten as a compiler variable.
50 The var_map data structure is used to manage these partitions. It allows
51 partitions to be combined, and determines which partition belongs to what
52 ssa_name or variable, and vice versa. */
55 /* This routine will initialize the basevar fields of MAP. */
58 var_map_base_init (var_map map
)
65 num_part
= num_var_partitions (map
);
67 /* If a base table already exists, clear it, otherwise create it. */
68 if (map
->partition_to_base_index
!= NULL
)
70 free (map
->partition_to_base_index
);
71 VEC_truncate (tree
, map
->basevars
, 0);
74 map
->basevars
= VEC_alloc (tree
, heap
, MAX (40, (num_part
/ 10)));
76 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
78 /* Build the base variable list, and point partitions at their bases. */
79 for (x
= 0; x
< num_part
; x
++)
81 var
= partition_to_var (map
, x
);
82 if (TREE_CODE (var
) == SSA_NAME
)
83 var
= SSA_NAME_VAR (var
);
85 /* If base variable hasn't been seen, set it up. */
86 if (!ann
->base_var_processed
)
88 ann
->base_var_processed
= 1;
89 VAR_ANN_BASE_INDEX (ann
) = num
++;
90 VEC_safe_push (tree
, heap
, map
->basevars
, var
);
92 map
->partition_to_base_index
[x
] = VAR_ANN_BASE_INDEX (ann
);
95 map
->num_basevars
= num
;
97 /* Now clear the processed bit. */
98 for (x
= 0; x
< num
; x
++)
100 var
= VEC_index (tree
, map
->basevars
, x
);
101 var_ann (var
)->base_var_processed
= 0;
104 #ifdef ENABLE_CHECKING
105 for (x
= 0; x
< num_part
; x
++)
108 var
= SSA_NAME_VAR (partition_to_var (map
, x
));
109 var2
= VEC_index (tree
, map
->basevars
, basevar_index (map
, x
));
110 gcc_assert (var
== var2
);
116 /* Remove the base table in MAP. */
119 var_map_base_fini (var_map map
)
121 /* Free the basevar info if it is present. */
122 if (map
->partition_to_base_index
!= NULL
)
124 VEC_free (tree
, heap
, map
->basevars
);
125 free (map
->partition_to_base_index
);
126 map
->partition_to_base_index
= NULL
;
127 map
->num_basevars
= 0;
130 /* Create a variable partition map of SIZE, initialize and return it. */
133 init_var_map (int size
)
137 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
138 map
->var_partition
= partition_new (size
);
140 map
->partition_to_view
= NULL
;
141 map
->view_to_partition
= NULL
;
142 map
->num_partitions
= size
;
143 map
->partition_size
= size
;
144 map
->num_basevars
= 0;
145 map
->partition_to_base_index
= NULL
;
146 map
->basevars
= NULL
;
151 /* Free memory associated with MAP. */
154 delete_var_map (var_map map
)
156 var_map_base_fini (map
);
157 partition_delete (map
->var_partition
);
158 if (map
->partition_to_view
)
159 free (map
->partition_to_view
);
160 if (map
->view_to_partition
)
161 free (map
->view_to_partition
);
166 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
167 Returns the partition which represents the new partition. If the two
168 partitions cannot be combined, NO_PARTITION is returned. */
171 var_union (var_map map
, tree var1
, tree var2
)
175 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
176 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
178 /* This is independent of partition_to_view. If partition_to_view is
179 on, then whichever one of these partitions is absorbed will never have a
180 dereference into the partition_to_view array any more. */
182 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
183 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
185 gcc_assert (p1
!= NO_PARTITION
);
186 gcc_assert (p2
!= NO_PARTITION
);
191 p3
= partition_union (map
->var_partition
, p1
, p2
);
193 if (map
->partition_to_view
)
194 p3
= map
->partition_to_view
[p3
];
200 /* Compress the partition numbers in MAP such that they fall in the range
201 0..(num_partitions-1) instead of wherever they turned out during
202 the partitioning exercise. This removes any references to unused
203 partitions, thereby allowing bitmaps and other vectors to be much
206 This is implemented such that compaction doesn't affect partitioning.
207 Ie., once partitions are created and possibly merged, running one
208 or more different kind of compaction will not affect the partitions
209 themselves. Their index might change, but all the same variables will
210 still be members of the same partition group. This allows work on reduced
211 sets, and no loss of information when a larger set is later desired.
213 In particular, coalescing can work on partitions which have 2 or more
214 definitions, and then 'recompact' later to include all the single
215 definitions for assignment to program variables. */
218 /* Set MAP back to the initial state of having no partition view. Return a
219 bitmap which has a bit set for each partition number which is in use in the
223 partition_view_init (var_map map
)
229 used
= BITMAP_ALLOC (NULL
);
231 /* Already in a view? Abandon the old one. */
232 if (map
->partition_to_view
)
234 free (map
->partition_to_view
);
235 map
->partition_to_view
= NULL
;
237 if (map
->view_to_partition
)
239 free (map
->view_to_partition
);
240 map
->view_to_partition
= NULL
;
243 /* Find out which partitions are actually referenced. */
244 for (x
= 0; x
< map
->partition_size
; x
++)
246 tmp
= partition_find (map
->var_partition
, x
);
247 if (ssa_name (tmp
) != NULL_TREE
&& is_gimple_reg (ssa_name (tmp
))
248 && (!has_zero_uses (ssa_name (tmp
))
249 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp
))))
250 bitmap_set_bit (used
, tmp
);
253 map
->num_partitions
= map
->partition_size
;
258 /* This routine will finalize the view data for MAP based on the partitions
259 set in SELECTED. This is either the same bitmap returned from
260 partition_view_init, or a trimmed down version if some of those partitions
261 were not desired in this view. SELECTED is freed before returning. */
264 partition_view_fini (var_map map
, bitmap selected
)
267 unsigned count
, i
, x
, limit
;
269 gcc_assert (selected
);
271 count
= bitmap_count_bits (selected
);
272 limit
= map
->partition_size
;
274 /* If its a one-to-one ratio, we don't need any view compaction. */
277 map
->partition_to_view
= (int *)xmalloc (limit
* sizeof (int));
278 memset (map
->partition_to_view
, 0xff, (limit
* sizeof (int)));
279 map
->view_to_partition
= (int *)xmalloc (count
* sizeof (int));
282 /* Give each selected partition an index. */
283 EXECUTE_IF_SET_IN_BITMAP (selected
, 0, x
, bi
)
285 map
->partition_to_view
[x
] = i
;
286 map
->view_to_partition
[i
] = x
;
289 gcc_assert (i
== count
);
290 map
->num_partitions
= i
;
293 BITMAP_FREE (selected
);
297 /* Create a partition view which includes all the used partitions in MAP. If
298 WANT_BASES is true, create the base variable map as well. */
301 partition_view_normal (var_map map
, bool want_bases
)
305 used
= partition_view_init (map
);
306 partition_view_fini (map
, used
);
309 var_map_base_init (map
);
311 var_map_base_fini (map
);
315 /* Create a partition view in MAP which includes just partitions which occur in
316 the bitmap ONLY. If WANT_BASES is true, create the base variable map
320 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
323 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
327 used
= partition_view_init (map
);
328 EXECUTE_IF_SET_IN_BITMAP (only
, 0, x
, bi
)
330 p
= partition_find (map
->var_partition
, x
);
331 gcc_assert (bitmap_bit_p (used
, p
));
332 bitmap_set_bit (new_partitions
, p
);
334 partition_view_fini (map
, new_partitions
);
338 var_map_base_init (map
);
340 var_map_base_fini (map
);
344 static inline void mark_all_vars_used (tree
*, void *data
);
346 /* Helper function for mark_all_vars_used, called via walk_tree. */
349 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
, void *data
)
352 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
355 if (TREE_CODE (t
) == SSA_NAME
)
356 t
= SSA_NAME_VAR (t
);
358 if (IS_EXPR_CODE_CLASS (c
)
359 && (b
= TREE_BLOCK (t
)) != NULL
)
360 TREE_USED (b
) = true;
362 /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
363 fields that do not contain vars. */
364 if (TREE_CODE (t
) == TARGET_MEM_REF
)
366 mark_all_vars_used (&TMR_SYMBOL (t
), data
);
367 mark_all_vars_used (&TMR_BASE (t
), data
);
368 mark_all_vars_used (&TMR_INDEX (t
), data
);
373 /* Only need to mark VAR_DECLS; parameters and return results are not
374 eliminated as unused. */
375 if (TREE_CODE (t
) == VAR_DECL
)
377 if (data
!= NULL
&& bitmap_bit_p ((bitmap
) data
, DECL_UID (t
)))
379 bitmap_clear_bit ((bitmap
) data
, DECL_UID (t
));
380 mark_all_vars_used (&DECL_INITIAL (t
), data
);
385 if (IS_TYPE_OR_DECL_P (t
))
391 /* Mark the scope block SCOPE and its subblocks unused when they can be
392 possibly eliminated if dead. */
395 mark_scope_block_unused (tree scope
)
398 TREE_USED (scope
) = false;
399 if (!(*debug_hooks
->ignore_block
) (scope
))
400 TREE_USED (scope
) = true;
401 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
402 mark_scope_block_unused (t
);
405 /* Look if the block is dead (by possibly eliminating its dead subblocks)
406 and return true if so.
407 Block is declared dead if:
408 1) No statements are associated with it.
409 2) Declares no live variables
410 3) All subblocks are dead
411 or there is precisely one subblocks and the block
412 has same abstract origin as outer block and declares
413 no variables, so it is pure wrapper.
414 When we are not outputting full debug info, we also eliminate dead variables
415 out of scope blocks to let them to be recycled by GGC and to save copying work
416 done by the inliner. */
419 remove_unused_scope_block_p (tree scope
)
422 bool unused
= !TREE_USED (scope
);
426 for (t
= &BLOCK_VARS (scope
); *t
; t
= next
)
428 next
= &TREE_CHAIN (*t
);
430 /* Debug info of nested function refers to the block of the
431 function. We might stil call it even if all statements
432 of function it was nested into was elliminated.
434 TODO: We can actually look into cgraph to see if function
435 will be output to file. */
436 if (TREE_CODE (*t
) == FUNCTION_DECL
)
438 /* Remove everything we don't generate debug info for. */
439 else if (DECL_IGNORED_P (*t
))
441 *t
= TREE_CHAIN (*t
);
445 /* When we are outputting debug info, we usually want to output
446 info about optimized-out variables in the scope blocks.
447 Exception are the scope blocks not containing any instructions
448 at all so user can't get into the scopes at first place. */
449 else if ((ann
= var_ann (*t
)) != NULL
453 /* When we are not doing full debug info, we however can keep around
454 only the used variables for cfgexpand's memory packing saving quite
457 For sake of -g3, we keep around those vars but we don't count this as
458 use of block, so innermost block with no used vars and no instructions
459 can be considered dead. We only want to keep around blocks user can
460 breakpoint into and ask about value of optimized out variables.
462 Similarly we need to keep around types at least until all variables of
463 all nested blocks are gone. We track no information on whether given
464 type is used or not. */
466 else if (debug_info_level
== DINFO_LEVEL_NORMAL
467 || debug_info_level
== DINFO_LEVEL_VERBOSE
468 /* Removing declarations before inlining is going to affect
469 DECL_UID that in turn is going to affect hashtables and
471 || !cfun
->after_inlining
)
475 *t
= TREE_CHAIN (*t
);
480 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
481 if (remove_unused_scope_block_p (*t
))
483 if (BLOCK_SUBBLOCKS (*t
))
485 tree next
= BLOCK_CHAIN (*t
);
486 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
488 *t
= BLOCK_SUBBLOCKS (*t
);
489 while (BLOCK_CHAIN (*t
))
491 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
492 t
= &BLOCK_CHAIN (*t
);
494 BLOCK_CHAIN (*t
) = next
;
495 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
496 t
= &BLOCK_CHAIN (*t
);
500 *t
= BLOCK_CHAIN (*t
);
504 t
= &BLOCK_CHAIN (*t
);
511 /* Outer scope is always used. */
512 else if (!BLOCK_SUPERCONTEXT (scope
)
513 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
515 /* Innermost blocks with no live variables nor statements can be always
517 else if (!nsubblocks
)
519 /* If there are live subblocks and we still have some unused variables
520 or types declared, we must keep them.
521 Before inliing we must not depend on debug info verbosity to keep
523 else if (!cfun
->after_inlining
&& BLOCK_VARS (scope
))
525 /* For terse debug info we can eliminate info on unused variables. */
526 else if (debug_info_level
== DINFO_LEVEL_NONE
527 || debug_info_level
== DINFO_LEVEL_TERSE
)
529 else if (BLOCK_VARS (scope
) || BLOCK_NUM_NONLOCALIZED_VARS (scope
))
531 /* See if this block is important for representation of inlined function.
532 Inlined functions are always represented by block with
533 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
535 else if (inlined_function_outer_scope_p (scope
))
538 /* Verfify that only blocks with source location set
539 are entry points to the inlined functions. */
540 gcc_assert (BLOCK_SOURCE_LOCATION (scope
) == UNKNOWN_LOCATION
);
542 TREE_USED (scope
) = !unused
;
546 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
547 eliminated during the tree->rtl conversion process. */
550 mark_all_vars_used (tree
*expr_p
, void *data
)
552 walk_tree (expr_p
, mark_all_vars_used_1
, data
, NULL
);
556 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
557 indentation level and FLAGS is as in print_generic_expr. */
560 dump_scope_block (FILE *file
, int indent
, tree scope
, int flags
)
565 fprintf (file
, "\n%*s{ Scope block #%i%s%s",indent
, "" , BLOCK_NUMBER (scope
),
566 TREE_USED (scope
) ? "" : " (unused)",
567 BLOCK_ABSTRACT (scope
) ? " (abstract)": "");
568 if (BLOCK_SOURCE_LOCATION (scope
) != UNKNOWN_LOCATION
)
570 expanded_location s
= expand_location (BLOCK_SOURCE_LOCATION (scope
));
571 fprintf (file
, " %s:%i", s
.file
, s
.line
);
573 if (BLOCK_ABSTRACT_ORIGIN (scope
))
575 tree origin
= block_ultimate_origin (scope
);
578 fprintf (file
, " Originating from :");
580 print_generic_decl (file
, origin
, flags
);
582 fprintf (file
, "#%i", BLOCK_NUMBER (origin
));
585 fprintf (file
, " \n");
586 for (var
= BLOCK_VARS (scope
); var
; var
= TREE_CHAIN (var
))
591 if ((ann
= var_ann (var
))
595 fprintf (file
, "%*s",indent
, "");
596 print_generic_decl (file
, var
, flags
);
597 fprintf (file
, "%s\n", used
? "" : " (unused)");
599 for (i
= 0; i
< BLOCK_NUM_NONLOCALIZED_VARS (scope
); i
++)
601 fprintf (file
, "%*s",indent
, "");
602 print_generic_decl (file
, BLOCK_NONLOCALIZED_VAR (scope
, i
),
604 fprintf (file
, " (nonlocalized)\n");
606 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
607 dump_scope_block (file
, indent
+ 2, t
, flags
);
608 fprintf (file
, "\n%*s}\n",indent
, "");
612 /* Dump the tree of lexical scopes of current_function_decl to FILE.
613 FLAGS is as in print_generic_expr. */
616 dump_scope_blocks (FILE *file
, int flags
)
618 dump_scope_block (file
, 0, DECL_INITIAL (current_function_decl
), flags
);
622 /* Dump the tree of lexical scopes of current_function_decl to stderr.
623 FLAGS is as in print_generic_expr. */
626 debug_scope_blocks (int flags
)
628 dump_scope_blocks (stderr
, flags
);
631 /* Remove local variables that are not referenced in the IL. */
634 remove_unused_locals (void)
638 referenced_var_iterator rvi
;
640 bitmap global_unused_vars
= NULL
;
642 /* Removing declarations from lexical blocks when not optimizing is
643 not only a waste of time, it actually causes differences in stack
648 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
650 /* Assume all locals are unused. */
651 FOR_EACH_REFERENCED_VAR (t
, rvi
)
652 var_ann (t
)->used
= false;
654 /* Walk the CFG marking all referenced symbols. */
657 gimple_stmt_iterator gsi
;
662 /* Walk the statements. */
663 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
665 gimple stmt
= gsi_stmt (gsi
);
666 tree b
= gimple_block (stmt
);
669 TREE_USED (b
) = true;
671 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
672 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi
), i
), NULL
);
675 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
680 gimple phi
= gsi_stmt (gsi
);
682 /* No point processing globals. */
683 if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi
))))
686 def
= gimple_phi_result (phi
);
687 mark_all_vars_used (&def
, NULL
);
689 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
691 tree arg
= USE_FROM_PTR (arg_p
);
692 mark_all_vars_used (&arg
, NULL
);
696 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
698 TREE_USED (e
->goto_block
) = true;
701 cfun
->has_local_explicit_reg_vars
= false;
703 /* Remove unmarked local vars from local_decls. */
704 for (cell
= &cfun
->local_decls
; *cell
; )
706 tree var
= TREE_VALUE (*cell
);
708 if (TREE_CODE (var
) != FUNCTION_DECL
709 && (!(ann
= var_ann (var
))
712 if (is_global_var (var
))
714 if (global_unused_vars
== NULL
)
715 global_unused_vars
= BITMAP_ALLOC (NULL
);
716 bitmap_set_bit (global_unused_vars
, DECL_UID (var
));
720 *cell
= TREE_CHAIN (*cell
);
724 else if (TREE_CODE (var
) == VAR_DECL
725 && DECL_HARD_REGISTER (var
)
726 && !is_global_var (var
))
727 cfun
->has_local_explicit_reg_vars
= true;
728 cell
= &TREE_CHAIN (*cell
);
731 /* Remove unmarked global vars from local_decls. */
732 if (global_unused_vars
!= NULL
)
734 for (t
= cfun
->local_decls
; t
; t
= TREE_CHAIN (t
))
736 tree var
= TREE_VALUE (t
);
738 if (TREE_CODE (var
) == VAR_DECL
739 && is_global_var (var
)
740 && (ann
= var_ann (var
)) != NULL
742 mark_all_vars_used (&DECL_INITIAL (var
), global_unused_vars
);
745 for (cell
= &cfun
->local_decls
; *cell
; )
747 tree var
= TREE_VALUE (*cell
);
749 if (TREE_CODE (var
) == VAR_DECL
750 && is_global_var (var
)
751 && bitmap_bit_p (global_unused_vars
, DECL_UID (var
)))
752 *cell
= TREE_CHAIN (*cell
);
754 cell
= &TREE_CHAIN (*cell
);
756 BITMAP_FREE (global_unused_vars
);
759 /* Remove unused variables from REFERENCED_VARs. As a special
760 exception keep the variables that are believed to be aliased.
761 Those can't be easily removed from the alias sets and operand
762 caches. They will be removed shortly after the next may_alias
763 pass is performed. */
764 FOR_EACH_REFERENCED_VAR (t
, rvi
)
765 if (!is_global_var (t
)
766 && TREE_CODE (t
) != PARM_DECL
767 && TREE_CODE (t
) != RESULT_DECL
768 && !(ann
= var_ann (t
))->used
769 && !TREE_ADDRESSABLE (t
))
770 remove_referenced_var (t
);
771 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
));
772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
774 fprintf (dump_file
, "Scope blocks after cleanups:\n");
775 dump_scope_blocks (dump_file
, dump_flags
);
780 /* Allocate and return a new live range information object base on MAP. */
782 static tree_live_info_p
783 new_tree_live_info (var_map map
)
785 tree_live_info_p live
;
788 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
790 live
->num_blocks
= last_basic_block
;
792 live
->livein
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
793 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
794 live
->livein
[x
] = BITMAP_ALLOC (NULL
);
796 live
->liveout
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
797 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
798 live
->liveout
[x
] = BITMAP_ALLOC (NULL
);
800 live
->work_stack
= XNEWVEC (int, last_basic_block
);
801 live
->stack_top
= live
->work_stack
;
803 live
->global
= BITMAP_ALLOC (NULL
);
808 /* Free storage for live range info object LIVE. */
811 delete_tree_live_info (tree_live_info_p live
)
815 BITMAP_FREE (live
->global
);
816 free (live
->work_stack
);
818 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
819 BITMAP_FREE (live
->liveout
[x
]);
820 free (live
->liveout
);
822 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
823 BITMAP_FREE (live
->livein
[x
]);
830 /* Visit basic block BB and propagate any required live on entry bits from
831 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
832 TMP is a temporary work bitmap which is passed in to avoid reallocating
836 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
844 gcc_assert (!TEST_BIT (visited
, bb
->index
));
846 SET_BIT (visited
, bb
->index
);
847 loe
= live_on_entry (live
, bb
);
849 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
852 if (pred_bb
== ENTRY_BLOCK_PTR
)
854 /* TMP is variables live-on-entry from BB that aren't defined in the
855 predecessor block. This should be the live on entry vars to pred.
856 Note that liveout is the DEFs in a block while live on entry is
858 bitmap_and_compl (tmp
, loe
, live
->liveout
[pred_bb
->index
]);
860 /* Add these bits to live-on-entry for the pred. if there are any
861 changes, and pred_bb has been visited already, add it to the
863 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
864 if (TEST_BIT (visited
, pred_bb
->index
) && change
)
866 RESET_BIT (visited
, pred_bb
->index
);
867 *(live
->stack_top
)++ = pred_bb
->index
;
873 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
874 of all the variables. */
877 live_worklist (tree_live_info_p live
)
881 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
882 bitmap tmp
= BITMAP_ALLOC (NULL
);
884 sbitmap_zero (visited
);
886 /* Visit all the blocks in reverse order and propagate live on entry values
887 into the predecessors blocks. */
888 FOR_EACH_BB_REVERSE (bb
)
889 loe_visit_block (live
, bb
, visited
, tmp
);
891 /* Process any blocks which require further iteration. */
892 while (live
->stack_top
!= live
->work_stack
)
894 b
= *--(live
->stack_top
);
895 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
899 sbitmap_free (visited
);
903 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
904 links. Set the live on entry fields in LIVE. Def's are marked temporarily
905 in the liveout vector. */
908 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
913 basic_block def_bb
= NULL
;
914 imm_use_iterator imm_iter
;
917 p
= var_to_partition (live
->map
, ssa_name
);
918 if (p
== NO_PARTITION
)
921 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
924 def_bb
= gimple_bb (stmt
);
925 /* Mark defs in liveout bitmap temporarily. */
927 bitmap_set_bit (live
->liveout
[def_bb
->index
], p
);
930 def_bb
= ENTRY_BLOCK_PTR
;
932 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
933 add it to the list of live on entry blocks. */
934 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
936 gimple use_stmt
= USE_STMT (use
);
937 basic_block add_block
= NULL
;
939 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
941 /* Uses in PHI's are considered to be live at exit of the SRC block
942 as this is where a copy would be inserted. Check to see if it is
943 defined in that block, or whether its live on entry. */
944 int index
= PHI_ARG_INDEX_FROM_USE (use
);
945 edge e
= gimple_phi_arg_edge (use_stmt
, index
);
946 if (e
->src
!= ENTRY_BLOCK_PTR
)
948 if (e
->src
!= def_bb
)
954 /* If its not defined in this block, its live on entry. */
955 basic_block use_bb
= gimple_bb (use_stmt
);
956 if (use_bb
!= def_bb
)
960 /* If there was a live on entry use, set the bit. */
964 bitmap_set_bit (live
->livein
[add_block
->index
], p
);
968 /* If SSA_NAME is live on entry to at least one block, fill in all the live
969 on entry blocks between the def and all the uses. */
971 bitmap_set_bit (live
->global
, p
);
975 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
978 calculate_live_on_exit (tree_live_info_p liveinfo
)
984 /* live on entry calculations used liveout vectors for defs, clear them. */
986 bitmap_clear (liveinfo
->liveout
[bb
->index
]);
988 /* Set all the live-on-exit bits for uses in PHIs. */
991 gimple_stmt_iterator gsi
;
994 /* Mark the PHI arguments which are live on exit to the pred block. */
995 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
997 gimple phi
= gsi_stmt (gsi
);
998 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1000 tree t
= PHI_ARG_DEF (phi
, i
);
1003 if (TREE_CODE (t
) != SSA_NAME
)
1006 p
= var_to_partition (liveinfo
->map
, t
);
1007 if (p
== NO_PARTITION
)
1009 e
= gimple_phi_arg_edge (phi
, i
);
1010 if (e
->src
!= ENTRY_BLOCK_PTR
)
1011 bitmap_set_bit (liveinfo
->liveout
[e
->src
->index
], p
);
1015 /* Add each successors live on entry to this bock live on exit. */
1016 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1017 if (e
->dest
!= EXIT_BLOCK_PTR
)
1018 bitmap_ior_into (liveinfo
->liveout
[bb
->index
],
1019 live_on_entry (liveinfo
, e
->dest
));
1024 /* Given partition map MAP, calculate all the live on entry bitmaps for
1025 each partition. Return a new live info object. */
1028 calculate_live_ranges (var_map map
)
1032 tree_live_info_p live
;
1034 live
= new_tree_live_info (map
);
1035 for (i
= 0; i
< num_var_partitions (map
); i
++)
1037 var
= partition_to_var (map
, i
);
1038 if (var
!= NULL_TREE
)
1039 set_var_live_on_entry (var
, live
);
1042 live_worklist (live
);
1044 #ifdef ENABLE_CHECKING
1045 verify_live_on_entry (live
);
1048 calculate_live_on_exit (live
);
1053 /* Output partition map MAP to file F. */
1056 dump_var_map (FILE *f
, var_map map
)
1062 fprintf (f
, "\nPartition map \n\n");
1064 for (x
= 0; x
< map
->num_partitions
; x
++)
1066 if (map
->view_to_partition
!= NULL
)
1067 p
= map
->view_to_partition
[x
];
1071 if (ssa_name (p
) == NULL_TREE
)
1075 for (y
= 1; y
< num_ssa_names
; y
++)
1077 p
= partition_find (map
->var_partition
, y
);
1078 if (map
->partition_to_view
)
1079 p
= map
->partition_to_view
[p
];
1084 fprintf(f
, "Partition %d (", x
);
1085 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1088 fprintf (f
, "%d ", y
);
1098 /* Output live range info LIVE to file F, controlled by FLAG. */
1101 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1105 var_map map
= live
->map
;
1108 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1112 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1113 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[bb
->index
], 0, i
, bi
)
1115 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1122 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1126 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1127 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
, bi
)
1129 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1138 #ifdef ENABLE_CHECKING
1139 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1142 register_ssa_partition_check (tree ssa_var
)
1144 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
1145 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
1147 fprintf (stderr
, "Illegally registering a virtual SSA name :");
1148 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
1149 fprintf (stderr
, " in the SSA->Normal phase.\n");
1150 internal_error ("SSA corruption");
1155 /* Verify that the info in LIVE matches the current cfg. */
1158 verify_live_on_entry (tree_live_info_p live
)
1167 var_map map
= live
->map
;
1169 /* Check for live on entry partitions and report those with a DEF in
1170 the program. This will typically mean an optimization has done
1172 bb
= ENTRY_BLOCK_PTR
;
1174 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1176 int entry_block
= e
->dest
->index
;
1177 if (e
->dest
== EXIT_BLOCK_PTR
)
1179 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1184 var
= partition_to_var (map
, i
);
1185 stmt
= SSA_NAME_DEF_STMT (var
);
1186 tmp
= gimple_bb (stmt
);
1187 d
= gimple_default_def (cfun
, SSA_NAME_VAR (var
));
1189 loe
= live_on_entry (live
, e
->dest
);
1190 if (loe
&& bitmap_bit_p (loe
, i
))
1192 if (!gimple_nop_p (stmt
))
1195 print_generic_expr (stderr
, var
, TDF_SLIM
);
1196 fprintf (stderr
, " is defined ");
1198 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1199 fprintf (stderr
, "by:\n");
1200 print_gimple_stmt (stderr
, stmt
, 0, TDF_SLIM
);
1201 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1203 fprintf (stderr
, " So it appears to have multiple defs.\n");
1210 print_generic_expr (stderr
, var
, TDF_SLIM
);
1211 fprintf (stderr
, " is live-on-entry to BB%d ",
1215 fprintf (stderr
, " but is not the default def of ");
1216 print_generic_expr (stderr
, d
, TDF_SLIM
);
1217 fprintf (stderr
, "\n");
1220 fprintf (stderr
, " and there is no default def.\n");
1227 /* The only way this var shouldn't be marked live on entry is
1228 if it occurs in a PHI argument of the block. */
1231 gimple_stmt_iterator gsi
;
1232 for (gsi
= gsi_start_phis (e
->dest
);
1233 !gsi_end_p (gsi
) && !ok
;
1236 gimple phi
= gsi_stmt (gsi
);
1237 for (z
= 0; z
< gimple_phi_num_args (phi
); z
++)
1238 if (var
== gimple_phi_arg_def (phi
, z
))
1247 print_generic_expr (stderr
, var
, TDF_SLIM
);
1248 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1250 fprintf (stderr
, "but it is a default def so it should be.\n");
1254 gcc_assert (num
<= 0);