1 /* Liveness for SSA trees.
2 Copyright (C) 2003 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 2, 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 COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-inline.h"
37 #include "tree-alias-common.h"
39 #include "tree-dump.h"
40 #include "tree-ssa-live.h"
42 static void live_worklist (tree_live_info_p
, varray_type
, int);
43 static tree_live_info_p
new_tree_live_info (var_map
);
44 static inline void set_if_valid (var_map
, bitmap
, tree
);
45 static inline void add_livein_if_notdef (tree_live_info_p
, bitmap
,
47 static inline void register_ssa_partition (var_map
, tree
, bool);
48 static inline void add_conflicts_if_valid (tpa_p
, conflict_graph
,
49 var_map
, bitmap
, tree
);
50 static partition_pair_p
find_partition_pair (coalesce_list_p
, int, int, bool);
52 /* This is where the mapping from SSA version number to real storage variable
55 All SSA versions of the same variable may not ultimately be mapped back to
56 the same real variable. In that instance, we need to detect the live
57 range overlap, and give one of the variable new storage. The vector
58 'partition_to_var' tracks which partition maps to which variable.
60 Given a VAR, it is sometimes desirable to know which partition that VAR
61 represents. There is an additional field in the variable annotation to
62 track that information. */
64 /* Create a variable partition map of SIZE, initialize and return it. */
67 init_var_map (int size
)
71 map
= (var_map
) xmalloc (sizeof (struct _var_map
));
72 map
->var_partition
= partition_new (size
);
74 = (tree
*)xmalloc (size
* sizeof (tree
));
75 memset (map
->partition_to_var
, 0, size
* sizeof (tree
));
77 map
->partition_to_compact
= NULL
;
78 map
->compact_to_partition
= NULL
;
79 map
->num_partitions
= size
;
80 map
->partition_size
= size
;
81 map
->ref_count
= NULL
;
86 /* Free memory associated with MAP. */
89 delete_var_map (var_map map
)
91 free (map
->partition_to_var
);
92 partition_delete (map
->var_partition
);
93 if (map
->partition_to_compact
)
94 free (map
->partition_to_compact
);
95 if (map
->compact_to_partition
)
96 free (map
->compact_to_partition
);
98 free (map
->ref_count
);
103 /* This function will combine the partitions in MAP for VAR1 and VAR2. It
104 Returns the partition which represents the new partition. If the two
105 partitions cannot be combined, NO_PARTITION is returned. */
108 var_union (var_map map
, tree var1
, tree var2
)
111 tree root_var
= NULL_TREE
;
112 tree other_var
= NULL_TREE
;
114 /* This is independent of partition_to_compact. If partition_to_compact is
115 on, then whichever one of these partitions is absorbed will never have a
116 dereference into the partition_to_compact array any more. */
118 if (TREE_CODE (var1
) == SSA_NAME
)
119 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
122 p1
= var_to_partition (map
, var1
);
123 if (map
->compact_to_partition
)
124 p1
= map
->compact_to_partition
[p1
];
128 if (TREE_CODE (var2
) == SSA_NAME
)
129 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
132 p2
= var_to_partition (map
, var2
);
133 if (map
->compact_to_partition
)
134 p2
= map
->compact_to_partition
[p2
];
136 /* If there is no root_var set, or its not a user variable, set the
137 root_var to this one. */
138 if (!root_var
|| is_gimple_tmp_var (root_var
))
140 other_var
= root_var
;
147 if (p1
== NO_PARTITION
|| p2
== NO_PARTITION
)
153 p3
= partition_union (map
->var_partition
, p1
, p2
);
155 if (map
->partition_to_compact
)
156 p3
= map
->partition_to_compact
[p3
];
159 change_partition_var (map
, root_var
, p3
);
161 change_partition_var (map
, other_var
, p3
);
167 /* Compress the partition numbers in MAP such that they fall in the range
168 0..(num_partitions-1) instead of wherever they turned out during
169 the partitioning exercise. This removes any references to unused
170 partitions, thereby allowing bitmaps and other vectors to be much
171 denser. Compression type is controlled by FLAGS.
173 This is implemented such that compaction doesn't affect partitioning.
174 Ie., once partitions are created and possibly merged, running one
175 or more different kind of compaction will not affect the partitions
176 themselves. Their index might change, but all the same variables will
177 still be members of the same partition group. This allows work on reduced
178 sets, and no loss of information when a larger set is later desired.
180 In particular, coalescing can work on partitions which have 2 or more
181 definitions, and then 'recompact' later to include all the single
182 definitions for assignment to program variables. */
185 compact_var_map (var_map map
, int flags
)
188 int x
, limit
, count
, tmp
, root
, root_i
;
190 root_var_p rv
= NULL
;
192 limit
= map
->partition_size
;
193 used
= sbitmap_alloc (limit
);
196 /* Already compressed? Abandon the old one. */
197 if (map
->partition_to_compact
)
199 free (map
->partition_to_compact
);
200 map
->partition_to_compact
= NULL
;
202 if (map
->compact_to_partition
)
204 free (map
->compact_to_partition
);
205 map
->compact_to_partition
= NULL
;
208 map
->num_partitions
= map
->partition_size
;
210 if (flags
& VARMAP_NO_SINGLE_DEFS
)
211 rv
= root_var_init (map
);
213 map
->partition_to_compact
= (int *)xmalloc (limit
* sizeof (int));
214 memset (map
->partition_to_compact
, 0xff, (limit
* sizeof (int)));
216 /* Find out which partitions are actually referenced. */
218 for (x
= 0; x
< limit
; x
++)
220 tmp
= partition_find (map
->var_partition
, x
);
221 if (!TEST_BIT (used
, tmp
) && map
->partition_to_var
[tmp
] != NULL_TREE
)
223 /* It is referenced, check to see if there is more than one version
224 in the root_var table, if one is available. */
227 root
= root_var_find (rv
, tmp
);
228 root_i
= root_var_first_partition (rv
, root
);
229 /* If there is only one, don't include this in the compaction. */
230 if (root_var_next_partition (rv
, root_i
) == ROOT_VAR_NONE
)
238 /* Build a compacted partitioning. */
241 map
->compact_to_partition
= (int *)xmalloc (count
* sizeof (int));
243 /* SSA renaming begins at 1, so skip 0 when compacting. */
244 EXECUTE_IF_SET_IN_SBITMAP (used
, 1, x
,
246 map
->partition_to_compact
[x
] = count
;
247 map
->compact_to_partition
[count
] = x
;
248 var
= map
->partition_to_var
[x
];
249 if (TREE_CODE (var
) != SSA_NAME
)
250 change_partition_var (map
, var
, count
);
256 free (map
->partition_to_compact
);
257 map
->partition_to_compact
= NULL
;
260 map
->num_partitions
= count
;
263 root_var_delete (rv
);
268 /* This function is used to change the representative variable in MAP for VAR's
269 partition from an SSA_NAME variable to a regular variable. This allows
270 partitions to be mapped back to real variables. */
273 change_partition_var (var_map map
, tree var
, int part
)
277 if (TREE_CODE (var
) == SSA_NAME
)
281 ann
->out_of_ssa_tag
= 1;
282 VAR_ANN_PARTITION (ann
) = part
;
283 if (map
->compact_to_partition
)
284 map
->partition_to_var
[map
->compact_to_partition
[part
]] = var
;
288 /* Helper function for mark_all_vars_used, called via walk_tree. */
291 mark_all_vars_used_1 (tree
*tp
, int *walk_subtrees
,
292 void *data ATTRIBUTE_UNUSED
)
296 /* Only need to mark VAR_DECLS; parameters and return results are not
297 eliminated as unused. */
298 if (TREE_CODE (t
) == VAR_DECL
)
301 if (DECL_P (t
) || TYPE_P (t
))
307 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
308 eliminated during the tree->rtl conversion process. */
311 mark_all_vars_used (tree
*expr_p
)
313 walk_tree (expr_p
, mark_all_vars_used_1
, NULL
, NULL
);
316 /* This function looks through the program and uses FLAGS to determine what
317 SSA versioned variables are given entries in a new partition table. This
318 new partition map is returned. */
321 create_ssa_var_map (int flags
)
323 block_stmt_iterator bsi
;
329 v_may_def_optype v_may_defs
;
330 v_must_def_optype v_must_defs
;
335 #if defined ENABLE_CHECKING
336 sbitmap used_in_real_ops
;
337 sbitmap used_in_virtual_ops
;
340 map
= init_var_map (num_ssa_names
+ 1);
342 #if defined ENABLE_CHECKING
343 used_in_real_ops
= sbitmap_alloc (num_referenced_vars
);
344 sbitmap_zero (used_in_real_ops
);
346 used_in_virtual_ops
= sbitmap_alloc (num_referenced_vars
);
347 sbitmap_zero (used_in_virtual_ops
);
350 if (flags
& SSA_VAR_MAP_REF_COUNT
)
353 = (int *)xmalloc (((num_ssa_names
+ 1) * sizeof (int)));
354 memset (map
->ref_count
, 0, (num_ssa_names
+ 1) * sizeof (int));
360 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
363 register_ssa_partition (map
, PHI_RESULT (phi
), false);
364 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
366 arg
= PHI_ARG_DEF (phi
, i
);
367 if (TREE_CODE (arg
) == SSA_NAME
)
368 register_ssa_partition (map
, arg
, true);
370 mark_all_vars_used (&PHI_ARG_DEF_TREE (phi
, i
));
374 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
376 stmt
= bsi_stmt (bsi
);
377 get_stmt_operands (stmt
);
378 ann
= stmt_ann (stmt
);
380 /* Register USE and DEF operands in each statement. */
381 uses
= USE_OPS (ann
);
382 for (x
= 0; x
< NUM_USES (uses
); x
++)
384 use
= USE_OP (uses
, x
);
385 register_ssa_partition (map
, use
, true);
387 #if defined ENABLE_CHECKING
388 SET_BIT (used_in_real_ops
, var_ann (SSA_NAME_VAR (use
))->uid
);
392 defs
= DEF_OPS (ann
);
393 for (x
= 0; x
< NUM_DEFS (defs
); x
++)
395 dest
= DEF_OP (defs
, x
);
396 register_ssa_partition (map
, dest
, false);
398 #if defined ENABLE_CHECKING
399 SET_BIT (used_in_real_ops
, var_ann (SSA_NAME_VAR (dest
))->uid
);
403 /* While we do not care about virtual operands for
404 out of SSA, we do need to look at them to make sure
405 we mark all the variables which are used. */
406 vuses
= VUSE_OPS (ann
);
407 for (x
= 0; x
< NUM_VUSES (vuses
); x
++)
409 tree var
= VUSE_OP (vuses
, x
);
410 #if defined ENABLE_CHECKING
411 SET_BIT (used_in_virtual_ops
, var_ann (SSA_NAME_VAR (var
))->uid
);
415 v_may_defs
= V_MAY_DEF_OPS (ann
);
416 for (x
= 0; x
< NUM_V_MAY_DEFS (v_may_defs
); x
++)
418 tree var
= V_MAY_DEF_OP (v_may_defs
, x
);
419 #if defined ENABLE_CHECKING
420 SET_BIT (used_in_virtual_ops
, var_ann (SSA_NAME_VAR (var
))->uid
);
424 v_must_defs
= V_MUST_DEF_OPS (ann
);
425 for (x
= 0; x
< NUM_V_MUST_DEFS (v_must_defs
); x
++)
427 tree var
= V_MUST_DEF_OP (v_must_defs
, x
);
428 #if defined ENABLE_CHECKING
429 SET_BIT (used_in_virtual_ops
, var_ann (SSA_NAME_VAR (var
))->uid
);
433 mark_all_vars_used (bsi_stmt_ptr (bsi
));
437 #if defined ENABLE_CHECKING
440 sbitmap both
= sbitmap_alloc (num_referenced_vars
);
441 sbitmap_a_and_b (both
, used_in_real_ops
, used_in_virtual_ops
);
442 if (sbitmap_first_set_bit (both
) >= 0)
444 EXECUTE_IF_SET_IN_SBITMAP (both
, 0, i
,
445 fprintf (stderr
, "Variable %s used in real and virtual operands\n",
446 get_name (referenced_var (i
))));
450 sbitmap_free (used_in_real_ops
);
451 sbitmap_free (used_in_virtual_ops
);
460 /* Allocate and return a new live range information object base on MAP. */
462 static tree_live_info_p
463 new_tree_live_info (var_map map
)
465 tree_live_info_p live
;
468 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
470 live
->num_blocks
= last_basic_block
;
472 live
->global
= BITMAP_XMALLOC ();
474 live
->livein
= (bitmap
*)xmalloc (num_var_partitions (map
) * sizeof (bitmap
));
475 for (x
= 0; x
< num_var_partitions (map
); x
++)
476 live
->livein
[x
] = BITMAP_XMALLOC ();
478 /* liveout is deferred until it is actually requested. */
479 live
->liveout
= NULL
;
484 /* Free storage for live range info object LIVE. */
487 delete_tree_live_info (tree_live_info_p live
)
492 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
493 BITMAP_XFREE (live
->liveout
[x
]);
494 free (live
->liveout
);
498 for (x
= num_var_partitions (live
->map
) - 1; x
>= 0; x
--)
499 BITMAP_XFREE (live
->livein
[x
]);
503 BITMAP_XFREE (live
->global
);
509 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
510 for partition I. STACK is a varray used for temporary memory which is
511 passed in rather than being allocated on every call. */
514 live_worklist (tree_live_info_p live
, varray_type stack
, int i
)
518 basic_block def_bb
= NULL
;
520 var_map map
= live
->map
;
522 var
= partition_to_var (map
, i
);
523 if (SSA_NAME_DEF_STMT (var
))
524 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
526 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[i
], 0, b
,
528 VARRAY_PUSH_INT (stack
, b
);
531 while (VARRAY_ACTIVE_SIZE (stack
) > 0)
533 b
= VARRAY_TOP_INT (stack
);
536 for (e
= BASIC_BLOCK (b
)->pred
; e
; e
= e
->pred_next
)
537 if (e
->src
!= ENTRY_BLOCK_PTR
)
539 /* Its not live on entry to the block its defined in. */
540 if (e
->src
== def_bb
)
542 if (!bitmap_bit_p (live
->livein
[i
], e
->src
->index
))
544 bitmap_set_bit (live
->livein
[i
], e
->src
->index
);
545 VARRAY_PUSH_INT (stack
, e
->src
->index
);
552 /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
555 set_if_valid (var_map map
, bitmap vec
, tree var
)
557 int p
= var_to_partition (map
, var
);
558 if (p
!= NO_PARTITION
)
559 bitmap_set_bit (vec
, p
);
563 /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
564 global bit for it in the LIVE object. BB is the block being processed. */
567 add_livein_if_notdef (tree_live_info_p live
, bitmap def_vec
,
568 tree var
, basic_block bb
)
570 int p
= var_to_partition (live
->map
, var
);
571 if (p
== NO_PARTITION
|| bb
== ENTRY_BLOCK_PTR
)
573 if (!bitmap_bit_p (def_vec
, p
))
575 bitmap_set_bit (live
->livein
[p
], bb
->index
);
576 bitmap_set_bit (live
->global
, p
);
581 /* Given partition map MAP, calculate all the live on entry bitmaps for
582 each basic block. Return a live info object. */
585 calculate_live_on_entry (var_map map
)
587 tree_live_info_p live
;
595 block_stmt_iterator bsi
;
600 saw_def
= BITMAP_XMALLOC ();
602 live
= new_tree_live_info (map
);
606 bitmap_clear (saw_def
);
608 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
610 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
612 var
= PHI_ARG_DEF (phi
, i
);
613 if (!phi_ssa_name_p (var
))
615 stmt
= SSA_NAME_DEF_STMT (var
);
616 e
= PHI_ARG_EDGE (phi
, i
);
618 /* Any uses in PHIs which either don't have def's or are not
619 defined in the block from which the def comes, will be live
620 on entry to that block. */
621 if (!stmt
|| e
->src
!= bb_for_stmt (stmt
))
622 add_livein_if_notdef (live
, saw_def
, var
, e
->src
);
626 /* Don't mark PHI results as defined until all the PHI nodes have
627 been processed. If the PHI sequence is:
630 The a_3 referred to in b_3's PHI node is the one incoming on the
631 edge, *not* the PHI node just seen. */
633 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
635 var
= PHI_RESULT (phi
);
636 set_if_valid (map
, saw_def
, var
);
639 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
641 stmt
= bsi_stmt (bsi
);
642 get_stmt_operands (stmt
);
643 ann
= stmt_ann (stmt
);
645 uses
= USE_OPS (ann
);
646 num
= NUM_USES (uses
);
647 for (i
= 0; i
< num
; i
++)
649 op
= USE_OP (uses
, i
);
650 add_livein_if_notdef (live
, saw_def
, op
, bb
);
653 defs
= DEF_OPS (ann
);
654 num
= NUM_DEFS (defs
);
655 for (i
= 0; i
< num
; i
++)
657 op
= DEF_OP (defs
, i
);
658 set_if_valid (map
, saw_def
, op
);
663 VARRAY_INT_INIT (stack
, last_basic_block
, "stack");
664 EXECUTE_IF_SET_IN_BITMAP (live
->global
, 0, i
,
666 live_worklist (live
, stack
, i
);
669 #ifdef ENABLE_CHECKING
670 /* Check for live on entry partitions and report those with a DEF in
671 the program. This will typically mean an optimization has done
674 bb
= ENTRY_BLOCK_PTR
;
676 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
678 int entry_block
= e
->dest
->index
;
679 if (e
->dest
== EXIT_BLOCK_PTR
)
681 for (i
= 0; i
< num_var_partitions (map
); i
++)
685 var
= partition_to_var (map
, i
);
686 stmt
= SSA_NAME_DEF_STMT (var
);
687 tmp
= bb_for_stmt (stmt
);
688 d
= default_def (SSA_NAME_VAR (var
));
690 if (bitmap_bit_p (live_entry_blocks (live
, i
), entry_block
))
692 if (!IS_EMPTY_STMT (stmt
))
695 print_generic_expr (stderr
, var
, TDF_SLIM
);
696 fprintf (stderr
, " is defined ");
698 fprintf (stderr
, " in BB%d, ", tmp
->index
);
699 fprintf (stderr
, "by:\n");
700 print_generic_expr (stderr
, stmt
, TDF_SLIM
);
701 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
703 fprintf (stderr
, " So it appears to have multiple defs.\n");
710 print_generic_expr (stderr
, var
, TDF_SLIM
);
711 fprintf (stderr
, " is live-on-entry to BB%d ",entry_block
);
714 fprintf (stderr
, " but is not the default def of ");
715 print_generic_expr (stderr
, d
, TDF_SLIM
);
716 fprintf (stderr
, "\n");
719 fprintf (stderr
, " and there is no default def.\n");
726 /* The only way this var shouldn't be marked live on entry is
727 if it occurs in a PHI argument of the block. */
729 for (phi
= phi_nodes (e
->dest
);
731 phi
= PHI_CHAIN (phi
))
733 for (z
= 0; z
< PHI_NUM_ARGS (phi
); z
++)
734 if (var
== PHI_ARG_DEF (phi
, z
))
743 print_generic_expr (stderr
, var
, TDF_SLIM
);
744 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
746 fprintf (stderr
, "but it is a default def so it should be.\n");
754 BITMAP_XFREE (saw_def
);
760 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
763 calculate_live_on_exit (tree_live_info_p liveinfo
)
772 var_map map
= liveinfo
->map
;
774 on_exit
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
775 for (x
= 0; x
< last_basic_block
; x
++)
776 on_exit
[x
] = BITMAP_XMALLOC ();
778 /* Set all the live-on-exit bits for uses in PHIs. */
781 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
782 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
784 t
= PHI_ARG_DEF (phi
, i
);
785 e
= PHI_ARG_EDGE (phi
, i
);
786 if (!phi_ssa_name_p (t
) || e
->src
== ENTRY_BLOCK_PTR
)
788 set_if_valid (map
, on_exit
[e
->src
->index
], t
);
792 /* Set live on exit for all predecessors of live on entry's. */
793 for (i
= 0; i
< num_var_partitions (map
); i
++)
795 on_entry
= live_entry_blocks (liveinfo
, i
);
796 EXECUTE_IF_SET_IN_BITMAP (on_entry
, 0, b
,
798 for (e
= BASIC_BLOCK(b
)->pred
; e
; e
= e
->pred_next
)
799 if (e
->src
!= ENTRY_BLOCK_PTR
)
800 bitmap_set_bit (on_exit
[e
->src
->index
], i
);
804 liveinfo
->liveout
= on_exit
;
808 /* Initialize a tree_partition_associator object using MAP. */
811 tpa_init (var_map map
)
814 int num_partitions
= num_var_partitions (map
);
817 if (num_partitions
== 0)
820 tpa
= (tpa_p
) xmalloc (sizeof (struct tree_partition_associator_d
));
822 tpa
->uncompressed_num
= -1;
824 tpa
->next_partition
= (int *)xmalloc (num_partitions
* sizeof (int));
825 memset (tpa
->next_partition
, TPA_NONE
, num_partitions
* sizeof (int));
827 tpa
->partition_to_tree_map
= (int *)xmalloc (num_partitions
* sizeof (int));
828 memset (tpa
->partition_to_tree_map
, TPA_NONE
, num_partitions
* sizeof (int));
830 x
= MAX (40, (num_partitions
/ 20));
831 VARRAY_TREE_INIT (tpa
->trees
, x
, "trees");
832 VARRAY_INT_INIT (tpa
->first_partition
, x
, "first_partition");
839 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
842 tpa_remove_partition (tpa_p tpa
, int tree_index
, int partition_index
)
846 i
= tpa_first_partition (tpa
, tree_index
);
847 if (i
== partition_index
)
849 VARRAY_INT (tpa
->first_partition
, tree_index
) = tpa
->next_partition
[i
];
853 for ( ; i
!= TPA_NONE
; i
= tpa_next_partition (tpa
, i
))
855 if (tpa
->next_partition
[i
] == partition_index
)
857 tpa
->next_partition
[i
] = tpa
->next_partition
[partition_index
];
865 /* Free the memory used by tree_partition_associator object TPA. */
868 tpa_delete (tpa_p tpa
)
873 free (tpa
->partition_to_tree_map
);
874 free (tpa
->next_partition
);
879 /* This function will remove any tree entries from TPA which have only a single
880 element. This will help keep the size of the conflict graph down. The
881 function returns the number of remaining tree lists. */
884 tpa_compact (tpa_p tpa
)
886 int last
, x
, y
, first
, swap_i
;
889 /* Find the last list which has more than 1 partition. */
890 for (last
= tpa
->num_trees
- 1; last
> 0; last
--)
892 first
= tpa_first_partition (tpa
, last
);
893 if (tpa_next_partition (tpa
, first
) != NO_PARTITION
)
900 first
= tpa_first_partition (tpa
, x
);
902 /* If there is not more than one partition, swap with the current end
904 if (tpa_next_partition (tpa
, first
) == NO_PARTITION
)
906 swap_t
= VARRAY_TREE (tpa
->trees
, last
);
907 swap_i
= VARRAY_INT (tpa
->first_partition
, last
);
909 /* Update the last entry. Since it is known to only have one
910 partition, there is nothing else to update. */
911 VARRAY_TREE (tpa
->trees
, last
) = VARRAY_TREE (tpa
->trees
, x
);
912 VARRAY_INT (tpa
->first_partition
, last
)
913 = VARRAY_INT (tpa
->first_partition
, x
);
914 tpa
->partition_to_tree_map
[tpa_first_partition (tpa
, last
)] = last
;
916 /* Since this list is known to have more than one partition, update
917 the list owner entries. */
918 VARRAY_TREE (tpa
->trees
, x
) = swap_t
;
919 VARRAY_INT (tpa
->first_partition
, x
) = swap_i
;
920 for (y
= tpa_first_partition (tpa
, x
);
922 y
= tpa_next_partition (tpa
, y
))
923 tpa
->partition_to_tree_map
[y
] = x
;
925 /* Ensure last is a list with more than one partition. */
927 for (; last
> x
; last
--)
929 first
= tpa_first_partition (tpa
, last
);
930 if (tpa_next_partition (tpa
, first
) != NO_PARTITION
)
937 first
= tpa_first_partition (tpa
, x
);
938 if (tpa_next_partition (tpa
, first
) != NO_PARTITION
)
940 tpa
->uncompressed_num
= tpa
->num_trees
;
946 /* Initialize a root_var object with SSA partitions from MAP which are based
947 on each root variable. */
950 root_var_init (var_map map
)
953 int num_partitions
= num_var_partitions (map
);
963 seen
= sbitmap_alloc (num_partitions
);
966 /* Start at the end and work towards the front. This will provide a list
967 that is ordered from smallest to largest. */
968 for (x
= num_partitions
- 1; x
>= 0; x
--)
970 t
= partition_to_var (map
, x
);
972 /* The var map may not be compacted yet, so check for NULL. */
976 p
= var_to_partition (map
, t
);
978 #ifdef ENABLE_CHECKING
979 if (p
== NO_PARTITION
)
983 /* Make sure we only put coalesced partitions into the list once. */
984 if (TEST_BIT (seen
, p
))
987 if (TREE_CODE (t
) == SSA_NAME
)
988 t
= SSA_NAME_VAR (t
);
990 if (ann
->root_var_processed
)
992 rv
->next_partition
[p
] = VARRAY_INT (rv
->first_partition
,
993 VAR_ANN_ROOT_INDEX (ann
));
994 VARRAY_INT (rv
->first_partition
, VAR_ANN_ROOT_INDEX (ann
)) = p
;
998 ann
->root_var_processed
= 1;
999 VAR_ANN_ROOT_INDEX (ann
) = rv
->num_trees
++;
1000 VARRAY_PUSH_TREE (rv
->trees
, t
);
1001 VARRAY_PUSH_INT (rv
->first_partition
, p
);
1003 rv
->partition_to_tree_map
[p
] = VAR_ANN_ROOT_INDEX (ann
);
1006 /* Reset the out_of_ssa_tag flag on each variable for later use. */
1007 for (x
= 0; x
< rv
->num_trees
; x
++)
1009 t
= VARRAY_TREE (rv
->trees
, x
);
1010 var_ann (t
)->root_var_processed
= 0;
1013 sbitmap_free (seen
);
1018 /* Initialize a type_var structure which associates all the partitions in MAP
1019 of the same type to the type node's index. Volatiles are ignored. */
1022 type_var_init (var_map map
)
1026 int num_partitions
= num_var_partitions (map
);
1030 seen
= sbitmap_alloc (num_partitions
);
1031 sbitmap_zero (seen
);
1033 tv
= tpa_init (map
);
1037 for (x
= num_partitions
- 1; x
>= 0; x
--)
1039 t
= partition_to_var (map
, x
);
1041 /* Disallow coalescing of these types of variables. */
1043 || TREE_THIS_VOLATILE (t
)
1044 || TREE_CODE (t
) == RESULT_DECL
1045 || TREE_CODE (t
) == PARM_DECL
1047 && (DECL_REGISTER (t
)
1048 || !DECL_ARTIFICIAL (t
)
1049 || DECL_RTL_SET_P (t
))))
1052 p
= var_to_partition (map
, t
);
1054 #ifdef ENABLE_CHECKING
1055 if (p
== NO_PARTITION
)
1059 /* If partitions have been coalesced, only add the representative
1060 for the partition to the list once. */
1061 if (TEST_BIT (seen
, p
))
1066 /* Find the list for this type. */
1067 for (y
= 0; y
< tv
->num_trees
; y
++)
1068 if (t
== VARRAY_TREE (tv
->trees
, y
))
1070 if (y
== tv
->num_trees
)
1073 VARRAY_PUSH_TREE (tv
->trees
, t
);
1074 VARRAY_PUSH_INT (tv
->first_partition
, p
);
1078 tv
->next_partition
[p
] = VARRAY_INT (tv
->first_partition
, y
);
1079 VARRAY_INT (tv
->first_partition
, y
) = p
;
1081 tv
->partition_to_tree_map
[p
] = y
;
1083 sbitmap_free (seen
);
1088 /* Create a new coalesce list object from MAP and return it. */
1091 create_coalesce_list (var_map map
)
1093 coalesce_list_p list
;
1095 list
= (coalesce_list_p
) xmalloc (sizeof (struct coalesce_list_d
));
1098 list
->add_mode
= true;
1099 list
->list
= (partition_pair_p
*) xcalloc (num_var_partitions (map
),
1100 sizeof (struct partition_pair_d
));
1105 /* Delete coalesce list CL. */
1108 delete_coalesce_list (coalesce_list_p cl
)
1115 /* Find a matching coalesce pair object in CL for partitions P1 and P2. If
1116 one isn't found, return NULL if CREATE is false, otherwise create a new
1117 coalesce pair object and return it. */
1119 static partition_pair_p
1120 find_partition_pair (coalesce_list_p cl
, int p1
, int p2
, bool create
)
1122 partition_pair_p node
, tmp
;
1125 /* Normalize so that p1 is the smaller value. */
1135 /* The list is sorted such that if we find a value greater than p2,
1136 p2 is not in the list. */
1137 for (node
= cl
->list
[p1
]; node
; node
= node
->next
)
1139 if (node
->second_partition
== p2
)
1142 if (node
->second_partition
> p2
)
1150 node
= (partition_pair_p
) xmalloc (sizeof (struct partition_pair_d
));
1151 node
->first_partition
= p1
;
1152 node
->second_partition
= p2
;
1157 node
->next
= tmp
->next
;
1162 /* This is now the first node in the list. */
1163 node
->next
= cl
->list
[p1
];
1164 cl
->list
[p1
] = node
;
1171 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
1174 add_coalesce (coalesce_list_p cl
, int p1
, int p2
, int value
)
1176 partition_pair_p node
;
1178 #ifdef ENABLE_CHECKING
1186 node
= find_partition_pair (cl
, p1
, p2
, true);
1188 node
->cost
+= value
;
1192 /* Comparison function to allow qsort to sort P1 and P2 in descending order. */
1195 int compare_pairs (const void *p1
, const void *p2
)
1197 return (*(partition_pair_p
*)p2
)->cost
- (*(partition_pair_p
*)p1
)->cost
;
1201 /* Prepare CL for removal of preferred pairs. When finished, list element
1202 0 has all the coalesce pairs, sorted in order from most important coalesce
1203 to least important. */
1206 sort_coalesce_list (coalesce_list_p cl
)
1209 partition_pair_p chain
, p
;
1210 partition_pair_p
*list
;
1215 cl
->add_mode
= false;
1217 /* Compact the array of lists to a single list, and count the elements. */
1220 for (x
= 0; x
< num_var_partitions (cl
->map
); x
++)
1221 if (cl
->list
[x
] != NULL
)
1223 for (p
= cl
->list
[x
]; p
->next
!= NULL
; p
= p
->next
)
1227 chain
= cl
->list
[x
];
1231 /* Only call qsort if there are more than 2 items. */
1234 list
= xmalloc (sizeof (partition_pair_p
) * num
);
1236 for (p
= chain
; p
!= NULL
; p
= p
->next
)
1239 #ifdef ENABLE_CHECKING
1244 qsort (list
, count
, sizeof (partition_pair_p
), compare_pairs
);
1247 for (x
= 1; x
< num
; x
++)
1253 cl
->list
[0] = list
[0];
1258 cl
->list
[0] = chain
;
1261 /* Simply swap the two elements if they are in the wrong order. */
1262 if (chain
->cost
< chain
->next
->cost
)
1264 cl
->list
[0] = chain
->next
;
1265 cl
->list
[0]->next
= chain
;
1273 /* Retrieve the best remaining pair to coalesce from CL. Returns the 2
1274 partitions via P1 and P2. Their calculated cost is returned by the function.
1275 NO_BEST_COALESCE is returned if the coalesce list is empty. */
1278 pop_best_coalesce (coalesce_list_p cl
, int *p1
, int *p2
)
1280 partition_pair_p node
;
1288 return NO_BEST_COALESCE
;
1290 cl
->list
[0] = node
->next
;
1292 *p1
= node
->first_partition
;
1293 *p2
= node
->second_partition
;
1301 /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
1302 VAR and any other live partitions in VEC which are associated via TPA.
1303 Reset the live bit in VEC. */
1306 add_conflicts_if_valid (tpa_p tpa
, conflict_graph graph
,
1307 var_map map
, bitmap vec
, tree var
)
1310 p
= var_to_partition (map
, var
);
1311 if (p
!= NO_PARTITION
)
1313 bitmap_clear_bit (vec
, p
);
1314 first
= tpa_find_tree (tpa
, p
);
1315 /* If find returns nothing, this object isn't interesting. */
1316 if (first
== TPA_NONE
)
1318 /* Only add interferences between objects in the same list. */
1319 for (y
= tpa_first_partition (tpa
, first
);
1321 y
= tpa_next_partition (tpa
, y
))
1323 if (bitmap_bit_p (vec
, y
))
1324 conflict_graph_add (graph
, p
, y
);
1330 /* Return a conflict graph for the information contained in LIVE_INFO. Only
1331 conflicts between items in the same TPA list are added. If optional
1332 coalesce list CL is passed in, any copies encountered are added. */
1335 build_tree_conflict_graph (tree_live_info_p liveinfo
, tpa_p tpa
,
1338 conflict_graph graph
;
1343 varray_type partition_link
, tpa_to_clear
, tpa_nodes
;
1348 map
= live_var_map (liveinfo
);
1349 graph
= conflict_graph_new (num_var_partitions (map
));
1351 if (tpa_num_trees (tpa
) == 0)
1354 live
= BITMAP_XMALLOC ();
1356 VARRAY_INT_INIT (partition_link
, num_var_partitions (map
) + 1, "part_link");
1357 VARRAY_INT_INIT (tpa_nodes
, tpa_num_trees (tpa
), "tpa nodes");
1358 VARRAY_INT_INIT (tpa_to_clear
, 50, "tpa to clear");
1362 block_stmt_iterator bsi
;
1365 /* Start with live on exit temporaries. */
1366 bitmap_copy (live
, live_on_exit (liveinfo
, bb
));
1368 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
); bsi_prev (&bsi
))
1370 bool is_a_copy
= false;
1371 tree stmt
= bsi_stmt (bsi
);
1374 get_stmt_operands (stmt
);
1375 ann
= stmt_ann (stmt
);
1377 /* A copy between 2 partitions does not introduce an interference
1378 by itself. If they did, you would never be able to coalesce
1379 two things which are copied. If the two variables really do
1380 conflict, they will conflict elsewhere in the program.
1382 This is handled specially here since we may also be interested
1383 in copies between real variables and SSA_NAME variables. We may
1384 be interested in trying to coalesce SSA_NAME variables with
1385 root variables in some cases. */
1387 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1389 tree lhs
= TREE_OPERAND (stmt
, 0);
1390 tree rhs
= TREE_OPERAND (stmt
, 1);
1394 if (DECL_P (lhs
) || TREE_CODE (lhs
) == SSA_NAME
)
1395 p1
= var_to_partition (map
, lhs
);
1399 if (DECL_P (rhs
) || TREE_CODE (rhs
) == SSA_NAME
)
1400 p2
= var_to_partition (map
, rhs
);
1404 if (p1
!= NO_PARTITION
&& p2
!= NO_PARTITION
)
1407 bit
= bitmap_bit_p (live
, p2
);
1408 /* If the RHS is live, make it not live while we add
1409 the conflicts, then make it live again. */
1411 bitmap_clear_bit (live
, p2
);
1412 add_conflicts_if_valid (tpa
, graph
, map
, live
, lhs
);
1414 bitmap_set_bit (live
, p2
);
1416 add_coalesce (cl
, p1
, p2
, 1);
1417 set_if_valid (map
, live
, rhs
);
1425 defs
= DEF_OPS (ann
);
1426 num
= NUM_DEFS (defs
);
1427 for (x
= 0; x
< num
; x
++)
1429 var
= DEF_OP (defs
, x
);
1430 add_conflicts_if_valid (tpa
, graph
, map
, live
, var
);
1433 uses
= USE_OPS (ann
);
1434 num
= NUM_USES (uses
);
1435 for (x
= 0; x
< num
; x
++)
1437 var
= USE_OP (uses
, x
);
1438 set_if_valid (map
, live
, var
);
1443 /* If result of a PHI is unused, then the loops over the statements
1444 will not record any conflicts. However, since the PHI node is
1445 going to be translated out of SSA form we must record a conflict
1446 between the result of the PHI and any variables with are live.
1447 Otherwise the out-of-ssa translation may create incorrect code. */
1448 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1450 tree result
= PHI_RESULT (phi
);
1451 int p
= var_to_partition (map
, result
);
1453 if (p
!= NO_PARTITION
&& ! bitmap_bit_p (live
, p
))
1454 add_conflicts_if_valid (tpa
, graph
, map
, live
, result
);
1457 /* Anything which is still live at this point interferes.
1458 In order to implement this efficiently, only conflicts between
1459 partitions which have the same TPA root need be added.
1460 TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
1461 entry points to an index into 'partition_link', which then indexes
1462 into itself forming a linked list of partitions sharing a tpa root
1463 which have been seen as live up to this point. Since partitions start
1464 at index zero, all entries in partition_link are (partition + 1).
1466 Conflicts are added between the current partition and any already seen.
1467 tpa_clear contains all the tpa_roots processed, and these are the only
1468 entries which need to be zero'd out for a clean restart. */
1470 EXECUTE_IF_SET_IN_BITMAP (live
, 0, x
,
1472 i
= tpa_find_tree (tpa
, x
);
1475 int start
= VARRAY_INT (tpa_nodes
, i
);
1476 /* If start is 0, a new root reference list is being started.
1477 Register it to be cleared. */
1479 VARRAY_PUSH_INT (tpa_to_clear
, i
);
1481 /* Add interferences to other tpa members seen. */
1482 for (y
= start
; y
!= 0; y
= VARRAY_INT (partition_link
, y
))
1483 conflict_graph_add (graph
, x
, y
- 1);
1484 VARRAY_INT (tpa_nodes
, i
) = x
+ 1;
1485 VARRAY_INT (partition_link
, x
+ 1) = start
;
1489 /* Now clear the used tpa root references. */
1490 for (l
= 0; l
< VARRAY_ACTIVE_SIZE (tpa_to_clear
); l
++)
1491 VARRAY_INT (tpa_nodes
, VARRAY_INT (tpa_to_clear
, l
)) = 0;
1492 VARRAY_POP_ALL (tpa_to_clear
);
1495 BITMAP_XFREE (live
);
1500 /* This routine will attempt to coalesce the elements in TPA subject to the
1501 conflicts found in GRAPH. If optional coalesce_list CL is provided,
1502 only coalesces specified within the coalesce list are attempted. Otherwise
1503 an attempt is made to coalesce as many partitions within each TPA grouping
1504 as possible. If DEBUG is provided, debug output will be sent there. */
1507 coalesce_tpa_members (tpa_p tpa
, conflict_graph graph
, var_map map
,
1508 coalesce_list_p cl
, FILE *debug
)
1513 /* Attempt to coalesce any items in a coalesce list. */
1516 while (pop_best_coalesce (cl
, &x
, &y
) != NO_BEST_COALESCE
)
1520 fprintf (debug
, "Coalesce list: (%d)", x
);
1521 print_generic_expr (debug
, partition_to_var (map
, x
), TDF_SLIM
);
1522 fprintf (debug
, " & (%d)", y
);
1523 print_generic_expr (debug
, partition_to_var (map
, y
), TDF_SLIM
);
1526 w
= tpa_find_tree (tpa
, x
);
1527 z
= tpa_find_tree (tpa
, y
);
1528 if (w
!= z
|| w
== TPA_NONE
|| z
== TPA_NONE
)
1533 fprintf (debug
, ": Fail, Non-matching TPA's\n");
1535 fprintf (debug
, ": Fail %d non TPA.\n", x
);
1537 fprintf (debug
, ": Fail %d non TPA.\n", y
);
1541 var
= partition_to_var (map
, x
);
1542 tmp
= partition_to_var (map
, y
);
1543 x
= var_to_partition (map
, var
);
1544 y
= var_to_partition (map
, tmp
);
1546 fprintf (debug
, " [map: %d, %d] ", x
, y
);
1550 fprintf (debug
, ": Already Coalesced.\n");
1553 if (!conflict_graph_conflict_p (graph
, x
, y
))
1555 z
= var_union (map
, var
, tmp
);
1556 if (z
== NO_PARTITION
)
1559 fprintf (debug
, ": Unable to perform partition union.\n");
1563 /* z is the new combined partition. We need to remove the other
1564 partition from the list. Set x to be that other partition. */
1567 conflict_graph_merge_regs (graph
, x
, y
);
1568 w
= tpa_find_tree (tpa
, y
);
1569 tpa_remove_partition (tpa
, w
, y
);
1573 conflict_graph_merge_regs (graph
, y
, x
);
1574 w
= tpa_find_tree (tpa
, x
);
1575 tpa_remove_partition (tpa
, w
, x
);
1579 fprintf (debug
, ": Success -> %d\n", z
);
1583 fprintf (debug
, ": Fail due to conflict\n");
1585 /* If using a coalesce list, don't try to coalesce anything else. */
1589 for (x
= 0; x
< tpa_num_trees (tpa
); x
++)
1591 while (tpa_first_partition (tpa
, x
) != TPA_NONE
)
1594 /* Coalesce first partition with anything that doesn't conflict. */
1595 y
= tpa_first_partition (tpa
, x
);
1596 tpa_remove_partition (tpa
, x
, y
);
1598 var
= partition_to_var (map
, y
);
1599 /* p1 is the partition representative to which y belongs. */
1600 p1
= var_to_partition (map
, var
);
1602 for (z
= tpa_next_partition (tpa
, y
);
1604 z
= tpa_next_partition (tpa
, z
))
1606 tmp
= partition_to_var (map
, z
);
1607 /* p2 is the partition representative to which z belongs. */
1608 p2
= var_to_partition (map
, tmp
);
1611 fprintf (debug
, "Coalesce : ");
1612 print_generic_expr (debug
, var
, TDF_SLIM
);
1613 fprintf (debug
, " &");
1614 print_generic_expr (debug
, tmp
, TDF_SLIM
);
1615 fprintf (debug
, " (%d ,%d)", p1
, p2
);
1618 /* If partitions are already merged, don't check for conflict. */
1621 tpa_remove_partition (tpa
, x
, z
);
1623 fprintf (debug
, ": Already coalesced\n");
1626 if (!conflict_graph_conflict_p (graph
, p1
, p2
))
1629 if (tpa_find_tree (tpa
, y
) == TPA_NONE
1630 || tpa_find_tree (tpa
, z
) == TPA_NONE
)
1633 fprintf (debug
, ": Fail non-TPA member\n");
1636 if ((v
= var_union (map
, var
, tmp
)) == NO_PARTITION
)
1639 fprintf (debug
, ": Fail cannot combine partitions\n");
1643 tpa_remove_partition (tpa
, x
, z
);
1645 conflict_graph_merge_regs (graph
, v
, z
);
1648 /* Update the first partition's representative. */
1649 conflict_graph_merge_regs (graph
, v
, y
);
1653 /* The root variable of the partition may be changed
1655 var
= partition_to_var (map
, p1
);
1658 fprintf (debug
, ": Success -> %d\n", v
);
1662 fprintf (debug
, ": Fail, Conflict\n");
1669 /* Send debug info for coalesce list CL to file F. */
1672 dump_coalesce_list (FILE *f
, coalesce_list_p cl
)
1674 partition_pair_p node
;
1680 fprintf (f
, "Coalesce List:\n");
1681 num
= num_var_partitions (cl
->map
);
1682 for (x
= 0; x
< num
; x
++)
1688 print_generic_expr (f
, partition_to_var (cl
->map
, x
), TDF_SLIM
);
1689 fprintf (f
, "] - ");
1690 for ( ; node
; node
= node
->next
)
1692 var
= partition_to_var (cl
->map
, node
->second_partition
);
1693 print_generic_expr (f
, var
, TDF_SLIM
);
1694 fprintf (f
, "(%1d), ", node
->cost
);
1702 fprintf (f
, "Sorted Coalesce list:\n");
1703 for (node
= cl
->list
[0]; node
; node
= node
->next
)
1705 fprintf (f
, "(%d) ", node
->cost
);
1706 var
= partition_to_var (cl
->map
, node
->first_partition
);
1707 print_generic_expr (f
, var
, TDF_SLIM
);
1709 var
= partition_to_var (cl
->map
, node
->second_partition
);
1710 print_generic_expr (f
, var
, TDF_SLIM
);
1717 /* Output tree_partition_associator object TPA to file F.. */
1720 tpa_dump (FILE *f
, tpa_p tpa
)
1727 for (x
= 0; x
< tpa_num_trees (tpa
); x
++)
1729 print_generic_expr (f
, tpa_tree (tpa
, x
), TDF_SLIM
);
1730 fprintf (f
, " : (");
1731 for (i
= tpa_first_partition (tpa
, x
);
1733 i
= tpa_next_partition (tpa
, i
))
1735 fprintf (f
, "(%d)",i
);
1736 print_generic_expr (f
, partition_to_var (tpa
->map
, i
), TDF_SLIM
);
1739 #ifdef ENABLE_CHECKING
1740 if (tpa_find_tree (tpa
, i
) != x
)
1741 fprintf (f
, "**find tree incorrectly set** ");
1751 /* Output partition map MAP to file F. */
1754 dump_var_map (FILE *f
, var_map map
)
1760 fprintf (f
, "\nPartition map \n\n");
1762 for (x
= 0; x
< map
->num_partitions
; x
++)
1764 if (map
->compact_to_partition
!= NULL
)
1765 p
= map
->compact_to_partition
[x
];
1769 if (map
->partition_to_var
[p
] == NULL_TREE
)
1773 for (y
= 1; y
< num_ssa_names
; y
++)
1775 p
= partition_find (map
->var_partition
, y
);
1776 if (map
->partition_to_compact
)
1777 p
= map
->partition_to_compact
[p
];
1782 fprintf(f
, "Partition %d (", x
);
1783 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1786 fprintf (f
, "%d ", y
);
1796 /* Output live range info LIVE to file F, controlled by FLAG. */
1799 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1803 var_map map
= live
->map
;
1805 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1809 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1810 for (i
= 0; i
< num_var_partitions (map
); i
++)
1812 if (bitmap_bit_p (live_entry_blocks (live
, i
), bb
->index
))
1814 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1822 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1826 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1827 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
,
1829 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1837 /* Register partitions in MAP so that we can take VARS out of SSA form.
1838 This requires a walk over all the PHI nodes and all the statements. */
1841 register_ssa_partitions_for_vars (bitmap vars
, var_map map
)
1845 if (bitmap_first_set_bit (vars
) >= 0)
1848 /* Find every instance (SSA_NAME) of variables in VARs and
1849 register a new partition for them. This requires examining
1850 every statement and every PHI node once. */
1853 block_stmt_iterator bsi
;
1857 /* Register partitions for SSA_NAMEs appearing in the PHI
1858 nodes in this basic block.
1860 Note we delete PHI nodes in this loop if they are
1861 associated with virtual vars which are going to be
1863 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
1865 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
1867 next
= PHI_CHAIN (phi
);
1868 if (bitmap_bit_p (vars
, var_ann (result
)->uid
))
1870 if (! is_gimple_reg (result
))
1871 remove_phi_node (phi
, NULL_TREE
, bb
);
1876 /* Register a partition for the result. */
1877 register_ssa_partition (map
, PHI_RESULT (phi
), 0);
1879 /* Register a partition for each argument as needed. */
1880 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1882 tree arg
= PHI_ARG_DEF (phi
, i
);
1884 if (TREE_CODE (arg
) != SSA_NAME
)
1886 if (!bitmap_bit_p (vars
,
1887 var_ann (SSA_NAME_VAR (arg
))->uid
))
1890 register_ssa_partition (map
, arg
, 1);
1896 /* Now register partitions for SSA_NAMEs appearing in each
1897 statement in this block. */
1898 for (bsi
= bsi_start (bb
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
1900 stmt_ann_t ann
= stmt_ann (bsi_stmt (bsi
));
1901 use_optype uses
= USE_OPS (ann
);
1902 def_optype defs
= DEF_OPS (ann
);
1905 for (i
= 0; i
< NUM_USES (uses
); i
++)
1907 tree op
= USE_OP (uses
, i
);
1909 if (TREE_CODE (op
) == SSA_NAME
1910 && bitmap_bit_p (vars
, var_ann (SSA_NAME_VAR (op
))->uid
))
1911 register_ssa_partition (map
, op
, 1);
1914 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
1916 tree op
= DEF_OP (defs
, i
);
1918 if (TREE_CODE (op
) == SSA_NAME
1919 && bitmap_bit_p (vars
,
1920 var_ann (SSA_NAME_VAR (op
))->uid
))
1921 register_ssa_partition (map
, op
, 0);