1 /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 Copyright (C) 2004-2017 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
->frequency
, optimize_bb_for_size_p (bb
));
171 /* Return the cost of executing a copy instruction on edge E. */
174 coalesce_cost_edge (edge e
)
178 /* Inserting copy on critical edge costs more than inserting it elsewhere. */
179 if (EDGE_CRITICAL_P (e
))
181 if (e
->flags
& EDGE_ABNORMAL
)
182 return MUST_COALESCE_COST
;
183 if (e
->flags
& EDGE_EH
)
187 FOR_EACH_EDGE (e2
, ei
, e
->dest
->preds
)
190 /* Putting code on EH edge that leads to BB
191 with multiple predecestors imply splitting of
195 /* If there are multiple EH predecestors, we
196 also copy EH regions and produce separate
197 landing pad. This is expensive. */
198 if (e2
->flags
& EDGE_EH
)
206 return coalesce_cost (EDGE_FREQUENCY (e
),
207 optimize_edge_for_size_p (e
)) * mult
;
211 /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
212 2 elements via P1 and P2. 1 is returned by the function if there is a pair,
213 NO_BEST_COALESCE is returned if there aren't any. */
216 pop_cost_one_pair (coalesce_list
*cl
, int *p1
, int *p2
)
220 ptr
= cl
->cost_one_list
;
222 return NO_BEST_COALESCE
;
224 *p1
= ptr
->first_element
;
225 *p2
= ptr
->second_element
;
226 cl
->cost_one_list
= ptr
->next
;
233 /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
234 2 elements via P1 and P2. Their calculated cost is returned by the function.
235 NO_BEST_COALESCE is returned if the coalesce list is empty. */
238 pop_best_coalesce (coalesce_list
*cl
, int *p1
, int *p2
)
243 if (cl
->sorted
== NULL
)
244 return pop_cost_one_pair (cl
, p1
, p2
);
246 if (cl
->num_sorted
== 0)
247 return pop_cost_one_pair (cl
, p1
, p2
);
249 node
= cl
->sorted
[--(cl
->num_sorted
)];
250 *p1
= node
->first_element
;
251 *p2
= node
->second_element
;
259 /* Create a new empty coalesce list object and return it. */
261 static inline coalesce_list
*
262 create_coalesce_list (void)
265 unsigned size
= num_ssa_names
* 3;
270 list
= (coalesce_list
*) xmalloc (sizeof (struct coalesce_list
));
271 list
->list
= new coalesce_table_type (size
);
273 list
->num_sorted
= 0;
274 list
->cost_one_list
= NULL
;
279 /* Delete coalesce list CL. */
282 delete_coalesce_list (coalesce_list
*cl
)
284 gcc_assert (cl
->cost_one_list
== NULL
);
288 gcc_assert (cl
->num_sorted
== 0);
292 /* Return the number of unique coalesce pairs in CL. */
295 num_coalesce_pairs (coalesce_list
*cl
)
297 return cl
->list
->elements ();
300 /* Find a matching coalesce pair object in CL for the pair P1 and P2. If
301 one isn't found, return NULL if CREATE is false, otherwise create a new
302 coalesce pair object and return it. */
304 static coalesce_pair
*
305 find_coalesce_pair (coalesce_list
*cl
, int p1
, int p2
, bool create
)
307 struct coalesce_pair p
;
308 coalesce_pair
**slot
;
311 /* Normalize so that p1 is the smaller value. */
314 p
.first_element
= p2
;
315 p
.second_element
= p1
;
319 p
.first_element
= p1
;
320 p
.second_element
= p2
;
323 hash
= coalesce_pair_hasher::hash (&p
);
324 slot
= cl
->list
->find_slot_with_hash (&p
, hash
, create
? INSERT
: NO_INSERT
);
330 struct coalesce_pair
* pair
= XNEW (struct coalesce_pair
);
331 gcc_assert (cl
->sorted
== NULL
);
332 pair
->first_element
= p
.first_element
;
333 pair
->second_element
= p
.second_element
;
335 pair
->index
= num_coalesce_pairs (cl
);
336 pair
->conflict_count
= 0;
340 return (struct coalesce_pair
*) *slot
;
344 add_cost_one_coalesce (coalesce_list
*cl
, int p1
, int p2
)
348 pair
= XNEW (cost_one_pair
);
349 pair
->first_element
= p1
;
350 pair
->second_element
= p2
;
351 pair
->next
= cl
->cost_one_list
;
352 cl
->cost_one_list
= pair
;
356 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
359 add_coalesce (coalesce_list
*cl
, int p1
, int p2
, int value
)
363 gcc_assert (cl
->sorted
== NULL
);
367 node
= find_coalesce_pair (cl
, p1
, p2
, true);
369 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
370 if (node
->cost
< MUST_COALESCE_COST
- 1)
372 if (value
< MUST_COALESCE_COST
- 1)
379 /* Compute and record how many unique conflicts would exist for the
380 representative partition for each coalesce pair in CL.
382 CONFLICTS is the conflict graph and MAP is the current partition view. */
385 initialize_conflict_count (coalesce_pair
*p
,
386 ssa_conflicts
*conflicts
,
389 int p1
= var_to_partition (map
, ssa_name (p
->first_element
));
390 int p2
= var_to_partition (map
, ssa_name (p
->second_element
));
392 /* 4 cases. If both P1 and P2 have conflicts, then build their
393 union and count the members. Else handle the degenerate cases
394 in the obvious ways. */
395 if (conflicts
->conflicts
[p1
] && conflicts
->conflicts
[p2
])
396 p
->conflict_count
= bitmap_count_unique_bits (conflicts
->conflicts
[p1
],
397 conflicts
->conflicts
[p2
]);
398 else if (conflicts
->conflicts
[p1
])
399 p
->conflict_count
= bitmap_count_bits (conflicts
->conflicts
[p1
]);
400 else if (conflicts
->conflicts
[p2
])
401 p
->conflict_count
= bitmap_count_bits (conflicts
->conflicts
[p2
]);
403 p
->conflict_count
= 0;
407 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
410 compare_pairs (const void *p1
, const void *p2
)
412 coalesce_pair
*const *const pp1
= (coalesce_pair
*const *) p1
;
413 coalesce_pair
*const *const pp2
= (coalesce_pair
*const *) p2
;
416 result
= (* pp1
)->cost
- (* pp2
)->cost
;
417 /* We use the size of the resulting conflict set as the secondary sort key.
418 Given two equal costing coalesce pairs, we want to prefer the pair that
419 has the smaller conflict set. */
422 if (flag_expensive_optimizations
)
424 /* Lazily initialize the conflict counts as it's fairly expensive
426 if ((*pp2
)->conflict_count
== 0)
427 initialize_conflict_count (*pp2
, conflicts_
, map_
);
428 if ((*pp1
)->conflict_count
== 0)
429 initialize_conflict_count (*pp1
, conflicts_
, map_
);
431 result
= (*pp2
)->conflict_count
- (*pp1
)->conflict_count
;
434 /* And if everything else is equal, then sort based on which
435 coalesce pair was found first. */
437 result
= (*pp2
)->index
- (*pp1
)->index
;
443 /* Iterate over CL using ITER, returning values in PAIR. */
445 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
446 FOR_EACH_HASH_TABLE_ELEMENT (*(CL)->list, (PAIR), coalesce_pair_p, (ITER))
449 /* Prepare CL for removal of preferred pairs. When finished they are sorted
450 in order from most important coalesce to least important. */
453 sort_coalesce_list (coalesce_list
*cl
, ssa_conflicts
*conflicts
, var_map map
)
457 coalesce_iterator_type ppi
;
459 gcc_assert (cl
->sorted
== NULL
);
461 num
= num_coalesce_pairs (cl
);
462 cl
->num_sorted
= num
;
466 /* Allocate a vector for the pair pointers. */
467 cl
->sorted
= XNEWVEC (coalesce_pair
*, num
);
469 /* Populate the vector with pointers to the pairs. */
471 FOR_EACH_PARTITION_PAIR (p
, ppi
, cl
)
473 gcc_assert (x
== num
);
475 /* Already sorted. */
479 /* We don't want to depend on qsort_r, so we have to stuff away
480 additional data into globals so it can be referenced in
482 conflicts_
= conflicts
;
484 qsort (cl
->sorted
, num
, sizeof (coalesce_pair
*), compare_pairs
);
490 /* Send debug info for coalesce list CL to file F. */
493 dump_coalesce_list (FILE *f
, coalesce_list
*cl
)
496 coalesce_iterator_type ppi
;
501 if (cl
->sorted
== NULL
)
503 fprintf (f
, "Coalesce List:\n");
504 FOR_EACH_PARTITION_PAIR (node
, ppi
, cl
)
506 tree var1
= ssa_name (node
->first_element
);
507 tree var2
= ssa_name (node
->second_element
);
508 print_generic_expr (f
, var1
, TDF_SLIM
);
509 fprintf (f
, " <-> ");
510 print_generic_expr (f
, var2
, TDF_SLIM
);
511 fprintf (f
, " (%1d, %1d), ", node
->cost
, node
->conflict_count
);
517 fprintf (f
, "Sorted Coalesce list:\n");
518 for (x
= cl
->num_sorted
- 1 ; x
>=0; x
--)
520 node
= cl
->sorted
[x
];
521 fprintf (f
, "(%d, %d) ", node
->cost
, node
->conflict_count
);
522 var
= ssa_name (node
->first_element
);
523 print_generic_expr (f
, var
, TDF_SLIM
);
524 fprintf (f
, " <-> ");
525 var
= ssa_name (node
->second_element
);
526 print_generic_expr (f
, var
, TDF_SLIM
);
533 /* Return an empty new conflict graph for SIZE elements. */
535 static inline ssa_conflicts
*
536 ssa_conflicts_new (unsigned size
)
540 ptr
= XNEW (ssa_conflicts
);
541 bitmap_obstack_initialize (&ptr
->obstack
);
542 ptr
->conflicts
.create (size
);
543 ptr
->conflicts
.safe_grow_cleared (size
);
548 /* Free storage for conflict graph PTR. */
551 ssa_conflicts_delete (ssa_conflicts
*ptr
)
553 bitmap_obstack_release (&ptr
->obstack
);
554 ptr
->conflicts
.release ();
559 /* Test if elements X and Y conflict in graph PTR. */
562 ssa_conflicts_test_p (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
564 bitmap bx
= ptr
->conflicts
[x
];
565 bitmap by
= ptr
->conflicts
[y
];
567 gcc_checking_assert (x
!= y
);
570 /* Avoid the lookup if Y has no conflicts. */
571 return by
? bitmap_bit_p (bx
, y
) : false;
577 /* Add a conflict with Y to the bitmap for X in graph PTR. */
580 ssa_conflicts_add_one (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
582 bitmap bx
= ptr
->conflicts
[x
];
583 /* If there are no conflicts yet, allocate the bitmap and set bit. */
585 bx
= ptr
->conflicts
[x
] = BITMAP_ALLOC (&ptr
->obstack
);
586 bitmap_set_bit (bx
, y
);
590 /* Add conflicts between X and Y in graph PTR. */
593 ssa_conflicts_add (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
595 gcc_checking_assert (x
!= y
);
596 ssa_conflicts_add_one (ptr
, x
, y
);
597 ssa_conflicts_add_one (ptr
, y
, x
);
601 /* Merge all Y's conflict into X in graph PTR. */
604 ssa_conflicts_merge (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
608 bitmap bx
= ptr
->conflicts
[x
];
609 bitmap by
= ptr
->conflicts
[y
];
611 gcc_checking_assert (x
!= y
);
615 /* Add a conflict between X and every one Y has. If the bitmap doesn't
616 exist, then it has already been coalesced, and we don't need to add a
618 EXECUTE_IF_SET_IN_BITMAP (by
, 0, z
, bi
)
620 bitmap bz
= ptr
->conflicts
[z
];
622 bitmap_set_bit (bz
, x
);
627 /* If X has conflicts, add Y's to X. */
628 bitmap_ior_into (bx
, by
);
630 ptr
->conflicts
[y
] = NULL
;
634 /* If X has no conflicts, simply use Y's. */
635 ptr
->conflicts
[x
] = by
;
636 ptr
->conflicts
[y
] = NULL
;
641 /* Dump a conflicts graph. */
644 ssa_conflicts_dump (FILE *file
, ssa_conflicts
*ptr
)
649 fprintf (file
, "\nConflict graph:\n");
651 FOR_EACH_VEC_ELT (ptr
->conflicts
, x
, b
)
654 fprintf (file
, "%d: ", x
);
655 dump_bitmap (file
, b
);
660 /* This structure is used to efficiently record the current status of live
661 SSA_NAMES when building a conflict graph.
662 LIVE_BASE_VAR has a bit set for each base variable which has at least one
664 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
665 index, and is used to track what partitions of each base variable are
666 live. This makes it easy to add conflicts between just live partitions
667 with the same base variable.
668 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
669 marked as being live. This delays clearing of these bitmaps until
670 they are actually needed again. */
674 bitmap_obstack obstack
; /* A place to allocate our bitmaps. */
675 bitmap live_base_var
; /* Indicates if a basevar is live. */
676 bitmap
*live_base_partitions
; /* Live partitions for each basevar. */
677 var_map map
; /* Var_map being used for partition mapping. */
681 /* This routine will create a new live track structure based on the partitions
685 new_live_track (var_map map
)
690 /* Make sure there is a partition view in place. */
691 gcc_assert (map
->partition_to_base_index
!= NULL
);
693 ptr
= (live_track
*) xmalloc (sizeof (live_track
));
695 lim
= num_basevars (map
);
696 bitmap_obstack_initialize (&ptr
->obstack
);
697 ptr
->live_base_partitions
= (bitmap
*) xmalloc (sizeof (bitmap
*) * lim
);
698 ptr
->live_base_var
= BITMAP_ALLOC (&ptr
->obstack
);
699 for (x
= 0; x
< lim
; x
++)
700 ptr
->live_base_partitions
[x
] = BITMAP_ALLOC (&ptr
->obstack
);
705 /* This routine will free the memory associated with PTR. */
708 delete_live_track (live_track
*ptr
)
710 bitmap_obstack_release (&ptr
->obstack
);
711 free (ptr
->live_base_partitions
);
716 /* This function will remove PARTITION from the live list in PTR. */
719 live_track_remove_partition (live_track
*ptr
, int partition
)
723 root
= basevar_index (ptr
->map
, partition
);
724 bitmap_clear_bit (ptr
->live_base_partitions
[root
], partition
);
725 /* If the element list is empty, make the base variable not live either. */
726 if (bitmap_empty_p (ptr
->live_base_partitions
[root
]))
727 bitmap_clear_bit (ptr
->live_base_var
, root
);
731 /* This function will adds PARTITION to the live list in PTR. */
734 live_track_add_partition (live_track
*ptr
, int partition
)
738 root
= basevar_index (ptr
->map
, partition
);
739 /* If this base var wasn't live before, it is now. Clear the element list
740 since it was delayed until needed. */
741 if (bitmap_set_bit (ptr
->live_base_var
, root
))
742 bitmap_clear (ptr
->live_base_partitions
[root
]);
743 bitmap_set_bit (ptr
->live_base_partitions
[root
], partition
);
748 /* Clear the live bit for VAR in PTR. */
751 live_track_clear_var (live_track
*ptr
, tree var
)
755 p
= var_to_partition (ptr
->map
, var
);
756 if (p
!= NO_PARTITION
)
757 live_track_remove_partition (ptr
, p
);
761 /* Return TRUE if VAR is live in PTR. */
764 live_track_live_p (live_track
*ptr
, tree var
)
768 p
= var_to_partition (ptr
->map
, var
);
769 if (p
!= NO_PARTITION
)
771 root
= basevar_index (ptr
->map
, p
);
772 if (bitmap_bit_p (ptr
->live_base_var
, root
))
773 return bitmap_bit_p (ptr
->live_base_partitions
[root
], p
);
779 /* This routine will add USE to PTR. USE will be marked as live in both the
780 ssa live map and the live bitmap for the root of USE. */
783 live_track_process_use (live_track
*ptr
, tree use
)
787 p
= var_to_partition (ptr
->map
, use
);
788 if (p
== NO_PARTITION
)
791 /* Mark as live in the appropriate live list. */
792 live_track_add_partition (ptr
, p
);
796 /* This routine will process a DEF in PTR. DEF will be removed from the live
797 lists, and if there are any other live partitions with the same base
798 variable, conflicts will be added to GRAPH. */
801 live_track_process_def (live_track
*ptr
, tree def
, ssa_conflicts
*graph
)
808 p
= var_to_partition (ptr
->map
, def
);
809 if (p
== NO_PARTITION
)
812 /* Clear the liveness bit. */
813 live_track_remove_partition (ptr
, p
);
815 /* If the bitmap isn't empty now, conflicts need to be added. */
816 root
= basevar_index (ptr
->map
, p
);
817 if (bitmap_bit_p (ptr
->live_base_var
, root
))
819 b
= ptr
->live_base_partitions
[root
];
820 EXECUTE_IF_SET_IN_BITMAP (b
, 0, x
, bi
)
821 ssa_conflicts_add (graph
, p
, x
);
826 /* Initialize PTR with the partitions set in INIT. */
829 live_track_init (live_track
*ptr
, bitmap init
)
834 /* Mark all live on exit partitions. */
835 EXECUTE_IF_SET_IN_BITMAP (init
, 0, p
, bi
)
836 live_track_add_partition (ptr
, p
);
840 /* This routine will clear all live partitions in PTR. */
843 live_track_clear_base_vars (live_track
*ptr
)
845 /* Simply clear the live base list. Anything marked as live in the element
846 lists will be cleared later if/when the base variable ever comes alive
848 bitmap_clear (ptr
->live_base_var
);
852 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
853 partition view of the var_map liveinfo is based on get entries in the
854 conflict graph. Only conflicts between ssa_name partitions with the same
855 base variable are added. */
857 static ssa_conflicts
*
858 build_ssa_conflict_graph (tree_live_info_p liveinfo
)
860 ssa_conflicts
*graph
;
867 /* If inter-variable coalescing is enabled, we may attempt to
868 coalesce variables from different base variables, including
869 different parameters, so we have to make sure default defs live
870 at the entry block conflict with each other. */
871 if (flag_tree_coalesce_vars
)
872 entry
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
876 map
= live_var_map (liveinfo
);
877 graph
= ssa_conflicts_new (num_var_partitions (map
));
879 live
= new_live_track (map
);
881 FOR_EACH_BB_FN (bb
, cfun
)
883 /* Start with live on exit temporaries. */
884 live_track_init (live
, live_on_exit (liveinfo
, bb
));
886 for (gimple_stmt_iterator gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);
890 gimple
*stmt
= gsi_stmt (gsi
);
892 /* A copy between 2 partitions does not introduce an interference
893 by itself. If they did, you would never be able to coalesce
894 two things which are copied. If the two variables really do
895 conflict, they will conflict elsewhere in the program.
897 This is handled by simply removing the SRC of the copy from the
898 live list, and processing the stmt normally. */
899 if (is_gimple_assign (stmt
))
901 tree lhs
= gimple_assign_lhs (stmt
);
902 tree rhs1
= gimple_assign_rhs1 (stmt
);
903 if (gimple_assign_copy_p (stmt
)
904 && TREE_CODE (lhs
) == SSA_NAME
905 && TREE_CODE (rhs1
) == SSA_NAME
)
906 live_track_clear_var (live
, rhs1
);
908 else if (is_gimple_debug (stmt
))
911 /* For stmts with more than one SSA_NAME definition pretend all the
912 SSA_NAME outputs but the first one are live at this point, so
913 that conflicts are added in between all those even when they are
914 actually not really live after the asm, because expansion might
915 copy those into pseudos after the asm and if multiple outputs
916 share the same partition, it might overwrite those that should
918 asm volatile (".." : "=r" (a) : "=r" (b) : "0" (a), "1" (a));
922 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_DEF
)
926 live_track_process_use (live
, var
);
928 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_DEF
)
929 live_track_process_def (live
, var
, graph
);
931 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_USE
)
932 live_track_process_use (live
, var
);
935 /* If result of a PHI is unused, looping over the statements will not
936 record any conflicts since the def was never live. Since the PHI node
937 is going to be translated out of SSA form, it will insert a copy.
938 There must be a conflict recorded between the result of the PHI and
939 any variables that are live. Otherwise the out-of-ssa translation
940 may create incorrect code. */
941 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
944 gphi
*phi
= gsi
.phi ();
945 tree result
= PHI_RESULT (phi
);
946 if (live_track_live_p (live
, result
))
947 live_track_process_def (live
, result
, graph
);
950 /* Pretend there are defs for params' default defs at the start
951 of the (post-)entry block. This will prevent PARM_DECLs from
952 coalescing into the same partition. Although RESULT_DECLs'
953 default defs don't have a useful initial value, we have to
954 prevent them from coalescing with PARM_DECLs' default defs
955 too, otherwise assign_parms would attempt to assign different
956 RTL to the same partition. */
962 FOR_EACH_SSA_NAME (i
, var
, cfun
)
964 if (!SSA_NAME_IS_DEFAULT_DEF (var
)
965 || !SSA_NAME_VAR (var
)
966 || VAR_P (SSA_NAME_VAR (var
)))
969 live_track_process_def (live
, var
, graph
);
970 /* Process a use too, so that it remains live and
971 conflicts with other parms' default defs, even unused
973 live_track_process_use (live
, var
);
977 live_track_clear_base_vars (live
);
980 delete_live_track (live
);
985 /* Shortcut routine to print messages to file F of the form:
986 "STR1 EXPR1 STR2 EXPR2 STR3." */
989 print_exprs (FILE *f
, const char *str1
, tree expr1
, const char *str2
,
990 tree expr2
, const char *str3
)
992 fprintf (f
, "%s", str1
);
993 print_generic_expr (f
, expr1
, TDF_SLIM
);
994 fprintf (f
, "%s", str2
);
995 print_generic_expr (f
, expr2
, TDF_SLIM
);
996 fprintf (f
, "%s", str3
);
1000 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
1003 fail_abnormal_edge_coalesce (int x
, int y
)
1005 fprintf (stderr
, "\nUnable to coalesce ssa_names %d and %d",x
, y
);
1006 fprintf (stderr
, " which are marked as MUST COALESCE.\n");
1007 print_generic_expr (stderr
, ssa_name (x
), TDF_SLIM
);
1008 fprintf (stderr
, " and ");
1009 print_generic_stmt (stderr
, ssa_name (y
), TDF_SLIM
);
1011 internal_error ("SSA corruption");
1014 /* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
1015 assign_parms may ask for a default partition. */
1018 for_all_parms (void (*callback
)(tree var
, void *arg
), void *arg
)
1020 for (tree var
= DECL_ARGUMENTS (current_function_decl
); var
;
1021 var
= DECL_CHAIN (var
))
1022 callback (var
, arg
);
1023 if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
1024 callback (DECL_RESULT (current_function_decl
), arg
);
1025 if (cfun
->static_chain_decl
)
1026 callback (cfun
->static_chain_decl
, arg
);
1029 /* Create a default def for VAR. */
1032 create_default_def (tree var
, void *arg ATTRIBUTE_UNUSED
)
1034 if (!is_gimple_reg (var
))
1037 tree ssa
= get_or_create_ssa_default_def (cfun
, var
);
1041 /* Register VAR's default def in MAP. */
1044 register_default_def (tree var
, void *arg ATTRIBUTE_UNUSED
)
1046 if (!is_gimple_reg (var
))
1049 tree ssa
= ssa_default_def (cfun
, var
);
1053 /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
1054 and the DECL's default def is unused (i.e., it was introduced by
1055 create_default_def), mark VAR and the default def for
1059 coalesce_with_default (tree var
, coalesce_list
*cl
, bitmap used_in_copy
)
1061 if (SSA_NAME_IS_DEFAULT_DEF (var
)
1062 || !SSA_NAME_VAR (var
)
1063 || VAR_P (SSA_NAME_VAR (var
)))
1066 tree ssa
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1067 if (!has_zero_uses (ssa
))
1070 add_cost_one_coalesce (cl
, SSA_NAME_VERSION (ssa
), SSA_NAME_VERSION (var
));
1071 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1072 /* Default defs will have their used_in_copy bits set at the end of
1073 create_outofssa_var_map. */
1076 /* This function creates a var_map for the current function as well as creating
1077 a coalesce list for use later in the out of ssa process. */
1080 create_outofssa_var_map (coalesce_list
*cl
, bitmap used_in_copy
)
1082 gimple_stmt_iterator gsi
;
1091 for_all_parms (create_default_def
, NULL
);
1093 map
= init_var_map (num_ssa_names
);
1095 for_all_parms (register_default_def
, NULL
);
1097 FOR_EACH_BB_FN (bb
, cfun
)
1101 for (gphi_iterator gpi
= gsi_start_phis (bb
);
1105 gphi
*phi
= gpi
.phi ();
1109 bool saw_copy
= false;
1111 res
= gimple_phi_result (phi
);
1112 ver
= SSA_NAME_VERSION (res
);
1114 /* Register ssa_names and coalesces between the args and the result
1116 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1118 edge e
= gimple_phi_arg_edge (phi
, i
);
1119 arg
= PHI_ARG_DEF (phi
, i
);
1120 if (TREE_CODE (arg
) != SSA_NAME
)
1123 if (gimple_can_coalesce_p (arg
, res
)
1124 || (e
->flags
& EDGE_ABNORMAL
))
1127 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (arg
));
1128 if ((e
->flags
& EDGE_ABNORMAL
) == 0)
1130 int cost
= coalesce_cost_edge (e
);
1131 if (cost
== 1 && has_single_use (arg
))
1132 add_cost_one_coalesce (cl
, ver
, SSA_NAME_VERSION (arg
));
1134 add_coalesce (cl
, ver
, SSA_NAME_VERSION (arg
), cost
);
1139 bitmap_set_bit (used_in_copy
, ver
);
1142 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1144 stmt
= gsi_stmt (gsi
);
1146 if (is_gimple_debug (stmt
))
1149 /* Check for copy coalesces. */
1150 switch (gimple_code (stmt
))
1154 tree lhs
= gimple_assign_lhs (stmt
);
1155 tree rhs1
= gimple_assign_rhs1 (stmt
);
1156 if (gimple_assign_ssa_name_copy_p (stmt
)
1157 && gimple_can_coalesce_p (lhs
, rhs1
))
1159 v1
= SSA_NAME_VERSION (lhs
);
1160 v2
= SSA_NAME_VERSION (rhs1
);
1161 cost
= coalesce_cost_bb (bb
);
1162 add_coalesce (cl
, v1
, v2
, cost
);
1163 bitmap_set_bit (used_in_copy
, v1
);
1164 bitmap_set_bit (used_in_copy
, v2
);
1171 tree res
= DECL_RESULT (current_function_decl
);
1172 if (VOID_TYPE_P (TREE_TYPE (res
))
1173 || !is_gimple_reg (res
))
1175 tree rhs1
= gimple_return_retval (as_a
<greturn
*> (stmt
));
1178 tree lhs
= ssa_default_def (cfun
, res
);
1180 if (TREE_CODE (rhs1
) == SSA_NAME
1181 && gimple_can_coalesce_p (lhs
, rhs1
))
1183 v1
= SSA_NAME_VERSION (lhs
);
1184 v2
= SSA_NAME_VERSION (rhs1
);
1185 cost
= coalesce_cost_bb (bb
);
1186 add_coalesce (cl
, v1
, v2
, cost
);
1187 bitmap_set_bit (used_in_copy
, v1
);
1188 bitmap_set_bit (used_in_copy
, v2
);
1195 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
1196 unsigned long noutputs
, i
;
1197 unsigned long ninputs
;
1198 tree
*outputs
, link
;
1199 noutputs
= gimple_asm_noutputs (asm_stmt
);
1200 ninputs
= gimple_asm_ninputs (asm_stmt
);
1201 outputs
= (tree
*) alloca (noutputs
* sizeof (tree
));
1202 for (i
= 0; i
< noutputs
; ++i
)
1204 link
= gimple_asm_output_op (asm_stmt
, i
);
1205 outputs
[i
] = TREE_VALUE (link
);
1208 for (i
= 0; i
< ninputs
; ++i
)
1210 const char *constraint
;
1213 unsigned long match
;
1215 link
= gimple_asm_input_op (asm_stmt
, i
);
1217 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
1218 input
= TREE_VALUE (link
);
1220 if (TREE_CODE (input
) != SSA_NAME
)
1223 match
= strtoul (constraint
, &end
, 10);
1224 if (match
>= noutputs
|| end
== constraint
)
1227 if (TREE_CODE (outputs
[match
]) != SSA_NAME
)
1230 v1
= SSA_NAME_VERSION (outputs
[match
]);
1231 v2
= SSA_NAME_VERSION (input
);
1233 if (gimple_can_coalesce_p (outputs
[match
], input
))
1235 cost
= coalesce_cost (REG_BR_PROB_BASE
,
1236 optimize_bb_for_size_p (bb
));
1237 add_coalesce (cl
, v1
, v2
, cost
);
1238 bitmap_set_bit (used_in_copy
, v1
);
1239 bitmap_set_bit (used_in_copy
, v2
);
1251 /* Now process result decls and live on entry variables for entry into
1252 the coalesce list. */
1254 FOR_EACH_SSA_NAME (i
, var
, cfun
)
1256 if (!virtual_operand_p (var
))
1258 coalesce_with_default (var
, cl
, used_in_copy
);
1260 /* Add coalesces between all the result decls. */
1261 if (SSA_NAME_VAR (var
)
1262 && TREE_CODE (SSA_NAME_VAR (var
)) == RESULT_DECL
)
1264 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1265 if (first
== NULL_TREE
)
1269 gcc_assert (gimple_can_coalesce_p (var
, first
));
1270 v1
= SSA_NAME_VERSION (first
);
1271 v2
= SSA_NAME_VERSION (var
);
1272 cost
= coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun
));
1273 add_coalesce (cl
, v1
, v2
, cost
);
1276 /* Mark any default_def variables as being in the coalesce list
1277 since they will have to be coalesced with the base variable. If
1278 not marked as present, they won't be in the coalesce view. */
1279 if (SSA_NAME_IS_DEFAULT_DEF (var
)
1280 && (!has_zero_uses (var
)
1281 || (SSA_NAME_VAR (var
)
1282 && !VAR_P (SSA_NAME_VAR (var
)))))
1283 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1291 /* Attempt to coalesce ssa versions X and Y together using the partition
1292 mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1293 DEBUG, if it is nun-NULL. */
1296 attempt_coalesce (var_map map
, ssa_conflicts
*graph
, int x
, int y
,
1303 p1
= var_to_partition (map
, ssa_name (x
));
1304 p2
= var_to_partition (map
, ssa_name (y
));
1308 fprintf (debug
, "(%d)", x
);
1309 print_generic_expr (debug
, partition_to_var (map
, p1
), TDF_SLIM
);
1310 fprintf (debug
, " & (%d)", y
);
1311 print_generic_expr (debug
, partition_to_var (map
, p2
), TDF_SLIM
);
1317 fprintf (debug
, ": Already Coalesced.\n");
1322 fprintf (debug
, " [map: %d, %d] ", p1
, p2
);
1325 if (!ssa_conflicts_test_p (graph
, p1
, p2
))
1327 var1
= partition_to_var (map
, p1
);
1328 var2
= partition_to_var (map
, p2
);
1330 z
= var_union (map
, var1
, var2
);
1331 if (z
== NO_PARTITION
)
1334 fprintf (debug
, ": Unable to perform partition union.\n");
1338 /* z is the new combined partition. Remove the other partition from
1339 the list, and merge the conflicts. */
1341 ssa_conflicts_merge (graph
, p1
, p2
);
1343 ssa_conflicts_merge (graph
, p2
, p1
);
1346 fprintf (debug
, ": Success -> %d\n", z
);
1352 fprintf (debug
, ": Fail due to conflict\n");
1358 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1359 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1362 coalesce_partitions (var_map map
, ssa_conflicts
*graph
, coalesce_list
*cl
,
1372 /* First, coalesce all the copies across abnormal edges. These are not placed
1373 in the coalesce list because they do not need to be sorted, and simply
1374 consume extra memory/compilation time in large programs. */
1376 FOR_EACH_BB_FN (bb
, cfun
)
1378 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1379 if (e
->flags
& EDGE_ABNORMAL
)
1382 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1385 gphi
*phi
= gsi
.phi ();
1386 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1387 if (SSA_NAME_IS_DEFAULT_DEF (arg
)
1388 && (!SSA_NAME_VAR (arg
)
1389 || TREE_CODE (SSA_NAME_VAR (arg
)) != PARM_DECL
))
1392 tree res
= PHI_RESULT (phi
);
1393 int v1
= SSA_NAME_VERSION (res
);
1394 int v2
= SSA_NAME_VERSION (arg
);
1397 fprintf (debug
, "Abnormal coalesce: ");
1399 if (!attempt_coalesce (map
, graph
, v1
, v2
, debug
))
1400 fail_abnormal_edge_coalesce (v1
, v2
);
1405 /* Now process the items in the coalesce list. */
1407 while ((cost
= pop_best_coalesce (cl
, &x
, &y
)) != NO_BEST_COALESCE
)
1409 var1
= ssa_name (x
);
1410 var2
= ssa_name (y
);
1412 /* Assert the coalesces have the same base variable. */
1413 gcc_assert (gimple_can_coalesce_p (var1
, var2
));
1416 fprintf (debug
, "Coalesce list: ");
1417 attempt_coalesce (map
, graph
, x
, y
, debug
);
1422 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1424 struct ssa_name_var_hash
: nofree_ptr_hash
<tree_node
>
1426 static inline hashval_t
hash (const tree_node
*);
1427 static inline int equal (const tree_node
*, const tree_node
*);
1431 ssa_name_var_hash::hash (const_tree n
)
1433 return DECL_UID (SSA_NAME_VAR (n
));
1437 ssa_name_var_hash::equal (const tree_node
*n1
, const tree_node
*n2
)
1439 return SSA_NAME_VAR (n1
) == SSA_NAME_VAR (n2
);
1443 /* Output partition map MAP with coalescing plan PART to file F. */
1446 dump_part_var_map (FILE *f
, partition part
, var_map map
)
1452 fprintf (f
, "\nCoalescible Partition map \n\n");
1454 for (x
= 0; x
< map
->num_partitions
; x
++)
1456 if (map
->view_to_partition
!= NULL
)
1457 p
= map
->view_to_partition
[x
];
1461 if (ssa_name (p
) == NULL_TREE
1462 || virtual_operand_p (ssa_name (p
)))
1466 for (y
= 1; y
< num_ssa_names
; y
++)
1468 tree var
= version_to_var (map
, y
);
1471 int q
= var_to_partition (map
, var
);
1472 p
= partition_find (part
, q
);
1473 gcc_assert (map
->partition_to_base_index
[q
]
1474 == map
->partition_to_base_index
[p
]);
1480 fprintf (f
, "Partition %d, base %d (", x
,
1481 map
->partition_to_base_index
[q
]);
1482 print_generic_expr (f
, partition_to_var (map
, q
), TDF_SLIM
);
1485 fprintf (f
, "%d ", y
);
1494 /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
1495 coalescing together, false otherwise.
1497 This must stay consistent with compute_samebase_partition_bases and
1498 compute_optimized_partition_bases. */
1501 gimple_can_coalesce_p (tree name1
, tree name2
)
1503 /* First check the SSA_NAME's associated DECL. Without
1504 optimization, we only want to coalesce if they have the same DECL
1505 or both have no associated DECL. */
1506 tree var1
= SSA_NAME_VAR (name1
);
1507 tree var2
= SSA_NAME_VAR (name2
);
1508 var1
= (var1
&& (!VAR_P (var1
) || !DECL_IGNORED_P (var1
))) ? var1
: NULL_TREE
;
1509 var2
= (var2
&& (!VAR_P (var2
) || !DECL_IGNORED_P (var2
))) ? var2
: NULL_TREE
;
1510 if (var1
!= var2
&& !flag_tree_coalesce_vars
)
1513 /* Now check the types. If the types are the same, then we should
1514 try to coalesce V1 and V2. */
1515 tree t1
= TREE_TYPE (name1
);
1516 tree t2
= TREE_TYPE (name2
);
1520 /* If the base variables are the same, we're good: none of the
1521 other tests below could possibly fail. */
1522 var1
= SSA_NAME_VAR (name1
);
1523 var2
= SSA_NAME_VAR (name2
);
1527 /* We don't want to coalesce two SSA names if one of the base
1528 variables is supposed to be a register while the other is
1529 supposed to be on the stack. Anonymous SSA names most often
1530 take registers, but when not optimizing, user variables
1531 should go on the stack, so coalescing them with the anonymous
1532 variable as the partition leader would end up assigning the
1533 user variable to a register. Don't do that! */
1534 bool reg1
= use_register_for_decl (name1
);
1535 bool reg2
= use_register_for_decl (name2
);
1539 /* Check that the promoted modes and unsignedness are the same.
1540 We don't want to coalesce if the promoted modes would be
1541 different, or if they would sign-extend differently. Only
1542 PARM_DECLs and RESULT_DECLs have different promotion rules,
1543 so skip the test if both are variables, or both are anonymous
1545 int unsigned1
, unsigned2
;
1546 return ((!var1
|| VAR_P (var1
)) && (!var2
|| VAR_P (var2
)))
1547 || ((promote_ssa_mode (name1
, &unsigned1
)
1548 == promote_ssa_mode (name2
, &unsigned2
))
1549 && unsigned1
== unsigned2
);
1552 /* If alignment requirements are different, we can't coalesce. */
1553 if (MINIMUM_ALIGNMENT (t1
,
1554 var1
? DECL_MODE (var1
) : TYPE_MODE (t1
),
1555 var1
? LOCAL_DECL_ALIGNMENT (var1
) : TYPE_ALIGN (t1
))
1556 != MINIMUM_ALIGNMENT (t2
,
1557 var2
? DECL_MODE (var2
) : TYPE_MODE (t2
),
1558 var2
? LOCAL_DECL_ALIGNMENT (var2
) : TYPE_ALIGN (t2
)))
1561 /* If the types are not the same, see whether they are compatible. This
1562 (for example) allows coalescing when the types are fundamentally the
1563 same, but just have different names.
1565 In the non-optimized case, we must first test TYPE_CANONICAL because
1566 we use it to compute the partition_to_base_index of the map. */
1567 if (flag_tree_coalesce_vars
)
1569 if (types_compatible_p (t1
, t2
))
1574 if (TYPE_CANONICAL (t1
)
1575 && TYPE_CANONICAL (t1
) == TYPE_CANONICAL (t2
)
1576 && types_compatible_p (t1
, t2
))
1583 /* Fill in MAP's partition_to_base_index, with one index for each
1584 partition of SSA names USED_IN_COPIES and related by CL coalesce
1585 possibilities. This must match gimple_can_coalesce_p in the
1589 compute_optimized_partition_bases (var_map map
, bitmap used_in_copies
,
1592 int parts
= num_var_partitions (map
);
1593 partition tentative
= partition_new (parts
);
1595 /* Partition the SSA versions so that, for each coalescible
1596 pair, both of its members are in the same partition in
1598 gcc_assert (!cl
->sorted
);
1599 coalesce_pair
*node
;
1600 coalesce_iterator_type ppi
;
1601 FOR_EACH_PARTITION_PAIR (node
, ppi
, cl
)
1603 tree v1
= ssa_name (node
->first_element
);
1604 int p1
= partition_find (tentative
, var_to_partition (map
, v1
));
1605 tree v2
= ssa_name (node
->second_element
);
1606 int p2
= partition_find (tentative
, var_to_partition (map
, v2
));
1611 partition_union (tentative
, p1
, p2
);
1614 /* We have to deal with cost one pairs too. */
1615 for (cost_one_pair
*co
= cl
->cost_one_list
; co
; co
= co
->next
)
1617 tree v1
= ssa_name (co
->first_element
);
1618 int p1
= partition_find (tentative
, var_to_partition (map
, v1
));
1619 tree v2
= ssa_name (co
->second_element
);
1620 int p2
= partition_find (tentative
, var_to_partition (map
, v2
));
1625 partition_union (tentative
, p1
, p2
);
1628 /* And also with abnormal edges. */
1632 FOR_EACH_BB_FN (bb
, cfun
)
1634 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1635 if (e
->flags
& EDGE_ABNORMAL
)
1638 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1641 gphi
*phi
= gsi
.phi ();
1642 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1643 if (SSA_NAME_IS_DEFAULT_DEF (arg
)
1644 && (!SSA_NAME_VAR (arg
)
1645 || TREE_CODE (SSA_NAME_VAR (arg
)) != PARM_DECL
))
1648 tree res
= PHI_RESULT (phi
);
1650 int p1
= partition_find (tentative
, var_to_partition (map
, res
));
1651 int p2
= partition_find (tentative
, var_to_partition (map
, arg
));
1656 partition_union (tentative
, p1
, p2
);
1661 map
->partition_to_base_index
= XCNEWVEC (int, parts
);
1662 auto_vec
<unsigned int> index_map (parts
);
1664 index_map
.quick_grow (parts
);
1666 const unsigned no_part
= -1;
1667 unsigned count
= parts
;
1669 index_map
[--count
] = no_part
;
1671 /* Initialize MAP's mapping from partition to base index, using
1672 as base indices an enumeration of the TENTATIVE partitions in
1673 which each SSA version ended up, so that we compute conflicts
1674 between all SSA versions that ended up in the same potential
1675 coalesce partition. */
1678 EXECUTE_IF_SET_IN_BITMAP (used_in_copies
, 0, i
, bi
)
1680 int pidx
= var_to_partition (map
, ssa_name (i
));
1681 int base
= partition_find (tentative
, pidx
);
1682 if (index_map
[base
] != no_part
)
1684 index_map
[base
] = count
++;
1687 map
->num_basevars
= count
;
1689 EXECUTE_IF_SET_IN_BITMAP (used_in_copies
, 0, i
, bi
)
1691 int pidx
= var_to_partition (map
, ssa_name (i
));
1692 int base
= partition_find (tentative
, pidx
);
1693 gcc_assert (index_map
[base
] < count
);
1694 map
->partition_to_base_index
[pidx
] = index_map
[base
];
1697 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1698 dump_part_var_map (dump_file
, tentative
, map
);
1700 partition_delete (tentative
);
1703 /* Hashtable helpers. */
1705 struct tree_int_map_hasher
: nofree_ptr_hash
<tree_int_map
>
1707 static inline hashval_t
hash (const tree_int_map
*);
1708 static inline bool equal (const tree_int_map
*, const tree_int_map
*);
1712 tree_int_map_hasher::hash (const tree_int_map
*v
)
1714 return tree_map_base_hash (v
);
1718 tree_int_map_hasher::equal (const tree_int_map
*v
, const tree_int_map
*c
)
1720 return tree_int_map_eq (v
, c
);
1723 /* This routine will initialize the basevar fields of MAP with base
1724 names. Partitions will share the same base if they have the same
1725 SSA_NAME_VAR, or, being anonymous variables, the same type. This
1726 must match gimple_can_coalesce_p in the non-optimized case. */
1729 compute_samebase_partition_bases (var_map map
)
1733 struct tree_int_map
*m
, *mapstorage
;
1735 num_part
= num_var_partitions (map
);
1736 hash_table
<tree_int_map_hasher
> tree_to_index (num_part
);
1737 /* We can have at most num_part entries in the hash tables, so it's
1738 enough to allocate so many map elements once, saving some malloc
1740 mapstorage
= m
= XNEWVEC (struct tree_int_map
, num_part
);
1742 /* If a base table already exists, clear it, otherwise create it. */
1743 free (map
->partition_to_base_index
);
1744 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
1746 /* Build the base variable list, and point partitions at their bases. */
1747 for (x
= 0; x
< num_part
; x
++)
1749 struct tree_int_map
**slot
;
1751 var
= partition_to_var (map
, x
);
1752 if (SSA_NAME_VAR (var
)
1753 && (!VAR_P (SSA_NAME_VAR (var
))
1754 || !DECL_IGNORED_P (SSA_NAME_VAR (var
))))
1755 m
->base
.from
= SSA_NAME_VAR (var
);
1757 /* This restricts what anonymous SSA names we can coalesce
1758 as it restricts the sets we compute conflicts for.
1759 Using TREE_TYPE to generate sets is the easiest as
1760 type equivalency also holds for SSA names with the same
1763 Check gimple_can_coalesce_p when changing this code. */
1764 m
->base
.from
= (TYPE_CANONICAL (TREE_TYPE (var
))
1765 ? TYPE_CANONICAL (TREE_TYPE (var
))
1767 /* If base variable hasn't been seen, set it up. */
1768 slot
= tree_to_index
.find_slot (m
, INSERT
);
1771 baseindex
= m
- mapstorage
;
1777 baseindex
= (*slot
)->to
;
1778 map
->partition_to_base_index
[x
] = baseindex
;
1781 map
->num_basevars
= m
- mapstorage
;
1786 /* Reduce the number of copies by coalescing variables in the function. Return
1787 a partition map with the resulting coalesces. */
1790 coalesce_ssa_name (void)
1792 tree_live_info_p liveinfo
;
1793 ssa_conflicts
*graph
;
1795 auto_bitmap used_in_copies
;
1800 cl
= create_coalesce_list ();
1801 map
= create_outofssa_var_map (cl
, used_in_copies
);
1803 /* If this optimization is disabled, we need to coalesce all the
1804 names originating from the same SSA_NAME_VAR so debug info
1805 remains undisturbed. */
1806 if (!flag_tree_coalesce_vars
)
1808 hash_table
<ssa_name_var_hash
> ssa_name_hash (10);
1810 FOR_EACH_SSA_NAME (i
, a
, cfun
)
1812 if (SSA_NAME_VAR (a
)
1813 && !DECL_IGNORED_P (SSA_NAME_VAR (a
))
1814 && (!has_zero_uses (a
) || !SSA_NAME_IS_DEFAULT_DEF (a
)
1815 || !VAR_P (SSA_NAME_VAR (a
))))
1817 tree
*slot
= ssa_name_hash
.find_slot (a
, INSERT
);
1823 /* If the variable is a PARM_DECL or a RESULT_DECL, we
1824 _require_ that all the names originating from it be
1825 coalesced, because there must be a single partition
1826 containing all the names so that it can be assigned
1827 the canonical RTL location of the DECL safely.
1828 If in_lto_p, a function could have been compiled
1829 originally with optimizations and only the link
1830 performed at -O0, so we can't actually require it. */
1832 = (TREE_CODE (SSA_NAME_VAR (a
)) == VAR_DECL
|| in_lto_p
)
1833 ? MUST_COALESCE_COST
- 1 : MUST_COALESCE_COST
;
1834 add_coalesce (cl
, SSA_NAME_VERSION (a
),
1835 SSA_NAME_VERSION (*slot
), cost
);
1836 bitmap_set_bit (used_in_copies
, SSA_NAME_VERSION (a
));
1837 bitmap_set_bit (used_in_copies
, SSA_NAME_VERSION (*slot
));
1842 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1843 dump_var_map (dump_file
, map
);
1845 partition_view_bitmap (map
, used_in_copies
);
1847 if (flag_tree_coalesce_vars
)
1848 compute_optimized_partition_bases (map
, used_in_copies
, cl
);
1850 compute_samebase_partition_bases (map
);
1852 if (num_var_partitions (map
) < 1)
1854 delete_coalesce_list (cl
);
1858 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1859 dump_var_map (dump_file
, map
);
1861 liveinfo
= calculate_live_ranges (map
, false);
1863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1864 dump_live_info (dump_file
, liveinfo
, LIVEDUMP_ENTRY
);
1866 /* Build a conflict graph. */
1867 graph
= build_ssa_conflict_graph (liveinfo
);
1868 delete_tree_live_info (liveinfo
);
1869 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1870 ssa_conflicts_dump (dump_file
, graph
);
1872 sort_coalesce_list (cl
, graph
, map
);
1874 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1876 fprintf (dump_file
, "\nAfter sorting:\n");
1877 dump_coalesce_list (dump_file
, cl
);
1880 /* First, coalesce all live on entry variables to their base variable.
1881 This will ensure the first use is coming from the correct location. */
1883 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1884 dump_var_map (dump_file
, map
);
1886 /* Now coalesce everything in the list. */
1887 coalesce_partitions (map
, graph
, cl
,
1888 ((dump_flags
& TDF_DETAILS
) ? dump_file
: NULL
));
1890 delete_coalesce_list (cl
);
1891 ssa_conflicts_delete (graph
);
1896 /* We need to pass two arguments to set_parm_default_def_partition,
1897 but for_all_parms only supports one. Use a pair. */
1899 typedef std::pair
<var_map
, bitmap
> parm_default_def_partition_arg
;
1901 /* Set in ARG's PARTS bitmap the bit corresponding to the partition in
1902 ARG's MAP containing VAR's default def. */
1905 set_parm_default_def_partition (tree var
, void *arg_
)
1907 parm_default_def_partition_arg
*arg
= (parm_default_def_partition_arg
*)arg_
;
1908 var_map map
= arg
->first
;
1909 bitmap parts
= arg
->second
;
1911 if (!is_gimple_reg (var
))
1914 tree ssa
= ssa_default_def (cfun
, var
);
1917 int version
= var_to_partition (map
, ssa
);
1918 gcc_assert (version
!= NO_PARTITION
);
1920 bool changed
= bitmap_set_bit (parts
, version
);
1921 gcc_assert (changed
);
1924 /* Allocate and return a bitmap that has a bit set for each partition
1925 that contains a default def for a parameter. */
1928 get_parm_default_def_partitions (var_map map
)
1930 bitmap parm_default_def_parts
= BITMAP_ALLOC (NULL
);
1932 parm_default_def_partition_arg
1933 arg
= std::make_pair (map
, parm_default_def_parts
);
1935 for_all_parms (set_parm_default_def_partition
, &arg
);
1937 return parm_default_def_parts
;
1940 /* Allocate and return a bitmap that has a bit set for each partition
1941 that contains an undefined value. */
1944 get_undefined_value_partitions (var_map map
)
1946 bitmap undefined_value_parts
= BITMAP_ALLOC (NULL
);
1948 for (unsigned int i
= 1; i
< num_ssa_names
; i
++)
1950 tree var
= ssa_name (i
);
1952 && !virtual_operand_p (var
)
1953 && !has_zero_uses (var
)
1954 && ssa_undefined_value_p (var
))
1956 const int p
= var_to_partition (map
, var
);
1957 if (p
!= NO_PARTITION
)
1958 bitmap_set_bit (undefined_value_parts
, p
);
1962 return undefined_value_parts
;