1 /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 Copyright (C) 2004-2018 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"
32 #include "tree-pretty-print.h"
33 #include "diagnostic-core.h"
35 #include "gimple-iterator.h"
36 #include "tree-ssa-live.h"
37 #include "tree-ssa-coalesce.h"
40 #include "stor-layout.h"
42 /* This set of routines implements a coalesce_list. This is an object which
43 is used to track pairs of ssa_names which are desirable to coalesce
44 together to avoid copies. Costs are associated with each pair, and when
45 all desired information has been collected, the object can be used to
46 order the pairs for processing. */
48 /* This structure defines a pair entry. */
56 /* A count of the number of unique partitions this pair would conflict
57 with if coalescing was successful. This is the secondary sort key,
58 given two pairs with equal costs, we will prefer the pair with a smaller
61 This is lazily initialized when we discover two coalescing pairs have
62 the same primary cost.
64 Note this is not updated and propagated as pairs are coalesced. */
67 /* The order in which coalescing pairs are discovered is recorded in this
68 field, which is used as the final tie breaker when sorting coalesce
73 /* This represents a conflict graph. Implemented as an array of bitmaps.
74 A full matrix is used for conflicts rather than just upper triangular form.
75 this makes it much simpler and faster to perform conflict merges. */
79 bitmap_obstack obstack
; /* A place to allocate our bitmaps. */
80 vec
<bitmap
> conflicts
;
83 /* The narrow API of the qsort comparison function doesn't allow easy
84 access to additional arguments. So we have two globals (ick) to hold
85 the data we need. They're initialized before the call to qsort and
86 wiped immediately after. */
87 static ssa_conflicts
*conflicts_
;
90 /* Coalesce pair hashtable helpers. */
92 struct coalesce_pair_hasher
: nofree_ptr_hash
<coalesce_pair
>
94 static inline hashval_t
hash (const coalesce_pair
*);
95 static inline bool equal (const coalesce_pair
*, const coalesce_pair
*);
98 /* Hash function for coalesce list. Calculate hash for PAIR. */
101 coalesce_pair_hasher::hash (const coalesce_pair
*pair
)
103 hashval_t a
= (hashval_t
)(pair
->first_element
);
104 hashval_t b
= (hashval_t
)(pair
->second_element
);
106 return b
* (b
- 1) / 2 + a
;
109 /* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2,
110 returning TRUE if the two pairs are equivalent. */
113 coalesce_pair_hasher::equal (const coalesce_pair
*p1
, const coalesce_pair
*p2
)
115 return (p1
->first_element
== p2
->first_element
116 && p1
->second_element
== p2
->second_element
);
119 typedef hash_table
<coalesce_pair_hasher
> coalesce_table_type
;
120 typedef coalesce_table_type::iterator coalesce_iterator_type
;
130 /* This structure maintains the list of coalesce pairs. */
134 coalesce_table_type
*list
; /* Hash table. */
135 coalesce_pair
**sorted
; /* List when sorted. */
136 int num_sorted
; /* Number in the sorted list. */
137 cost_one_pair
*cost_one_list
;/* Single use coalesces with cost 1. */
140 #define NO_BEST_COALESCE -1
141 #define MUST_COALESCE_COST INT_MAX
144 /* Return cost of execution of copy instruction with FREQUENCY. */
147 coalesce_cost (int frequency
, bool optimize_for_size
)
149 /* Base costs on BB frequencies bounded by 1. */
150 int cost
= frequency
;
155 if (optimize_for_size
)
162 /* Return the cost of executing a copy instruction in basic block BB. */
165 coalesce_cost_bb (basic_block bb
)
167 return coalesce_cost (bb
->count
.to_frequency (cfun
),
168 optimize_bb_for_size_p (bb
));
172 /* Return the cost of executing a copy instruction on edge E. */
175 coalesce_cost_edge (edge e
)
179 /* Inserting copy on critical edge costs more than inserting it elsewhere. */
180 if (EDGE_CRITICAL_P (e
))
182 if (e
->flags
& EDGE_ABNORMAL
)
183 return MUST_COALESCE_COST
;
184 if (e
->flags
& EDGE_EH
)
188 FOR_EACH_EDGE (e2
, ei
, e
->dest
->preds
)
191 /* Putting code on EH edge that leads to BB
192 with multiple predecestors imply splitting of
196 /* If there are multiple EH predecestors, we
197 also copy EH regions and produce separate
198 landing pad. This is expensive. */
199 if (e2
->flags
& EDGE_EH
)
207 return coalesce_cost (EDGE_FREQUENCY (e
),
208 optimize_edge_for_size_p (e
)) * mult
;
212 /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
213 2 elements via P1 and P2. 1 is returned by the function if there is a pair,
214 NO_BEST_COALESCE is returned if there aren't any. */
217 pop_cost_one_pair (coalesce_list
*cl
, int *p1
, int *p2
)
221 ptr
= cl
->cost_one_list
;
223 return NO_BEST_COALESCE
;
225 *p1
= ptr
->first_element
;
226 *p2
= ptr
->second_element
;
227 cl
->cost_one_list
= ptr
->next
;
234 /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
235 2 elements via P1 and P2. Their calculated cost is returned by the function.
236 NO_BEST_COALESCE is returned if the coalesce list is empty. */
239 pop_best_coalesce (coalesce_list
*cl
, int *p1
, int *p2
)
244 if (cl
->sorted
== NULL
)
245 return pop_cost_one_pair (cl
, p1
, p2
);
247 if (cl
->num_sorted
== 0)
248 return pop_cost_one_pair (cl
, p1
, p2
);
250 node
= cl
->sorted
[--(cl
->num_sorted
)];
251 *p1
= node
->first_element
;
252 *p2
= node
->second_element
;
260 /* Create a new empty coalesce list object and return it. */
262 static inline coalesce_list
*
263 create_coalesce_list (void)
266 unsigned size
= num_ssa_names
* 3;
271 list
= (coalesce_list
*) xmalloc (sizeof (struct coalesce_list
));
272 list
->list
= new coalesce_table_type (size
);
274 list
->num_sorted
= 0;
275 list
->cost_one_list
= NULL
;
280 /* Delete coalesce list CL. */
283 delete_coalesce_list (coalesce_list
*cl
)
285 gcc_assert (cl
->cost_one_list
== NULL
);
289 gcc_assert (cl
->num_sorted
== 0);
293 /* Return the number of unique coalesce pairs in CL. */
296 num_coalesce_pairs (coalesce_list
*cl
)
298 return cl
->list
->elements ();
301 /* Find a matching coalesce pair object in CL for the pair P1 and P2. If
302 one isn't found, return NULL if CREATE is false, otherwise create a new
303 coalesce pair object and return it. */
305 static coalesce_pair
*
306 find_coalesce_pair (coalesce_list
*cl
, int p1
, int p2
, bool create
)
308 struct coalesce_pair p
;
309 coalesce_pair
**slot
;
312 /* Normalize so that p1 is the smaller value. */
315 p
.first_element
= p2
;
316 p
.second_element
= p1
;
320 p
.first_element
= p1
;
321 p
.second_element
= p2
;
324 hash
= coalesce_pair_hasher::hash (&p
);
325 slot
= cl
->list
->find_slot_with_hash (&p
, hash
, create
? INSERT
: NO_INSERT
);
331 struct coalesce_pair
* pair
= XNEW (struct coalesce_pair
);
332 gcc_assert (cl
->sorted
== NULL
);
333 pair
->first_element
= p
.first_element
;
334 pair
->second_element
= p
.second_element
;
336 pair
->index
= num_coalesce_pairs (cl
);
337 pair
->conflict_count
= 0;
341 return (struct coalesce_pair
*) *slot
;
345 add_cost_one_coalesce (coalesce_list
*cl
, int p1
, int p2
)
349 pair
= XNEW (cost_one_pair
);
350 pair
->first_element
= p1
;
351 pair
->second_element
= p2
;
352 pair
->next
= cl
->cost_one_list
;
353 cl
->cost_one_list
= pair
;
357 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
360 add_coalesce (coalesce_list
*cl
, int p1
, int p2
, int value
)
364 gcc_assert (cl
->sorted
== NULL
);
368 node
= find_coalesce_pair (cl
, p1
, p2
, true);
370 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
371 if (node
->cost
< MUST_COALESCE_COST
- 1)
373 if (value
< MUST_COALESCE_COST
- 1)
380 /* Compute and record how many unique conflicts would exist for the
381 representative partition for each coalesce pair in CL.
383 CONFLICTS is the conflict graph and MAP is the current partition view. */
386 initialize_conflict_count (coalesce_pair
*p
,
387 ssa_conflicts
*conflicts
,
390 int p1
= var_to_partition (map
, ssa_name (p
->first_element
));
391 int p2
= var_to_partition (map
, ssa_name (p
->second_element
));
393 /* 4 cases. If both P1 and P2 have conflicts, then build their
394 union and count the members. Else handle the degenerate cases
395 in the obvious ways. */
396 if (conflicts
->conflicts
[p1
] && conflicts
->conflicts
[p2
])
397 p
->conflict_count
= bitmap_count_unique_bits (conflicts
->conflicts
[p1
],
398 conflicts
->conflicts
[p2
]);
399 else if (conflicts
->conflicts
[p1
])
400 p
->conflict_count
= bitmap_count_bits (conflicts
->conflicts
[p1
]);
401 else if (conflicts
->conflicts
[p2
])
402 p
->conflict_count
= bitmap_count_bits (conflicts
->conflicts
[p2
]);
404 p
->conflict_count
= 0;
408 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
411 compare_pairs (const void *p1
, const void *p2
)
413 coalesce_pair
*const *const pp1
= (coalesce_pair
*const *) p1
;
414 coalesce_pair
*const *const pp2
= (coalesce_pair
*const *) p2
;
417 result
= (* pp1
)->cost
- (* pp2
)->cost
;
418 /* We use the size of the resulting conflict set as the secondary sort key.
419 Given two equal costing coalesce pairs, we want to prefer the pair that
420 has the smaller conflict set. */
423 if (flag_expensive_optimizations
)
425 /* Lazily initialize the conflict counts as it's fairly expensive
427 if ((*pp2
)->conflict_count
== 0)
428 initialize_conflict_count (*pp2
, conflicts_
, map_
);
429 if ((*pp1
)->conflict_count
== 0)
430 initialize_conflict_count (*pp1
, conflicts_
, map_
);
432 result
= (*pp2
)->conflict_count
- (*pp1
)->conflict_count
;
435 /* And if everything else is equal, then sort based on which
436 coalesce pair was found first. */
438 result
= (*pp2
)->index
- (*pp1
)->index
;
444 /* Iterate over CL using ITER, returning values in PAIR. */
446 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
447 FOR_EACH_HASH_TABLE_ELEMENT (*(CL)->list, (PAIR), coalesce_pair_p, (ITER))
450 /* Prepare CL for removal of preferred pairs. When finished they are sorted
451 in order from most important coalesce to least important. */
454 sort_coalesce_list (coalesce_list
*cl
, ssa_conflicts
*conflicts
, var_map map
)
458 coalesce_iterator_type ppi
;
460 gcc_assert (cl
->sorted
== NULL
);
462 num
= num_coalesce_pairs (cl
);
463 cl
->num_sorted
= num
;
467 /* Allocate a vector for the pair pointers. */
468 cl
->sorted
= XNEWVEC (coalesce_pair
*, num
);
470 /* Populate the vector with pointers to the pairs. */
472 FOR_EACH_PARTITION_PAIR (p
, ppi
, cl
)
474 gcc_assert (x
== num
);
476 /* Already sorted. */
480 /* We don't want to depend on qsort_r, so we have to stuff away
481 additional data into globals so it can be referenced in
483 conflicts_
= conflicts
;
485 qsort (cl
->sorted
, num
, sizeof (coalesce_pair
*), compare_pairs
);
491 /* Send debug info for coalesce list CL to file F. */
494 dump_coalesce_list (FILE *f
, coalesce_list
*cl
)
497 coalesce_iterator_type ppi
;
502 if (cl
->sorted
== NULL
)
504 fprintf (f
, "Coalesce List:\n");
505 FOR_EACH_PARTITION_PAIR (node
, ppi
, cl
)
507 tree var1
= ssa_name (node
->first_element
);
508 tree var2
= ssa_name (node
->second_element
);
509 print_generic_expr (f
, var1
, TDF_SLIM
);
510 fprintf (f
, " <-> ");
511 print_generic_expr (f
, var2
, TDF_SLIM
);
512 fprintf (f
, " (%1d, %1d), ", node
->cost
, node
->conflict_count
);
518 fprintf (f
, "Sorted Coalesce list:\n");
519 for (x
= cl
->num_sorted
- 1 ; x
>=0; x
--)
521 node
= cl
->sorted
[x
];
522 fprintf (f
, "(%d, %d) ", node
->cost
, node
->conflict_count
);
523 var
= ssa_name (node
->first_element
);
524 print_generic_expr (f
, var
, TDF_SLIM
);
525 fprintf (f
, " <-> ");
526 var
= ssa_name (node
->second_element
);
527 print_generic_expr (f
, var
, TDF_SLIM
);
534 /* Return an empty new conflict graph for SIZE elements. */
536 static inline ssa_conflicts
*
537 ssa_conflicts_new (unsigned size
)
541 ptr
= XNEW (ssa_conflicts
);
542 bitmap_obstack_initialize (&ptr
->obstack
);
543 ptr
->conflicts
.create (size
);
544 ptr
->conflicts
.safe_grow_cleared (size
);
549 /* Free storage for conflict graph PTR. */
552 ssa_conflicts_delete (ssa_conflicts
*ptr
)
554 bitmap_obstack_release (&ptr
->obstack
);
555 ptr
->conflicts
.release ();
560 /* Test if elements X and Y conflict in graph PTR. */
563 ssa_conflicts_test_p (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
565 bitmap bx
= ptr
->conflicts
[x
];
566 bitmap by
= ptr
->conflicts
[y
];
568 gcc_checking_assert (x
!= y
);
571 /* Avoid the lookup if Y has no conflicts. */
572 return by
? bitmap_bit_p (bx
, y
) : false;
578 /* Add a conflict with Y to the bitmap for X in graph PTR. */
581 ssa_conflicts_add_one (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
583 bitmap bx
= ptr
->conflicts
[x
];
584 /* If there are no conflicts yet, allocate the bitmap and set bit. */
586 bx
= ptr
->conflicts
[x
] = BITMAP_ALLOC (&ptr
->obstack
);
587 bitmap_set_bit (bx
, y
);
591 /* Add conflicts between X and Y in graph PTR. */
594 ssa_conflicts_add (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
596 gcc_checking_assert (x
!= y
);
597 ssa_conflicts_add_one (ptr
, x
, y
);
598 ssa_conflicts_add_one (ptr
, y
, x
);
602 /* Merge all Y's conflict into X in graph PTR. */
605 ssa_conflicts_merge (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
609 bitmap bx
= ptr
->conflicts
[x
];
610 bitmap by
= ptr
->conflicts
[y
];
612 gcc_checking_assert (x
!= y
);
616 /* Add a conflict between X and every one Y has. If the bitmap doesn't
617 exist, then it has already been coalesced, and we don't need to add a
619 EXECUTE_IF_SET_IN_BITMAP (by
, 0, z
, bi
)
621 bitmap bz
= ptr
->conflicts
[z
];
624 bool was_there
= bitmap_clear_bit (bz
, y
);
625 gcc_checking_assert (was_there
);
626 bitmap_set_bit (bz
, x
);
632 /* If X has conflicts, add Y's to X. */
633 bitmap_ior_into (bx
, by
);
635 ptr
->conflicts
[y
] = NULL
;
639 /* If X has no conflicts, simply use Y's. */
640 ptr
->conflicts
[x
] = by
;
641 ptr
->conflicts
[y
] = NULL
;
646 /* Dump a conflicts graph. */
649 ssa_conflicts_dump (FILE *file
, ssa_conflicts
*ptr
)
654 fprintf (file
, "\nConflict graph:\n");
656 FOR_EACH_VEC_ELT (ptr
->conflicts
, x
, b
)
659 fprintf (file
, "%d: ", x
);
660 dump_bitmap (file
, b
);
665 /* This structure is used to efficiently record the current status of live
666 SSA_NAMES when building a conflict graph.
667 LIVE_BASE_VAR has a bit set for each base variable which has at least one
669 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
670 index, and is used to track what partitions of each base variable are
671 live. This makes it easy to add conflicts between just live partitions
672 with the same base variable.
673 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
674 marked as being live. This delays clearing of these bitmaps until
675 they are actually needed again. */
679 bitmap_obstack obstack
; /* A place to allocate our bitmaps. */
680 bitmap live_base_var
; /* Indicates if a basevar is live. */
681 bitmap
*live_base_partitions
; /* Live partitions for each basevar. */
682 var_map map
; /* Var_map being used for partition mapping. */
686 /* This routine will create a new live track structure based on the partitions
690 new_live_track (var_map map
)
695 /* Make sure there is a partition view in place. */
696 gcc_assert (map
->partition_to_base_index
!= NULL
);
698 ptr
= (live_track
*) xmalloc (sizeof (live_track
));
700 lim
= num_basevars (map
);
701 bitmap_obstack_initialize (&ptr
->obstack
);
702 ptr
->live_base_partitions
= (bitmap
*) xmalloc (sizeof (bitmap
*) * lim
);
703 ptr
->live_base_var
= BITMAP_ALLOC (&ptr
->obstack
);
704 for (x
= 0; x
< lim
; x
++)
705 ptr
->live_base_partitions
[x
] = BITMAP_ALLOC (&ptr
->obstack
);
710 /* This routine will free the memory associated with PTR. */
713 delete_live_track (live_track
*ptr
)
715 bitmap_obstack_release (&ptr
->obstack
);
716 free (ptr
->live_base_partitions
);
721 /* This function will remove PARTITION from the live list in PTR. */
724 live_track_remove_partition (live_track
*ptr
, int partition
)
728 root
= basevar_index (ptr
->map
, partition
);
729 bitmap_clear_bit (ptr
->live_base_partitions
[root
], partition
);
730 /* If the element list is empty, make the base variable not live either. */
731 if (bitmap_empty_p (ptr
->live_base_partitions
[root
]))
732 bitmap_clear_bit (ptr
->live_base_var
, root
);
736 /* This function will adds PARTITION to the live list in PTR. */
739 live_track_add_partition (live_track
*ptr
, int partition
)
743 root
= basevar_index (ptr
->map
, partition
);
744 /* If this base var wasn't live before, it is now. Clear the element list
745 since it was delayed until needed. */
746 if (bitmap_set_bit (ptr
->live_base_var
, root
))
747 bitmap_clear (ptr
->live_base_partitions
[root
]);
748 bitmap_set_bit (ptr
->live_base_partitions
[root
], partition
);
753 /* Clear the live bit for VAR in PTR. */
756 live_track_clear_var (live_track
*ptr
, tree var
)
760 p
= var_to_partition (ptr
->map
, var
);
761 if (p
!= NO_PARTITION
)
762 live_track_remove_partition (ptr
, p
);
766 /* Return TRUE if VAR is live in PTR. */
769 live_track_live_p (live_track
*ptr
, tree var
)
773 p
= var_to_partition (ptr
->map
, var
);
774 if (p
!= NO_PARTITION
)
776 root
= basevar_index (ptr
->map
, p
);
777 if (bitmap_bit_p (ptr
->live_base_var
, root
))
778 return bitmap_bit_p (ptr
->live_base_partitions
[root
], p
);
784 /* This routine will add USE to PTR. USE will be marked as live in both the
785 ssa live map and the live bitmap for the root of USE. */
788 live_track_process_use (live_track
*ptr
, tree use
)
792 p
= var_to_partition (ptr
->map
, use
);
793 if (p
== NO_PARTITION
)
796 /* Mark as live in the appropriate live list. */
797 live_track_add_partition (ptr
, p
);
801 /* This routine will process a DEF in PTR. DEF will be removed from the live
802 lists, and if there are any other live partitions with the same base
803 variable, conflicts will be added to GRAPH. */
806 live_track_process_def (live_track
*ptr
, tree def
, ssa_conflicts
*graph
)
813 p
= var_to_partition (ptr
->map
, def
);
814 if (p
== NO_PARTITION
)
817 /* Clear the liveness bit. */
818 live_track_remove_partition (ptr
, p
);
820 /* If the bitmap isn't empty now, conflicts need to be added. */
821 root
= basevar_index (ptr
->map
, p
);
822 if (bitmap_bit_p (ptr
->live_base_var
, root
))
824 b
= ptr
->live_base_partitions
[root
];
825 EXECUTE_IF_SET_IN_BITMAP (b
, 0, x
, bi
)
826 ssa_conflicts_add (graph
, p
, x
);
831 /* Initialize PTR with the partitions set in INIT. */
834 live_track_init (live_track
*ptr
, bitmap init
)
839 /* Mark all live on exit partitions. */
840 EXECUTE_IF_SET_IN_BITMAP (init
, 0, p
, bi
)
841 live_track_add_partition (ptr
, p
);
845 /* This routine will clear all live partitions in PTR. */
848 live_track_clear_base_vars (live_track
*ptr
)
850 /* Simply clear the live base list. Anything marked as live in the element
851 lists will be cleared later if/when the base variable ever comes alive
853 bitmap_clear (ptr
->live_base_var
);
857 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
858 partition view of the var_map liveinfo is based on get entries in the
859 conflict graph. Only conflicts between ssa_name partitions with the same
860 base variable are added. */
862 static ssa_conflicts
*
863 build_ssa_conflict_graph (tree_live_info_p liveinfo
)
865 ssa_conflicts
*graph
;
872 /* If inter-variable coalescing is enabled, we may attempt to
873 coalesce variables from different base variables, including
874 different parameters, so we have to make sure default defs live
875 at the entry block conflict with each other. */
876 if (flag_tree_coalesce_vars
)
877 entry
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
881 map
= live_var_map (liveinfo
);
882 graph
= ssa_conflicts_new (num_var_partitions (map
));
884 live
= new_live_track (map
);
886 for (unsigned i
= 0; liveinfo
->map
->vec_bbs
.iterate (i
, &bb
); ++i
)
888 /* Start with live on exit temporaries. */
889 live_track_init (live
, live_on_exit (liveinfo
, bb
));
891 for (gimple_stmt_iterator gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);
895 gimple
*stmt
= gsi_stmt (gsi
);
897 /* A copy between 2 partitions does not introduce an interference
898 by itself. If they did, you would never be able to coalesce
899 two things which are copied. If the two variables really do
900 conflict, they will conflict elsewhere in the program.
902 This is handled by simply removing the SRC of the copy from the
903 live list, and processing the stmt normally. */
904 if (is_gimple_assign (stmt
))
906 tree lhs
= gimple_assign_lhs (stmt
);
907 tree rhs1
= gimple_assign_rhs1 (stmt
);
908 if (gimple_assign_copy_p (stmt
)
909 && TREE_CODE (lhs
) == SSA_NAME
910 && TREE_CODE (rhs1
) == SSA_NAME
)
911 live_track_clear_var (live
, rhs1
);
913 else if (is_gimple_debug (stmt
))
916 /* For stmts with more than one SSA_NAME definition pretend all the
917 SSA_NAME outputs but the first one are live at this point, so
918 that conflicts are added in between all those even when they are
919 actually not really live after the asm, because expansion might
920 copy those into pseudos after the asm and if multiple outputs
921 share the same partition, it might overwrite those that should
923 asm volatile (".." : "=r" (a) : "=r" (b) : "0" (a), "1" (a));
927 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_DEF
)
931 live_track_process_use (live
, var
);
933 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_DEF
)
934 live_track_process_def (live
, var
, graph
);
936 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_USE
)
937 live_track_process_use (live
, var
);
940 /* If result of a PHI is unused, looping over the statements will not
941 record any conflicts since the def was never live. Since the PHI node
942 is going to be translated out of SSA form, it will insert a copy.
943 There must be a conflict recorded between the result of the PHI and
944 any variables that are live. Otherwise the out-of-ssa translation
945 may create incorrect code. */
946 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
949 gphi
*phi
= gsi
.phi ();
950 tree result
= PHI_RESULT (phi
);
951 if (virtual_operand_p (result
))
953 if (live_track_live_p (live
, result
))
954 live_track_process_def (live
, result
, graph
);
957 /* Pretend there are defs for params' default defs at the start
958 of the (post-)entry block. This will prevent PARM_DECLs from
959 coalescing into the same partition. Although RESULT_DECLs'
960 default defs don't have a useful initial value, we have to
961 prevent them from coalescing with PARM_DECLs' default defs
962 too, otherwise assign_parms would attempt to assign different
963 RTL to the same partition. */
969 FOR_EACH_SSA_NAME (i
, var
, cfun
)
971 if (!SSA_NAME_IS_DEFAULT_DEF (var
)
972 || !SSA_NAME_VAR (var
)
973 || VAR_P (SSA_NAME_VAR (var
)))
976 live_track_process_def (live
, var
, graph
);
977 /* Process a use too, so that it remains live and
978 conflicts with other parms' default defs, even unused
980 live_track_process_use (live
, var
);
984 live_track_clear_base_vars (live
);
987 delete_live_track (live
);
992 /* Shortcut routine to print messages to file F of the form:
993 "STR1 EXPR1 STR2 EXPR2 STR3." */
996 print_exprs (FILE *f
, const char *str1
, tree expr1
, const char *str2
,
997 tree expr2
, const char *str3
)
999 fprintf (f
, "%s", str1
);
1000 print_generic_expr (f
, expr1
, TDF_SLIM
);
1001 fprintf (f
, "%s", str2
);
1002 print_generic_expr (f
, expr2
, TDF_SLIM
);
1003 fprintf (f
, "%s", str3
);
1007 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
1010 fail_abnormal_edge_coalesce (int x
, int y
)
1012 fprintf (stderr
, "\nUnable to coalesce ssa_names %d and %d",x
, y
);
1013 fprintf (stderr
, " which are marked as MUST COALESCE.\n");
1014 print_generic_expr (stderr
, ssa_name (x
), TDF_SLIM
);
1015 fprintf (stderr
, " and ");
1016 print_generic_stmt (stderr
, ssa_name (y
), TDF_SLIM
);
1018 internal_error ("SSA corruption");
1021 /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
1022 and the DECL's default def is unused (i.e., it was introduced by
1023 create_default_def for out-of-ssa), mark VAR and the default def for
1027 coalesce_with_default (tree var
, coalesce_list
*cl
, bitmap used_in_copy
)
1029 if (SSA_NAME_IS_DEFAULT_DEF (var
)
1030 || !SSA_NAME_VAR (var
)
1031 || VAR_P (SSA_NAME_VAR (var
)))
1034 tree ssa
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1035 if (!has_zero_uses (ssa
))
1038 add_cost_one_coalesce (cl
, SSA_NAME_VERSION (ssa
), SSA_NAME_VERSION (var
));
1039 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1040 /* Default defs will have their used_in_copy bits set at the beginning of
1041 populate_coalesce_list_for_outofssa. */
1045 /* Given var_map MAP for a region, this function creates and returns a coalesce
1046 list as well as recording related ssa names in USED_IN_COPIES for use later
1047 in the out-of-ssa or live range computation process. */
1049 static coalesce_list
*
1050 create_coalesce_list_for_region (var_map map
, bitmap used_in_copy
)
1052 gimple_stmt_iterator gsi
;
1054 coalesce_list
*cl
= create_coalesce_list ();
1058 for (unsigned j
= 0; map
->vec_bbs
.iterate (j
, &bb
); ++j
)
1062 for (gphi_iterator gpi
= gsi_start_phis (bb
);
1066 gphi
*phi
= gpi
.phi ();
1070 bool saw_copy
= false;
1072 res
= gimple_phi_result (phi
);
1073 if (virtual_operand_p (res
))
1075 ver
= SSA_NAME_VERSION (res
);
1077 /* Register ssa_names and coalesces between the args and the result
1079 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1081 edge e
= gimple_phi_arg_edge (phi
, i
);
1082 arg
= PHI_ARG_DEF (phi
, i
);
1083 if (TREE_CODE (arg
) != SSA_NAME
)
1086 if (gimple_can_coalesce_p (arg
, res
)
1087 || (e
->flags
& EDGE_ABNORMAL
))
1090 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (arg
));
1091 if ((e
->flags
& EDGE_ABNORMAL
) == 0)
1093 int cost
= coalesce_cost_edge (e
);
1094 if (cost
== 1 && has_single_use (arg
))
1095 add_cost_one_coalesce (cl
, ver
, SSA_NAME_VERSION (arg
));
1097 add_coalesce (cl
, ver
, SSA_NAME_VERSION (arg
), cost
);
1102 bitmap_set_bit (used_in_copy
, ver
);
1105 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1107 stmt
= gsi_stmt (gsi
);
1109 if (is_gimple_debug (stmt
))
1112 /* Check for copy coalesces. */
1113 switch (gimple_code (stmt
))
1117 tree lhs
= gimple_assign_lhs (stmt
);
1118 tree rhs1
= gimple_assign_rhs1 (stmt
);
1119 if (gimple_assign_ssa_name_copy_p (stmt
)
1120 && gimple_can_coalesce_p (lhs
, rhs1
))
1122 v1
= SSA_NAME_VERSION (lhs
);
1123 v2
= SSA_NAME_VERSION (rhs1
);
1124 cost
= coalesce_cost_bb (bb
);
1125 add_coalesce (cl
, v1
, v2
, cost
);
1126 bitmap_set_bit (used_in_copy
, v1
);
1127 bitmap_set_bit (used_in_copy
, v2
);
1134 tree res
= DECL_RESULT (current_function_decl
);
1135 if (VOID_TYPE_P (TREE_TYPE (res
))
1136 || !is_gimple_reg (res
))
1138 tree rhs1
= gimple_return_retval (as_a
<greturn
*> (stmt
));
1141 tree lhs
= ssa_default_def (cfun
, res
);
1143 if (TREE_CODE (rhs1
) == SSA_NAME
1144 && gimple_can_coalesce_p (lhs
, rhs1
))
1146 v1
= SSA_NAME_VERSION (lhs
);
1147 v2
= SSA_NAME_VERSION (rhs1
);
1148 cost
= coalesce_cost_bb (bb
);
1149 add_coalesce (cl
, v1
, v2
, cost
);
1150 bitmap_set_bit (used_in_copy
, v1
);
1151 bitmap_set_bit (used_in_copy
, v2
);
1158 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
1159 unsigned long noutputs
, i
;
1160 unsigned long ninputs
;
1161 tree
*outputs
, link
;
1162 noutputs
= gimple_asm_noutputs (asm_stmt
);
1163 ninputs
= gimple_asm_ninputs (asm_stmt
);
1164 outputs
= (tree
*) alloca (noutputs
* sizeof (tree
));
1165 for (i
= 0; i
< noutputs
; ++i
)
1167 link
= gimple_asm_output_op (asm_stmt
, i
);
1168 outputs
[i
] = TREE_VALUE (link
);
1171 for (i
= 0; i
< ninputs
; ++i
)
1173 const char *constraint
;
1176 unsigned long match
;
1178 link
= gimple_asm_input_op (asm_stmt
, i
);
1180 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
1181 input
= TREE_VALUE (link
);
1183 if (TREE_CODE (input
) != SSA_NAME
)
1186 match
= strtoul (constraint
, &end
, 10);
1187 if (match
>= noutputs
|| end
== constraint
)
1190 if (TREE_CODE (outputs
[match
]) != SSA_NAME
)
1193 v1
= SSA_NAME_VERSION (outputs
[match
]);
1194 v2
= SSA_NAME_VERSION (input
);
1196 if (gimple_can_coalesce_p (outputs
[match
], input
))
1198 cost
= coalesce_cost (REG_BR_PROB_BASE
,
1199 optimize_bb_for_size_p (bb
));
1200 add_coalesce (cl
, v1
, v2
, cost
);
1201 bitmap_set_bit (used_in_copy
, v1
);
1202 bitmap_set_bit (used_in_copy
, v2
);
1218 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1220 struct ssa_name_var_hash
: nofree_ptr_hash
<tree_node
>
1222 static inline hashval_t
hash (const tree_node
*);
1223 static inline int equal (const tree_node
*, const tree_node
*);
1227 ssa_name_var_hash::hash (const_tree n
)
1229 return DECL_UID (SSA_NAME_VAR (n
));
1233 ssa_name_var_hash::equal (const tree_node
*n1
, const tree_node
*n2
)
1235 return SSA_NAME_VAR (n1
) == SSA_NAME_VAR (n2
);
1239 /* This function populates coalesce list CL as well as recording related ssa
1240 names in USED_IN_COPIES for use later in the out-of-ssa process. */
1243 populate_coalesce_list_for_outofssa (coalesce_list
*cl
, bitmap used_in_copy
)
1250 /* Process result decls and live on entry variables for entry into the
1253 FOR_EACH_SSA_NAME (i
, var
, cfun
)
1255 if (!virtual_operand_p (var
))
1257 coalesce_with_default (var
, cl
, used_in_copy
);
1259 /* Add coalesces between all the result decls. */
1260 if (SSA_NAME_VAR (var
)
1261 && TREE_CODE (SSA_NAME_VAR (var
)) == RESULT_DECL
)
1263 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1264 if (first
== NULL_TREE
)
1268 gcc_assert (gimple_can_coalesce_p (var
, first
));
1269 v1
= SSA_NAME_VERSION (first
);
1270 v2
= SSA_NAME_VERSION (var
);
1271 cost
= coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun
));
1272 add_coalesce (cl
, v1
, v2
, cost
);
1275 /* Mark any default_def variables as being in the coalesce list
1276 since they will have to be coalesced with the base variable. If
1277 not marked as present, they won't be in the coalesce view. */
1278 if (SSA_NAME_IS_DEFAULT_DEF (var
)
1279 && (!has_zero_uses (var
)
1280 || (SSA_NAME_VAR (var
)
1281 && !VAR_P (SSA_NAME_VAR (var
)))))
1282 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1286 /* If this optimization is disabled, we need to coalesce all the
1287 names originating from the same SSA_NAME_VAR so debug info
1288 remains undisturbed. */
1289 if (!flag_tree_coalesce_vars
)
1292 hash_table
<ssa_name_var_hash
> ssa_name_hash (10);
1294 FOR_EACH_SSA_NAME (i
, a
, cfun
)
1296 if (SSA_NAME_VAR (a
)
1297 && !DECL_IGNORED_P (SSA_NAME_VAR (a
))
1298 && (!has_zero_uses (a
) || !SSA_NAME_IS_DEFAULT_DEF (a
)
1299 || !VAR_P (SSA_NAME_VAR (a
))))
1301 tree
*slot
= ssa_name_hash
.find_slot (a
, INSERT
);
1307 /* If the variable is a PARM_DECL or a RESULT_DECL, we
1308 _require_ that all the names originating from it be
1309 coalesced, because there must be a single partition
1310 containing all the names so that it can be assigned
1311 the canonical RTL location of the DECL safely.
1312 If in_lto_p, a function could have been compiled
1313 originally with optimizations and only the link
1314 performed at -O0, so we can't actually require it. */
1316 = (TREE_CODE (SSA_NAME_VAR (a
)) == VAR_DECL
|| in_lto_p
)
1317 ? MUST_COALESCE_COST
- 1 : MUST_COALESCE_COST
;
1318 add_coalesce (cl
, SSA_NAME_VERSION (a
),
1319 SSA_NAME_VERSION (*slot
), cost
);
1320 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (a
));
1321 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (*slot
));
1329 /* Attempt to coalesce ssa versions X and Y together using the partition
1330 mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1331 DEBUG, if it is nun-NULL. */
1334 attempt_coalesce (var_map map
, ssa_conflicts
*graph
, int x
, int y
,
1341 p1
= var_to_partition (map
, ssa_name (x
));
1342 p2
= var_to_partition (map
, ssa_name (y
));
1346 fprintf (debug
, "(%d)", x
);
1347 print_generic_expr (debug
, partition_to_var (map
, p1
), TDF_SLIM
);
1348 fprintf (debug
, " & (%d)", y
);
1349 print_generic_expr (debug
, partition_to_var (map
, p2
), TDF_SLIM
);
1355 fprintf (debug
, ": Already Coalesced.\n");
1360 fprintf (debug
, " [map: %d, %d] ", p1
, p2
);
1363 if (!ssa_conflicts_test_p (graph
, p1
, p2
))
1365 var1
= partition_to_var (map
, p1
);
1366 var2
= partition_to_var (map
, p2
);
1368 z
= var_union (map
, var1
, var2
);
1369 if (z
== NO_PARTITION
)
1372 fprintf (debug
, ": Unable to perform partition union.\n");
1376 /* z is the new combined partition. Remove the other partition from
1377 the list, and merge the conflicts. */
1379 ssa_conflicts_merge (graph
, p1
, p2
);
1381 ssa_conflicts_merge (graph
, p2
, p1
);
1384 fprintf (debug
, ": Success -> %d\n", z
);
1390 fprintf (debug
, ": Fail due to conflict\n");
1396 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1397 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1400 coalesce_partitions (var_map map
, ssa_conflicts
*graph
, coalesce_list
*cl
,
1410 /* First, coalesce all the copies across abnormal edges. These are not placed
1411 in the coalesce list because they do not need to be sorted, and simply
1412 consume extra memory/compilation time in large programs. */
1414 FOR_EACH_BB_FN (bb
, cfun
)
1416 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1417 if (e
->flags
& EDGE_ABNORMAL
)
1420 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1423 gphi
*phi
= gsi
.phi ();
1424 tree res
= PHI_RESULT (phi
);
1425 if (virtual_operand_p (res
))
1427 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1428 if (SSA_NAME_IS_DEFAULT_DEF (arg
)
1429 && (!SSA_NAME_VAR (arg
)
1430 || TREE_CODE (SSA_NAME_VAR (arg
)) != PARM_DECL
))
1433 int v1
= SSA_NAME_VERSION (res
);
1434 int v2
= SSA_NAME_VERSION (arg
);
1437 fprintf (debug
, "Abnormal coalesce: ");
1439 if (!attempt_coalesce (map
, graph
, v1
, v2
, debug
))
1440 fail_abnormal_edge_coalesce (v1
, v2
);
1445 /* Now process the items in the coalesce list. */
1447 while ((cost
= pop_best_coalesce (cl
, &x
, &y
)) != NO_BEST_COALESCE
)
1449 var1
= ssa_name (x
);
1450 var2
= ssa_name (y
);
1452 /* Assert the coalesces have the same base variable. */
1453 gcc_assert (gimple_can_coalesce_p (var1
, var2
));
1456 fprintf (debug
, "Coalesce list: ");
1457 attempt_coalesce (map
, graph
, x
, y
, debug
);
1462 /* Output partition map MAP with coalescing plan PART to file F. */
1465 dump_part_var_map (FILE *f
, partition part
, var_map map
)
1471 fprintf (f
, "\nCoalescible Partition map \n\n");
1473 for (x
= 0; x
< map
->num_partitions
; x
++)
1475 if (map
->view_to_partition
!= NULL
)
1476 p
= map
->view_to_partition
[x
];
1480 if (ssa_name (p
) == NULL_TREE
1481 || virtual_operand_p (ssa_name (p
)))
1485 for (y
= 1; y
< num_ssa_names
; y
++)
1487 tree var
= version_to_var (map
, y
);
1490 int q
= var_to_partition (map
, var
);
1491 p
= partition_find (part
, q
);
1492 gcc_assert (map
->partition_to_base_index
[q
]
1493 == map
->partition_to_base_index
[p
]);
1499 fprintf (f
, "Partition %d, base %d (", x
,
1500 map
->partition_to_base_index
[q
]);
1501 print_generic_expr (f
, partition_to_var (map
, q
), TDF_SLIM
);
1504 fprintf (f
, "%d ", y
);
1513 /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
1514 coalescing together, false otherwise.
1516 This must stay consistent with compute_samebase_partition_bases and
1517 compute_optimized_partition_bases. */
1520 gimple_can_coalesce_p (tree name1
, tree name2
)
1522 /* First check the SSA_NAME's associated DECL. Without
1523 optimization, we only want to coalesce if they have the same DECL
1524 or both have no associated DECL. */
1525 tree var1
= SSA_NAME_VAR (name1
);
1526 tree var2
= SSA_NAME_VAR (name2
);
1527 var1
= (var1
&& (!VAR_P (var1
) || !DECL_IGNORED_P (var1
))) ? var1
: NULL_TREE
;
1528 var2
= (var2
&& (!VAR_P (var2
) || !DECL_IGNORED_P (var2
))) ? var2
: NULL_TREE
;
1529 if (var1
!= var2
&& !flag_tree_coalesce_vars
)
1532 /* Now check the types. If the types are the same, then we should
1533 try to coalesce V1 and V2. */
1534 tree t1
= TREE_TYPE (name1
);
1535 tree t2
= TREE_TYPE (name2
);
1539 /* If the base variables are the same, we're good: none of the
1540 other tests below could possibly fail. */
1541 var1
= SSA_NAME_VAR (name1
);
1542 var2
= SSA_NAME_VAR (name2
);
1546 /* We don't want to coalesce two SSA names if one of the base
1547 variables is supposed to be a register while the other is
1548 supposed to be on the stack. Anonymous SSA names most often
1549 take registers, but when not optimizing, user variables
1550 should go on the stack, so coalescing them with the anonymous
1551 variable as the partition leader would end up assigning the
1552 user variable to a register. Don't do that! */
1553 bool reg1
= use_register_for_decl (name1
);
1554 bool reg2
= use_register_for_decl (name2
);
1558 /* Check that the promoted modes and unsignedness are the same.
1559 We don't want to coalesce if the promoted modes would be
1560 different, or if they would sign-extend differently. Only
1561 PARM_DECLs and RESULT_DECLs have different promotion rules,
1562 so skip the test if both are variables, or both are anonymous
1564 int unsigned1
, unsigned2
;
1565 return ((!var1
|| VAR_P (var1
)) && (!var2
|| VAR_P (var2
)))
1566 || ((promote_ssa_mode (name1
, &unsigned1
)
1567 == promote_ssa_mode (name2
, &unsigned2
))
1568 && unsigned1
== unsigned2
);
1571 /* If alignment requirements are different, we can't coalesce. */
1572 if (MINIMUM_ALIGNMENT (t1
,
1573 var1
? DECL_MODE (var1
) : TYPE_MODE (t1
),
1574 var1
? LOCAL_DECL_ALIGNMENT (var1
) : TYPE_ALIGN (t1
))
1575 != MINIMUM_ALIGNMENT (t2
,
1576 var2
? DECL_MODE (var2
) : TYPE_MODE (t2
),
1577 var2
? LOCAL_DECL_ALIGNMENT (var2
) : TYPE_ALIGN (t2
)))
1580 /* If the types are not the same, see whether they are compatible. This
1581 (for example) allows coalescing when the types are fundamentally the
1582 same, but just have different names.
1584 In the non-optimized case, we must first test TYPE_CANONICAL because
1585 we use it to compute the partition_to_base_index of the map. */
1586 if (flag_tree_coalesce_vars
)
1588 if (types_compatible_p (t1
, t2
))
1593 if (TYPE_CANONICAL (t1
)
1594 && TYPE_CANONICAL (t1
) == TYPE_CANONICAL (t2
)
1595 && types_compatible_p (t1
, t2
))
1602 /* Fill in MAP's partition_to_base_index, with one index for each
1603 partition of SSA names USED_IN_COPIES and related by CL coalesce
1604 possibilities. This must match gimple_can_coalesce_p in the
1608 compute_optimized_partition_bases (var_map map
, bitmap used_in_copies
,
1611 int parts
= num_var_partitions (map
);
1612 partition tentative
= partition_new (parts
);
1614 /* Partition the SSA versions so that, for each coalescible
1615 pair, both of its members are in the same partition in
1617 gcc_assert (!cl
->sorted
);
1618 coalesce_pair
*node
;
1619 coalesce_iterator_type ppi
;
1620 FOR_EACH_PARTITION_PAIR (node
, ppi
, cl
)
1622 tree v1
= ssa_name (node
->first_element
);
1623 int p1
= partition_find (tentative
, var_to_partition (map
, v1
));
1624 tree v2
= ssa_name (node
->second_element
);
1625 int p2
= partition_find (tentative
, var_to_partition (map
, v2
));
1630 partition_union (tentative
, p1
, p2
);
1633 /* We have to deal with cost one pairs too. */
1634 for (cost_one_pair
*co
= cl
->cost_one_list
; co
; co
= co
->next
)
1636 tree v1
= ssa_name (co
->first_element
);
1637 int p1
= partition_find (tentative
, var_to_partition (map
, v1
));
1638 tree v2
= ssa_name (co
->second_element
);
1639 int p2
= partition_find (tentative
, var_to_partition (map
, v2
));
1644 partition_union (tentative
, p1
, p2
);
1647 /* And also with abnormal edges. */
1652 for (i
= 0; map
->vec_bbs
.iterate (i
, &bb
); ++i
)
1654 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1655 if (e
->flags
& EDGE_ABNORMAL
)
1658 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1661 gphi
*phi
= gsi
.phi ();
1662 tree res
= PHI_RESULT (phi
);
1663 if (virtual_operand_p (res
))
1665 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1666 if (SSA_NAME_IS_DEFAULT_DEF (arg
)
1667 && (!SSA_NAME_VAR (arg
)
1668 || TREE_CODE (SSA_NAME_VAR (arg
)) != PARM_DECL
))
1671 int p1
= partition_find (tentative
, var_to_partition (map
, res
));
1672 int p2
= partition_find (tentative
, var_to_partition (map
, arg
));
1677 partition_union (tentative
, p1
, p2
);
1682 map
->partition_to_base_index
= XCNEWVEC (int, parts
);
1683 auto_vec
<unsigned int> index_map (parts
);
1685 index_map
.quick_grow (parts
);
1687 const unsigned no_part
= -1;
1688 unsigned count
= parts
;
1690 index_map
[--count
] = no_part
;
1692 /* Initialize MAP's mapping from partition to base index, using
1693 as base indices an enumeration of the TENTATIVE partitions in
1694 which each SSA version ended up, so that we compute conflicts
1695 between all SSA versions that ended up in the same potential
1696 coalesce partition. */
1698 EXECUTE_IF_SET_IN_BITMAP (used_in_copies
, 0, i
, bi
)
1700 int pidx
= var_to_partition (map
, ssa_name (i
));
1701 int base
= partition_find (tentative
, pidx
);
1702 if (index_map
[base
] != no_part
)
1704 index_map
[base
] = count
++;
1707 map
->num_basevars
= count
;
1709 EXECUTE_IF_SET_IN_BITMAP (used_in_copies
, 0, i
, bi
)
1711 int pidx
= var_to_partition (map
, ssa_name (i
));
1712 int base
= partition_find (tentative
, pidx
);
1713 gcc_assert (index_map
[base
] < count
);
1714 map
->partition_to_base_index
[pidx
] = index_map
[base
];
1717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1718 dump_part_var_map (dump_file
, tentative
, map
);
1720 partition_delete (tentative
);
1723 /* Hashtable helpers. */
1725 struct tree_int_map_hasher
: nofree_ptr_hash
<tree_int_map
>
1727 static inline hashval_t
hash (const tree_int_map
*);
1728 static inline bool equal (const tree_int_map
*, const tree_int_map
*);
1732 tree_int_map_hasher::hash (const tree_int_map
*v
)
1734 return tree_map_base_hash (v
);
1738 tree_int_map_hasher::equal (const tree_int_map
*v
, const tree_int_map
*c
)
1740 return tree_int_map_eq (v
, c
);
1743 /* This routine will initialize the basevar fields of MAP with base
1744 names. Partitions will share the same base if they have the same
1745 SSA_NAME_VAR, or, being anonymous variables, the same type. This
1746 must match gimple_can_coalesce_p in the non-optimized case. */
1749 compute_samebase_partition_bases (var_map map
)
1753 struct tree_int_map
*m
, *mapstorage
;
1755 num_part
= num_var_partitions (map
);
1756 hash_table
<tree_int_map_hasher
> tree_to_index (num_part
);
1757 /* We can have at most num_part entries in the hash tables, so it's
1758 enough to allocate so many map elements once, saving some malloc
1760 mapstorage
= m
= XNEWVEC (struct tree_int_map
, num_part
);
1762 /* If a base table already exists, clear it, otherwise create it. */
1763 free (map
->partition_to_base_index
);
1764 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
1766 /* Build the base variable list, and point partitions at their bases. */
1767 for (x
= 0; x
< num_part
; x
++)
1769 struct tree_int_map
**slot
;
1771 var
= partition_to_var (map
, x
);
1772 if (SSA_NAME_VAR (var
)
1773 && (!VAR_P (SSA_NAME_VAR (var
))
1774 || !DECL_IGNORED_P (SSA_NAME_VAR (var
))))
1775 m
->base
.from
= SSA_NAME_VAR (var
);
1777 /* This restricts what anonymous SSA names we can coalesce
1778 as it restricts the sets we compute conflicts for.
1779 Using TREE_TYPE to generate sets is the easiest as
1780 type equivalency also holds for SSA names with the same
1783 Check gimple_can_coalesce_p when changing this code. */
1784 m
->base
.from
= (TYPE_CANONICAL (TREE_TYPE (var
))
1785 ? TYPE_CANONICAL (TREE_TYPE (var
))
1787 /* If base variable hasn't been seen, set it up. */
1788 slot
= tree_to_index
.find_slot (m
, INSERT
);
1791 baseindex
= m
- mapstorage
;
1797 baseindex
= (*slot
)->to
;
1798 map
->partition_to_base_index
[x
] = baseindex
;
1801 map
->num_basevars
= m
- mapstorage
;
1806 /* Given an initial var_map MAP, coalesce variables and return a partition map
1807 with the resulting coalesce. Note that this function is called in either
1808 live range computation context or out-of-ssa context, indicated by MAP. */
1811 coalesce_ssa_name (var_map map
)
1813 tree_live_info_p liveinfo
;
1814 ssa_conflicts
*graph
;
1816 auto_bitmap used_in_copies
;
1818 cl
= create_coalesce_list_for_region (map
, used_in_copies
);
1819 if (map
->outofssa_p
)
1820 populate_coalesce_list_for_outofssa (cl
, used_in_copies
);
1822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1823 dump_var_map (dump_file
, map
);
1825 partition_view_bitmap (map
, used_in_copies
);
1827 if (flag_tree_coalesce_vars
)
1828 compute_optimized_partition_bases (map
, used_in_copies
, cl
);
1830 compute_samebase_partition_bases (map
);
1832 if (num_var_partitions (map
) < 1)
1834 delete_coalesce_list (cl
);
1838 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1839 dump_var_map (dump_file
, map
);
1841 liveinfo
= calculate_live_ranges (map
, false);
1843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1844 dump_live_info (dump_file
, liveinfo
, LIVEDUMP_ENTRY
);
1846 /* Build a conflict graph. */
1847 graph
= build_ssa_conflict_graph (liveinfo
);
1848 delete_tree_live_info (liveinfo
);
1849 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1850 ssa_conflicts_dump (dump_file
, graph
);
1852 sort_coalesce_list (cl
, graph
, map
);
1854 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1856 fprintf (dump_file
, "\nAfter sorting:\n");
1857 dump_coalesce_list (dump_file
, cl
);
1860 /* First, coalesce all live on entry variables to their base variable.
1861 This will ensure the first use is coming from the correct location. */
1863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1864 dump_var_map (dump_file
, map
);
1866 /* Now coalesce everything in the list. */
1867 coalesce_partitions (map
, graph
, cl
,
1868 ((dump_flags
& TDF_DETAILS
) ? dump_file
: NULL
));
1870 delete_coalesce_list (cl
);
1871 ssa_conflicts_delete (graph
);