gcc/
[official-gcc.git] / gcc / tree-ssa-live.c
blob23eaf262c64d1eb6923f7e1ff73ef2ada60fc999
1 /* Liveness for SSA trees.
2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "hash-table.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "gimple-pretty-print.h"
28 #include "bitmap.h"
29 #include "sbitmap.h"
30 #include "basic-block.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "gimple-expr.h"
34 #include "is-a.h"
35 #include "gimple.h"
36 #include "gimple-iterator.h"
37 #include "gimple-ssa.h"
38 #include "tree-phinodes.h"
39 #include "ssa-iterators.h"
40 #include "stringpool.h"
41 #include "tree-ssanames.h"
42 #include "expr.h"
43 #include "tree-dfa.h"
44 #include "timevar.h"
45 #include "dumpfile.h"
46 #include "tree-ssa-live.h"
47 #include "diagnostic-core.h"
48 #include "debug.h"
49 #include "flags.h"
51 #ifdef ENABLE_CHECKING
52 static void verify_live_on_entry (tree_live_info_p);
53 #endif
56 /* VARMAP maintains a mapping from SSA version number to real variables.
58 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
59 only member of it's own partition. Coalescing will attempt to group any
60 ssa_names which occur in a copy or in a PHI node into the same partition.
62 At the end of out-of-ssa, each partition becomes a "real" variable and is
63 rewritten as a compiler variable.
65 The var_map data structure is used to manage these partitions. It allows
66 partitions to be combined, and determines which partition belongs to what
67 ssa_name or variable, and vice versa. */
70 /* Hashtable helpers. */
72 struct tree_int_map_hasher : typed_noop_remove <tree_int_map>
74 typedef tree_int_map value_type;
75 typedef tree_int_map compare_type;
76 static inline hashval_t hash (const value_type *);
77 static inline bool equal (const value_type *, const compare_type *);
80 inline hashval_t
81 tree_int_map_hasher::hash (const value_type *v)
83 return tree_map_base_hash (v);
86 inline bool
87 tree_int_map_hasher::equal (const value_type *v, const compare_type *c)
89 return tree_int_map_eq (v, c);
93 /* This routine will initialize the basevar fields of MAP. */
95 static void
96 var_map_base_init (var_map map)
98 int x, num_part;
99 tree var;
100 struct tree_int_map *m, *mapstorage;
102 num_part = num_var_partitions (map);
103 hash_table<tree_int_map_hasher> tree_to_index (num_part);
104 /* We can have at most num_part entries in the hash tables, so it's
105 enough to allocate so many map elements once, saving some malloc
106 calls. */
107 mapstorage = m = XNEWVEC (struct tree_int_map, num_part);
109 /* If a base table already exists, clear it, otherwise create it. */
110 free (map->partition_to_base_index);
111 map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
113 /* Build the base variable list, and point partitions at their bases. */
114 for (x = 0; x < num_part; x++)
116 struct tree_int_map **slot;
117 unsigned baseindex;
118 var = partition_to_var (map, x);
119 if (SSA_NAME_VAR (var)
120 && (!VAR_P (SSA_NAME_VAR (var))
121 || !DECL_IGNORED_P (SSA_NAME_VAR (var))))
122 m->base.from = SSA_NAME_VAR (var);
123 else
124 /* This restricts what anonymous SSA names we can coalesce
125 as it restricts the sets we compute conflicts for.
126 Using TREE_TYPE to generate sets is the easies as
127 type equivalency also holds for SSA names with the same
128 underlying decl.
130 Check gimple_can_coalesce_p when changing this code. */
131 m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
132 ? TYPE_CANONICAL (TREE_TYPE (var))
133 : TREE_TYPE (var));
134 /* If base variable hasn't been seen, set it up. */
135 slot = tree_to_index.find_slot (m, INSERT);
136 if (!*slot)
138 baseindex = m - mapstorage;
139 m->to = baseindex;
140 *slot = m;
141 m++;
143 else
144 baseindex = (*slot)->to;
145 map->partition_to_base_index[x] = baseindex;
148 map->num_basevars = m - mapstorage;
150 free (mapstorage);
154 /* Remove the base table in MAP. */
156 static void
157 var_map_base_fini (var_map map)
159 /* Free the basevar info if it is present. */
160 if (map->partition_to_base_index != NULL)
162 free (map->partition_to_base_index);
163 map->partition_to_base_index = NULL;
164 map->num_basevars = 0;
167 /* Create a variable partition map of SIZE, initialize and return it. */
169 var_map
170 init_var_map (int size)
172 var_map map;
174 map = (var_map) xmalloc (sizeof (struct _var_map));
175 map->var_partition = partition_new (size);
177 map->partition_to_view = NULL;
178 map->view_to_partition = NULL;
179 map->num_partitions = size;
180 map->partition_size = size;
181 map->num_basevars = 0;
182 map->partition_to_base_index = NULL;
183 return map;
187 /* Free memory associated with MAP. */
189 void
190 delete_var_map (var_map map)
192 var_map_base_fini (map);
193 partition_delete (map->var_partition);
194 free (map->partition_to_view);
195 free (map->view_to_partition);
196 free (map);
200 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
201 Returns the partition which represents the new partition. If the two
202 partitions cannot be combined, NO_PARTITION is returned. */
205 var_union (var_map map, tree var1, tree var2)
207 int p1, p2, p3;
209 gcc_assert (TREE_CODE (var1) == SSA_NAME);
210 gcc_assert (TREE_CODE (var2) == SSA_NAME);
212 /* This is independent of partition_to_view. If partition_to_view is
213 on, then whichever one of these partitions is absorbed will never have a
214 dereference into the partition_to_view array any more. */
216 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
217 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
219 gcc_assert (p1 != NO_PARTITION);
220 gcc_assert (p2 != NO_PARTITION);
222 if (p1 == p2)
223 p3 = p1;
224 else
225 p3 = partition_union (map->var_partition, p1, p2);
227 if (map->partition_to_view)
228 p3 = map->partition_to_view[p3];
230 return 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
238 denser.
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
254 varmap. */
256 static bitmap
257 partition_view_init (var_map map)
259 bitmap used;
260 int tmp;
261 unsigned int x;
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 (ssa_name (tmp) != NULL_TREE && !virtual_operand_p (ssa_name (tmp))
282 && (!has_zero_uses (ssa_name (tmp))
283 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp))))
284 bitmap_set_bit (used, tmp);
287 map->num_partitions = map->partition_size;
288 return used;
292 /* This routine will finalize the view data for MAP based on the partitions
293 set in SELECTED. This is either the same bitmap returned from
294 partition_view_init, or a trimmed down version if some of those partitions
295 were not desired in this view. SELECTED is freed before returning. */
297 static void
298 partition_view_fini (var_map map, bitmap selected)
300 bitmap_iterator bi;
301 unsigned count, i, x, limit;
303 gcc_assert (selected);
305 count = bitmap_count_bits (selected);
306 limit = map->partition_size;
308 /* If its a one-to-one ratio, we don't need any view compaction. */
309 if (count < limit)
311 map->partition_to_view = (int *)xmalloc (limit * sizeof (int));
312 memset (map->partition_to_view, 0xff, (limit * sizeof (int)));
313 map->view_to_partition = (int *)xmalloc (count * sizeof (int));
315 i = 0;
316 /* Give each selected partition an index. */
317 EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)
319 map->partition_to_view[x] = i;
320 map->view_to_partition[i] = x;
321 i++;
323 gcc_assert (i == count);
324 map->num_partitions = i;
327 BITMAP_FREE (selected);
331 /* Create a partition view which includes all the used partitions in MAP. If
332 WANT_BASES is true, create the base variable map as well. */
334 void
335 partition_view_normal (var_map map, bool want_bases)
337 bitmap used;
339 used = partition_view_init (map);
340 partition_view_fini (map, used);
342 if (want_bases)
343 var_map_base_init (map);
344 else
345 var_map_base_fini (map);
349 /* Create a partition view in MAP which includes just partitions which occur in
350 the bitmap ONLY. If WANT_BASES is true, create the base variable map
351 as well. */
353 void
354 partition_view_bitmap (var_map map, bitmap only, bool want_bases)
356 bitmap used;
357 bitmap new_partitions = BITMAP_ALLOC (NULL);
358 unsigned x, p;
359 bitmap_iterator bi;
361 used = partition_view_init (map);
362 EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)
364 p = partition_find (map->var_partition, x);
365 gcc_assert (bitmap_bit_p (used, p));
366 bitmap_set_bit (new_partitions, p);
368 partition_view_fini (map, new_partitions);
370 if (want_bases)
371 var_map_base_init (map);
372 else
373 var_map_base_fini (map);
377 static bitmap usedvars;
379 /* Mark VAR as used, so that it'll be preserved during rtl expansion.
380 Returns true if VAR wasn't marked before. */
382 static inline bool
383 set_is_used (tree var)
385 return bitmap_set_bit (usedvars, DECL_UID (var));
388 /* Return true if VAR is marked as used. */
390 static inline bool
391 is_used_p (tree var)
393 return bitmap_bit_p (usedvars, DECL_UID (var));
396 static inline void mark_all_vars_used (tree *);
398 /* Helper function for mark_all_vars_used, called via walk_tree. */
400 static tree
401 mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
403 tree t = *tp;
404 enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));
405 tree b;
407 if (TREE_CODE (t) == SSA_NAME)
409 *walk_subtrees = 0;
410 t = SSA_NAME_VAR (t);
411 if (!t)
412 return NULL;
415 if (IS_EXPR_CODE_CLASS (c)
416 && (b = TREE_BLOCK (t)) != NULL)
417 TREE_USED (b) = true;
419 /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
420 fields do not contain vars. */
421 if (TREE_CODE (t) == TARGET_MEM_REF)
423 mark_all_vars_used (&TMR_BASE (t));
424 mark_all_vars_used (&TMR_INDEX (t));
425 mark_all_vars_used (&TMR_INDEX2 (t));
426 *walk_subtrees = 0;
427 return NULL;
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 /* When a global var becomes used for the first time also walk its
435 initializer (non global ones don't have any). */
436 if (set_is_used (t) && is_global_var (t)
437 && DECL_CONTEXT (t) == current_function_decl)
438 mark_all_vars_used (&DECL_INITIAL (t));
440 /* remove_unused_scope_block_p requires information about labels
441 which are not DECL_IGNORED_P to tell if they might be used in the IL. */
442 else if (TREE_CODE (t) == LABEL_DECL)
443 /* Although the TREE_USED values that the frontend uses would be
444 acceptable (albeit slightly over-conservative) for our purposes,
445 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
446 must re-compute it here. */
447 TREE_USED (t) = 1;
449 if (IS_TYPE_OR_DECL_P (t))
450 *walk_subtrees = 0;
452 return NULL;
455 /* Mark the scope block SCOPE and its subblocks unused when they can be
456 possibly eliminated if dead. */
458 static void
459 mark_scope_block_unused (tree scope)
461 tree t;
462 TREE_USED (scope) = false;
463 if (!(*debug_hooks->ignore_block) (scope))
464 TREE_USED (scope) = true;
465 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
466 mark_scope_block_unused (t);
469 /* Look if the block is dead (by possibly eliminating its dead subblocks)
470 and return true if so.
471 Block is declared dead if:
472 1) No statements are associated with it.
473 2) Declares no live variables
474 3) All subblocks are dead
475 or there is precisely one subblocks and the block
476 has same abstract origin as outer block and declares
477 no variables, so it is pure wrapper.
478 When we are not outputting full debug info, we also eliminate dead variables
479 out of scope blocks to let them to be recycled by GGC and to save copying work
480 done by the inliner. */
482 static bool
483 remove_unused_scope_block_p (tree scope)
485 tree *t, *next;
486 bool unused = !TREE_USED (scope);
487 int nsubblocks = 0;
489 for (t = &BLOCK_VARS (scope); *t; t = next)
491 next = &DECL_CHAIN (*t);
493 /* Debug info of nested function refers to the block of the
494 function. We might stil call it even if all statements
495 of function it was nested into was elliminated.
497 TODO: We can actually look into cgraph to see if function
498 will be output to file. */
499 if (TREE_CODE (*t) == FUNCTION_DECL)
500 unused = false;
502 /* If a decl has a value expr, we need to instantiate it
503 regardless of debug info generation, to avoid codegen
504 differences in memory overlap tests. update_equiv_regs() may
505 indirectly call validate_equiv_mem() to test whether a
506 SET_DEST overlaps with others, and if the value expr changes
507 by virtual register instantiation, we may get end up with
508 different results. */
509 else if (TREE_CODE (*t) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*t))
510 unused = false;
512 /* Remove everything we don't generate debug info for. */
513 else if (DECL_IGNORED_P (*t))
515 *t = DECL_CHAIN (*t);
516 next = t;
519 /* When we are outputting debug info, we usually want to output
520 info about optimized-out variables in the scope blocks.
521 Exception are the scope blocks not containing any instructions
522 at all so user can't get into the scopes at first place. */
523 else if (is_used_p (*t))
524 unused = false;
525 else if (TREE_CODE (*t) == LABEL_DECL && TREE_USED (*t))
526 /* For labels that are still used in the IL, the decision to
527 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
528 risk having different ordering in debug vs. non-debug builds
529 during inlining or versioning.
530 A label appearing here (we have already checked DECL_IGNORED_P)
531 should not be used in the IL unless it has been explicitly used
532 before, so we use TREE_USED as an approximation. */
533 /* In principle, we should do the same here as for the debug case
534 below, however, when debugging, there might be additional nested
535 levels that keep an upper level with a label live, so we have to
536 force this block to be considered used, too. */
537 unused = false;
539 /* When we are not doing full debug info, we however can keep around
540 only the used variables for cfgexpand's memory packing saving quite
541 a lot of memory.
543 For sake of -g3, we keep around those vars but we don't count this as
544 use of block, so innermost block with no used vars and no instructions
545 can be considered dead. We only want to keep around blocks user can
546 breakpoint into and ask about value of optimized out variables.
548 Similarly we need to keep around types at least until all
549 variables of all nested blocks are gone. We track no
550 information on whether given type is used or not, so we have
551 to keep them even when not emitting debug information,
552 otherwise we may end up remapping variables and their (local)
553 types in different orders depending on whether debug
554 information is being generated. */
556 else if (TREE_CODE (*t) == TYPE_DECL
557 || debug_info_level == DINFO_LEVEL_NORMAL
558 || debug_info_level == DINFO_LEVEL_VERBOSE)
560 else
562 *t = DECL_CHAIN (*t);
563 next = t;
567 for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
568 if (remove_unused_scope_block_p (*t))
570 if (BLOCK_SUBBLOCKS (*t))
572 tree next = BLOCK_CHAIN (*t);
573 tree supercontext = BLOCK_SUPERCONTEXT (*t);
575 *t = BLOCK_SUBBLOCKS (*t);
576 while (BLOCK_CHAIN (*t))
578 BLOCK_SUPERCONTEXT (*t) = supercontext;
579 t = &BLOCK_CHAIN (*t);
581 BLOCK_CHAIN (*t) = next;
582 BLOCK_SUPERCONTEXT (*t) = supercontext;
583 t = &BLOCK_CHAIN (*t);
584 nsubblocks ++;
586 else
587 *t = BLOCK_CHAIN (*t);
589 else
591 t = &BLOCK_CHAIN (*t);
592 nsubblocks ++;
596 if (!unused)
598 /* Outer scope is always used. */
599 else if (!BLOCK_SUPERCONTEXT (scope)
600 || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)
601 unused = false;
602 /* Innermost blocks with no live variables nor statements can be always
603 eliminated. */
604 else if (!nsubblocks)
606 /* When not generating debug info we can eliminate info on unused
607 variables. */
608 else if (debug_info_level == DINFO_LEVEL_NONE)
610 /* Even for -g0 don't prune outer scopes from artificial
611 functions, otherwise diagnostics using tree_nonartificial_location
612 will not be emitted properly. */
613 if (inlined_function_outer_scope_p (scope))
615 tree ao = scope;
617 while (ao
618 && TREE_CODE (ao) == BLOCK
619 && BLOCK_ABSTRACT_ORIGIN (ao) != ao)
620 ao = BLOCK_ABSTRACT_ORIGIN (ao);
621 if (ao
622 && TREE_CODE (ao) == FUNCTION_DECL
623 && DECL_DECLARED_INLINE_P (ao)
624 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao)))
625 unused = false;
628 else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope))
629 unused = false;
630 /* See if this block is important for representation of inlined function.
631 Inlined functions are always represented by block with
632 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
633 set... */
634 else if (inlined_function_outer_scope_p (scope))
635 unused = false;
636 else
637 /* Verfify that only blocks with source location set
638 are entry points to the inlined functions. */
639 gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope))
640 == UNKNOWN_LOCATION);
642 TREE_USED (scope) = !unused;
643 return unused;
646 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
647 eliminated during the tree->rtl conversion process. */
649 static inline void
650 mark_all_vars_used (tree *expr_p)
652 walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
655 /* Helper function for clear_unused_block_pointer, called via walk_tree. */
657 static tree
658 clear_unused_block_pointer_1 (tree *tp, int *, void *)
660 if (EXPR_P (*tp) && TREE_BLOCK (*tp)
661 && !TREE_USED (TREE_BLOCK (*tp)))
662 TREE_SET_BLOCK (*tp, NULL);
663 return NULL_TREE;
666 /* Set all block pointer in debug or clobber stmt to NULL if the block
667 is unused, so that they will not be streamed out. */
669 static void
670 clear_unused_block_pointer (void)
672 basic_block bb;
673 gimple_stmt_iterator gsi;
675 FOR_EACH_BB_FN (bb, cfun)
676 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
678 unsigned i;
679 tree b;
680 gimple stmt = gsi_stmt (gsi);
682 if (!is_gimple_debug (stmt) && !gimple_clobber_p (stmt))
683 continue;
684 b = gimple_block (stmt);
685 if (b && !TREE_USED (b))
686 gimple_set_block (stmt, NULL);
687 for (i = 0; i < gimple_num_ops (stmt); i++)
688 walk_tree (gimple_op_ptr (stmt, i), clear_unused_block_pointer_1,
689 NULL, NULL);
693 /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
694 indentation level and FLAGS is as in print_generic_expr. */
696 static void
697 dump_scope_block (FILE *file, int indent, tree scope, int flags)
699 tree var, t;
700 unsigned int i;
702 fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope),
703 TREE_USED (scope) ? "" : " (unused)",
704 BLOCK_ABSTRACT (scope) ? " (abstract)": "");
705 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope)) != UNKNOWN_LOCATION)
707 expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope));
708 fprintf (file, " %s:%i", s.file, s.line);
710 if (BLOCK_ABSTRACT_ORIGIN (scope))
712 tree origin = block_ultimate_origin (scope);
713 if (origin)
715 fprintf (file, " Originating from :");
716 if (DECL_P (origin))
717 print_generic_decl (file, origin, flags);
718 else
719 fprintf (file, "#%i", BLOCK_NUMBER (origin));
722 fprintf (file, " \n");
723 for (var = BLOCK_VARS (scope); var; var = DECL_CHAIN (var))
725 fprintf (file, "%*s", indent, "");
726 print_generic_decl (file, var, flags);
727 fprintf (file, "\n");
729 for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++)
731 fprintf (file, "%*s",indent, "");
732 print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i),
733 flags);
734 fprintf (file, " (nonlocalized)\n");
736 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
737 dump_scope_block (file, indent + 2, t, flags);
738 fprintf (file, "\n%*s}\n",indent, "");
741 /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
742 is as in print_generic_expr. */
744 DEBUG_FUNCTION void
745 debug_scope_block (tree scope, int flags)
747 dump_scope_block (stderr, 0, scope, flags);
751 /* Dump the tree of lexical scopes of current_function_decl to FILE.
752 FLAGS is as in print_generic_expr. */
754 void
755 dump_scope_blocks (FILE *file, int flags)
757 dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags);
761 /* Dump the tree of lexical scopes of current_function_decl to stderr.
762 FLAGS is as in print_generic_expr. */
764 DEBUG_FUNCTION void
765 debug_scope_blocks (int flags)
767 dump_scope_blocks (stderr, flags);
770 /* Remove local variables that are not referenced in the IL. */
772 void
773 remove_unused_locals (void)
775 basic_block bb;
776 tree var;
777 unsigned srcidx, dstidx, num;
778 bool have_local_clobbers = false;
780 /* Removing declarations from lexical blocks when not optimizing is
781 not only a waste of time, it actually causes differences in stack
782 layout. */
783 if (!optimize)
784 return;
786 timevar_push (TV_REMOVE_UNUSED);
788 mark_scope_block_unused (DECL_INITIAL (current_function_decl));
790 usedvars = BITMAP_ALLOC (NULL);
792 /* Walk the CFG marking all referenced symbols. */
793 FOR_EACH_BB_FN (bb, cfun)
795 gimple_stmt_iterator gsi;
796 size_t i;
797 edge_iterator ei;
798 edge e;
800 /* Walk the statements. */
801 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
803 gimple stmt = gsi_stmt (gsi);
804 tree b = gimple_block (stmt);
806 if (is_gimple_debug (stmt))
807 continue;
809 if (gimple_clobber_p (stmt))
811 have_local_clobbers = true;
812 continue;
815 if (b)
816 TREE_USED (b) = true;
818 for (i = 0; i < gimple_num_ops (stmt); i++)
819 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i));
822 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
824 use_operand_p arg_p;
825 ssa_op_iter i;
826 tree def;
827 gimple phi = gsi_stmt (gsi);
829 if (virtual_operand_p (gimple_phi_result (phi)))
830 continue;
832 def = gimple_phi_result (phi);
833 mark_all_vars_used (&def);
835 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
837 tree arg = USE_FROM_PTR (arg_p);
838 int index = PHI_ARG_INDEX_FROM_USE (arg_p);
839 tree block =
840 LOCATION_BLOCK (gimple_phi_arg_location (phi, index));
841 if (block != NULL)
842 TREE_USED (block) = true;
843 mark_all_vars_used (&arg);
847 FOR_EACH_EDGE (e, ei, bb->succs)
848 if (LOCATION_BLOCK (e->goto_locus) != NULL)
849 TREE_USED (LOCATION_BLOCK (e->goto_locus)) = true;
852 /* We do a two-pass approach about the out-of-scope clobbers. We want
853 to remove them if they are the only references to a local variable,
854 but we want to retain them when there's any other. So the first pass
855 ignores them, and the second pass (if there were any) tries to remove
856 them. */
857 if (have_local_clobbers)
858 FOR_EACH_BB_FN (bb, cfun)
860 gimple_stmt_iterator gsi;
862 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
864 gimple stmt = gsi_stmt (gsi);
865 tree b = gimple_block (stmt);
867 if (gimple_clobber_p (stmt))
869 tree lhs = gimple_assign_lhs (stmt);
870 tree base = get_base_address (lhs);
871 /* Remove clobbers referencing unused vars, or clobbers
872 with MEM_REF lhs referencing uninitialized pointers. */
873 if ((TREE_CODE (base) == VAR_DECL && !is_used_p (base))
874 || (TREE_CODE (lhs) == MEM_REF
875 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME
876 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs, 0))
877 && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs, 0)))
878 != PARM_DECL)))
880 unlink_stmt_vdef (stmt);
881 gsi_remove (&gsi, true);
882 release_defs (stmt);
883 continue;
885 if (b)
886 TREE_USED (b) = true;
888 gsi_next (&gsi);
892 cfun->has_local_explicit_reg_vars = false;
894 /* Remove unmarked local and global vars from local_decls. */
895 num = vec_safe_length (cfun->local_decls);
896 for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++)
898 var = (*cfun->local_decls)[srcidx];
899 if (TREE_CODE (var) == VAR_DECL)
901 if (!is_used_p (var))
903 tree def;
904 if (cfun->nonlocal_goto_save_area
905 && TREE_OPERAND (cfun->nonlocal_goto_save_area, 0) == var)
906 cfun->nonlocal_goto_save_area = NULL;
907 /* Release any default def associated with var. */
908 if ((def = ssa_default_def (cfun, var)) != NULL_TREE)
910 set_ssa_default_def (cfun, var, NULL_TREE);
911 release_ssa_name (def);
913 continue;
916 if (TREE_CODE (var) == VAR_DECL
917 && DECL_HARD_REGISTER (var)
918 && !is_global_var (var))
919 cfun->has_local_explicit_reg_vars = true;
921 if (srcidx != dstidx)
922 (*cfun->local_decls)[dstidx] = var;
923 dstidx++;
925 if (dstidx != num)
927 statistics_counter_event (cfun, "unused VAR_DECLs removed", num - dstidx);
928 cfun->local_decls->truncate (dstidx);
931 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl));
932 clear_unused_block_pointer ();
934 BITMAP_FREE (usedvars);
936 if (dump_file && (dump_flags & TDF_DETAILS))
938 fprintf (dump_file, "Scope blocks after cleanups:\n");
939 dump_scope_blocks (dump_file, dump_flags);
942 timevar_pop (TV_REMOVE_UNUSED);
945 /* Obstack for globale liveness info bitmaps. We don't want to put these
946 on the default obstack because these bitmaps can grow quite large and
947 we'll hold on to all that memory until the end of the compiler run.
948 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
949 releasing the whole obstack. */
950 static bitmap_obstack liveness_bitmap_obstack;
952 /* Allocate and return a new live range information object base on MAP. */
954 static tree_live_info_p
955 new_tree_live_info (var_map map)
957 tree_live_info_p live;
958 basic_block bb;
960 live = XNEW (struct tree_live_info_d);
961 live->map = map;
962 live->num_blocks = last_basic_block_for_fn (cfun);
964 live->livein = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
965 FOR_EACH_BB_FN (bb, cfun)
966 bitmap_initialize (&live->livein[bb->index], &liveness_bitmap_obstack);
968 live->liveout = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
969 FOR_EACH_BB_FN (bb, cfun)
970 bitmap_initialize (&live->liveout[bb->index], &liveness_bitmap_obstack);
972 live->work_stack = XNEWVEC (int, last_basic_block_for_fn (cfun));
973 live->stack_top = live->work_stack;
975 live->global = BITMAP_ALLOC (&liveness_bitmap_obstack);
976 return live;
980 /* Free storage for live range info object LIVE. */
982 void
983 delete_tree_live_info (tree_live_info_p live)
985 bitmap_obstack_release (&liveness_bitmap_obstack);
986 free (live->work_stack);
987 free (live->liveout);
988 free (live->livein);
989 free (live);
993 /* Visit basic block BB and propagate any required live on entry bits from
994 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
995 TMP is a temporary work bitmap which is passed in to avoid reallocating
996 it each time. */
998 static void
999 loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
1000 bitmap tmp)
1002 edge e;
1003 bool change;
1004 edge_iterator ei;
1005 basic_block pred_bb;
1006 bitmap loe;
1008 gcc_checking_assert (!bitmap_bit_p (visited, bb->index));
1009 bitmap_set_bit (visited, bb->index);
1011 loe = live_on_entry (live, bb);
1013 FOR_EACH_EDGE (e, ei, bb->preds)
1015 pred_bb = e->src;
1016 if (pred_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1017 continue;
1018 /* TMP is variables live-on-entry from BB that aren't defined in the
1019 predecessor block. This should be the live on entry vars to pred.
1020 Note that liveout is the DEFs in a block while live on entry is
1021 being calculated. */
1022 bitmap_and_compl (tmp, loe, &live->liveout[pred_bb->index]);
1024 /* Add these bits to live-on-entry for the pred. if there are any
1025 changes, and pred_bb has been visited already, add it to the
1026 revisit stack. */
1027 change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
1028 if (bitmap_bit_p (visited, pred_bb->index) && change)
1030 bitmap_clear_bit (visited, pred_bb->index);
1031 *(live->stack_top)++ = pred_bb->index;
1037 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
1038 of all the variables. */
1040 static void
1041 live_worklist (tree_live_info_p live)
1043 unsigned b;
1044 basic_block bb;
1045 sbitmap visited = sbitmap_alloc (last_basic_block_for_fn (cfun) + 1);
1046 bitmap tmp = BITMAP_ALLOC (&liveness_bitmap_obstack);
1048 bitmap_clear (visited);
1050 /* Visit all the blocks in reverse order and propagate live on entry values
1051 into the predecessors blocks. */
1052 FOR_EACH_BB_REVERSE_FN (bb, cfun)
1053 loe_visit_block (live, bb, visited, tmp);
1055 /* Process any blocks which require further iteration. */
1056 while (live->stack_top != live->work_stack)
1058 b = *--(live->stack_top);
1059 loe_visit_block (live, BASIC_BLOCK_FOR_FN (cfun, b), visited, tmp);
1062 BITMAP_FREE (tmp);
1063 sbitmap_free (visited);
1067 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1068 links. Set the live on entry fields in LIVE. Def's are marked temporarily
1069 in the liveout vector. */
1071 static void
1072 set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
1074 int p;
1075 gimple stmt;
1076 use_operand_p use;
1077 basic_block def_bb = NULL;
1078 imm_use_iterator imm_iter;
1079 bool global = false;
1081 p = var_to_partition (live->map, ssa_name);
1082 if (p == NO_PARTITION)
1083 return;
1085 stmt = SSA_NAME_DEF_STMT (ssa_name);
1086 if (stmt)
1088 def_bb = gimple_bb (stmt);
1089 /* Mark defs in liveout bitmap temporarily. */
1090 if (def_bb)
1091 bitmap_set_bit (&live->liveout[def_bb->index], p);
1093 else
1094 def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1096 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1097 add it to the list of live on entry blocks. */
1098 FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
1100 gimple use_stmt = USE_STMT (use);
1101 basic_block add_block = NULL;
1103 if (gimple_code (use_stmt) == GIMPLE_PHI)
1105 /* Uses in PHI's are considered to be live at exit of the SRC block
1106 as this is where a copy would be inserted. Check to see if it is
1107 defined in that block, or whether its live on entry. */
1108 int index = PHI_ARG_INDEX_FROM_USE (use);
1109 edge e = gimple_phi_arg_edge (use_stmt, index);
1110 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1112 if (e->src != def_bb)
1113 add_block = e->src;
1116 else if (is_gimple_debug (use_stmt))
1117 continue;
1118 else
1120 /* If its not defined in this block, its live on entry. */
1121 basic_block use_bb = gimple_bb (use_stmt);
1122 if (use_bb != def_bb)
1123 add_block = use_bb;
1126 /* If there was a live on entry use, set the bit. */
1127 if (add_block)
1129 global = true;
1130 bitmap_set_bit (&live->livein[add_block->index], p);
1134 /* If SSA_NAME is live on entry to at least one block, fill in all the live
1135 on entry blocks between the def and all the uses. */
1136 if (global)
1137 bitmap_set_bit (live->global, p);
1141 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1143 void
1144 calculate_live_on_exit (tree_live_info_p liveinfo)
1146 basic_block bb;
1147 edge e;
1148 edge_iterator ei;
1150 /* live on entry calculations used liveout vectors for defs, clear them. */
1151 FOR_EACH_BB_FN (bb, cfun)
1152 bitmap_clear (&liveinfo->liveout[bb->index]);
1154 /* Set all the live-on-exit bits for uses in PHIs. */
1155 FOR_EACH_BB_FN (bb, cfun)
1157 gimple_stmt_iterator gsi;
1158 size_t i;
1160 /* Mark the PHI arguments which are live on exit to the pred block. */
1161 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1163 gimple phi = gsi_stmt (gsi);
1164 for (i = 0; i < gimple_phi_num_args (phi); i++)
1166 tree t = PHI_ARG_DEF (phi, i);
1167 int p;
1169 if (TREE_CODE (t) != SSA_NAME)
1170 continue;
1172 p = var_to_partition (liveinfo->map, t);
1173 if (p == NO_PARTITION)
1174 continue;
1175 e = gimple_phi_arg_edge (phi, i);
1176 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1177 bitmap_set_bit (&liveinfo->liveout[e->src->index], p);
1181 /* Add each successors live on entry to this bock live on exit. */
1182 FOR_EACH_EDGE (e, ei, bb->succs)
1183 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1184 bitmap_ior_into (&liveinfo->liveout[bb->index],
1185 live_on_entry (liveinfo, e->dest));
1190 /* Given partition map MAP, calculate all the live on entry bitmaps for
1191 each partition. Return a new live info object. */
1193 tree_live_info_p
1194 calculate_live_ranges (var_map map)
1196 tree var;
1197 unsigned i;
1198 tree_live_info_p live;
1200 bitmap_obstack_initialize (&liveness_bitmap_obstack);
1201 live = new_tree_live_info (map);
1202 for (i = 0; i < num_var_partitions (map); i++)
1204 var = partition_to_var (map, i);
1205 if (var != NULL_TREE)
1206 set_var_live_on_entry (var, live);
1209 live_worklist (live);
1211 #ifdef ENABLE_CHECKING
1212 verify_live_on_entry (live);
1213 #endif
1215 calculate_live_on_exit (live);
1216 return live;
1220 /* Output partition map MAP to file F. */
1222 void
1223 dump_var_map (FILE *f, var_map map)
1225 int t;
1226 unsigned x, y;
1227 int p;
1229 fprintf (f, "\nPartition map \n\n");
1231 for (x = 0; x < map->num_partitions; x++)
1233 if (map->view_to_partition != NULL)
1234 p = map->view_to_partition[x];
1235 else
1236 p = x;
1238 if (ssa_name (p) == NULL_TREE
1239 || virtual_operand_p (ssa_name (p)))
1240 continue;
1242 t = 0;
1243 for (y = 1; y < num_ssa_names; y++)
1245 p = partition_find (map->var_partition, y);
1246 if (map->partition_to_view)
1247 p = map->partition_to_view[p];
1248 if (p == (int)x)
1250 if (t++ == 0)
1252 fprintf (f, "Partition %d (", x);
1253 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1254 fprintf (f, " - ");
1256 fprintf (f, "%d ", y);
1259 if (t != 0)
1260 fprintf (f, ")\n");
1262 fprintf (f, "\n");
1266 /* Generic dump for the above. */
1268 DEBUG_FUNCTION void
1269 debug (_var_map &ref)
1271 dump_var_map (stderr, &ref);
1274 DEBUG_FUNCTION void
1275 debug (_var_map *ptr)
1277 if (ptr)
1278 debug (*ptr);
1279 else
1280 fprintf (stderr, "<nil>\n");
1284 /* Output live range info LIVE to file F, controlled by FLAG. */
1286 void
1287 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1289 basic_block bb;
1290 unsigned i;
1291 var_map map = live->map;
1292 bitmap_iterator bi;
1294 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1296 FOR_EACH_BB_FN (bb, cfun)
1298 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1299 EXECUTE_IF_SET_IN_BITMAP (&live->livein[bb->index], 0, i, bi)
1301 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1302 fprintf (f, " ");
1304 fprintf (f, "\n");
1308 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1310 FOR_EACH_BB_FN (bb, cfun)
1312 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1313 EXECUTE_IF_SET_IN_BITMAP (&live->liveout[bb->index], 0, i, bi)
1315 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1316 fprintf (f, " ");
1318 fprintf (f, "\n");
1324 /* Generic dump for the above. */
1326 DEBUG_FUNCTION void
1327 debug (tree_live_info_d &ref)
1329 dump_live_info (stderr, &ref, 0);
1332 DEBUG_FUNCTION void
1333 debug (tree_live_info_d *ptr)
1335 if (ptr)
1336 debug (*ptr);
1337 else
1338 fprintf (stderr, "<nil>\n");
1342 #ifdef ENABLE_CHECKING
1343 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1345 void
1346 register_ssa_partition_check (tree ssa_var)
1348 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1349 if (virtual_operand_p (ssa_var))
1351 fprintf (stderr, "Illegally registering a virtual SSA name :");
1352 print_generic_expr (stderr, ssa_var, TDF_SLIM);
1353 fprintf (stderr, " in the SSA->Normal phase.\n");
1354 internal_error ("SSA corruption");
1359 /* Verify that the info in LIVE matches the current cfg. */
1361 static void
1362 verify_live_on_entry (tree_live_info_p live)
1364 unsigned i;
1365 tree var;
1366 gimple stmt;
1367 basic_block bb;
1368 edge e;
1369 int num;
1370 edge_iterator ei;
1371 var_map map = live->map;
1373 /* Check for live on entry partitions and report those with a DEF in
1374 the program. This will typically mean an optimization has done
1375 something wrong. */
1376 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1377 num = 0;
1378 FOR_EACH_EDGE (e, ei, bb->succs)
1380 int entry_block = e->dest->index;
1381 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1382 continue;
1383 for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1385 basic_block tmp;
1386 tree d = NULL_TREE;
1387 bitmap loe;
1388 var = partition_to_var (map, i);
1389 stmt = SSA_NAME_DEF_STMT (var);
1390 tmp = gimple_bb (stmt);
1391 if (SSA_NAME_VAR (var))
1392 d = ssa_default_def (cfun, SSA_NAME_VAR (var));
1394 loe = live_on_entry (live, e->dest);
1395 if (loe && bitmap_bit_p (loe, i))
1397 if (!gimple_nop_p (stmt))
1399 num++;
1400 print_generic_expr (stderr, var, TDF_SLIM);
1401 fprintf (stderr, " is defined ");
1402 if (tmp)
1403 fprintf (stderr, " in BB%d, ", tmp->index);
1404 fprintf (stderr, "by:\n");
1405 print_gimple_stmt (stderr, stmt, 0, TDF_SLIM);
1406 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1407 entry_block);
1408 fprintf (stderr, " So it appears to have multiple defs.\n");
1410 else
1412 if (d != var)
1414 num++;
1415 print_generic_expr (stderr, var, TDF_SLIM);
1416 fprintf (stderr, " is live-on-entry to BB%d ",
1417 entry_block);
1418 if (d)
1420 fprintf (stderr, " but is not the default def of ");
1421 print_generic_expr (stderr, d, TDF_SLIM);
1422 fprintf (stderr, "\n");
1424 else
1425 fprintf (stderr, " and there is no default def.\n");
1429 else
1430 if (d == var)
1432 /* The only way this var shouldn't be marked live on entry is
1433 if it occurs in a PHI argument of the block. */
1434 size_t z;
1435 bool ok = false;
1436 gimple_stmt_iterator gsi;
1437 for (gsi = gsi_start_phis (e->dest);
1438 !gsi_end_p (gsi) && !ok;
1439 gsi_next (&gsi))
1441 gimple phi = gsi_stmt (gsi);
1442 for (z = 0; z < gimple_phi_num_args (phi); z++)
1443 if (var == gimple_phi_arg_def (phi, z))
1445 ok = true;
1446 break;
1449 if (ok)
1450 continue;
1451 num++;
1452 print_generic_expr (stderr, var, TDF_SLIM);
1453 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1454 entry_block);
1455 fprintf (stderr, "but it is a default def so it should be.\n");
1459 gcc_assert (num <= 0);
1461 #endif