gcc/
[official-gcc.git] / gcc / tree-ssa-coalesce.c
blob34c3fa16ccf852343589377e69cf7edaefdf1d29
1 /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 Copyright (C) 2004-2016 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
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 "tm_p.h"
29 #include "ssa.h"
30 #include "tree-pretty-print.h"
31 #include "diagnostic-core.h"
32 #include "dumpfile.h"
33 #include "gimple-iterator.h"
34 #include "tree-ssa-live.h"
35 #include "tree-ssa-coalesce.h"
36 #include "explow.h"
37 #include "tree-dfa.h"
38 #include "stor-layout.h"
40 /* This set of routines implements a coalesce_list. This is an object which
41 is used to track pairs of ssa_names which are desirable to coalesce
42 together to avoid copies. Costs are associated with each pair, and when
43 all desired information has been collected, the object can be used to
44 order the pairs for processing. */
46 /* This structure defines a pair entry. */
48 struct coalesce_pair
50 int first_element;
51 int second_element;
52 int cost;
54 /* A count of the number of unique partitions this pair would conflict
55 with if coalescing was successful. This is the secondary sort key,
56 given two pairs with equal costs, we will prefer the pair with a smaller
57 conflict set.
59 This is lazily initialized when we discover two coalescing pairs have
60 the same primary cost.
62 Note this is not updated and propagated as pairs are coalesced. */
63 int conflict_count;
65 /* The order in which coalescing pairs are discovered is recorded in this
66 field, which is used as the final tie breaker when sorting coalesce
67 pairs. */
68 int index;
71 /* This represents a conflict graph. Implemented as an array of bitmaps.
72 A full matrix is used for conflicts rather than just upper triangular form.
73 this makes it much simpler and faster to perform conflict merges. */
75 struct ssa_conflicts
77 bitmap_obstack obstack; /* A place to allocate our bitmaps. */
78 vec<bitmap> conflicts;
81 /* The narrow API of the qsort comparison function doesn't allow easy
82 access to additional arguments. So we have two globals (ick) to hold
83 the data we need. They're initialized before the call to qsort and
84 wiped immediately after. */
85 static ssa_conflicts *conflicts_;
86 static var_map map_;
88 /* Coalesce pair hashtable helpers. */
90 struct coalesce_pair_hasher : nofree_ptr_hash <coalesce_pair>
92 static inline hashval_t hash (const coalesce_pair *);
93 static inline bool equal (const coalesce_pair *, const coalesce_pair *);
96 /* Hash function for coalesce list. Calculate hash for PAIR. */
98 inline hashval_t
99 coalesce_pair_hasher::hash (const coalesce_pair *pair)
101 hashval_t a = (hashval_t)(pair->first_element);
102 hashval_t b = (hashval_t)(pair->second_element);
104 return b * (b - 1) / 2 + a;
107 /* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2,
108 returning TRUE if the two pairs are equivalent. */
110 inline bool
111 coalesce_pair_hasher::equal (const coalesce_pair *p1, const coalesce_pair *p2)
113 return (p1->first_element == p2->first_element
114 && p1->second_element == p2->second_element);
117 typedef hash_table<coalesce_pair_hasher> coalesce_table_type;
118 typedef coalesce_table_type::iterator coalesce_iterator_type;
121 struct cost_one_pair
123 int first_element;
124 int second_element;
125 cost_one_pair *next;
128 /* This structure maintains the list of coalesce pairs. */
130 struct coalesce_list
132 coalesce_table_type *list; /* Hash table. */
133 coalesce_pair **sorted; /* List when sorted. */
134 int num_sorted; /* Number in the sorted list. */
135 cost_one_pair *cost_one_list;/* Single use coalesces with cost 1. */
138 #define NO_BEST_COALESCE -1
139 #define MUST_COALESCE_COST INT_MAX
142 /* Return cost of execution of copy instruction with FREQUENCY. */
144 static inline int
145 coalesce_cost (int frequency, bool optimize_for_size)
147 /* Base costs on BB frequencies bounded by 1. */
148 int cost = frequency;
150 if (!cost)
151 cost = 1;
153 if (optimize_for_size)
154 cost = 1;
156 return cost;
160 /* Return the cost of executing a copy instruction in basic block BB. */
162 static inline int
163 coalesce_cost_bb (basic_block bb)
165 return coalesce_cost (bb->frequency, optimize_bb_for_size_p (bb));
169 /* Return the cost of executing a copy instruction on edge E. */
171 static inline int
172 coalesce_cost_edge (edge e)
174 int mult = 1;
176 /* Inserting copy on critical edge costs more than inserting it elsewhere. */
177 if (EDGE_CRITICAL_P (e))
178 mult = 2;
179 if (e->flags & EDGE_ABNORMAL)
180 return MUST_COALESCE_COST;
181 if (e->flags & EDGE_EH)
183 edge e2;
184 edge_iterator ei;
185 FOR_EACH_EDGE (e2, ei, e->dest->preds)
186 if (e2 != e)
188 /* Putting code on EH edge that leads to BB
189 with multiple predecestors imply splitting of
190 edge too. */
191 if (mult < 2)
192 mult = 2;
193 /* If there are multiple EH predecestors, we
194 also copy EH regions and produce separate
195 landing pad. This is expensive. */
196 if (e2->flags & EDGE_EH)
198 mult = 5;
199 break;
204 return coalesce_cost (EDGE_FREQUENCY (e),
205 optimize_edge_for_size_p (e)) * mult;
209 /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
210 2 elements via P1 and P2. 1 is returned by the function if there is a pair,
211 NO_BEST_COALESCE is returned if there aren't any. */
213 static inline int
214 pop_cost_one_pair (coalesce_list *cl, int *p1, int *p2)
216 cost_one_pair *ptr;
218 ptr = cl->cost_one_list;
219 if (!ptr)
220 return NO_BEST_COALESCE;
222 *p1 = ptr->first_element;
223 *p2 = ptr->second_element;
224 cl->cost_one_list = ptr->next;
226 free (ptr);
228 return 1;
231 /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
232 2 elements via P1 and P2. Their calculated cost is returned by the function.
233 NO_BEST_COALESCE is returned if the coalesce list is empty. */
235 static inline int
236 pop_best_coalesce (coalesce_list *cl, int *p1, int *p2)
238 coalesce_pair *node;
239 int ret;
241 if (cl->sorted == NULL)
242 return pop_cost_one_pair (cl, p1, p2);
244 if (cl->num_sorted == 0)
245 return pop_cost_one_pair (cl, p1, p2);
247 node = cl->sorted[--(cl->num_sorted)];
248 *p1 = node->first_element;
249 *p2 = node->second_element;
250 ret = node->cost;
251 free (node);
253 return ret;
257 /* Create a new empty coalesce list object and return it. */
259 static inline coalesce_list *
260 create_coalesce_list (void)
262 coalesce_list *list;
263 unsigned size = num_ssa_names * 3;
265 if (size < 40)
266 size = 40;
268 list = (coalesce_list *) xmalloc (sizeof (struct coalesce_list));
269 list->list = new coalesce_table_type (size);
270 list->sorted = NULL;
271 list->num_sorted = 0;
272 list->cost_one_list = NULL;
273 return list;
277 /* Delete coalesce list CL. */
279 static inline void
280 delete_coalesce_list (coalesce_list *cl)
282 gcc_assert (cl->cost_one_list == NULL);
283 delete cl->list;
284 cl->list = NULL;
285 free (cl->sorted);
286 gcc_assert (cl->num_sorted == 0);
287 free (cl);
290 /* Return the number of unique coalesce pairs in CL. */
292 static inline int
293 num_coalesce_pairs (coalesce_list *cl)
295 return cl->list->elements ();
298 /* Find a matching coalesce pair object in CL for the pair P1 and P2. If
299 one isn't found, return NULL if CREATE is false, otherwise create a new
300 coalesce pair object and return it. */
302 static coalesce_pair *
303 find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
305 struct coalesce_pair p;
306 coalesce_pair **slot;
307 unsigned int hash;
309 /* Normalize so that p1 is the smaller value. */
310 if (p2 < p1)
312 p.first_element = p2;
313 p.second_element = p1;
315 else
317 p.first_element = p1;
318 p.second_element = p2;
321 hash = coalesce_pair_hasher::hash (&p);
322 slot = cl->list->find_slot_with_hash (&p, hash, create ? INSERT : NO_INSERT);
323 if (!slot)
324 return NULL;
326 if (!*slot)
328 struct coalesce_pair * pair = XNEW (struct coalesce_pair);
329 gcc_assert (cl->sorted == NULL);
330 pair->first_element = p.first_element;
331 pair->second_element = p.second_element;
332 pair->cost = 0;
333 pair->index = num_coalesce_pairs (cl);
334 pair->conflict_count = 0;
335 *slot = pair;
338 return (struct coalesce_pair *) *slot;
341 static inline void
342 add_cost_one_coalesce (coalesce_list *cl, int p1, int p2)
344 cost_one_pair *pair;
346 pair = XNEW (cost_one_pair);
347 pair->first_element = p1;
348 pair->second_element = p2;
349 pair->next = cl->cost_one_list;
350 cl->cost_one_list = pair;
354 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
356 static inline void
357 add_coalesce (coalesce_list *cl, int p1, int p2, int value)
359 coalesce_pair *node;
361 gcc_assert (cl->sorted == NULL);
362 if (p1 == p2)
363 return;
365 node = find_coalesce_pair (cl, p1, p2, true);
367 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
368 if (node->cost < MUST_COALESCE_COST - 1)
370 if (value < MUST_COALESCE_COST - 1)
371 node->cost += value;
372 else
373 node->cost = value;
377 /* Compute and record how many unique conflicts would exist for the
378 representative partition for each coalesce pair in CL.
380 CONFLICTS is the conflict graph and MAP is the current partition view. */
382 static void
383 initialize_conflict_count (coalesce_pair *p,
384 ssa_conflicts *conflicts,
385 var_map map)
387 int p1 = var_to_partition (map, ssa_name (p->first_element));
388 int p2 = var_to_partition (map, ssa_name (p->second_element));
390 /* 4 cases. If both P1 and P2 have conflicts, then build their
391 union and count the members. Else handle the degenerate cases
392 in the obvious ways. */
393 if (conflicts->conflicts[p1] && conflicts->conflicts[p2])
394 p->conflict_count = bitmap_count_unique_bits (conflicts->conflicts[p1],
395 conflicts->conflicts[p2]);
396 else if (conflicts->conflicts[p1])
397 p->conflict_count = bitmap_count_bits (conflicts->conflicts[p1]);
398 else if (conflicts->conflicts[p2])
399 p->conflict_count = bitmap_count_bits (conflicts->conflicts[p2]);
400 else
401 p->conflict_count = 0;
405 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
407 static int
408 compare_pairs (const void *p1, const void *p2)
410 coalesce_pair *const *const pp1 = (coalesce_pair *const *) p1;
411 coalesce_pair *const *const pp2 = (coalesce_pair *const *) p2;
412 int result;
414 result = (* pp1)->cost - (* pp2)->cost;
415 /* We use the size of the resulting conflict set as the secondary sort key.
416 Given two equal costing coalesce pairs, we want to prefer the pair that
417 has the smaller conflict set. */
418 if (result == 0)
420 if (flag_expensive_optimizations)
422 /* Lazily initialize the conflict counts as it's fairly expensive
423 to compute. */
424 if ((*pp2)->conflict_count == 0)
425 initialize_conflict_count (*pp2, conflicts_, map_);
426 if ((*pp1)->conflict_count == 0)
427 initialize_conflict_count (*pp1, conflicts_, map_);
429 result = (*pp2)->conflict_count - (*pp1)->conflict_count;
432 /* And if everything else is equal, then sort based on which
433 coalesce pair was found first. */
434 if (result == 0)
435 result = (*pp2)->index - (*pp1)->index;
438 return result;
441 /* Iterate over CL using ITER, returning values in PAIR. */
443 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
444 FOR_EACH_HASH_TABLE_ELEMENT (*(CL)->list, (PAIR), coalesce_pair_p, (ITER))
447 /* Prepare CL for removal of preferred pairs. When finished they are sorted
448 in order from most important coalesce to least important. */
450 static void
451 sort_coalesce_list (coalesce_list *cl, ssa_conflicts *conflicts, var_map map)
453 unsigned x, num;
454 coalesce_pair *p;
455 coalesce_iterator_type ppi;
457 gcc_assert (cl->sorted == NULL);
459 num = num_coalesce_pairs (cl);
460 cl->num_sorted = num;
461 if (num == 0)
462 return;
464 /* Allocate a vector for the pair pointers. */
465 cl->sorted = XNEWVEC (coalesce_pair *, num);
467 /* Populate the vector with pointers to the pairs. */
468 x = 0;
469 FOR_EACH_PARTITION_PAIR (p, ppi, cl)
470 cl->sorted[x++] = p;
471 gcc_assert (x == num);
473 /* Already sorted. */
474 if (num == 1)
475 return;
477 /* We don't want to depend on qsort_r, so we have to stuff away
478 additional data into globals so it can be referenced in
479 compare_pairs. */
480 conflicts_ = conflicts;
481 map_ = map;
482 qsort (cl->sorted, num, sizeof (coalesce_pair *), compare_pairs);
483 conflicts_ = NULL;
484 map_ = NULL;
488 /* Send debug info for coalesce list CL to file F. */
490 static void
491 dump_coalesce_list (FILE *f, coalesce_list *cl)
493 coalesce_pair *node;
494 coalesce_iterator_type ppi;
496 int x;
497 tree var;
499 if (cl->sorted == NULL)
501 fprintf (f, "Coalesce List:\n");
502 FOR_EACH_PARTITION_PAIR (node, ppi, cl)
504 tree var1 = ssa_name (node->first_element);
505 tree var2 = ssa_name (node->second_element);
506 print_generic_expr (f, var1, TDF_SLIM);
507 fprintf (f, " <-> ");
508 print_generic_expr (f, var2, TDF_SLIM);
509 fprintf (f, " (%1d, %1d), ", node->cost, node->conflict_count);
510 fprintf (f, "\n");
513 else
515 fprintf (f, "Sorted Coalesce list:\n");
516 for (x = cl->num_sorted - 1 ; x >=0; x--)
518 node = cl->sorted[x];
519 fprintf (f, "(%d, %d) ", node->cost, node->conflict_count);
520 var = ssa_name (node->first_element);
521 print_generic_expr (f, var, TDF_SLIM);
522 fprintf (f, " <-> ");
523 var = ssa_name (node->second_element);
524 print_generic_expr (f, var, TDF_SLIM);
525 fprintf (f, "\n");
531 /* Return an empty new conflict graph for SIZE elements. */
533 static inline ssa_conflicts *
534 ssa_conflicts_new (unsigned size)
536 ssa_conflicts *ptr;
538 ptr = XNEW (ssa_conflicts);
539 bitmap_obstack_initialize (&ptr->obstack);
540 ptr->conflicts.create (size);
541 ptr->conflicts.safe_grow_cleared (size);
542 return ptr;
546 /* Free storage for conflict graph PTR. */
548 static inline void
549 ssa_conflicts_delete (ssa_conflicts *ptr)
551 bitmap_obstack_release (&ptr->obstack);
552 ptr->conflicts.release ();
553 free (ptr);
557 /* Test if elements X and Y conflict in graph PTR. */
559 static inline bool
560 ssa_conflicts_test_p (ssa_conflicts *ptr, unsigned x, unsigned y)
562 bitmap bx = ptr->conflicts[x];
563 bitmap by = ptr->conflicts[y];
565 gcc_checking_assert (x != y);
567 if (bx)
568 /* Avoid the lookup if Y has no conflicts. */
569 return by ? bitmap_bit_p (bx, y) : false;
570 else
571 return false;
575 /* Add a conflict with Y to the bitmap for X in graph PTR. */
577 static inline void
578 ssa_conflicts_add_one (ssa_conflicts *ptr, unsigned x, unsigned y)
580 bitmap bx = ptr->conflicts[x];
581 /* If there are no conflicts yet, allocate the bitmap and set bit. */
582 if (! bx)
583 bx = ptr->conflicts[x] = BITMAP_ALLOC (&ptr->obstack);
584 bitmap_set_bit (bx, y);
588 /* Add conflicts between X and Y in graph PTR. */
590 static inline void
591 ssa_conflicts_add (ssa_conflicts *ptr, unsigned x, unsigned y)
593 gcc_checking_assert (x != y);
594 ssa_conflicts_add_one (ptr, x, y);
595 ssa_conflicts_add_one (ptr, y, x);
599 /* Merge all Y's conflict into X in graph PTR. */
601 static inline void
602 ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y)
604 unsigned z;
605 bitmap_iterator bi;
606 bitmap bx = ptr->conflicts[x];
607 bitmap by = ptr->conflicts[y];
609 gcc_checking_assert (x != y);
610 if (! by)
611 return;
613 /* Add a conflict between X and every one Y has. If the bitmap doesn't
614 exist, then it has already been coalesced, and we don't need to add a
615 conflict. */
616 EXECUTE_IF_SET_IN_BITMAP (by, 0, z, bi)
618 bitmap bz = ptr->conflicts[z];
619 if (bz)
620 bitmap_set_bit (bz, x);
623 if (bx)
625 /* If X has conflicts, add Y's to X. */
626 bitmap_ior_into (bx, by);
627 BITMAP_FREE (by);
628 ptr->conflicts[y] = NULL;
630 else
632 /* If X has no conflicts, simply use Y's. */
633 ptr->conflicts[x] = by;
634 ptr->conflicts[y] = NULL;
639 /* Dump a conflicts graph. */
641 static void
642 ssa_conflicts_dump (FILE *file, ssa_conflicts *ptr)
644 unsigned x;
645 bitmap b;
647 fprintf (file, "\nConflict graph:\n");
649 FOR_EACH_VEC_ELT (ptr->conflicts, x, b)
650 if (b)
652 fprintf (file, "%d: ", x);
653 dump_bitmap (file, b);
658 /* This structure is used to efficiently record the current status of live
659 SSA_NAMES when building a conflict graph.
660 LIVE_BASE_VAR has a bit set for each base variable which has at least one
661 ssa version live.
662 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
663 index, and is used to track what partitions of each base variable are
664 live. This makes it easy to add conflicts between just live partitions
665 with the same base variable.
666 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
667 marked as being live. This delays clearing of these bitmaps until
668 they are actually needed again. */
670 struct live_track
672 bitmap_obstack obstack; /* A place to allocate our bitmaps. */
673 bitmap live_base_var; /* Indicates if a basevar is live. */
674 bitmap *live_base_partitions; /* Live partitions for each basevar. */
675 var_map map; /* Var_map being used for partition mapping. */
679 /* This routine will create a new live track structure based on the partitions
680 in MAP. */
682 static live_track *
683 new_live_track (var_map map)
685 live_track *ptr;
686 int lim, x;
688 /* Make sure there is a partition view in place. */
689 gcc_assert (map->partition_to_base_index != NULL);
691 ptr = (live_track *) xmalloc (sizeof (live_track));
692 ptr->map = map;
693 lim = num_basevars (map);
694 bitmap_obstack_initialize (&ptr->obstack);
695 ptr->live_base_partitions = (bitmap *) xmalloc (sizeof (bitmap *) * lim);
696 ptr->live_base_var = BITMAP_ALLOC (&ptr->obstack);
697 for (x = 0; x < lim; x++)
698 ptr->live_base_partitions[x] = BITMAP_ALLOC (&ptr->obstack);
699 return ptr;
703 /* This routine will free the memory associated with PTR. */
705 static void
706 delete_live_track (live_track *ptr)
708 bitmap_obstack_release (&ptr->obstack);
709 free (ptr->live_base_partitions);
710 free (ptr);
714 /* This function will remove PARTITION from the live list in PTR. */
716 static inline void
717 live_track_remove_partition (live_track *ptr, int partition)
719 int root;
721 root = basevar_index (ptr->map, partition);
722 bitmap_clear_bit (ptr->live_base_partitions[root], partition);
723 /* If the element list is empty, make the base variable not live either. */
724 if (bitmap_empty_p (ptr->live_base_partitions[root]))
725 bitmap_clear_bit (ptr->live_base_var, root);
729 /* This function will adds PARTITION to the live list in PTR. */
731 static inline void
732 live_track_add_partition (live_track *ptr, int partition)
734 int root;
736 root = basevar_index (ptr->map, partition);
737 /* If this base var wasn't live before, it is now. Clear the element list
738 since it was delayed until needed. */
739 if (bitmap_set_bit (ptr->live_base_var, root))
740 bitmap_clear (ptr->live_base_partitions[root]);
741 bitmap_set_bit (ptr->live_base_partitions[root], partition);
746 /* Clear the live bit for VAR in PTR. */
748 static inline void
749 live_track_clear_var (live_track *ptr, tree var)
751 int p;
753 p = var_to_partition (ptr->map, var);
754 if (p != NO_PARTITION)
755 live_track_remove_partition (ptr, p);
759 /* Return TRUE if VAR is live in PTR. */
761 static inline bool
762 live_track_live_p (live_track *ptr, tree var)
764 int p, root;
766 p = var_to_partition (ptr->map, var);
767 if (p != NO_PARTITION)
769 root = basevar_index (ptr->map, p);
770 if (bitmap_bit_p (ptr->live_base_var, root))
771 return bitmap_bit_p (ptr->live_base_partitions[root], p);
773 return false;
777 /* This routine will add USE to PTR. USE will be marked as live in both the
778 ssa live map and the live bitmap for the root of USE. */
780 static inline void
781 live_track_process_use (live_track *ptr, tree use)
783 int p;
785 p = var_to_partition (ptr->map, use);
786 if (p == NO_PARTITION)
787 return;
789 /* Mark as live in the appropriate live list. */
790 live_track_add_partition (ptr, p);
794 /* This routine will process a DEF in PTR. DEF will be removed from the live
795 lists, and if there are any other live partitions with the same base
796 variable, conflicts will be added to GRAPH. */
798 static inline void
799 live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph)
801 int p, root;
802 bitmap b;
803 unsigned x;
804 bitmap_iterator bi;
806 p = var_to_partition (ptr->map, def);
807 if (p == NO_PARTITION)
808 return;
810 /* Clear the liveness bit. */
811 live_track_remove_partition (ptr, p);
813 /* If the bitmap isn't empty now, conflicts need to be added. */
814 root = basevar_index (ptr->map, p);
815 if (bitmap_bit_p (ptr->live_base_var, root))
817 b = ptr->live_base_partitions[root];
818 EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
819 ssa_conflicts_add (graph, p, x);
824 /* Initialize PTR with the partitions set in INIT. */
826 static inline void
827 live_track_init (live_track *ptr, bitmap init)
829 unsigned p;
830 bitmap_iterator bi;
832 /* Mark all live on exit partitions. */
833 EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
834 live_track_add_partition (ptr, p);
838 /* This routine will clear all live partitions in PTR. */
840 static inline void
841 live_track_clear_base_vars (live_track *ptr)
843 /* Simply clear the live base list. Anything marked as live in the element
844 lists will be cleared later if/when the base variable ever comes alive
845 again. */
846 bitmap_clear (ptr->live_base_var);
850 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
851 partition view of the var_map liveinfo is based on get entries in the
852 conflict graph. Only conflicts between ssa_name partitions with the same
853 base variable are added. */
855 static ssa_conflicts *
856 build_ssa_conflict_graph (tree_live_info_p liveinfo)
858 ssa_conflicts *graph;
859 var_map map;
860 basic_block bb;
861 ssa_op_iter iter;
862 live_track *live;
863 basic_block entry;
865 /* If inter-variable coalescing is enabled, we may attempt to
866 coalesce variables from different base variables, including
867 different parameters, so we have to make sure default defs live
868 at the entry block conflict with each other. */
869 if (flag_tree_coalesce_vars)
870 entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
871 else
872 entry = NULL;
874 map = live_var_map (liveinfo);
875 graph = ssa_conflicts_new (num_var_partitions (map));
877 live = new_live_track (map);
879 FOR_EACH_BB_FN (bb, cfun)
881 /* Start with live on exit temporaries. */
882 live_track_init (live, live_on_exit (liveinfo, bb));
884 for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
885 gsi_prev (&gsi))
887 tree var;
888 gimple *stmt = gsi_stmt (gsi);
890 /* A copy between 2 partitions does not introduce an interference
891 by itself. If they did, you would never be able to coalesce
892 two things which are copied. If the two variables really do
893 conflict, they will conflict elsewhere in the program.
895 This is handled by simply removing the SRC of the copy from the
896 live list, and processing the stmt normally. */
897 if (is_gimple_assign (stmt))
899 tree lhs = gimple_assign_lhs (stmt);
900 tree rhs1 = gimple_assign_rhs1 (stmt);
901 if (gimple_assign_copy_p (stmt)
902 && TREE_CODE (lhs) == SSA_NAME
903 && TREE_CODE (rhs1) == SSA_NAME)
904 live_track_clear_var (live, rhs1);
906 else if (is_gimple_debug (stmt))
907 continue;
909 /* For stmts with more than one SSA_NAME definition pretend all the
910 SSA_NAME outputs but the first one are live at this point, so
911 that conflicts are added in between all those even when they are
912 actually not really live after the asm, because expansion might
913 copy those into pseudos after the asm and if multiple outputs
914 share the same partition, it might overwrite those that should
915 be live. E.g.
916 asm volatile (".." : "=r" (a) : "=r" (b) : "0" (a), "1" (a));
917 return a;
918 See PR70593. */
919 bool first = true;
920 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
921 if (first)
922 first = false;
923 else
924 live_track_process_use (live, var);
926 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
927 live_track_process_def (live, var, graph);
929 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
930 live_track_process_use (live, var);
933 /* If result of a PHI is unused, looping over the statements will not
934 record any conflicts since the def was never live. Since the PHI node
935 is going to be translated out of SSA form, it will insert a copy.
936 There must be a conflict recorded between the result of the PHI and
937 any variables that are live. Otherwise the out-of-ssa translation
938 may create incorrect code. */
939 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
940 gsi_next (&gsi))
942 gphi *phi = gsi.phi ();
943 tree result = PHI_RESULT (phi);
944 if (live_track_live_p (live, result))
945 live_track_process_def (live, result, graph);
948 /* Pretend there are defs for params' default defs at the start
949 of the (post-)entry block. This will prevent PARM_DECLs from
950 coalescing into the same partition. Although RESULT_DECLs'
951 default defs don't have a useful initial value, we have to
952 prevent them from coalescing with PARM_DECLs' default defs
953 too, otherwise assign_parms would attempt to assign different
954 RTL to the same partition. */
955 if (bb == entry)
957 unsigned i;
958 for (i = 1; i < num_ssa_names; i++)
960 tree var = ssa_name (i);
962 if (!var
963 || !SSA_NAME_IS_DEFAULT_DEF (var)
964 || !SSA_NAME_VAR (var)
965 || VAR_P (SSA_NAME_VAR (var)))
966 continue;
968 live_track_process_def (live, var, graph);
969 /* Process a use too, so that it remains live and
970 conflicts with other parms' default defs, even unused
971 ones. */
972 live_track_process_use (live, var);
976 live_track_clear_base_vars (live);
979 delete_live_track (live);
980 return graph;
984 /* Shortcut routine to print messages to file F of the form:
985 "STR1 EXPR1 STR2 EXPR2 STR3." */
987 static inline void
988 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
989 tree expr2, const char *str3)
991 fprintf (f, "%s", str1);
992 print_generic_expr (f, expr1, TDF_SLIM);
993 fprintf (f, "%s", str2);
994 print_generic_expr (f, expr2, TDF_SLIM);
995 fprintf (f, "%s", str3);
999 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
1001 static inline void
1002 fail_abnormal_edge_coalesce (int x, int y)
1004 fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
1005 fprintf (stderr, " which are marked as MUST COALESCE.\n");
1006 print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
1007 fprintf (stderr, " and ");
1008 print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
1010 internal_error ("SSA corruption");
1013 /* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
1014 assign_parms may ask for a default partition. */
1016 static void
1017 for_all_parms (void (*callback)(tree var, void *arg), void *arg)
1019 for (tree var = DECL_ARGUMENTS (current_function_decl); var;
1020 var = DECL_CHAIN (var))
1021 callback (var, arg);
1022 if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
1023 callback (DECL_RESULT (current_function_decl), arg);
1024 if (cfun->static_chain_decl)
1025 callback (cfun->static_chain_decl, arg);
1028 /* Create a default def for VAR. */
1030 static void
1031 create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
1033 if (!is_gimple_reg (var))
1034 return;
1036 tree ssa = get_or_create_ssa_default_def (cfun, var);
1037 gcc_assert (ssa);
1040 /* Register VAR's default def in MAP. */
1042 static void
1043 register_default_def (tree var, void *map_)
1045 var_map map = (var_map)map_;
1047 if (!is_gimple_reg (var))
1048 return;
1050 tree ssa = ssa_default_def (cfun, var);
1051 gcc_assert (ssa);
1053 register_ssa_partition (map, ssa);
1056 /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
1057 and the DECL's default def is unused (i.e., it was introduced by
1058 create_default_def), mark VAR and the default def for
1059 coalescing. */
1061 static void
1062 coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
1064 if (SSA_NAME_IS_DEFAULT_DEF (var)
1065 || !SSA_NAME_VAR (var)
1066 || VAR_P (SSA_NAME_VAR (var)))
1067 return;
1069 tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var));
1070 if (!has_zero_uses (ssa))
1071 return;
1073 add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var));
1074 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1075 /* Default defs will have their used_in_copy bits set at the end of
1076 create_outofssa_var_map. */
1079 /* This function creates a var_map for the current function as well as creating
1080 a coalesce list for use later in the out of ssa process. */
1082 static var_map
1083 create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
1085 gimple_stmt_iterator gsi;
1086 basic_block bb;
1087 tree var;
1088 gimple *stmt;
1089 tree first;
1090 var_map map;
1091 ssa_op_iter iter;
1092 int v1, v2, cost;
1093 unsigned i;
1095 for_all_parms (create_default_def, NULL);
1097 map = init_var_map (num_ssa_names);
1099 for_all_parms (register_default_def, map);
1101 FOR_EACH_BB_FN (bb, cfun)
1103 tree arg;
1105 for (gphi_iterator gpi = gsi_start_phis (bb);
1106 !gsi_end_p (gpi);
1107 gsi_next (&gpi))
1109 gphi *phi = gpi.phi ();
1110 size_t i;
1111 int ver;
1112 tree res;
1113 bool saw_copy = false;
1115 res = gimple_phi_result (phi);
1116 ver = SSA_NAME_VERSION (res);
1117 register_ssa_partition (map, res);
1119 /* Register ssa_names and coalesces between the args and the result
1120 of all PHI. */
1121 for (i = 0; i < gimple_phi_num_args (phi); i++)
1123 edge e = gimple_phi_arg_edge (phi, i);
1124 arg = PHI_ARG_DEF (phi, i);
1125 if (TREE_CODE (arg) != SSA_NAME)
1126 continue;
1128 register_ssa_partition (map, arg);
1129 if (gimple_can_coalesce_p (arg, res)
1130 || (e->flags & EDGE_ABNORMAL))
1132 saw_copy = true;
1133 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1134 if ((e->flags & EDGE_ABNORMAL) == 0)
1136 int cost = coalesce_cost_edge (e);
1137 if (cost == 1 && has_single_use (arg))
1138 add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1139 else
1140 add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1144 if (saw_copy)
1145 bitmap_set_bit (used_in_copy, ver);
1148 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1150 stmt = gsi_stmt (gsi);
1152 if (is_gimple_debug (stmt))
1153 continue;
1155 /* Register USE and DEF operands in each statement. */
1156 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
1157 register_ssa_partition (map, var);
1159 /* Check for copy coalesces. */
1160 switch (gimple_code (stmt))
1162 case GIMPLE_ASSIGN:
1164 tree lhs = gimple_assign_lhs (stmt);
1165 tree rhs1 = gimple_assign_rhs1 (stmt);
1166 if (gimple_assign_ssa_name_copy_p (stmt)
1167 && gimple_can_coalesce_p (lhs, rhs1))
1169 v1 = SSA_NAME_VERSION (lhs);
1170 v2 = SSA_NAME_VERSION (rhs1);
1171 cost = coalesce_cost_bb (bb);
1172 add_coalesce (cl, v1, v2, cost);
1173 bitmap_set_bit (used_in_copy, v1);
1174 bitmap_set_bit (used_in_copy, v2);
1177 break;
1179 case GIMPLE_RETURN:
1181 tree res = DECL_RESULT (current_function_decl);
1182 if (VOID_TYPE_P (TREE_TYPE (res))
1183 || !is_gimple_reg (res))
1184 break;
1185 tree rhs1 = gimple_return_retval (as_a <greturn *> (stmt));
1186 if (!rhs1)
1187 break;
1188 tree lhs = ssa_default_def (cfun, res);
1189 gcc_assert (lhs);
1190 if (TREE_CODE (rhs1) == SSA_NAME
1191 && gimple_can_coalesce_p (lhs, rhs1))
1193 v1 = SSA_NAME_VERSION (lhs);
1194 v2 = SSA_NAME_VERSION (rhs1);
1195 cost = coalesce_cost_bb (bb);
1196 add_coalesce (cl, v1, v2, cost);
1197 bitmap_set_bit (used_in_copy, v1);
1198 bitmap_set_bit (used_in_copy, v2);
1200 break;
1203 case GIMPLE_ASM:
1205 gasm *asm_stmt = as_a <gasm *> (stmt);
1206 unsigned long noutputs, i;
1207 unsigned long ninputs;
1208 tree *outputs, link;
1209 noutputs = gimple_asm_noutputs (asm_stmt);
1210 ninputs = gimple_asm_ninputs (asm_stmt);
1211 outputs = (tree *) alloca (noutputs * sizeof (tree));
1212 for (i = 0; i < noutputs; ++i)
1214 link = gimple_asm_output_op (asm_stmt, i);
1215 outputs[i] = TREE_VALUE (link);
1218 for (i = 0; i < ninputs; ++i)
1220 const char *constraint;
1221 tree input;
1222 char *end;
1223 unsigned long match;
1225 link = gimple_asm_input_op (asm_stmt, i);
1226 constraint
1227 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1228 input = TREE_VALUE (link);
1230 if (TREE_CODE (input) != SSA_NAME)
1231 continue;
1233 match = strtoul (constraint, &end, 10);
1234 if (match >= noutputs || end == constraint)
1235 continue;
1237 if (TREE_CODE (outputs[match]) != SSA_NAME)
1238 continue;
1240 v1 = SSA_NAME_VERSION (outputs[match]);
1241 v2 = SSA_NAME_VERSION (input);
1243 if (gimple_can_coalesce_p (outputs[match], input))
1245 cost = coalesce_cost (REG_BR_PROB_BASE,
1246 optimize_bb_for_size_p (bb));
1247 add_coalesce (cl, v1, v2, cost);
1248 bitmap_set_bit (used_in_copy, v1);
1249 bitmap_set_bit (used_in_copy, v2);
1252 break;
1255 default:
1256 break;
1261 /* Now process result decls and live on entry variables for entry into
1262 the coalesce list. */
1263 first = NULL_TREE;
1264 for (i = 1; i < num_ssa_names; i++)
1266 var = ssa_name (i);
1267 if (var != NULL_TREE && !virtual_operand_p (var))
1269 coalesce_with_default (var, cl, used_in_copy);
1271 /* Add coalesces between all the result decls. */
1272 if (SSA_NAME_VAR (var)
1273 && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1275 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1276 if (first == NULL_TREE)
1277 first = var;
1278 else
1280 gcc_assert (gimple_can_coalesce_p (var, first));
1281 v1 = SSA_NAME_VERSION (first);
1282 v2 = SSA_NAME_VERSION (var);
1283 cost = coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
1284 add_coalesce (cl, v1, v2, cost);
1287 /* Mark any default_def variables as being in the coalesce list
1288 since they will have to be coalesced with the base variable. If
1289 not marked as present, they won't be in the coalesce view. */
1290 if (SSA_NAME_IS_DEFAULT_DEF (var)
1291 && (!has_zero_uses (var)
1292 || (SSA_NAME_VAR (var)
1293 && !VAR_P (SSA_NAME_VAR (var)))))
1294 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1298 return map;
1302 /* Attempt to coalesce ssa versions X and Y together using the partition
1303 mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1304 DEBUG, if it is nun-NULL. */
1306 static inline bool
1307 attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y,
1308 FILE *debug)
1310 int z;
1311 tree var1, var2;
1312 int p1, p2;
1314 p1 = var_to_partition (map, ssa_name (x));
1315 p2 = var_to_partition (map, ssa_name (y));
1317 if (debug)
1319 fprintf (debug, "(%d)", x);
1320 print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1321 fprintf (debug, " & (%d)", y);
1322 print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1325 if (p1 == p2)
1327 if (debug)
1328 fprintf (debug, ": Already Coalesced.\n");
1329 return true;
1332 if (debug)
1333 fprintf (debug, " [map: %d, %d] ", p1, p2);
1336 if (!ssa_conflicts_test_p (graph, p1, p2))
1338 var1 = partition_to_var (map, p1);
1339 var2 = partition_to_var (map, p2);
1341 z = var_union (map, var1, var2);
1342 if (z == NO_PARTITION)
1344 if (debug)
1345 fprintf (debug, ": Unable to perform partition union.\n");
1346 return false;
1349 /* z is the new combined partition. Remove the other partition from
1350 the list, and merge the conflicts. */
1351 if (z == p1)
1352 ssa_conflicts_merge (graph, p1, p2);
1353 else
1354 ssa_conflicts_merge (graph, p2, p1);
1356 if (debug)
1357 fprintf (debug, ": Success -> %d\n", z);
1359 return true;
1362 if (debug)
1363 fprintf (debug, ": Fail due to conflict\n");
1365 return false;
1369 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1370 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1372 static void
1373 coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
1374 FILE *debug)
1376 int x = 0, y = 0;
1377 tree var1, var2;
1378 int cost;
1379 basic_block bb;
1380 edge e;
1381 edge_iterator ei;
1383 /* First, coalesce all the copies across abnormal edges. These are not placed
1384 in the coalesce list because they do not need to be sorted, and simply
1385 consume extra memory/compilation time in large programs. */
1387 FOR_EACH_BB_FN (bb, cfun)
1389 FOR_EACH_EDGE (e, ei, bb->preds)
1390 if (e->flags & EDGE_ABNORMAL)
1392 gphi_iterator gsi;
1393 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1394 gsi_next (&gsi))
1396 gphi *phi = gsi.phi ();
1397 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1398 if (SSA_NAME_IS_DEFAULT_DEF (arg)
1399 && (!SSA_NAME_VAR (arg)
1400 || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1401 continue;
1403 tree res = PHI_RESULT (phi);
1404 int v1 = SSA_NAME_VERSION (res);
1405 int v2 = SSA_NAME_VERSION (arg);
1407 if (debug)
1408 fprintf (debug, "Abnormal coalesce: ");
1410 if (!attempt_coalesce (map, graph, v1, v2, debug))
1411 fail_abnormal_edge_coalesce (v1, v2);
1416 /* Now process the items in the coalesce list. */
1418 while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1420 var1 = ssa_name (x);
1421 var2 = ssa_name (y);
1423 /* Assert the coalesces have the same base variable. */
1424 gcc_assert (gimple_can_coalesce_p (var1, var2));
1426 if (debug)
1427 fprintf (debug, "Coalesce list: ");
1428 attempt_coalesce (map, graph, x, y, debug);
1433 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1435 struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
1437 static inline hashval_t hash (const tree_node *);
1438 static inline int equal (const tree_node *, const tree_node *);
1441 inline hashval_t
1442 ssa_name_var_hash::hash (const_tree n)
1444 return DECL_UID (SSA_NAME_VAR (n));
1447 inline int
1448 ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
1450 return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
1454 /* Output partition map MAP with coalescing plan PART to file F. */
1456 void
1457 dump_part_var_map (FILE *f, partition part, var_map map)
1459 int t;
1460 unsigned x, y;
1461 int p;
1463 fprintf (f, "\nCoalescible Partition map \n\n");
1465 for (x = 0; x < map->num_partitions; x++)
1467 if (map->view_to_partition != NULL)
1468 p = map->view_to_partition[x];
1469 else
1470 p = x;
1472 if (ssa_name (p) == NULL_TREE
1473 || virtual_operand_p (ssa_name (p)))
1474 continue;
1476 t = 0;
1477 for (y = 1; y < num_ssa_names; y++)
1479 tree var = version_to_var (map, y);
1480 if (!var)
1481 continue;
1482 int q = var_to_partition (map, var);
1483 p = partition_find (part, q);
1484 gcc_assert (map->partition_to_base_index[q]
1485 == map->partition_to_base_index[p]);
1487 if (p == (int)x)
1489 if (t++ == 0)
1491 fprintf (f, "Partition %d, base %d (", x,
1492 map->partition_to_base_index[q]);
1493 print_generic_expr (f, partition_to_var (map, q), TDF_SLIM);
1494 fprintf (f, " - ");
1496 fprintf (f, "%d ", y);
1499 if (t != 0)
1500 fprintf (f, ")\n");
1502 fprintf (f, "\n");
1505 /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
1506 coalescing together, false otherwise.
1508 This must stay consistent with compute_samebase_partition_bases and
1509 compute_optimized_partition_bases. */
1511 bool
1512 gimple_can_coalesce_p (tree name1, tree name2)
1514 /* First check the SSA_NAME's associated DECL. Without
1515 optimization, we only want to coalesce if they have the same DECL
1516 or both have no associated DECL. */
1517 tree var1 = SSA_NAME_VAR (name1);
1518 tree var2 = SSA_NAME_VAR (name2);
1519 var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
1520 var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
1521 if (var1 != var2 && !flag_tree_coalesce_vars)
1522 return false;
1524 /* Now check the types. If the types are the same, then we should
1525 try to coalesce V1 and V2. */
1526 tree t1 = TREE_TYPE (name1);
1527 tree t2 = TREE_TYPE (name2);
1528 if (t1 == t2)
1530 check_modes:
1531 /* If the base variables are the same, we're good: none of the
1532 other tests below could possibly fail. */
1533 var1 = SSA_NAME_VAR (name1);
1534 var2 = SSA_NAME_VAR (name2);
1535 if (var1 == var2)
1536 return true;
1538 /* We don't want to coalesce two SSA names if one of the base
1539 variables is supposed to be a register while the other is
1540 supposed to be on the stack. Anonymous SSA names most often
1541 take registers, but when not optimizing, user variables
1542 should go on the stack, so coalescing them with the anonymous
1543 variable as the partition leader would end up assigning the
1544 user variable to a register. Don't do that! */
1545 bool reg1 = use_register_for_decl (name1);
1546 bool reg2 = use_register_for_decl (name2);
1547 if (reg1 != reg2)
1548 return false;
1550 /* Check that the promoted modes and unsignedness are the same.
1551 We don't want to coalesce if the promoted modes would be
1552 different, or if they would sign-extend differently. Only
1553 PARM_DECLs and RESULT_DECLs have different promotion rules,
1554 so skip the test if both are variables, or both are anonymous
1555 SSA_NAMEs. */
1556 int unsigned1, unsigned2;
1557 return ((!var1 || VAR_P (var1)) && (!var2 || VAR_P (var2)))
1558 || ((promote_ssa_mode (name1, &unsigned1)
1559 == promote_ssa_mode (name2, &unsigned2))
1560 && unsigned1 == unsigned2);
1563 /* If alignment requirements are different, we can't coalesce. */
1564 if (MINIMUM_ALIGNMENT (t1,
1565 var1 ? DECL_MODE (var1) : TYPE_MODE (t1),
1566 var1 ? LOCAL_DECL_ALIGNMENT (var1) : TYPE_ALIGN (t1))
1567 != MINIMUM_ALIGNMENT (t2,
1568 var2 ? DECL_MODE (var2) : TYPE_MODE (t2),
1569 var2 ? LOCAL_DECL_ALIGNMENT (var2) : TYPE_ALIGN (t2)))
1570 return false;
1572 /* If the types are not the same, see whether they are compatible. This
1573 (for example) allows coalescing when the types are fundamentally the
1574 same, but just have different names.
1576 In the non-optimized case, we must first test TYPE_CANONICAL because
1577 we use it to compute the partition_to_base_index of the map. */
1578 if (flag_tree_coalesce_vars)
1580 if (types_compatible_p (t1, t2))
1581 goto check_modes;
1583 else
1585 if (TYPE_CANONICAL (t1)
1586 && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)
1587 && types_compatible_p (t1, t2))
1588 goto check_modes;
1591 return false;
1594 /* Fill in MAP's partition_to_base_index, with one index for each
1595 partition of SSA names USED_IN_COPIES and related by CL coalesce
1596 possibilities. This must match gimple_can_coalesce_p in the
1597 optimized case. */
1599 static void
1600 compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1601 coalesce_list *cl)
1603 int parts = num_var_partitions (map);
1604 partition tentative = partition_new (parts);
1606 /* Partition the SSA versions so that, for each coalescible
1607 pair, both of its members are in the same partition in
1608 TENTATIVE. */
1609 gcc_assert (!cl->sorted);
1610 coalesce_pair *node;
1611 coalesce_iterator_type ppi;
1612 FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1614 tree v1 = ssa_name (node->first_element);
1615 int p1 = partition_find (tentative, var_to_partition (map, v1));
1616 tree v2 = ssa_name (node->second_element);
1617 int p2 = partition_find (tentative, var_to_partition (map, v2));
1619 if (p1 == p2)
1620 continue;
1622 partition_union (tentative, p1, p2);
1625 /* We have to deal with cost one pairs too. */
1626 for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1628 tree v1 = ssa_name (co->first_element);
1629 int p1 = partition_find (tentative, var_to_partition (map, v1));
1630 tree v2 = ssa_name (co->second_element);
1631 int p2 = partition_find (tentative, var_to_partition (map, v2));
1633 if (p1 == p2)
1634 continue;
1636 partition_union (tentative, p1, p2);
1639 /* And also with abnormal edges. */
1640 basic_block bb;
1641 edge e;
1642 edge_iterator ei;
1643 FOR_EACH_BB_FN (bb, cfun)
1645 FOR_EACH_EDGE (e, ei, bb->preds)
1646 if (e->flags & EDGE_ABNORMAL)
1648 gphi_iterator gsi;
1649 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1650 gsi_next (&gsi))
1652 gphi *phi = gsi.phi ();
1653 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1654 if (SSA_NAME_IS_DEFAULT_DEF (arg)
1655 && (!SSA_NAME_VAR (arg)
1656 || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1657 continue;
1659 tree res = PHI_RESULT (phi);
1661 int p1 = partition_find (tentative, var_to_partition (map, res));
1662 int p2 = partition_find (tentative, var_to_partition (map, arg));
1664 if (p1 == p2)
1665 continue;
1667 partition_union (tentative, p1, p2);
1672 map->partition_to_base_index = XCNEWVEC (int, parts);
1673 auto_vec<unsigned int> index_map (parts);
1674 if (parts)
1675 index_map.quick_grow (parts);
1677 const unsigned no_part = -1;
1678 unsigned count = parts;
1679 while (count)
1680 index_map[--count] = no_part;
1682 /* Initialize MAP's mapping from partition to base index, using
1683 as base indices an enumeration of the TENTATIVE partitions in
1684 which each SSA version ended up, so that we compute conflicts
1685 between all SSA versions that ended up in the same potential
1686 coalesce partition. */
1687 bitmap_iterator bi;
1688 unsigned i;
1689 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1691 int pidx = var_to_partition (map, ssa_name (i));
1692 int base = partition_find (tentative, pidx);
1693 if (index_map[base] != no_part)
1694 continue;
1695 index_map[base] = count++;
1698 map->num_basevars = count;
1700 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1702 int pidx = var_to_partition (map, ssa_name (i));
1703 int base = partition_find (tentative, pidx);
1704 gcc_assert (index_map[base] < count);
1705 map->partition_to_base_index[pidx] = index_map[base];
1708 if (dump_file && (dump_flags & TDF_DETAILS))
1709 dump_part_var_map (dump_file, tentative, map);
1711 partition_delete (tentative);
1714 /* Hashtable helpers. */
1716 struct tree_int_map_hasher : nofree_ptr_hash <tree_int_map>
1718 static inline hashval_t hash (const tree_int_map *);
1719 static inline bool equal (const tree_int_map *, const tree_int_map *);
1722 inline hashval_t
1723 tree_int_map_hasher::hash (const tree_int_map *v)
1725 return tree_map_base_hash (v);
1728 inline bool
1729 tree_int_map_hasher::equal (const tree_int_map *v, const tree_int_map *c)
1731 return tree_int_map_eq (v, c);
1734 /* This routine will initialize the basevar fields of MAP with base
1735 names. Partitions will share the same base if they have the same
1736 SSA_NAME_VAR, or, being anonymous variables, the same type. This
1737 must match gimple_can_coalesce_p in the non-optimized case. */
1739 static void
1740 compute_samebase_partition_bases (var_map map)
1742 int x, num_part;
1743 tree var;
1744 struct tree_int_map *m, *mapstorage;
1746 num_part = num_var_partitions (map);
1747 hash_table<tree_int_map_hasher> tree_to_index (num_part);
1748 /* We can have at most num_part entries in the hash tables, so it's
1749 enough to allocate so many map elements once, saving some malloc
1750 calls. */
1751 mapstorage = m = XNEWVEC (struct tree_int_map, num_part);
1753 /* If a base table already exists, clear it, otherwise create it. */
1754 free (map->partition_to_base_index);
1755 map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
1757 /* Build the base variable list, and point partitions at their bases. */
1758 for (x = 0; x < num_part; x++)
1760 struct tree_int_map **slot;
1761 unsigned baseindex;
1762 var = partition_to_var (map, x);
1763 if (SSA_NAME_VAR (var)
1764 && (!VAR_P (SSA_NAME_VAR (var))
1765 || !DECL_IGNORED_P (SSA_NAME_VAR (var))))
1766 m->base.from = SSA_NAME_VAR (var);
1767 else
1768 /* This restricts what anonymous SSA names we can coalesce
1769 as it restricts the sets we compute conflicts for.
1770 Using TREE_TYPE to generate sets is the easiest as
1771 type equivalency also holds for SSA names with the same
1772 underlying decl.
1774 Check gimple_can_coalesce_p when changing this code. */
1775 m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
1776 ? TYPE_CANONICAL (TREE_TYPE (var))
1777 : TREE_TYPE (var));
1778 /* If base variable hasn't been seen, set it up. */
1779 slot = tree_to_index.find_slot (m, INSERT);
1780 if (!*slot)
1782 baseindex = m - mapstorage;
1783 m->to = baseindex;
1784 *slot = m;
1785 m++;
1787 else
1788 baseindex = (*slot)->to;
1789 map->partition_to_base_index[x] = baseindex;
1792 map->num_basevars = m - mapstorage;
1794 free (mapstorage);
1797 /* Reduce the number of copies by coalescing variables in the function. Return
1798 a partition map with the resulting coalesces. */
1800 extern var_map
1801 coalesce_ssa_name (void)
1803 tree_live_info_p liveinfo;
1804 ssa_conflicts *graph;
1805 coalesce_list *cl;
1806 bitmap used_in_copies = BITMAP_ALLOC (NULL);
1807 var_map map;
1808 unsigned int i;
1810 cl = create_coalesce_list ();
1811 map = create_outofssa_var_map (cl, used_in_copies);
1813 /* If this optimization is disabled, we need to coalesce all the
1814 names originating from the same SSA_NAME_VAR so debug info
1815 remains undisturbed. */
1816 if (!flag_tree_coalesce_vars)
1818 hash_table<ssa_name_var_hash> ssa_name_hash (10);
1820 for (i = 1; i < num_ssa_names; i++)
1822 tree a = ssa_name (i);
1824 if (a
1825 && SSA_NAME_VAR (a)
1826 && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1827 && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
1828 || !VAR_P (SSA_NAME_VAR (a))))
1830 tree *slot = ssa_name_hash.find_slot (a, INSERT);
1832 if (!*slot)
1833 *slot = a;
1834 else
1836 /* If the variable is a PARM_DECL or a RESULT_DECL, we
1837 _require_ that all the names originating from it be
1838 coalesced, because there must be a single partition
1839 containing all the names so that it can be assigned
1840 the canonical RTL location of the DECL safely.
1841 If in_lto_p, a function could have been compiled
1842 originally with optimizations and only the link
1843 performed at -O0, so we can't actually require it. */
1844 const int cost
1845 = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p)
1846 ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
1847 add_coalesce (cl, SSA_NAME_VERSION (a),
1848 SSA_NAME_VERSION (*slot), cost);
1849 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a));
1850 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot));
1855 if (dump_file && (dump_flags & TDF_DETAILS))
1856 dump_var_map (dump_file, map);
1858 partition_view_bitmap (map, used_in_copies);
1860 if (flag_tree_coalesce_vars)
1861 compute_optimized_partition_bases (map, used_in_copies, cl);
1862 else
1863 compute_samebase_partition_bases (map);
1865 BITMAP_FREE (used_in_copies);
1867 if (num_var_partitions (map) < 1)
1869 delete_coalesce_list (cl);
1870 return map;
1873 if (dump_file && (dump_flags & TDF_DETAILS))
1874 dump_var_map (dump_file, map);
1876 liveinfo = calculate_live_ranges (map, false);
1878 if (dump_file && (dump_flags & TDF_DETAILS))
1879 dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1881 /* Build a conflict graph. */
1882 graph = build_ssa_conflict_graph (liveinfo);
1883 delete_tree_live_info (liveinfo);
1884 if (dump_file && (dump_flags & TDF_DETAILS))
1885 ssa_conflicts_dump (dump_file, graph);
1887 sort_coalesce_list (cl, graph, map);
1889 if (dump_file && (dump_flags & TDF_DETAILS))
1891 fprintf (dump_file, "\nAfter sorting:\n");
1892 dump_coalesce_list (dump_file, cl);
1895 /* First, coalesce all live on entry variables to their base variable.
1896 This will ensure the first use is coming from the correct location. */
1898 if (dump_file && (dump_flags & TDF_DETAILS))
1899 dump_var_map (dump_file, map);
1901 /* Now coalesce everything in the list. */
1902 coalesce_partitions (map, graph, cl,
1903 ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1905 delete_coalesce_list (cl);
1906 ssa_conflicts_delete (graph);
1908 return map;
1911 /* We need to pass two arguments to set_parm_default_def_partition,
1912 but for_all_parms only supports one. Use a pair. */
1914 typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
1916 /* Set in ARG's PARTS bitmap the bit corresponding to the partition in
1917 ARG's MAP containing VAR's default def. */
1919 static void
1920 set_parm_default_def_partition (tree var, void *arg_)
1922 parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
1923 var_map map = arg->first;
1924 bitmap parts = arg->second;
1926 if (!is_gimple_reg (var))
1927 return;
1929 tree ssa = ssa_default_def (cfun, var);
1930 gcc_assert (ssa);
1932 int version = var_to_partition (map, ssa);
1933 gcc_assert (version != NO_PARTITION);
1935 bool changed = bitmap_set_bit (parts, version);
1936 gcc_assert (changed);
1939 /* Allocate and return a bitmap that has a bit set for each partition
1940 that contains a default def for a parameter. */
1942 extern bitmap
1943 get_parm_default_def_partitions (var_map map)
1945 bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
1947 parm_default_def_partition_arg
1948 arg = std::make_pair (map, parm_default_def_parts);
1950 for_all_parms (set_parm_default_def_partition, &arg);
1952 return parm_default_def_parts;