2018-10-26 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / tree-ssa-coalesce.c
blob83b0c1fec8a44c67d4c1800f811b859695c1595c
1 /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 Copyright (C) 2004-2018 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "predict.h"
28 #include "memmodel.h"
29 #include "tm_p.h"
30 #include "ssa.h"
31 #include "tree-ssa.h"
32 #include "tree-pretty-print.h"
33 #include "diagnostic-core.h"
34 #include "dumpfile.h"
35 #include "gimple-iterator.h"
36 #include "tree-ssa-live.h"
37 #include "tree-ssa-coalesce.h"
38 #include "explow.h"
39 #include "tree-dfa.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. */
50 struct coalesce_pair
52 int first_element;
53 int second_element;
54 int cost;
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
59 conflict set.
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. */
65 int conflict_count;
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
69 pairs. */
70 int index;
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. */
77 struct ssa_conflicts
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_;
88 static var_map map_;
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. */
100 inline hashval_t
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. */
112 inline bool
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;
123 struct cost_one_pair
125 int first_element;
126 int second_element;
127 cost_one_pair *next;
130 /* This structure maintains the list of coalesce pairs. */
132 struct coalesce_list
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. */
146 static inline int
147 coalesce_cost (int frequency, bool optimize_for_size)
149 /* Base costs on BB frequencies bounded by 1. */
150 int cost = frequency;
152 if (!cost)
153 cost = 1;
155 if (optimize_for_size)
156 cost = 1;
158 return cost;
162 /* Return the cost of executing a copy instruction in basic block BB. */
164 static inline int
165 coalesce_cost_bb (basic_block bb)
167 return coalesce_cost (bb->count.to_frequency (cfun),
168 optimize_bb_for_size_p (bb));
172 /* Return the cost of executing a copy instruction on edge E. */
174 static inline int
175 coalesce_cost_edge (edge e)
177 int mult = 1;
179 /* Inserting copy on critical edge costs more than inserting it elsewhere. */
180 if (EDGE_CRITICAL_P (e))
181 mult = 2;
182 if (e->flags & EDGE_ABNORMAL)
183 return MUST_COALESCE_COST;
184 if (e->flags & EDGE_EH)
186 edge e2;
187 edge_iterator ei;
188 FOR_EACH_EDGE (e2, ei, e->dest->preds)
189 if (e2 != e)
191 /* Putting code on EH edge that leads to BB
192 with multiple predecestors imply splitting of
193 edge too. */
194 if (mult < 2)
195 mult = 2;
196 /* If there are multiple EH predecestors, we
197 also copy EH regions and produce separate
198 landing pad. This is expensive. */
199 if (e2->flags & EDGE_EH)
201 mult = 5;
202 break;
207 return coalesce_cost (EDGE_FREQUENCY (e),
208 optimize_edge_for_size_p (e)) * mult;
212 /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
213 2 elements via P1 and P2. 1 is returned by the function if there is a pair,
214 NO_BEST_COALESCE is returned if there aren't any. */
216 static inline int
217 pop_cost_one_pair (coalesce_list *cl, int *p1, int *p2)
219 cost_one_pair *ptr;
221 ptr = cl->cost_one_list;
222 if (!ptr)
223 return NO_BEST_COALESCE;
225 *p1 = ptr->first_element;
226 *p2 = ptr->second_element;
227 cl->cost_one_list = ptr->next;
229 free (ptr);
231 return 1;
234 /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
235 2 elements via P1 and P2. Their calculated cost is returned by the function.
236 NO_BEST_COALESCE is returned if the coalesce list is empty. */
238 static inline int
239 pop_best_coalesce (coalesce_list *cl, int *p1, int *p2)
241 coalesce_pair *node;
242 int ret;
244 if (cl->sorted == NULL)
245 return pop_cost_one_pair (cl, p1, p2);
247 if (cl->num_sorted == 0)
248 return pop_cost_one_pair (cl, p1, p2);
250 node = cl->sorted[--(cl->num_sorted)];
251 *p1 = node->first_element;
252 *p2 = node->second_element;
253 ret = node->cost;
254 free (node);
256 return ret;
260 /* Create a new empty coalesce list object and return it. */
262 static inline coalesce_list *
263 create_coalesce_list (void)
265 coalesce_list *list;
266 unsigned size = num_ssa_names * 3;
268 if (size < 40)
269 size = 40;
271 list = (coalesce_list *) xmalloc (sizeof (struct coalesce_list));
272 list->list = new coalesce_table_type (size);
273 list->sorted = NULL;
274 list->num_sorted = 0;
275 list->cost_one_list = NULL;
276 return list;
280 /* Delete coalesce list CL. */
282 static inline void
283 delete_coalesce_list (coalesce_list *cl)
285 gcc_assert (cl->cost_one_list == NULL);
286 delete cl->list;
287 cl->list = NULL;
288 free (cl->sorted);
289 gcc_assert (cl->num_sorted == 0);
290 free (cl);
293 /* Return the number of unique coalesce pairs in CL. */
295 static inline int
296 num_coalesce_pairs (coalesce_list *cl)
298 return cl->list->elements ();
301 /* Find a matching coalesce pair object in CL for the pair P1 and P2. If
302 one isn't found, return NULL if CREATE is false, otherwise create a new
303 coalesce pair object and return it. */
305 static coalesce_pair *
306 find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
308 struct coalesce_pair p;
309 coalesce_pair **slot;
310 unsigned int hash;
312 /* Normalize so that p1 is the smaller value. */
313 if (p2 < p1)
315 p.first_element = p2;
316 p.second_element = p1;
318 else
320 p.first_element = p1;
321 p.second_element = p2;
324 hash = coalesce_pair_hasher::hash (&p);
325 slot = cl->list->find_slot_with_hash (&p, hash, create ? INSERT : NO_INSERT);
326 if (!slot)
327 return NULL;
329 if (!*slot)
331 struct coalesce_pair * pair = XNEW (struct coalesce_pair);
332 gcc_assert (cl->sorted == NULL);
333 pair->first_element = p.first_element;
334 pair->second_element = p.second_element;
335 pair->cost = 0;
336 pair->index = num_coalesce_pairs (cl);
337 pair->conflict_count = 0;
338 *slot = pair;
341 return (struct coalesce_pair *) *slot;
344 static inline void
345 add_cost_one_coalesce (coalesce_list *cl, int p1, int p2)
347 cost_one_pair *pair;
349 pair = XNEW (cost_one_pair);
350 pair->first_element = p1;
351 pair->second_element = p2;
352 pair->next = cl->cost_one_list;
353 cl->cost_one_list = pair;
357 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
359 static inline void
360 add_coalesce (coalesce_list *cl, int p1, int p2, int value)
362 coalesce_pair *node;
364 gcc_assert (cl->sorted == NULL);
365 if (p1 == p2)
366 return;
368 node = find_coalesce_pair (cl, p1, p2, true);
370 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
371 if (node->cost < MUST_COALESCE_COST - 1)
373 if (value < MUST_COALESCE_COST - 1)
374 node->cost += value;
375 else
376 node->cost = value;
380 /* Compute and record how many unique conflicts would exist for the
381 representative partition for each coalesce pair in CL.
383 CONFLICTS is the conflict graph and MAP is the current partition view. */
385 static void
386 initialize_conflict_count (coalesce_pair *p,
387 ssa_conflicts *conflicts,
388 var_map map)
390 int p1 = var_to_partition (map, ssa_name (p->first_element));
391 int p2 = var_to_partition (map, ssa_name (p->second_element));
393 /* 4 cases. If both P1 and P2 have conflicts, then build their
394 union and count the members. Else handle the degenerate cases
395 in the obvious ways. */
396 if (conflicts->conflicts[p1] && conflicts->conflicts[p2])
397 p->conflict_count = bitmap_count_unique_bits (conflicts->conflicts[p1],
398 conflicts->conflicts[p2]);
399 else if (conflicts->conflicts[p1])
400 p->conflict_count = bitmap_count_bits (conflicts->conflicts[p1]);
401 else if (conflicts->conflicts[p2])
402 p->conflict_count = bitmap_count_bits (conflicts->conflicts[p2]);
403 else
404 p->conflict_count = 0;
408 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
410 static int
411 compare_pairs (const void *p1, const void *p2)
413 coalesce_pair *const *const pp1 = (coalesce_pair *const *) p1;
414 coalesce_pair *const *const pp2 = (coalesce_pair *const *) p2;
415 int result;
417 result = (* pp1)->cost - (* pp2)->cost;
418 /* We use the size of the resulting conflict set as the secondary sort key.
419 Given two equal costing coalesce pairs, we want to prefer the pair that
420 has the smaller conflict set. */
421 if (result == 0)
423 if (flag_expensive_optimizations)
425 /* Lazily initialize the conflict counts as it's fairly expensive
426 to compute. */
427 if ((*pp2)->conflict_count == 0)
428 initialize_conflict_count (*pp2, conflicts_, map_);
429 if ((*pp1)->conflict_count == 0)
430 initialize_conflict_count (*pp1, conflicts_, map_);
432 result = (*pp2)->conflict_count - (*pp1)->conflict_count;
435 /* And if everything else is equal, then sort based on which
436 coalesce pair was found first. */
437 if (result == 0)
438 result = (*pp2)->index - (*pp1)->index;
441 return result;
444 /* Iterate over CL using ITER, returning values in PAIR. */
446 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
447 FOR_EACH_HASH_TABLE_ELEMENT (*(CL)->list, (PAIR), coalesce_pair_p, (ITER))
450 /* Prepare CL for removal of preferred pairs. When finished they are sorted
451 in order from most important coalesce to least important. */
453 static void
454 sort_coalesce_list (coalesce_list *cl, ssa_conflicts *conflicts, var_map map)
456 unsigned x, num;
457 coalesce_pair *p;
458 coalesce_iterator_type ppi;
460 gcc_assert (cl->sorted == NULL);
462 num = num_coalesce_pairs (cl);
463 cl->num_sorted = num;
464 if (num == 0)
465 return;
467 /* Allocate a vector for the pair pointers. */
468 cl->sorted = XNEWVEC (coalesce_pair *, num);
470 /* Populate the vector with pointers to the pairs. */
471 x = 0;
472 FOR_EACH_PARTITION_PAIR (p, ppi, cl)
473 cl->sorted[x++] = p;
474 gcc_assert (x == num);
476 /* Already sorted. */
477 if (num == 1)
478 return;
480 /* We don't want to depend on qsort_r, so we have to stuff away
481 additional data into globals so it can be referenced in
482 compare_pairs. */
483 conflicts_ = conflicts;
484 map_ = map;
485 qsort (cl->sorted, num, sizeof (coalesce_pair *), compare_pairs);
486 conflicts_ = NULL;
487 map_ = NULL;
491 /* Send debug info for coalesce list CL to file F. */
493 static void
494 dump_coalesce_list (FILE *f, coalesce_list *cl)
496 coalesce_pair *node;
497 coalesce_iterator_type ppi;
499 int x;
500 tree var;
502 if (cl->sorted == NULL)
504 fprintf (f, "Coalesce List:\n");
505 FOR_EACH_PARTITION_PAIR (node, ppi, cl)
507 tree var1 = ssa_name (node->first_element);
508 tree var2 = ssa_name (node->second_element);
509 print_generic_expr (f, var1, TDF_SLIM);
510 fprintf (f, " <-> ");
511 print_generic_expr (f, var2, TDF_SLIM);
512 fprintf (f, " (%1d, %1d), ", node->cost, node->conflict_count);
513 fprintf (f, "\n");
516 else
518 fprintf (f, "Sorted Coalesce list:\n");
519 for (x = cl->num_sorted - 1 ; x >=0; x--)
521 node = cl->sorted[x];
522 fprintf (f, "(%d, %d) ", node->cost, node->conflict_count);
523 var = ssa_name (node->first_element);
524 print_generic_expr (f, var, TDF_SLIM);
525 fprintf (f, " <-> ");
526 var = ssa_name (node->second_element);
527 print_generic_expr (f, var, TDF_SLIM);
528 fprintf (f, "\n");
534 /* Return an empty new conflict graph for SIZE elements. */
536 static inline ssa_conflicts *
537 ssa_conflicts_new (unsigned size)
539 ssa_conflicts *ptr;
541 ptr = XNEW (ssa_conflicts);
542 bitmap_obstack_initialize (&ptr->obstack);
543 ptr->conflicts.create (size);
544 ptr->conflicts.safe_grow_cleared (size);
545 return ptr;
549 /* Free storage for conflict graph PTR. */
551 static inline void
552 ssa_conflicts_delete (ssa_conflicts *ptr)
554 bitmap_obstack_release (&ptr->obstack);
555 ptr->conflicts.release ();
556 free (ptr);
560 /* Test if elements X and Y conflict in graph PTR. */
562 static inline bool
563 ssa_conflicts_test_p (ssa_conflicts *ptr, unsigned x, unsigned y)
565 bitmap bx = ptr->conflicts[x];
566 bitmap by = ptr->conflicts[y];
568 gcc_checking_assert (x != y);
570 if (bx)
571 /* Avoid the lookup if Y has no conflicts. */
572 return by ? bitmap_bit_p (bx, y) : false;
573 else
574 return false;
578 /* Add a conflict with Y to the bitmap for X in graph PTR. */
580 static inline void
581 ssa_conflicts_add_one (ssa_conflicts *ptr, unsigned x, unsigned y)
583 bitmap bx = ptr->conflicts[x];
584 /* If there are no conflicts yet, allocate the bitmap and set bit. */
585 if (! bx)
586 bx = ptr->conflicts[x] = BITMAP_ALLOC (&ptr->obstack);
587 bitmap_set_bit (bx, y);
591 /* Add conflicts between X and Y in graph PTR. */
593 static inline void
594 ssa_conflicts_add (ssa_conflicts *ptr, unsigned x, unsigned y)
596 gcc_checking_assert (x != y);
597 ssa_conflicts_add_one (ptr, x, y);
598 ssa_conflicts_add_one (ptr, y, x);
602 /* Merge all Y's conflict into X in graph PTR. */
604 static inline void
605 ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y)
607 unsigned z;
608 bitmap_iterator bi;
609 bitmap bx = ptr->conflicts[x];
610 bitmap by = ptr->conflicts[y];
612 gcc_checking_assert (x != y);
613 if (! by)
614 return;
616 /* Add a conflict between X and every one Y has. If the bitmap doesn't
617 exist, then it has already been coalesced, and we don't need to add a
618 conflict. */
619 EXECUTE_IF_SET_IN_BITMAP (by, 0, z, bi)
621 bitmap bz = ptr->conflicts[z];
622 if (bz)
624 bool was_there = bitmap_clear_bit (bz, y);
625 gcc_checking_assert (was_there);
626 bitmap_set_bit (bz, x);
630 if (bx)
632 /* If X has conflicts, add Y's to X. */
633 bitmap_ior_into (bx, by);
634 BITMAP_FREE (by);
635 ptr->conflicts[y] = NULL;
637 else
639 /* If X has no conflicts, simply use Y's. */
640 ptr->conflicts[x] = by;
641 ptr->conflicts[y] = NULL;
646 /* Dump a conflicts graph. */
648 static void
649 ssa_conflicts_dump (FILE *file, ssa_conflicts *ptr)
651 unsigned x;
652 bitmap b;
654 fprintf (file, "\nConflict graph:\n");
656 FOR_EACH_VEC_ELT (ptr->conflicts, x, b)
657 if (b)
659 fprintf (file, "%d: ", x);
660 dump_bitmap (file, b);
665 /* This structure is used to efficiently record the current status of live
666 SSA_NAMES when building a conflict graph.
667 LIVE_BASE_VAR has a bit set for each base variable which has at least one
668 ssa version live.
669 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
670 index, and is used to track what partitions of each base variable are
671 live. This makes it easy to add conflicts between just live partitions
672 with the same base variable.
673 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
674 marked as being live. This delays clearing of these bitmaps until
675 they are actually needed again. */
677 struct live_track
679 bitmap_obstack obstack; /* A place to allocate our bitmaps. */
680 bitmap live_base_var; /* Indicates if a basevar is live. */
681 bitmap *live_base_partitions; /* Live partitions for each basevar. */
682 var_map map; /* Var_map being used for partition mapping. */
686 /* This routine will create a new live track structure based on the partitions
687 in MAP. */
689 static live_track *
690 new_live_track (var_map map)
692 live_track *ptr;
693 int lim, x;
695 /* Make sure there is a partition view in place. */
696 gcc_assert (map->partition_to_base_index != NULL);
698 ptr = (live_track *) xmalloc (sizeof (live_track));
699 ptr->map = map;
700 lim = num_basevars (map);
701 bitmap_obstack_initialize (&ptr->obstack);
702 ptr->live_base_partitions = (bitmap *) xmalloc (sizeof (bitmap *) * lim);
703 ptr->live_base_var = BITMAP_ALLOC (&ptr->obstack);
704 for (x = 0; x < lim; x++)
705 ptr->live_base_partitions[x] = BITMAP_ALLOC (&ptr->obstack);
706 return ptr;
710 /* This routine will free the memory associated with PTR. */
712 static void
713 delete_live_track (live_track *ptr)
715 bitmap_obstack_release (&ptr->obstack);
716 free (ptr->live_base_partitions);
717 free (ptr);
721 /* This function will remove PARTITION from the live list in PTR. */
723 static inline void
724 live_track_remove_partition (live_track *ptr, int partition)
726 int root;
728 root = basevar_index (ptr->map, partition);
729 bitmap_clear_bit (ptr->live_base_partitions[root], partition);
730 /* If the element list is empty, make the base variable not live either. */
731 if (bitmap_empty_p (ptr->live_base_partitions[root]))
732 bitmap_clear_bit (ptr->live_base_var, root);
736 /* This function will adds PARTITION to the live list in PTR. */
738 static inline void
739 live_track_add_partition (live_track *ptr, int partition)
741 int root;
743 root = basevar_index (ptr->map, partition);
744 /* If this base var wasn't live before, it is now. Clear the element list
745 since it was delayed until needed. */
746 if (bitmap_set_bit (ptr->live_base_var, root))
747 bitmap_clear (ptr->live_base_partitions[root]);
748 bitmap_set_bit (ptr->live_base_partitions[root], partition);
753 /* Clear the live bit for VAR in PTR. */
755 static inline void
756 live_track_clear_var (live_track *ptr, tree var)
758 int p;
760 p = var_to_partition (ptr->map, var);
761 if (p != NO_PARTITION)
762 live_track_remove_partition (ptr, p);
766 /* Return TRUE if VAR is live in PTR. */
768 static inline bool
769 live_track_live_p (live_track *ptr, tree var)
771 int p, root;
773 p = var_to_partition (ptr->map, var);
774 if (p != NO_PARTITION)
776 root = basevar_index (ptr->map, p);
777 if (bitmap_bit_p (ptr->live_base_var, root))
778 return bitmap_bit_p (ptr->live_base_partitions[root], p);
780 return false;
784 /* This routine will add USE to PTR. USE will be marked as live in both the
785 ssa live map and the live bitmap for the root of USE. */
787 static inline void
788 live_track_process_use (live_track *ptr, tree use)
790 int p;
792 p = var_to_partition (ptr->map, use);
793 if (p == NO_PARTITION)
794 return;
796 /* Mark as live in the appropriate live list. */
797 live_track_add_partition (ptr, p);
801 /* This routine will process a DEF in PTR. DEF will be removed from the live
802 lists, and if there are any other live partitions with the same base
803 variable, conflicts will be added to GRAPH. */
805 static inline void
806 live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph)
808 int p, root;
809 bitmap b;
810 unsigned x;
811 bitmap_iterator bi;
813 p = var_to_partition (ptr->map, def);
814 if (p == NO_PARTITION)
815 return;
817 /* Clear the liveness bit. */
818 live_track_remove_partition (ptr, p);
820 /* If the bitmap isn't empty now, conflicts need to be added. */
821 root = basevar_index (ptr->map, p);
822 if (bitmap_bit_p (ptr->live_base_var, root))
824 b = ptr->live_base_partitions[root];
825 EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
826 ssa_conflicts_add (graph, p, x);
831 /* Initialize PTR with the partitions set in INIT. */
833 static inline void
834 live_track_init (live_track *ptr, bitmap init)
836 unsigned p;
837 bitmap_iterator bi;
839 /* Mark all live on exit partitions. */
840 EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
841 live_track_add_partition (ptr, p);
845 /* This routine will clear all live partitions in PTR. */
847 static inline void
848 live_track_clear_base_vars (live_track *ptr)
850 /* Simply clear the live base list. Anything marked as live in the element
851 lists will be cleared later if/when the base variable ever comes alive
852 again. */
853 bitmap_clear (ptr->live_base_var);
857 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
858 partition view of the var_map liveinfo is based on get entries in the
859 conflict graph. Only conflicts between ssa_name partitions with the same
860 base variable are added. */
862 static ssa_conflicts *
863 build_ssa_conflict_graph (tree_live_info_p liveinfo)
865 ssa_conflicts *graph;
866 var_map map;
867 basic_block bb;
868 ssa_op_iter iter;
869 live_track *live;
870 basic_block entry;
872 /* If inter-variable coalescing is enabled, we may attempt to
873 coalesce variables from different base variables, including
874 different parameters, so we have to make sure default defs live
875 at the entry block conflict with each other. */
876 if (flag_tree_coalesce_vars)
877 entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
878 else
879 entry = NULL;
881 map = live_var_map (liveinfo);
882 graph = ssa_conflicts_new (num_var_partitions (map));
884 live = new_live_track (map);
886 for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
888 /* Start with live on exit temporaries. */
889 live_track_init (live, live_on_exit (liveinfo, bb));
891 for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
892 gsi_prev (&gsi))
894 tree var;
895 gimple *stmt = gsi_stmt (gsi);
897 /* A copy between 2 partitions does not introduce an interference
898 by itself. If they did, you would never be able to coalesce
899 two things which are copied. If the two variables really do
900 conflict, they will conflict elsewhere in the program.
902 This is handled by simply removing the SRC of the copy from the
903 live list, and processing the stmt normally. */
904 if (is_gimple_assign (stmt))
906 tree lhs = gimple_assign_lhs (stmt);
907 tree rhs1 = gimple_assign_rhs1 (stmt);
908 if (gimple_assign_copy_p (stmt)
909 && TREE_CODE (lhs) == SSA_NAME
910 && TREE_CODE (rhs1) == SSA_NAME)
911 live_track_clear_var (live, rhs1);
913 else if (is_gimple_debug (stmt))
914 continue;
916 /* For stmts with more than one SSA_NAME definition pretend all the
917 SSA_NAME outputs but the first one are live at this point, so
918 that conflicts are added in between all those even when they are
919 actually not really live after the asm, because expansion might
920 copy those into pseudos after the asm and if multiple outputs
921 share the same partition, it might overwrite those that should
922 be live. E.g.
923 asm volatile (".." : "=r" (a) : "=r" (b) : "0" (a), "1" (a));
924 return a;
925 See PR70593. */
926 bool first = true;
927 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
928 if (first)
929 first = false;
930 else
931 live_track_process_use (live, var);
933 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
934 live_track_process_def (live, var, graph);
936 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
937 live_track_process_use (live, var);
940 /* If result of a PHI is unused, looping over the statements will not
941 record any conflicts since the def was never live. Since the PHI node
942 is going to be translated out of SSA form, it will insert a copy.
943 There must be a conflict recorded between the result of the PHI and
944 any variables that are live. Otherwise the out-of-ssa translation
945 may create incorrect code. */
946 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
947 gsi_next (&gsi))
949 gphi *phi = gsi.phi ();
950 tree result = PHI_RESULT (phi);
951 if (virtual_operand_p (result))
952 continue;
953 if (live_track_live_p (live, result))
954 live_track_process_def (live, result, graph);
957 /* Pretend there are defs for params' default defs at the start
958 of the (post-)entry block. This will prevent PARM_DECLs from
959 coalescing into the same partition. Although RESULT_DECLs'
960 default defs don't have a useful initial value, we have to
961 prevent them from coalescing with PARM_DECLs' default defs
962 too, otherwise assign_parms would attempt to assign different
963 RTL to the same partition. */
964 if (bb == entry)
966 unsigned i;
967 tree var;
969 FOR_EACH_SSA_NAME (i, var, cfun)
971 if (!SSA_NAME_IS_DEFAULT_DEF (var)
972 || !SSA_NAME_VAR (var)
973 || VAR_P (SSA_NAME_VAR (var)))
974 continue;
976 live_track_process_def (live, var, graph);
977 /* Process a use too, so that it remains live and
978 conflicts with other parms' default defs, even unused
979 ones. */
980 live_track_process_use (live, var);
984 live_track_clear_base_vars (live);
987 delete_live_track (live);
988 return graph;
991 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
993 static inline void
994 fail_abnormal_edge_coalesce (int x, int y)
996 fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
997 fprintf (stderr, " which are marked as MUST COALESCE.\n");
998 print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
999 fprintf (stderr, " and ");
1000 print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
1002 internal_error ("SSA corruption");
1005 /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
1006 and the DECL's default def is unused (i.e., it was introduced by
1007 create_default_def for out-of-ssa), mark VAR and the default def for
1008 coalescing. */
1010 static void
1011 coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
1013 if (SSA_NAME_IS_DEFAULT_DEF (var)
1014 || !SSA_NAME_VAR (var)
1015 || VAR_P (SSA_NAME_VAR (var)))
1016 return;
1018 tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var));
1019 if (!has_zero_uses (ssa))
1020 return;
1022 add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var));
1023 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1024 /* Default defs will have their used_in_copy bits set at the beginning of
1025 populate_coalesce_list_for_outofssa. */
1029 /* Given var_map MAP for a region, this function creates and returns a coalesce
1030 list as well as recording related ssa names in USED_IN_COPIES for use later
1031 in the out-of-ssa or live range computation process. */
1033 static coalesce_list *
1034 create_coalesce_list_for_region (var_map map, bitmap used_in_copy)
1036 gimple_stmt_iterator gsi;
1037 basic_block bb;
1038 coalesce_list *cl = create_coalesce_list ();
1039 gimple *stmt;
1040 int v1, v2, cost;
1042 for (unsigned j = 0; map->vec_bbs.iterate (j, &bb); ++j)
1044 tree arg;
1046 for (gphi_iterator gpi = gsi_start_phis (bb);
1047 !gsi_end_p (gpi);
1048 gsi_next (&gpi))
1050 gphi *phi = gpi.phi ();
1051 size_t i;
1052 int ver;
1053 tree res;
1054 bool saw_copy = false;
1056 res = gimple_phi_result (phi);
1057 if (virtual_operand_p (res))
1058 continue;
1059 ver = SSA_NAME_VERSION (res);
1061 /* Register ssa_names and coalesces between the args and the result
1062 of all PHI. */
1063 for (i = 0; i < gimple_phi_num_args (phi); i++)
1065 edge e = gimple_phi_arg_edge (phi, i);
1066 arg = PHI_ARG_DEF (phi, i);
1067 if (TREE_CODE (arg) != SSA_NAME)
1068 continue;
1070 if (gimple_can_coalesce_p (arg, res)
1071 || (e->flags & EDGE_ABNORMAL))
1073 saw_copy = true;
1074 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1075 if ((e->flags & EDGE_ABNORMAL) == 0)
1077 int cost = coalesce_cost_edge (e);
1078 if (cost == 1 && has_single_use (arg))
1079 add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1080 else
1081 add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1085 if (saw_copy)
1086 bitmap_set_bit (used_in_copy, ver);
1089 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1091 stmt = gsi_stmt (gsi);
1093 if (is_gimple_debug (stmt))
1094 continue;
1096 /* Check for copy coalesces. */
1097 switch (gimple_code (stmt))
1099 case GIMPLE_ASSIGN:
1101 tree lhs = gimple_assign_lhs (stmt);
1102 tree rhs1 = gimple_assign_rhs1 (stmt);
1103 if (gimple_assign_ssa_name_copy_p (stmt)
1104 && gimple_can_coalesce_p (lhs, rhs1))
1106 v1 = SSA_NAME_VERSION (lhs);
1107 v2 = SSA_NAME_VERSION (rhs1);
1108 cost = coalesce_cost_bb (bb);
1109 add_coalesce (cl, v1, v2, cost);
1110 bitmap_set_bit (used_in_copy, v1);
1111 bitmap_set_bit (used_in_copy, v2);
1114 break;
1116 case GIMPLE_RETURN:
1118 tree res = DECL_RESULT (current_function_decl);
1119 if (VOID_TYPE_P (TREE_TYPE (res))
1120 || !is_gimple_reg (res))
1121 break;
1122 tree rhs1 = gimple_return_retval (as_a <greturn *> (stmt));
1123 if (!rhs1)
1124 break;
1125 tree lhs = ssa_default_def (cfun, res);
1126 gcc_assert (lhs);
1127 if (TREE_CODE (rhs1) == SSA_NAME
1128 && gimple_can_coalesce_p (lhs, rhs1))
1130 v1 = SSA_NAME_VERSION (lhs);
1131 v2 = SSA_NAME_VERSION (rhs1);
1132 cost = coalesce_cost_bb (bb);
1133 add_coalesce (cl, v1, v2, cost);
1134 bitmap_set_bit (used_in_copy, v1);
1135 bitmap_set_bit (used_in_copy, v2);
1137 break;
1140 case GIMPLE_ASM:
1142 gasm *asm_stmt = as_a <gasm *> (stmt);
1143 unsigned long noutputs, i;
1144 unsigned long ninputs;
1145 tree *outputs, link;
1146 noutputs = gimple_asm_noutputs (asm_stmt);
1147 ninputs = gimple_asm_ninputs (asm_stmt);
1148 outputs = (tree *) alloca (noutputs * sizeof (tree));
1149 for (i = 0; i < noutputs; ++i)
1151 link = gimple_asm_output_op (asm_stmt, i);
1152 outputs[i] = TREE_VALUE (link);
1155 for (i = 0; i < ninputs; ++i)
1157 const char *constraint;
1158 tree input;
1159 char *end;
1160 unsigned long match;
1162 link = gimple_asm_input_op (asm_stmt, i);
1163 constraint
1164 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1165 input = TREE_VALUE (link);
1167 if (TREE_CODE (input) != SSA_NAME)
1168 continue;
1170 match = strtoul (constraint, &end, 10);
1171 if (match >= noutputs || end == constraint)
1172 continue;
1174 if (TREE_CODE (outputs[match]) != SSA_NAME)
1175 continue;
1177 v1 = SSA_NAME_VERSION (outputs[match]);
1178 v2 = SSA_NAME_VERSION (input);
1180 if (gimple_can_coalesce_p (outputs[match], input))
1182 cost = coalesce_cost (REG_BR_PROB_BASE,
1183 optimize_bb_for_size_p (bb));
1184 add_coalesce (cl, v1, v2, cost);
1185 bitmap_set_bit (used_in_copy, v1);
1186 bitmap_set_bit (used_in_copy, v2);
1189 break;
1192 default:
1193 break;
1198 return cl;
1202 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1204 struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
1206 static inline hashval_t hash (const tree_node *);
1207 static inline int equal (const tree_node *, const tree_node *);
1210 inline hashval_t
1211 ssa_name_var_hash::hash (const_tree n)
1213 return DECL_UID (SSA_NAME_VAR (n));
1216 inline int
1217 ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
1219 return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
1223 /* This function populates coalesce list CL as well as recording related ssa
1224 names in USED_IN_COPIES for use later in the out-of-ssa process. */
1226 static void
1227 populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy)
1229 tree var;
1230 tree first;
1231 int v1, v2, cost;
1232 unsigned i;
1234 /* Process result decls and live on entry variables for entry into the
1235 coalesce list. */
1236 first = NULL_TREE;
1237 FOR_EACH_SSA_NAME (i, var, cfun)
1239 if (!virtual_operand_p (var))
1241 coalesce_with_default (var, cl, used_in_copy);
1243 /* Add coalesces between all the result decls. */
1244 if (SSA_NAME_VAR (var)
1245 && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1247 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1248 if (first == NULL_TREE)
1249 first = var;
1250 else
1252 gcc_assert (gimple_can_coalesce_p (var, first));
1253 v1 = SSA_NAME_VERSION (first);
1254 v2 = SSA_NAME_VERSION (var);
1255 cost = coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
1256 add_coalesce (cl, v1, v2, cost);
1259 /* Mark any default_def variables as being in the coalesce list
1260 since they will have to be coalesced with the base variable. If
1261 not marked as present, they won't be in the coalesce view. */
1262 if (SSA_NAME_IS_DEFAULT_DEF (var)
1263 && (!has_zero_uses (var)
1264 || (SSA_NAME_VAR (var)
1265 && !VAR_P (SSA_NAME_VAR (var)))))
1266 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1270 /* If this optimization is disabled, we need to coalesce all the
1271 names originating from the same SSA_NAME_VAR so debug info
1272 remains undisturbed. */
1273 if (!flag_tree_coalesce_vars)
1275 tree a;
1276 hash_table<ssa_name_var_hash> ssa_name_hash (10);
1278 FOR_EACH_SSA_NAME (i, a, cfun)
1280 if (SSA_NAME_VAR (a)
1281 && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1282 && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
1283 || !VAR_P (SSA_NAME_VAR (a))))
1285 tree *slot = ssa_name_hash.find_slot (a, INSERT);
1287 if (!*slot)
1288 *slot = a;
1289 else
1291 /* If the variable is a PARM_DECL or a RESULT_DECL, we
1292 _require_ that all the names originating from it be
1293 coalesced, because there must be a single partition
1294 containing all the names so that it can be assigned
1295 the canonical RTL location of the DECL safely.
1296 If in_lto_p, a function could have been compiled
1297 originally with optimizations and only the link
1298 performed at -O0, so we can't actually require it. */
1299 const int cost
1300 = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p)
1301 ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
1302 add_coalesce (cl, SSA_NAME_VERSION (a),
1303 SSA_NAME_VERSION (*slot), cost);
1304 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a));
1305 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot));
1313 /* Attempt to coalesce ssa versions X and Y together using the partition
1314 mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1315 DEBUG, if it is nun-NULL. */
1317 static inline bool
1318 attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y,
1319 FILE *debug)
1321 int z;
1322 tree var1, var2;
1323 int p1, p2;
1325 p1 = var_to_partition (map, ssa_name (x));
1326 p2 = var_to_partition (map, ssa_name (y));
1328 if (debug)
1330 fprintf (debug, "(%d)", x);
1331 print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1332 fprintf (debug, " & (%d)", y);
1333 print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1336 if (p1 == p2)
1338 if (debug)
1339 fprintf (debug, ": Already Coalesced.\n");
1340 return true;
1343 if (debug)
1344 fprintf (debug, " [map: %d, %d] ", p1, p2);
1347 if (!ssa_conflicts_test_p (graph, p1, p2))
1349 var1 = partition_to_var (map, p1);
1350 var2 = partition_to_var (map, p2);
1352 z = var_union (map, var1, var2);
1353 if (z == NO_PARTITION)
1355 if (debug)
1356 fprintf (debug, ": Unable to perform partition union.\n");
1357 return false;
1360 /* z is the new combined partition. Remove the other partition from
1361 the list, and merge the conflicts. */
1362 if (z == p1)
1363 ssa_conflicts_merge (graph, p1, p2);
1364 else
1365 ssa_conflicts_merge (graph, p2, p1);
1367 if (debug)
1368 fprintf (debug, ": Success -> %d\n", z);
1370 return true;
1373 if (debug)
1374 fprintf (debug, ": Fail due to conflict\n");
1376 return false;
1380 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1381 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1383 static void
1384 coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
1385 FILE *debug)
1387 int x = 0, y = 0;
1388 tree var1, var2;
1389 int cost;
1390 basic_block bb;
1391 edge e;
1392 edge_iterator ei;
1394 /* First, coalesce all the copies across abnormal edges. These are not placed
1395 in the coalesce list because they do not need to be sorted, and simply
1396 consume extra memory/compilation time in large programs. */
1398 FOR_EACH_BB_FN (bb, cfun)
1400 FOR_EACH_EDGE (e, ei, bb->preds)
1401 if (e->flags & EDGE_ABNORMAL)
1403 gphi_iterator gsi;
1404 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1405 gsi_next (&gsi))
1407 gphi *phi = gsi.phi ();
1408 tree res = PHI_RESULT (phi);
1409 if (virtual_operand_p (res))
1410 continue;
1411 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1412 if (SSA_NAME_IS_DEFAULT_DEF (arg)
1413 && (!SSA_NAME_VAR (arg)
1414 || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1415 continue;
1417 int v1 = SSA_NAME_VERSION (res);
1418 int v2 = SSA_NAME_VERSION (arg);
1420 if (debug)
1421 fprintf (debug, "Abnormal coalesce: ");
1423 if (!attempt_coalesce (map, graph, v1, v2, debug))
1424 fail_abnormal_edge_coalesce (v1, v2);
1429 /* Now process the items in the coalesce list. */
1431 while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1433 var1 = ssa_name (x);
1434 var2 = ssa_name (y);
1436 /* Assert the coalesces have the same base variable. */
1437 gcc_assert (gimple_can_coalesce_p (var1, var2));
1439 if (debug)
1440 fprintf (debug, "Coalesce list: ");
1441 attempt_coalesce (map, graph, x, y, debug);
1446 /* Output partition map MAP with coalescing plan PART to file F. */
1448 void
1449 dump_part_var_map (FILE *f, partition part, var_map map)
1451 int t;
1452 unsigned x, y;
1453 int p;
1455 fprintf (f, "\nCoalescible Partition map \n\n");
1457 for (x = 0; x < map->num_partitions; x++)
1459 if (map->view_to_partition != NULL)
1460 p = map->view_to_partition[x];
1461 else
1462 p = x;
1464 if (ssa_name (p) == NULL_TREE
1465 || virtual_operand_p (ssa_name (p)))
1466 continue;
1468 t = 0;
1469 for (y = 1; y < num_ssa_names; y++)
1471 tree var = version_to_var (map, y);
1472 if (!var)
1473 continue;
1474 int q = var_to_partition (map, var);
1475 p = partition_find (part, q);
1476 gcc_assert (map->partition_to_base_index[q]
1477 == map->partition_to_base_index[p]);
1479 if (p == (int)x)
1481 if (t++ == 0)
1483 fprintf (f, "Partition %d, base %d (", x,
1484 map->partition_to_base_index[q]);
1485 print_generic_expr (f, partition_to_var (map, q), TDF_SLIM);
1486 fprintf (f, " - ");
1488 fprintf (f, "%d ", y);
1491 if (t != 0)
1492 fprintf (f, ")\n");
1494 fprintf (f, "\n");
1497 /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
1498 coalescing together, false otherwise.
1500 This must stay consistent with compute_samebase_partition_bases and
1501 compute_optimized_partition_bases. */
1503 bool
1504 gimple_can_coalesce_p (tree name1, tree name2)
1506 /* First check the SSA_NAME's associated DECL. Without
1507 optimization, we only want to coalesce if they have the same DECL
1508 or both have no associated DECL. */
1509 tree var1 = SSA_NAME_VAR (name1);
1510 tree var2 = SSA_NAME_VAR (name2);
1511 var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
1512 var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
1513 if (var1 != var2 && !flag_tree_coalesce_vars)
1514 return false;
1516 /* Now check the types. If the types are the same, then we should
1517 try to coalesce V1 and V2. */
1518 tree t1 = TREE_TYPE (name1);
1519 tree t2 = TREE_TYPE (name2);
1520 if (t1 == t2)
1522 check_modes:
1523 /* If the base variables are the same, we're good: none of the
1524 other tests below could possibly fail. */
1525 var1 = SSA_NAME_VAR (name1);
1526 var2 = SSA_NAME_VAR (name2);
1527 if (var1 == var2)
1528 return true;
1530 /* We don't want to coalesce two SSA names if one of the base
1531 variables is supposed to be a register while the other is
1532 supposed to be on the stack. Anonymous SSA names most often
1533 take registers, but when not optimizing, user variables
1534 should go on the stack, so coalescing them with the anonymous
1535 variable as the partition leader would end up assigning the
1536 user variable to a register. Don't do that! */
1537 bool reg1 = use_register_for_decl (name1);
1538 bool reg2 = use_register_for_decl (name2);
1539 if (reg1 != reg2)
1540 return false;
1542 /* Check that the promoted modes and unsignedness are the same.
1543 We don't want to coalesce if the promoted modes would be
1544 different, or if they would sign-extend differently. Only
1545 PARM_DECLs and RESULT_DECLs have different promotion rules,
1546 so skip the test if both are variables, or both are anonymous
1547 SSA_NAMEs. */
1548 int unsigned1, unsigned2;
1549 return ((!var1 || VAR_P (var1)) && (!var2 || VAR_P (var2)))
1550 || ((promote_ssa_mode (name1, &unsigned1)
1551 == promote_ssa_mode (name2, &unsigned2))
1552 && unsigned1 == unsigned2);
1555 /* If alignment requirements are different, we can't coalesce. */
1556 if (MINIMUM_ALIGNMENT (t1,
1557 var1 ? DECL_MODE (var1) : TYPE_MODE (t1),
1558 var1 ? LOCAL_DECL_ALIGNMENT (var1) : TYPE_ALIGN (t1))
1559 != MINIMUM_ALIGNMENT (t2,
1560 var2 ? DECL_MODE (var2) : TYPE_MODE (t2),
1561 var2 ? LOCAL_DECL_ALIGNMENT (var2) : TYPE_ALIGN (t2)))
1562 return false;
1564 /* If the types are not the same, see whether they are compatible. This
1565 (for example) allows coalescing when the types are fundamentally the
1566 same, but just have different names. */
1567 if (types_compatible_p (t1, t2))
1568 goto check_modes;
1570 return false;
1573 /* Fill in MAP's partition_to_base_index, with one index for each
1574 partition of SSA names USED_IN_COPIES and related by CL coalesce
1575 possibilities. This must match gimple_can_coalesce_p in the
1576 optimized case. */
1578 static void
1579 compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1580 coalesce_list *cl)
1582 int parts = num_var_partitions (map);
1583 partition tentative = partition_new (parts);
1585 /* Partition the SSA versions so that, for each coalescible
1586 pair, both of its members are in the same partition in
1587 TENTATIVE. */
1588 gcc_assert (!cl->sorted);
1589 coalesce_pair *node;
1590 coalesce_iterator_type ppi;
1591 FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1593 tree v1 = ssa_name (node->first_element);
1594 int p1 = partition_find (tentative, var_to_partition (map, v1));
1595 tree v2 = ssa_name (node->second_element);
1596 int p2 = partition_find (tentative, var_to_partition (map, v2));
1598 if (p1 == p2)
1599 continue;
1601 partition_union (tentative, p1, p2);
1604 /* We have to deal with cost one pairs too. */
1605 for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1607 tree v1 = ssa_name (co->first_element);
1608 int p1 = partition_find (tentative, var_to_partition (map, v1));
1609 tree v2 = ssa_name (co->second_element);
1610 int p2 = partition_find (tentative, var_to_partition (map, v2));
1612 if (p1 == p2)
1613 continue;
1615 partition_union (tentative, p1, p2);
1618 /* And also with abnormal edges. */
1619 basic_block bb;
1620 edge e;
1621 unsigned i;
1622 edge_iterator ei;
1623 for (i = 0; map->vec_bbs.iterate (i, &bb); ++i)
1625 FOR_EACH_EDGE (e, ei, bb->preds)
1626 if (e->flags & EDGE_ABNORMAL)
1628 gphi_iterator gsi;
1629 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1630 gsi_next (&gsi))
1632 gphi *phi = gsi.phi ();
1633 tree res = PHI_RESULT (phi);
1634 if (virtual_operand_p (res))
1635 continue;
1636 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1637 if (SSA_NAME_IS_DEFAULT_DEF (arg)
1638 && (!SSA_NAME_VAR (arg)
1639 || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1640 continue;
1642 int p1 = partition_find (tentative, var_to_partition (map, res));
1643 int p2 = partition_find (tentative, var_to_partition (map, arg));
1645 if (p1 == p2)
1646 continue;
1648 partition_union (tentative, p1, p2);
1653 map->partition_to_base_index = XCNEWVEC (int, parts);
1654 auto_vec<unsigned int> index_map (parts);
1655 if (parts)
1656 index_map.quick_grow (parts);
1658 const unsigned no_part = -1;
1659 unsigned count = parts;
1660 while (count)
1661 index_map[--count] = no_part;
1663 /* Initialize MAP's mapping from partition to base index, using
1664 as base indices an enumeration of the TENTATIVE partitions in
1665 which each SSA version ended up, so that we compute conflicts
1666 between all SSA versions that ended up in the same potential
1667 coalesce partition. */
1668 bitmap_iterator bi;
1669 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1671 int pidx = var_to_partition (map, ssa_name (i));
1672 int base = partition_find (tentative, pidx);
1673 if (index_map[base] != no_part)
1674 continue;
1675 index_map[base] = count++;
1678 map->num_basevars = count;
1680 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1682 int pidx = var_to_partition (map, ssa_name (i));
1683 int base = partition_find (tentative, pidx);
1684 gcc_assert (index_map[base] < count);
1685 map->partition_to_base_index[pidx] = index_map[base];
1688 if (dump_file && (dump_flags & TDF_DETAILS))
1689 dump_part_var_map (dump_file, tentative, map);
1691 partition_delete (tentative);
1694 /* Given an initial var_map MAP, coalesce variables and return a partition map
1695 with the resulting coalesce. Note that this function is called in either
1696 live range computation context or out-of-ssa context, indicated by MAP. */
1698 extern void
1699 coalesce_ssa_name (var_map map)
1701 tree_live_info_p liveinfo;
1702 ssa_conflicts *graph;
1703 coalesce_list *cl;
1704 auto_bitmap used_in_copies;
1706 bitmap_tree_view (used_in_copies);
1707 cl = create_coalesce_list_for_region (map, used_in_copies);
1708 if (map->outofssa_p)
1709 populate_coalesce_list_for_outofssa (cl, used_in_copies);
1710 bitmap_list_view (used_in_copies);
1712 if (dump_file && (dump_flags & TDF_DETAILS))
1713 dump_var_map (dump_file, map);
1715 partition_view_bitmap (map, used_in_copies);
1717 compute_optimized_partition_bases (map, used_in_copies, cl);
1719 if (num_var_partitions (map) < 1)
1721 delete_coalesce_list (cl);
1722 return;
1725 if (dump_file && (dump_flags & TDF_DETAILS))
1726 dump_var_map (dump_file, map);
1728 liveinfo = calculate_live_ranges (map, false);
1730 if (dump_file && (dump_flags & TDF_DETAILS))
1731 dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1733 /* Build a conflict graph. */
1734 graph = build_ssa_conflict_graph (liveinfo);
1735 delete_tree_live_info (liveinfo);
1736 if (dump_file && (dump_flags & TDF_DETAILS))
1737 ssa_conflicts_dump (dump_file, graph);
1739 sort_coalesce_list (cl, graph, map);
1741 if (dump_file && (dump_flags & TDF_DETAILS))
1743 fprintf (dump_file, "\nAfter sorting:\n");
1744 dump_coalesce_list (dump_file, cl);
1747 /* First, coalesce all live on entry variables to their base variable.
1748 This will ensure the first use is coming from the correct location. */
1750 if (dump_file && (dump_flags & TDF_DETAILS))
1751 dump_var_map (dump_file, map);
1753 /* Now coalesce everything in the list. */
1754 coalesce_partitions (map, graph, cl,
1755 ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1757 delete_coalesce_list (cl);
1758 ssa_conflicts_delete (graph);