Daily bump.
[official-gcc.git] / gcc / tree-ssa-live.c
blob51d682c1c190114d7ace610c7b91120bb5130850
1 /* Liveness for SSA trees.
2 Copyright (C) 2003, 2004, 2005, 2007 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 "tm.h"
25 #include "tree.h"
26 #include "diagnostic.h"
27 #include "bitmap.h"
28 #include "tree-flow.h"
29 #include "tree-dump.h"
30 #include "tree-ssa-live.h"
31 #include "toplev.h"
32 #include "debug.h"
33 #include "flags.h"
35 #ifdef ENABLE_CHECKING
36 static void verify_live_on_entry (tree_live_info_p);
37 #endif
40 /* VARMAP maintains a mapping from SSA version number to real variables.
42 All SSA_NAMES are divided into partitions. Initially each ssa_name is the
43 only member of it's own partition. Coalescing will attempt to group any
44 ssa_names which occur in a copy or in a PHI node into the same partition.
46 At the end of out-of-ssa, each partition becomes a "real" variable and is
47 rewritten as a compiler variable.
49 The var_map datat structure is used to manage these partitions. It allows
50 partitions to be combined, and determines which partition belongs to what
51 ssa_name or variable, and vice versa. */
54 /* This routine will initialize the basevar fields of MAP. */
56 static void
57 var_map_base_init (var_map map)
59 int x, num_part, num;
60 tree var;
61 var_ann_t ann;
63 num = 0;
64 num_part = num_var_partitions (map);
66 /* If a base table already exists, clear it, otherwise create it. */
67 if (map->partition_to_base_index != NULL)
69 free (map->partition_to_base_index);
70 VEC_truncate (tree, map->basevars, 0);
72 else
73 map->basevars = VEC_alloc (tree, heap, MAX (40, (num_part / 10)));
75 map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
77 /* Build the base variable list, and point partitions at their bases. */
78 for (x = 0; x < num_part; x++)
80 var = partition_to_var (map, x);
81 if (TREE_CODE (var) == SSA_NAME)
82 var = SSA_NAME_VAR (var);
83 ann = var_ann (var);
84 /* If base variable hasn't been seen, set it up. */
85 if (!ann->base_var_processed)
87 ann->base_var_processed = 1;
88 VAR_ANN_BASE_INDEX (ann) = num++;
89 VEC_safe_push (tree, heap, map->basevars, var);
91 map->partition_to_base_index[x] = VAR_ANN_BASE_INDEX (ann);
94 map->num_basevars = num;
96 /* Now clear the processed bit. */
97 for (x = 0; x < num; x++)
99 var = VEC_index (tree, map->basevars, x);
100 var_ann (var)->base_var_processed = 0;
103 #ifdef ENABLE_CHECKING
104 for (x = 0; x < num_part; x++)
106 tree var2;
107 var = SSA_NAME_VAR (partition_to_var (map, x));
108 var2 = VEC_index (tree, map->basevars, basevar_index (map, x));
109 gcc_assert (var == var2);
111 #endif
115 /* Remove the base table in MAP. */
117 static void
118 var_map_base_fini (var_map map)
120 /* Free the basevar info if it is present. */
121 if (map->partition_to_base_index != NULL)
123 VEC_free (tree, heap, map->basevars);
124 free (map->partition_to_base_index);
125 map->partition_to_base_index = NULL;
126 map->num_basevars = 0;
129 /* Create a variable partition map of SIZE, initialize and return it. */
131 var_map
132 init_var_map (int size)
134 var_map map;
136 map = (var_map) xmalloc (sizeof (struct _var_map));
137 map->var_partition = partition_new (size);
138 map->partition_to_var
139 = (tree *)xmalloc (size * sizeof (tree));
140 memset (map->partition_to_var, 0, size * sizeof (tree));
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;
149 return map;
153 /* Free memory associated with MAP. */
155 void
156 delete_var_map (var_map map)
158 var_map_base_fini (map);
159 free (map->partition_to_var);
160 partition_delete (map->var_partition);
161 if (map->partition_to_view)
162 free (map->partition_to_view);
163 if (map->view_to_partition)
164 free (map->view_to_partition);
165 free (map);
169 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
170 Returns the partition which represents the new partition. If the two
171 partitions cannot be combined, NO_PARTITION is returned. */
174 var_union (var_map map, tree var1, tree var2)
176 int p1, p2, p3;
177 tree root_var = NULL_TREE;
178 tree other_var = NULL_TREE;
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 if (TREE_CODE (var1) == SSA_NAME)
185 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
186 else
188 p1 = var_to_partition (map, var1);
189 if (map->view_to_partition)
190 p1 = map->view_to_partition[p1];
191 root_var = var1;
194 if (TREE_CODE (var2) == SSA_NAME)
195 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
196 else
198 p2 = var_to_partition (map, var2);
199 if (map->view_to_partition)
200 p2 = map->view_to_partition[p2];
202 /* If there is no root_var set, or it's not a user variable, set the
203 root_var to this one. */
204 if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
206 other_var = root_var;
207 root_var = var2;
209 else
210 other_var = var2;
213 gcc_assert (p1 != NO_PARTITION);
214 gcc_assert (p2 != NO_PARTITION);
216 if (p1 == p2)
217 p3 = p1;
218 else
219 p3 = partition_union (map->var_partition, p1, p2);
221 if (map->partition_to_view)
222 p3 = map->partition_to_view[p3];
224 if (root_var)
225 change_partition_var (map, root_var, p3);
226 if (other_var)
227 change_partition_var (map, other_var, p3);
229 return p3;
233 /* Compress the partition numbers in MAP such that they fall in the range
234 0..(num_partitions-1) instead of wherever they turned out during
235 the partitioning exercise. This removes any references to unused
236 partitions, thereby allowing bitmaps and other vectors to be much
237 denser.
239 This is implemented such that compaction doesn't affect partitioning.
240 Ie., once partitions are created and possibly merged, running one
241 or more different kind of compaction will not affect the partitions
242 themselves. Their index might change, but all the same variables will
243 still be members of the same partition group. This allows work on reduced
244 sets, and no loss of information when a larger set is later desired.
246 In particular, coalescing can work on partitions which have 2 or more
247 definitions, and then 'recompact' later to include all the single
248 definitions for assignment to program variables. */
251 /* Set MAP back to the initial state of having no partition view. Return a
252 bitmap which has a bit set for each partition number which is in use in the
253 varmap. */
255 static bitmap
256 partition_view_init (var_map map)
258 bitmap used;
259 int tmp;
260 unsigned int x;
262 used = BITMAP_ALLOC (NULL);
264 /* Already in a view? Abandon the old one. */
265 if (map->partition_to_view)
267 free (map->partition_to_view);
268 map->partition_to_view = NULL;
270 if (map->view_to_partition)
272 free (map->view_to_partition);
273 map->view_to_partition = NULL;
276 /* Find out which partitions are actually referenced. */
277 for (x = 0; x < map->partition_size; x++)
279 tmp = partition_find (map->var_partition, x);
280 if (map->partition_to_var[tmp] != NULL_TREE && !bitmap_bit_p (used, tmp))
281 bitmap_set_bit (used, tmp);
284 map->num_partitions = map->partition_size;
285 return used;
289 /* This routine will finalize the view data for MAP based on the partitions
290 set in SELECTED. This is either the same bitmap returned from
291 partition_view_init, or a trimmed down version if some of those partitions
292 were not desired in this view. SELECTED is freed before returning. */
294 static void
295 partition_view_fini (var_map map, bitmap selected)
297 bitmap_iterator bi;
298 unsigned count, i, x, limit;
299 tree var;
301 gcc_assert (selected);
303 count = bitmap_count_bits (selected);
304 limit = map->partition_size;
306 /* If its a one-to-one ratio, we don't need any view compaction. */
307 if (count < limit)
309 map->partition_to_view = (int *)xmalloc (limit * sizeof (int));
310 memset (map->partition_to_view, 0xff, (limit * sizeof (int)));
311 map->view_to_partition = (int *)xmalloc (count * sizeof (int));
313 i = 0;
314 /* Give each selected partition an index. */
315 EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)
317 map->partition_to_view[x] = i;
318 map->view_to_partition[i] = x;
319 var = map->partition_to_var[x];
320 /* If any one of the members of a partition is not an SSA_NAME, make
321 sure it is the representative. */
322 if (TREE_CODE (var) != SSA_NAME)
323 change_partition_var (map, var, i);
324 i++;
326 gcc_assert (i == count);
327 map->num_partitions = i;
330 BITMAP_FREE (selected);
334 /* Create a partition view which includes all the used partitions in MAP. If
335 WANT_BASES is true, create the base variable map as well. */
337 extern void
338 partition_view_normal (var_map map, bool want_bases)
340 bitmap used;
342 used = partition_view_init (map);
343 partition_view_fini (map, used);
345 if (want_bases)
346 var_map_base_init (map);
347 else
348 var_map_base_fini (map);
352 /* Create a partition view in MAP which includes just partitions which occur in
353 the bitmap ONLY. If WANT_BASES is true, create the base variable map
354 as well. */
356 extern void
357 partition_view_bitmap (var_map map, bitmap only, bool want_bases)
359 bitmap used;
360 bitmap new_partitions = BITMAP_ALLOC (NULL);
361 unsigned x, p;
362 bitmap_iterator bi;
364 used = partition_view_init (map);
365 EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)
367 p = partition_find (map->var_partition, x);
368 gcc_assert (bitmap_bit_p (used, p));
369 bitmap_set_bit (new_partitions, p);
371 partition_view_fini (map, new_partitions);
373 BITMAP_FREE (used);
374 if (want_bases)
375 var_map_base_init (map);
376 else
377 var_map_base_fini (map);
381 /* This function is used to change the representative variable in MAP for VAR's
382 partition to a regular non-ssa variable. This allows partitions to be
383 mapped back to real variables. */
385 void
386 change_partition_var (var_map map, tree var, int part)
388 var_ann_t ann;
390 gcc_assert (TREE_CODE (var) != SSA_NAME);
392 ann = var_ann (var);
393 ann->out_of_ssa_tag = 1;
394 VAR_ANN_PARTITION (ann) = part;
395 if (map->view_to_partition)
396 map->partition_to_var[map->view_to_partition[part]] = var;
400 static inline void mark_all_vars_used (tree *, void *data);
402 /* Helper function for mark_all_vars_used, called via walk_tree. */
404 static tree
405 mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
406 void *data)
408 tree t = *tp;
409 enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));
410 tree b;
412 if (TREE_CODE (t) == SSA_NAME)
413 t = SSA_NAME_VAR (t);
414 if ((IS_EXPR_CODE_CLASS (c)
415 || IS_GIMPLE_STMT_CODE_CLASS (c))
416 && (b = TREE_BLOCK (t)) != NULL)
417 TREE_USED (b) = true;
419 /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
420 fields that do not contain vars. */
421 if (TREE_CODE (t) == TARGET_MEM_REF)
423 mark_all_vars_used (&TMR_SYMBOL (t), data);
424 mark_all_vars_used (&TMR_BASE (t), data);
425 mark_all_vars_used (&TMR_INDEX (t), data);
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 if (data != NULL && bitmap_bit_p ((bitmap) data, DECL_UID (t)))
436 bitmap_clear_bit ((bitmap) data, DECL_UID (t));
437 mark_all_vars_used (&DECL_INITIAL (t), data);
439 set_is_used (t);
442 if (IS_TYPE_OR_DECL_P (t))
443 *walk_subtrees = 0;
445 return NULL;
448 /* Mark the scope block SCOPE and its subblocks unused when they can be
449 possibly eliminated if dead. */
451 static void
452 mark_scope_block_unused (tree scope)
454 tree t;
455 TREE_USED (scope) = false;
456 if (!(*debug_hooks->ignore_block) (scope))
457 TREE_USED (scope) = true;
458 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
459 mark_scope_block_unused (t);
462 /* Look if the block is dead (by possibly eliminating its dead subblocks)
463 and return true if so.
464 Block is declared dead if:
465 1) No statements are associated with it.
466 2) Declares no live variables
467 3) All subblocks are dead
468 or there is precisely one subblocks and the block
469 has same abstract origin as outer block and declares
470 no variables, so it is pure wrapper.
471 When we are not outputting full debug info, we also eliminate dead variables
472 out of scope blocks to let them to be recycled by GGC and to save copying work
473 done by the inliner. */
475 static bool
476 remove_unused_scope_block_p (tree scope)
478 tree *t, *next;
479 bool unused = !TREE_USED (scope);
480 var_ann_t ann;
481 int nsubblocks = 0;
483 for (t = &BLOCK_VARS (scope); *t; t = next)
485 next = &TREE_CHAIN (*t);
487 /* Debug info of nested function refers to the block of the
488 function. */
489 if (TREE_CODE (*t) == FUNCTION_DECL)
490 unused = false;
492 /* When we are outputting debug info, we usually want to output
493 info about optimized-out variables in the scope blocks.
494 Exception are the scope blocks not containing any instructions
495 at all so user can't get into the scopes at first place. */
496 else if ((ann = var_ann (*t)) != NULL
497 && ann->used)
498 unused = false;
500 /* When we are not doing full debug info, we however can keep around
501 only the used variables for cfgexpand's memory packing saving quite
502 a lot of memory. */
503 else if (debug_info_level == DINFO_LEVEL_NORMAL
504 || debug_info_level == DINFO_LEVEL_VERBOSE
505 /* Removing declarations before inlining is going to affect
506 DECL_UID that in turn is going to affect hashtables and
507 code generation. */
508 || !cfun->after_inlining)
509 unused = false;
511 else
513 *t = TREE_CHAIN (*t);
514 next = t;
518 for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
519 if (remove_unused_scope_block_p (*t))
521 if (BLOCK_SUBBLOCKS (*t))
523 tree next = BLOCK_CHAIN (*t);
524 tree supercontext = BLOCK_SUPERCONTEXT (*t);
525 *t = BLOCK_SUBBLOCKS (*t);
526 gcc_assert (!BLOCK_CHAIN (*t));
527 BLOCK_CHAIN (*t) = next;
528 BLOCK_SUPERCONTEXT (*t) = supercontext;
529 t = &BLOCK_CHAIN (*t);
530 nsubblocks ++;
532 else
534 gcc_assert (!BLOCK_VARS (*t));
535 *t = BLOCK_CHAIN (*t);
538 else
540 t = &BLOCK_CHAIN (*t);
541 nsubblocks ++;
543 /* Outer scope is always used. */
544 if (!BLOCK_SUPERCONTEXT (scope)
545 || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)
546 unused = false;
547 /* If there are more than one live subblocks, it is used. */
548 else if (nsubblocks > 1)
549 unused = false;
550 /* When there is only one subblock, see if it is just wrapper we can
551 ignore. Wrappers are not declaring any variables and not changing
552 abstract origin. */
553 else if (nsubblocks == 1
554 && (BLOCK_VARS (scope)
555 || ((debug_info_level == DINFO_LEVEL_NORMAL
556 || debug_info_level == DINFO_LEVEL_VERBOSE)
557 && ((BLOCK_ABSTRACT_ORIGIN (scope)
558 != BLOCK_ABSTRACT_ORIGIN (BLOCK_SUPERCONTEXT (scope)))))))
559 unused = false;
560 return unused;
563 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
564 eliminated during the tree->rtl conversion process. */
566 static inline void
567 mark_all_vars_used (tree *expr_p, void *data)
569 walk_tree (expr_p, mark_all_vars_used_1, data, NULL);
573 /* Remove local variables that are not referenced in the IL. */
575 void
576 remove_unused_locals (void)
578 basic_block bb;
579 tree t, *cell;
580 referenced_var_iterator rvi;
581 var_ann_t ann;
582 bitmap global_unused_vars = NULL;
584 mark_scope_block_unused (DECL_INITIAL (current_function_decl));
585 /* Assume all locals are unused. */
586 FOR_EACH_REFERENCED_VAR (t, rvi)
587 var_ann (t)->used = false;
589 /* Walk the CFG marking all referenced symbols. */
590 FOR_EACH_BB (bb)
592 block_stmt_iterator bsi;
593 tree phi, def;
595 /* Walk the statements. */
596 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
597 mark_all_vars_used (bsi_stmt_ptr (bsi), NULL);
599 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
601 use_operand_p arg_p;
602 ssa_op_iter i;
604 /* No point processing globals. */
605 if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
606 continue;
608 def = PHI_RESULT (phi);
609 mark_all_vars_used (&def, NULL);
611 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
613 tree arg = USE_FROM_PTR (arg_p);
614 mark_all_vars_used (&arg, NULL);
619 /* Remove unmarked local vars from unexpanded_var_list. */
620 for (cell = &cfun->unexpanded_var_list; *cell; )
622 tree var = TREE_VALUE (*cell);
624 if (TREE_CODE (var) != FUNCTION_DECL
625 && (!(ann = var_ann (var))
626 || !ann->used))
628 if (is_global_var (var))
630 if (global_unused_vars == NULL)
631 global_unused_vars = BITMAP_ALLOC (NULL);
632 bitmap_set_bit (global_unused_vars, DECL_UID (var));
634 else
636 *cell = TREE_CHAIN (*cell);
637 continue;
640 cell = &TREE_CHAIN (*cell);
643 /* Remove unmarked global vars from unexpanded_var_list. */
644 if (global_unused_vars != NULL)
646 for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
648 tree var = TREE_VALUE (t);
650 if (TREE_CODE (var) == VAR_DECL
651 && is_global_var (var)
652 && (ann = var_ann (var)) != NULL
653 && ann->used)
654 mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars);
657 for (cell = &cfun->unexpanded_var_list; *cell; )
659 tree var = TREE_VALUE (*cell);
661 if (TREE_CODE (var) == VAR_DECL
662 && is_global_var (var)
663 && bitmap_bit_p (global_unused_vars, DECL_UID (var)))
664 *cell = TREE_CHAIN (*cell);
665 else
666 cell = &TREE_CHAIN (*cell);
668 BITMAP_FREE (global_unused_vars);
671 /* Remove unused variables from REFERENCED_VARs. As a special
672 exception keep the variables that are believed to be aliased.
673 Those can't be easily removed from the alias sets and operand
674 caches. They will be removed shortly after the next may_alias
675 pass is performed. */
676 FOR_EACH_REFERENCED_VAR (t, rvi)
677 if (!is_global_var (t)
678 && !MTAG_P (t)
679 && TREE_CODE (t) != PARM_DECL
680 && TREE_CODE (t) != RESULT_DECL
681 && !(ann = var_ann (t))->used
682 && !ann->symbol_mem_tag
683 && !TREE_ADDRESSABLE (t))
684 remove_referenced_var (t);
685 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl));
689 /* Allocate and return a new live range information object base on MAP. */
691 static tree_live_info_p
692 new_tree_live_info (var_map map)
694 tree_live_info_p live;
695 unsigned x;
697 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
698 live->map = map;
699 live->num_blocks = last_basic_block;
701 live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
702 for (x = 0; x < (unsigned)last_basic_block; x++)
703 live->livein[x] = BITMAP_ALLOC (NULL);
705 live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
706 for (x = 0; x < (unsigned)last_basic_block; x++)
707 live->liveout[x] = BITMAP_ALLOC (NULL);
709 live->work_stack = XNEWVEC (int, last_basic_block);
710 live->stack_top = live->work_stack;
712 live->global = BITMAP_ALLOC (NULL);
713 return live;
717 /* Free storage for live range info object LIVE. */
719 void
720 delete_tree_live_info (tree_live_info_p live)
722 int x;
724 BITMAP_FREE (live->global);
725 free (live->work_stack);
727 for (x = live->num_blocks - 1; x >= 0; x--)
728 BITMAP_FREE (live->liveout[x]);
729 free (live->liveout);
731 for (x = live->num_blocks - 1; x >= 0; x--)
732 BITMAP_FREE (live->livein[x]);
733 free (live->livein);
735 free (live);
739 /* Visit basic block BB and propagate any required live on entry bits from
740 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
741 TMP is a temporary work bitmap which is passed in to avoid reallocating
742 it each time. */
744 static void
745 loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
746 bitmap tmp)
748 edge e;
749 bool change;
750 edge_iterator ei;
751 basic_block pred_bb;
752 bitmap loe;
753 gcc_assert (!TEST_BIT (visited, bb->index));
755 SET_BIT (visited, bb->index);
756 loe = live_on_entry (live, bb);
758 FOR_EACH_EDGE (e, ei, bb->preds)
760 pred_bb = e->src;
761 if (pred_bb == ENTRY_BLOCK_PTR)
762 continue;
763 /* TMP is variables live-on-entry from BB that aren't defined in the
764 predecessor block. This should be the live on entry vars to pred.
765 Note that liveout is the DEFs in a block while live on entry is
766 being calculated. */
767 bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]);
769 /* Add these bits to live-on-entry for the pred. if there are any
770 changes, and pred_bb has been visited already, add it to the
771 revisit stack. */
772 change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
773 if (TEST_BIT (visited, pred_bb->index) && change)
775 RESET_BIT (visited, pred_bb->index);
776 *(live->stack_top)++ = pred_bb->index;
782 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
783 of all the variables. */
785 static void
786 live_worklist (tree_live_info_p live)
788 unsigned b;
789 basic_block bb;
790 sbitmap visited = sbitmap_alloc (last_basic_block + 1);
791 bitmap tmp = BITMAP_ALLOC (NULL);
793 sbitmap_zero (visited);
795 /* Visit all the blocks in reverse order and propagate live on entry values
796 into the predecessors blocks. */
797 FOR_EACH_BB_REVERSE (bb)
798 loe_visit_block (live, bb, visited, tmp);
800 /* Process any blocks which require further iteration. */
801 while (live->stack_top != live->work_stack)
803 b = *--(live->stack_top);
804 loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
807 BITMAP_FREE (tmp);
808 sbitmap_free (visited);
812 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
813 links. Set the live on entry fields in LIVE. Def's are marked temporarily
814 in the liveout vector. */
816 static void
817 set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
819 int p;
820 tree stmt;
821 use_operand_p use;
822 basic_block def_bb = NULL;
823 imm_use_iterator imm_iter;
824 bool global = false;
826 p = var_to_partition (live->map, ssa_name);
827 if (p == NO_PARTITION)
828 return;
830 stmt = SSA_NAME_DEF_STMT (ssa_name);
831 if (stmt)
833 def_bb = bb_for_stmt (stmt);
834 /* Mark defs in liveout bitmap temporarily. */
835 if (def_bb)
836 bitmap_set_bit (live->liveout[def_bb->index], p);
838 else
839 def_bb = ENTRY_BLOCK_PTR;
841 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
842 add it to the list of live on entry blocks. */
843 FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
845 tree use_stmt = USE_STMT (use);
846 basic_block add_block = NULL;
848 if (TREE_CODE (use_stmt) == PHI_NODE)
850 /* Uses in PHI's are considered to be live at exit of the SRC block
851 as this is where a copy would be inserted. Check to see if it is
852 defined in that block, or whether its live on entry. */
853 int index = PHI_ARG_INDEX_FROM_USE (use);
854 edge e = PHI_ARG_EDGE (use_stmt, index);
855 if (e->src != ENTRY_BLOCK_PTR)
857 if (e->src != def_bb)
858 add_block = e->src;
861 else
863 /* If its not defined in this block, its live on entry. */
864 basic_block use_bb = bb_for_stmt (use_stmt);
865 if (use_bb != def_bb)
866 add_block = use_bb;
869 /* If there was a live on entry use, set the bit. */
870 if (add_block)
872 global = true;
873 bitmap_set_bit (live->livein[add_block->index], p);
877 /* If SSA_NAME is live on entry to at least one block, fill in all the live
878 on entry blocks between the def and all the uses. */
879 if (global)
880 bitmap_set_bit (live->global, p);
884 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
886 void
887 calculate_live_on_exit (tree_live_info_p liveinfo)
889 unsigned i;
890 int p;
891 tree t, phi;
892 basic_block bb;
893 edge e;
894 edge_iterator ei;
896 /* live on entry calculations used liveout vectors for defs, clear them. */
897 FOR_EACH_BB (bb)
898 bitmap_clear (liveinfo->liveout[bb->index]);
900 /* Set all the live-on-exit bits for uses in PHIs. */
901 FOR_EACH_BB (bb)
903 /* Mark the PHI arguments which are live on exit to the pred block. */
904 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
905 for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
907 t = PHI_ARG_DEF (phi, i);
908 if (TREE_CODE (t) != SSA_NAME)
909 continue;
910 p = var_to_partition (liveinfo->map, t);
911 if (p == NO_PARTITION)
912 continue;
913 e = PHI_ARG_EDGE (phi, i);
914 if (e->src != ENTRY_BLOCK_PTR)
915 bitmap_set_bit (liveinfo->liveout[e->src->index], p);
918 /* Add each successors live on entry to this bock live on exit. */
919 FOR_EACH_EDGE (e, ei, bb->succs)
920 if (e->dest != EXIT_BLOCK_PTR)
921 bitmap_ior_into (liveinfo->liveout[bb->index],
922 live_on_entry (liveinfo, e->dest));
927 /* Given partition map MAP, calculate all the live on entry bitmaps for
928 each partition. Return a new live info object. */
930 tree_live_info_p
931 calculate_live_ranges (var_map map)
933 tree var;
934 unsigned i;
935 tree_live_info_p live;
937 live = new_tree_live_info (map);
938 for (i = 0; i < num_var_partitions (map); i++)
940 var = partition_to_var (map, i);
941 if (var != NULL_TREE)
942 set_var_live_on_entry (var, live);
945 live_worklist (live);
947 #ifdef ENABLE_CHECKING
948 verify_live_on_entry (live);
949 #endif
951 calculate_live_on_exit (live);
952 return live;
956 /* Output partition map MAP to file F. */
958 void
959 dump_var_map (FILE *f, var_map map)
961 int t;
962 unsigned x, y;
963 int p;
965 fprintf (f, "\nPartition map \n\n");
967 for (x = 0; x < map->num_partitions; x++)
969 if (map->view_to_partition != NULL)
970 p = map->view_to_partition[x];
971 else
972 p = x;
974 if (map->partition_to_var[p] == NULL_TREE)
975 continue;
977 t = 0;
978 for (y = 1; y < num_ssa_names; y++)
980 p = partition_find (map->var_partition, y);
981 if (map->partition_to_view)
982 p = map->partition_to_view[p];
983 if (p == (int)x)
985 if (t++ == 0)
987 fprintf(f, "Partition %d (", x);
988 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
989 fprintf (f, " - ");
991 fprintf (f, "%d ", y);
994 if (t != 0)
995 fprintf (f, ")\n");
997 fprintf (f, "\n");
1001 /* Output live range info LIVE to file F, controlled by FLAG. */
1003 void
1004 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1006 basic_block bb;
1007 unsigned i;
1008 var_map map = live->map;
1009 bitmap_iterator bi;
1011 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1013 FOR_EACH_BB (bb)
1015 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1016 EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
1018 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1019 fprintf (f, " ");
1021 fprintf (f, "\n");
1025 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1027 FOR_EACH_BB (bb)
1029 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1030 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1032 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1033 fprintf (f, " ");
1035 fprintf (f, "\n");
1041 #ifdef ENABLE_CHECKING
1042 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
1044 void
1045 register_ssa_partition_check (tree ssa_var)
1047 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1048 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1050 fprintf (stderr, "Illegally registering a virtual SSA name :");
1051 print_generic_expr (stderr, ssa_var, TDF_SLIM);
1052 fprintf (stderr, " in the SSA->Normal phase.\n");
1053 internal_error ("SSA corruption");
1058 /* Verify that the info in LIVE matches the current cfg. */
1060 static void
1061 verify_live_on_entry (tree_live_info_p live)
1063 unsigned i;
1064 tree var;
1065 tree phi, stmt;
1066 basic_block bb;
1067 edge e;
1068 int num;
1069 edge_iterator ei;
1070 var_map map = live->map;
1072 /* Check for live on entry partitions and report those with a DEF in
1073 the program. This will typically mean an optimization has done
1074 something wrong. */
1075 bb = ENTRY_BLOCK_PTR;
1076 num = 0;
1077 FOR_EACH_EDGE (e, ei, bb->succs)
1079 int entry_block = e->dest->index;
1080 if (e->dest == EXIT_BLOCK_PTR)
1081 continue;
1082 for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1084 basic_block tmp;
1085 tree d;
1086 bitmap loe;
1087 var = partition_to_var (map, i);
1088 stmt = SSA_NAME_DEF_STMT (var);
1089 tmp = bb_for_stmt (stmt);
1090 d = gimple_default_def (cfun, SSA_NAME_VAR (var));
1092 loe = live_on_entry (live, e->dest);
1093 if (loe && bitmap_bit_p (loe, i))
1095 if (!IS_EMPTY_STMT (stmt))
1097 num++;
1098 print_generic_expr (stderr, var, TDF_SLIM);
1099 fprintf (stderr, " is defined ");
1100 if (tmp)
1101 fprintf (stderr, " in BB%d, ", tmp->index);
1102 fprintf (stderr, "by:\n");
1103 print_generic_expr (stderr, stmt, TDF_SLIM);
1104 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1105 entry_block);
1106 fprintf (stderr, " So it appears to have multiple defs.\n");
1108 else
1110 if (d != var)
1112 num++;
1113 print_generic_expr (stderr, var, TDF_SLIM);
1114 fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
1115 if (d)
1117 fprintf (stderr, " but is not the default def of ");
1118 print_generic_expr (stderr, d, TDF_SLIM);
1119 fprintf (stderr, "\n");
1121 else
1122 fprintf (stderr, " and there is no default def.\n");
1126 else
1127 if (d == var)
1129 /* The only way this var shouldn't be marked live on entry is
1130 if it occurs in a PHI argument of the block. */
1131 int z, ok = 0;
1132 for (phi = phi_nodes (e->dest);
1133 phi && !ok;
1134 phi = PHI_CHAIN (phi))
1136 for (z = 0; z < PHI_NUM_ARGS (phi); z++)
1137 if (var == PHI_ARG_DEF (phi, z))
1139 ok = 1;
1140 break;
1143 if (ok)
1144 continue;
1145 num++;
1146 print_generic_expr (stderr, var, TDF_SLIM);
1147 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1148 entry_block);
1149 fprintf (stderr, "but it is a default def so it should be.\n");
1153 gcc_assert (num <= 0);
1155 #endif