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)
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/>. */
23 #include "coretypes.h"
26 #include "diagnostic.h"
28 #include "tree-flow.h"
29 #include "tree-dump.h"
30 #include "tree-ssa-live.h"
35 #ifdef ENABLE_CHECKING
36 static void verify_live_on_entry (tree_live_info_p
);
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. */
57 var_map_base_init (var_map map
)
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);
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
);
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
++)
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
);
115 /* Remove the base table in MAP. */
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. */
132 init_var_map (int size
)
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
;
153 /* Free memory associated with MAP. */
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
);
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
)
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
));
188 p1
= var_to_partition (map
, var1
);
189 if (map
->view_to_partition
)
190 p1
= map
->view_to_partition
[p1
];
194 if (TREE_CODE (var2
) == SSA_NAME
)
195 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
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
;
213 gcc_assert (p1
!= NO_PARTITION
);
214 gcc_assert (p2
!= NO_PARTITION
);
219 p3
= partition_union (map
->var_partition
, p1
, p2
);
221 if (map
->partition_to_view
)
222 p3
= map
->partition_to_view
[p3
];
225 change_partition_var (map
, root_var
, p3
);
227 change_partition_var (map
, other_var
, 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
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
256 partition_view_init (var_map map
)
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
;
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. */
295 partition_view_fini (var_map map
, bitmap selected
)
298 unsigned count
, i
, x
, limit
;
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. */
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));
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
);
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. */
338 partition_view_normal (var_map map
, bool want_bases
)
342 used
= partition_view_init (map
);
343 partition_view_fini (map
, used
);
346 var_map_base_init (map
);
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
357 partition_view_bitmap (var_map map
, bitmap only
, bool want_bases
)
360 bitmap new_partitions
= BITMAP_ALLOC (NULL
);
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
);
375 var_map_base_init (map
);
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. */
386 change_partition_var (var_map map
, tree var
, int part
)
390 gcc_assert (TREE_CODE (var
) != SSA_NAME
);
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
*);
402 /* Helper function for mark_all_vars_used, called via walk_tree. */
405 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
,
406 void *data ATTRIBUTE_UNUSED
)
409 enum tree_code_class c
= TREE_CODE_CLASS (TREE_CODE (t
));
412 if (TREE_CODE (t
) == SSA_NAME
)
413 t
= SSA_NAME_VAR (t
);
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
));
424 mark_all_vars_used (&TMR_BASE (t
));
425 mark_all_vars_used (&TMR_INDEX (t
));
430 /* Only need to mark VAR_DECLS; parameters and return results are not
431 eliminated as unused. */
432 if (TREE_CODE (t
) == VAR_DECL
)
435 if (IS_TYPE_OR_DECL_P (t
))
441 /* Mark the scope block SCOPE and its subblocks unused when they can be
442 possibly eliminated if dead. */
445 mark_scope_block_unused (tree scope
)
448 TREE_USED (scope
) = false;
449 if (!(*debug_hooks
->ignore_block
) (scope
))
450 TREE_USED (scope
) = true;
451 for (t
= BLOCK_SUBBLOCKS (scope
); t
; t
= BLOCK_CHAIN (t
))
452 mark_scope_block_unused (t
);
455 /* Look if the block is dead (by possibly eliminating its dead subblocks)
456 and return true if so.
457 Block is declared dead if:
458 1) No statements are associated with it.
459 2) Declares no live variables
460 3) All subblocks are dead
461 or there is precisely one subblocks and the block
462 has same abstract origin as outer block and declares
463 no variables, so it is pure wrapper.
464 When we are not outputting full debug info, we also eliminate dead variables
465 out of scope blocks to let them to be recycled by GGC and to save copying work
466 done by the inliner. */
469 remove_unused_scope_block_p (tree scope
)
472 bool unused
= !TREE_USED (scope
);
475 for (t
= &BLOCK_SUBBLOCKS (scope
); *t
;)
476 if (remove_unused_scope_block_p (*t
))
478 if (BLOCK_SUBBLOCKS (*t
))
480 tree next
= BLOCK_CHAIN (*t
);
481 tree supercontext
= BLOCK_SUPERCONTEXT (*t
);
482 *t
= BLOCK_SUBBLOCKS (*t
);
483 gcc_assert (!BLOCK_CHAIN (*t
));
484 BLOCK_CHAIN (*t
) = next
;
485 BLOCK_SUPERCONTEXT (*t
) = supercontext
;
486 t
= &BLOCK_CHAIN (*t
);
490 *t
= BLOCK_CHAIN (*t
);
494 t
= &BLOCK_CHAIN (*t
);
497 /* Outer scope is always used. */
498 if (!BLOCK_SUPERCONTEXT (scope
)
499 || TREE_CODE (BLOCK_SUPERCONTEXT (scope
)) == FUNCTION_DECL
)
501 /* If there are more than one live subblocks, it is used. */
502 else if (nsubblocks
> 1)
504 /* When there is only one subblock, see if it is just wrapper we can
505 ignore. Wrappers are not declaring any variables and not changing
507 else if (nsubblocks
<= 1
508 && (BLOCK_VARS (scope
)
509 || (BLOCK_ABSTRACT_ORIGIN (scope
)
510 != BLOCK_ABSTRACT_ORIGIN (BLOCK_SUPERCONTEXT (scope
)))))
515 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
516 eliminated during the tree->rtl conversion process. */
519 mark_all_vars_used (tree
*expr_p
)
521 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
525 /* Remove local variables that are not referenced in the IL. */
528 remove_unused_locals (void)
532 referenced_var_iterator rvi
;
535 mark_scope_block_unused (DECL_INITIAL (current_function_decl
));
536 /* Assume all locals are unused. */
537 FOR_EACH_REFERENCED_VAR (t
, rvi
)
538 var_ann (t
)->used
= false;
540 /* Walk the CFG marking all referenced symbols. */
543 block_stmt_iterator bsi
;
546 /* Walk the statements. */
547 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
548 mark_all_vars_used (bsi_stmt_ptr (bsi
));
550 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
555 /* No point processing globals. */
556 if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi
))))
559 def
= PHI_RESULT (phi
);
560 mark_all_vars_used (&def
);
562 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_ALL_USES
)
564 tree arg
= USE_FROM_PTR (arg_p
);
565 mark_all_vars_used (&arg
);
570 /* Remove unmarked vars and clear used flag. */
571 for (cell
= &cfun
->unexpanded_var_list
; *cell
; )
573 tree var
= TREE_VALUE (*cell
);
575 if (TREE_CODE (var
) != FUNCTION_DECL
576 && (!(ann
= var_ann (var
))
579 *cell
= TREE_CHAIN (*cell
);
582 cell
= &TREE_CHAIN (*cell
);
585 /* Remove unused variables from REFERENCED_VARs. As a special
586 exception keep the variables that are believed to be aliased.
587 Those can't be easily removed from the alias sets and operand
588 caches. They will be removed shortly after the next may_alias
589 pass is performed. */
590 FOR_EACH_REFERENCED_VAR (t
, rvi
)
591 if (!is_global_var (t
)
593 && TREE_CODE (t
) != PARM_DECL
594 && TREE_CODE (t
) != RESULT_DECL
595 && !(ann
= var_ann (t
))->used
596 && !ann
->symbol_mem_tag
597 && !TREE_ADDRESSABLE (t
))
598 remove_referenced_var (t
);
599 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl
));
603 /* Allocate and return a new live range information object base on MAP. */
605 static tree_live_info_p
606 new_tree_live_info (var_map map
)
608 tree_live_info_p live
;
611 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
613 live
->num_blocks
= last_basic_block
;
615 live
->livein
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
616 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
617 live
->livein
[x
] = BITMAP_ALLOC (NULL
);
619 live
->liveout
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
620 for (x
= 0; x
< (unsigned)last_basic_block
; x
++)
621 live
->liveout
[x
] = BITMAP_ALLOC (NULL
);
623 live
->work_stack
= XNEWVEC (int, last_basic_block
);
624 live
->stack_top
= live
->work_stack
;
626 live
->global
= BITMAP_ALLOC (NULL
);
631 /* Free storage for live range info object LIVE. */
634 delete_tree_live_info (tree_live_info_p live
)
638 BITMAP_FREE (live
->global
);
639 free (live
->work_stack
);
641 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
642 BITMAP_FREE (live
->liveout
[x
]);
643 free (live
->liveout
);
645 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
646 BITMAP_FREE (live
->livein
[x
]);
653 /* Visit basic block BB and propagate any required live on entry bits from
654 LIVE into the predecessors. VISITED is the bitmap of visited blocks.
655 TMP is a temporary work bitmap which is passed in to avoid reallocating
659 loe_visit_block (tree_live_info_p live
, basic_block bb
, sbitmap visited
,
667 gcc_assert (!TEST_BIT (visited
, bb
->index
));
669 SET_BIT (visited
, bb
->index
);
670 loe
= live_on_entry (live
, bb
);
672 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
675 if (pred_bb
== ENTRY_BLOCK_PTR
)
677 /* TMP is variables live-on-entry from BB that aren't defined in the
678 predecessor block. This should be the live on entry vars to pred.
679 Note that liveout is the DEFs in a block while live on entry is
681 bitmap_and_compl (tmp
, loe
, live
->liveout
[pred_bb
->index
]);
683 /* Add these bits to live-on-entry for the pred. if there are any
684 changes, and pred_bb has been visited already, add it to the
686 change
= bitmap_ior_into (live_on_entry (live
, pred_bb
), tmp
);
687 if (TEST_BIT (visited
, pred_bb
->index
) && change
)
689 RESET_BIT (visited
, pred_bb
->index
);
690 *(live
->stack_top
)++ = pred_bb
->index
;
696 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
697 of all the variables. */
700 live_worklist (tree_live_info_p live
)
704 sbitmap visited
= sbitmap_alloc (last_basic_block
+ 1);
705 bitmap tmp
= BITMAP_ALLOC (NULL
);
707 sbitmap_zero (visited
);
709 /* Visit all the blocks in reverse order and propagate live on entry values
710 into the predecessors blocks. */
711 FOR_EACH_BB_REVERSE (bb
)
712 loe_visit_block (live
, bb
, visited
, tmp
);
714 /* Process any blocks which require further iteration. */
715 while (live
->stack_top
!= live
->work_stack
)
717 b
= *--(live
->stack_top
);
718 loe_visit_block (live
, BASIC_BLOCK (b
), visited
, tmp
);
722 sbitmap_free (visited
);
726 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
727 links. Set the live on entry fields in LIVE. Def's are marked temporarily
728 in the liveout vector. */
731 set_var_live_on_entry (tree ssa_name
, tree_live_info_p live
)
736 basic_block def_bb
= NULL
;
737 imm_use_iterator imm_iter
;
740 p
= var_to_partition (live
->map
, ssa_name
);
741 if (p
== NO_PARTITION
)
744 stmt
= SSA_NAME_DEF_STMT (ssa_name
);
747 def_bb
= bb_for_stmt (stmt
);
748 /* Mark defs in liveout bitmap temporarily. */
750 bitmap_set_bit (live
->liveout
[def_bb
->index
], p
);
753 def_bb
= ENTRY_BLOCK_PTR
;
755 /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
756 add it to the list of live on entry blocks. */
757 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, ssa_name
)
759 tree use_stmt
= USE_STMT (use
);
760 basic_block add_block
= NULL
;
762 if (TREE_CODE (use_stmt
) == PHI_NODE
)
764 /* Uses in PHI's are considered to be live at exit of the SRC block
765 as this is where a copy would be inserted. Check to see if it is
766 defined in that block, or whether its live on entry. */
767 int index
= PHI_ARG_INDEX_FROM_USE (use
);
768 edge e
= PHI_ARG_EDGE (use_stmt
, index
);
769 if (e
->src
!= ENTRY_BLOCK_PTR
)
771 if (e
->src
!= def_bb
)
777 /* If its not defined in this block, its live on entry. */
778 basic_block use_bb
= bb_for_stmt (use_stmt
);
779 if (use_bb
!= def_bb
)
783 /* If there was a live on entry use, set the bit. */
787 bitmap_set_bit (live
->livein
[add_block
->index
], p
);
791 /* If SSA_NAME is live on entry to at least one block, fill in all the live
792 on entry blocks between the def and all the uses. */
794 bitmap_set_bit (live
->global
, p
);
798 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
801 calculate_live_on_exit (tree_live_info_p liveinfo
)
810 /* live on entry calculations used liveout vectors for defs, clear them. */
812 bitmap_clear (liveinfo
->liveout
[bb
->index
]);
814 /* Set all the live-on-exit bits for uses in PHIs. */
817 /* Mark the PHI arguments which are live on exit to the pred block. */
818 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
819 for (i
= 0; i
< (unsigned)PHI_NUM_ARGS (phi
); i
++)
821 t
= PHI_ARG_DEF (phi
, i
);
822 if (TREE_CODE (t
) != SSA_NAME
)
824 p
= var_to_partition (liveinfo
->map
, t
);
825 if (p
== NO_PARTITION
)
827 e
= PHI_ARG_EDGE (phi
, i
);
828 if (e
->src
!= ENTRY_BLOCK_PTR
)
829 bitmap_set_bit (liveinfo
->liveout
[e
->src
->index
], p
);
832 /* Add each successors live on entry to this bock live on exit. */
833 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
834 if (e
->dest
!= EXIT_BLOCK_PTR
)
835 bitmap_ior_into (liveinfo
->liveout
[bb
->index
],
836 live_on_entry (liveinfo
, e
->dest
));
841 /* Given partition map MAP, calculate all the live on entry bitmaps for
842 each partition. Return a new live info object. */
845 calculate_live_ranges (var_map map
)
849 tree_live_info_p live
;
851 live
= new_tree_live_info (map
);
852 for (i
= 0; i
< num_var_partitions (map
); i
++)
854 var
= partition_to_var (map
, i
);
855 if (var
!= NULL_TREE
)
856 set_var_live_on_entry (var
, live
);
859 live_worklist (live
);
861 #ifdef ENABLE_CHECKING
862 verify_live_on_entry (live
);
865 calculate_live_on_exit (live
);
870 /* Output partition map MAP to file F. */
873 dump_var_map (FILE *f
, var_map map
)
879 fprintf (f
, "\nPartition map \n\n");
881 for (x
= 0; x
< map
->num_partitions
; x
++)
883 if (map
->view_to_partition
!= NULL
)
884 p
= map
->view_to_partition
[x
];
888 if (map
->partition_to_var
[p
] == NULL_TREE
)
892 for (y
= 1; y
< num_ssa_names
; y
++)
894 p
= partition_find (map
->var_partition
, y
);
895 if (map
->partition_to_view
)
896 p
= map
->partition_to_view
[p
];
901 fprintf(f
, "Partition %d (", x
);
902 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
905 fprintf (f
, "%d ", y
);
915 /* Output live range info LIVE to file F, controlled by FLAG. */
918 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
922 var_map map
= live
->map
;
925 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
929 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
930 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[bb
->index
], 0, i
, bi
)
932 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
939 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
943 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
944 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
, bi
)
946 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
955 #ifdef ENABLE_CHECKING
956 /* Verify that SSA_VAR is a non-virtual SSA_NAME. */
959 register_ssa_partition_check (tree ssa_var
)
961 gcc_assert (TREE_CODE (ssa_var
) == SSA_NAME
);
962 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var
)))
964 fprintf (stderr
, "Illegally registering a virtual SSA name :");
965 print_generic_expr (stderr
, ssa_var
, TDF_SLIM
);
966 fprintf (stderr
, " in the SSA->Normal phase.\n");
967 internal_error ("SSA corruption");
972 /* Verify that the info in LIVE matches the current cfg. */
975 verify_live_on_entry (tree_live_info_p live
)
984 var_map map
= live
->map
;
986 /* Check for live on entry partitions and report those with a DEF in
987 the program. This will typically mean an optimization has done
989 bb
= ENTRY_BLOCK_PTR
;
991 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
993 int entry_block
= e
->dest
->index
;
994 if (e
->dest
== EXIT_BLOCK_PTR
)
996 for (i
= 0; i
< (unsigned)num_var_partitions (map
); i
++)
1001 var
= partition_to_var (map
, i
);
1002 stmt
= SSA_NAME_DEF_STMT (var
);
1003 tmp
= bb_for_stmt (stmt
);
1004 d
= gimple_default_def (cfun
, SSA_NAME_VAR (var
));
1006 loe
= live_on_entry (live
, e
->dest
);
1007 if (loe
&& bitmap_bit_p (loe
, i
))
1009 if (!IS_EMPTY_STMT (stmt
))
1012 print_generic_expr (stderr
, var
, TDF_SLIM
);
1013 fprintf (stderr
, " is defined ");
1015 fprintf (stderr
, " in BB%d, ", tmp
->index
);
1016 fprintf (stderr
, "by:\n");
1017 print_generic_expr (stderr
, stmt
, TDF_SLIM
);
1018 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
1020 fprintf (stderr
, " So it appears to have multiple defs.\n");
1027 print_generic_expr (stderr
, var
, TDF_SLIM
);
1028 fprintf (stderr
, " is live-on-entry to BB%d ",entry_block
);
1031 fprintf (stderr
, " but is not the default def of ");
1032 print_generic_expr (stderr
, d
, TDF_SLIM
);
1033 fprintf (stderr
, "\n");
1036 fprintf (stderr
, " and there is no default def.\n");
1043 /* The only way this var shouldn't be marked live on entry is
1044 if it occurs in a PHI argument of the block. */
1046 for (phi
= phi_nodes (e
->dest
);
1048 phi
= PHI_CHAIN (phi
))
1050 for (z
= 0; z
< PHI_NUM_ARGS (phi
); z
++)
1051 if (var
== PHI_ARG_DEF (phi
, z
))
1060 print_generic_expr (stderr
, var
, TDF_SLIM
);
1061 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
1063 fprintf (stderr
, "but it is a default def so it should be.\n");
1067 gcc_assert (num
<= 0);