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);
139 map->partition_to_var
140 = (tree *)xmalloc (size * sizeof (tree));
141 memset (map->partition_to_var, 0, size * sizeof (tree));
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 free (map->partition_to_var);
161 partition_delete (map->var_partition);
162 if (map->partition_to_view)
163 free (map->partition_to_view);
164 if (map->view_to_partition)
165 free (map->view_to_partition);
170 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
171 Returns the partition which represents the new partition. If the two
172 partitions cannot be combined, NO_PARTITION is returned. */
175 var_union (var_map map, tree var1, tree var2)
178 tree root_var = NULL_TREE;
179 tree other_var = NULL_TREE;
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 if (TREE_CODE (var1) == SSA_NAME)
186 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
189 p1 = var_to_partition (map, var1);
190 if (map->view_to_partition)
191 p1 = map->view_to_partition[p1];
195 if (TREE_CODE (var2) == SSA_NAME)
196 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
199 p2 = var_to_partition (map, var2);
200 if (map->view_to_partition)
201 p2 = map->view_to_partition[p2];
203 /* If there is no root_var set, or it's not a user variable, set the
204 root_var to this one. */
205 if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
207 other_var = root_var;
214 gcc_assert (p1 != NO_PARTITION);
215 gcc_assert (p2 != NO_PARTITION);
220 p3 = partition_union (map->var_partition, p1, p2);
222 if (map->partition_to_view)
223 p3 = map->partition_to_view[p3];
226 change_partition_var (map, root_var, p3);
228 change_partition_var (map, other_var, p3);
234 /* Compress the partition numbers in MAP such that they fall in the range
235 0..(num_partitions-1) instead of wherever they turned out during
236 the partitioning exercise. This removes any references to unused
237 partitions, thereby allowing bitmaps and other vectors to be much
240 This is implemented such that compaction doesn't affect partitioning.
241 Ie., once partitions are created and possibly merged, running one
242 or more different kind of compaction will not affect the partitions
243 themselves. Their index might change, but all the same variables will
244 still be members of the same partition group. This allows work on reduced
245 sets, and no loss of information when a larger set is later desired.
247 In particular, coalescing can work on partitions which have 2 or more
248 definitions, and then 'recompact' later to include all the single
249 definitions for assignment to program variables. */
252 /* Set MAP back to the initial state of having no partition view. Return a
253 bitmap which has a bit set for each partition number which is in use in the
257 partition_view_init (var_map map)
263 used = BITMAP_ALLOC (NULL);
265 /* Already in a view? Abandon the old one. */
266 if (map->partition_to_view)
268 free (map->partition_to_view);
269 map->partition_to_view = NULL;
271 if (map->view_to_partition)
273 free (map->view_to_partition);
274 map->view_to_partition = NULL;
277 /* Find out which partitions are actually referenced. */
278 for (x = 0; x < map->partition_size; x++)
280 tmp = partition_find (map->var_partition, x);
281 if (map->partition_to_var[tmp] != NULL_TREE && !bitmap_bit_p (used, tmp))
282 bitmap_set_bit (used, tmp);
285 map->num_partitions = map->partition_size;
290 /* This routine will finalize the view data for MAP based on the partitions
291 set in SELECTED. This is either the same bitmap returned from
292 partition_view_init, or a trimmed down version if some of those partitions
293 were not desired in this view. SELECTED is freed before returning. */
296 partition_view_fini (var_map map, bitmap selected)
299 unsigned count, i, x, limit;
302 gcc_assert (selected);
304 count = bitmap_count_bits (selected);
305 limit = map->partition_size;
307 /* If its a one-to-one ratio, we don't need any view compaction. */
310 map->partition_to_view = (int *)xmalloc (limit * sizeof (int));
311 memset (map->partition_to_view, 0xff, (limit * sizeof (int)));
312 map->view_to_partition = (int *)xmalloc (count * sizeof (int));
315 /* Give each selected partition an index. */
316 EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)
318 map->partition_to_view[x] = i;
319 map->view_to_partition[i] = x;
320 var = map->partition_to_var[x];
321 /* If any one of the members of a partition is not an SSA_NAME, make
322 sure it is the representative. */
323 if (TREE_CODE (var) != SSA_NAME)
324 change_partition_var (map, var, i);
327 gcc_assert (i == count);
328 map->num_partitions = i;
331 BITMAP_FREE (selected);
335 /* Create a partition view which includes all the used partitions in MAP. If
336 WANT_BASES is true, create the base variable map as well. */
339 partition_view_normal (var_map map, bool want_bases)
343 used = partition_view_init (map);
344 partition_view_fini (map, used);
347 var_map_base_init (map);
349 var_map_base_fini (map);
353 /* Create a partition view in MAP which includes just partitions which occur in
354 the bitmap ONLY. If WANT_BASES is true, create the base variable map
358 partition_view_bitmap (var_map map, bitmap only, bool want_bases)
361 bitmap new_partitions = BITMAP_ALLOC (NULL);
365 used = partition_view_init (map);
366 EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)
368 p = partition_find (map->var_partition, x);
369 gcc_assert (bitmap_bit_p (used, p));
370 bitmap_set_bit (new_partitions, p);
372 partition_view_fini (map, new_partitions);
376 var_map_base_init (map);
378 var_map_base_fini (map);
382 /* This function is used to change the representative variable in MAP for VAR's
383 partition to a regular non-ssa variable. This allows partitions to be
384 mapped back to real variables. */
387 change_partition_var (var_map map, tree var, int part)
391 gcc_assert (TREE_CODE (var) != SSA_NAME);
394 ann->out_of_ssa_tag = 1;
395 VAR_ANN_PARTITION (ann) = part;
396 if (map->view_to_partition)
397 map->partition_to_var[map->view_to_partition[part]] = var;
401 static inline void mark_all_vars_used (tree *, void *data);
403 /* Helper function for mark_all_vars_used, called via walk_tree. */
406 mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data)
409 enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));
412 if (TREE_CODE (t) == SSA_NAME)
413 t = SSA_NAME_VAR (t);
415 if (IS_EXPR_CODE_CLASS (c)
416 && (b = TREE_BLOCK (t)) != NULL)
417 TREE_USED (b) = true;
419 /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
420 fields that do not contain vars. */
421 if (TREE_CODE (t) == TARGET_MEM_REF)
423 mark_all_vars_used (&TMR_SYMBOL (t), data);
424 mark_all_vars_used (&TMR_BASE (t), data);
425 mark_all_vars_used (&TMR_INDEX (t), data);
430 /* Only need to mark VAR_DECLS; parameters and return results are not
431 eliminated as unused. */
432 if (TREE_CODE (t) == VAR_DECL)
434 if (data != NULL && bitmap_bit_p ((bitmap) data, DECL_UID (t)))
436 bitmap_clear_bit ((bitmap) data, DECL_UID (t));
437 mark_all_vars_used (&DECL_INITIAL (t), data);
442 if (IS_TYPE_OR_DECL_P (t))
448 /* Mark the scope block SCOPE and its subblocks unused when they can be
449 possibly eliminated if dead. */
452 mark_scope_block_unused (tree scope)
455 TREE_USED (scope) = false;
456 if (!(*debug_hooks->ignore_block) (scope))
457 TREE_USED (scope) = true;
458 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
459 mark_scope_block_unused (t);
462 /* Look if the block is dead (by possibly eliminating its dead subblocks)
463 and return true if so.
464 Block is declared dead if:
465 1) No statements are associated with it.
466 2) Declares no live variables
467 3) All subblocks are dead
468 or there is precisely one subblocks and the block
469 has same abstract origin as outer block and declares
470 no variables, so it is pure wrapper.
471 When we are not outputting full debug info, we also eliminate dead variables
472 out of scope blocks to let them to be recycled by GGC and to save copying work
473 done by the inliner. */
476 remove_unused_scope_block_p (tree scope)
479 bool unused = !TREE_USED (scope);
483 for (t = &BLOCK_VARS (scope); *t; t = next)
485 next = &TREE_CHAIN (*t);
487 /* Debug info of nested function refers to the block of the
488 function. We might stil call it even if all statements
489 of function it was nested into was elliminated.
491 TODO: We can actually look into cgraph to see if function
492 will be output to file. */
493 if (TREE_CODE (*t) == FUNCTION_DECL)
495 /* Remove everything we don't generate debug info for. */
496 else if (DECL_IGNORED_P (*t))
498 *t = TREE_CHAIN (*t);
502 /* When we are outputting debug info, we usually want to output
503 info about optimized-out variables in the scope blocks.
504 Exception are the scope blocks not containing any instructions
505 at all so user can't get into the scopes at first place. */
506 else if ((ann = var_ann (*t)) != NULL
510 /* When we are not doing full debug info, we however can keep around
511 only the used variables for cfgexpand's memory packing saving quite
514 For sake of -g3, we keep around those vars but we don't count this as
515 use of block, so innermost block with no used vars and no instructions
516 can be considered dead. We only want to keep around blocks user can
517 breakpoint into and ask about value of optimized out variables.
519 Similarly we need to keep around types at least until all variables of
520 all nested blocks are gone. We track no information on whether given
521 type is used or not. */
523 else if (debug_info_level == DINFO_LEVEL_NORMAL
524 || debug_info_level == DINFO_LEVEL_VERBOSE
525 /* Removing declarations before inlining is going to affect
526 DECL_UID that in turn is going to affect hashtables and
528 || !cfun->after_inlining)
532 *t = TREE_CHAIN (*t);
537 for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
538 if (remove_unused_scope_block_p (*t))
540 if (BLOCK_SUBBLOCKS (*t))
542 tree next = BLOCK_CHAIN (*t);
543 tree supercontext = BLOCK_SUPERCONTEXT (*t);
545 *t = BLOCK_SUBBLOCKS (*t);
546 while (BLOCK_CHAIN (*t))
548 BLOCK_SUPERCONTEXT (*t) = supercontext;
549 t = &BLOCK_CHAIN (*t);
551 BLOCK_CHAIN (*t) = next;
552 BLOCK_SUPERCONTEXT (*t) = supercontext;
553 t = &BLOCK_CHAIN (*t);
557 *t = BLOCK_CHAIN (*t);
561 t = &BLOCK_CHAIN (*t);
568 /* Outer scope is always used. */
569 else if (!BLOCK_SUPERCONTEXT (scope)
570 || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)
572 /* Innermost blocks with no live variables nor statements can be always
574 else if (!nsubblocks)
576 /* If there are live subblocks and we still have some unused variables
577 or types declared, we must keep them.
578 Before inliing we must not depend on debug info verbosity to keep
580 else if (!cfun->after_inlining && BLOCK_VARS (scope))
582 /* For terse debug info we can eliminate info on unused variables. */
583 else if (debug_info_level == DINFO_LEVEL_NONE
584 || debug_info_level == DINFO_LEVEL_TERSE)
586 /* Even for -g0/-g1 don't prune outer scopes from artificial
587 functions, otherwise diagnostics using tree_nonartificial_location
588 will not be emitted properly. */
589 if (inlined_function_outer_scope_p (scope))
594 && TREE_CODE (ao) == BLOCK
595 && BLOCK_ABSTRACT_ORIGIN (ao) != ao)
596 ao = BLOCK_ABSTRACT_ORIGIN (ao);
598 && TREE_CODE (ao) == FUNCTION_DECL
599 && DECL_DECLARED_INLINE_P (ao)
600 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao)))
604 else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope))
606 /* See if this block is important for representation of inlined function.
607 Inlined functions are always represented by block with
608 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
610 else if (inlined_function_outer_scope_p (scope))
613 /* Verfify that only blocks with source location set
614 are entry points to the inlined functions. */
615 gcc_assert (BLOCK_SOURCE_LOCATION (scope) == UNKNOWN_LOCATION);
617 TREE_USED (scope) = !unused;
621 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
622 eliminated during the tree->rtl conversion process. */
625 mark_all_vars_used (tree *expr_p, void *data)
627 walk_tree (expr_p, mark_all_vars_used_1, data, NULL);
630 /* Dump scope blocks. */
633 dump_scope_block (FILE *file, int indent, tree scope, int flags)
638 fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope),
639 TREE_USED (scope) ? "" : " (unused)",
640 BLOCK_ABSTRACT (scope) ? " (abstract)": "");
641 if (BLOCK_SOURCE_LOCATION (scope) != UNKNOWN_LOCATION)
643 expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope));
644 fprintf (file, " %s:%i", s.file, s.line);
646 if (BLOCK_ABSTRACT_ORIGIN (scope))
648 tree origin = block_ultimate_origin (scope);
651 fprintf (file, " Originating from :");
653 print_generic_decl (file, origin, flags);
655 fprintf (file, "#%i", BLOCK_NUMBER (origin));
658 fprintf (file, " \n");
659 for (var = BLOCK_VARS (scope); var; var = TREE_CHAIN (var))
664 if ((ann = var_ann (var))
668 fprintf (file, "%*s",indent, "");
669 print_generic_decl (file, var, flags);
670 fprintf (file, "%s\n", used ? "" : " (unused)");
672 for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++)
674 fprintf (file, "%*s",indent, "");
675 print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i),
677 fprintf (file, " (nonlocalized)\n");
679 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
680 dump_scope_block (file, indent + 2, t, flags);
681 fprintf (file, "\n%*s}\n",indent, "");
685 dump_scope_blocks (FILE *file, int flags)
687 dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags);
690 /* Remove local variables that are not referenced in the IL. */
693 remove_unused_locals (void)
697 referenced_var_iterator rvi;
699 bitmap global_unused_vars = NULL;
701 /* Removing declarations from lexical blocks when not optimizing is
702 not only a waste of time, it actually causes differences in stack
707 mark_scope_block_unused (DECL_INITIAL (current_function_decl));
709 /* Assume all locals are unused. */
710 FOR_EACH_REFERENCED_VAR (t, rvi)
711 var_ann (t)->used = false;
713 /* Walk the CFG marking all referenced symbols. */
716 gimple_stmt_iterator gsi;
721 /* Walk the statements. */
722 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
724 gimple stmt = gsi_stmt (gsi);
725 tree b = gimple_block (stmt);
728 TREE_USED (b) = true;
730 for (i = 0; i < gimple_num_ops (stmt); i++)
731 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i), NULL);
734 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
739 gimple phi = gsi_stmt (gsi);
741 /* No point processing globals. */
742 if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi))))
745 def = gimple_phi_result (phi);
746 mark_all_vars_used (&def, NULL);
748 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
750 tree arg = USE_FROM_PTR (arg_p);
751 mark_all_vars_used (&arg, NULL);
755 FOR_EACH_EDGE (e, ei, bb->succs)
757 TREE_USED (e->goto_block) = true;
760 cfun->has_local_explicit_reg_vars = false;
762 /* Remove unmarked local vars from local_decls. */
763 for (cell = &cfun->local_decls; *cell; )
765 tree var = TREE_VALUE (*cell);
767 if (TREE_CODE (var) != FUNCTION_DECL
768 && (!(ann = var_ann (var))
771 if (is_global_var (var))
773 if (global_unused_vars == NULL)
774 global_unused_vars = BITMAP_ALLOC (NULL);
775 bitmap_set_bit (global_unused_vars, DECL_UID (var));
779 *cell = TREE_CHAIN (*cell);
783 else if (TREE_CODE (var) == VAR_DECL
784 && DECL_HARD_REGISTER (var)
785 && !is_global_var (var))
786 cfun->has_local_explicit_reg_vars = true;
787 cell = &TREE_CHAIN (*cell);
790 /* Remove unmarked global vars from local_decls. */
791 if (global_unused_vars != NULL)
793 for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
795 tree var = TREE_VALUE (t);
797 if (TREE_CODE (var) == VAR_DECL
798 && is_global_var (var)
799 && (ann = var_ann (var)) != NULL
801 mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars);
804 for (cell = &cfun->local_decls; *cell; )
806 tree var = TREE_VALUE (*cell);
808 if (TREE_CODE (var) == VAR_DECL
809 && is_global_var (var)
810 && bitmap_bit_p (global_unused_vars, DECL_UID (var)))
811 *cell = TREE_CHAIN (*cell);
813 cell = &TREE_CHAIN (*cell);
815 BITMAP_FREE (global_unused_vars);
818 /* Remove unused variables from REFERENCED_VARs. As a special
819 exception keep the variables that are believed to be aliased.
820 Those can't be easily removed from the alias sets and operand
821 caches. They will be removed shortly after the next may_alias
822 pass is performed. */
823 FOR_EACH_REFERENCED_VAR (t, rvi)
824 if (!is_global_var (t)
826 && TREE_CODE (t) != PARM_DECL
827 && TREE_CODE (t) != RESULT_DECL
828 && !(ann = var_ann (t))->used
829 && !ann->symbol_mem_tag
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)
1015 /* If its not defined in this block, its live on entry. */
1016 basic_block use_bb = gimple_bb (use_stmt);
1017 if (use_bb != def_bb)
1021 /* If there was a live on entry use, set the bit. */
1025 bitmap_set_bit (live->livein[add_block->index], p);
1029 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1030 on entry blocks between the def and all the uses. */
1032 bitmap_set_bit (live->global, p);
1036 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1039 calculate_live_on_exit (tree_live_info_p liveinfo)
1045 /* live on entry calculations used liveout vectors for defs, clear them. */
1047 bitmap_clear (liveinfo->liveout[bb->index]);
1049 /* Set all the live-on-exit bits for uses in PHIs. */
1052 gimple_stmt_iterator gsi;
1055 /* Mark the PHI arguments which are live on exit to the pred block. */
1056 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1058 gimple phi = gsi_stmt (gsi);
1059 for (i = 0; i < gimple_phi_num_args (phi); i++)
1061 tree t = PHI_ARG_DEF (phi, i);
1064 if (TREE_CODE (t) != SSA_NAME)
1067 p = var_to_partition (liveinfo->map, t);
1068 if (p == NO_PARTITION)
1070 e = gimple_phi_arg_edge (phi, i);
1071 if (e->src != ENTRY_BLOCK_PTR)
1072 bitmap_set_bit (liveinfo->liveout[e->src->index], p);
1076 /* Add each successors live on entry to this bock live on exit. */
1077 FOR_EACH_EDGE (e, ei, bb->succs)
1078 if (e->dest != EXIT_BLOCK_PTR)
1079 bitmap_ior_into (liveinfo->liveout[bb->index],
1080 live_on_entry (liveinfo, e->dest));
1085 /* Given partition map MAP, calculate all the live on entry bitmaps for
1086 each partition. Return a new live info object. */
1089 calculate_live_ranges (var_map map)
1093 tree_live_info_p live;
1095 live = new_tree_live_info (map);
1096 for (i = 0; i < num_var_partitions (map); i++)
1098 var = partition_to_var (map, i);
1099 if (var != NULL_TREE)
1100 set_var_live_on_entry (var, live);
1103 live_worklist (live);
1105 #ifdef ENABLE_CHECKING
1106 verify_live_on_entry (live);
1109 calculate_live_on_exit (live);
1114 /* Output partition map MAP to file F. */
1117 dump_var_map (FILE *f, var_map map)
1123 fprintf (f, "\nPartition map \n\n");
1125 for (x = 0; x < map->num_partitions; x++)
1127 if (map->view_to_partition != NULL)
1128 p = map->view_to_partition[x];
1132 if (map->partition_to_var[p] == NULL_TREE)
1136 for (y = 1; y < num_ssa_names; y++)
1138 p = partition_find (map->var_partition, y);
1139 if (map->partition_to_view)
1140 p = map->partition_to_view[p];
1145 fprintf(f, "Partition %d (", x);
1146 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1149 fprintf (f, "%d ", y);
1159 /* Output live range info LIVE to file F, controlled by FLAG. */
1162 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1166 var_map map = live->map;
1169 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1173 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1174 EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
1176 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1183 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1187 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1188 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1190 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1199 #ifdef ENABLE_CHECKING
1200 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1203 register_ssa_partition_check (tree ssa_var)
1205 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1206 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1208 fprintf (stderr, "Illegally registering a virtual SSA name :");
1209 print_generic_expr (stderr, ssa_var, TDF_SLIM);
1210 fprintf (stderr, " in the SSA->Normal phase.\n");
1211 internal_error ("SSA corruption");
1216 /* Verify that the info in LIVE matches the current cfg. */
1219 verify_live_on_entry (tree_live_info_p live)
1228 var_map map = live->map;
1230 /* Check for live on entry partitions and report those with a DEF in
1231 the program. This will typically mean an optimization has done
1233 bb = ENTRY_BLOCK_PTR;
1235 FOR_EACH_EDGE (e, ei, bb->succs)
1237 int entry_block = e->dest->index;
1238 if (e->dest == EXIT_BLOCK_PTR)
1240 for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1245 var = partition_to_var (map, i);
1246 stmt = SSA_NAME_DEF_STMT (var);
1247 tmp = gimple_bb (stmt);
1248 d = gimple_default_def (cfun, SSA_NAME_VAR (var));
1250 loe = live_on_entry (live, e->dest);
1251 if (loe && bitmap_bit_p (loe, i))
1253 if (!gimple_nop_p (stmt))
1256 print_generic_expr (stderr, var, TDF_SLIM);
1257 fprintf (stderr, " is defined ");
1259 fprintf (stderr, " in BB%d, ", tmp->index);
1260 fprintf (stderr, "by:\n");
1261 print_gimple_stmt (stderr, stmt, 0, TDF_SLIM);
1262 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1264 fprintf (stderr, " So it appears to have multiple defs.\n");
1271 print_generic_expr (stderr, var, TDF_SLIM);
1272 fprintf (stderr, " is live-on-entry to BB%d ",
1276 fprintf (stderr, " but is not the default def of ");
1277 print_generic_expr (stderr, d, TDF_SLIM);
1278 fprintf (stderr, "\n");
1281 fprintf (stderr, " and there is no default def.\n");
1288 /* The only way this var shouldn't be marked live on entry is
1289 if it occurs in a PHI argument of the block. */
1292 gimple_stmt_iterator gsi;
1293 for (gsi = gsi_start_phis (e->dest);
1294 !gsi_end_p (gsi) && !ok;
1297 gimple phi = gsi_stmt (gsi);
1298 for (z = 0; z < gimple_phi_num_args (phi); z++)
1299 if (var == gimple_phi_arg_def (phi, z))
1308 print_generic_expr (stderr, var, TDF_SLIM);
1309 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1311 fprintf (stderr, "but it is a default def so it should be.\n");
1315 gcc_assert (num <= 0);