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 /* This function looks through the program and uses FLAGS to determine what
289 SSA versioned variables are given entries in a new partition table. This
290 new partition map is returned. */
293 create_ssa_var_map (int flags
)
295 block_stmt_iterator bsi
;
301 v_may_def_optype v_may_defs
;
302 v_must_def_optype v_must_defs
;
307 #if defined ENABLE_CHECKING
308 sbitmap used_in_real_ops
;
309 sbitmap used_in_virtual_ops
;
312 map
= init_var_map (num_ssa_names
+ 1);
314 #if defined ENABLE_CHECKING
315 used_in_real_ops
= sbitmap_alloc (num_referenced_vars
);
316 sbitmap_zero (used_in_real_ops
);
318 used_in_virtual_ops
= sbitmap_alloc (num_referenced_vars
);
319 sbitmap_zero (used_in_virtual_ops
);
322 if (flags
& SSA_VAR_MAP_REF_COUNT
)
325 = (int *)xmalloc (((num_ssa_names
+ 1) * sizeof (int)));
326 memset (map
->ref_count
, 0, (num_ssa_names
+ 1) * sizeof (int));
332 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
335 register_ssa_partition (map
, PHI_RESULT (phi
), false);
336 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
338 arg
= PHI_ARG_DEF (phi
, i
);
339 if (TREE_CODE (arg
) == SSA_NAME
)
340 register_ssa_partition (map
, arg
, true);
344 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
346 stmt
= bsi_stmt (bsi
);
347 get_stmt_operands (stmt
);
348 ann
= stmt_ann (stmt
);
350 /* Register USE and DEF operands in each statement. */
351 uses
= USE_OPS (ann
);
352 for (x
= 0; x
< NUM_USES (uses
); x
++)
354 use
= USE_OP (uses
, x
);
355 register_ssa_partition (map
, use
, true);
357 #if defined ENABLE_CHECKING
358 SET_BIT (used_in_real_ops
, var_ann (SSA_NAME_VAR (use
))->uid
);
362 defs
= DEF_OPS (ann
);
363 for (x
= 0; x
< NUM_DEFS (defs
); x
++)
365 dest
= DEF_OP (defs
, x
);
366 register_ssa_partition (map
, dest
, false);
368 #if defined ENABLE_CHECKING
369 SET_BIT (used_in_real_ops
, var_ann (SSA_NAME_VAR (dest
))->uid
);
373 /* While we do not care about virtual operands for
374 out of SSA, we do need to look at them to make sure
375 we mark all the variables which are used. */
376 vuses
= VUSE_OPS (ann
);
377 for (x
= 0; x
< NUM_VUSES (vuses
); x
++)
379 tree var
= VUSE_OP (vuses
, x
);
382 #if defined ENABLE_CHECKING
383 SET_BIT (used_in_virtual_ops
, var_ann (SSA_NAME_VAR (var
))->uid
);
387 v_may_defs
= V_MAY_DEF_OPS (ann
);
388 for (x
= 0; x
< NUM_V_MAY_DEFS (v_may_defs
); x
++)
390 tree var
= V_MAY_DEF_OP (v_may_defs
, x
);
393 #if defined ENABLE_CHECKING
394 SET_BIT (used_in_virtual_ops
, var_ann (SSA_NAME_VAR (var
))->uid
);
398 v_must_defs
= V_MUST_DEF_OPS (ann
);
399 for (x
= 0; x
< NUM_V_MUST_DEFS (v_must_defs
); x
++)
401 tree var
= V_MUST_DEF_OP (v_must_defs
, x
);
403 #if defined ENABLE_CHECKING
404 SET_BIT (used_in_virtual_ops
, var_ann (SSA_NAME_VAR (var
))->uid
);
410 #if defined ENABLE_CHECKING
413 sbitmap both
= sbitmap_alloc (num_referenced_vars
);
414 sbitmap_a_and_b (both
, used_in_real_ops
, used_in_virtual_ops
);
415 if (sbitmap_first_set_bit (both
) >= 0)
417 EXECUTE_IF_SET_IN_SBITMAP (both
, 0, i
,
418 fprintf (stderr
, "Variable %s used in real and virtual operands\n",
419 get_name (referenced_var (i
))));
423 sbitmap_free (used_in_real_ops
);
424 sbitmap_free (used_in_virtual_ops
);
433 /* Allocate and return a new live range information object base on MAP. */
435 static tree_live_info_p
436 new_tree_live_info (var_map map
)
438 tree_live_info_p live
;
441 live
= (tree_live_info_p
) xmalloc (sizeof (struct tree_live_info_d
));
443 live
->num_blocks
= last_basic_block
;
445 live
->global
= BITMAP_XMALLOC ();
447 live
->livein
= (bitmap
*)xmalloc (num_var_partitions (map
) * sizeof (bitmap
));
448 for (x
= 0; x
< num_var_partitions (map
); x
++)
449 live
->livein
[x
] = BITMAP_XMALLOC ();
451 /* liveout is deferred until it is actually requested. */
452 live
->liveout
= NULL
;
457 /* Free storage for live range info object LIVE. */
460 delete_tree_live_info (tree_live_info_p live
)
465 for (x
= live
->num_blocks
- 1; x
>= 0; x
--)
466 BITMAP_XFREE (live
->liveout
[x
]);
467 free (live
->liveout
);
471 for (x
= num_var_partitions (live
->map
) - 1; x
>= 0; x
--)
472 BITMAP_XFREE (live
->livein
[x
]);
476 BITMAP_XFREE (live
->global
);
482 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
483 for partition I. STACK is a varray used for temporary memory which is
484 passed in rather than being allocated on every call. */
487 live_worklist (tree_live_info_p live
, varray_type stack
, int i
)
491 basic_block def_bb
= NULL
;
493 var_map map
= live
->map
;
495 var
= partition_to_var (map
, i
);
496 if (SSA_NAME_DEF_STMT (var
))
497 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
499 EXECUTE_IF_SET_IN_BITMAP (live
->livein
[i
], 0, b
,
501 VARRAY_PUSH_INT (stack
, b
);
504 while (VARRAY_ACTIVE_SIZE (stack
) > 0)
506 b
= VARRAY_TOP_INT (stack
);
509 for (e
= BASIC_BLOCK (b
)->pred
; e
; e
= e
->pred_next
)
510 if (e
->src
!= ENTRY_BLOCK_PTR
)
512 /* Its not live on entry to the block its defined in. */
513 if (e
->src
== def_bb
)
515 if (!bitmap_bit_p (live
->livein
[i
], e
->src
->index
))
517 bitmap_set_bit (live
->livein
[i
], e
->src
->index
);
518 VARRAY_PUSH_INT (stack
, e
->src
->index
);
525 /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
528 set_if_valid (var_map map
, bitmap vec
, tree var
)
530 int p
= var_to_partition (map
, var
);
531 if (p
!= NO_PARTITION
)
532 bitmap_set_bit (vec
, p
);
536 /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
537 global bit for it in the LIVE object. BB is the block being processed. */
540 add_livein_if_notdef (tree_live_info_p live
, bitmap def_vec
,
541 tree var
, basic_block bb
)
543 int p
= var_to_partition (live
->map
, var
);
544 if (p
== NO_PARTITION
|| bb
== ENTRY_BLOCK_PTR
)
546 if (!bitmap_bit_p (def_vec
, p
))
548 bitmap_set_bit (live
->livein
[p
], bb
->index
);
549 bitmap_set_bit (live
->global
, p
);
554 /* Given partition map MAP, calculate all the live on entry bitmaps for
555 each basic block. Return a live info object. */
558 calculate_live_on_entry (var_map map
)
560 tree_live_info_p live
;
568 block_stmt_iterator bsi
;
573 saw_def
= BITMAP_XMALLOC ();
575 live
= new_tree_live_info (map
);
579 bitmap_clear (saw_def
);
581 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
583 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
585 var
= PHI_ARG_DEF (phi
, i
);
586 if (!phi_ssa_name_p (var
))
588 stmt
= SSA_NAME_DEF_STMT (var
);
589 e
= PHI_ARG_EDGE (phi
, i
);
591 /* Any uses in PHIs which either don't have def's or are not
592 defined in the block from which the def comes, will be live
593 on entry to that block. */
594 if (!stmt
|| e
->src
!= bb_for_stmt (stmt
))
595 add_livein_if_notdef (live
, saw_def
, var
, e
->src
);
599 /* Don't mark PHI results as defined until all the PHI nodes have
600 been processed. If the PHI sequence is:
603 The a_3 referred to in b_3's PHI node is the one incoming on the
604 edge, *not* the PHI node just seen. */
606 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
608 var
= PHI_RESULT (phi
);
609 set_if_valid (map
, saw_def
, var
);
612 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
614 stmt
= bsi_stmt (bsi
);
615 get_stmt_operands (stmt
);
616 ann
= stmt_ann (stmt
);
618 uses
= USE_OPS (ann
);
619 num
= NUM_USES (uses
);
620 for (i
= 0; i
< num
; i
++)
622 op
= USE_OP (uses
, i
);
623 add_livein_if_notdef (live
, saw_def
, op
, bb
);
626 defs
= DEF_OPS (ann
);
627 num
= NUM_DEFS (defs
);
628 for (i
= 0; i
< num
; i
++)
630 op
= DEF_OP (defs
, i
);
631 set_if_valid (map
, saw_def
, op
);
636 VARRAY_INT_INIT (stack
, last_basic_block
, "stack");
637 EXECUTE_IF_SET_IN_BITMAP (live
->global
, 0, i
,
639 live_worklist (live
, stack
, i
);
642 #ifdef ENABLE_CHECKING
643 /* Check for live on entry partitions and report those with a DEF in
644 the program. This will typically mean an optimization has done
647 bb
= ENTRY_BLOCK_PTR
;
649 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
651 int entry_block
= e
->dest
->index
;
652 if (e
->dest
== EXIT_BLOCK_PTR
)
654 for (i
= 0; i
< num_var_partitions (map
); i
++)
658 var
= partition_to_var (map
, i
);
659 stmt
= SSA_NAME_DEF_STMT (var
);
660 tmp
= bb_for_stmt (stmt
);
661 d
= default_def (SSA_NAME_VAR (var
));
663 if (bitmap_bit_p (live_entry_blocks (live
, i
), entry_block
))
665 if (!IS_EMPTY_STMT (stmt
))
668 print_generic_expr (stderr
, var
, TDF_SLIM
);
669 fprintf (stderr
, " is defined ");
671 fprintf (stderr
, " in BB%d, ", tmp
->index
);
672 fprintf (stderr
, "by:\n");
673 print_generic_expr (stderr
, stmt
, TDF_SLIM
);
674 fprintf (stderr
, "\nIt is also live-on-entry to entry BB %d",
676 fprintf (stderr
, " So it appears to have multiple defs.\n");
683 print_generic_expr (stderr
, var
, TDF_SLIM
);
684 fprintf (stderr
, " is live-on-entry to BB%d ",entry_block
);
687 fprintf (stderr
, " but is not the default def of ");
688 print_generic_expr (stderr
, d
, TDF_SLIM
);
689 fprintf (stderr
, "\n");
692 fprintf (stderr
, " and there is no default def.\n");
699 /* The only way this var shouldn't be marked live on entry is
700 if it occurs in a PHI argument of the block. */
702 for (phi
= phi_nodes (e
->dest
);
704 phi
= PHI_CHAIN (phi
))
706 for (z
= 0; z
< PHI_NUM_ARGS (phi
); z
++)
707 if (var
== PHI_ARG_DEF (phi
, z
))
716 print_generic_expr (stderr
, var
, TDF_SLIM
);
717 fprintf (stderr
, " is not marked live-on-entry to entry BB%d ",
719 fprintf (stderr
, "but it is a default def so it should be.\n");
727 BITMAP_XFREE (saw_def
);
733 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
736 calculate_live_on_exit (tree_live_info_p liveinfo
)
745 var_map map
= liveinfo
->map
;
747 on_exit
= (bitmap
*)xmalloc (last_basic_block
* sizeof (bitmap
));
748 for (x
= 0; x
< last_basic_block
; x
++)
749 on_exit
[x
] = BITMAP_XMALLOC ();
751 /* Set all the live-on-exit bits for uses in PHIs. */
754 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
755 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
757 t
= PHI_ARG_DEF (phi
, i
);
758 e
= PHI_ARG_EDGE (phi
, i
);
759 if (!phi_ssa_name_p (t
) || e
->src
== ENTRY_BLOCK_PTR
)
761 set_if_valid (map
, on_exit
[e
->src
->index
], t
);
765 /* Set live on exit for all predecessors of live on entry's. */
766 for (i
= 0; i
< num_var_partitions (map
); i
++)
768 on_entry
= live_entry_blocks (liveinfo
, i
);
769 EXECUTE_IF_SET_IN_BITMAP (on_entry
, 0, b
,
771 for (e
= BASIC_BLOCK(b
)->pred
; e
; e
= e
->pred_next
)
772 if (e
->src
!= ENTRY_BLOCK_PTR
)
773 bitmap_set_bit (on_exit
[e
->src
->index
], i
);
777 liveinfo
->liveout
= on_exit
;
781 /* Initialize a tree_partition_associator object using MAP. */
784 tpa_init (var_map map
)
787 int num_partitions
= num_var_partitions (map
);
790 if (num_partitions
== 0)
793 tpa
= (tpa_p
) xmalloc (sizeof (struct tree_partition_associator_d
));
795 tpa
->uncompressed_num
= -1;
797 tpa
->next_partition
= (int *)xmalloc (num_partitions
* sizeof (int));
798 memset (tpa
->next_partition
, TPA_NONE
, num_partitions
* sizeof (int));
800 tpa
->partition_to_tree_map
= (int *)xmalloc (num_partitions
* sizeof (int));
801 memset (tpa
->partition_to_tree_map
, TPA_NONE
, num_partitions
* sizeof (int));
803 x
= MAX (40, (num_partitions
/ 20));
804 VARRAY_TREE_INIT (tpa
->trees
, x
, "trees");
805 VARRAY_INT_INIT (tpa
->first_partition
, x
, "first_partition");
812 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
815 tpa_remove_partition (tpa_p tpa
, int tree_index
, int partition_index
)
819 i
= tpa_first_partition (tpa
, tree_index
);
820 if (i
== partition_index
)
822 VARRAY_INT (tpa
->first_partition
, tree_index
) = tpa
->next_partition
[i
];
826 for ( ; i
!= TPA_NONE
; i
= tpa_next_partition (tpa
, i
))
828 if (tpa
->next_partition
[i
] == partition_index
)
830 tpa
->next_partition
[i
] = tpa
->next_partition
[partition_index
];
838 /* Free the memory used by tree_partition_associator object TPA. */
841 tpa_delete (tpa_p tpa
)
846 free (tpa
->partition_to_tree_map
);
847 free (tpa
->next_partition
);
852 /* This function will remove any tree entries from TPA which have only a single
853 element. This will help keep the size of the conflict graph down. The
854 function returns the number of remaining tree lists. */
857 tpa_compact (tpa_p tpa
)
859 int last
, x
, y
, first
, swap_i
;
862 /* Find the last list which has more than 1 partition. */
863 for (last
= tpa
->num_trees
- 1; last
> 0; last
--)
865 first
= tpa_first_partition (tpa
, last
);
866 if (tpa_next_partition (tpa
, first
) != NO_PARTITION
)
873 first
= tpa_first_partition (tpa
, x
);
875 /* If there is not more than one partition, swap with the current end
877 if (tpa_next_partition (tpa
, first
) == NO_PARTITION
)
879 swap_t
= VARRAY_TREE (tpa
->trees
, last
);
880 swap_i
= VARRAY_INT (tpa
->first_partition
, last
);
882 /* Update the last entry. Since it is known to only have one
883 partition, there is nothing else to update. */
884 VARRAY_TREE (tpa
->trees
, last
) = VARRAY_TREE (tpa
->trees
, x
);
885 VARRAY_INT (tpa
->first_partition
, last
)
886 = VARRAY_INT (tpa
->first_partition
, x
);
887 tpa
->partition_to_tree_map
[tpa_first_partition (tpa
, last
)] = last
;
889 /* Since this list is known to have more than one partition, update
890 the list owner entries. */
891 VARRAY_TREE (tpa
->trees
, x
) = swap_t
;
892 VARRAY_INT (tpa
->first_partition
, x
) = swap_i
;
893 for (y
= tpa_first_partition (tpa
, x
);
895 y
= tpa_next_partition (tpa
, y
))
896 tpa
->partition_to_tree_map
[y
] = x
;
898 /* Ensure last is a list with more than one partition. */
900 for (; last
> x
; last
--)
902 first
= tpa_first_partition (tpa
, last
);
903 if (tpa_next_partition (tpa
, first
) != NO_PARTITION
)
910 first
= tpa_first_partition (tpa
, x
);
911 if (tpa_next_partition (tpa
, first
) != NO_PARTITION
)
913 tpa
->uncompressed_num
= tpa
->num_trees
;
919 /* Initialize a root_var object with SSA partitions from MAP which are based
920 on each root variable. */
923 root_var_init (var_map map
)
926 int num_partitions
= num_var_partitions (map
);
936 seen
= sbitmap_alloc (num_partitions
);
939 /* Start at the end and work towards the front. This will provide a list
940 that is ordered from smallest to largest. */
941 for (x
= num_partitions
- 1; x
>= 0; x
--)
943 t
= partition_to_var (map
, x
);
945 /* The var map may not be compacted yet, so check for NULL. */
949 p
= var_to_partition (map
, t
);
951 #ifdef ENABLE_CHECKING
952 if (p
== NO_PARTITION
)
956 /* Make sure we only put coalesced partitions into the list once. */
957 if (TEST_BIT (seen
, p
))
960 if (TREE_CODE (t
) == SSA_NAME
)
961 t
= SSA_NAME_VAR (t
);
963 if (ann
->root_var_processed
)
965 rv
->next_partition
[p
] = VARRAY_INT (rv
->first_partition
,
966 VAR_ANN_ROOT_INDEX (ann
));
967 VARRAY_INT (rv
->first_partition
, VAR_ANN_ROOT_INDEX (ann
)) = p
;
971 ann
->root_var_processed
= 1;
972 VAR_ANN_ROOT_INDEX (ann
) = rv
->num_trees
++;
973 VARRAY_PUSH_TREE (rv
->trees
, t
);
974 VARRAY_PUSH_INT (rv
->first_partition
, p
);
976 rv
->partition_to_tree_map
[p
] = VAR_ANN_ROOT_INDEX (ann
);
979 /* Reset the out_of_ssa_tag flag on each variable for later use. */
980 for (x
= 0; x
< rv
->num_trees
; x
++)
982 t
= VARRAY_TREE (rv
->trees
, x
);
983 var_ann (t
)->root_var_processed
= 0;
991 /* Initialize a type_var structure which associates all the partitions in MAP
992 of the same type to the type node's index. Volatiles are ignored. */
995 type_var_init (var_map map
)
999 int num_partitions
= num_var_partitions (map
);
1003 seen
= sbitmap_alloc (num_partitions
);
1004 sbitmap_zero (seen
);
1006 tv
= tpa_init (map
);
1010 for (x
= num_partitions
- 1; x
>= 0; x
--)
1012 t
= partition_to_var (map
, x
);
1014 /* Disallow coalescing of these types of variables. */
1016 || TREE_THIS_VOLATILE (t
)
1017 || TREE_CODE (t
) == RESULT_DECL
1018 || TREE_CODE (t
) == PARM_DECL
1020 && (DECL_REGISTER (t
)
1021 || !DECL_ARTIFICIAL (t
)
1022 || DECL_RTL_SET_P (t
))))
1025 p
= var_to_partition (map
, t
);
1027 #ifdef ENABLE_CHECKING
1028 if (p
== NO_PARTITION
)
1032 /* If partitions have been coalesced, only add the representative
1033 for the partition to the list once. */
1034 if (TEST_BIT (seen
, p
))
1039 /* Find the list for this type. */
1040 for (y
= 0; y
< tv
->num_trees
; y
++)
1041 if (t
== VARRAY_TREE (tv
->trees
, y
))
1043 if (y
== tv
->num_trees
)
1046 VARRAY_PUSH_TREE (tv
->trees
, t
);
1047 VARRAY_PUSH_INT (tv
->first_partition
, p
);
1051 tv
->next_partition
[p
] = VARRAY_INT (tv
->first_partition
, y
);
1052 VARRAY_INT (tv
->first_partition
, y
) = p
;
1054 tv
->partition_to_tree_map
[p
] = y
;
1056 sbitmap_free (seen
);
1061 /* Create a new coalesce list object from MAP and return it. */
1064 create_coalesce_list (var_map map
)
1066 coalesce_list_p list
;
1068 list
= (coalesce_list_p
) xmalloc (sizeof (struct coalesce_list_d
));
1071 list
->add_mode
= true;
1072 list
->list
= (partition_pair_p
*) xcalloc (num_var_partitions (map
),
1073 sizeof (struct partition_pair_d
));
1078 /* Delete coalesce list CL. */
1081 delete_coalesce_list (coalesce_list_p cl
)
1088 /* Find a matching coalesce pair object in CL for partitions P1 and P2. If
1089 one isn't found, return NULL if CREATE is false, otherwise create a new
1090 coalesce pair object and return it. */
1092 static partition_pair_p
1093 find_partition_pair (coalesce_list_p cl
, int p1
, int p2
, bool create
)
1095 partition_pair_p node
, tmp
;
1098 /* Normalize so that p1 is the smaller value. */
1108 /* The list is sorted such that if we find a value greater than p2,
1109 p2 is not in the list. */
1110 for (node
= cl
->list
[p1
]; node
; node
= node
->next
)
1112 if (node
->second_partition
== p2
)
1115 if (node
->second_partition
> p2
)
1123 node
= (partition_pair_p
) xmalloc (sizeof (struct partition_pair_d
));
1124 node
->first_partition
= p1
;
1125 node
->second_partition
= p2
;
1130 node
->next
= tmp
->next
;
1135 /* This is now the first node in the list. */
1136 node
->next
= cl
->list
[p1
];
1137 cl
->list
[p1
] = node
;
1144 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
1147 add_coalesce (coalesce_list_p cl
, int p1
, int p2
, int value
)
1149 partition_pair_p node
;
1151 #ifdef ENABLE_CHECKING
1159 node
= find_partition_pair (cl
, p1
, p2
, true);
1161 node
->cost
+= value
;
1165 /* Comparison function to allow qsort to sort P1 and P2 in descending order. */
1168 int compare_pairs (const void *p1
, const void *p2
)
1170 return (*(partition_pair_p
*)p2
)->cost
- (*(partition_pair_p
*)p1
)->cost
;
1174 /* Prepare CL for removal of preferred pairs. When finished, list element
1175 0 has all the coalesce pairs, sorted in order from most important coalesce
1176 to least important. */
1179 sort_coalesce_list (coalesce_list_p cl
)
1182 partition_pair_p chain
, p
;
1183 partition_pair_p
*list
;
1188 cl
->add_mode
= false;
1190 /* Compact the array of lists to a single list, and count the elements. */
1193 for (x
= 0; x
< num_var_partitions (cl
->map
); x
++)
1194 if (cl
->list
[x
] != NULL
)
1196 for (p
= cl
->list
[x
]; p
->next
!= NULL
; p
= p
->next
)
1200 chain
= cl
->list
[x
];
1204 /* Only call qsort if there are more than 2 items. */
1207 list
= xmalloc (sizeof (partition_pair_p
) * num
);
1209 for (p
= chain
; p
!= NULL
; p
= p
->next
)
1212 #ifdef ENABLE_CHECKING
1217 qsort (list
, count
, sizeof (partition_pair_p
), compare_pairs
);
1220 for (x
= 1; x
< num
; x
++)
1226 cl
->list
[0] = list
[0];
1231 cl
->list
[0] = chain
;
1234 /* Simply swap the two elements if they are in the wrong order. */
1235 if (chain
->cost
< chain
->next
->cost
)
1237 cl
->list
[0] = chain
->next
;
1238 cl
->list
[0]->next
= chain
;
1246 /* Retrieve the best remaining pair to coalesce from CL. Returns the 2
1247 partitions via P1 and P2. Their calculated cost is returned by the function.
1248 NO_BEST_COALESCE is returned if the coalesce list is empty. */
1251 pop_best_coalesce (coalesce_list_p cl
, int *p1
, int *p2
)
1253 partition_pair_p node
;
1261 return NO_BEST_COALESCE
;
1263 cl
->list
[0] = node
->next
;
1265 *p1
= node
->first_partition
;
1266 *p2
= node
->second_partition
;
1274 /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
1275 VAR and any other live partitions in VEC which are associated via TPA.
1276 Reset the live bit in VEC. */
1279 add_conflicts_if_valid (tpa_p tpa
, conflict_graph graph
,
1280 var_map map
, bitmap vec
, tree var
)
1283 p
= var_to_partition (map
, var
);
1284 if (p
!= NO_PARTITION
)
1286 bitmap_clear_bit (vec
, p
);
1287 first
= tpa_find_tree (tpa
, p
);
1288 /* If find returns nothing, this object isn't interesting. */
1289 if (first
== TPA_NONE
)
1291 /* Only add interferences between objects in the same list. */
1292 for (y
= tpa_first_partition (tpa
, first
);
1294 y
= tpa_next_partition (tpa
, y
))
1296 if (bitmap_bit_p (vec
, y
))
1297 conflict_graph_add (graph
, p
, y
);
1303 /* Return a conflict graph for the information contained in LIVE_INFO. Only
1304 conflicts between items in the same TPA list are added. If optional
1305 coalesce list CL is passed in, any copies encountered are added. */
1308 build_tree_conflict_graph (tree_live_info_p liveinfo
, tpa_p tpa
,
1311 conflict_graph graph
;
1316 varray_type partition_link
, tpa_to_clear
, tpa_nodes
;
1321 map
= live_var_map (liveinfo
);
1322 graph
= conflict_graph_new (num_var_partitions (map
));
1324 if (tpa_num_trees (tpa
) == 0)
1327 live
= BITMAP_XMALLOC ();
1329 VARRAY_INT_INIT (partition_link
, num_var_partitions (map
) + 1, "part_link");
1330 VARRAY_INT_INIT (tpa_nodes
, tpa_num_trees (tpa
), "tpa nodes");
1331 VARRAY_INT_INIT (tpa_to_clear
, 50, "tpa to clear");
1335 block_stmt_iterator bsi
;
1338 /* Start with live on exit temporaries. */
1339 bitmap_copy (live
, live_on_exit (liveinfo
, bb
));
1341 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
); bsi_prev (&bsi
))
1343 bool is_a_copy
= false;
1344 tree stmt
= bsi_stmt (bsi
);
1347 get_stmt_operands (stmt
);
1348 ann
= stmt_ann (stmt
);
1350 /* A copy between 2 partitions does not introduce an interference
1351 by itself. If they did, you would never be able to coalesce
1352 two things which are copied. If the two variables really do
1353 conflict, they will conflict elsewhere in the program.
1355 This is handled specially here since we may also be interested
1356 in copies between real variables and SSA_NAME variables. We may
1357 be interested in trying to coalesce SSA_NAME variables with
1358 root variables in some cases. */
1360 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1362 tree lhs
= TREE_OPERAND (stmt
, 0);
1363 tree rhs
= TREE_OPERAND (stmt
, 1);
1367 if (DECL_P (lhs
) || TREE_CODE (lhs
) == SSA_NAME
)
1368 p1
= var_to_partition (map
, lhs
);
1372 if (DECL_P (rhs
) || TREE_CODE (rhs
) == SSA_NAME
)
1373 p2
= var_to_partition (map
, rhs
);
1377 if (p1
!= NO_PARTITION
&& p2
!= NO_PARTITION
)
1380 bit
= bitmap_bit_p (live
, p2
);
1381 /* If the RHS is live, make it not live while we add
1382 the conflicts, then make it live again. */
1384 bitmap_clear_bit (live
, p2
);
1385 add_conflicts_if_valid (tpa
, graph
, map
, live
, lhs
);
1387 bitmap_set_bit (live
, p2
);
1389 add_coalesce (cl
, p1
, p2
, 1);
1390 set_if_valid (map
, live
, rhs
);
1398 defs
= DEF_OPS (ann
);
1399 num
= NUM_DEFS (defs
);
1400 for (x
= 0; x
< num
; x
++)
1402 var
= DEF_OP (defs
, x
);
1403 add_conflicts_if_valid (tpa
, graph
, map
, live
, var
);
1406 uses
= USE_OPS (ann
);
1407 num
= NUM_USES (uses
);
1408 for (x
= 0; x
< num
; x
++)
1410 var
= USE_OP (uses
, x
);
1411 set_if_valid (map
, live
, var
);
1416 /* If result of a PHI is unused, then the loops over the statements
1417 will not record any conflicts. However, since the PHI node is
1418 going to be translated out of SSA form we must record a conflict
1419 between the result of the PHI and any variables with are live.
1420 Otherwise the out-of-ssa translation may create incorrect code. */
1421 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1423 tree result
= PHI_RESULT (phi
);
1424 int p
= var_to_partition (map
, result
);
1426 if (p
!= NO_PARTITION
&& ! bitmap_bit_p (live
, p
))
1427 add_conflicts_if_valid (tpa
, graph
, map
, live
, result
);
1430 /* Anything which is still live at this point interferes.
1431 In order to implement this efficiently, only conflicts between
1432 partitions which have the same TPA root need be added.
1433 TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
1434 entry points to an index into 'partition_link', which then indexes
1435 into itself forming a linked list of partitions sharing a tpa root
1436 which have been seen as live up to this point. Since partitions start
1437 at index zero, all entries in partition_link are (partition + 1).
1439 Conflicts are added between the current partition and any already seen.
1440 tpa_clear contains all the tpa_roots processed, and these are the only
1441 entries which need to be zero'd out for a clean restart. */
1443 EXECUTE_IF_SET_IN_BITMAP (live
, 0, x
,
1445 i
= tpa_find_tree (tpa
, x
);
1448 int start
= VARRAY_INT (tpa_nodes
, i
);
1449 /* If start is 0, a new root reference list is being started.
1450 Register it to be cleared. */
1452 VARRAY_PUSH_INT (tpa_to_clear
, i
);
1454 /* Add interferences to other tpa members seen. */
1455 for (y
= start
; y
!= 0; y
= VARRAY_INT (partition_link
, y
))
1456 conflict_graph_add (graph
, x
, y
- 1);
1457 VARRAY_INT (tpa_nodes
, i
) = x
+ 1;
1458 VARRAY_INT (partition_link
, x
+ 1) = start
;
1462 /* Now clear the used tpa root references. */
1463 for (l
= 0; l
< VARRAY_ACTIVE_SIZE (tpa_to_clear
); l
++)
1464 VARRAY_INT (tpa_nodes
, VARRAY_INT (tpa_to_clear
, l
)) = 0;
1465 VARRAY_POP_ALL (tpa_to_clear
);
1468 BITMAP_XFREE (live
);
1473 /* This routine will attempt to coalesce the elements in TPA subject to the
1474 conflicts found in GRAPH. If optional coalesce_list CL is provided,
1475 only coalesces specified within the coalesce list are attempted. Otherwise
1476 an attempt is made to coalesce as many partitions within each TPA grouping
1477 as possible. If DEBUG is provided, debug output will be sent there. */
1480 coalesce_tpa_members (tpa_p tpa
, conflict_graph graph
, var_map map
,
1481 coalesce_list_p cl
, FILE *debug
)
1486 /* Attempt to coalesce any items in a coalesce list. */
1489 while (pop_best_coalesce (cl
, &x
, &y
) != NO_BEST_COALESCE
)
1493 fprintf (debug
, "Coalesce list: (%d)", x
);
1494 print_generic_expr (debug
, partition_to_var (map
, x
), TDF_SLIM
);
1495 fprintf (debug
, " & (%d)", y
);
1496 print_generic_expr (debug
, partition_to_var (map
, y
), TDF_SLIM
);
1499 w
= tpa_find_tree (tpa
, x
);
1500 z
= tpa_find_tree (tpa
, y
);
1501 if (w
!= z
|| w
== TPA_NONE
|| z
== TPA_NONE
)
1506 fprintf (debug
, ": Fail, Non-matching TPA's\n");
1508 fprintf (debug
, ": Fail %d non TPA.\n", x
);
1510 fprintf (debug
, ": Fail %d non TPA.\n", y
);
1514 var
= partition_to_var (map
, x
);
1515 tmp
= partition_to_var (map
, y
);
1516 x
= var_to_partition (map
, var
);
1517 y
= var_to_partition (map
, tmp
);
1519 fprintf (debug
, " [map: %d, %d] ", x
, y
);
1523 fprintf (debug
, ": Already Coalesced.\n");
1526 if (!conflict_graph_conflict_p (graph
, x
, y
))
1528 z
= var_union (map
, var
, tmp
);
1529 if (z
== NO_PARTITION
)
1532 fprintf (debug
, ": Unable to perform partition union.\n");
1536 /* z is the new combined partition. We need to remove the other
1537 partition from the list. Set x to be that other partition. */
1540 conflict_graph_merge_regs (graph
, x
, y
);
1541 w
= tpa_find_tree (tpa
, y
);
1542 tpa_remove_partition (tpa
, w
, y
);
1546 conflict_graph_merge_regs (graph
, y
, x
);
1547 w
= tpa_find_tree (tpa
, x
);
1548 tpa_remove_partition (tpa
, w
, x
);
1552 fprintf (debug
, ": Success -> %d\n", z
);
1556 fprintf (debug
, ": Fail due to conflict\n");
1558 /* If using a coalesce list, don't try to coalesce anything else. */
1562 for (x
= 0; x
< tpa_num_trees (tpa
); x
++)
1564 while (tpa_first_partition (tpa
, x
) != TPA_NONE
)
1567 /* Coalesce first partition with anything that doesn't conflict. */
1568 y
= tpa_first_partition (tpa
, x
);
1569 tpa_remove_partition (tpa
, x
, y
);
1571 var
= partition_to_var (map
, y
);
1572 /* p1 is the partition representative to which y belongs. */
1573 p1
= var_to_partition (map
, var
);
1575 for (z
= tpa_next_partition (tpa
, y
);
1577 z
= tpa_next_partition (tpa
, z
))
1579 tmp
= partition_to_var (map
, z
);
1580 /* p2 is the partition representative to which z belongs. */
1581 p2
= var_to_partition (map
, tmp
);
1584 fprintf (debug
, "Coalesce : ");
1585 print_generic_expr (debug
, var
, TDF_SLIM
);
1586 fprintf (debug
, " &");
1587 print_generic_expr (debug
, tmp
, TDF_SLIM
);
1588 fprintf (debug
, " (%d ,%d)", p1
, p2
);
1591 /* If partitions are already merged, don't check for conflict. */
1594 tpa_remove_partition (tpa
, x
, z
);
1596 fprintf (debug
, ": Already coalesced\n");
1599 if (!conflict_graph_conflict_p (graph
, p1
, p2
))
1602 if (tpa_find_tree (tpa
, y
) == TPA_NONE
1603 || tpa_find_tree (tpa
, z
) == TPA_NONE
)
1606 fprintf (debug
, ": Fail non-TPA member\n");
1609 if ((v
= var_union (map
, var
, tmp
)) == NO_PARTITION
)
1612 fprintf (debug
, ": Fail cannot combine partitions\n");
1616 tpa_remove_partition (tpa
, x
, z
);
1618 conflict_graph_merge_regs (graph
, v
, z
);
1621 /* Update the first partition's representative. */
1622 conflict_graph_merge_regs (graph
, v
, y
);
1626 /* The root variable of the partition may be changed
1628 var
= partition_to_var (map
, p1
);
1631 fprintf (debug
, ": Success -> %d\n", v
);
1635 fprintf (debug
, ": Fail, Conflict\n");
1642 /* Send debug info for coalesce list CL to file F. */
1645 dump_coalesce_list (FILE *f
, coalesce_list_p cl
)
1647 partition_pair_p node
;
1653 fprintf (f
, "Coalesce List:\n");
1654 num
= num_var_partitions (cl
->map
);
1655 for (x
= 0; x
< num
; x
++)
1661 print_generic_expr (f
, partition_to_var (cl
->map
, x
), TDF_SLIM
);
1662 fprintf (f
, "] - ");
1663 for ( ; node
; node
= node
->next
)
1665 var
= partition_to_var (cl
->map
, node
->second_partition
);
1666 print_generic_expr (f
, var
, TDF_SLIM
);
1667 fprintf (f
, "(%1d), ", node
->cost
);
1675 fprintf (f
, "Sorted Coalesce list:\n");
1676 for (node
= cl
->list
[0]; node
; node
= node
->next
)
1678 fprintf (f
, "(%d) ", node
->cost
);
1679 var
= partition_to_var (cl
->map
, node
->first_partition
);
1680 print_generic_expr (f
, var
, TDF_SLIM
);
1682 var
= partition_to_var (cl
->map
, node
->second_partition
);
1683 print_generic_expr (f
, var
, TDF_SLIM
);
1690 /* Output tree_partition_associator object TPA to file F.. */
1693 tpa_dump (FILE *f
, tpa_p tpa
)
1700 for (x
= 0; x
< tpa_num_trees (tpa
); x
++)
1702 print_generic_expr (f
, tpa_tree (tpa
, x
), TDF_SLIM
);
1703 fprintf (f
, " : (");
1704 for (i
= tpa_first_partition (tpa
, x
);
1706 i
= tpa_next_partition (tpa
, i
))
1708 fprintf (f
, "(%d)",i
);
1709 print_generic_expr (f
, partition_to_var (tpa
->map
, i
), TDF_SLIM
);
1712 #ifdef ENABLE_CHECKING
1713 if (tpa_find_tree (tpa
, i
) != x
)
1714 fprintf (f
, "**find tree incorrectly set** ");
1724 /* Output partition map MAP to file F. */
1727 dump_var_map (FILE *f
, var_map map
)
1733 fprintf (f
, "\nPartition map \n\n");
1735 for (x
= 0; x
< map
->num_partitions
; x
++)
1737 if (map
->compact_to_partition
!= NULL
)
1738 p
= map
->compact_to_partition
[x
];
1742 if (map
->partition_to_var
[p
] == NULL_TREE
)
1746 for (y
= 1; y
< num_ssa_names
; y
++)
1748 p
= partition_find (map
->var_partition
, y
);
1749 if (map
->partition_to_compact
)
1750 p
= map
->partition_to_compact
[p
];
1755 fprintf(f
, "Partition %d (", x
);
1756 print_generic_expr (f
, partition_to_var (map
, p
), TDF_SLIM
);
1759 fprintf (f
, "%d ", y
);
1769 /* Output live range info LIVE to file F, controlled by FLAG. */
1772 dump_live_info (FILE *f
, tree_live_info_p live
, int flag
)
1776 var_map map
= live
->map
;
1778 if ((flag
& LIVEDUMP_ENTRY
) && live
->livein
)
1782 fprintf (f
, "\nLive on entry to BB%d : ", bb
->index
);
1783 for (i
= 0; i
< num_var_partitions (map
); i
++)
1785 if (bitmap_bit_p (live_entry_blocks (live
, i
), bb
->index
))
1787 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1795 if ((flag
& LIVEDUMP_EXIT
) && live
->liveout
)
1799 fprintf (f
, "\nLive on exit from BB%d : ", bb
->index
);
1800 EXECUTE_IF_SET_IN_BITMAP (live
->liveout
[bb
->index
], 0, i
,
1802 print_generic_expr (f
, partition_to_var (map
, i
), TDF_SLIM
);
1810 /* Register partitions in MAP so that we can take VARS out of SSA form.
1811 This requires a walk over all the PHI nodes and all the statements. */
1814 register_ssa_partitions_for_vars (bitmap vars
, var_map map
)
1818 if (bitmap_first_set_bit (vars
) >= 0)
1821 /* Find every instance (SSA_NAME) of variables in VARs and
1822 register a new partition for them. This requires examining
1823 every statement and every PHI node once. */
1826 block_stmt_iterator bsi
;
1830 /* Register partitions for SSA_NAMEs appearing in the PHI
1831 nodes in this basic block.
1833 Note we delete PHI nodes in this loop if they are
1834 associated with virtual vars which are going to be
1836 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
1838 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
1840 next
= PHI_CHAIN (phi
);
1841 if (bitmap_bit_p (vars
, var_ann (result
)->uid
))
1843 if (! is_gimple_reg (result
))
1844 remove_phi_node (phi
, NULL_TREE
, bb
);
1849 /* Register a partition for the result. */
1850 register_ssa_partition (map
, PHI_RESULT (phi
), 0);
1852 /* Register a partition for each argument as needed. */
1853 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1855 tree arg
= PHI_ARG_DEF (phi
, i
);
1857 if (TREE_CODE (arg
) != SSA_NAME
)
1859 if (!bitmap_bit_p (vars
,
1860 var_ann (SSA_NAME_VAR (arg
))->uid
))
1863 register_ssa_partition (map
, arg
, 1);
1869 /* Now register partitions for SSA_NAMEs appearing in each
1870 statement in this block. */
1871 for (bsi
= bsi_start (bb
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
1873 stmt_ann_t ann
= stmt_ann (bsi_stmt (bsi
));
1874 use_optype uses
= USE_OPS (ann
);
1875 def_optype defs
= DEF_OPS (ann
);
1878 for (i
= 0; i
< NUM_USES (uses
); i
++)
1880 tree op
= USE_OP (uses
, i
);
1882 if (TREE_CODE (op
) == SSA_NAME
1883 && bitmap_bit_p (vars
, var_ann (SSA_NAME_VAR (op
))->uid
))
1884 register_ssa_partition (map
, op
, 1);
1887 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
1889 tree op
= DEF_OP (defs
, i
);
1891 if (TREE_CODE (op
) == SSA_NAME
1892 && bitmap_bit_p (vars
,
1893 var_ann (SSA_NAME_VAR (op
))->uid
))
1894 register_ssa_partition (map
, op
, 0);