1 /* Liveness for SSA trees.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Andrew MacLeod <amacleod@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
27 #include "tree-pretty-print.h"
28 #include "gimple-pretty-print.h"
30 #include "tree-flow.h"
31 #include "tree-dump.h"
32 #include "tree-ssa-live.h"
33 #include "diagnostic-core.h"
38 #ifdef ENABLE_CHECKING
39 static void verify_live_on_entry (tree_live_info_p);
43 /* VARMAP maintains a mapping from SSA version number to real variables.
45 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
46 only member of it's own partition. Coalescing will attempt to group any
47 ssa_names which occur in a copy or in a PHI node into the same partition.
49 At the end of out-of-ssa, each partition becomes a "real" variable and is
50 rewritten as a compiler variable.
52 The var_map data structure is used to manage these partitions. It allows
53 partitions to be combined, and determines which partition belongs to what
54 ssa_name or variable, and vice versa. */
57 /* This routine will initialize the basevar fields of MAP. */
60 var_map_base_init (var_map map)
67 num_part = num_var_partitions (map);
69 /* If a base table already exists, clear it, otherwise create it. */
70 if (map->partition_to_base_index != NULL)
72 free (map->partition_to_base_index);
73 VEC_truncate (tree, map->basevars, 0);
76 map->basevars = VEC_alloc (tree, heap, MAX (40, (num_part / 10)));
78 map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
80 /* Build the base variable list, and point partitions at their bases. */
81 for (x = 0; x < num_part; x++)
83 var = partition_to_var (map, x);
84 if (TREE_CODE (var) == SSA_NAME)
85 var = SSA_NAME_VAR (var);
87 /* If base variable hasn't been seen, set it up. */
88 if (!ann->base_var_processed)
90 ann->base_var_processed = 1;
91 VAR_ANN_BASE_INDEX (ann) = num++;
92 VEC_safe_push (tree, heap, map->basevars, var);
94 map->partition_to_base_index[x] = VAR_ANN_BASE_INDEX (ann);
97 map->num_basevars = num;
99 /* Now clear the processed bit. */
100 for (x = 0; x < num; x++)
102 var = VEC_index (tree, map->basevars, x);
103 var_ann (var)->base_var_processed = 0;
106 #ifdef ENABLE_CHECKING
107 for (x = 0; x < num_part; x++)
110 var = SSA_NAME_VAR (partition_to_var (map, x));
111 var2 = VEC_index (tree, map->basevars, basevar_index (map, x));
112 gcc_assert (var == var2);
118 /* Remove the base table in MAP. */
121 var_map_base_fini (var_map map)
123 /* Free the basevar info if it is present. */
124 if (map->partition_to_base_index != NULL)
126 VEC_free (tree, heap, map->basevars);
127 free (map->partition_to_base_index);
128 map->partition_to_base_index = NULL;
129 map->num_basevars = 0;
132 /* Create a variable partition map of SIZE, initialize and return it. */
135 init_var_map (int size)
139 map = (var_map) xmalloc (sizeof (struct _var_map));
140 map->var_partition = partition_new (size);
142 map->partition_to_view = NULL;
143 map->view_to_partition = NULL;
144 map->num_partitions = size;
145 map->partition_size = size;
146 map->num_basevars = 0;
147 map->partition_to_base_index = NULL;
148 map->basevars = NULL;
153 /* Free memory associated with MAP. */
156 delete_var_map (var_map map)
158 var_map_base_fini (map);
159 partition_delete (map->var_partition);
160 if (map->partition_to_view)
161 free (map->partition_to_view);
162 if (map->view_to_partition)
163 free (map->view_to_partition);
168 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
169 Returns the partition which represents the new partition. If the two
170 partitions cannot be combined, NO_PARTITION is returned. */
173 var_union (var_map map, tree var1, tree var2)
177 gcc_assert (TREE_CODE (var1) == SSA_NAME);
178 gcc_assert (TREE_CODE (var2) == SSA_NAME);
180 /* This is independent of partition_to_view. If partition_to_view is
181 on, then whichever one of these partitions is absorbed will never have a
182 dereference into the partition_to_view array any more. */
184 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
185 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
187 gcc_assert (p1 != NO_PARTITION);
188 gcc_assert (p2 != NO_PARTITION);
193 p3 = partition_union (map->var_partition, p1, p2);
195 if (map->partition_to_view)
196 p3 = map->partition_to_view[p3];
202 /* Compress the partition numbers in MAP such that they fall in the range
203 0..(num_partitions-1) instead of wherever they turned out during
204 the partitioning exercise. This removes any references to unused
205 partitions, thereby allowing bitmaps and other vectors to be much
208 This is implemented such that compaction doesn't affect partitioning.
209 Ie., once partitions are created and possibly merged, running one
210 or more different kind of compaction will not affect the partitions
211 themselves. Their index might change, but all the same variables will
212 still be members of the same partition group. This allows work on reduced
213 sets, and no loss of information when a larger set is later desired.
215 In particular, coalescing can work on partitions which have 2 or more
216 definitions, and then 'recompact' later to include all the single
217 definitions for assignment to program variables. */
220 /* Set MAP back to the initial state of having no partition view. Return a
221 bitmap which has a bit set for each partition number which is in use in the
225 partition_view_init (var_map map)
231 used = BITMAP_ALLOC (NULL);
233 /* Already in a view? Abandon the old one. */
234 if (map->partition_to_view)
236 free (map->partition_to_view);
237 map->partition_to_view = NULL;
239 if (map->view_to_partition)
241 free (map->view_to_partition);
242 map->view_to_partition = NULL;
245 /* Find out which partitions are actually referenced. */
246 for (x = 0; x < map->partition_size; x++)
248 tmp = partition_find (map->var_partition, x);
249 if (ssa_name (tmp) != NULL_TREE && is_gimple_reg (ssa_name (tmp))
250 && (!has_zero_uses (ssa_name (tmp))
251 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp))))
252 bitmap_set_bit (used, tmp);
255 map->num_partitions = map->partition_size;
260 /* This routine will finalize the view data for MAP based on the partitions
261 set in SELECTED. This is either the same bitmap returned from
262 partition_view_init, or a trimmed down version if some of those partitions
263 were not desired in this view. SELECTED is freed before returning. */
266 partition_view_fini (var_map map, bitmap selected)
269 unsigned count, i, x, limit;
271 gcc_assert (selected);
273 count = bitmap_count_bits (selected);
274 limit = map->partition_size;
276 /* If its a one-to-one ratio, we don't need any view compaction. */
279 map->partition_to_view = (int *)xmalloc (limit * sizeof (int));
280 memset (map->partition_to_view, 0xff, (limit * sizeof (int)));
281 map->view_to_partition = (int *)xmalloc (count * sizeof (int));
284 /* Give each selected partition an index. */
285 EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)
287 map->partition_to_view[x] = i;
288 map->view_to_partition[i] = x;
291 gcc_assert (i == count);
292 map->num_partitions = i;
295 BITMAP_FREE (selected);
299 /* Create a partition view which includes all the used partitions in MAP. If
300 WANT_BASES is true, create the base variable map as well. */
303 partition_view_normal (var_map map, bool want_bases)
307 used = partition_view_init (map);
308 partition_view_fini (map, used);
311 var_map_base_init (map);
313 var_map_base_fini (map);
317 /* Create a partition view in MAP which includes just partitions which occur in
318 the bitmap ONLY. If WANT_BASES is true, create the base variable map
322 partition_view_bitmap (var_map map, bitmap only, bool want_bases)
325 bitmap new_partitions = BITMAP_ALLOC (NULL);
329 used = partition_view_init (map);
330 EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)
332 p = partition_find (map->var_partition, x);
333 gcc_assert (bitmap_bit_p (used, p));
334 bitmap_set_bit (new_partitions, p);
336 partition_view_fini (map, new_partitions);
340 var_map_base_init (map);
342 var_map_base_fini (map);
346 static inline void mark_all_vars_used (tree *, void *data);
348 /* Helper function for mark_all_vars_used, called via walk_tree. */
351 mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data)
354 enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));
357 if (TREE_CODE (t) == SSA_NAME)
358 t = SSA_NAME_VAR (t);
360 if (IS_EXPR_CODE_CLASS (c)
361 && (b = TREE_BLOCK (t)) != NULL)
362 TREE_USED (b) = true;
364 /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
365 fields that do not contain vars. */
366 if (TREE_CODE (t) == TARGET_MEM_REF)
368 mark_all_vars_used (&TMR_SYMBOL (t), data);
369 mark_all_vars_used (&TMR_BASE (t), data);
370 mark_all_vars_used (&TMR_INDEX (t), data);
375 /* Only need to mark VAR_DECLS; parameters and return results are not
376 eliminated as unused. */
377 if (TREE_CODE (t) == VAR_DECL)
379 if (data != NULL && bitmap_bit_p ((bitmap) data, DECL_UID (t)))
381 bitmap_clear_bit ((bitmap) data, DECL_UID (t));
382 mark_all_vars_used (&DECL_INITIAL (t), data);
386 /* remove_unused_scope_block_p requires information about labels
387 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
388 if (TREE_CODE (t) == LABEL_DECL)
389 /* Although the TREE_USED values that the frontend uses would be
390 acceptable (albeit slightly over-conservative) for our purposes,
391 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
392 must re-compute it here. */
395 if (IS_TYPE_OR_DECL_P (t))
401 /* Mark the scope block SCOPE and its subblocks unused when they can be
402 possibly eliminated if dead. */
405 mark_scope_block_unused (tree scope)
408 TREE_USED (scope) = false;
409 if (!(*debug_hooks->ignore_block) (scope))
410 TREE_USED (scope) = true;
411 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
412 mark_scope_block_unused (t);
415 /* Look if the block is dead (by possibly eliminating its dead subblocks)
416 and return true if so.
417 Block is declared dead if:
418 1) No statements are associated with it.
419 2) Declares no live variables
420 3) All subblocks are dead
421 or there is precisely one subblocks and the block
422 has same abstract origin as outer block and declares
423 no variables, so it is pure wrapper.
424 When we are not outputting full debug info, we also eliminate dead variables
425 out of scope blocks to let them to be recycled by GGC and to save copying work
426 done by the inliner. */
429 remove_unused_scope_block_p (tree scope)
432 bool unused = !TREE_USED (scope);
436 for (t = &BLOCK_VARS (scope); *t; t = next)
438 next = &TREE_CHAIN (*t);
440 /* Debug info of nested function refers to the block of the
441 function. We might stil call it even if all statements
442 of function it was nested into was elliminated.
444 TODO: We can actually look into cgraph to see if function
445 will be output to file. */
446 if (TREE_CODE (*t) == FUNCTION_DECL)
449 /* If a decl has a value expr, we need to instantiate it
450 regardless of debug info generation, to avoid codegen
451 differences in memory overlap tests. update_equiv_regs() may
452 indirectly call validate_equiv_mem() to test whether a
453 SET_DEST overlaps with others, and if the value expr changes
454 by virtual register instantiation, we may get end up with
455 different results. */
456 else if (TREE_CODE (*t) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*t))
459 /* Remove everything we don't generate debug info for. */
460 else if (DECL_IGNORED_P (*t))
462 *t = TREE_CHAIN (*t);
466 /* When we are outputting debug info, we usually want to output
467 info about optimized-out variables in the scope blocks.
468 Exception are the scope blocks not containing any instructions
469 at all so user can't get into the scopes at first place. */
470 else if ((ann = var_ann (*t)) != NULL
473 else if (TREE_CODE (*t) == LABEL_DECL && TREE_USED (*t))
474 /* For labels that are still used in the IL, the decision to
475 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
476 risk having different ordering in debug vs. non-debug builds
477 during inlining or versioning.
478 A label appearing here (we have already checked DECL_IGNORED_P)
479 should not be used in the IL unless it has been explicitly used
480 before, so we use TREE_USED as an approximation. */
481 /* In principle, we should do the same here as for the debug case
482 below, however, when debugging, there might be additional nested
483 levels that keep an upper level with a label live, so we have to
484 force this block to be considered used, too. */
487 /* When we are not doing full debug info, we however can keep around
488 only the used variables for cfgexpand's memory packing saving quite
491 For sake of -g3, we keep around those vars but we don't count this as
492 use of block, so innermost block with no used vars and no instructions
493 can be considered dead. We only want to keep around blocks user can
494 breakpoint into and ask about value of optimized out variables.
496 Similarly we need to keep around types at least until all variables of
497 all nested blocks are gone. We track no information on whether given
498 type is used or not. */
500 else if (debug_info_level == DINFO_LEVEL_NORMAL
501 || debug_info_level == DINFO_LEVEL_VERBOSE)
505 *t = TREE_CHAIN (*t);
510 for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
511 if (remove_unused_scope_block_p (*t))
513 if (BLOCK_SUBBLOCKS (*t))
515 tree next = BLOCK_CHAIN (*t);
516 tree supercontext = BLOCK_SUPERCONTEXT (*t);
518 *t = BLOCK_SUBBLOCKS (*t);
519 while (BLOCK_CHAIN (*t))
521 BLOCK_SUPERCONTEXT (*t) = supercontext;
522 t = &BLOCK_CHAIN (*t);
524 BLOCK_CHAIN (*t) = next;
525 BLOCK_SUPERCONTEXT (*t) = supercontext;
526 t = &BLOCK_CHAIN (*t);
530 *t = BLOCK_CHAIN (*t);
534 t = &BLOCK_CHAIN (*t);
541 /* Outer scope is always used. */
542 else if (!BLOCK_SUPERCONTEXT (scope)
543 || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)
545 /* Innermost blocks with no live variables nor statements can be always
547 else if (!nsubblocks)
549 /* For terse debug info we can eliminate info on unused variables. */
550 else if (debug_info_level == DINFO_LEVEL_NONE
551 || debug_info_level == DINFO_LEVEL_TERSE)
553 /* Even for -g0/-g1 don't prune outer scopes from artificial
554 functions, otherwise diagnostics using tree_nonartificial_location
555 will not be emitted properly. */
556 if (inlined_function_outer_scope_p (scope))
561 && TREE_CODE (ao) == BLOCK
562 && BLOCK_ABSTRACT_ORIGIN (ao) != ao)
563 ao = BLOCK_ABSTRACT_ORIGIN (ao);
565 && TREE_CODE (ao) == FUNCTION_DECL
566 && DECL_DECLARED_INLINE_P (ao)
567 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao)))
571 else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope))
573 /* See if this block is important for representation of inlined function.
574 Inlined functions are always represented by block with
575 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
577 else if (inlined_function_outer_scope_p (scope))
580 /* Verfify that only blocks with source location set
581 are entry points to the inlined functions. */
582 gcc_assert (BLOCK_SOURCE_LOCATION (scope) == UNKNOWN_LOCATION);
584 TREE_USED (scope) = !unused;
588 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
589 eliminated during the tree->rtl conversion process. */
592 mark_all_vars_used (tree *expr_p, void *data)
594 walk_tree (expr_p, mark_all_vars_used_1, data, NULL);
598 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
599 indentation level and FLAGS is as in print_generic_expr. */
602 dump_scope_block (FILE *file, int indent, tree scope, int flags)
607 fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope),
608 TREE_USED (scope) ? "" : " (unused)",
609 BLOCK_ABSTRACT (scope) ? " (abstract)": "");
610 if (BLOCK_SOURCE_LOCATION (scope) != UNKNOWN_LOCATION)
612 expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope));
613 fprintf (file, " %s:%i", s.file, s.line);
615 if (BLOCK_ABSTRACT_ORIGIN (scope))
617 tree origin = block_ultimate_origin (scope);
620 fprintf (file, " Originating from :");
622 print_generic_decl (file, origin, flags);
624 fprintf (file, "#%i", BLOCK_NUMBER (origin));
627 fprintf (file, " \n");
628 for (var = BLOCK_VARS (scope); var; var = TREE_CHAIN (var))
633 if ((ann = var_ann (var))
637 fprintf (file, "%*s",indent, "");
638 print_generic_decl (file, var, flags);
639 fprintf (file, "%s\n", used ? "" : " (unused)");
641 for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++)
643 fprintf (file, "%*s",indent, "");
644 print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i),
646 fprintf (file, " (nonlocalized)\n");
648 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
649 dump_scope_block (file, indent + 2, t, flags);
650 fprintf (file, "\n%*s}\n",indent, "");
653 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
654 is as in print_generic_expr. */
657 debug_scope_block (tree scope, int flags)
659 dump_scope_block (stderr, 0, scope, flags);
663 /* Dump the tree of lexical scopes of current_function_decl to FILE.
664 FLAGS is as in print_generic_expr. */
667 dump_scope_blocks (FILE *file, int flags)
669 dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags);
673 /* Dump the tree of lexical scopes of current_function_decl to stderr.
674 FLAGS is as in print_generic_expr. */
677 debug_scope_blocks (int flags)
679 dump_scope_blocks (stderr, flags);
682 /* Remove local variables that are not referenced in the IL. */
685 remove_unused_locals (void)
689 referenced_var_iterator rvi;
691 bitmap global_unused_vars = NULL;
692 unsigned srcidx, dstidx, num;
694 /* Removing declarations from lexical blocks when not optimizing is
695 not only a waste of time, it actually causes differences in stack
700 mark_scope_block_unused (DECL_INITIAL (current_function_decl));
702 /* Assume all locals are unused. */
703 FOR_EACH_REFERENCED_VAR (t, rvi)
704 var_ann (t)->used = false;
706 /* Walk the CFG marking all referenced symbols. */
709 gimple_stmt_iterator gsi;
714 /* Walk the statements. */
715 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
717 gimple stmt = gsi_stmt (gsi);
718 tree b = gimple_block (stmt);
720 if (is_gimple_debug (stmt))
724 TREE_USED (b) = true;
726 for (i = 0; i < gimple_num_ops (stmt); i++)
727 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i), NULL);
730 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
735 gimple phi = gsi_stmt (gsi);
737 /* No point processing globals. */
738 if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi))))
741 def = gimple_phi_result (phi);
742 mark_all_vars_used (&def, NULL);
744 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
746 tree arg = USE_FROM_PTR (arg_p);
747 mark_all_vars_used (&arg, NULL);
751 FOR_EACH_EDGE (e, ei, bb->succs)
753 TREE_USED (e->goto_block) = true;
756 cfun->has_local_explicit_reg_vars = false;
758 /* Remove unmarked local vars from local_decls. */
759 num = VEC_length (tree, cfun->local_decls);
760 for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++)
762 var = VEC_index (tree, cfun->local_decls, srcidx);
763 if (TREE_CODE (var) != FUNCTION_DECL
764 && (!(ann = var_ann (var))
767 if (is_global_var (var))
769 if (global_unused_vars == NULL)
770 global_unused_vars = BITMAP_ALLOC (NULL);
771 bitmap_set_bit (global_unused_vars, DECL_UID (var));
776 else if (TREE_CODE (var) == VAR_DECL
777 && DECL_HARD_REGISTER (var)
778 && !is_global_var (var))
779 cfun->has_local_explicit_reg_vars = true;
781 if (srcidx != dstidx)
782 VEC_replace (tree, cfun->local_decls, dstidx, var);
786 VEC_truncate (tree, cfun->local_decls, dstidx);
788 /* Remove unmarked global vars from local_decls. */
789 if (global_unused_vars != NULL)
793 FOR_EACH_LOCAL_DECL (cfun, ix, var)
794 if (TREE_CODE (var) == VAR_DECL
795 && is_global_var (var)
796 && (ann = var_ann (var)) != NULL
798 mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars);
800 num = VEC_length (tree, cfun->local_decls);
801 for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++)
803 var = VEC_index (tree, cfun->local_decls, srcidx);
804 if (TREE_CODE (var) == VAR_DECL
805 && is_global_var (var)
806 && bitmap_bit_p (global_unused_vars, DECL_UID (var)))
809 if (srcidx != dstidx)
810 VEC_replace (tree, cfun->local_decls, dstidx, var);
814 VEC_truncate (tree, cfun->local_decls, dstidx);
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)
825 && TREE_CODE (t) != PARM_DECL
826 && TREE_CODE (t) != RESULT_DECL
827 && !(ann = var_ann (t))->used
829 && !TREE_ADDRESSABLE (t))
830 remove_referenced_var (t);
831 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl));
832 if (dump_file && (dump_flags & TDF_DETAILS))
834 fprintf (dump_file, "Scope blocks after cleanups:\n");
835 dump_scope_blocks (dump_file, dump_flags);
840 /* Allocate and return a new live range information object base on MAP. */
842 static tree_live_info_p
843 new_tree_live_info (var_map map)
845 tree_live_info_p live;
848 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
850 live->num_blocks = last_basic_block;
852 live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
853 for (x = 0; x < (unsigned)last_basic_block; x++)
854 live->livein[x] = BITMAP_ALLOC (NULL);
856 live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
857 for (x = 0; x < (unsigned)last_basic_block; x++)
858 live->liveout[x] = BITMAP_ALLOC (NULL);
860 live->work_stack = XNEWVEC (int, last_basic_block);
861 live->stack_top = live->work_stack;
863 live->global = BITMAP_ALLOC (NULL);
868 /* Free storage for live range info object LIVE. */
871 delete_tree_live_info (tree_live_info_p live)
875 BITMAP_FREE (live->global);
876 free (live->work_stack);
878 for (x = live->num_blocks - 1; x >= 0; x--)
879 BITMAP_FREE (live->liveout[x]);
880 free (live->liveout);
882 for (x = live->num_blocks - 1; x >= 0; x--)
883 BITMAP_FREE (live->livein[x]);
890 /* Visit basic block BB and propagate any required live on entry bits from
891 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
892 TMP is a temporary work bitmap which is passed in to avoid reallocating
896 loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
904 gcc_assert (!TEST_BIT (visited, bb->index));
906 SET_BIT (visited, bb->index);
907 loe = live_on_entry (live, bb);
909 FOR_EACH_EDGE (e, ei, bb->preds)
912 if (pred_bb == ENTRY_BLOCK_PTR)
914 /* TMP is variables live-on-entry from BB that aren't defined in the
915 predecessor block. This should be the live on entry vars to pred.
916 Note that liveout is the DEFs in a block while live on entry is
918 bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]);
920 /* Add these bits to live-on-entry for the pred. if there are any
921 changes, and pred_bb has been visited already, add it to the
923 change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
924 if (TEST_BIT (visited, pred_bb->index) && change)
926 RESET_BIT (visited, pred_bb->index);
927 *(live->stack_top)++ = pred_bb->index;
933 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
934 of all the variables. */
937 live_worklist (tree_live_info_p live)
941 sbitmap visited = sbitmap_alloc (last_basic_block + 1);
942 bitmap tmp = BITMAP_ALLOC (NULL);
944 sbitmap_zero (visited);
946 /* Visit all the blocks in reverse order and propagate live on entry values
947 into the predecessors blocks. */
948 FOR_EACH_BB_REVERSE (bb)
949 loe_visit_block (live, bb, visited, tmp);
951 /* Process any blocks which require further iteration. */
952 while (live->stack_top != live->work_stack)
954 b = *--(live->stack_top);
955 loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
959 sbitmap_free (visited);
963 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
964 links. Set the live on entry fields in LIVE. Def's are marked temporarily
965 in the liveout vector. */
968 set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
973 basic_block def_bb = NULL;
974 imm_use_iterator imm_iter;
977 p = var_to_partition (live->map, ssa_name);
978 if (p == NO_PARTITION)
981 stmt = SSA_NAME_DEF_STMT (ssa_name);
984 def_bb = gimple_bb (stmt);
985 /* Mark defs in liveout bitmap temporarily. */
987 bitmap_set_bit (live->liveout[def_bb->index], p);
990 def_bb = ENTRY_BLOCK_PTR;
992 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
993 add it to the list of live on entry blocks. */
994 FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
996 gimple use_stmt = USE_STMT (use);
997 basic_block add_block = NULL;
999 if (gimple_code (use_stmt) == GIMPLE_PHI)
1001 /* Uses in PHI's are considered to be live at exit of the SRC block
1002 as this is where a copy would be inserted. Check to see if it is
1003 defined in that block, or whether its live on entry. */
1004 int index = PHI_ARG_INDEX_FROM_USE (use);
1005 edge e = gimple_phi_arg_edge (use_stmt, index);
1006 if (e->src != ENTRY_BLOCK_PTR)
1008 if (e->src != def_bb)
1012 else if (is_gimple_debug (use_stmt))
1016 /* If its not defined in this block, its live on entry. */
1017 basic_block use_bb = gimple_bb (use_stmt);
1018 if (use_bb != def_bb)
1022 /* If there was a live on entry use, set the bit. */
1026 bitmap_set_bit (live->livein[add_block->index], p);
1030 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1031 on entry blocks between the def and all the uses. */
1033 bitmap_set_bit (live->global, p);
1037 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1040 calculate_live_on_exit (tree_live_info_p liveinfo)
1046 /* live on entry calculations used liveout vectors for defs, clear them. */
1048 bitmap_clear (liveinfo->liveout[bb->index]);
1050 /* Set all the live-on-exit bits for uses in PHIs. */
1053 gimple_stmt_iterator gsi;
1056 /* Mark the PHI arguments which are live on exit to the pred block. */
1057 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1059 gimple phi = gsi_stmt (gsi);
1060 for (i = 0; i < gimple_phi_num_args (phi); i++)
1062 tree t = PHI_ARG_DEF (phi, i);
1065 if (TREE_CODE (t) != SSA_NAME)
1068 p = var_to_partition (liveinfo->map, t);
1069 if (p == NO_PARTITION)
1071 e = gimple_phi_arg_edge (phi, i);
1072 if (e->src != ENTRY_BLOCK_PTR)
1073 bitmap_set_bit (liveinfo->liveout[e->src->index], p);
1077 /* Add each successors live on entry to this bock live on exit. */
1078 FOR_EACH_EDGE (e, ei, bb->succs)
1079 if (e->dest != EXIT_BLOCK_PTR)
1080 bitmap_ior_into (liveinfo->liveout[bb->index],
1081 live_on_entry (liveinfo, e->dest));
1086 /* Given partition map MAP, calculate all the live on entry bitmaps for
1087 each partition. Return a new live info object. */
1090 calculate_live_ranges (var_map map)
1094 tree_live_info_p live;
1096 live = new_tree_live_info (map);
1097 for (i = 0; i < num_var_partitions (map); i++)
1099 var = partition_to_var (map, i);
1100 if (var != NULL_TREE)
1101 set_var_live_on_entry (var, live);
1104 live_worklist (live);
1106 #ifdef ENABLE_CHECKING
1107 verify_live_on_entry (live);
1110 calculate_live_on_exit (live);
1115 /* Output partition map MAP to file F. */
1118 dump_var_map (FILE *f, var_map map)
1124 fprintf (f, "\nPartition map \n\n");
1126 for (x = 0; x < map->num_partitions; x++)
1128 if (map->view_to_partition != NULL)
1129 p = map->view_to_partition[x];
1133 if (ssa_name (p) == NULL_TREE)
1137 for (y = 1; y < num_ssa_names; y++)
1139 p = partition_find (map->var_partition, y);
1140 if (map->partition_to_view)
1141 p = map->partition_to_view[p];
1146 fprintf(f, "Partition %d (", x);
1147 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1150 fprintf (f, "%d ", y);
1160 /* Output live range info LIVE to file F, controlled by FLAG. */
1163 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1167 var_map map = live->map;
1170 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1174 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1175 EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
1177 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1184 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1188 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1189 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1191 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1200 #ifdef ENABLE_CHECKING
1201 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1204 register_ssa_partition_check (tree ssa_var)
1206 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1207 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1209 fprintf (stderr, "Illegally registering a virtual SSA name :");
1210 print_generic_expr (stderr, ssa_var, TDF_SLIM);
1211 fprintf (stderr, " in the SSA->Normal phase.\n");
1212 internal_error ("SSA corruption");
1217 /* Verify that the info in LIVE matches the current cfg. */
1220 verify_live_on_entry (tree_live_info_p live)
1229 var_map map = live->map;
1231 /* Check for live on entry partitions and report those with a DEF in
1232 the program. This will typically mean an optimization has done
1234 bb = ENTRY_BLOCK_PTR;
1236 FOR_EACH_EDGE (e, ei, bb->succs)
1238 int entry_block = e->dest->index;
1239 if (e->dest == EXIT_BLOCK_PTR)
1241 for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1246 var = partition_to_var (map, i);
1247 stmt = SSA_NAME_DEF_STMT (var);
1248 tmp = gimple_bb (stmt);
1249 d = gimple_default_def (cfun, SSA_NAME_VAR (var));
1251 loe = live_on_entry (live, e->dest);
1252 if (loe && bitmap_bit_p (loe, i))
1254 if (!gimple_nop_p (stmt))
1257 print_generic_expr (stderr, var, TDF_SLIM);
1258 fprintf (stderr, " is defined ");
1260 fprintf (stderr, " in BB%d, ", tmp->index);
1261 fprintf (stderr, "by:\n");
1262 print_gimple_stmt (stderr, stmt, 0, TDF_SLIM);
1263 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1265 fprintf (stderr, " So it appears to have multiple defs.\n");
1272 print_generic_expr (stderr, var, TDF_SLIM);
1273 fprintf (stderr, " is live-on-entry to BB%d ",
1277 fprintf (stderr, " but is not the default def of ");
1278 print_generic_expr (stderr, d, TDF_SLIM);
1279 fprintf (stderr, "\n");
1282 fprintf (stderr, " and there is no default def.\n");
1289 /* The only way this var shouldn't be marked live on entry is
1290 if it occurs in a PHI argument of the block. */
1293 gimple_stmt_iterator gsi;
1294 for (gsi = gsi_start_phis (e->dest);
1295 !gsi_end_p (gsi) && !ok;
1298 gimple phi = gsi_stmt (gsi);
1299 for (z = 0; z < gimple_phi_num_args (phi); z++)
1300 if (var == gimple_phi_arg_def (phi, z))
1309 print_generic_expr (stderr, var, TDF_SLIM);
1310 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1312 fprintf (stderr, "but it is a default def so it should be.\n");
1316 gcc_assert (num <= 0);