1 /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 Copyright (C) 2004-2016 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"
31 #include "tree-pretty-print.h"
32 #include "diagnostic-core.h"
34 #include "gimple-iterator.h"
35 #include "tree-ssa-live.h"
36 #include "tree-ssa-coalesce.h"
39 #include "stor-layout.h"
41 /* This set of routines implements a coalesce_list. This is an object which
42 is used to track pairs of ssa_names which are desirable to coalesce
43 together to avoid copies. Costs are associated with each pair, and when
44 all desired information has been collected, the object can be used to
45 order the pairs for processing. */
47 /* This structure defines a pair entry. */
55 /* A count of the number of unique partitions this pair would conflict
56 with if coalescing was successful. This is the secondary sort key,
57 given two pairs with equal costs, we will prefer the pair with a smaller
60 This is lazily initialized when we discover two coalescing pairs have
61 the same primary cost.
63 Note this is not updated and propagated as pairs are coalesced. */
66 /* The order in which coalescing pairs are discovered is recorded in this
67 field, which is used as the final tie breaker when sorting coalesce
72 /* This represents a conflict graph. Implemented as an array of bitmaps.
73 A full matrix is used for conflicts rather than just upper triangular form.
74 this makes it much simpler and faster to perform conflict merges. */
78 bitmap_obstack obstack
; /* A place to allocate our bitmaps. */
79 vec
<bitmap
> conflicts
;
82 /* The narrow API of the qsort comparison function doesn't allow easy
83 access to additional arguments. So we have two globals (ick) to hold
84 the data we need. They're initialized before the call to qsort and
85 wiped immediately after. */
86 static ssa_conflicts
*conflicts_
;
89 /* Coalesce pair hashtable helpers. */
91 struct coalesce_pair_hasher
: nofree_ptr_hash
<coalesce_pair
>
93 static inline hashval_t
hash (const coalesce_pair
*);
94 static inline bool equal (const coalesce_pair
*, const coalesce_pair
*);
97 /* Hash function for coalesce list. Calculate hash for PAIR. */
100 coalesce_pair_hasher::hash (const coalesce_pair
*pair
)
102 hashval_t a
= (hashval_t
)(pair
->first_element
);
103 hashval_t b
= (hashval_t
)(pair
->second_element
);
105 return b
* (b
- 1) / 2 + a
;
108 /* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2,
109 returning TRUE if the two pairs are equivalent. */
112 coalesce_pair_hasher::equal (const coalesce_pair
*p1
, const coalesce_pair
*p2
)
114 return (p1
->first_element
== p2
->first_element
115 && p1
->second_element
== p2
->second_element
);
118 typedef hash_table
<coalesce_pair_hasher
> coalesce_table_type
;
119 typedef coalesce_table_type::iterator coalesce_iterator_type
;
129 /* This structure maintains the list of coalesce pairs. */
133 coalesce_table_type
*list
; /* Hash table. */
134 coalesce_pair
**sorted
; /* List when sorted. */
135 int num_sorted
; /* Number in the sorted list. */
136 cost_one_pair
*cost_one_list
;/* Single use coalesces with cost 1. */
139 #define NO_BEST_COALESCE -1
140 #define MUST_COALESCE_COST INT_MAX
143 /* Return cost of execution of copy instruction with FREQUENCY. */
146 coalesce_cost (int frequency
, bool optimize_for_size
)
148 /* Base costs on BB frequencies bounded by 1. */
149 int cost
= frequency
;
154 if (optimize_for_size
)
161 /* Return the cost of executing a copy instruction in basic block BB. */
164 coalesce_cost_bb (basic_block bb
)
166 return coalesce_cost (bb
->frequency
, optimize_bb_for_size_p (bb
));
170 /* Return the cost of executing a copy instruction on edge E. */
173 coalesce_cost_edge (edge e
)
177 /* Inserting copy on critical edge costs more than inserting it elsewhere. */
178 if (EDGE_CRITICAL_P (e
))
180 if (e
->flags
& EDGE_ABNORMAL
)
181 return MUST_COALESCE_COST
;
182 if (e
->flags
& EDGE_EH
)
186 FOR_EACH_EDGE (e2
, ei
, e
->dest
->preds
)
189 /* Putting code on EH edge that leads to BB
190 with multiple predecestors imply splitting of
194 /* If there are multiple EH predecestors, we
195 also copy EH regions and produce separate
196 landing pad. This is expensive. */
197 if (e2
->flags
& EDGE_EH
)
205 return coalesce_cost (EDGE_FREQUENCY (e
),
206 optimize_edge_for_size_p (e
)) * mult
;
210 /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
211 2 elements via P1 and P2. 1 is returned by the function if there is a pair,
212 NO_BEST_COALESCE is returned if there aren't any. */
215 pop_cost_one_pair (coalesce_list
*cl
, int *p1
, int *p2
)
219 ptr
= cl
->cost_one_list
;
221 return NO_BEST_COALESCE
;
223 *p1
= ptr
->first_element
;
224 *p2
= ptr
->second_element
;
225 cl
->cost_one_list
= ptr
->next
;
232 /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
233 2 elements via P1 and P2. Their calculated cost is returned by the function.
234 NO_BEST_COALESCE is returned if the coalesce list is empty. */
237 pop_best_coalesce (coalesce_list
*cl
, int *p1
, int *p2
)
242 if (cl
->sorted
== NULL
)
243 return pop_cost_one_pair (cl
, p1
, p2
);
245 if (cl
->num_sorted
== 0)
246 return pop_cost_one_pair (cl
, p1
, p2
);
248 node
= cl
->sorted
[--(cl
->num_sorted
)];
249 *p1
= node
->first_element
;
250 *p2
= node
->second_element
;
258 /* Create a new empty coalesce list object and return it. */
260 static inline coalesce_list
*
261 create_coalesce_list (void)
264 unsigned size
= num_ssa_names
* 3;
269 list
= (coalesce_list
*) xmalloc (sizeof (struct coalesce_list
));
270 list
->list
= new coalesce_table_type (size
);
272 list
->num_sorted
= 0;
273 list
->cost_one_list
= NULL
;
278 /* Delete coalesce list CL. */
281 delete_coalesce_list (coalesce_list
*cl
)
283 gcc_assert (cl
->cost_one_list
== NULL
);
287 gcc_assert (cl
->num_sorted
== 0);
291 /* Return the number of unique coalesce pairs in CL. */
294 num_coalesce_pairs (coalesce_list
*cl
)
296 return cl
->list
->elements ();
299 /* Find a matching coalesce pair object in CL for the pair P1 and P2. If
300 one isn't found, return NULL if CREATE is false, otherwise create a new
301 coalesce pair object and return it. */
303 static coalesce_pair
*
304 find_coalesce_pair (coalesce_list
*cl
, int p1
, int p2
, bool create
)
306 struct coalesce_pair p
;
307 coalesce_pair
**slot
;
310 /* Normalize so that p1 is the smaller value. */
313 p
.first_element
= p2
;
314 p
.second_element
= p1
;
318 p
.first_element
= p1
;
319 p
.second_element
= p2
;
322 hash
= coalesce_pair_hasher::hash (&p
);
323 slot
= cl
->list
->find_slot_with_hash (&p
, hash
, create
? INSERT
: NO_INSERT
);
329 struct coalesce_pair
* pair
= XNEW (struct coalesce_pair
);
330 gcc_assert (cl
->sorted
== NULL
);
331 pair
->first_element
= p
.first_element
;
332 pair
->second_element
= p
.second_element
;
334 pair
->index
= num_coalesce_pairs (cl
);
335 pair
->conflict_count
= 0;
339 return (struct coalesce_pair
*) *slot
;
343 add_cost_one_coalesce (coalesce_list
*cl
, int p1
, int p2
)
347 pair
= XNEW (cost_one_pair
);
348 pair
->first_element
= p1
;
349 pair
->second_element
= p2
;
350 pair
->next
= cl
->cost_one_list
;
351 cl
->cost_one_list
= pair
;
355 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
358 add_coalesce (coalesce_list
*cl
, int p1
, int p2
, int value
)
362 gcc_assert (cl
->sorted
== NULL
);
366 node
= find_coalesce_pair (cl
, p1
, p2
, true);
368 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
369 if (node
->cost
< MUST_COALESCE_COST
- 1)
371 if (value
< MUST_COALESCE_COST
- 1)
378 /* Compute and record how many unique conflicts would exist for the
379 representative partition for each coalesce pair in CL.
381 CONFLICTS is the conflict graph and MAP is the current partition view. */
384 initialize_conflict_count (coalesce_pair
*p
,
385 ssa_conflicts
*conflicts
,
388 int p1
= var_to_partition (map
, ssa_name (p
->first_element
));
389 int p2
= var_to_partition (map
, ssa_name (p
->second_element
));
391 /* 4 cases. If both P1 and P2 have conflicts, then build their
392 union and count the members. Else handle the degenerate cases
393 in the obvious ways. */
394 if (conflicts
->conflicts
[p1
] && conflicts
->conflicts
[p2
])
395 p
->conflict_count
= bitmap_count_unique_bits (conflicts
->conflicts
[p1
],
396 conflicts
->conflicts
[p2
]);
397 else if (conflicts
->conflicts
[p1
])
398 p
->conflict_count
= bitmap_count_bits (conflicts
->conflicts
[p1
]);
399 else if (conflicts
->conflicts
[p2
])
400 p
->conflict_count
= bitmap_count_bits (conflicts
->conflicts
[p2
]);
402 p
->conflict_count
= 0;
406 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
409 compare_pairs (const void *p1
, const void *p2
)
411 coalesce_pair
*const *const pp1
= (coalesce_pair
*const *) p1
;
412 coalesce_pair
*const *const pp2
= (coalesce_pair
*const *) p2
;
415 result
= (* pp1
)->cost
- (* pp2
)->cost
;
416 /* We use the size of the resulting conflict set as the secondary sort key.
417 Given two equal costing coalesce pairs, we want to prefer the pair that
418 has the smaller conflict set. */
421 if (flag_expensive_optimizations
)
423 /* Lazily initialize the conflict counts as it's fairly expensive
425 if ((*pp2
)->conflict_count
== 0)
426 initialize_conflict_count (*pp2
, conflicts_
, map_
);
427 if ((*pp1
)->conflict_count
== 0)
428 initialize_conflict_count (*pp1
, conflicts_
, map_
);
430 result
= (*pp2
)->conflict_count
- (*pp1
)->conflict_count
;
433 /* And if everything else is equal, then sort based on which
434 coalesce pair was found first. */
436 result
= (*pp2
)->index
- (*pp1
)->index
;
442 /* Iterate over CL using ITER, returning values in PAIR. */
444 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
445 FOR_EACH_HASH_TABLE_ELEMENT (*(CL)->list, (PAIR), coalesce_pair_p, (ITER))
448 /* Prepare CL for removal of preferred pairs. When finished they are sorted
449 in order from most important coalesce to least important. */
452 sort_coalesce_list (coalesce_list
*cl
, ssa_conflicts
*conflicts
, var_map map
)
456 coalesce_iterator_type ppi
;
458 gcc_assert (cl
->sorted
== NULL
);
460 num
= num_coalesce_pairs (cl
);
461 cl
->num_sorted
= num
;
465 /* Allocate a vector for the pair pointers. */
466 cl
->sorted
= XNEWVEC (coalesce_pair
*, num
);
468 /* Populate the vector with pointers to the pairs. */
470 FOR_EACH_PARTITION_PAIR (p
, ppi
, cl
)
472 gcc_assert (x
== num
);
474 /* Already sorted. */
478 /* We don't want to depend on qsort_r, so we have to stuff away
479 additional data into globals so it can be referenced in
481 conflicts_
= conflicts
;
483 qsort (cl
->sorted
, num
, sizeof (coalesce_pair
*), compare_pairs
);
489 /* Send debug info for coalesce list CL to file F. */
492 dump_coalesce_list (FILE *f
, coalesce_list
*cl
)
495 coalesce_iterator_type ppi
;
500 if (cl
->sorted
== NULL
)
502 fprintf (f
, "Coalesce List:\n");
503 FOR_EACH_PARTITION_PAIR (node
, ppi
, cl
)
505 tree var1
= ssa_name (node
->first_element
);
506 tree var2
= ssa_name (node
->second_element
);
507 print_generic_expr (f
, var1
, TDF_SLIM
);
508 fprintf (f
, " <-> ");
509 print_generic_expr (f
, var2
, TDF_SLIM
);
510 fprintf (f
, " (%1d, %1d), ", node
->cost
, node
->conflict_count
);
516 fprintf (f
, "Sorted Coalesce list:\n");
517 for (x
= cl
->num_sorted
- 1 ; x
>=0; x
--)
519 node
= cl
->sorted
[x
];
520 fprintf (f
, "(%d, %d) ", node
->cost
, node
->conflict_count
);
521 var
= ssa_name (node
->first_element
);
522 print_generic_expr (f
, var
, TDF_SLIM
);
523 fprintf (f
, " <-> ");
524 var
= ssa_name (node
->second_element
);
525 print_generic_expr (f
, var
, TDF_SLIM
);
532 /* Return an empty new conflict graph for SIZE elements. */
534 static inline ssa_conflicts
*
535 ssa_conflicts_new (unsigned size
)
539 ptr
= XNEW (ssa_conflicts
);
540 bitmap_obstack_initialize (&ptr
->obstack
);
541 ptr
->conflicts
.create (size
);
542 ptr
->conflicts
.safe_grow_cleared (size
);
547 /* Free storage for conflict graph PTR. */
550 ssa_conflicts_delete (ssa_conflicts
*ptr
)
552 bitmap_obstack_release (&ptr
->obstack
);
553 ptr
->conflicts
.release ();
558 /* Test if elements X and Y conflict in graph PTR. */
561 ssa_conflicts_test_p (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
563 bitmap bx
= ptr
->conflicts
[x
];
564 bitmap by
= ptr
->conflicts
[y
];
566 gcc_checking_assert (x
!= y
);
569 /* Avoid the lookup if Y has no conflicts. */
570 return by
? bitmap_bit_p (bx
, y
) : false;
576 /* Add a conflict with Y to the bitmap for X in graph PTR. */
579 ssa_conflicts_add_one (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
581 bitmap bx
= ptr
->conflicts
[x
];
582 /* If there are no conflicts yet, allocate the bitmap and set bit. */
584 bx
= ptr
->conflicts
[x
] = BITMAP_ALLOC (&ptr
->obstack
);
585 bitmap_set_bit (bx
, y
);
589 /* Add conflicts between X and Y in graph PTR. */
592 ssa_conflicts_add (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
594 gcc_checking_assert (x
!= y
);
595 ssa_conflicts_add_one (ptr
, x
, y
);
596 ssa_conflicts_add_one (ptr
, y
, x
);
600 /* Merge all Y's conflict into X in graph PTR. */
603 ssa_conflicts_merge (ssa_conflicts
*ptr
, unsigned x
, unsigned y
)
607 bitmap bx
= ptr
->conflicts
[x
];
608 bitmap by
= ptr
->conflicts
[y
];
610 gcc_checking_assert (x
!= y
);
614 /* Add a conflict between X and every one Y has. If the bitmap doesn't
615 exist, then it has already been coalesced, and we don't need to add a
617 EXECUTE_IF_SET_IN_BITMAP (by
, 0, z
, bi
)
619 bitmap bz
= ptr
->conflicts
[z
];
621 bitmap_set_bit (bz
, x
);
626 /* If X has conflicts, add Y's to X. */
627 bitmap_ior_into (bx
, by
);
629 ptr
->conflicts
[y
] = NULL
;
633 /* If X has no conflicts, simply use Y's. */
634 ptr
->conflicts
[x
] = by
;
635 ptr
->conflicts
[y
] = NULL
;
640 /* Dump a conflicts graph. */
643 ssa_conflicts_dump (FILE *file
, ssa_conflicts
*ptr
)
648 fprintf (file
, "\nConflict graph:\n");
650 FOR_EACH_VEC_ELT (ptr
->conflicts
, x
, b
)
653 fprintf (file
, "%d: ", x
);
654 dump_bitmap (file
, b
);
659 /* This structure is used to efficiently record the current status of live
660 SSA_NAMES when building a conflict graph.
661 LIVE_BASE_VAR has a bit set for each base variable which has at least one
663 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
664 index, and is used to track what partitions of each base variable are
665 live. This makes it easy to add conflicts between just live partitions
666 with the same base variable.
667 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
668 marked as being live. This delays clearing of these bitmaps until
669 they are actually needed again. */
673 bitmap_obstack obstack
; /* A place to allocate our bitmaps. */
674 bitmap live_base_var
; /* Indicates if a basevar is live. */
675 bitmap
*live_base_partitions
; /* Live partitions for each basevar. */
676 var_map map
; /* Var_map being used for partition mapping. */
680 /* This routine will create a new live track structure based on the partitions
684 new_live_track (var_map map
)
689 /* Make sure there is a partition view in place. */
690 gcc_assert (map
->partition_to_base_index
!= NULL
);
692 ptr
= (live_track
*) xmalloc (sizeof (live_track
));
694 lim
= num_basevars (map
);
695 bitmap_obstack_initialize (&ptr
->obstack
);
696 ptr
->live_base_partitions
= (bitmap
*) xmalloc (sizeof (bitmap
*) * lim
);
697 ptr
->live_base_var
= BITMAP_ALLOC (&ptr
->obstack
);
698 for (x
= 0; x
< lim
; x
++)
699 ptr
->live_base_partitions
[x
] = BITMAP_ALLOC (&ptr
->obstack
);
704 /* This routine will free the memory associated with PTR. */
707 delete_live_track (live_track
*ptr
)
709 bitmap_obstack_release (&ptr
->obstack
);
710 free (ptr
->live_base_partitions
);
715 /* This function will remove PARTITION from the live list in PTR. */
718 live_track_remove_partition (live_track
*ptr
, int partition
)
722 root
= basevar_index (ptr
->map
, partition
);
723 bitmap_clear_bit (ptr
->live_base_partitions
[root
], partition
);
724 /* If the element list is empty, make the base variable not live either. */
725 if (bitmap_empty_p (ptr
->live_base_partitions
[root
]))
726 bitmap_clear_bit (ptr
->live_base_var
, root
);
730 /* This function will adds PARTITION to the live list in PTR. */
733 live_track_add_partition (live_track
*ptr
, int partition
)
737 root
= basevar_index (ptr
->map
, partition
);
738 /* If this base var wasn't live before, it is now. Clear the element list
739 since it was delayed until needed. */
740 if (bitmap_set_bit (ptr
->live_base_var
, root
))
741 bitmap_clear (ptr
->live_base_partitions
[root
]);
742 bitmap_set_bit (ptr
->live_base_partitions
[root
], partition
);
747 /* Clear the live bit for VAR in PTR. */
750 live_track_clear_var (live_track
*ptr
, tree var
)
754 p
= var_to_partition (ptr
->map
, var
);
755 if (p
!= NO_PARTITION
)
756 live_track_remove_partition (ptr
, p
);
760 /* Return TRUE if VAR is live in PTR. */
763 live_track_live_p (live_track
*ptr
, tree var
)
767 p
= var_to_partition (ptr
->map
, var
);
768 if (p
!= NO_PARTITION
)
770 root
= basevar_index (ptr
->map
, p
);
771 if (bitmap_bit_p (ptr
->live_base_var
, root
))
772 return bitmap_bit_p (ptr
->live_base_partitions
[root
], p
);
778 /* This routine will add USE to PTR. USE will be marked as live in both the
779 ssa live map and the live bitmap for the root of USE. */
782 live_track_process_use (live_track
*ptr
, tree use
)
786 p
= var_to_partition (ptr
->map
, use
);
787 if (p
== NO_PARTITION
)
790 /* Mark as live in the appropriate live list. */
791 live_track_add_partition (ptr
, p
);
795 /* This routine will process a DEF in PTR. DEF will be removed from the live
796 lists, and if there are any other live partitions with the same base
797 variable, conflicts will be added to GRAPH. */
800 live_track_process_def (live_track
*ptr
, tree def
, ssa_conflicts
*graph
)
807 p
= var_to_partition (ptr
->map
, def
);
808 if (p
== NO_PARTITION
)
811 /* Clear the liveness bit. */
812 live_track_remove_partition (ptr
, p
);
814 /* If the bitmap isn't empty now, conflicts need to be added. */
815 root
= basevar_index (ptr
->map
, p
);
816 if (bitmap_bit_p (ptr
->live_base_var
, root
))
818 b
= ptr
->live_base_partitions
[root
];
819 EXECUTE_IF_SET_IN_BITMAP (b
, 0, x
, bi
)
820 ssa_conflicts_add (graph
, p
, x
);
825 /* Initialize PTR with the partitions set in INIT. */
828 live_track_init (live_track
*ptr
, bitmap init
)
833 /* Mark all live on exit partitions. */
834 EXECUTE_IF_SET_IN_BITMAP (init
, 0, p
, bi
)
835 live_track_add_partition (ptr
, p
);
839 /* This routine will clear all live partitions in PTR. */
842 live_track_clear_base_vars (live_track
*ptr
)
844 /* Simply clear the live base list. Anything marked as live in the element
845 lists will be cleared later if/when the base variable ever comes alive
847 bitmap_clear (ptr
->live_base_var
);
851 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
852 partition view of the var_map liveinfo is based on get entries in the
853 conflict graph. Only conflicts between ssa_name partitions with the same
854 base variable are added. */
856 static ssa_conflicts
*
857 build_ssa_conflict_graph (tree_live_info_p liveinfo
)
859 ssa_conflicts
*graph
;
866 /* If inter-variable coalescing is enabled, we may attempt to
867 coalesce variables from different base variables, including
868 different parameters, so we have to make sure default defs live
869 at the entry block conflict with each other. */
870 if (flag_tree_coalesce_vars
)
871 entry
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
875 map
= live_var_map (liveinfo
);
876 graph
= ssa_conflicts_new (num_var_partitions (map
));
878 live
= new_live_track (map
);
880 FOR_EACH_BB_FN (bb
, cfun
)
882 /* Start with live on exit temporaries. */
883 live_track_init (live
, live_on_exit (liveinfo
, bb
));
885 for (gimple_stmt_iterator gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);
889 gimple
*stmt
= gsi_stmt (gsi
);
891 /* A copy between 2 partitions does not introduce an interference
892 by itself. If they did, you would never be able to coalesce
893 two things which are copied. If the two variables really do
894 conflict, they will conflict elsewhere in the program.
896 This is handled by simply removing the SRC of the copy from the
897 live list, and processing the stmt normally. */
898 if (is_gimple_assign (stmt
))
900 tree lhs
= gimple_assign_lhs (stmt
);
901 tree rhs1
= gimple_assign_rhs1 (stmt
);
902 if (gimple_assign_copy_p (stmt
)
903 && TREE_CODE (lhs
) == SSA_NAME
904 && TREE_CODE (rhs1
) == SSA_NAME
)
905 live_track_clear_var (live
, rhs1
);
907 else if (is_gimple_debug (stmt
))
910 /* For stmts with more than one SSA_NAME definition pretend all the
911 SSA_NAME outputs but the first one are live at this point, so
912 that conflicts are added in between all those even when they are
913 actually not really live after the asm, because expansion might
914 copy those into pseudos after the asm and if multiple outputs
915 share the same partition, it might overwrite those that should
917 asm volatile (".." : "=r" (a) : "=r" (b) : "0" (a), "1" (a));
921 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_DEF
)
925 live_track_process_use (live
, var
);
927 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_DEF
)
928 live_track_process_def (live
, var
, graph
);
930 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_USE
)
931 live_track_process_use (live
, var
);
934 /* If result of a PHI is unused, looping over the statements will not
935 record any conflicts since the def was never live. Since the PHI node
936 is going to be translated out of SSA form, it will insert a copy.
937 There must be a conflict recorded between the result of the PHI and
938 any variables that are live. Otherwise the out-of-ssa translation
939 may create incorrect code. */
940 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
943 gphi
*phi
= gsi
.phi ();
944 tree result
= PHI_RESULT (phi
);
945 if (live_track_live_p (live
, result
))
946 live_track_process_def (live
, result
, graph
);
949 /* Pretend there are defs for params' default defs at the start
950 of the (post-)entry block. This will prevent PARM_DECLs from
951 coalescing into the same partition. Although RESULT_DECLs'
952 default defs don't have a useful initial value, we have to
953 prevent them from coalescing with PARM_DECLs' default defs
954 too, otherwise assign_parms would attempt to assign different
955 RTL to the same partition. */
961 FOR_EACH_SSA_NAME (i
, var
, cfun
)
963 if (!SSA_NAME_IS_DEFAULT_DEF (var
)
964 || !SSA_NAME_VAR (var
)
965 || VAR_P (SSA_NAME_VAR (var
)))
968 live_track_process_def (live
, var
, graph
);
969 /* Process a use too, so that it remains live and
970 conflicts with other parms' default defs, even unused
972 live_track_process_use (live
, var
);
976 live_track_clear_base_vars (live
);
979 delete_live_track (live
);
984 /* Shortcut routine to print messages to file F of the form:
985 "STR1 EXPR1 STR2 EXPR2 STR3." */
988 print_exprs (FILE *f
, const char *str1
, tree expr1
, const char *str2
,
989 tree expr2
, const char *str3
)
991 fprintf (f
, "%s", str1
);
992 print_generic_expr (f
, expr1
, TDF_SLIM
);
993 fprintf (f
, "%s", str2
);
994 print_generic_expr (f
, expr2
, TDF_SLIM
);
995 fprintf (f
, "%s", str3
);
999 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
1002 fail_abnormal_edge_coalesce (int x
, int y
)
1004 fprintf (stderr
, "\nUnable to coalesce ssa_names %d and %d",x
, y
);
1005 fprintf (stderr
, " which are marked as MUST COALESCE.\n");
1006 print_generic_expr (stderr
, ssa_name (x
), TDF_SLIM
);
1007 fprintf (stderr
, " and ");
1008 print_generic_stmt (stderr
, ssa_name (y
), TDF_SLIM
);
1010 internal_error ("SSA corruption");
1013 /* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
1014 assign_parms may ask for a default partition. */
1017 for_all_parms (void (*callback
)(tree var
, void *arg
), void *arg
)
1019 for (tree var
= DECL_ARGUMENTS (current_function_decl
); var
;
1020 var
= DECL_CHAIN (var
))
1021 callback (var
, arg
);
1022 if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
1023 callback (DECL_RESULT (current_function_decl
), arg
);
1024 if (cfun
->static_chain_decl
)
1025 callback (cfun
->static_chain_decl
, arg
);
1028 /* Create a default def for VAR. */
1031 create_default_def (tree var
, void *arg ATTRIBUTE_UNUSED
)
1033 if (!is_gimple_reg (var
))
1036 tree ssa
= get_or_create_ssa_default_def (cfun
, var
);
1040 /* Register VAR's default def in MAP. */
1043 register_default_def (tree var
, void *map_
)
1045 var_map map
= (var_map
)map_
;
1047 if (!is_gimple_reg (var
))
1050 tree ssa
= ssa_default_def (cfun
, var
);
1053 register_ssa_partition (map
, ssa
);
1056 /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
1057 and the DECL's default def is unused (i.e., it was introduced by
1058 create_default_def), mark VAR and the default def for
1062 coalesce_with_default (tree var
, coalesce_list
*cl
, bitmap used_in_copy
)
1064 if (SSA_NAME_IS_DEFAULT_DEF (var
)
1065 || !SSA_NAME_VAR (var
)
1066 || VAR_P (SSA_NAME_VAR (var
)))
1069 tree ssa
= ssa_default_def (cfun
, SSA_NAME_VAR (var
));
1070 if (!has_zero_uses (ssa
))
1073 add_cost_one_coalesce (cl
, SSA_NAME_VERSION (ssa
), SSA_NAME_VERSION (var
));
1074 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1075 /* Default defs will have their used_in_copy bits set at the end of
1076 create_outofssa_var_map. */
1079 /* This function creates a var_map for the current function as well as creating
1080 a coalesce list for use later in the out of ssa process. */
1083 create_outofssa_var_map (coalesce_list
*cl
, bitmap used_in_copy
)
1085 gimple_stmt_iterator gsi
;
1095 for_all_parms (create_default_def
, NULL
);
1097 map
= init_var_map (num_ssa_names
);
1099 for_all_parms (register_default_def
, map
);
1101 FOR_EACH_BB_FN (bb
, cfun
)
1105 for (gphi_iterator gpi
= gsi_start_phis (bb
);
1109 gphi
*phi
= gpi
.phi ();
1113 bool saw_copy
= false;
1115 res
= gimple_phi_result (phi
);
1116 ver
= SSA_NAME_VERSION (res
);
1117 register_ssa_partition (map
, res
);
1119 /* Register ssa_names and coalesces between the args and the result
1121 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1123 edge e
= gimple_phi_arg_edge (phi
, i
);
1124 arg
= PHI_ARG_DEF (phi
, i
);
1125 if (TREE_CODE (arg
) != SSA_NAME
)
1128 register_ssa_partition (map
, arg
);
1129 if (gimple_can_coalesce_p (arg
, res
)
1130 || (e
->flags
& EDGE_ABNORMAL
))
1133 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (arg
));
1134 if ((e
->flags
& EDGE_ABNORMAL
) == 0)
1136 int cost
= coalesce_cost_edge (e
);
1137 if (cost
== 1 && has_single_use (arg
))
1138 add_cost_one_coalesce (cl
, ver
, SSA_NAME_VERSION (arg
));
1140 add_coalesce (cl
, ver
, SSA_NAME_VERSION (arg
), cost
);
1145 bitmap_set_bit (used_in_copy
, ver
);
1148 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1150 stmt
= gsi_stmt (gsi
);
1152 if (is_gimple_debug (stmt
))
1155 /* Register USE and DEF operands in each statement. */
1156 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, (SSA_OP_DEF
|SSA_OP_USE
))
1157 register_ssa_partition (map
, var
);
1159 /* Check for copy coalesces. */
1160 switch (gimple_code (stmt
))
1164 tree lhs
= gimple_assign_lhs (stmt
);
1165 tree rhs1
= gimple_assign_rhs1 (stmt
);
1166 if (gimple_assign_ssa_name_copy_p (stmt
)
1167 && gimple_can_coalesce_p (lhs
, rhs1
))
1169 v1
= SSA_NAME_VERSION (lhs
);
1170 v2
= SSA_NAME_VERSION (rhs1
);
1171 cost
= coalesce_cost_bb (bb
);
1172 add_coalesce (cl
, v1
, v2
, cost
);
1173 bitmap_set_bit (used_in_copy
, v1
);
1174 bitmap_set_bit (used_in_copy
, v2
);
1181 tree res
= DECL_RESULT (current_function_decl
);
1182 if (VOID_TYPE_P (TREE_TYPE (res
))
1183 || !is_gimple_reg (res
))
1185 tree rhs1
= gimple_return_retval (as_a
<greturn
*> (stmt
));
1188 tree lhs
= ssa_default_def (cfun
, res
);
1190 if (TREE_CODE (rhs1
) == SSA_NAME
1191 && gimple_can_coalesce_p (lhs
, rhs1
))
1193 v1
= SSA_NAME_VERSION (lhs
);
1194 v2
= SSA_NAME_VERSION (rhs1
);
1195 cost
= coalesce_cost_bb (bb
);
1196 add_coalesce (cl
, v1
, v2
, cost
);
1197 bitmap_set_bit (used_in_copy
, v1
);
1198 bitmap_set_bit (used_in_copy
, v2
);
1205 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
1206 unsigned long noutputs
, i
;
1207 unsigned long ninputs
;
1208 tree
*outputs
, link
;
1209 noutputs
= gimple_asm_noutputs (asm_stmt
);
1210 ninputs
= gimple_asm_ninputs (asm_stmt
);
1211 outputs
= (tree
*) alloca (noutputs
* sizeof (tree
));
1212 for (i
= 0; i
< noutputs
; ++i
)
1214 link
= gimple_asm_output_op (asm_stmt
, i
);
1215 outputs
[i
] = TREE_VALUE (link
);
1218 for (i
= 0; i
< ninputs
; ++i
)
1220 const char *constraint
;
1223 unsigned long match
;
1225 link
= gimple_asm_input_op (asm_stmt
, i
);
1227 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
1228 input
= TREE_VALUE (link
);
1230 if (TREE_CODE (input
) != SSA_NAME
)
1233 match
= strtoul (constraint
, &end
, 10);
1234 if (match
>= noutputs
|| end
== constraint
)
1237 if (TREE_CODE (outputs
[match
]) != SSA_NAME
)
1240 v1
= SSA_NAME_VERSION (outputs
[match
]);
1241 v2
= SSA_NAME_VERSION (input
);
1243 if (gimple_can_coalesce_p (outputs
[match
], input
))
1245 cost
= coalesce_cost (REG_BR_PROB_BASE
,
1246 optimize_bb_for_size_p (bb
));
1247 add_coalesce (cl
, v1
, v2
, cost
);
1248 bitmap_set_bit (used_in_copy
, v1
);
1249 bitmap_set_bit (used_in_copy
, v2
);
1261 /* Now process result decls and live on entry variables for entry into
1262 the coalesce list. */
1264 FOR_EACH_SSA_NAME (i
, var
, cfun
)
1266 if (!virtual_operand_p (var
))
1268 coalesce_with_default (var
, cl
, used_in_copy
);
1270 /* Add coalesces between all the result decls. */
1271 if (SSA_NAME_VAR (var
)
1272 && TREE_CODE (SSA_NAME_VAR (var
)) == RESULT_DECL
)
1274 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1275 if (first
== NULL_TREE
)
1279 gcc_assert (gimple_can_coalesce_p (var
, first
));
1280 v1
= SSA_NAME_VERSION (first
);
1281 v2
= SSA_NAME_VERSION (var
);
1282 cost
= coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun
));
1283 add_coalesce (cl
, v1
, v2
, cost
);
1286 /* Mark any default_def variables as being in the coalesce list
1287 since they will have to be coalesced with the base variable. If
1288 not marked as present, they won't be in the coalesce view. */
1289 if (SSA_NAME_IS_DEFAULT_DEF (var
)
1290 && (!has_zero_uses (var
)
1291 || (SSA_NAME_VAR (var
)
1292 && !VAR_P (SSA_NAME_VAR (var
)))))
1293 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1301 /* Attempt to coalesce ssa versions X and Y together using the partition
1302 mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1303 DEBUG, if it is nun-NULL. */
1306 attempt_coalesce (var_map map
, ssa_conflicts
*graph
, int x
, int y
,
1313 p1
= var_to_partition (map
, ssa_name (x
));
1314 p2
= var_to_partition (map
, ssa_name (y
));
1318 fprintf (debug
, "(%d)", x
);
1319 print_generic_expr (debug
, partition_to_var (map
, p1
), TDF_SLIM
);
1320 fprintf (debug
, " & (%d)", y
);
1321 print_generic_expr (debug
, partition_to_var (map
, p2
), TDF_SLIM
);
1327 fprintf (debug
, ": Already Coalesced.\n");
1332 fprintf (debug
, " [map: %d, %d] ", p1
, p2
);
1335 if (!ssa_conflicts_test_p (graph
, p1
, p2
))
1337 var1
= partition_to_var (map
, p1
);
1338 var2
= partition_to_var (map
, p2
);
1340 z
= var_union (map
, var1
, var2
);
1341 if (z
== NO_PARTITION
)
1344 fprintf (debug
, ": Unable to perform partition union.\n");
1348 /* z is the new combined partition. Remove the other partition from
1349 the list, and merge the conflicts. */
1351 ssa_conflicts_merge (graph
, p1
, p2
);
1353 ssa_conflicts_merge (graph
, p2
, p1
);
1356 fprintf (debug
, ": Success -> %d\n", z
);
1362 fprintf (debug
, ": Fail due to conflict\n");
1368 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1369 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1372 coalesce_partitions (var_map map
, ssa_conflicts
*graph
, coalesce_list
*cl
,
1382 /* First, coalesce all the copies across abnormal edges. These are not placed
1383 in the coalesce list because they do not need to be sorted, and simply
1384 consume extra memory/compilation time in large programs. */
1386 FOR_EACH_BB_FN (bb
, cfun
)
1388 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1389 if (e
->flags
& EDGE_ABNORMAL
)
1392 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1395 gphi
*phi
= gsi
.phi ();
1396 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1397 if (SSA_NAME_IS_DEFAULT_DEF (arg
)
1398 && (!SSA_NAME_VAR (arg
)
1399 || TREE_CODE (SSA_NAME_VAR (arg
)) != PARM_DECL
))
1402 tree res
= PHI_RESULT (phi
);
1403 int v1
= SSA_NAME_VERSION (res
);
1404 int v2
= SSA_NAME_VERSION (arg
);
1407 fprintf (debug
, "Abnormal coalesce: ");
1409 if (!attempt_coalesce (map
, graph
, v1
, v2
, debug
))
1410 fail_abnormal_edge_coalesce (v1
, v2
);
1415 /* Now process the items in the coalesce list. */
1417 while ((cost
= pop_best_coalesce (cl
, &x
, &y
)) != NO_BEST_COALESCE
)
1419 var1
= ssa_name (x
);
1420 var2
= ssa_name (y
);
1422 /* Assert the coalesces have the same base variable. */
1423 gcc_assert (gimple_can_coalesce_p (var1
, var2
));
1426 fprintf (debug
, "Coalesce list: ");
1427 attempt_coalesce (map
, graph
, x
, y
, debug
);
1432 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1434 struct ssa_name_var_hash
: nofree_ptr_hash
<tree_node
>
1436 static inline hashval_t
hash (const tree_node
*);
1437 static inline int equal (const tree_node
*, const tree_node
*);
1441 ssa_name_var_hash::hash (const_tree n
)
1443 return DECL_UID (SSA_NAME_VAR (n
));
1447 ssa_name_var_hash::equal (const tree_node
*n1
, const tree_node
*n2
)
1449 return SSA_NAME_VAR (n1
) == SSA_NAME_VAR (n2
);
1453 /* Output partition map MAP with coalescing plan PART to file F. */
1456 dump_part_var_map (FILE *f
, partition part
, var_map map
)
1462 fprintf (f
, "\nCoalescible Partition map \n\n");
1464 for (x
= 0; x
< map
->num_partitions
; x
++)
1466 if (map
->view_to_partition
!= NULL
)
1467 p
= map
->view_to_partition
[x
];
1471 if (ssa_name (p
) == NULL_TREE
1472 || virtual_operand_p (ssa_name (p
)))
1476 for (y
= 1; y
< num_ssa_names
; y
++)
1478 tree var
= version_to_var (map
, y
);
1481 int q
= var_to_partition (map
, var
);
1482 p
= partition_find (part
, q
);
1483 gcc_assert (map
->partition_to_base_index
[q
]
1484 == map
->partition_to_base_index
[p
]);
1490 fprintf (f
, "Partition %d, base %d (", x
,
1491 map
->partition_to_base_index
[q
]);
1492 print_generic_expr (f
, partition_to_var (map
, q
), TDF_SLIM
);
1495 fprintf (f
, "%d ", y
);
1504 /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
1505 coalescing together, false otherwise.
1507 This must stay consistent with compute_samebase_partition_bases and
1508 compute_optimized_partition_bases. */
1511 gimple_can_coalesce_p (tree name1
, tree name2
)
1513 /* First check the SSA_NAME's associated DECL. Without
1514 optimization, we only want to coalesce if they have the same DECL
1515 or both have no associated DECL. */
1516 tree var1
= SSA_NAME_VAR (name1
);
1517 tree var2
= SSA_NAME_VAR (name2
);
1518 var1
= (var1
&& (!VAR_P (var1
) || !DECL_IGNORED_P (var1
))) ? var1
: NULL_TREE
;
1519 var2
= (var2
&& (!VAR_P (var2
) || !DECL_IGNORED_P (var2
))) ? var2
: NULL_TREE
;
1520 if (var1
!= var2
&& !flag_tree_coalesce_vars
)
1523 /* Now check the types. If the types are the same, then we should
1524 try to coalesce V1 and V2. */
1525 tree t1
= TREE_TYPE (name1
);
1526 tree t2
= TREE_TYPE (name2
);
1530 /* If the base variables are the same, we're good: none of the
1531 other tests below could possibly fail. */
1532 var1
= SSA_NAME_VAR (name1
);
1533 var2
= SSA_NAME_VAR (name2
);
1537 /* We don't want to coalesce two SSA names if one of the base
1538 variables is supposed to be a register while the other is
1539 supposed to be on the stack. Anonymous SSA names most often
1540 take registers, but when not optimizing, user variables
1541 should go on the stack, so coalescing them with the anonymous
1542 variable as the partition leader would end up assigning the
1543 user variable to a register. Don't do that! */
1544 bool reg1
= use_register_for_decl (name1
);
1545 bool reg2
= use_register_for_decl (name2
);
1549 /* Check that the promoted modes and unsignedness are the same.
1550 We don't want to coalesce if the promoted modes would be
1551 different, or if they would sign-extend differently. Only
1552 PARM_DECLs and RESULT_DECLs have different promotion rules,
1553 so skip the test if both are variables, or both are anonymous
1555 int unsigned1
, unsigned2
;
1556 return ((!var1
|| VAR_P (var1
)) && (!var2
|| VAR_P (var2
)))
1557 || ((promote_ssa_mode (name1
, &unsigned1
)
1558 == promote_ssa_mode (name2
, &unsigned2
))
1559 && unsigned1
== unsigned2
);
1562 /* If alignment requirements are different, we can't coalesce. */
1563 if (MINIMUM_ALIGNMENT (t1
,
1564 var1
? DECL_MODE (var1
) : TYPE_MODE (t1
),
1565 var1
? LOCAL_DECL_ALIGNMENT (var1
) : TYPE_ALIGN (t1
))
1566 != MINIMUM_ALIGNMENT (t2
,
1567 var2
? DECL_MODE (var2
) : TYPE_MODE (t2
),
1568 var2
? LOCAL_DECL_ALIGNMENT (var2
) : TYPE_ALIGN (t2
)))
1571 /* If the types are not the same, see whether they are compatible. This
1572 (for example) allows coalescing when the types are fundamentally the
1573 same, but just have different names.
1575 In the non-optimized case, we must first test TYPE_CANONICAL because
1576 we use it to compute the partition_to_base_index of the map. */
1577 if (flag_tree_coalesce_vars
)
1579 if (types_compatible_p (t1
, t2
))
1584 if (TYPE_CANONICAL (t1
)
1585 && TYPE_CANONICAL (t1
) == TYPE_CANONICAL (t2
)
1586 && types_compatible_p (t1
, t2
))
1593 /* Fill in MAP's partition_to_base_index, with one index for each
1594 partition of SSA names USED_IN_COPIES and related by CL coalesce
1595 possibilities. This must match gimple_can_coalesce_p in the
1599 compute_optimized_partition_bases (var_map map
, bitmap used_in_copies
,
1602 int parts
= num_var_partitions (map
);
1603 partition tentative
= partition_new (parts
);
1605 /* Partition the SSA versions so that, for each coalescible
1606 pair, both of its members are in the same partition in
1608 gcc_assert (!cl
->sorted
);
1609 coalesce_pair
*node
;
1610 coalesce_iterator_type ppi
;
1611 FOR_EACH_PARTITION_PAIR (node
, ppi
, cl
)
1613 tree v1
= ssa_name (node
->first_element
);
1614 int p1
= partition_find (tentative
, var_to_partition (map
, v1
));
1615 tree v2
= ssa_name (node
->second_element
);
1616 int p2
= partition_find (tentative
, var_to_partition (map
, v2
));
1621 partition_union (tentative
, p1
, p2
);
1624 /* We have to deal with cost one pairs too. */
1625 for (cost_one_pair
*co
= cl
->cost_one_list
; co
; co
= co
->next
)
1627 tree v1
= ssa_name (co
->first_element
);
1628 int p1
= partition_find (tentative
, var_to_partition (map
, v1
));
1629 tree v2
= ssa_name (co
->second_element
);
1630 int p2
= partition_find (tentative
, var_to_partition (map
, v2
));
1635 partition_union (tentative
, p1
, p2
);
1638 /* And also with abnormal edges. */
1642 FOR_EACH_BB_FN (bb
, cfun
)
1644 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1645 if (e
->flags
& EDGE_ABNORMAL
)
1648 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1651 gphi
*phi
= gsi
.phi ();
1652 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1653 if (SSA_NAME_IS_DEFAULT_DEF (arg
)
1654 && (!SSA_NAME_VAR (arg
)
1655 || TREE_CODE (SSA_NAME_VAR (arg
)) != PARM_DECL
))
1658 tree res
= PHI_RESULT (phi
);
1660 int p1
= partition_find (tentative
, var_to_partition (map
, res
));
1661 int p2
= partition_find (tentative
, var_to_partition (map
, arg
));
1666 partition_union (tentative
, p1
, p2
);
1671 map
->partition_to_base_index
= XCNEWVEC (int, parts
);
1672 auto_vec
<unsigned int> index_map (parts
);
1674 index_map
.quick_grow (parts
);
1676 const unsigned no_part
= -1;
1677 unsigned count
= parts
;
1679 index_map
[--count
] = no_part
;
1681 /* Initialize MAP's mapping from partition to base index, using
1682 as base indices an enumeration of the TENTATIVE partitions in
1683 which each SSA version ended up, so that we compute conflicts
1684 between all SSA versions that ended up in the same potential
1685 coalesce partition. */
1688 EXECUTE_IF_SET_IN_BITMAP (used_in_copies
, 0, i
, bi
)
1690 int pidx
= var_to_partition (map
, ssa_name (i
));
1691 int base
= partition_find (tentative
, pidx
);
1692 if (index_map
[base
] != no_part
)
1694 index_map
[base
] = count
++;
1697 map
->num_basevars
= count
;
1699 EXECUTE_IF_SET_IN_BITMAP (used_in_copies
, 0, i
, bi
)
1701 int pidx
= var_to_partition (map
, ssa_name (i
));
1702 int base
= partition_find (tentative
, pidx
);
1703 gcc_assert (index_map
[base
] < count
);
1704 map
->partition_to_base_index
[pidx
] = index_map
[base
];
1707 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1708 dump_part_var_map (dump_file
, tentative
, map
);
1710 partition_delete (tentative
);
1713 /* Hashtable helpers. */
1715 struct tree_int_map_hasher
: nofree_ptr_hash
<tree_int_map
>
1717 static inline hashval_t
hash (const tree_int_map
*);
1718 static inline bool equal (const tree_int_map
*, const tree_int_map
*);
1722 tree_int_map_hasher::hash (const tree_int_map
*v
)
1724 return tree_map_base_hash (v
);
1728 tree_int_map_hasher::equal (const tree_int_map
*v
, const tree_int_map
*c
)
1730 return tree_int_map_eq (v
, c
);
1733 /* This routine will initialize the basevar fields of MAP with base
1734 names. Partitions will share the same base if they have the same
1735 SSA_NAME_VAR, or, being anonymous variables, the same type. This
1736 must match gimple_can_coalesce_p in the non-optimized case. */
1739 compute_samebase_partition_bases (var_map map
)
1743 struct tree_int_map
*m
, *mapstorage
;
1745 num_part
= num_var_partitions (map
);
1746 hash_table
<tree_int_map_hasher
> tree_to_index (num_part
);
1747 /* We can have at most num_part entries in the hash tables, so it's
1748 enough to allocate so many map elements once, saving some malloc
1750 mapstorage
= m
= XNEWVEC (struct tree_int_map
, num_part
);
1752 /* If a base table already exists, clear it, otherwise create it. */
1753 free (map
->partition_to_base_index
);
1754 map
->partition_to_base_index
= (int *) xmalloc (sizeof (int) * num_part
);
1756 /* Build the base variable list, and point partitions at their bases. */
1757 for (x
= 0; x
< num_part
; x
++)
1759 struct tree_int_map
**slot
;
1761 var
= partition_to_var (map
, x
);
1762 if (SSA_NAME_VAR (var
)
1763 && (!VAR_P (SSA_NAME_VAR (var
))
1764 || !DECL_IGNORED_P (SSA_NAME_VAR (var
))))
1765 m
->base
.from
= SSA_NAME_VAR (var
);
1767 /* This restricts what anonymous SSA names we can coalesce
1768 as it restricts the sets we compute conflicts for.
1769 Using TREE_TYPE to generate sets is the easiest as
1770 type equivalency also holds for SSA names with the same
1773 Check gimple_can_coalesce_p when changing this code. */
1774 m
->base
.from
= (TYPE_CANONICAL (TREE_TYPE (var
))
1775 ? TYPE_CANONICAL (TREE_TYPE (var
))
1777 /* If base variable hasn't been seen, set it up. */
1778 slot
= tree_to_index
.find_slot (m
, INSERT
);
1781 baseindex
= m
- mapstorage
;
1787 baseindex
= (*slot
)->to
;
1788 map
->partition_to_base_index
[x
] = baseindex
;
1791 map
->num_basevars
= m
- mapstorage
;
1796 /* Reduce the number of copies by coalescing variables in the function. Return
1797 a partition map with the resulting coalesces. */
1800 coalesce_ssa_name (void)
1802 tree_live_info_p liveinfo
;
1803 ssa_conflicts
*graph
;
1805 bitmap used_in_copies
= BITMAP_ALLOC (NULL
);
1810 cl
= create_coalesce_list ();
1811 map
= create_outofssa_var_map (cl
, used_in_copies
);
1813 /* If this optimization is disabled, we need to coalesce all the
1814 names originating from the same SSA_NAME_VAR so debug info
1815 remains undisturbed. */
1816 if (!flag_tree_coalesce_vars
)
1818 hash_table
<ssa_name_var_hash
> ssa_name_hash (10);
1820 FOR_EACH_SSA_NAME (i
, a
, cfun
)
1822 if (SSA_NAME_VAR (a
)
1823 && !DECL_IGNORED_P (SSA_NAME_VAR (a
))
1824 && (!has_zero_uses (a
) || !SSA_NAME_IS_DEFAULT_DEF (a
)
1825 || !VAR_P (SSA_NAME_VAR (a
))))
1827 tree
*slot
= ssa_name_hash
.find_slot (a
, INSERT
);
1833 /* If the variable is a PARM_DECL or a RESULT_DECL, we
1834 _require_ that all the names originating from it be
1835 coalesced, because there must be a single partition
1836 containing all the names so that it can be assigned
1837 the canonical RTL location of the DECL safely.
1838 If in_lto_p, a function could have been compiled
1839 originally with optimizations and only the link
1840 performed at -O0, so we can't actually require it. */
1842 = (TREE_CODE (SSA_NAME_VAR (a
)) == VAR_DECL
|| in_lto_p
)
1843 ? MUST_COALESCE_COST
- 1 : MUST_COALESCE_COST
;
1844 add_coalesce (cl
, SSA_NAME_VERSION (a
),
1845 SSA_NAME_VERSION (*slot
), cost
);
1846 bitmap_set_bit (used_in_copies
, SSA_NAME_VERSION (a
));
1847 bitmap_set_bit (used_in_copies
, SSA_NAME_VERSION (*slot
));
1852 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1853 dump_var_map (dump_file
, map
);
1855 partition_view_bitmap (map
, used_in_copies
);
1857 if (flag_tree_coalesce_vars
)
1858 compute_optimized_partition_bases (map
, used_in_copies
, cl
);
1860 compute_samebase_partition_bases (map
);
1862 BITMAP_FREE (used_in_copies
);
1864 if (num_var_partitions (map
) < 1)
1866 delete_coalesce_list (cl
);
1870 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1871 dump_var_map (dump_file
, map
);
1873 liveinfo
= calculate_live_ranges (map
, false);
1875 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1876 dump_live_info (dump_file
, liveinfo
, LIVEDUMP_ENTRY
);
1878 /* Build a conflict graph. */
1879 graph
= build_ssa_conflict_graph (liveinfo
);
1880 delete_tree_live_info (liveinfo
);
1881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1882 ssa_conflicts_dump (dump_file
, graph
);
1884 sort_coalesce_list (cl
, graph
, map
);
1886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1888 fprintf (dump_file
, "\nAfter sorting:\n");
1889 dump_coalesce_list (dump_file
, cl
);
1892 /* First, coalesce all live on entry variables to their base variable.
1893 This will ensure the first use is coming from the correct location. */
1895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1896 dump_var_map (dump_file
, map
);
1898 /* Now coalesce everything in the list. */
1899 coalesce_partitions (map
, graph
, cl
,
1900 ((dump_flags
& TDF_DETAILS
) ? dump_file
: NULL
));
1902 delete_coalesce_list (cl
);
1903 ssa_conflicts_delete (graph
);
1908 /* We need to pass two arguments to set_parm_default_def_partition,
1909 but for_all_parms only supports one. Use a pair. */
1911 typedef std::pair
<var_map
, bitmap
> parm_default_def_partition_arg
;
1913 /* Set in ARG's PARTS bitmap the bit corresponding to the partition in
1914 ARG's MAP containing VAR's default def. */
1917 set_parm_default_def_partition (tree var
, void *arg_
)
1919 parm_default_def_partition_arg
*arg
= (parm_default_def_partition_arg
*)arg_
;
1920 var_map map
= arg
->first
;
1921 bitmap parts
= arg
->second
;
1923 if (!is_gimple_reg (var
))
1926 tree ssa
= ssa_default_def (cfun
, var
);
1929 int version
= var_to_partition (map
, ssa
);
1930 gcc_assert (version
!= NO_PARTITION
);
1932 bool changed
= bitmap_set_bit (parts
, version
);
1933 gcc_assert (changed
);
1936 /* Allocate and return a bitmap that has a bit set for each partition
1937 that contains a default def for a parameter. */
1940 get_parm_default_def_partitions (var_map map
)
1942 bitmap parm_default_def_parts
= BITMAP_ALLOC (NULL
);
1944 parm_default_def_partition_arg
1945 arg
= std::make_pair (map
, parm_default_def_parts
);
1947 for_all_parms (set_parm_default_def_partition
, &arg
);
1949 return parm_default_def_parts
;