1 /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 Copyright (C) 2004-2018 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>. */
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
50 struct 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
77 struct 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. */
87 static ssa_conflicts *conflicts_;
88 static var_map map_;
89
90 /* Coalesce pair hashtable helpers. */
91
92 struct 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
100 inline hashval_t
hash(const coalesce_pair * pair)101 coalesce_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
112 inline bool
equal(const coalesce_pair * p1,const coalesce_pair * p2)113 coalesce_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
119 typedef hash_table<coalesce_pair_hasher> coalesce_table_type;
120 typedef coalesce_table_type::iterator coalesce_iterator_type;
121
122
123 struct 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
132 struct 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
146 static inline int
coalesce_cost(int frequency,bool optimize_for_size)147 coalesce_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
164 static inline int
coalesce_cost_bb(basic_block bb)165 coalesce_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
174 static inline int
coalesce_cost_edge(edge e)175 coalesce_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
216 static inline int
pop_cost_one_pair(coalesce_list * cl,int * p1,int * p2)217 pop_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
238 static inline int
pop_best_coalesce(coalesce_list * cl,int * p1,int * p2)239 pop_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
262 static inline coalesce_list *
create_coalesce_list(void)263 create_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
282 static inline void
delete_coalesce_list(coalesce_list * cl)283 delete_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
295 static inline int
num_coalesce_pairs(coalesce_list * cl)296 num_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
305 static coalesce_pair *
find_coalesce_pair(coalesce_list * cl,int p1,int p2,bool create)306 find_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
344 static inline void
add_cost_one_coalesce(coalesce_list * cl,int p1,int p2)345 add_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
359 static inline void
add_coalesce(coalesce_list * cl,int p1,int p2,int value)360 add_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
385 static void
initialize_conflict_count(coalesce_pair * p,ssa_conflicts * conflicts,var_map map)386 initialize_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
410 static int
compare_pairs(const void * p1,const void * p2)411 compare_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
453 static void
sort_coalesce_list(coalesce_list * cl,ssa_conflicts * conflicts,var_map map)454 sort_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
493 static void
dump_coalesce_list(FILE * f,coalesce_list * cl)494 dump_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
536 static inline ssa_conflicts *
ssa_conflicts_new(unsigned size)537 ssa_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
551 static inline void
ssa_conflicts_delete(ssa_conflicts * ptr)552 ssa_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
562 static inline bool
ssa_conflicts_test_p(ssa_conflicts * ptr,unsigned x,unsigned y)563 ssa_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
580 static inline void
ssa_conflicts_add_one(ssa_conflicts * ptr,unsigned x,unsigned y)581 ssa_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
593 static inline void
ssa_conflicts_add(ssa_conflicts * ptr,unsigned x,unsigned y)594 ssa_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
604 static inline void
ssa_conflicts_merge(ssa_conflicts * ptr,unsigned x,unsigned y)605 ssa_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
644 static void
ssa_conflicts_dump(FILE * file,ssa_conflicts * ptr)645 ssa_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
673 struct 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
685 static live_track *
new_live_track(var_map map)686 new_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
708 static void
delete_live_track(live_track * ptr)709 delete_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
719 static inline void
live_track_remove_partition(live_track * ptr,int partition)720 live_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
734 static inline void
live_track_add_partition(live_track * ptr,int partition)735 live_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
751 static inline void
live_track_clear_var(live_track * ptr,tree var)752 live_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
764 static inline bool
live_track_live_p(live_track * ptr,tree var)765 live_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
783 static inline void
live_track_process_use(live_track * ptr,tree use)784 live_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
801 static inline void
live_track_process_def(live_track * ptr,tree def,ssa_conflicts * graph)802 live_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
829 static inline void
live_track_init(live_track * ptr,bitmap init)830 live_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
843 static inline void
live_track_clear_base_vars(live_track * ptr)844 live_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
858 static ssa_conflicts *
build_ssa_conflict_graph(tree_live_info_p liveinfo)859 build_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
989 static inline void
print_exprs(FILE * f,const char * str1,tree expr1,const char * str2,tree expr2,const char * str3)990 print_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
1003 static inline void
fail_abnormal_edge_coalesce(int x,int y)1004 fail_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
1018 static void
for_all_parms(void (* callback)(tree var,void * arg),void * arg)1019 for_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
1032 static void
create_default_def(tree var,void * arg ATTRIBUTE_UNUSED)1033 create_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
1044 static void
register_default_def(tree var,void * arg ATTRIBUTE_UNUSED)1045 register_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
1059 static void
coalesce_with_default(tree var,coalesce_list * cl,bitmap used_in_copy)1060 coalesce_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
1080 static var_map
create_outofssa_var_map(coalesce_list * cl,bitmap used_in_copy)1081 create_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
1296 static inline bool
attempt_coalesce(var_map map,ssa_conflicts * graph,int x,int y,FILE * debug)1297 attempt_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
1362 static void
coalesce_partitions(var_map map,ssa_conflicts * graph,coalesce_list * cl,FILE * debug)1363 coalesce_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
1425 struct 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
1431 inline hashval_t
hash(const_tree n)1432 ssa_name_var_hash::hash (const_tree n)
1433 {
1434 return DECL_UID (SSA_NAME_VAR (n));
1435 }
1436
1437 inline int
equal(const tree_node * n1,const tree_node * n2)1438 ssa_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
1446 void
dump_part_var_map(FILE * f,partition part,var_map map)1447 dump_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
1501 bool
gimple_can_coalesce_p(tree name1,tree name2)1502 gimple_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 if (types_compatible_p (t1, t2))
1566 goto check_modes;
1567
1568 return false;
1569 }
1570
1571 /* Fill in MAP's partition_to_base_index, with one index for each
1572 partition of SSA names USED_IN_COPIES and related by CL coalesce
1573 possibilities. This must match gimple_can_coalesce_p in the
1574 optimized case. */
1575
1576 static void
compute_optimized_partition_bases(var_map map,bitmap used_in_copies,coalesce_list * cl)1577 compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1578 coalesce_list *cl)
1579 {
1580 int parts = num_var_partitions (map);
1581 partition tentative = partition_new (parts);
1582
1583 /* Partition the SSA versions so that, for each coalescible
1584 pair, both of its members are in the same partition in
1585 TENTATIVE. */
1586 gcc_assert (!cl->sorted);
1587 coalesce_pair *node;
1588 coalesce_iterator_type ppi;
1589 FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1590 {
1591 tree v1 = ssa_name (node->first_element);
1592 int p1 = partition_find (tentative, var_to_partition (map, v1));
1593 tree v2 = ssa_name (node->second_element);
1594 int p2 = partition_find (tentative, var_to_partition (map, v2));
1595
1596 if (p1 == p2)
1597 continue;
1598
1599 partition_union (tentative, p1, p2);
1600 }
1601
1602 /* We have to deal with cost one pairs too. */
1603 for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1604 {
1605 tree v1 = ssa_name (co->first_element);
1606 int p1 = partition_find (tentative, var_to_partition (map, v1));
1607 tree v2 = ssa_name (co->second_element);
1608 int p2 = partition_find (tentative, var_to_partition (map, v2));
1609
1610 if (p1 == p2)
1611 continue;
1612
1613 partition_union (tentative, p1, p2);
1614 }
1615
1616 /* And also with abnormal edges. */
1617 basic_block bb;
1618 edge e;
1619 edge_iterator ei;
1620 FOR_EACH_BB_FN (bb, cfun)
1621 {
1622 FOR_EACH_EDGE (e, ei, bb->preds)
1623 if (e->flags & EDGE_ABNORMAL)
1624 {
1625 gphi_iterator gsi;
1626 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1627 gsi_next (&gsi))
1628 {
1629 gphi *phi = gsi.phi ();
1630 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1631 if (SSA_NAME_IS_DEFAULT_DEF (arg)
1632 && (!SSA_NAME_VAR (arg)
1633 || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1634 continue;
1635
1636 tree res = PHI_RESULT (phi);
1637
1638 int p1 = partition_find (tentative, var_to_partition (map, res));
1639 int p2 = partition_find (tentative, var_to_partition (map, arg));
1640
1641 if (p1 == p2)
1642 continue;
1643
1644 partition_union (tentative, p1, p2);
1645 }
1646 }
1647 }
1648
1649 map->partition_to_base_index = XCNEWVEC (int, parts);
1650 auto_vec<unsigned int> index_map (parts);
1651 if (parts)
1652 index_map.quick_grow (parts);
1653
1654 const unsigned no_part = -1;
1655 unsigned count = parts;
1656 while (count)
1657 index_map[--count] = no_part;
1658
1659 /* Initialize MAP's mapping from partition to base index, using
1660 as base indices an enumeration of the TENTATIVE partitions in
1661 which each SSA version ended up, so that we compute conflicts
1662 between all SSA versions that ended up in the same potential
1663 coalesce partition. */
1664 bitmap_iterator bi;
1665 unsigned i;
1666 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1667 {
1668 int pidx = var_to_partition (map, ssa_name (i));
1669 int base = partition_find (tentative, pidx);
1670 if (index_map[base] != no_part)
1671 continue;
1672 index_map[base] = count++;
1673 }
1674
1675 map->num_basevars = count;
1676
1677 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1678 {
1679 int pidx = var_to_partition (map, ssa_name (i));
1680 int base = partition_find (tentative, pidx);
1681 gcc_assert (index_map[base] < count);
1682 map->partition_to_base_index[pidx] = index_map[base];
1683 }
1684
1685 if (dump_file && (dump_flags & TDF_DETAILS))
1686 dump_part_var_map (dump_file, tentative, map);
1687
1688 partition_delete (tentative);
1689 }
1690
1691 /* Reduce the number of copies by coalescing variables in the function. Return
1692 a partition map with the resulting coalesces. */
1693
1694 extern var_map
coalesce_ssa_name(void)1695 coalesce_ssa_name (void)
1696 {
1697 tree_live_info_p liveinfo;
1698 ssa_conflicts *graph;
1699 coalesce_list *cl;
1700 auto_bitmap used_in_copies;
1701 var_map map;
1702 unsigned int i;
1703 tree a;
1704
1705 cl = create_coalesce_list ();
1706 map = create_outofssa_var_map (cl, used_in_copies);
1707
1708 /* If this optimization is disabled, we need to coalesce all the
1709 names originating from the same SSA_NAME_VAR so debug info
1710 remains undisturbed. */
1711 if (!flag_tree_coalesce_vars)
1712 {
1713 hash_table<ssa_name_var_hash> ssa_name_hash (10);
1714
1715 FOR_EACH_SSA_NAME (i, a, cfun)
1716 {
1717 if (SSA_NAME_VAR (a)
1718 && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1719 && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
1720 || !VAR_P (SSA_NAME_VAR (a))))
1721 {
1722 tree *slot = ssa_name_hash.find_slot (a, INSERT);
1723
1724 if (!*slot)
1725 *slot = a;
1726 else
1727 {
1728 /* If the variable is a PARM_DECL or a RESULT_DECL, we
1729 _require_ that all the names originating from it be
1730 coalesced, because there must be a single partition
1731 containing all the names so that it can be assigned
1732 the canonical RTL location of the DECL safely.
1733 If in_lto_p, a function could have been compiled
1734 originally with optimizations and only the link
1735 performed at -O0, so we can't actually require it. */
1736 const int cost
1737 = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p)
1738 ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
1739 add_coalesce (cl, SSA_NAME_VERSION (a),
1740 SSA_NAME_VERSION (*slot), cost);
1741 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a));
1742 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot));
1743 }
1744 }
1745 }
1746 }
1747 if (dump_file && (dump_flags & TDF_DETAILS))
1748 dump_var_map (dump_file, map);
1749
1750 partition_view_bitmap (map, used_in_copies);
1751
1752 compute_optimized_partition_bases (map, used_in_copies, cl);
1753
1754 if (num_var_partitions (map) < 1)
1755 {
1756 delete_coalesce_list (cl);
1757 return map;
1758 }
1759
1760 if (dump_file && (dump_flags & TDF_DETAILS))
1761 dump_var_map (dump_file, map);
1762
1763 liveinfo = calculate_live_ranges (map, false);
1764
1765 if (dump_file && (dump_flags & TDF_DETAILS))
1766 dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1767
1768 /* Build a conflict graph. */
1769 graph = build_ssa_conflict_graph (liveinfo);
1770 delete_tree_live_info (liveinfo);
1771 if (dump_file && (dump_flags & TDF_DETAILS))
1772 ssa_conflicts_dump (dump_file, graph);
1773
1774 sort_coalesce_list (cl, graph, map);
1775
1776 if (dump_file && (dump_flags & TDF_DETAILS))
1777 {
1778 fprintf (dump_file, "\nAfter sorting:\n");
1779 dump_coalesce_list (dump_file, cl);
1780 }
1781
1782 /* First, coalesce all live on entry variables to their base variable.
1783 This will ensure the first use is coming from the correct location. */
1784
1785 if (dump_file && (dump_flags & TDF_DETAILS))
1786 dump_var_map (dump_file, map);
1787
1788 /* Now coalesce everything in the list. */
1789 coalesce_partitions (map, graph, cl,
1790 ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1791
1792 delete_coalesce_list (cl);
1793 ssa_conflicts_delete (graph);
1794
1795 return map;
1796 }
1797
1798 /* We need to pass two arguments to set_parm_default_def_partition,
1799 but for_all_parms only supports one. Use a pair. */
1800
1801 typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
1802
1803 /* Set in ARG's PARTS bitmap the bit corresponding to the partition in
1804 ARG's MAP containing VAR's default def. */
1805
1806 static void
set_parm_default_def_partition(tree var,void * arg_)1807 set_parm_default_def_partition (tree var, void *arg_)
1808 {
1809 parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
1810 var_map map = arg->first;
1811 bitmap parts = arg->second;
1812
1813 if (!is_gimple_reg (var))
1814 return;
1815
1816 tree ssa = ssa_default_def (cfun, var);
1817 gcc_assert (ssa);
1818
1819 int version = var_to_partition (map, ssa);
1820 gcc_assert (version != NO_PARTITION);
1821
1822 bool changed = bitmap_set_bit (parts, version);
1823 gcc_assert (changed);
1824 }
1825
1826 /* Allocate and return a bitmap that has a bit set for each partition
1827 that contains a default def for a parameter. */
1828
1829 bitmap
get_parm_default_def_partitions(var_map map)1830 get_parm_default_def_partitions (var_map map)
1831 {
1832 bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
1833
1834 parm_default_def_partition_arg
1835 arg = std::make_pair (map, parm_default_def_parts);
1836
1837 for_all_parms (set_parm_default_def_partition, &arg);
1838
1839 return parm_default_def_parts;
1840 }
1841
1842 /* Allocate and return a bitmap that has a bit set for each partition
1843 that contains an undefined value. */
1844
1845 bitmap
get_undefined_value_partitions(var_map map)1846 get_undefined_value_partitions (var_map map)
1847 {
1848 bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
1849
1850 for (unsigned int i = 1; i < num_ssa_names; i++)
1851 {
1852 tree var = ssa_name (i);
1853 if (var
1854 && !virtual_operand_p (var)
1855 && !has_zero_uses (var)
1856 && ssa_undefined_value_p (var))
1857 {
1858 const int p = var_to_partition (map, var);
1859 if (p != NO_PARTITION)
1860 bitmap_set_bit (undefined_value_parts, p);
1861 }
1862 }
1863
1864 return undefined_value_parts;
1865 }
1866