PR target/83368
[official-gcc.git] / gcc / tree-ssa-coalesce.c
blob5cc0acad3954b5b64a1b191ff6a640efa16b0e5f
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)
623 bitmap_set_bit (bz, x);
626 if (bx)
628 /* If X has conflicts, add Y's to X. */
629 bitmap_ior_into (bx, by);
630 BITMAP_FREE (by);
631 ptr->conflicts[y] = NULL;
633 else
635 /* If X has no conflicts, simply use Y's. */
636 ptr->conflicts[x] = by;
637 ptr->conflicts[y] = NULL;
642 /* Dump a conflicts graph. */
644 static void
645 ssa_conflicts_dump (FILE *file, ssa_conflicts *ptr)
647 unsigned x;
648 bitmap b;
650 fprintf (file, "\nConflict graph:\n");
652 FOR_EACH_VEC_ELT (ptr->conflicts, x, b)
653 if (b)
655 fprintf (file, "%d: ", x);
656 dump_bitmap (file, b);
661 /* This structure is used to efficiently record the current status of live
662 SSA_NAMES when building a conflict graph.
663 LIVE_BASE_VAR has a bit set for each base variable which has at least one
664 ssa version live.
665 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
666 index, and is used to track what partitions of each base variable are
667 live. This makes it easy to add conflicts between just live partitions
668 with the same base variable.
669 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
670 marked as being live. This delays clearing of these bitmaps until
671 they are actually needed again. */
673 struct live_track
675 bitmap_obstack obstack; /* A place to allocate our bitmaps. */
676 bitmap live_base_var; /* Indicates if a basevar is live. */
677 bitmap *live_base_partitions; /* Live partitions for each basevar. */
678 var_map map; /* Var_map being used for partition mapping. */
682 /* This routine will create a new live track structure based on the partitions
683 in MAP. */
685 static live_track *
686 new_live_track (var_map map)
688 live_track *ptr;
689 int lim, x;
691 /* Make sure there is a partition view in place. */
692 gcc_assert (map->partition_to_base_index != NULL);
694 ptr = (live_track *) xmalloc (sizeof (live_track));
695 ptr->map = map;
696 lim = num_basevars (map);
697 bitmap_obstack_initialize (&ptr->obstack);
698 ptr->live_base_partitions = (bitmap *) xmalloc (sizeof (bitmap *) * lim);
699 ptr->live_base_var = BITMAP_ALLOC (&ptr->obstack);
700 for (x = 0; x < lim; x++)
701 ptr->live_base_partitions[x] = BITMAP_ALLOC (&ptr->obstack);
702 return ptr;
706 /* This routine will free the memory associated with PTR. */
708 static void
709 delete_live_track (live_track *ptr)
711 bitmap_obstack_release (&ptr->obstack);
712 free (ptr->live_base_partitions);
713 free (ptr);
717 /* This function will remove PARTITION from the live list in PTR. */
719 static inline void
720 live_track_remove_partition (live_track *ptr, int partition)
722 int root;
724 root = basevar_index (ptr->map, partition);
725 bitmap_clear_bit (ptr->live_base_partitions[root], partition);
726 /* If the element list is empty, make the base variable not live either. */
727 if (bitmap_empty_p (ptr->live_base_partitions[root]))
728 bitmap_clear_bit (ptr->live_base_var, root);
732 /* This function will adds PARTITION to the live list in PTR. */
734 static inline void
735 live_track_add_partition (live_track *ptr, int partition)
737 int root;
739 root = basevar_index (ptr->map, partition);
740 /* If this base var wasn't live before, it is now. Clear the element list
741 since it was delayed until needed. */
742 if (bitmap_set_bit (ptr->live_base_var, root))
743 bitmap_clear (ptr->live_base_partitions[root]);
744 bitmap_set_bit (ptr->live_base_partitions[root], partition);
749 /* Clear the live bit for VAR in PTR. */
751 static inline void
752 live_track_clear_var (live_track *ptr, tree var)
754 int p;
756 p = var_to_partition (ptr->map, var);
757 if (p != NO_PARTITION)
758 live_track_remove_partition (ptr, p);
762 /* Return TRUE if VAR is live in PTR. */
764 static inline bool
765 live_track_live_p (live_track *ptr, tree var)
767 int p, root;
769 p = var_to_partition (ptr->map, var);
770 if (p != NO_PARTITION)
772 root = basevar_index (ptr->map, p);
773 if (bitmap_bit_p (ptr->live_base_var, root))
774 return bitmap_bit_p (ptr->live_base_partitions[root], p);
776 return false;
780 /* This routine will add USE to PTR. USE will be marked as live in both the
781 ssa live map and the live bitmap for the root of USE. */
783 static inline void
784 live_track_process_use (live_track *ptr, tree use)
786 int p;
788 p = var_to_partition (ptr->map, use);
789 if (p == NO_PARTITION)
790 return;
792 /* Mark as live in the appropriate live list. */
793 live_track_add_partition (ptr, p);
797 /* This routine will process a DEF in PTR. DEF will be removed from the live
798 lists, and if there are any other live partitions with the same base
799 variable, conflicts will be added to GRAPH. */
801 static inline void
802 live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph)
804 int p, root;
805 bitmap b;
806 unsigned x;
807 bitmap_iterator bi;
809 p = var_to_partition (ptr->map, def);
810 if (p == NO_PARTITION)
811 return;
813 /* Clear the liveness bit. */
814 live_track_remove_partition (ptr, p);
816 /* If the bitmap isn't empty now, conflicts need to be added. */
817 root = basevar_index (ptr->map, p);
818 if (bitmap_bit_p (ptr->live_base_var, root))
820 b = ptr->live_base_partitions[root];
821 EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
822 ssa_conflicts_add (graph, p, x);
827 /* Initialize PTR with the partitions set in INIT. */
829 static inline void
830 live_track_init (live_track *ptr, bitmap init)
832 unsigned p;
833 bitmap_iterator bi;
835 /* Mark all live on exit partitions. */
836 EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
837 live_track_add_partition (ptr, p);
841 /* This routine will clear all live partitions in PTR. */
843 static inline void
844 live_track_clear_base_vars (live_track *ptr)
846 /* Simply clear the live base list. Anything marked as live in the element
847 lists will be cleared later if/when the base variable ever comes alive
848 again. */
849 bitmap_clear (ptr->live_base_var);
853 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
854 partition view of the var_map liveinfo is based on get entries in the
855 conflict graph. Only conflicts between ssa_name partitions with the same
856 base variable are added. */
858 static ssa_conflicts *
859 build_ssa_conflict_graph (tree_live_info_p liveinfo)
861 ssa_conflicts *graph;
862 var_map map;
863 basic_block bb;
864 ssa_op_iter iter;
865 live_track *live;
866 basic_block entry;
868 /* If inter-variable coalescing is enabled, we may attempt to
869 coalesce variables from different base variables, including
870 different parameters, so we have to make sure default defs live
871 at the entry block conflict with each other. */
872 if (flag_tree_coalesce_vars)
873 entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
874 else
875 entry = NULL;
877 map = live_var_map (liveinfo);
878 graph = ssa_conflicts_new (num_var_partitions (map));
880 live = new_live_track (map);
882 FOR_EACH_BB_FN (bb, cfun)
884 /* Start with live on exit temporaries. */
885 live_track_init (live, live_on_exit (liveinfo, bb));
887 for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
888 gsi_prev (&gsi))
890 tree var;
891 gimple *stmt = gsi_stmt (gsi);
893 /* A copy between 2 partitions does not introduce an interference
894 by itself. If they did, you would never be able to coalesce
895 two things which are copied. If the two variables really do
896 conflict, they will conflict elsewhere in the program.
898 This is handled by simply removing the SRC of the copy from the
899 live list, and processing the stmt normally. */
900 if (is_gimple_assign (stmt))
902 tree lhs = gimple_assign_lhs (stmt);
903 tree rhs1 = gimple_assign_rhs1 (stmt);
904 if (gimple_assign_copy_p (stmt)
905 && TREE_CODE (lhs) == SSA_NAME
906 && TREE_CODE (rhs1) == SSA_NAME)
907 live_track_clear_var (live, rhs1);
909 else if (is_gimple_debug (stmt))
910 continue;
912 /* For stmts with more than one SSA_NAME definition pretend all the
913 SSA_NAME outputs but the first one are live at this point, so
914 that conflicts are added in between all those even when they are
915 actually not really live after the asm, because expansion might
916 copy those into pseudos after the asm and if multiple outputs
917 share the same partition, it might overwrite those that should
918 be live. E.g.
919 asm volatile (".." : "=r" (a) : "=r" (b) : "0" (a), "1" (a));
920 return a;
921 See PR70593. */
922 bool first = true;
923 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
924 if (first)
925 first = false;
926 else
927 live_track_process_use (live, var);
929 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
930 live_track_process_def (live, var, graph);
932 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
933 live_track_process_use (live, var);
936 /* If result of a PHI is unused, looping over the statements will not
937 record any conflicts since the def was never live. Since the PHI node
938 is going to be translated out of SSA form, it will insert a copy.
939 There must be a conflict recorded between the result of the PHI and
940 any variables that are live. Otherwise the out-of-ssa translation
941 may create incorrect code. */
942 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
943 gsi_next (&gsi))
945 gphi *phi = gsi.phi ();
946 tree result = PHI_RESULT (phi);
947 if (live_track_live_p (live, result))
948 live_track_process_def (live, result, graph);
951 /* Pretend there are defs for params' default defs at the start
952 of the (post-)entry block. This will prevent PARM_DECLs from
953 coalescing into the same partition. Although RESULT_DECLs'
954 default defs don't have a useful initial value, we have to
955 prevent them from coalescing with PARM_DECLs' default defs
956 too, otherwise assign_parms would attempt to assign different
957 RTL to the same partition. */
958 if (bb == entry)
960 unsigned i;
961 tree var;
963 FOR_EACH_SSA_NAME (i, var, cfun)
965 if (!SSA_NAME_IS_DEFAULT_DEF (var)
966 || !SSA_NAME_VAR (var)
967 || VAR_P (SSA_NAME_VAR (var)))
968 continue;
970 live_track_process_def (live, var, graph);
971 /* Process a use too, so that it remains live and
972 conflicts with other parms' default defs, even unused
973 ones. */
974 live_track_process_use (live, var);
978 live_track_clear_base_vars (live);
981 delete_live_track (live);
982 return graph;
986 /* Shortcut routine to print messages to file F of the form:
987 "STR1 EXPR1 STR2 EXPR2 STR3." */
989 static inline void
990 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
991 tree expr2, const char *str3)
993 fprintf (f, "%s", str1);
994 print_generic_expr (f, expr1, TDF_SLIM);
995 fprintf (f, "%s", str2);
996 print_generic_expr (f, expr2, TDF_SLIM);
997 fprintf (f, "%s", str3);
1001 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
1003 static inline void
1004 fail_abnormal_edge_coalesce (int x, int y)
1006 fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
1007 fprintf (stderr, " which are marked as MUST COALESCE.\n");
1008 print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
1009 fprintf (stderr, " and ");
1010 print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
1012 internal_error ("SSA corruption");
1015 /* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
1016 assign_parms may ask for a default partition. */
1018 static void
1019 for_all_parms (void (*callback)(tree var, void *arg), void *arg)
1021 for (tree var = DECL_ARGUMENTS (current_function_decl); var;
1022 var = DECL_CHAIN (var))
1023 callback (var, arg);
1024 if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
1025 callback (DECL_RESULT (current_function_decl), arg);
1026 if (cfun->static_chain_decl)
1027 callback (cfun->static_chain_decl, arg);
1030 /* Create a default def for VAR. */
1032 static void
1033 create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
1035 if (!is_gimple_reg (var))
1036 return;
1038 tree ssa = get_or_create_ssa_default_def (cfun, var);
1039 gcc_assert (ssa);
1042 /* Register VAR's default def in MAP. */
1044 static void
1045 register_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
1047 if (!is_gimple_reg (var))
1048 return;
1050 tree ssa = ssa_default_def (cfun, var);
1051 gcc_assert (ssa);
1054 /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
1055 and the DECL's default def is unused (i.e., it was introduced by
1056 create_default_def), mark VAR and the default def for
1057 coalescing. */
1059 static void
1060 coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
1062 if (SSA_NAME_IS_DEFAULT_DEF (var)
1063 || !SSA_NAME_VAR (var)
1064 || VAR_P (SSA_NAME_VAR (var)))
1065 return;
1067 tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var));
1068 if (!has_zero_uses (ssa))
1069 return;
1071 add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var));
1072 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1073 /* Default defs will have their used_in_copy bits set at the end of
1074 create_outofssa_var_map. */
1077 /* This function creates a var_map for the current function as well as creating
1078 a coalesce list for use later in the out of ssa process. */
1080 static var_map
1081 create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
1083 gimple_stmt_iterator gsi;
1084 basic_block bb;
1085 tree var;
1086 gimple *stmt;
1087 tree first;
1088 var_map map;
1089 int v1, v2, cost;
1090 unsigned i;
1092 for_all_parms (create_default_def, NULL);
1094 map = init_var_map (num_ssa_names);
1096 for_all_parms (register_default_def, NULL);
1098 FOR_EACH_BB_FN (bb, cfun)
1100 tree arg;
1102 for (gphi_iterator gpi = gsi_start_phis (bb);
1103 !gsi_end_p (gpi);
1104 gsi_next (&gpi))
1106 gphi *phi = gpi.phi ();
1107 size_t i;
1108 int ver;
1109 tree res;
1110 bool saw_copy = false;
1112 res = gimple_phi_result (phi);
1113 ver = SSA_NAME_VERSION (res);
1115 /* Register ssa_names and coalesces between the args and the result
1116 of all PHI. */
1117 for (i = 0; i < gimple_phi_num_args (phi); i++)
1119 edge e = gimple_phi_arg_edge (phi, i);
1120 arg = PHI_ARG_DEF (phi, i);
1121 if (TREE_CODE (arg) != SSA_NAME)
1122 continue;
1124 if (gimple_can_coalesce_p (arg, res)
1125 || (e->flags & EDGE_ABNORMAL))
1127 saw_copy = true;
1128 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1129 if ((e->flags & EDGE_ABNORMAL) == 0)
1131 int cost = coalesce_cost_edge (e);
1132 if (cost == 1 && has_single_use (arg))
1133 add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1134 else
1135 add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1139 if (saw_copy)
1140 bitmap_set_bit (used_in_copy, ver);
1143 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1145 stmt = gsi_stmt (gsi);
1147 if (is_gimple_debug (stmt))
1148 continue;
1150 /* Check for copy coalesces. */
1151 switch (gimple_code (stmt))
1153 case GIMPLE_ASSIGN:
1155 tree lhs = gimple_assign_lhs (stmt);
1156 tree rhs1 = gimple_assign_rhs1 (stmt);
1157 if (gimple_assign_ssa_name_copy_p (stmt)
1158 && gimple_can_coalesce_p (lhs, rhs1))
1160 v1 = SSA_NAME_VERSION (lhs);
1161 v2 = SSA_NAME_VERSION (rhs1);
1162 cost = coalesce_cost_bb (bb);
1163 add_coalesce (cl, v1, v2, cost);
1164 bitmap_set_bit (used_in_copy, v1);
1165 bitmap_set_bit (used_in_copy, v2);
1168 break;
1170 case GIMPLE_RETURN:
1172 tree res = DECL_RESULT (current_function_decl);
1173 if (VOID_TYPE_P (TREE_TYPE (res))
1174 || !is_gimple_reg (res))
1175 break;
1176 tree rhs1 = gimple_return_retval (as_a <greturn *> (stmt));
1177 if (!rhs1)
1178 break;
1179 tree lhs = ssa_default_def (cfun, res);
1180 gcc_assert (lhs);
1181 if (TREE_CODE (rhs1) == SSA_NAME
1182 && gimple_can_coalesce_p (lhs, rhs1))
1184 v1 = SSA_NAME_VERSION (lhs);
1185 v2 = SSA_NAME_VERSION (rhs1);
1186 cost = coalesce_cost_bb (bb);
1187 add_coalesce (cl, v1, v2, cost);
1188 bitmap_set_bit (used_in_copy, v1);
1189 bitmap_set_bit (used_in_copy, v2);
1191 break;
1194 case GIMPLE_ASM:
1196 gasm *asm_stmt = as_a <gasm *> (stmt);
1197 unsigned long noutputs, i;
1198 unsigned long ninputs;
1199 tree *outputs, link;
1200 noutputs = gimple_asm_noutputs (asm_stmt);
1201 ninputs = gimple_asm_ninputs (asm_stmt);
1202 outputs = (tree *) alloca (noutputs * sizeof (tree));
1203 for (i = 0; i < noutputs; ++i)
1205 link = gimple_asm_output_op (asm_stmt, i);
1206 outputs[i] = TREE_VALUE (link);
1209 for (i = 0; i < ninputs; ++i)
1211 const char *constraint;
1212 tree input;
1213 char *end;
1214 unsigned long match;
1216 link = gimple_asm_input_op (asm_stmt, i);
1217 constraint
1218 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1219 input = TREE_VALUE (link);
1221 if (TREE_CODE (input) != SSA_NAME)
1222 continue;
1224 match = strtoul (constraint, &end, 10);
1225 if (match >= noutputs || end == constraint)
1226 continue;
1228 if (TREE_CODE (outputs[match]) != SSA_NAME)
1229 continue;
1231 v1 = SSA_NAME_VERSION (outputs[match]);
1232 v2 = SSA_NAME_VERSION (input);
1234 if (gimple_can_coalesce_p (outputs[match], input))
1236 cost = coalesce_cost (REG_BR_PROB_BASE,
1237 optimize_bb_for_size_p (bb));
1238 add_coalesce (cl, v1, v2, cost);
1239 bitmap_set_bit (used_in_copy, v1);
1240 bitmap_set_bit (used_in_copy, v2);
1243 break;
1246 default:
1247 break;
1252 /* Now process result decls and live on entry variables for entry into
1253 the coalesce list. */
1254 first = NULL_TREE;
1255 FOR_EACH_SSA_NAME (i, var, cfun)
1257 if (!virtual_operand_p (var))
1259 coalesce_with_default (var, cl, used_in_copy);
1261 /* Add coalesces between all the result decls. */
1262 if (SSA_NAME_VAR (var)
1263 && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1265 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1266 if (first == NULL_TREE)
1267 first = var;
1268 else
1270 gcc_assert (gimple_can_coalesce_p (var, first));
1271 v1 = SSA_NAME_VERSION (first);
1272 v2 = SSA_NAME_VERSION (var);
1273 cost = coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
1274 add_coalesce (cl, v1, v2, cost);
1277 /* Mark any default_def variables as being in the coalesce list
1278 since they will have to be coalesced with the base variable. If
1279 not marked as present, they won't be in the coalesce view. */
1280 if (SSA_NAME_IS_DEFAULT_DEF (var)
1281 && (!has_zero_uses (var)
1282 || (SSA_NAME_VAR (var)
1283 && !VAR_P (SSA_NAME_VAR (var)))))
1284 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1288 return map;
1292 /* Attempt to coalesce ssa versions X and Y together using the partition
1293 mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1294 DEBUG, if it is nun-NULL. */
1296 static inline bool
1297 attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y,
1298 FILE *debug)
1300 int z;
1301 tree var1, var2;
1302 int p1, p2;
1304 p1 = var_to_partition (map, ssa_name (x));
1305 p2 = var_to_partition (map, ssa_name (y));
1307 if (debug)
1309 fprintf (debug, "(%d)", x);
1310 print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1311 fprintf (debug, " & (%d)", y);
1312 print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1315 if (p1 == p2)
1317 if (debug)
1318 fprintf (debug, ": Already Coalesced.\n");
1319 return true;
1322 if (debug)
1323 fprintf (debug, " [map: %d, %d] ", p1, p2);
1326 if (!ssa_conflicts_test_p (graph, p1, p2))
1328 var1 = partition_to_var (map, p1);
1329 var2 = partition_to_var (map, p2);
1331 z = var_union (map, var1, var2);
1332 if (z == NO_PARTITION)
1334 if (debug)
1335 fprintf (debug, ": Unable to perform partition union.\n");
1336 return false;
1339 /* z is the new combined partition. Remove the other partition from
1340 the list, and merge the conflicts. */
1341 if (z == p1)
1342 ssa_conflicts_merge (graph, p1, p2);
1343 else
1344 ssa_conflicts_merge (graph, p2, p1);
1346 if (debug)
1347 fprintf (debug, ": Success -> %d\n", z);
1349 return true;
1352 if (debug)
1353 fprintf (debug, ": Fail due to conflict\n");
1355 return false;
1359 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1360 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1362 static void
1363 coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
1364 FILE *debug)
1366 int x = 0, y = 0;
1367 tree var1, var2;
1368 int cost;
1369 basic_block bb;
1370 edge e;
1371 edge_iterator ei;
1373 /* First, coalesce all the copies across abnormal edges. These are not placed
1374 in the coalesce list because they do not need to be sorted, and simply
1375 consume extra memory/compilation time in large programs. */
1377 FOR_EACH_BB_FN (bb, cfun)
1379 FOR_EACH_EDGE (e, ei, bb->preds)
1380 if (e->flags & EDGE_ABNORMAL)
1382 gphi_iterator gsi;
1383 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1384 gsi_next (&gsi))
1386 gphi *phi = gsi.phi ();
1387 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1388 if (SSA_NAME_IS_DEFAULT_DEF (arg)
1389 && (!SSA_NAME_VAR (arg)
1390 || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1391 continue;
1393 tree res = PHI_RESULT (phi);
1394 int v1 = SSA_NAME_VERSION (res);
1395 int v2 = SSA_NAME_VERSION (arg);
1397 if (debug)
1398 fprintf (debug, "Abnormal coalesce: ");
1400 if (!attempt_coalesce (map, graph, v1, v2, debug))
1401 fail_abnormal_edge_coalesce (v1, v2);
1406 /* Now process the items in the coalesce list. */
1408 while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1410 var1 = ssa_name (x);
1411 var2 = ssa_name (y);
1413 /* Assert the coalesces have the same base variable. */
1414 gcc_assert (gimple_can_coalesce_p (var1, var2));
1416 if (debug)
1417 fprintf (debug, "Coalesce list: ");
1418 attempt_coalesce (map, graph, x, y, debug);
1423 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1425 struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
1427 static inline hashval_t hash (const tree_node *);
1428 static inline int equal (const tree_node *, const tree_node *);
1431 inline hashval_t
1432 ssa_name_var_hash::hash (const_tree n)
1434 return DECL_UID (SSA_NAME_VAR (n));
1437 inline int
1438 ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
1440 return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
1444 /* Output partition map MAP with coalescing plan PART to file F. */
1446 void
1447 dump_part_var_map (FILE *f, partition part, var_map map)
1449 int t;
1450 unsigned x, y;
1451 int p;
1453 fprintf (f, "\nCoalescible Partition map \n\n");
1455 for (x = 0; x < map->num_partitions; x++)
1457 if (map->view_to_partition != NULL)
1458 p = map->view_to_partition[x];
1459 else
1460 p = x;
1462 if (ssa_name (p) == NULL_TREE
1463 || virtual_operand_p (ssa_name (p)))
1464 continue;
1466 t = 0;
1467 for (y = 1; y < num_ssa_names; y++)
1469 tree var = version_to_var (map, y);
1470 if (!var)
1471 continue;
1472 int q = var_to_partition (map, var);
1473 p = partition_find (part, q);
1474 gcc_assert (map->partition_to_base_index[q]
1475 == map->partition_to_base_index[p]);
1477 if (p == (int)x)
1479 if (t++ == 0)
1481 fprintf (f, "Partition %d, base %d (", x,
1482 map->partition_to_base_index[q]);
1483 print_generic_expr (f, partition_to_var (map, q), TDF_SLIM);
1484 fprintf (f, " - ");
1486 fprintf (f, "%d ", y);
1489 if (t != 0)
1490 fprintf (f, ")\n");
1492 fprintf (f, "\n");
1495 /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
1496 coalescing together, false otherwise.
1498 This must stay consistent with compute_samebase_partition_bases and
1499 compute_optimized_partition_bases. */
1501 bool
1502 gimple_can_coalesce_p (tree name1, tree name2)
1504 /* First check the SSA_NAME's associated DECL. Without
1505 optimization, we only want to coalesce if they have the same DECL
1506 or both have no associated DECL. */
1507 tree var1 = SSA_NAME_VAR (name1);
1508 tree var2 = SSA_NAME_VAR (name2);
1509 var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
1510 var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
1511 if (var1 != var2 && !flag_tree_coalesce_vars)
1512 return false;
1514 /* Now check the types. If the types are the same, then we should
1515 try to coalesce V1 and V2. */
1516 tree t1 = TREE_TYPE (name1);
1517 tree t2 = TREE_TYPE (name2);
1518 if (t1 == t2)
1520 check_modes:
1521 /* If the base variables are the same, we're good: none of the
1522 other tests below could possibly fail. */
1523 var1 = SSA_NAME_VAR (name1);
1524 var2 = SSA_NAME_VAR (name2);
1525 if (var1 == var2)
1526 return true;
1528 /* We don't want to coalesce two SSA names if one of the base
1529 variables is supposed to be a register while the other is
1530 supposed to be on the stack. Anonymous SSA names most often
1531 take registers, but when not optimizing, user variables
1532 should go on the stack, so coalescing them with the anonymous
1533 variable as the partition leader would end up assigning the
1534 user variable to a register. Don't do that! */
1535 bool reg1 = use_register_for_decl (name1);
1536 bool reg2 = use_register_for_decl (name2);
1537 if (reg1 != reg2)
1538 return false;
1540 /* Check that the promoted modes and unsignedness are the same.
1541 We don't want to coalesce if the promoted modes would be
1542 different, or if they would sign-extend differently. Only
1543 PARM_DECLs and RESULT_DECLs have different promotion rules,
1544 so skip the test if both are variables, or both are anonymous
1545 SSA_NAMEs. */
1546 int unsigned1, unsigned2;
1547 return ((!var1 || VAR_P (var1)) && (!var2 || VAR_P (var2)))
1548 || ((promote_ssa_mode (name1, &unsigned1)
1549 == promote_ssa_mode (name2, &unsigned2))
1550 && unsigned1 == unsigned2);
1553 /* If alignment requirements are different, we can't coalesce. */
1554 if (MINIMUM_ALIGNMENT (t1,
1555 var1 ? DECL_MODE (var1) : TYPE_MODE (t1),
1556 var1 ? LOCAL_DECL_ALIGNMENT (var1) : TYPE_ALIGN (t1))
1557 != MINIMUM_ALIGNMENT (t2,
1558 var2 ? DECL_MODE (var2) : TYPE_MODE (t2),
1559 var2 ? LOCAL_DECL_ALIGNMENT (var2) : TYPE_ALIGN (t2)))
1560 return false;
1562 /* If the types are not the same, see whether they are compatible. This
1563 (for example) allows coalescing when the types are fundamentally the
1564 same, but just have different names.
1566 In the non-optimized case, we must first test TYPE_CANONICAL because
1567 we use it to compute the partition_to_base_index of the map. */
1568 if (flag_tree_coalesce_vars)
1570 if (types_compatible_p (t1, t2))
1571 goto check_modes;
1573 else
1575 if (TYPE_CANONICAL (t1)
1576 && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)
1577 && types_compatible_p (t1, t2))
1578 goto check_modes;
1581 return false;
1584 /* Fill in MAP's partition_to_base_index, with one index for each
1585 partition of SSA names USED_IN_COPIES and related by CL coalesce
1586 possibilities. This must match gimple_can_coalesce_p in the
1587 optimized case. */
1589 static void
1590 compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1591 coalesce_list *cl)
1593 int parts = num_var_partitions (map);
1594 partition tentative = partition_new (parts);
1596 /* Partition the SSA versions so that, for each coalescible
1597 pair, both of its members are in the same partition in
1598 TENTATIVE. */
1599 gcc_assert (!cl->sorted);
1600 coalesce_pair *node;
1601 coalesce_iterator_type ppi;
1602 FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1604 tree v1 = ssa_name (node->first_element);
1605 int p1 = partition_find (tentative, var_to_partition (map, v1));
1606 tree v2 = ssa_name (node->second_element);
1607 int p2 = partition_find (tentative, var_to_partition (map, v2));
1609 if (p1 == p2)
1610 continue;
1612 partition_union (tentative, p1, p2);
1615 /* We have to deal with cost one pairs too. */
1616 for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1618 tree v1 = ssa_name (co->first_element);
1619 int p1 = partition_find (tentative, var_to_partition (map, v1));
1620 tree v2 = ssa_name (co->second_element);
1621 int p2 = partition_find (tentative, var_to_partition (map, v2));
1623 if (p1 == p2)
1624 continue;
1626 partition_union (tentative, p1, p2);
1629 /* And also with abnormal edges. */
1630 basic_block bb;
1631 edge e;
1632 edge_iterator ei;
1633 FOR_EACH_BB_FN (bb, cfun)
1635 FOR_EACH_EDGE (e, ei, bb->preds)
1636 if (e->flags & EDGE_ABNORMAL)
1638 gphi_iterator gsi;
1639 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1640 gsi_next (&gsi))
1642 gphi *phi = gsi.phi ();
1643 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1644 if (SSA_NAME_IS_DEFAULT_DEF (arg)
1645 && (!SSA_NAME_VAR (arg)
1646 || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1647 continue;
1649 tree res = PHI_RESULT (phi);
1651 int p1 = partition_find (tentative, var_to_partition (map, res));
1652 int p2 = partition_find (tentative, var_to_partition (map, arg));
1654 if (p1 == p2)
1655 continue;
1657 partition_union (tentative, p1, p2);
1662 map->partition_to_base_index = XCNEWVEC (int, parts);
1663 auto_vec<unsigned int> index_map (parts);
1664 if (parts)
1665 index_map.quick_grow (parts);
1667 const unsigned no_part = -1;
1668 unsigned count = parts;
1669 while (count)
1670 index_map[--count] = no_part;
1672 /* Initialize MAP's mapping from partition to base index, using
1673 as base indices an enumeration of the TENTATIVE partitions in
1674 which each SSA version ended up, so that we compute conflicts
1675 between all SSA versions that ended up in the same potential
1676 coalesce partition. */
1677 bitmap_iterator bi;
1678 unsigned i;
1679 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1681 int pidx = var_to_partition (map, ssa_name (i));
1682 int base = partition_find (tentative, pidx);
1683 if (index_map[base] != no_part)
1684 continue;
1685 index_map[base] = count++;
1688 map->num_basevars = count;
1690 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1692 int pidx = var_to_partition (map, ssa_name (i));
1693 int base = partition_find (tentative, pidx);
1694 gcc_assert (index_map[base] < count);
1695 map->partition_to_base_index[pidx] = index_map[base];
1698 if (dump_file && (dump_flags & TDF_DETAILS))
1699 dump_part_var_map (dump_file, tentative, map);
1701 partition_delete (tentative);
1704 /* Hashtable helpers. */
1706 struct tree_int_map_hasher : nofree_ptr_hash <tree_int_map>
1708 static inline hashval_t hash (const tree_int_map *);
1709 static inline bool equal (const tree_int_map *, const tree_int_map *);
1712 inline hashval_t
1713 tree_int_map_hasher::hash (const tree_int_map *v)
1715 return tree_map_base_hash (v);
1718 inline bool
1719 tree_int_map_hasher::equal (const tree_int_map *v, const tree_int_map *c)
1721 return tree_int_map_eq (v, c);
1724 /* This routine will initialize the basevar fields of MAP with base
1725 names. Partitions will share the same base if they have the same
1726 SSA_NAME_VAR, or, being anonymous variables, the same type. This
1727 must match gimple_can_coalesce_p in the non-optimized case. */
1729 static void
1730 compute_samebase_partition_bases (var_map map)
1732 int x, num_part;
1733 tree var;
1734 struct tree_int_map *m, *mapstorage;
1736 num_part = num_var_partitions (map);
1737 hash_table<tree_int_map_hasher> tree_to_index (num_part);
1738 /* We can have at most num_part entries in the hash tables, so it's
1739 enough to allocate so many map elements once, saving some malloc
1740 calls. */
1741 mapstorage = m = XNEWVEC (struct tree_int_map, num_part);
1743 /* If a base table already exists, clear it, otherwise create it. */
1744 free (map->partition_to_base_index);
1745 map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
1747 /* Build the base variable list, and point partitions at their bases. */
1748 for (x = 0; x < num_part; x++)
1750 struct tree_int_map **slot;
1751 unsigned baseindex;
1752 var = partition_to_var (map, x);
1753 if (SSA_NAME_VAR (var)
1754 && (!VAR_P (SSA_NAME_VAR (var))
1755 || !DECL_IGNORED_P (SSA_NAME_VAR (var))))
1756 m->base.from = SSA_NAME_VAR (var);
1757 else
1758 /* This restricts what anonymous SSA names we can coalesce
1759 as it restricts the sets we compute conflicts for.
1760 Using TREE_TYPE to generate sets is the easiest as
1761 type equivalency also holds for SSA names with the same
1762 underlying decl.
1764 Check gimple_can_coalesce_p when changing this code. */
1765 m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
1766 ? TYPE_CANONICAL (TREE_TYPE (var))
1767 : TREE_TYPE (var));
1768 /* If base variable hasn't been seen, set it up. */
1769 slot = tree_to_index.find_slot (m, INSERT);
1770 if (!*slot)
1772 baseindex = m - mapstorage;
1773 m->to = baseindex;
1774 *slot = m;
1775 m++;
1777 else
1778 baseindex = (*slot)->to;
1779 map->partition_to_base_index[x] = baseindex;
1782 map->num_basevars = m - mapstorage;
1784 free (mapstorage);
1787 /* Reduce the number of copies by coalescing variables in the function. Return
1788 a partition map with the resulting coalesces. */
1790 extern var_map
1791 coalesce_ssa_name (void)
1793 tree_live_info_p liveinfo;
1794 ssa_conflicts *graph;
1795 coalesce_list *cl;
1796 auto_bitmap used_in_copies;
1797 var_map map;
1798 unsigned int i;
1799 tree a;
1801 cl = create_coalesce_list ();
1802 map = create_outofssa_var_map (cl, used_in_copies);
1804 /* If this optimization is disabled, we need to coalesce all the
1805 names originating from the same SSA_NAME_VAR so debug info
1806 remains undisturbed. */
1807 if (!flag_tree_coalesce_vars)
1809 hash_table<ssa_name_var_hash> ssa_name_hash (10);
1811 FOR_EACH_SSA_NAME (i, a, cfun)
1813 if (SSA_NAME_VAR (a)
1814 && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1815 && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
1816 || !VAR_P (SSA_NAME_VAR (a))))
1818 tree *slot = ssa_name_hash.find_slot (a, INSERT);
1820 if (!*slot)
1821 *slot = a;
1822 else
1824 /* If the variable is a PARM_DECL or a RESULT_DECL, we
1825 _require_ that all the names originating from it be
1826 coalesced, because there must be a single partition
1827 containing all the names so that it can be assigned
1828 the canonical RTL location of the DECL safely.
1829 If in_lto_p, a function could have been compiled
1830 originally with optimizations and only the link
1831 performed at -O0, so we can't actually require it. */
1832 const int cost
1833 = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p)
1834 ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
1835 add_coalesce (cl, SSA_NAME_VERSION (a),
1836 SSA_NAME_VERSION (*slot), cost);
1837 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a));
1838 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot));
1843 if (dump_file && (dump_flags & TDF_DETAILS))
1844 dump_var_map (dump_file, map);
1846 partition_view_bitmap (map, used_in_copies);
1848 if (flag_tree_coalesce_vars)
1849 compute_optimized_partition_bases (map, used_in_copies, cl);
1850 else
1851 compute_samebase_partition_bases (map);
1853 if (num_var_partitions (map) < 1)
1855 delete_coalesce_list (cl);
1856 return map;
1859 if (dump_file && (dump_flags & TDF_DETAILS))
1860 dump_var_map (dump_file, map);
1862 liveinfo = calculate_live_ranges (map, false);
1864 if (dump_file && (dump_flags & TDF_DETAILS))
1865 dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1867 /* Build a conflict graph. */
1868 graph = build_ssa_conflict_graph (liveinfo);
1869 delete_tree_live_info (liveinfo);
1870 if (dump_file && (dump_flags & TDF_DETAILS))
1871 ssa_conflicts_dump (dump_file, graph);
1873 sort_coalesce_list (cl, graph, map);
1875 if (dump_file && (dump_flags & TDF_DETAILS))
1877 fprintf (dump_file, "\nAfter sorting:\n");
1878 dump_coalesce_list (dump_file, cl);
1881 /* First, coalesce all live on entry variables to their base variable.
1882 This will ensure the first use is coming from the correct location. */
1884 if (dump_file && (dump_flags & TDF_DETAILS))
1885 dump_var_map (dump_file, map);
1887 /* Now coalesce everything in the list. */
1888 coalesce_partitions (map, graph, cl,
1889 ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1891 delete_coalesce_list (cl);
1892 ssa_conflicts_delete (graph);
1894 return map;
1897 /* We need to pass two arguments to set_parm_default_def_partition,
1898 but for_all_parms only supports one. Use a pair. */
1900 typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
1902 /* Set in ARG's PARTS bitmap the bit corresponding to the partition in
1903 ARG's MAP containing VAR's default def. */
1905 static void
1906 set_parm_default_def_partition (tree var, void *arg_)
1908 parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
1909 var_map map = arg->first;
1910 bitmap parts = arg->second;
1912 if (!is_gimple_reg (var))
1913 return;
1915 tree ssa = ssa_default_def (cfun, var);
1916 gcc_assert (ssa);
1918 int version = var_to_partition (map, ssa);
1919 gcc_assert (version != NO_PARTITION);
1921 bool changed = bitmap_set_bit (parts, version);
1922 gcc_assert (changed);
1925 /* Allocate and return a bitmap that has a bit set for each partition
1926 that contains a default def for a parameter. */
1928 bitmap
1929 get_parm_default_def_partitions (var_map map)
1931 bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
1933 parm_default_def_partition_arg
1934 arg = std::make_pair (map, parm_default_def_parts);
1936 for_all_parms (set_parm_default_def_partition, &arg);
1938 return parm_default_def_parts;
1941 /* Allocate and return a bitmap that has a bit set for each partition
1942 that contains an undefined value. */
1944 bitmap
1945 get_undefined_value_partitions (var_map map)
1947 bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
1949 for (unsigned int i = 1; i < num_ssa_names; i++)
1951 tree var = ssa_name (i);
1952 if (var
1953 && !virtual_operand_p (var)
1954 && !has_zero_uses (var)
1955 && ssa_undefined_value_p (var))
1957 const int p = var_to_partition (map, var);
1958 if (p != NO_PARTITION)
1959 bitmap_set_bit (undefined_value_parts, p);
1963 return undefined_value_parts;