re PR testsuite/40567 (Revision 149002 caused many failures)
[official-gcc.git] / gcc / tree-ssa-live.c
bloba710c65d3b4384a0898ace62358fcc4ceb7c70f8
1 /* Liveness for SSA trees.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009 Free Software Foundation,
3 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)
11 any later version.
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/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "diagnostic.h"
28 #include "bitmap.h"
29 #include "tree-flow.h"
30 #include "tree-dump.h"
31 #include "tree-ssa-live.h"
32 #include "toplev.h"
33 #include "debug.h"
34 #include "flags.h"
36 #ifdef ENABLE_CHECKING
37 static void verify_live_on_entry (tree_live_info_p);
38 #endif
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. */
57 static void
58 var_map_base_init (var_map map)
60 int x, num_part, num;
61 tree var;
62 var_ann_t ann;
64 num = 0;
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);
73 else
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);
84 ann = var_ann (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++)
107 tree var2;
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);
112 #endif
116 /* Remove the base table in MAP. */
118 static void
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. */
132 var_map
133 init_var_map (int size)
135 var_map map;
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;
147 return map;
151 /* Free memory associated with MAP. */
153 void
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);
162 free (map);
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)
173 int p1, p2, p3;
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);
188 if (p1 == p2)
189 p3 = p1;
190 else
191 p3 = partition_union (map->var_partition, p1, p2);
193 if (map->partition_to_view)
194 p3 = map->partition_to_view[p3];
196 return 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
204 denser.
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
220 varmap. */
222 static bitmap
223 partition_view_init (var_map map)
225 bitmap used;
226 int tmp;
227 unsigned int x;
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;
254 return used;
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. */
263 static void
264 partition_view_fini (var_map map, bitmap selected)
266 bitmap_iterator bi;
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. */
275 if (count < limit)
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));
281 i = 0;
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;
287 i++;
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. */
300 extern void
301 partition_view_normal (var_map map, bool want_bases)
303 bitmap used;
305 used = partition_view_init (map);
306 partition_view_fini (map, used);
308 if (want_bases)
309 var_map_base_init (map);
310 else
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
317 as well. */
319 extern void
320 partition_view_bitmap (var_map map, bitmap only, bool want_bases)
322 bitmap used;
323 bitmap new_partitions = BITMAP_ALLOC (NULL);
324 unsigned x, p;
325 bitmap_iterator bi;
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);
336 BITMAP_FREE (used);
337 if (want_bases)
338 var_map_base_init (map);
339 else
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. */
348 static tree
349 mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data)
351 tree t = *tp;
352 enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));
353 tree b;
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);
369 *walk_subtrees = 0;
370 return NULL;
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);
382 set_is_used (t);
385 if (IS_TYPE_OR_DECL_P (t))
386 *walk_subtrees = 0;
388 return NULL;
391 /* Mark the scope block SCOPE and its subblocks unused when they can be
392 possibly eliminated if dead. */
394 static void
395 mark_scope_block_unused (tree scope)
397 tree t;
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. */
418 static bool
419 remove_unused_scope_block_p (tree scope)
421 tree *t, *next;
422 bool unused = !TREE_USED (scope);
423 var_ann_t ann;
424 int nsubblocks = 0;
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)
437 unused = false;
439 /* If a decl has a value expr, we need to instantiate it
440 regardless of debug info generation, to avoid codegen
441 differences in memory overlap tests. update_equiv_regs() may
442 indirectly call validate_equiv_mem() to test whether a
443 SET_DEST overlaps with others, and if the value expr changes
444 by virtual register instantiation, we may get end up with
445 different results. */
446 else if (TREE_CODE (*t) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*t))
447 unused = false;
449 /* Remove everything we don't generate debug info for. */
450 else if (DECL_IGNORED_P (*t))
452 *t = TREE_CHAIN (*t);
453 next = t;
456 /* When we are outputting debug info, we usually want to output
457 info about optimized-out variables in the scope blocks.
458 Exception are the scope blocks not containing any instructions
459 at all so user can't get into the scopes at first place. */
460 else if ((ann = var_ann (*t)) != NULL
461 && ann->used)
462 unused = false;
464 /* When we are not doing full debug info, we however can keep around
465 only the used variables for cfgexpand's memory packing saving quite
466 a lot of memory.
468 For sake of -g3, we keep around those vars but we don't count this as
469 use of block, so innermost block with no used vars and no instructions
470 can be considered dead. We only want to keep around blocks user can
471 breakpoint into and ask about value of optimized out variables.
473 Similarly we need to keep around types at least until all variables of
474 all nested blocks are gone. We track no information on whether given
475 type is used or not. */
477 else if (debug_info_level == DINFO_LEVEL_NORMAL
478 || debug_info_level == DINFO_LEVEL_VERBOSE
479 /* Removing declarations before inlining is going to affect
480 DECL_UID that in turn is going to affect hashtables and
481 code generation. */
482 || !cfun->after_inlining)
484 else
486 *t = TREE_CHAIN (*t);
487 next = t;
491 for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
492 if (remove_unused_scope_block_p (*t))
494 if (BLOCK_SUBBLOCKS (*t))
496 tree next = BLOCK_CHAIN (*t);
497 tree supercontext = BLOCK_SUPERCONTEXT (*t);
499 *t = BLOCK_SUBBLOCKS (*t);
500 while (BLOCK_CHAIN (*t))
502 BLOCK_SUPERCONTEXT (*t) = supercontext;
503 t = &BLOCK_CHAIN (*t);
505 BLOCK_CHAIN (*t) = next;
506 BLOCK_SUPERCONTEXT (*t) = supercontext;
507 t = &BLOCK_CHAIN (*t);
508 nsubblocks ++;
510 else
511 *t = BLOCK_CHAIN (*t);
513 else
515 t = &BLOCK_CHAIN (*t);
516 nsubblocks ++;
520 if (!unused)
522 /* Outer scope is always used. */
523 else if (!BLOCK_SUPERCONTEXT (scope)
524 || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)
525 unused = false;
526 /* Innermost blocks with no live variables nor statements can be always
527 eliminated. */
528 else if (!nsubblocks)
530 /* If there are live subblocks and we still have some unused variables
531 or types declared, we must keep them.
532 Before inliing we must not depend on debug info verbosity to keep
533 DECL_UIDs stable. */
534 else if (!cfun->after_inlining && BLOCK_VARS (scope))
535 unused = false;
536 /* For terse debug info we can eliminate info on unused variables. */
537 else if (debug_info_level == DINFO_LEVEL_NONE
538 || debug_info_level == DINFO_LEVEL_TERSE)
540 /* Even for -g0/-g1 don't prune outer scopes from artificial
541 functions, otherwise diagnostics using tree_nonartificial_location
542 will not be emitted properly. */
543 if (inlined_function_outer_scope_p (scope))
545 tree ao = scope;
547 while (ao
548 && TREE_CODE (ao) == BLOCK
549 && BLOCK_ABSTRACT_ORIGIN (ao) != ao)
550 ao = BLOCK_ABSTRACT_ORIGIN (ao);
551 if (ao
552 && TREE_CODE (ao) == FUNCTION_DECL
553 && DECL_DECLARED_INLINE_P (ao)
554 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao)))
555 unused = false;
558 else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope))
559 unused = false;
560 /* See if this block is important for representation of inlined function.
561 Inlined functions are always represented by block with
562 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
563 set... */
564 else if (inlined_function_outer_scope_p (scope))
565 unused = false;
566 else
567 /* Verfify that only blocks with source location set
568 are entry points to the inlined functions. */
569 gcc_assert (BLOCK_SOURCE_LOCATION (scope) == UNKNOWN_LOCATION);
571 TREE_USED (scope) = !unused;
572 return unused;
575 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
576 eliminated during the tree->rtl conversion process. */
578 static inline void
579 mark_all_vars_used (tree *expr_p, void *data)
581 walk_tree (expr_p, mark_all_vars_used_1, data, NULL);
585 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
586 indentation level and FLAGS is as in print_generic_expr. */
588 static void
589 dump_scope_block (FILE *file, int indent, tree scope, int flags)
591 tree var, t;
592 unsigned int i;
594 fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope),
595 TREE_USED (scope) ? "" : " (unused)",
596 BLOCK_ABSTRACT (scope) ? " (abstract)": "");
597 if (BLOCK_SOURCE_LOCATION (scope) != UNKNOWN_LOCATION)
599 expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope));
600 fprintf (file, " %s:%i", s.file, s.line);
602 if (BLOCK_ABSTRACT_ORIGIN (scope))
604 tree origin = block_ultimate_origin (scope);
605 if (origin)
607 fprintf (file, " Originating from :");
608 if (DECL_P (origin))
609 print_generic_decl (file, origin, flags);
610 else
611 fprintf (file, "#%i", BLOCK_NUMBER (origin));
614 fprintf (file, " \n");
615 for (var = BLOCK_VARS (scope); var; var = TREE_CHAIN (var))
617 bool used = false;
618 var_ann_t ann;
620 if ((ann = var_ann (var))
621 && ann->used)
622 used = true;
624 fprintf (file, "%*s",indent, "");
625 print_generic_decl (file, var, flags);
626 fprintf (file, "%s\n", used ? "" : " (unused)");
628 for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++)
630 fprintf (file, "%*s",indent, "");
631 print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i),
632 flags);
633 fprintf (file, " (nonlocalized)\n");
635 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
636 dump_scope_block (file, indent + 2, t, flags);
637 fprintf (file, "\n%*s}\n",indent, "");
641 /* Dump the tree of lexical scopes of current_function_decl to FILE.
642 FLAGS is as in print_generic_expr. */
644 void
645 dump_scope_blocks (FILE *file, int flags)
647 dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags);
651 /* Dump the tree of lexical scopes of current_function_decl to stderr.
652 FLAGS is as in print_generic_expr. */
654 void
655 debug_scope_blocks (int flags)
657 dump_scope_blocks (stderr, flags);
660 /* Remove local variables that are not referenced in the IL. */
662 void
663 remove_unused_locals (void)
665 basic_block bb;
666 tree t, *cell;
667 referenced_var_iterator rvi;
668 var_ann_t ann;
669 bitmap global_unused_vars = NULL;
671 /* Removing declarations from lexical blocks when not optimizing is
672 not only a waste of time, it actually causes differences in stack
673 layout. */
674 if (!optimize)
675 return;
677 mark_scope_block_unused (DECL_INITIAL (current_function_decl));
679 /* Assume all locals are unused. */
680 FOR_EACH_REFERENCED_VAR (t, rvi)
681 var_ann (t)->used = false;
683 /* Walk the CFG marking all referenced symbols. */
684 FOR_EACH_BB (bb)
686 gimple_stmt_iterator gsi;
687 size_t i;
688 edge_iterator ei;
689 edge e;
691 /* Walk the statements. */
692 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
694 gimple stmt = gsi_stmt (gsi);
695 tree b = gimple_block (stmt);
697 if (b)
698 TREE_USED (b) = true;
700 for (i = 0; i < gimple_num_ops (stmt); i++)
701 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i), NULL);
704 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
706 use_operand_p arg_p;
707 ssa_op_iter i;
708 tree def;
709 gimple phi = gsi_stmt (gsi);
711 /* No point processing globals. */
712 if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi))))
713 continue;
715 def = gimple_phi_result (phi);
716 mark_all_vars_used (&def, NULL);
718 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
720 tree arg = USE_FROM_PTR (arg_p);
721 mark_all_vars_used (&arg, NULL);
725 FOR_EACH_EDGE (e, ei, bb->succs)
726 if (e->goto_locus)
727 TREE_USED (e->goto_block) = true;
730 cfun->has_local_explicit_reg_vars = false;
732 /* Remove unmarked local vars from local_decls. */
733 for (cell = &cfun->local_decls; *cell; )
735 tree var = TREE_VALUE (*cell);
737 if (TREE_CODE (var) != FUNCTION_DECL
738 && (!(ann = var_ann (var))
739 || !ann->used))
741 if (is_global_var (var))
743 if (global_unused_vars == NULL)
744 global_unused_vars = BITMAP_ALLOC (NULL);
745 bitmap_set_bit (global_unused_vars, DECL_UID (var));
747 else
749 *cell = TREE_CHAIN (*cell);
750 continue;
753 else if (TREE_CODE (var) == VAR_DECL
754 && DECL_HARD_REGISTER (var)
755 && !is_global_var (var))
756 cfun->has_local_explicit_reg_vars = true;
757 cell = &TREE_CHAIN (*cell);
760 /* Remove unmarked global vars from local_decls. */
761 if (global_unused_vars != NULL)
763 for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
765 tree var = TREE_VALUE (t);
767 if (TREE_CODE (var) == VAR_DECL
768 && is_global_var (var)
769 && (ann = var_ann (var)) != NULL
770 && ann->used)
771 mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars);
774 for (cell = &cfun->local_decls; *cell; )
776 tree var = TREE_VALUE (*cell);
778 if (TREE_CODE (var) == VAR_DECL
779 && is_global_var (var)
780 && bitmap_bit_p (global_unused_vars, DECL_UID (var)))
781 *cell = TREE_CHAIN (*cell);
782 else
783 cell = &TREE_CHAIN (*cell);
785 BITMAP_FREE (global_unused_vars);
788 /* Remove unused variables from REFERENCED_VARs. As a special
789 exception keep the variables that are believed to be aliased.
790 Those can't be easily removed from the alias sets and operand
791 caches. They will be removed shortly after the next may_alias
792 pass is performed. */
793 FOR_EACH_REFERENCED_VAR (t, rvi)
794 if (!is_global_var (t)
795 && TREE_CODE (t) != PARM_DECL
796 && TREE_CODE (t) != RESULT_DECL
797 && !(ann = var_ann (t))->used
798 && !TREE_ADDRESSABLE (t))
799 remove_referenced_var (t);
800 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl));
801 if (dump_file && (dump_flags & TDF_DETAILS))
803 fprintf (dump_file, "Scope blocks after cleanups:\n");
804 dump_scope_blocks (dump_file, dump_flags);
809 /* Allocate and return a new live range information object base on MAP. */
811 static tree_live_info_p
812 new_tree_live_info (var_map map)
814 tree_live_info_p live;
815 unsigned x;
817 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
818 live->map = map;
819 live->num_blocks = last_basic_block;
821 live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
822 for (x = 0; x < (unsigned)last_basic_block; x++)
823 live->livein[x] = BITMAP_ALLOC (NULL);
825 live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
826 for (x = 0; x < (unsigned)last_basic_block; x++)
827 live->liveout[x] = BITMAP_ALLOC (NULL);
829 live->work_stack = XNEWVEC (int, last_basic_block);
830 live->stack_top = live->work_stack;
832 live->global = BITMAP_ALLOC (NULL);
833 return live;
837 /* Free storage for live range info object LIVE. */
839 void
840 delete_tree_live_info (tree_live_info_p live)
842 int x;
844 BITMAP_FREE (live->global);
845 free (live->work_stack);
847 for (x = live->num_blocks - 1; x >= 0; x--)
848 BITMAP_FREE (live->liveout[x]);
849 free (live->liveout);
851 for (x = live->num_blocks - 1; x >= 0; x--)
852 BITMAP_FREE (live->livein[x]);
853 free (live->livein);
855 free (live);
859 /* Visit basic block BB and propagate any required live on entry bits from
860 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
861 TMP is a temporary work bitmap which is passed in to avoid reallocating
862 it each time. */
864 static void
865 loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
866 bitmap tmp)
868 edge e;
869 bool change;
870 edge_iterator ei;
871 basic_block pred_bb;
872 bitmap loe;
873 gcc_assert (!TEST_BIT (visited, bb->index));
875 SET_BIT (visited, bb->index);
876 loe = live_on_entry (live, bb);
878 FOR_EACH_EDGE (e, ei, bb->preds)
880 pred_bb = e->src;
881 if (pred_bb == ENTRY_BLOCK_PTR)
882 continue;
883 /* TMP is variables live-on-entry from BB that aren't defined in the
884 predecessor block. This should be the live on entry vars to pred.
885 Note that liveout is the DEFs in a block while live on entry is
886 being calculated. */
887 bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]);
889 /* Add these bits to live-on-entry for the pred. if there are any
890 changes, and pred_bb has been visited already, add it to the
891 revisit stack. */
892 change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
893 if (TEST_BIT (visited, pred_bb->index) && change)
895 RESET_BIT (visited, pred_bb->index);
896 *(live->stack_top)++ = pred_bb->index;
902 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
903 of all the variables. */
905 static void
906 live_worklist (tree_live_info_p live)
908 unsigned b;
909 basic_block bb;
910 sbitmap visited = sbitmap_alloc (last_basic_block + 1);
911 bitmap tmp = BITMAP_ALLOC (NULL);
913 sbitmap_zero (visited);
915 /* Visit all the blocks in reverse order and propagate live on entry values
916 into the predecessors blocks. */
917 FOR_EACH_BB_REVERSE (bb)
918 loe_visit_block (live, bb, visited, tmp);
920 /* Process any blocks which require further iteration. */
921 while (live->stack_top != live->work_stack)
923 b = *--(live->stack_top);
924 loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
927 BITMAP_FREE (tmp);
928 sbitmap_free (visited);
932 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
933 links. Set the live on entry fields in LIVE. Def's are marked temporarily
934 in the liveout vector. */
936 static void
937 set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
939 int p;
940 gimple stmt;
941 use_operand_p use;
942 basic_block def_bb = NULL;
943 imm_use_iterator imm_iter;
944 bool global = false;
946 p = var_to_partition (live->map, ssa_name);
947 if (p == NO_PARTITION)
948 return;
950 stmt = SSA_NAME_DEF_STMT (ssa_name);
951 if (stmt)
953 def_bb = gimple_bb (stmt);
954 /* Mark defs in liveout bitmap temporarily. */
955 if (def_bb)
956 bitmap_set_bit (live->liveout[def_bb->index], p);
958 else
959 def_bb = ENTRY_BLOCK_PTR;
961 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
962 add it to the list of live on entry blocks. */
963 FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
965 gimple use_stmt = USE_STMT (use);
966 basic_block add_block = NULL;
968 if (gimple_code (use_stmt) == GIMPLE_PHI)
970 /* Uses in PHI's are considered to be live at exit of the SRC block
971 as this is where a copy would be inserted. Check to see if it is
972 defined in that block, or whether its live on entry. */
973 int index = PHI_ARG_INDEX_FROM_USE (use);
974 edge e = gimple_phi_arg_edge (use_stmt, index);
975 if (e->src != ENTRY_BLOCK_PTR)
977 if (e->src != def_bb)
978 add_block = e->src;
981 else
983 /* If its not defined in this block, its live on entry. */
984 basic_block use_bb = gimple_bb (use_stmt);
985 if (use_bb != def_bb)
986 add_block = use_bb;
989 /* If there was a live on entry use, set the bit. */
990 if (add_block)
992 global = true;
993 bitmap_set_bit (live->livein[add_block->index], p);
997 /* If SSA_NAME is live on entry to at least one block, fill in all the live
998 on entry blocks between the def and all the uses. */
999 if (global)
1000 bitmap_set_bit (live->global, p);
1004 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1006 void
1007 calculate_live_on_exit (tree_live_info_p liveinfo)
1009 basic_block bb;
1010 edge e;
1011 edge_iterator ei;
1013 /* live on entry calculations used liveout vectors for defs, clear them. */
1014 FOR_EACH_BB (bb)
1015 bitmap_clear (liveinfo->liveout[bb->index]);
1017 /* Set all the live-on-exit bits for uses in PHIs. */
1018 FOR_EACH_BB (bb)
1020 gimple_stmt_iterator gsi;
1021 size_t i;
1023 /* Mark the PHI arguments which are live on exit to the pred block. */
1024 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1026 gimple phi = gsi_stmt (gsi);
1027 for (i = 0; i < gimple_phi_num_args (phi); i++)
1029 tree t = PHI_ARG_DEF (phi, i);
1030 int p;
1032 if (TREE_CODE (t) != SSA_NAME)
1033 continue;
1035 p = var_to_partition (liveinfo->map, t);
1036 if (p == NO_PARTITION)
1037 continue;
1038 e = gimple_phi_arg_edge (phi, i);
1039 if (e->src != ENTRY_BLOCK_PTR)
1040 bitmap_set_bit (liveinfo->liveout[e->src->index], p);
1044 /* Add each successors live on entry to this bock live on exit. */
1045 FOR_EACH_EDGE (e, ei, bb->succs)
1046 if (e->dest != EXIT_BLOCK_PTR)
1047 bitmap_ior_into (liveinfo->liveout[bb->index],
1048 live_on_entry (liveinfo, e->dest));
1053 /* Given partition map MAP, calculate all the live on entry bitmaps for
1054 each partition. Return a new live info object. */
1056 tree_live_info_p
1057 calculate_live_ranges (var_map map)
1059 tree var;
1060 unsigned i;
1061 tree_live_info_p live;
1063 live = new_tree_live_info (map);
1064 for (i = 0; i < num_var_partitions (map); i++)
1066 var = partition_to_var (map, i);
1067 if (var != NULL_TREE)
1068 set_var_live_on_entry (var, live);
1071 live_worklist (live);
1073 #ifdef ENABLE_CHECKING
1074 verify_live_on_entry (live);
1075 #endif
1077 calculate_live_on_exit (live);
1078 return live;
1082 /* Output partition map MAP to file F. */
1084 void
1085 dump_var_map (FILE *f, var_map map)
1087 int t;
1088 unsigned x, y;
1089 int p;
1091 fprintf (f, "\nPartition map \n\n");
1093 for (x = 0; x < map->num_partitions; x++)
1095 if (map->view_to_partition != NULL)
1096 p = map->view_to_partition[x];
1097 else
1098 p = x;
1100 if (ssa_name (p) == NULL_TREE)
1101 continue;
1103 t = 0;
1104 for (y = 1; y < num_ssa_names; y++)
1106 p = partition_find (map->var_partition, y);
1107 if (map->partition_to_view)
1108 p = map->partition_to_view[p];
1109 if (p == (int)x)
1111 if (t++ == 0)
1113 fprintf(f, "Partition %d (", x);
1114 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1115 fprintf (f, " - ");
1117 fprintf (f, "%d ", y);
1120 if (t != 0)
1121 fprintf (f, ")\n");
1123 fprintf (f, "\n");
1127 /* Output live range info LIVE to file F, controlled by FLAG. */
1129 void
1130 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1132 basic_block bb;
1133 unsigned i;
1134 var_map map = live->map;
1135 bitmap_iterator bi;
1137 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1139 FOR_EACH_BB (bb)
1141 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1142 EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
1144 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1145 fprintf (f, " ");
1147 fprintf (f, "\n");
1151 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1153 FOR_EACH_BB (bb)
1155 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1156 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1158 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1159 fprintf (f, " ");
1161 fprintf (f, "\n");
1167 #ifdef ENABLE_CHECKING
1168 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1170 void
1171 register_ssa_partition_check (tree ssa_var)
1173 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1174 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1176 fprintf (stderr, "Illegally registering a virtual SSA name :");
1177 print_generic_expr (stderr, ssa_var, TDF_SLIM);
1178 fprintf (stderr, " in the SSA->Normal phase.\n");
1179 internal_error ("SSA corruption");
1184 /* Verify that the info in LIVE matches the current cfg. */
1186 static void
1187 verify_live_on_entry (tree_live_info_p live)
1189 unsigned i;
1190 tree var;
1191 gimple stmt;
1192 basic_block bb;
1193 edge e;
1194 int num;
1195 edge_iterator ei;
1196 var_map map = live->map;
1198 /* Check for live on entry partitions and report those with a DEF in
1199 the program. This will typically mean an optimization has done
1200 something wrong. */
1201 bb = ENTRY_BLOCK_PTR;
1202 num = 0;
1203 FOR_EACH_EDGE (e, ei, bb->succs)
1205 int entry_block = e->dest->index;
1206 if (e->dest == EXIT_BLOCK_PTR)
1207 continue;
1208 for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1210 basic_block tmp;
1211 tree d;
1212 bitmap loe;
1213 var = partition_to_var (map, i);
1214 stmt = SSA_NAME_DEF_STMT (var);
1215 tmp = gimple_bb (stmt);
1216 d = gimple_default_def (cfun, SSA_NAME_VAR (var));
1218 loe = live_on_entry (live, e->dest);
1219 if (loe && bitmap_bit_p (loe, i))
1221 if (!gimple_nop_p (stmt))
1223 num++;
1224 print_generic_expr (stderr, var, TDF_SLIM);
1225 fprintf (stderr, " is defined ");
1226 if (tmp)
1227 fprintf (stderr, " in BB%d, ", tmp->index);
1228 fprintf (stderr, "by:\n");
1229 print_gimple_stmt (stderr, stmt, 0, TDF_SLIM);
1230 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1231 entry_block);
1232 fprintf (stderr, " So it appears to have multiple defs.\n");
1234 else
1236 if (d != var)
1238 num++;
1239 print_generic_expr (stderr, var, TDF_SLIM);
1240 fprintf (stderr, " is live-on-entry to BB%d ",
1241 entry_block);
1242 if (d)
1244 fprintf (stderr, " but is not the default def of ");
1245 print_generic_expr (stderr, d, TDF_SLIM);
1246 fprintf (stderr, "\n");
1248 else
1249 fprintf (stderr, " and there is no default def.\n");
1253 else
1254 if (d == var)
1256 /* The only way this var shouldn't be marked live on entry is
1257 if it occurs in a PHI argument of the block. */
1258 size_t z;
1259 bool ok = false;
1260 gimple_stmt_iterator gsi;
1261 for (gsi = gsi_start_phis (e->dest);
1262 !gsi_end_p (gsi) && !ok;
1263 gsi_next (&gsi))
1265 gimple phi = gsi_stmt (gsi);
1266 for (z = 0; z < gimple_phi_num_args (phi); z++)
1267 if (var == gimple_phi_arg_def (phi, z))
1269 ok = true;
1270 break;
1273 if (ok)
1274 continue;
1275 num++;
1276 print_generic_expr (stderr, var, TDF_SLIM);
1277 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1278 entry_block);
1279 fprintf (stderr, "but it is a default def so it should be.\n");
1283 gcc_assert (num <= 0);
1285 #endif