1/* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
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"
41
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. */
47
48/* This structure defines a pair entry. */
49
50struct coalesce_pair
51{
52 int first_element;
53 int second_element;
54 int cost;
55
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.
60
61 This is lazily initialized when we discover two coalescing pairs have
62 the same primary cost.
63
64 Note this is not updated and propagated as pairs are coalesced. */
65 int conflict_count;
66
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;
71};
72
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. */
76
77struct ssa_conflicts
78{
79 bitmap_obstack obstack; /* A place to allocate our bitmaps. */
80 vec<bitmap> conflicts;
81};
82
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. */
87static ssa_conflicts *conflicts_;
88static var_map map_;
89
90/* Coalesce pair hashtable helpers. */
91
92struct coalesce_pair_hasher : nofree_ptr_hash <coalesce_pair>
93{
94 static inline hashval_t hash (const coalesce_pair *);
95 static inline bool equal (const coalesce_pair *, const coalesce_pair *);
96};
97
98/* Hash function for coalesce list. Calculate hash for PAIR. */
99
100inline hashval_t
101coalesce_pair_hasher::hash (const coalesce_pair *pair)
102{
103 hashval_t a = (hashval_t)(pair->first_element);
104 hashval_t b = (hashval_t)(pair->second_element);
105
106 return b * (b - 1) / 2 + a;
107}
108
109/* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2,
110 returning TRUE if the two pairs are equivalent. */
111
112inline bool
113coalesce_pair_hasher::equal (const coalesce_pair *p1, const coalesce_pair *p2)
114{
115 return (p1->first_element == p2->first_element
116 && p1->second_element == p2->second_element);
117}
118
119typedef hash_table<coalesce_pair_hasher> coalesce_table_type;
120typedef coalesce_table_type::iterator coalesce_iterator_type;
121
122
123struct cost_one_pair
124{
125 int first_element;
126 int second_element;
127 cost_one_pair *next;
128};
129
130/* This structure maintains the list of coalesce pairs. */
131
132struct coalesce_list
133{
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. */
138};
139
140#define NO_BEST_COALESCE -1
141#define MUST_COALESCE_COST INT_MAX
142
143
144/* Return cost of execution of copy instruction with FREQUENCY. */
145
146static inline int
147coalesce_cost (int frequency, bool optimize_for_size)
148{
149 /* Base costs on BB frequencies bounded by 1. */
150 int cost = frequency;
151
152 if (!cost)
153 cost = 1;
154
155 if (optimize_for_size)
156 cost = 1;
157
158 return cost;
159}
160
161
162/* Return the cost of executing a copy instruction in basic block BB. */
163
164static inline int
165coalesce_cost_bb (basic_block bb)
166{
167 return coalesce_cost (bb->count.to_frequency (cfun),
168 optimize_bb_for_size_p (bb));
169}
170
171
172/* Return the cost of executing a copy instruction on edge E. */
173
174static inline int
175coalesce_cost_edge (edge e)
176{
177 int mult = 1;
178
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)
185 {
186 edge e2;
187 edge_iterator ei;
188 FOR_EACH_EDGE (e2, ei, e->dest->preds)
189 if (e2 != e)
190 {
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)
200 {
201 mult = 5;
202 break;
203 }
204 }
205 }
206
207 return coalesce_cost (EDGE_FREQUENCY (e),
208 optimize_edge_for_size_p (e)) * mult;
209}
210
211
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. */
215
216static inline int
217pop_cost_one_pair (coalesce_list *cl, int *p1, int *p2)
218{
219 cost_one_pair *ptr;
220
221 ptr = cl->cost_one_list;
222 if (!ptr)
223 return NO_BEST_COALESCE;
224
225 *p1 = ptr->first_element;
226 *p2 = ptr->second_element;
227 cl->cost_one_list = ptr->next;
228
229 free (ptr);
230
231 return 1;
232}
233
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. */
237
238static inline int
239pop_best_coalesce (coalesce_list *cl, int *p1, int *p2)
240{
241 coalesce_pair *node;
242 int ret;
243
244 if (cl->sorted == NULL)
245 return pop_cost_one_pair (cl, p1, p2);
246
247 if (cl->num_sorted == 0)
248 return pop_cost_one_pair (cl, p1, p2);
249
250 node = cl->sorted[--(cl->num_sorted)];
251 *p1 = node->first_element;
252 *p2 = node->second_element;
253 ret = node->cost;
254 free (node);
255
256 return ret;
257}
258
259
260/* Create a new empty coalesce list object and return it. */
261
262static inline coalesce_list *
263create_coalesce_list (void)
264{
265 coalesce_list *list;
266 unsigned size = num_ssa_names * 3;
267
268 if (size < 40)
269 size = 40;
270
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;
277}
278
279
280/* Delete coalesce list CL. */
281
282static inline void
283delete_coalesce_list (coalesce_list *cl)
284{
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);
291}
292
293/* Return the number of unique coalesce pairs in CL. */
294
295static inline int
296num_coalesce_pairs (coalesce_list *cl)
297{
298 return cl->list->elements ();
299}
300
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. */
304
305static coalesce_pair *
306find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
307{
308 struct coalesce_pair p;
309 coalesce_pair **slot;
310 unsigned int hash;
311
312 /* Normalize so that p1 is the smaller value. */
313 if (p2 < p1)
314 {
315 p.first_element = p2;
316 p.second_element = p1;
317 }
318 else
319 {
320 p.first_element = p1;
321 p.second_element = p2;
322 }
323
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;
328
329 if (!*slot)
330 {
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;
339 }
340
341 return (struct coalesce_pair *) *slot;
342}
343
344static inline void
345add_cost_one_coalesce (coalesce_list *cl, int p1, int p2)
346{
347 cost_one_pair *pair;
348
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;
354}
355
356
357/* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
358
359static inline void
360add_coalesce (coalesce_list *cl, int p1, int p2, int value)
361{
362 coalesce_pair *node;
363
364 gcc_assert (cl->sorted == NULL);
365 if (p1 == p2)
366 return;
367
368 node = find_coalesce_pair (cl, p1, p2, true);
369
370 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
371 if (node->cost < MUST_COALESCE_COST - 1)
372 {
373 if (value < MUST_COALESCE_COST - 1)
374 node->cost += value;
375 else
376 node->cost = value;
377 }
378}
379
380/* Compute and record how many unique conflicts would exist for the
381 representative partition for each coalesce pair in CL.
382
383 CONFLICTS is the conflict graph and MAP is the current partition view. */
384
385static void
386initialize_conflict_count (coalesce_pair *p,
387 ssa_conflicts *conflicts,
388 var_map map)
389{
390 int p1 = var_to_partition (map, ssa_name (p->first_element));
391 int p2 = var_to_partition (map, ssa_name (p->second_element));
392
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;
405}
406
407
408/* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
409
410static int
411compare_pairs (const void *p1, const void *p2)
412{
413 coalesce_pair *const *const pp1 = (coalesce_pair *const *) p1;
414 coalesce_pair *const *const pp2 = (coalesce_pair *const *) p2;
415 int result;
416
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)
422 {
423 if (flag_expensive_optimizations)
424 {
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_);
431
432 result = (*pp2)->conflict_count - (*pp1)->conflict_count;
433 }
434
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;
439 }
440
441 return result;
442}
443
444/* Iterate over CL using ITER, returning values in PAIR. */
445
446#define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
447 FOR_EACH_HASH_TABLE_ELEMENT (*(CL)->list, (PAIR), coalesce_pair_p, (ITER))
448
449
450/* Prepare CL for removal of preferred pairs. When finished they are sorted
451 in order from most important coalesce to least important. */
452
453static void
454sort_coalesce_list (coalesce_list *cl, ssa_conflicts *conflicts, var_map map)
455{
456 unsigned x, num;
457 coalesce_pair *p;
458 coalesce_iterator_type ppi;
459
460 gcc_assert (cl->sorted == NULL);
461
462 num = num_coalesce_pairs (cl);
463 cl->num_sorted = num;
464 if (num == 0)
465 return;
466
467 /* Allocate a vector for the pair pointers. */
468 cl->sorted = XNEWVEC (coalesce_pair *, num);
469
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);
475
476 /* Already sorted. */
477 if (num == 1)
478 return;
479
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;
488}
489
490
491/* Send debug info for coalesce list CL to file F. */
492
493static void
494dump_coalesce_list (FILE *f, coalesce_list *cl)
495{
496 coalesce_pair *node;
497 coalesce_iterator_type ppi;
498
499 int x;
500 tree var;
501
502 if (cl->sorted == NULL)
503 {
504 fprintf (f, "Coalesce List:\n");
505 FOR_EACH_PARTITION_PAIR (node, ppi, cl)
506 {
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");
514 }
515 }
516 else
517 {
518 fprintf (f, "Sorted Coalesce list:\n");
519 for (x = cl->num_sorted - 1 ; x >=0; x--)
520 {
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");
529 }
530 }
531}
532
533
534/* Return an empty new conflict graph for SIZE elements. */
535
536static inline ssa_conflicts *
537ssa_conflicts_new (unsigned size)
538{
539 ssa_conflicts *ptr;
540
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;
546}
547
548
549/* Free storage for conflict graph PTR. */
550
551static inline void
552ssa_conflicts_delete (ssa_conflicts *ptr)
553{
554 bitmap_obstack_release (&ptr->obstack);
555 ptr->conflicts.release ();
556 free (ptr);
557}
558
559
560/* Test if elements X and Y conflict in graph PTR. */
561
562static inline bool
563ssa_conflicts_test_p (ssa_conflicts *ptr, unsigned x, unsigned y)
564{
565 bitmap bx = ptr->conflicts[x];
566 bitmap by = ptr->conflicts[y];
567
568 gcc_checking_assert (x != y);
569
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;
575}
576
577
578/* Add a conflict with Y to the bitmap for X in graph PTR. */
579
580static inline void
581ssa_conflicts_add_one (ssa_conflicts *ptr, unsigned x, unsigned y)
582{
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);
588}
589
590
591/* Add conflicts between X and Y in graph PTR. */
592
593static inline void
594ssa_conflicts_add (ssa_conflicts *ptr, unsigned x, unsigned y)
595{
596 gcc_checking_assert (x != y);
597 ssa_conflicts_add_one (ptr, x, y);
598 ssa_conflicts_add_one (ptr, y, x);
599}
600
601
602/* Merge all Y's conflict into X in graph PTR. */
603
604static inline void
605ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y)
606{
607 unsigned z;
608 bitmap_iterator bi;
609 bitmap bx = ptr->conflicts[x];
610 bitmap by = ptr->conflicts[y];
611
612 gcc_checking_assert (x != y);
613 if (! by)
614 return;
615
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)
620 {
621 bitmap bz = ptr->conflicts[z];
622 if (bz)
623 bitmap_set_bit (bz, x);
624 }
625
626 if (bx)
627 {
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;
632 }
633 else
634 {
635 /* If X has no conflicts, simply use Y's. */
636 ptr->conflicts[x] = by;
637 ptr->conflicts[y] = NULL;
638 }
639}
640
641
642/* Dump a conflicts graph. */
643
644static void
645ssa_conflicts_dump (FILE *file, ssa_conflicts *ptr)
646{
647 unsigned x;
648 bitmap b;
649
650 fprintf (file, "\nConflict graph:\n");
651
652 FOR_EACH_VEC_ELT (ptr->conflicts, x, b)
653 if (b)
654 {
655 fprintf (file, "%d: ", x);
656 dump_bitmap (file, b);
657 }
658}
659
660
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. */
672
673struct live_track
674{
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. */
679};
680
681
682/* This routine will create a new live track structure based on the partitions
683 in MAP. */
684
685static live_track *
686new_live_track (var_map map)
687{
688 live_track *ptr;
689 int lim, x;
690
691 /* Make sure there is a partition view in place. */
692 gcc_assert (map->partition_to_base_index != NULL);
693
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;
703}
704
705
706/* This routine will free the memory associated with PTR. */
707
708static void
709delete_live_track (live_track *ptr)
710{
711 bitmap_obstack_release (&ptr->obstack);
712 free (ptr->live_base_partitions);
713 free (ptr);
714}
715
716
717/* This function will remove PARTITION from the live list in PTR. */
718
719static inline void
720live_track_remove_partition (live_track *ptr, int partition)
721{
722 int root;
723
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);
729}
730
731
732/* This function will adds PARTITION to the live list in PTR. */
733
734static inline void
735live_track_add_partition (live_track *ptr, int partition)
736{
737 int root;
738
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);
745
746}
747
748
749/* Clear the live bit for VAR in PTR. */
750
751static inline void
752live_track_clear_var (live_track *ptr, tree var)
753{
754 int p;
755
756 p = var_to_partition (ptr->map, var);
757 if (p != NO_PARTITION)
758 live_track_remove_partition (ptr, p);
759}
760
761
762/* Return TRUE if VAR is live in PTR. */
763
764static inline bool
765live_track_live_p (live_track *ptr, tree var)
766{
767 int p, root;
768
769 p = var_to_partition (ptr->map, var);
770 if (p != NO_PARTITION)
771 {
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);
775 }
776 return false;
777}
778
779
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. */
782
783static inline void
784live_track_process_use (live_track *ptr, tree use)
785{
786 int p;
787
788 p = var_to_partition (ptr->map, use);
789 if (p == NO_PARTITION)
790 return;
791
792 /* Mark as live in the appropriate live list. */
793 live_track_add_partition (ptr, p);
794}
795
796
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. */
800
801static inline void
802live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph)
803{
804 int p, root;
805 bitmap b;
806 unsigned x;
807 bitmap_iterator bi;
808
809 p = var_to_partition (ptr->map, def);
810 if (p == NO_PARTITION)
811 return;
812
813 /* Clear the liveness bit. */
814 live_track_remove_partition (ptr, p);
815
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))
819 {
820 b = ptr->live_base_partitions[root];
821 EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
822 ssa_conflicts_add (graph, p, x);
823 }
824}
825
826
827/* Initialize PTR with the partitions set in INIT. */
828
829static inline void
830live_track_init (live_track *ptr, bitmap init)
831{
832 unsigned p;
833 bitmap_iterator bi;
834
835 /* Mark all live on exit partitions. */
836 EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
837 live_track_add_partition (ptr, p);
838}
839
840
841/* This routine will clear all live partitions in PTR. */
842
843static inline void
844live_track_clear_base_vars (live_track *ptr)
845{
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);
850}
851
852
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. */
857
858static ssa_conflicts *
859build_ssa_conflict_graph (tree_live_info_p liveinfo)
860{
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;
867
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;
876
877 map = live_var_map (liveinfo);
878 graph = ssa_conflicts_new (num_var_partitions (map));
879
880 live = new_live_track (map);
881
882 FOR_EACH_BB_FN (bb, cfun)
883 {
884 /* Start with live on exit temporaries. */
885 live_track_init (live, live_on_exit (liveinfo, bb));
886
887 for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
888 gsi_prev (&gsi))
889 {
890 tree var;
891 gimple *stmt = gsi_stmt (gsi);
892
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.
897
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))
901 {
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);
908 }
909 else if (is_gimple_debug (stmt))
910 continue;
911
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);
928
929 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
930 live_track_process_def (live, var, graph);
931
932 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
933 live_track_process_use (live, var);
934 }
935
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))
944 {
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);
949 }
950
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)
959 {
960 unsigned i;
961 tree var;
962
963 FOR_EACH_SSA_NAME (i, var, cfun)
964 {
965 if (!SSA_NAME_IS_DEFAULT_DEF (var)
966 || !SSA_NAME_VAR (var)
967 || VAR_P (SSA_NAME_VAR (var)))
968 continue;
969
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);
975 }
976 }
977
978 live_track_clear_base_vars (live);
979 }
980
981 delete_live_track (live);
982 return graph;
983}
984
985
986/* Shortcut routine to print messages to file F of the form:
987 "STR1 EXPR1 STR2 EXPR2 STR3." */
988
989static inline void
990print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
991 tree expr2, const char *str3)
992{
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);
998}
999
1000
1001/* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
1002
1003static inline void
1004fail_abnormal_edge_coalesce (int x, int y)
1005{
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);
1011
1012 internal_error ("SSA corruption");
1013}
1014
1015/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
1016 assign_parms may ask for a default partition. */
1017
1018static void
1019for_all_parms (void (*callback)(tree var, void *arg), void *arg)
1020{
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);
1028}
1029
1030/* Create a default def for VAR. */
1031
1032static void
1033create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
1034{
1035 if (!is_gimple_reg (var))
1036 return;
1037
1038 tree ssa = get_or_create_ssa_default_def (cfun, var);
1039 gcc_assert (ssa);
1040}
1041
1042/* Register VAR's default def in MAP. */
1043
1044static void
1045register_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
1046{
1047 if (!is_gimple_reg (var))
1048 return;
1049
1050 tree ssa = ssa_default_def (cfun, var);
1051 gcc_assert (ssa);
1052}
1053
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. */
1058
1059static void
1060coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
1061{
1062 if (SSA_NAME_IS_DEFAULT_DEF (var)
1063 || !SSA_NAME_VAR (var)
1064 || VAR_P (SSA_NAME_VAR (var)))
1065 return;
1066
1067 tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var));
1068 if (!has_zero_uses (ssa))
1069 return;
1070
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. */
1075}
1076
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. */
1079
1080static var_map
1081create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
1082{
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;
1091
1092 for_all_parms (create_default_def, NULL);
1093
1094 map = init_var_map (num_ssa_names);
1095
1096 for_all_parms (register_default_def, NULL);
1097
1098 FOR_EACH_BB_FN (bb, cfun)
1099 {
1100 tree arg;
1101
1102 for (gphi_iterator gpi = gsi_start_phis (bb);
1103 !gsi_end_p (gpi);
1104 gsi_next (&gpi))
1105 {
1106 gphi *phi = gpi.phi ();
1107 size_t i;
1108 int ver;
1109 tree res;
1110 bool saw_copy = false;
1111
1112 res = gimple_phi_result (phi);
1113 ver = SSA_NAME_VERSION (res);
1114
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++)
1118 {
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;
1123
1124 if (gimple_can_coalesce_p (arg, res)
1125 || (e->flags & EDGE_ABNORMAL))
1126 {
1127 saw_copy = true;
1128 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1129 if ((e->flags & EDGE_ABNORMAL) == 0)
1130 {
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);
1136 }
1137 }
1138 }
1139 if (saw_copy)
1140 bitmap_set_bit (used_in_copy, ver);
1141 }
1142
1143 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1144 {
1145 stmt = gsi_stmt (gsi);
1146
1147 if (is_gimple_debug (stmt))
1148 continue;
1149
1150 /* Check for copy coalesces. */
1151 switch (gimple_code (stmt))
1152 {
1153 case GIMPLE_ASSIGN:
1154 {
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))
1159 {
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);
1166 }
1167 }
1168 break;
1169
1170 case GIMPLE_RETURN:
1171 {
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))
1183 {
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);
1190 }
1191 break;
1192 }
1193
1194 case GIMPLE_ASM:
1195 {
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)
1204 {
1205 link = gimple_asm_output_op (asm_stmt, i);
1206 outputs[i] = TREE_VALUE (link);
1207 }
1208
1209 for (i = 0; i < ninputs; ++i)
1210 {
1211 const char *constraint;
1212 tree input;
1213 char *end;
1214 unsigned long match;
1215
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);
1220
1221 if (TREE_CODE (input) != SSA_NAME)
1222 continue;
1223
1224 match = strtoul (constraint, &end, 10);
1225 if (match >= noutputs || end == constraint)
1226 continue;
1227
1228 if (TREE_CODE (outputs[match]) != SSA_NAME)
1229 continue;
1230
1231 v1 = SSA_NAME_VERSION (outputs[match]);
1232 v2 = SSA_NAME_VERSION (input);
1233
1234 if (gimple_can_coalesce_p (outputs[match], input))
1235 {
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);
1241 }
1242 }
1243 break;
1244 }
1245
1246 default:
1247 break;
1248 }
1249 }
1250 }
1251
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)
1256 {
1257 if (!virtual_operand_p (var))
1258 {
1259 coalesce_with_default (var, cl, used_in_copy);
1260
1261 /* Add coalesces between all the result decls. */
1262 if (SSA_NAME_VAR (var)
1263 && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1264 {
1265 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1266 if (first == NULL_TREE)
1267 first = var;
1268 else
1269 {
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);
1275 }
1276 }
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));
1285 }
1286 }
1287
1288 return map;
1289}
1290
1291
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. */
1295
1296static inline bool
1297attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y,
1298 FILE *debug)
1299{
1300 int z;
1301 tree var1, var2;
1302 int p1, p2;
1303
1304 p1 = var_to_partition (map, ssa_name (x));
1305 p2 = var_to_partition (map, ssa_name (y));
1306
1307 if (debug)
1308 {
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);
1313 }
1314
1315 if (p1 == p2)
1316 {
1317 if (debug)
1318 fprintf (debug, ": Already Coalesced.\n");
1319 return true;
1320 }
1321
1322 if (debug)
1323 fprintf (debug, " [map: %d, %d] ", p1, p2);
1324
1325
1326 if (!ssa_conflicts_test_p (graph, p1, p2))
1327 {
1328 var1 = partition_to_var (map, p1);
1329 var2 = partition_to_var (map, p2);
1330
1331 z = var_union (map, var1, var2);
1332 if (z == NO_PARTITION)
1333 {
1334 if (debug)
1335 fprintf (debug, ": Unable to perform partition union.\n");
1336 return false;
1337 }
1338
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);
1345
1346 if (debug)
1347 fprintf (debug, ": Success -> %d\n", z);
1348
1349 return true;
1350 }
1351
1352 if (debug)
1353 fprintf (debug, ": Fail due to conflict\n");
1354
1355 return false;
1356}
1357
1358
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. */
1361
1362static void
1363coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
1364 FILE *debug)
1365{
1366 int x = 0, y = 0;
1367 tree var1, var2;
1368 int cost;
1369 basic_block bb;
1370 edge e;
1371 edge_iterator ei;
1372
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. */
1376
1377 FOR_EACH_BB_FN (bb, cfun)
1378 {
1379 FOR_EACH_EDGE (e, ei, bb->preds)
1380 if (e->flags & EDGE_ABNORMAL)
1381 {
1382 gphi_iterator gsi;
1383 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1384 gsi_next (&gsi))
1385 {
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;
1392
1393 tree res = PHI_RESULT (phi);
1394 int v1 = SSA_NAME_VERSION (res);
1395 int v2 = SSA_NAME_VERSION (arg);
1396
1397 if (debug)
1398 fprintf (debug, "Abnormal coalesce: ");
1399
1400 if (!attempt_coalesce (map, graph, v1, v2, debug))
1401 fail_abnormal_edge_coalesce (v1, v2);
1402 }
1403 }
1404 }
1405
1406 /* Now process the items in the coalesce list. */
1407
1408 while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1409 {
1410 var1 = ssa_name (x);
1411 var2 = ssa_name (y);
1412
1413 /* Assert the coalesces have the same base variable. */
1414 gcc_assert (gimple_can_coalesce_p (var1, var2));
1415
1416 if (debug)
1417 fprintf (debug, "Coalesce list: ");
1418 attempt_coalesce (map, graph, x, y, debug);
1419 }
1420}
1421
1422
1423/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1424
1425struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
1426{
1427 static inline hashval_t hash (const tree_node *);
1428 static inline int equal (const tree_node *, const tree_node *);
1429};
1430
1431inline hashval_t
1432ssa_name_var_hash::hash (const_tree n)
1433{
1434 return DECL_UID (SSA_NAME_VAR (n));
1435}
1436
1437inline int
1438ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
1439{
1440 return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
1441}
1442
1443
1444/* Output partition map MAP with coalescing plan PART to file F. */
1445
1446void
1447dump_part_var_map (FILE *f, partition part, var_map map)
1448{
1449 int t;
1450 unsigned x, y;
1451 int p;
1452
1453 fprintf (f, "\nCoalescible Partition map \n\n");
1454
1455 for (x = 0; x < map->num_partitions; x++)
1456 {
1457 if (map->view_to_partition != NULL)
1458 p = map->view_to_partition[x];
1459 else
1460 p = x;
1461
1462 if (ssa_name (p) == NULL_TREE
1463 || virtual_operand_p (ssa_name (p)))
1464 continue;
1465
1466 t = 0;
1467 for (y = 1; y < num_ssa_names; y++)
1468 {
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]);
1476
1477 if (p == (int)x)
1478 {
1479 if (t++ == 0)
1480 {
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, " - ");
1485 }
1486 fprintf (f, "%d ", y);
1487 }
1488 }
1489 if (t != 0)
1490 fprintf (f, ")\n");
1491 }
1492 fprintf (f, "\n");
1493}
1494
1495/* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
1496 coalescing together, false otherwise.
1497
1498 This must stay consistent with compute_samebase_partition_bases and
1499 compute_optimized_partition_bases. */
1500
1501bool
1502gimple_can_coalesce_p (tree name1, tree name2)
1503{
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;
1513
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)
1519 {
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;
1527
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;
1539
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);
1551 }
1552
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;
1561
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.
1565
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)
1569 {
1570 if (types_compatible_p (t1, t2))
1571 goto check_modes;
1572 }
1573 else
1574 {
1575 if (TYPE_CANONICAL (t1)
1576 && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)
1577 && types_compatible_p (t1, t2))
1578 goto check_modes;
1579 }
1580
1581 return false;
1582}
1583
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. */
1588
1589static void
1590compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1591 coalesce_list *cl)
1592{
1593 int parts = num_var_partitions (map);
1594 partition tentative = partition_new (parts);
1595
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)
1603 {
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));
1608
1609 if (p1 == p2)
1610 continue;
1611
1612 partition_union (tentative, p1, p2);
1613 }
1614
1615 /* We have to deal with cost one pairs too. */
1616 for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1617 {
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));
1622
1623 if (p1 == p2)
1624 continue;
1625
1626 partition_union (tentative, p1, p2);
1627 }
1628
1629 /* And also with abnormal edges. */
1630 basic_block bb;
1631 edge e;
1632 edge_iterator ei;
1633 FOR_EACH_BB_FN (bb, cfun)
1634 {
1635 FOR_EACH_EDGE (e, ei, bb->preds)
1636 if (e->flags & EDGE_ABNORMAL)
1637 {
1638 gphi_iterator gsi;
1639 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1640 gsi_next (&gsi))
1641 {
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;
1648
1649 tree res = PHI_RESULT (phi);
1650
1651 int p1 = partition_find (tentative, var_to_partition (map, res));
1652 int p2 = partition_find (tentative, var_to_partition (map, arg));
1653
1654 if (p1 == p2)
1655 continue;
1656
1657 partition_union (tentative, p1, p2);
1658 }
1659 }
1660 }
1661
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);
1666
1667 const unsigned no_part = -1;
1668 unsigned count = parts;
1669 while (count)
1670 index_map[--count] = no_part;
1671
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)
1680 {
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++;
1686 }
1687
1688 map->num_basevars = count;
1689
1690 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1691 {
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];
1696 }
1697
1698 if (dump_file && (dump_flags & TDF_DETAILS))
1699 dump_part_var_map (dump_file, tentative, map);
1700
1701 partition_delete (tentative);
1702}
1703
1704/* Hashtable helpers. */
1705
1706struct tree_int_map_hasher : nofree_ptr_hash <tree_int_map>
1707{
1708 static inline hashval_t hash (const tree_int_map *);
1709 static inline bool equal (const tree_int_map *, const tree_int_map *);
1710};
1711
1712inline hashval_t
1713tree_int_map_hasher::hash (const tree_int_map *v)
1714{
1715 return tree_map_base_hash (v);
1716}
1717
1718inline bool
1719tree_int_map_hasher::equal (const tree_int_map *v, const tree_int_map *c)
1720{
1721 return tree_int_map_eq (v, c);
1722}
1723
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. */
1728
1729static void
1730compute_samebase_partition_bases (var_map map)
1731{
1732 int x, num_part;
1733 tree var;
1734 struct tree_int_map *m, *mapstorage;
1735
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);
1742
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);
1746
1747 /* Build the base variable list, and point partitions at their bases. */
1748 for (x = 0; x < num_part; x++)
1749 {
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.
1763
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)
1771 {
1772 baseindex = m - mapstorage;
1773 m->to = baseindex;
1774 *slot = m;
1775 m++;
1776 }
1777 else
1778 baseindex = (*slot)->to;
1779 map->partition_to_base_index[x] = baseindex;
1780 }
1781
1782 map->num_basevars = m - mapstorage;
1783
1784 free (mapstorage);
1785}
1786
1787/* Reduce the number of copies by coalescing variables in the function. Return
1788 a partition map with the resulting coalesces. */
1789
1790extern var_map
1791coalesce_ssa_name (void)
1792{
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;
1800
1801 cl = create_coalesce_list ();
1802 map = create_outofssa_var_map (cl, used_in_copies);
1803
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)
1808 {
1809 hash_table<ssa_name_var_hash> ssa_name_hash (10);
1810
1811 FOR_EACH_SSA_NAME (i, a, cfun)
1812 {
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))))
1817 {
1818 tree *slot = ssa_name_hash.find_slot (a, INSERT);
1819
1820 if (!*slot)
1821 *slot = a;
1822 else
1823 {
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));
1839 }
1840 }
1841 }
1842 }
1843 if (dump_file && (dump_flags & TDF_DETAILS))
1844 dump_var_map (dump_file, map);
1845
1846 partition_view_bitmap (map, used_in_copies);
1847
1848 if (flag_tree_coalesce_vars)
1849 compute_optimized_partition_bases (map, used_in_copies, cl);
1850 else
1851 compute_samebase_partition_bases (map);
1852
1853 if (num_var_partitions (map) < 1)
1854 {
1855 delete_coalesce_list (cl);
1856 return map;
1857 }
1858
1859 if (dump_file && (dump_flags & TDF_DETAILS))
1860 dump_var_map (dump_file, map);
1861
1862 liveinfo = calculate_live_ranges (map, false);
1863
1864 if (dump_file && (dump_flags & TDF_DETAILS))
1865 dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1866
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);
1872
1873 sort_coalesce_list (cl, graph, map);
1874
1875 if (dump_file && (dump_flags & TDF_DETAILS))
1876 {
1877 fprintf (dump_file, "\nAfter sorting:\n");
1878 dump_coalesce_list (dump_file, cl);
1879 }
1880
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. */
1883
1884 if (dump_file && (dump_flags & TDF_DETAILS))
1885 dump_var_map (dump_file, map);
1886
1887 /* Now coalesce everything in the list. */
1888 coalesce_partitions (map, graph, cl,
1889 ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1890
1891 delete_coalesce_list (cl);
1892 ssa_conflicts_delete (graph);
1893
1894 return map;
1895}
1896
1897/* We need to pass two arguments to set_parm_default_def_partition,
1898 but for_all_parms only supports one. Use a pair. */
1899
1900typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
1901
1902/* Set in ARG's PARTS bitmap the bit corresponding to the partition in
1903 ARG's MAP containing VAR's default def. */
1904
1905static void
1906set_parm_default_def_partition (tree var, void *arg_)
1907{
1908 parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
1909 var_map map = arg->first;
1910 bitmap parts = arg->second;
1911
1912 if (!is_gimple_reg (var))
1913 return;
1914
1915 tree ssa = ssa_default_def (cfun, var);
1916 gcc_assert (ssa);
1917
1918 int version = var_to_partition (map, ssa);
1919 gcc_assert (version != NO_PARTITION);
1920
1921 bool changed = bitmap_set_bit (parts, version);
1922 gcc_assert (changed);
1923}
1924
1925/* Allocate and return a bitmap that has a bit set for each partition
1926 that contains a default def for a parameter. */
1927
1928bitmap
1929get_parm_default_def_partitions (var_map map)
1930{
1931 bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
1932
1933 parm_default_def_partition_arg
1934 arg = std::make_pair (map, parm_default_def_parts);
1935
1936 for_all_parms (set_parm_default_def_partition, &arg);
1937
1938 return parm_default_def_parts;
1939}
1940
1941/* Allocate and return a bitmap that has a bit set for each partition
1942 that contains an undefined value. */
1943
1944bitmap
1945get_undefined_value_partitions (var_map map)
1946{
1947 bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
1948
1949 for (unsigned int i = 1; i < num_ssa_names; i++)
1950 {
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))
1956 {
1957 const int p = var_to_partition (map, var);
1958 if (p != NO_PARTITION)
1959 bitmap_set_bit (undefined_value_parts, p);
1960 }
1961 }
1962
1963 return undefined_value_parts;
1964}
1965