Line data Source code
1 : /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 : Copyright (C) 2004-2026 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 : #include "gimple-lower-bitint.h"
42 :
43 : /* This set of routines implements a coalesce_list. This is an object which
44 : is used to track pairs of ssa_names which are desirable to coalesce
45 : together to avoid copies. Costs are associated with each pair, and when
46 : all desired information has been collected, the object can be used to
47 : order the pairs for processing. */
48 :
49 : /* This structure defines a pair entry. */
50 :
51 : struct coalesce_pair
52 : {
53 : int first_element;
54 : int second_element;
55 : int cost;
56 :
57 : /* A count of the number of unique partitions this pair would conflict
58 : with if coalescing was successful. This is the secondary sort key,
59 : given two pairs with equal costs, we will prefer the pair with a smaller
60 : conflict set.
61 :
62 : This is lazily initialized when we discover two coalescing pairs have
63 : the same primary cost.
64 :
65 : Note this is not updated and propagated as pairs are coalesced. */
66 : int conflict_count;
67 :
68 : /* The order in which coalescing pairs are discovered is recorded in this
69 : field, which is used as the final tie breaker when sorting coalesce
70 : pairs. */
71 : int index;
72 : };
73 :
74 : /* This represents a conflict graph. Implemented as an array of bitmaps.
75 : A full matrix is used for conflicts rather than just upper triangular form.
76 : this makes it much simpler and faster to perform conflict merges. */
77 :
78 : struct ssa_conflicts
79 : {
80 : bitmap_obstack obstack; /* A place to allocate our bitmaps. */
81 : vec<bitmap> conflicts;
82 : };
83 :
84 : /* The narrow API of the qsort comparison function doesn't allow easy
85 : access to additional arguments. So we have two globals (ick) to hold
86 : the data we need. They're initialized before the call to qsort and
87 : wiped immediately after. */
88 : static ssa_conflicts *conflicts_;
89 : static var_map map_;
90 :
91 : /* Coalesce pair hashtable helpers. */
92 :
93 : struct coalesce_pair_hasher : nofree_ptr_hash <coalesce_pair>
94 : {
95 : static inline hashval_t hash (const coalesce_pair *);
96 : static inline bool equal (const coalesce_pair *, const coalesce_pair *);
97 : };
98 :
99 : /* Hash function for coalesce list. Calculate hash for PAIR. */
100 :
101 : inline hashval_t
102 8765797 : coalesce_pair_hasher::hash (const coalesce_pair *pair)
103 : {
104 8765797 : hashval_t a = (hashval_t)(pair->first_element);
105 8765797 : hashval_t b = (hashval_t)(pair->second_element);
106 :
107 2083388 : return b * (b - 1) / 2 + a;
108 : }
109 :
110 : /* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2,
111 : returning TRUE if the two pairs are equivalent. */
112 :
113 : inline bool
114 2863707 : coalesce_pair_hasher::equal (const coalesce_pair *p1, const coalesce_pair *p2)
115 : {
116 2863707 : return (p1->first_element == p2->first_element
117 2863707 : && p1->second_element == p2->second_element);
118 : }
119 :
120 : typedef hash_table<coalesce_pair_hasher> coalesce_table_type;
121 : typedef coalesce_table_type::iterator coalesce_iterator_type;
122 :
123 :
124 : struct cost_one_pair
125 : {
126 : int first_element;
127 : int second_element;
128 : cost_one_pair *next;
129 : };
130 :
131 : /* This structure maintains the list of coalesce pairs. */
132 :
133 : struct coalesce_list
134 : {
135 : coalesce_table_type *list; /* Hash table. */
136 : coalesce_pair **sorted; /* List when sorted. */
137 : int num_sorted; /* Number in the sorted list. */
138 : cost_one_pair *cost_one_list;/* Single use coalesces with cost 1. */
139 : obstack ob;
140 : };
141 :
142 : #define NO_BEST_COALESCE -1
143 : #define MUST_COALESCE_COST INT_MAX
144 :
145 :
146 : /* Return cost of execution of copy instruction with FREQUENCY. */
147 :
148 : static inline int
149 6391114 : coalesce_cost (int frequency, bool optimize_for_size)
150 : {
151 : /* Base costs on BB frequencies bounded by 1. */
152 6391114 : int cost = frequency;
153 :
154 6391114 : if (!cost)
155 567176 : cost = 1;
156 :
157 6386653 : if (optimize_for_size)
158 797953 : cost = 1;
159 :
160 6391114 : return cost;
161 : }
162 :
163 :
164 : /* Return the cost of executing a copy instruction in basic block BB. */
165 :
166 : static inline int
167 744735 : coalesce_cost_bb (basic_block bb)
168 : {
169 744735 : return coalesce_cost (bb->count.to_frequency (cfun),
170 744735 : optimize_bb_for_size_p (bb));
171 : }
172 :
173 :
174 : /* Return the cost of executing a copy instruction on edge E. */
175 :
176 : static inline int
177 5641918 : coalesce_cost_edge (edge e)
178 : {
179 5641918 : int mult = 1;
180 :
181 : /* Inserting copy on critical edge costs more than inserting it elsewhere. */
182 5641918 : if (EDGE_CRITICAL_P (e))
183 : mult = 2;
184 5641918 : if (e->flags & EDGE_ABNORMAL)
185 : return MUST_COALESCE_COST;
186 5641918 : if (e->flags & EDGE_EH)
187 : {
188 39626 : edge e2;
189 39626 : edge_iterator ei;
190 118865 : FOR_EACH_EDGE (e2, ei, e->dest->preds)
191 114658 : if (e2 != e)
192 : {
193 : /* Putting code on EH edge that leads to BB
194 : with multiple predecestors imply splitting of
195 : edge too. */
196 105265 : if (mult < 2)
197 105265 : mult = 2;
198 : /* If there are multiple EH predecestors, we
199 : also copy EH regions and produce separate
200 : landing pad. This is expensive. */
201 105265 : if (e2->flags & EDGE_EH)
202 : {
203 : mult = 5;
204 : break;
205 : }
206 : }
207 : }
208 :
209 5641918 : return coalesce_cost (EDGE_FREQUENCY (e),
210 11283836 : optimize_edge_for_size_p (e)) * mult;
211 : }
212 :
213 :
214 : /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
215 : 2 elements via P1 and P2. 1 is returned by the function if there is a pair,
216 : NO_BEST_COALESCE is returned if there aren't any. */
217 :
218 : static inline int
219 1566868 : pop_cost_one_pair (coalesce_list *cl, int *p1, int *p2)
220 : {
221 1566868 : cost_one_pair *ptr;
222 :
223 1566868 : ptr = cl->cost_one_list;
224 1566868 : if (!ptr)
225 : return NO_BEST_COALESCE;
226 :
227 273004 : *p1 = ptr->first_element;
228 273004 : *p2 = ptr->second_element;
229 273004 : cl->cost_one_list = ptr->next;
230 :
231 273004 : 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
239 7615362 : pop_best_coalesce (coalesce_list *cl, int *p1, int *p2)
240 : {
241 7615362 : coalesce_pair *node;
242 7615362 : int ret;
243 :
244 7615362 : if (cl->sorted == NULL)
245 596135 : return pop_cost_one_pair (cl, p1, p2);
246 :
247 7019227 : if (cl->num_sorted == 0)
248 970733 : return pop_cost_one_pair (cl, p1, p2);
249 :
250 6048494 : node = cl->sorted[--(cl->num_sorted)];
251 6048494 : *p1 = node->first_element;
252 6048494 : *p2 = node->second_element;
253 6048494 : ret = node->cost;
254 :
255 6048494 : return ret;
256 : }
257 :
258 :
259 : /* Create a new empty coalesce list object and return it. */
260 :
261 : static inline coalesce_list *
262 1477646 : create_coalesce_list (void)
263 : {
264 1477646 : coalesce_list *list;
265 1477646 : unsigned size = num_ssa_names * 3;
266 :
267 1477646 : if (size < 40)
268 1477646 : size = 40;
269 :
270 1477646 : list = (coalesce_list *) xmalloc (sizeof (struct coalesce_list));
271 1477646 : list->list = new coalesce_table_type (size);
272 1477646 : list->sorted = NULL;
273 1477646 : list->num_sorted = 0;
274 1477646 : list->cost_one_list = NULL;
275 1477646 : gcc_obstack_init (&list->ob);
276 1477646 : return list;
277 : }
278 :
279 :
280 : /* Delete coalesce list CL. */
281 :
282 : static inline void
283 1477646 : delete_coalesce_list (coalesce_list *cl)
284 : {
285 1477646 : gcc_assert (cl->cost_one_list == NULL);
286 1477646 : delete cl->list;
287 1477646 : cl->list = NULL;
288 1477646 : free (cl->sorted);
289 1477646 : gcc_assert (cl->num_sorted == 0);
290 1477646 : obstack_free (&cl->ob, NULL);
291 1477646 : free (cl);
292 1477646 : }
293 :
294 : /* Return the number of unique coalesce pairs in CL. */
295 :
296 : static inline int
297 7342358 : num_coalesce_pairs (coalesce_list *cl)
298 : {
299 7342358 : return cl->list->elements ();
300 : }
301 :
302 : /* Find a matching coalesce pair object in CL for the pair P1 and P2. If
303 : one isn't found, return NULL if CREATE is false, otherwise create a new
304 : coalesce pair object and return it. */
305 :
306 : static coalesce_pair *
307 6682409 : find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
308 : {
309 6682409 : struct coalesce_pair p;
310 6682409 : coalesce_pair **slot;
311 6682409 : unsigned int hash;
312 :
313 : /* Normalize so that p1 is the smaller value. */
314 6682409 : if (p2 < p1)
315 : {
316 3887510 : p.first_element = p2;
317 3887510 : p.second_element = p1;
318 : }
319 : else
320 : {
321 2794899 : p.first_element = p1;
322 2794899 : p.second_element = p2;
323 : }
324 :
325 6682409 : hash = coalesce_pair_hasher::hash (&p);
326 6682409 : slot = cl->list->find_slot_with_hash (&p, hash, create ? INSERT : NO_INSERT);
327 6682409 : if (!slot)
328 : return NULL;
329 :
330 6682409 : if (!*slot)
331 : {
332 6048494 : struct coalesce_pair * pair = XOBNEW (&cl->ob, struct coalesce_pair);
333 6048494 : gcc_assert (cl->sorted == NULL);
334 6048494 : pair->first_element = p.first_element;
335 6048494 : pair->second_element = p.second_element;
336 6048494 : pair->cost = 0;
337 6048494 : pair->index = num_coalesce_pairs (cl);
338 6048494 : pair->conflict_count = 0;
339 6048494 : *slot = pair;
340 : }
341 :
342 6682409 : return (struct coalesce_pair *) *slot;
343 : }
344 :
345 : static inline void
346 273004 : add_cost_one_coalesce (coalesce_list *cl, int p1, int p2)
347 : {
348 273004 : cost_one_pair *pair;
349 :
350 273004 : pair = XOBNEW (&cl->ob, cost_one_pair);
351 273004 : pair->first_element = p1;
352 273004 : pair->second_element = p2;
353 273004 : pair->next = cl->cost_one_list;
354 273004 : cl->cost_one_list = pair;
355 273004 : }
356 :
357 :
358 : /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
359 :
360 : static inline void
361 6691573 : add_coalesce (coalesce_list *cl, int p1, int p2, int value)
362 : {
363 6691573 : coalesce_pair *node;
364 :
365 6691573 : gcc_assert (cl->sorted == NULL);
366 6691573 : if (p1 == p2)
367 : return;
368 :
369 6682409 : node = find_coalesce_pair (cl, p1, p2, true);
370 :
371 : /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
372 6682409 : if (node->cost < MUST_COALESCE_COST - 1)
373 : {
374 6682409 : if (value < MUST_COALESCE_COST - 1)
375 6109717 : node->cost += value;
376 : else
377 572692 : node->cost = value;
378 : }
379 : }
380 :
381 : /* Compute and record how many unique conflicts would exist for the
382 : representative partition for each coalesce pair in CL.
383 :
384 : CONFLICTS is the conflict graph and MAP is the current partition view. */
385 :
386 : static void
387 58247274 : initialize_conflict_count (coalesce_pair *p,
388 : ssa_conflicts *conflicts,
389 : var_map map)
390 : {
391 58247274 : int p1 = var_to_partition (map, ssa_name (p->first_element));
392 58247274 : int p2 = var_to_partition (map, ssa_name (p->second_element));
393 :
394 : /* 4 cases. If both P1 and P2 have conflicts, then build their
395 : union and count the members. Else handle the degenerate cases
396 : in the obvious ways. */
397 58247274 : if (conflicts->conflicts[p1] && conflicts->conflicts[p2])
398 797688 : p->conflict_count = bitmap_count_unique_bits (conflicts->conflicts[p1],
399 797688 : conflicts->conflicts[p2]);
400 57449586 : else if (conflicts->conflicts[p1])
401 137378 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p1]);
402 57312208 : else if (conflicts->conflicts[p2])
403 143562 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p2]);
404 : else
405 57168646 : p->conflict_count = 0;
406 58247274 : }
407 :
408 :
409 : /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
410 :
411 : static int
412 172712717 : compare_pairs (const void *p1, const void *p2)
413 : {
414 172712717 : coalesce_pair *const *const pp1 = (coalesce_pair *const *) p1;
415 172712717 : coalesce_pair *const *const pp2 = (coalesce_pair *const *) p2;
416 172712717 : int result;
417 :
418 172712717 : result = (* pp1)->cost - (* pp2)->cost;
419 : /* We use the size of the resulting conflict set as the secondary sort key.
420 : Given two equal costing coalesce pairs, we want to prefer the pair that
421 : has the smaller conflict set. */
422 172712717 : if (result == 0)
423 : {
424 73369310 : if (flag_expensive_optimizations)
425 : {
426 : /* Lazily initialize the conflict counts as it's fairly expensive
427 : to compute. */
428 40461503 : if ((*pp2)->conflict_count == 0)
429 29295162 : initialize_conflict_count (*pp2, conflicts_, map_);
430 40461503 : if ((*pp1)->conflict_count == 0)
431 28952112 : initialize_conflict_count (*pp1, conflicts_, map_);
432 :
433 40461503 : result = (*pp2)->conflict_count - (*pp1)->conflict_count;
434 : }
435 :
436 : /* And if everything else is equal, then sort based on which
437 : coalesce pair was found first. */
438 73369310 : if (result == 0)
439 63567204 : result = (*pp2)->index - (*pp1)->index;
440 : }
441 :
442 172712717 : return result;
443 : }
444 :
445 : /* Iterate over CL using ITER, returning values in PAIR. */
446 :
447 : #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
448 : FOR_EACH_HASH_TABLE_ELEMENT (*(CL)->list, (PAIR), coalesce_pair_p, (ITER))
449 :
450 :
451 : /* Prepare CL for removal of preferred pairs. When finished they are sorted
452 : in order from most important coalesce to least important. */
453 :
454 : static void
455 1293864 : sort_coalesce_list (coalesce_list *cl, ssa_conflicts *conflicts, var_map map)
456 : {
457 1293864 : unsigned x, num;
458 1293864 : coalesce_pair *p;
459 1293864 : coalesce_iterator_type ppi;
460 :
461 1293864 : gcc_assert (cl->sorted == NULL);
462 :
463 1293864 : num = num_coalesce_pairs (cl);
464 1293864 : cl->num_sorted = num;
465 1293864 : if (num == 0)
466 914055 : return;
467 :
468 : /* Allocate a vector for the pair pointers. */
469 703514 : cl->sorted = XNEWVEC (coalesce_pair *, num);
470 :
471 : /* Populate the vector with pointers to the pairs. */
472 703514 : x = 0;
473 6752008 : FOR_EACH_PARTITION_PAIR (p, ppi, cl)
474 6048494 : cl->sorted[x++] = p;
475 703514 : gcc_assert (x == num);
476 :
477 : /* Already sorted. */
478 703514 : if (num == 1)
479 : return;
480 :
481 : /* We don't want to depend on qsort_r, so we have to stuff away
482 : additional data into globals so it can be referenced in
483 : compare_pairs. */
484 379809 : conflicts_ = conflicts;
485 379809 : map_ = map;
486 379809 : qsort (cl->sorted, num, sizeof (coalesce_pair *), compare_pairs);
487 379809 : conflicts_ = NULL;
488 379809 : map_ = NULL;
489 : }
490 :
491 :
492 : /* Send debug info for coalesce list CL to file F. */
493 :
494 : static void
495 64 : dump_coalesce_list (FILE *f, coalesce_list *cl)
496 : {
497 64 : coalesce_pair *node;
498 64 : coalesce_iterator_type ppi;
499 :
500 64 : int x;
501 64 : tree var;
502 :
503 64 : if (cl->sorted == NULL)
504 : {
505 50 : fprintf (f, "Coalesce List:\n");
506 50 : FOR_EACH_PARTITION_PAIR (node, ppi, cl)
507 : {
508 0 : tree var1 = ssa_name (node->first_element);
509 0 : tree var2 = ssa_name (node->second_element);
510 0 : print_generic_expr (f, var1, TDF_SLIM);
511 0 : fprintf (f, " <-> ");
512 0 : print_generic_expr (f, var2, TDF_SLIM);
513 0 : fprintf (f, " (%1d, %1d), ", node->cost, node->conflict_count);
514 0 : fprintf (f, "\n");
515 : }
516 : }
517 : else
518 : {
519 14 : fprintf (f, "Sorted Coalesce list:\n");
520 46 : for (x = cl->num_sorted - 1 ; x >=0; x--)
521 : {
522 32 : node = cl->sorted[x];
523 32 : fprintf (f, "(%d, %d) ", node->cost, node->conflict_count);
524 32 : var = ssa_name (node->first_element);
525 32 : print_generic_expr (f, var, TDF_SLIM);
526 32 : fprintf (f, " <-> ");
527 32 : var = ssa_name (node->second_element);
528 32 : print_generic_expr (f, var, TDF_SLIM);
529 32 : fprintf (f, "\n");
530 : }
531 : }
532 64 : }
533 :
534 :
535 : /* Return an empty new conflict graph for SIZE elements. */
536 :
537 : static inline ssa_conflicts *
538 1293864 : ssa_conflicts_new (unsigned size)
539 : {
540 1293864 : ssa_conflicts *ptr;
541 :
542 1293864 : ptr = XNEW (ssa_conflicts);
543 1293864 : bitmap_obstack_initialize (&ptr->obstack);
544 1293864 : ptr->conflicts.create (size);
545 1293864 : ptr->conflicts.safe_grow_cleared (size, true);
546 1293864 : return ptr;
547 : }
548 :
549 :
550 : /* Free storage for conflict graph PTR. */
551 :
552 : static inline void
553 1293864 : ssa_conflicts_delete (ssa_conflicts *ptr)
554 : {
555 1293864 : bitmap_obstack_release (&ptr->obstack);
556 1293864 : ptr->conflicts.release ();
557 1293864 : free (ptr);
558 1293864 : }
559 :
560 :
561 : /* Test if elements X and Y conflict in graph PTR. */
562 :
563 : static inline bool
564 5887563 : ssa_conflicts_test_p (ssa_conflicts *ptr, unsigned x, unsigned y)
565 : {
566 5887563 : bitmap bx = ptr->conflicts[x];
567 5887563 : bitmap by = ptr->conflicts[y];
568 :
569 5887563 : gcc_checking_assert (x != y);
570 :
571 5887563 : if (bx)
572 : /* Avoid the lookup if Y has no conflicts. */
573 1313528 : return by ? bitmap_bit_p (bx, y) : false;
574 : else
575 : return false;
576 : }
577 :
578 :
579 : /* Add a conflict with Y to the bitmap for X in graph PTR. */
580 :
581 : static inline void
582 3032180 : ssa_conflicts_add_one (ssa_conflicts *ptr, unsigned x, unsigned y)
583 : {
584 3032180 : bitmap bx = ptr->conflicts[x];
585 : /* If there are no conflicts yet, allocate the bitmap and set bit. */
586 3032180 : if (! bx)
587 1290113 : bx = ptr->conflicts[x] = BITMAP_ALLOC (&ptr->obstack);
588 3032180 : bitmap_set_bit (bx, y);
589 3032180 : }
590 :
591 :
592 : /* Add conflicts between X and Y in graph PTR. */
593 :
594 : static inline void
595 1516090 : ssa_conflicts_add (ssa_conflicts *ptr, unsigned x, unsigned y)
596 : {
597 1516090 : gcc_checking_assert (x != y);
598 1516090 : ssa_conflicts_add_one (ptr, x, y);
599 1516090 : ssa_conflicts_add_one (ptr, y, x);
600 1516090 : }
601 :
602 :
603 : /* Merge all Y's conflict into X in graph PTR. */
604 :
605 : static inline void
606 5380982 : ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y)
607 : {
608 5380982 : unsigned z;
609 5380982 : bitmap_iterator bi;
610 5380982 : bitmap bx = ptr->conflicts[x];
611 5380982 : bitmap by = ptr->conflicts[y];
612 :
613 5380982 : gcc_checking_assert (x != y);
614 5380982 : if (! by)
615 4666035 : return;
616 :
617 : /* Add a conflict between X and every one Y has. If the bitmap doesn't
618 : exist, then it has already been coalesced, and we don't need to add a
619 : conflict. */
620 2359103 : EXECUTE_IF_SET_IN_BITMAP (by, 0, z, bi)
621 : {
622 1644156 : bitmap bz = ptr->conflicts[z];
623 1644156 : if (bz)
624 : {
625 1644156 : bool was_there = bitmap_clear_bit (bz, y);
626 1644156 : gcc_checking_assert (was_there);
627 1644156 : bitmap_set_bit (bz, x);
628 : }
629 : }
630 :
631 714947 : if (bx)
632 : {
633 : /* If X has conflicts, add Y's to X. */
634 602319 : bitmap_ior_into (bx, by);
635 602319 : BITMAP_FREE (by);
636 602319 : ptr->conflicts[y] = NULL;
637 : }
638 : else
639 : {
640 : /* If X has no conflicts, simply use Y's. */
641 112628 : ptr->conflicts[x] = by;
642 112628 : ptr->conflicts[y] = NULL;
643 : }
644 : }
645 :
646 :
647 : /* Dump a conflicts graph. */
648 :
649 : static void
650 64 : ssa_conflicts_dump (FILE *file, ssa_conflicts *ptr)
651 : {
652 64 : unsigned x;
653 64 : bitmap b;
654 :
655 64 : fprintf (file, "\nConflict graph:\n");
656 :
657 248 : FOR_EACH_VEC_ELT (ptr->conflicts, x, b)
658 120 : if (b)
659 : {
660 0 : fprintf (file, "%d: ", x);
661 0 : dump_bitmap (file, b);
662 : }
663 64 : }
664 :
665 :
666 : /* This structure is used to efficiently record the current status of live
667 : SSA_NAMES when building a conflict graph.
668 : LIVE_BASE_VAR has a bit set for each base variable which has at least one
669 : ssa version live.
670 : LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
671 : index, and is used to track what partitions of each base variable are
672 : live. This makes it easy to add conflicts between just live partitions
673 : with the same base variable.
674 : The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
675 : marked as being live. This delays clearing of these bitmaps until
676 : they are actually needed again. */
677 :
678 : class live_track
679 : {
680 : public:
681 : bitmap_obstack obstack; /* A place to allocate our bitmaps. */
682 : bitmap_head live_base_var; /* Indicates if a basevar is live. */
683 : bitmap_head *live_base_partitions; /* Live partitions for each basevar. */
684 : var_map map; /* Var_map being used for partition mapping. */
685 : };
686 :
687 :
688 : /* This routine will create a new live track structure based on the partitions
689 : in MAP. */
690 :
691 : static live_track *
692 1293864 : new_live_track (var_map map)
693 : {
694 1293864 : live_track *ptr;
695 1293864 : int lim, x;
696 :
697 : /* Make sure there is a partition view in place. */
698 1293864 : gcc_assert (map->partition_to_base_index != NULL);
699 :
700 1293864 : ptr = XNEW (live_track);
701 1293864 : ptr->map = map;
702 1293864 : lim = num_basevars (map);
703 1293864 : bitmap_obstack_initialize (&ptr->obstack);
704 1293864 : ptr->live_base_partitions = XNEWVEC (bitmap_head, lim);
705 1293864 : bitmap_initialize (&ptr->live_base_var, &ptr->obstack);
706 6781181 : for (x = 0; x < lim; x++)
707 5487317 : bitmap_initialize (&ptr->live_base_partitions[x], &ptr->obstack);
708 1293864 : return ptr;
709 : }
710 :
711 :
712 : /* This routine will free the memory associated with PTR. */
713 :
714 : static void
715 1293864 : delete_live_track (live_track *ptr)
716 : {
717 1293864 : bitmap_obstack_release (&ptr->obstack);
718 1293864 : XDELETEVEC (ptr->live_base_partitions);
719 1293864 : XDELETE (ptr);
720 1293864 : }
721 :
722 :
723 : /* This function will remove PARTITION from the live list in PTR. */
724 :
725 : static inline void
726 10890166 : live_track_remove_partition (live_track *ptr, int partition)
727 : {
728 10890166 : int root;
729 :
730 10890166 : root = basevar_index (ptr->map, partition);
731 10890166 : bitmap_clear_bit (&ptr->live_base_partitions[root], partition);
732 : /* If the element list is empty, make the base variable not live either. */
733 10890166 : if (bitmap_empty_p (&ptr->live_base_partitions[root]))
734 9559491 : bitmap_clear_bit (&ptr->live_base_var, root);
735 10890166 : }
736 :
737 :
738 : /* This function will adds PARTITION to the live list in PTR. */
739 :
740 : static inline void
741 46102780 : live_track_add_partition (live_track *ptr, int partition)
742 : {
743 46102780 : int root;
744 :
745 46102780 : root = basevar_index (ptr->map, partition);
746 : /* If this base var wasn't live before, it is now. Clear the element list
747 : since it was delayed until needed. */
748 46102780 : if (bitmap_set_bit (&ptr->live_base_var, root))
749 34237153 : bitmap_clear (&ptr->live_base_partitions[root]);
750 46102780 : bitmap_set_bit (&ptr->live_base_partitions[root], partition);
751 :
752 46102780 : }
753 :
754 :
755 : /* Clear the live bit for VAR in PTR. */
756 :
757 : static inline void
758 689732 : live_track_clear_var (live_track *ptr, tree var)
759 : {
760 689732 : int p;
761 :
762 689732 : p = var_to_partition (ptr->map, var);
763 689732 : if (p != NO_PARTITION)
764 594337 : live_track_remove_partition (ptr, p);
765 689732 : }
766 :
767 :
768 : /* Return TRUE if VAR is live in PTR. */
769 :
770 : static inline bool
771 2906823 : live_track_live_p (live_track *ptr, tree var)
772 : {
773 2906823 : int p, root;
774 :
775 2906823 : p = var_to_partition (ptr->map, var);
776 2906823 : if (p != NO_PARTITION)
777 : {
778 2866423 : root = basevar_index (ptr->map, p);
779 2866423 : if (bitmap_bit_p (&ptr->live_base_var, root))
780 2866423 : return bitmap_bit_p (&ptr->live_base_partitions[root], p);
781 : }
782 : return false;
783 : }
784 :
785 :
786 : /* This routine will add USE to PTR. USE will be marked as live in both the
787 : ssa live map and the live bitmap for the root of USE. */
788 :
789 : static inline void
790 40671304 : live_track_process_use (live_track *ptr, tree use)
791 : {
792 40671304 : int p;
793 :
794 40671304 : p = var_to_partition (ptr->map, use);
795 40671304 : if (p == NO_PARTITION)
796 : return;
797 :
798 : /* Mark as live in the appropriate live list. */
799 16427601 : live_track_add_partition (ptr, p);
800 : }
801 :
802 :
803 : /* This routine will process a DEF in PTR. DEF will be removed from the live
804 : lists, and if there are any other live partitions with the same base
805 : variable, conflicts will be added to GRAPH. */
806 :
807 : static inline void
808 28630054 : live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph)
809 : {
810 28630054 : int p, root;
811 28630054 : bitmap b;
812 28630054 : unsigned x;
813 28630054 : bitmap_iterator bi;
814 :
815 28630054 : p = var_to_partition (ptr->map, def);
816 28630054 : if (p == NO_PARTITION)
817 18334225 : return;
818 :
819 : /* Clear the liveness bit. */
820 10295829 : live_track_remove_partition (ptr, p);
821 :
822 : /* If the bitmap isn't empty now, conflicts need to be added. */
823 10295829 : root = basevar_index (ptr->map, p);
824 10295829 : if (bitmap_bit_p (&ptr->live_base_var, root))
825 : {
826 947064 : b = &ptr->live_base_partitions[root];
827 2463154 : EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
828 1516090 : ssa_conflicts_add (graph, p, x);
829 : }
830 : }
831 :
832 :
833 : /* Initialize PTR with the partitions set in INIT. */
834 :
835 : static inline void
836 11806736 : live_track_init (live_track *ptr, bitmap init)
837 : {
838 11806736 : unsigned p;
839 11806736 : bitmap_iterator bi;
840 :
841 : /* Mark all live on exit partitions. */
842 41481915 : EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
843 29675179 : live_track_add_partition (ptr, p);
844 11806736 : }
845 :
846 :
847 : /* This routine will clear all live partitions in PTR. */
848 :
849 : static inline void
850 11806736 : live_track_clear_base_vars (live_track *ptr)
851 : {
852 : /* Simply clear the live base list. Anything marked as live in the element
853 : lists will be cleared later if/when the base variable ever comes alive
854 : again. */
855 11806736 : bitmap_clear (&ptr->live_base_var);
856 : }
857 :
858 :
859 : /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
860 : partition view of the var_map liveinfo is based on get entries in the
861 : conflict graph. Only conflicts between ssa_name partitions with the same
862 : base variable are added. */
863 :
864 : static ssa_conflicts *
865 1293864 : build_ssa_conflict_graph (tree_live_info_p liveinfo)
866 : {
867 1293864 : ssa_conflicts *graph;
868 1293864 : var_map map;
869 1293864 : basic_block bb;
870 1293864 : ssa_op_iter iter;
871 1293864 : live_track *live;
872 1293864 : basic_block entry;
873 :
874 : /* If inter-variable coalescing is enabled, we may attempt to
875 : coalesce variables from different base variables, including
876 : different parameters, so we have to make sure default defs live
877 : at the entry block conflict with each other. */
878 1293864 : if (flag_tree_coalesce_vars)
879 932705 : entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
880 : else
881 : entry = NULL;
882 :
883 1293864 : map = live_var_map (liveinfo);
884 1293864 : graph = ssa_conflicts_new (num_var_partitions (map));
885 :
886 1293864 : live = new_live_track (map);
887 :
888 13100600 : for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
889 : {
890 : /* Start with live on exit temporaries. */
891 11806736 : live_track_init (live, live_on_exit (liveinfo, bb));
892 :
893 11806736 : for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
894 191789036 : gsi_prev (&gsi))
895 : {
896 89991150 : tree var;
897 89991150 : gimple *stmt = gsi_stmt (gsi);
898 :
899 89991150 : if (is_gimple_debug (stmt))
900 47327599 : continue;
901 :
902 42663551 : if (map->bitint)
903 : {
904 81817 : build_bitint_stmt_ssa_conflicts (stmt, live, graph, map->bitint,
905 : live_track_process_def,
906 : live_track_process_use,
907 : live_track_clear_var);
908 81817 : continue;
909 : }
910 :
911 : /* A copy between 2 partitions does not introduce an interference
912 : by itself. If they did, you would never be able to coalesce
913 : two things which are copied. If the two variables really do
914 : conflict, they will conflict elsewhere in the program.
915 :
916 : This is handled by simply removing the SRC of the copy from the
917 : live list, and processing the stmt normally. */
918 42581734 : if (is_gimple_assign (stmt))
919 : {
920 29309362 : tree lhs = gimple_assign_lhs (stmt);
921 29309362 : tree rhs1 = gimple_assign_rhs1 (stmt);
922 29309362 : if (gimple_assign_copy_p (stmt)
923 8003647 : && TREE_CODE (lhs) == SSA_NAME
924 30519841 : && TREE_CODE (rhs1) == SSA_NAME)
925 689701 : live_track_clear_var (live, rhs1);
926 : }
927 :
928 : /* For stmts with more than one SSA_NAME definition pretend all the
929 : SSA_NAME outputs but the first one are live at this point, so
930 : that conflicts are added in between all those even when they are
931 : actually not really live after the asm, because expansion might
932 : copy those into pseudos after the asm and if multiple outputs
933 : share the same partition, it might overwrite those that should
934 : be live. E.g.
935 : asm volatile (".." : "=r" (a) : "=r" (b) : "0" (a), "1" (a));
936 : return a;
937 : See PR70593. */
938 42581734 : bool first = true;
939 65631125 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
940 23049391 : if (first)
941 : first = false;
942 : else
943 18363 : live_track_process_use (live, var);
944 :
945 65631125 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
946 23049391 : live_track_process_def (live, var, graph);
947 :
948 80522068 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
949 37940334 : live_track_process_use (live, var);
950 : }
951 :
952 : /* If result of a PHI is unused, looping over the statements will not
953 : record any conflicts since the def was never live. Since the PHI node
954 : is going to be translated out of SSA form, it will insert a copy.
955 : There must be a conflict recorded between the result of the PHI and
956 : any variables that are live. Otherwise the out-of-ssa translation
957 : may create incorrect code. */
958 14719215 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
959 2912479 : gsi_next (&gsi))
960 : {
961 2912479 : gphi *phi = gsi.phi ();
962 2912479 : tree result = PHI_RESULT (phi);
963 5824958 : if (virtual_operand_p (result))
964 5656 : continue;
965 2906823 : if (live_track_live_p (live, result))
966 2866423 : live_track_process_def (live, result, graph);
967 : }
968 :
969 : /* Pretend there are defs for params' default defs at the start
970 : of the (post-)entry block. This will prevent PARM_DECLs from
971 : coalescing into the same partition. Although RESULT_DECLs'
972 : default defs don't have a useful initial value, we have to
973 : prevent them from coalescing with PARM_DECLs' default defs
974 : too, otherwise assign_parms would attempt to assign different
975 : RTL to the same partition. */
976 11806736 : if (bb == entry)
977 : {
978 : unsigned i;
979 : tree var;
980 :
981 54191092 : FOR_EACH_SSA_NAME (i, var, cfun)
982 : {
983 33258538 : if (!SSA_NAME_IS_DEFAULT_DEF (var)
984 3889629 : || !SSA_NAME_VAR (var)
985 37148167 : || VAR_P (SSA_NAME_VAR (var)))
986 30580729 : continue;
987 :
988 2677809 : live_track_process_def (live, var, graph);
989 : /* Process a use too, so that it remains live and
990 : conflicts with other parms' default defs, even unused
991 : ones. */
992 2677809 : live_track_process_use (live, var);
993 : }
994 : }
995 :
996 11806736 : live_track_clear_base_vars (live);
997 : }
998 :
999 1293864 : delete_live_track (live);
1000 1293864 : return graph;
1001 : }
1002 :
1003 : /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
1004 :
1005 : static inline void
1006 0 : fail_abnormal_edge_coalesce (int x, int y)
1007 : {
1008 0 : fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
1009 0 : fprintf (stderr, " which are marked as MUST COALESCE.\n");
1010 0 : print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
1011 0 : fprintf (stderr, " and ");
1012 0 : print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
1013 :
1014 0 : internal_error ("SSA corruption");
1015 : }
1016 :
1017 : /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
1018 : and the DECL's default def is unused (i.e., it was introduced by
1019 : create_default_def for out-of-ssa), mark VAR and the default def for
1020 : coalescing. */
1021 :
1022 : static void
1023 31400731 : coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
1024 : {
1025 31400731 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1026 27485388 : || !SSA_NAME_VAR (var)
1027 38147625 : || VAR_P (SSA_NAME_VAR (var)))
1028 : return;
1029 :
1030 158928 : tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var));
1031 158928 : if (!has_zero_uses (ssa))
1032 : return;
1033 :
1034 771 : add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var));
1035 771 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1036 : /* Default defs will have their used_in_copy bits set at the beginning of
1037 : populate_coalesce_list_for_outofssa. */
1038 : }
1039 :
1040 :
1041 : /* Given var_map MAP for a region, this function creates and returns a coalesce
1042 : list as well as recording related ssa names in USED_IN_COPIES for use later
1043 : in the out-of-ssa or live range computation process. */
1044 :
1045 : static coalesce_list *
1046 1477646 : create_coalesce_list_for_region (var_map map, bitmap used_in_copy)
1047 : {
1048 1477646 : gimple_stmt_iterator gsi;
1049 1477646 : basic_block bb;
1050 1477646 : coalesce_list *cl = create_coalesce_list ();
1051 1477646 : gimple *stmt;
1052 1477646 : int v1, v2, cost;
1053 :
1054 14077803 : for (unsigned j = 0; map->vec_bbs.iterate (j, &bb); ++j)
1055 : {
1056 12600157 : tree arg;
1057 :
1058 12600157 : for (gphi_iterator gpi = gsi_start_phis (bb);
1059 15513944 : !gsi_end_p (gpi);
1060 2913787 : gsi_next (&gpi))
1061 : {
1062 2913787 : gphi *phi = gpi.phi ();
1063 2913787 : size_t i;
1064 2913787 : int ver;
1065 2913787 : tree res;
1066 2913787 : bool saw_copy = false;
1067 :
1068 2913787 : res = gimple_phi_result (phi);
1069 5827574 : if (virtual_operand_p (res))
1070 6059 : continue;
1071 2907728 : ver = SSA_NAME_VERSION (res);
1072 2907728 : if (map->bitint && !bitmap_bit_p (map->bitint, ver))
1073 751 : continue;
1074 :
1075 : /* Register ssa_names and coalesces between the args and the result
1076 : of all PHI. */
1077 10034252 : for (i = 0; i < gimple_phi_num_args (phi); i++)
1078 : {
1079 7127275 : edge e = gimple_phi_arg_edge (phi, i);
1080 7127275 : arg = PHI_ARG_DEF (phi, i);
1081 7127275 : if (TREE_CODE (arg) != SSA_NAME)
1082 1290588 : continue;
1083 :
1084 5836687 : if (gimple_can_coalesce_p (arg, res)
1085 5836687 : || (e->flags & EDGE_ABNORMAL))
1086 : {
1087 5836385 : saw_copy = true;
1088 5836385 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1089 5836385 : if ((e->flags & EDGE_ABNORMAL) == 0)
1090 : {
1091 5641918 : int cost = coalesce_cost_edge (e);
1092 5641918 : if (cost == 1 && has_single_use (arg))
1093 272233 : add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1094 : else
1095 5369685 : add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1096 : }
1097 : }
1098 : }
1099 2906977 : if (saw_copy)
1100 2832090 : bitmap_set_bit (used_in_copy, ver);
1101 : }
1102 :
1103 120743466 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1104 : {
1105 95543152 : stmt = gsi_stmt (gsi);
1106 :
1107 95543152 : if (is_gimple_debug (stmt))
1108 49150209 : continue;
1109 :
1110 : /* Check for copy coalesces. */
1111 46392943 : switch (gimple_code (stmt))
1112 : {
1113 31610957 : case GIMPLE_ASSIGN:
1114 31610957 : {
1115 31610957 : tree lhs = gimple_assign_lhs (stmt);
1116 31610957 : tree rhs1 = gimple_assign_rhs1 (stmt);
1117 31610957 : if (gimple_assign_ssa_name_copy_p (stmt)
1118 31610957 : && gimple_can_coalesce_p (lhs, rhs1))
1119 : {
1120 366065 : v1 = SSA_NAME_VERSION (lhs);
1121 366065 : v2 = SSA_NAME_VERSION (rhs1);
1122 366065 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1123 : break;
1124 365999 : cost = coalesce_cost_bb (bb);
1125 365999 : add_coalesce (cl, v1, v2, cost);
1126 365999 : bitmap_set_bit (used_in_copy, v1);
1127 365999 : bitmap_set_bit (used_in_copy, v2);
1128 : }
1129 : }
1130 : break;
1131 :
1132 1445388 : case GIMPLE_RETURN:
1133 1445388 : {
1134 1445388 : tree res = DECL_RESULT (current_function_decl);
1135 1445388 : if (VOID_TYPE_P (TREE_TYPE (res))
1136 1445388 : || !is_gimple_reg (res))
1137 : break;
1138 661494 : tree rhs1 = gimple_return_retval (as_a <greturn *> (stmt));
1139 661494 : if (!rhs1)
1140 : break;
1141 656302 : tree lhs = ssa_default_def (cfun, res);
1142 656302 : if (map->bitint && !lhs)
1143 : break;
1144 655822 : gcc_assert (lhs);
1145 655822 : if (TREE_CODE (rhs1) == SSA_NAME
1146 655822 : && gimple_can_coalesce_p (lhs, rhs1))
1147 : {
1148 378736 : v1 = SSA_NAME_VERSION (lhs);
1149 378736 : v2 = SSA_NAME_VERSION (rhs1);
1150 378736 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1151 : break;
1152 378736 : cost = coalesce_cost_bb (bb);
1153 378736 : add_coalesce (cl, v1, v2, cost);
1154 378736 : bitmap_set_bit (used_in_copy, v1);
1155 378736 : bitmap_set_bit (used_in_copy, v2);
1156 : }
1157 : break;
1158 : }
1159 :
1160 109507 : case GIMPLE_ASM:
1161 109507 : {
1162 109507 : gasm *asm_stmt = as_a <gasm *> (stmt);
1163 109507 : unsigned long noutputs, i;
1164 109507 : unsigned long ninputs;
1165 109507 : tree *outputs, link;
1166 109507 : noutputs = gimple_asm_noutputs (asm_stmt);
1167 109507 : ninputs = gimple_asm_ninputs (asm_stmt);
1168 109507 : outputs = (tree *) alloca (noutputs * sizeof (tree));
1169 185007 : for (i = 0; i < noutputs; ++i)
1170 : {
1171 75500 : link = gimple_asm_output_op (asm_stmt, i);
1172 75500 : outputs[i] = TREE_VALUE (link);
1173 : }
1174 :
1175 164238 : for (i = 0; i < ninputs; ++i)
1176 : {
1177 54731 : const char *constraint;
1178 54731 : tree input;
1179 54731 : char *end;
1180 54731 : unsigned long match;
1181 :
1182 54731 : link = gimple_asm_input_op (asm_stmt, i);
1183 54731 : constraint
1184 54731 : = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1185 54731 : input = TREE_VALUE (link);
1186 :
1187 54731 : if (TREE_CODE (input) != SSA_NAME)
1188 49843 : continue;
1189 :
1190 14594 : match = strtoul (constraint, &end, 10);
1191 14594 : if (match >= noutputs || end == constraint)
1192 7998 : continue;
1193 :
1194 6596 : if (TREE_CODE (outputs[match]) != SSA_NAME)
1195 1708 : continue;
1196 :
1197 4888 : v1 = SSA_NAME_VERSION (outputs[match]);
1198 4888 : v2 = SSA_NAME_VERSION (input);
1199 4888 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1200 0 : continue;
1201 :
1202 4888 : if (gimple_can_coalesce_p (outputs[match], input))
1203 : {
1204 4461 : cost = coalesce_cost (REG_BR_PROB_BASE,
1205 4461 : optimize_bb_for_size_p (bb));
1206 4461 : add_coalesce (cl, v1, v2, cost);
1207 4461 : bitmap_set_bit (used_in_copy, v1);
1208 4461 : bitmap_set_bit (used_in_copy, v2);
1209 : }
1210 : }
1211 : break;
1212 : }
1213 :
1214 : default:
1215 : break;
1216 : }
1217 : }
1218 : }
1219 :
1220 1477646 : return cl;
1221 : }
1222 :
1223 :
1224 : /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1225 :
1226 : struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
1227 : {
1228 : static inline hashval_t hash (const tree_node *);
1229 : static inline int equal (const tree_node *, const tree_node *);
1230 : };
1231 :
1232 : inline hashval_t
1233 6728514 : ssa_name_var_hash::hash (const_tree n)
1234 : {
1235 6728514 : return DECL_UID (SSA_NAME_VAR (n));
1236 : }
1237 :
1238 : inline int
1239 4944760 : ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
1240 : {
1241 9889520 : return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
1242 : }
1243 :
1244 :
1245 : /* This function populates coalesce list CL as well as recording related ssa
1246 : names in USED_IN_COPIES for use later in the out-of-ssa process. */
1247 :
1248 : static void
1249 1472141 : populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy)
1250 : {
1251 1472141 : tree var;
1252 1472141 : tree first;
1253 1472141 : int v1, v2, cost;
1254 1472141 : unsigned i;
1255 :
1256 : /* Process result decls and live on entry variables for entry into the
1257 : coalesce list. */
1258 1472141 : first = NULL_TREE;
1259 72560160 : FOR_EACH_SSA_NAME (i, var, cfun)
1260 : {
1261 96588756 : if (!virtual_operand_p (var))
1262 : {
1263 31400731 : coalesce_with_default (var, cl, used_in_copy);
1264 :
1265 : /* Add coalesces between all the result decls. */
1266 31400731 : if (SSA_NAME_VAR (var)
1267 10662237 : && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1268 : {
1269 673378 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1270 673378 : if (first == NULL_TREE)
1271 : first = var;
1272 : else
1273 : {
1274 0 : gcc_assert (gimple_can_coalesce_p (var, first));
1275 0 : v1 = SSA_NAME_VERSION (first);
1276 0 : v2 = SSA_NAME_VERSION (var);
1277 0 : cost = coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
1278 0 : add_coalesce (cl, v1, v2, cost);
1279 : }
1280 : }
1281 : /* Mark any default_def variables as being in the coalesce list
1282 : since they will have to be coalesced with the base variable. If
1283 : not marked as present, they won't be in the coalesce view. */
1284 31400731 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1285 31400731 : && (!has_zero_uses (var)
1286 1886040 : || (SSA_NAME_VAR (var)
1287 1886040 : && !VAR_P (SSA_NAME_VAR (var)))))
1288 3667352 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1289 : }
1290 : }
1291 :
1292 : /* If this optimization is disabled, we need to coalesce all the
1293 : names originating from the same SSA_NAME_VAR so debug info
1294 : remains undisturbed. */
1295 1472141 : if (!flag_tree_coalesce_vars)
1296 : {
1297 428176 : tree a;
1298 428176 : hash_table<ssa_name_var_hash> ssa_name_hash (10);
1299 :
1300 13912145 : FOR_EACH_SSA_NAME (i, a, cfun)
1301 : {
1302 12569588 : if (SSA_NAME_VAR (a)
1303 6562127 : && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1304 1772385 : && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
1305 233427 : || !VAR_P (SSA_NAME_VAR (a))))
1306 : {
1307 1772354 : tree *slot = ssa_name_hash.find_slot (a, INSERT);
1308 :
1309 1772354 : if (!*slot)
1310 1199662 : *slot = a;
1311 : else
1312 : {
1313 : /* If the variable is a PARM_DECL or a RESULT_DECL, we
1314 : _require_ that all the names originating from it be
1315 : coalesced, because there must be a single partition
1316 : containing all the names so that it can be assigned
1317 : the canonical RTL location of the DECL safely.
1318 : If in_lto_p, a function could have been compiled
1319 : originally with optimizations and only the link
1320 : performed at -O0, so we can't actually require it. */
1321 572692 : const int cost
1322 659164 : = (VAR_P (SSA_NAME_VAR (a)) || in_lto_p)
1323 572692 : ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
1324 1145384 : add_coalesce (cl, SSA_NAME_VERSION (a),
1325 572692 : SSA_NAME_VERSION (*slot), cost);
1326 572692 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a));
1327 572692 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot));
1328 : }
1329 : }
1330 : }
1331 428176 : }
1332 1472141 : }
1333 :
1334 :
1335 : /* Attempt to coalesce ssa versions X and Y together using the partition
1336 : mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1337 : DEBUG, if it is nun-NULL. */
1338 :
1339 : static inline bool
1340 6519931 : attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y,
1341 : FILE *debug)
1342 : {
1343 6519931 : int z;
1344 6519931 : tree var1, var2;
1345 6519931 : int p1, p2;
1346 :
1347 6519931 : p1 = var_to_partition (map, ssa_name (x));
1348 6519931 : p2 = var_to_partition (map, ssa_name (y));
1349 :
1350 6519931 : if (debug)
1351 : {
1352 32 : fprintf (debug, "(%d)", x);
1353 32 : print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1354 32 : fprintf (debug, " & (%d)", y);
1355 32 : print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1356 : }
1357 :
1358 6519931 : if (p1 == p2)
1359 : {
1360 632368 : if (debug)
1361 0 : fprintf (debug, ": Already Coalesced.\n");
1362 632368 : return true;
1363 : }
1364 :
1365 5887563 : if (debug)
1366 32 : fprintf (debug, " [map: %d, %d] ", p1, p2);
1367 :
1368 :
1369 5887563 : if (!ssa_conflicts_test_p (graph, p1, p2))
1370 : {
1371 5380982 : var1 = partition_to_var (map, p1);
1372 5380982 : var2 = partition_to_var (map, p2);
1373 :
1374 5380982 : z = var_union (map, var1, var2);
1375 5380982 : if (z == NO_PARTITION)
1376 : {
1377 0 : if (debug)
1378 0 : fprintf (debug, ": Unable to perform partition union.\n");
1379 0 : return false;
1380 : }
1381 :
1382 : /* z is the new combined partition. Remove the other partition from
1383 : the list, and merge the conflicts. */
1384 5380982 : if (z == p1)
1385 4513503 : ssa_conflicts_merge (graph, p1, p2);
1386 : else
1387 867479 : ssa_conflicts_merge (graph, p2, p1);
1388 :
1389 5380982 : if (debug)
1390 32 : fprintf (debug, ": Success -> %d\n", z);
1391 :
1392 5380982 : return true;
1393 : }
1394 :
1395 506581 : if (debug)
1396 0 : fprintf (debug, ": Fail due to conflict\n");
1397 :
1398 : return false;
1399 : }
1400 :
1401 :
1402 : /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1403 : GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1404 :
1405 : static void
1406 1293864 : coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
1407 : FILE *debug)
1408 : {
1409 1293864 : int x = 0, y = 0;
1410 1293864 : tree var1, var2;
1411 1293864 : int cost;
1412 1293864 : basic_block bb;
1413 1293864 : edge e;
1414 1293864 : edge_iterator ei;
1415 :
1416 : /* First, coalesce all the copies across abnormal edges. These are not placed
1417 : in the coalesce list because they do not need to be sorted, and simply
1418 : consume extra memory/compilation time in large programs. */
1419 :
1420 13100600 : FOR_EACH_BB_FN (bb, cfun)
1421 : {
1422 29008651 : FOR_EACH_EDGE (e, ei, bb->preds)
1423 17201915 : if (e->flags & EDGE_ABNORMAL)
1424 : {
1425 8531 : gphi_iterator gsi;
1426 203074 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1427 194543 : gsi_next (&gsi))
1428 : {
1429 194543 : gphi *phi = gsi.phi ();
1430 194543 : tree res = PHI_RESULT (phi);
1431 389086 : if (virtual_operand_p (res))
1432 48 : continue;
1433 194495 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1434 194495 : if (SSA_NAME_IS_DEFAULT_DEF (arg)
1435 194495 : && (!SSA_NAME_VAR (arg)
1436 953 : || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1437 848 : continue;
1438 :
1439 193647 : int v1 = SSA_NAME_VERSION (res);
1440 193647 : int v2 = SSA_NAME_VERSION (arg);
1441 :
1442 193647 : if (debug)
1443 0 : fprintf (debug, "Abnormal coalesce: ");
1444 :
1445 193647 : if (!attempt_coalesce (map, graph, v1, v2, debug))
1446 0 : fail_abnormal_edge_coalesce (v1, v2);
1447 : }
1448 : }
1449 : }
1450 :
1451 : /* Now process the items in the coalesce list. */
1452 :
1453 7615362 : while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1454 : {
1455 6321498 : var1 = ssa_name (x);
1456 6321498 : var2 = ssa_name (y);
1457 :
1458 : /* Assert the coalesces have the same base variable. */
1459 6321498 : gcc_assert (gimple_can_coalesce_p (var1, var2));
1460 :
1461 6321498 : if (debug)
1462 32 : fprintf (debug, "Coalesce list: ");
1463 6321498 : attempt_coalesce (map, graph, x, y, debug);
1464 : }
1465 1293864 : }
1466 :
1467 :
1468 : /* Output partition map MAP with coalescing plan PART to file F. */
1469 :
1470 : void
1471 115 : dump_part_var_map (FILE *f, partition part, var_map map)
1472 : {
1473 115 : int t;
1474 115 : unsigned x, y;
1475 115 : int p;
1476 :
1477 115 : fprintf (f, "\nCoalescible Partition map \n\n");
1478 :
1479 235 : for (x = 0; x < map->num_partitions; x++)
1480 : {
1481 120 : if (map->view_to_partition != NULL)
1482 120 : p = map->view_to_partition[x];
1483 : else
1484 0 : p = x;
1485 :
1486 120 : if (ssa_name (p) == NULL_TREE
1487 240 : || virtual_operand_p (ssa_name (p)))
1488 0 : continue;
1489 :
1490 : t = 0;
1491 1658 : for (y = 1; y < num_ssa_names; y++)
1492 : {
1493 1538 : tree var = version_to_var (map, y);
1494 1538 : if (!var)
1495 1046 : continue;
1496 492 : int q = var_to_partition (map, var);
1497 492 : p = partition_find (part, q);
1498 492 : gcc_assert (map->partition_to_base_index[q]
1499 : == map->partition_to_base_index[p]);
1500 :
1501 492 : if (p == (int)x)
1502 : {
1503 120 : if (t++ == 0)
1504 : {
1505 88 : fprintf (f, "Partition %d, base %d (", x,
1506 : map->partition_to_base_index[q]);
1507 88 : print_generic_expr (f, partition_to_var (map, q), TDF_SLIM);
1508 88 : fprintf (f, " - ");
1509 : }
1510 120 : fprintf (f, "%d ", y);
1511 : }
1512 : }
1513 120 : if (t != 0)
1514 88 : fprintf (f, ")\n");
1515 : }
1516 115 : fprintf (f, "\n");
1517 115 : }
1518 :
1519 : /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
1520 : coalescing together, false otherwise.
1521 :
1522 : This must stay consistent with compute_samebase_partition_bases and
1523 : compute_optimized_partition_bases. */
1524 :
1525 : bool
1526 24501085 : gimple_can_coalesce_p (tree name1, tree name2)
1527 : {
1528 : /* First check the SSA_NAME's associated DECL. Without
1529 : optimization, we only want to coalesce if they have the same DECL
1530 : or both have no associated DECL. */
1531 24501085 : tree var1 = SSA_NAME_VAR (name1);
1532 24501085 : tree var2 = SSA_NAME_VAR (name2);
1533 24501085 : var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
1534 24501085 : var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
1535 24501085 : if (var1 != var2 && !flag_tree_coalesce_vars)
1536 : return false;
1537 :
1538 : /* Now check the types. If the types are the same, then we should
1539 : try to coalesce V1 and V2. */
1540 24010381 : tree t1 = TREE_TYPE (name1);
1541 24010381 : tree t2 = TREE_TYPE (name2);
1542 24010381 : if (t1 == t2)
1543 : {
1544 21934269 : check_modes:
1545 : /* If the base variables are the same, we're good: none of the
1546 : other tests below could possibly fail. */
1547 23379892 : var1 = SSA_NAME_VAR (name1);
1548 23379892 : var2 = SSA_NAME_VAR (name2);
1549 23379892 : if (var1 == var2)
1550 : return true;
1551 :
1552 : /* We don't want to coalesce two SSA names if one of the base
1553 : variables is supposed to be a register while the other is
1554 : supposed to be on the stack. Anonymous SSA names most often
1555 : take registers, but when not optimizing, user variables
1556 : should go on the stack, so coalescing them with the anonymous
1557 : variable as the partition leader would end up assigning the
1558 : user variable to a register. Don't do that! */
1559 4543349 : bool reg1 = use_register_for_decl (name1);
1560 4543349 : bool reg2 = use_register_for_decl (name2);
1561 4543349 : if (reg1 != reg2)
1562 : return false;
1563 :
1564 : /* Check that the promoted modes and unsignedness are the same.
1565 : We don't want to coalesce if the promoted modes would be
1566 : different, or if they would sign-extend differently. Only
1567 : PARM_DECLs and RESULT_DECLs have different promotion rules,
1568 : so skip the test if both are variables, or both are anonymous
1569 : SSA_NAMEs. */
1570 4543327 : int unsigned1, unsigned2;
1571 4543327 : return ((!var1 || VAR_P (var1)) && (!var2 || VAR_P (var2)))
1572 6340793 : || ((promote_ssa_mode (name1, &unsigned1)
1573 898733 : == promote_ssa_mode (name2, &unsigned2))
1574 898733 : && unsigned1 == unsigned2);
1575 : }
1576 :
1577 : /* If alignment requirements are different, we can't coalesce. */
1578 4152224 : if (MINIMUM_ALIGNMENT (t1,
1579 : var1 ? DECL_MODE (var1) : TYPE_MODE (t1),
1580 : var1 ? LOCAL_DECL_ALIGNMENT (var1) : TYPE_ALIGN (t1))
1581 2076112 : != MINIMUM_ALIGNMENT (t2,
1582 : var2 ? DECL_MODE (var2) : TYPE_MODE (t2),
1583 : var2 ? LOCAL_DECL_ALIGNMENT (var2) : TYPE_ALIGN (t2)))
1584 : return false;
1585 :
1586 : /* If the types are not the same, see whether they are compatible. This
1587 : (for example) allows coalescing when the types are fundamentally the
1588 : same, but just have different names. */
1589 1593050 : if (types_compatible_p (t1, t2))
1590 1445623 : goto check_modes;
1591 :
1592 : return false;
1593 : }
1594 :
1595 : /* Fill in MAP's partition_to_base_index, with one index for each
1596 : partition of SSA names USED_IN_COPIES and related by CL coalesce
1597 : possibilities. This must match gimple_can_coalesce_p in the
1598 : optimized case. */
1599 :
1600 : static void
1601 1477646 : compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1602 : coalesce_list *cl)
1603 : {
1604 1477646 : int parts = num_var_partitions (map);
1605 1477646 : partition tentative = partition_new (parts);
1606 :
1607 : /* Partition the SSA versions so that, for each coalescible
1608 : pair, both of its members are in the same partition in
1609 : TENTATIVE. */
1610 1477646 : gcc_assert (!cl->sorted);
1611 1477646 : coalesce_pair *node;
1612 1477646 : coalesce_iterator_type ppi;
1613 13574634 : FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1614 : {
1615 6048494 : tree v1 = ssa_name (node->first_element);
1616 6048494 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1617 6048494 : tree v2 = ssa_name (node->second_element);
1618 6048494 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1619 :
1620 6048494 : if (p1 == p2)
1621 507709 : continue;
1622 :
1623 5540785 : partition_union (tentative, p1, p2);
1624 : }
1625 :
1626 : /* We have to deal with cost one pairs too. */
1627 1750650 : for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1628 : {
1629 273004 : tree v1 = ssa_name (co->first_element);
1630 273004 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1631 273004 : tree v2 = ssa_name (co->second_element);
1632 273004 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1633 :
1634 273004 : if (p1 == p2)
1635 16385 : continue;
1636 :
1637 256619 : partition_union (tentative, p1, p2);
1638 : }
1639 :
1640 : /* And also with abnormal edges. */
1641 1477646 : basic_block bb;
1642 1477646 : edge e;
1643 1477646 : unsigned i;
1644 1477646 : edge_iterator ei;
1645 14077803 : for (i = 0; map->vec_bbs.iterate (i, &bb); ++i)
1646 : {
1647 30839125 : FOR_EACH_EDGE (e, ei, bb->preds)
1648 18238968 : if (e->flags & EDGE_ABNORMAL)
1649 : {
1650 10228 : gphi_iterator gsi;
1651 204771 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1652 194543 : gsi_next (&gsi))
1653 : {
1654 194543 : gphi *phi = gsi.phi ();
1655 194543 : tree res = PHI_RESULT (phi);
1656 389086 : if (virtual_operand_p (res))
1657 48 : continue;
1658 194495 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1659 194495 : if (SSA_NAME_IS_DEFAULT_DEF (arg)
1660 194495 : && (!SSA_NAME_VAR (arg)
1661 953 : || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1662 848 : continue;
1663 :
1664 193647 : int p1 = partition_find (tentative, var_to_partition (map, res));
1665 193647 : int p2 = partition_find (tentative, var_to_partition (map, arg));
1666 :
1667 193647 : if (p1 == p2)
1668 192232 : continue;
1669 :
1670 1415 : partition_union (tentative, p1, p2);
1671 : }
1672 : }
1673 : }
1674 :
1675 1477646 : if (map->bitint
1676 5505 : && flag_tree_coalesce_vars
1677 2784 : && (optimize > 1 || parts < 500))
1678 10367 : for (i = 0; i < (unsigned) parts; ++i)
1679 : {
1680 7583 : tree s1 = partition_to_var (map, i);
1681 7583 : int p1 = partition_find (tentative, i);
1682 34240 : for (unsigned j = i + 1; j < (unsigned) parts; ++j)
1683 : {
1684 26675 : tree s2 = partition_to_var (map, j);
1685 26675 : if (s1 == s2)
1686 0 : continue;
1687 26675 : if (tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1688 26675 : TYPE_SIZE (TREE_TYPE (s2))))
1689 : {
1690 21476 : int p2 = partition_find (tentative, j);
1691 :
1692 21476 : if (p1 == p2)
1693 16865 : continue;
1694 :
1695 4611 : partition_union (tentative, p1, p2);
1696 4611 : if (partition_find (tentative, i) != p1)
1697 : break;
1698 : }
1699 : }
1700 : }
1701 :
1702 1477646 : map->partition_to_base_index = XCNEWVEC (int, parts);
1703 1477646 : auto_vec<unsigned int> index_map (parts);
1704 1477646 : if (parts)
1705 1293864 : index_map.quick_grow (parts);
1706 :
1707 : const unsigned no_part = -1;
1708 : unsigned count = parts;
1709 12768393 : while (count)
1710 11290747 : index_map[--count] = no_part;
1711 :
1712 : /* Initialize MAP's mapping from partition to base index, using
1713 : as base indices an enumeration of the TENTATIVE partitions in
1714 : which each SSA version ended up, so that we compute conflicts
1715 : between all SSA versions that ended up in the same potential
1716 : coalesce partition. */
1717 1477646 : bitmap_iterator bi;
1718 12768393 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1719 : {
1720 11290747 : int pidx = var_to_partition (map, ssa_name (i));
1721 11290747 : int base = partition_find (tentative, pidx);
1722 11290747 : if (index_map[base] != no_part)
1723 5803430 : continue;
1724 5487317 : index_map[base] = count++;
1725 : }
1726 :
1727 1477646 : map->num_basevars = count;
1728 :
1729 12768393 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1730 : {
1731 11290747 : int pidx = var_to_partition (map, ssa_name (i));
1732 11290747 : int base = partition_find (tentative, pidx);
1733 11290747 : gcc_assert (index_map[base] < count);
1734 11290747 : map->partition_to_base_index[pidx] = index_map[base];
1735 : }
1736 :
1737 1477646 : if (dump_file && (dump_flags & TDF_DETAILS))
1738 115 : dump_part_var_map (dump_file, tentative, map);
1739 :
1740 1477646 : partition_delete (tentative);
1741 1477646 : }
1742 :
1743 : /* For the bitint lowering pass, try harder. Partitions which contain
1744 : SSA_NAME default def of a PARM_DECL or have RESULT_DECL need to have
1745 : compatible types because they will use that RESULT_DECL or PARM_DECL.
1746 : Other partitions can have even incompatible _BitInt types, as long
1747 : as they have the same size - those will use VAR_DECLs which are just
1748 : arrays of the limbs. */
1749 :
1750 : static void
1751 2647 : coalesce_bitint (var_map map, ssa_conflicts *graph)
1752 : {
1753 2647 : unsigned n = num_var_partitions (map);
1754 2647 : if (optimize <= 1 && n > 500)
1755 1791 : return;
1756 :
1757 2647 : bool try_same_size = false;
1758 2647 : FILE *debug_file = (dump_flags & TDF_DETAILS) ? dump_file : NULL;
1759 10230 : for (unsigned i = 0; i < n; ++i)
1760 : {
1761 7583 : tree s1 = partition_to_var (map, i);
1762 7583 : if ((unsigned) var_to_partition (map, s1) != i)
1763 2610 : continue;
1764 4973 : int v1 = SSA_NAME_VERSION (s1);
1765 14441 : for (unsigned j = i + 1; j < n; ++j)
1766 : {
1767 9476 : tree s2 = partition_to_var (map, j);
1768 9476 : if (s1 == s2 || (unsigned) var_to_partition (map, s2) != j)
1769 1817 : continue;
1770 7659 : if (!types_compatible_p (TREE_TYPE (s1), TREE_TYPE (s2)))
1771 : {
1772 3470 : if (!try_same_size
1773 4504 : && tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1774 1034 : TYPE_SIZE (TREE_TYPE (s2))))
1775 : try_same_size = true;
1776 3470 : continue;
1777 : }
1778 4189 : int v2 = SSA_NAME_VERSION (s2);
1779 4189 : if (attempt_coalesce (map, graph, v1, v2, debug_file)
1780 4189 : && partition_to_var (map, i) != s1)
1781 : break;
1782 : }
1783 : }
1784 :
1785 2647 : if (!try_same_size)
1786 : return;
1787 :
1788 856 : unsigned i;
1789 856 : bitmap_iterator bi;
1790 856 : bitmap same_type = NULL;
1791 :
1792 3749 : EXECUTE_IF_SET_IN_BITMAP (map->bitint, 0, i, bi)
1793 : {
1794 2893 : tree s = ssa_name (i);
1795 2893 : if (!SSA_NAME_VAR (s))
1796 1617 : continue;
1797 1491 : if (TREE_CODE (SSA_NAME_VAR (s)) != RESULT_DECL
1798 1276 : && (TREE_CODE (SSA_NAME_VAR (s)) != PARM_DECL
1799 1061 : || !SSA_NAME_IS_DEFAULT_DEF (s)))
1800 215 : continue;
1801 1061 : if (same_type == NULL)
1802 816 : same_type = BITMAP_ALLOC (NULL);
1803 1061 : int p = var_to_partition (map, s);
1804 1061 : bitmap_set_bit (same_type, p);
1805 : }
1806 :
1807 3749 : for (i = 0; i < n; ++i)
1808 : {
1809 2893 : if (same_type && bitmap_bit_p (same_type, i))
1810 1061 : continue;
1811 1832 : tree s1 = partition_to_var (map, i);
1812 1832 : if ((unsigned) var_to_partition (map, s1) != i)
1813 845 : continue;
1814 987 : int v1 = SSA_NAME_VERSION (s1);
1815 5150 : for (unsigned j = i + 1; j < n; ++j)
1816 : {
1817 4180 : if (same_type && bitmap_bit_p (same_type, j))
1818 1049 : continue;
1819 :
1820 3131 : tree s2 = partition_to_var (map, j);
1821 3131 : if (s1 == s2 || (unsigned) var_to_partition (map, s2) != j)
1822 2148 : continue;
1823 :
1824 983 : if (!tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1825 983 : TYPE_SIZE (TREE_TYPE (s2))))
1826 386 : continue;
1827 :
1828 597 : int v2 = SSA_NAME_VERSION (s2);
1829 597 : if (attempt_coalesce (map, graph, v1, v2, debug_file)
1830 597 : && partition_to_var (map, i) != s1)
1831 : break;
1832 : }
1833 : }
1834 :
1835 856 : BITMAP_FREE (same_type);
1836 : }
1837 :
1838 : /* Given an initial var_map MAP, coalesce variables and return a partition map
1839 : with the resulting coalesce. Note that this function is called in either
1840 : live range computation context or out-of-ssa context, indicated by MAP. */
1841 :
1842 : extern void
1843 1477646 : coalesce_ssa_name (var_map map)
1844 : {
1845 1477646 : tree_live_info_p liveinfo;
1846 1477646 : ssa_conflicts *graph;
1847 1477646 : coalesce_list *cl;
1848 1477646 : auto_bitmap used_in_copies;
1849 :
1850 1477646 : bitmap_tree_view (used_in_copies);
1851 1477646 : cl = create_coalesce_list_for_region (map, used_in_copies);
1852 1477646 : if (map->outofssa_p)
1853 1472141 : populate_coalesce_list_for_outofssa (cl, used_in_copies);
1854 1477646 : bitmap_list_view (used_in_copies);
1855 1477646 : if (map->bitint)
1856 5505 : bitmap_ior_into (used_in_copies, map->bitint);
1857 :
1858 1477646 : if (dump_file && (dump_flags & TDF_DETAILS))
1859 115 : dump_var_map (dump_file, map);
1860 :
1861 1477646 : partition_view_bitmap (map, used_in_copies);
1862 :
1863 1477646 : compute_optimized_partition_bases (map, used_in_copies, cl);
1864 :
1865 1477646 : if (num_var_partitions (map) < 1)
1866 : {
1867 183782 : delete_coalesce_list (cl);
1868 183782 : return;
1869 : }
1870 :
1871 1293864 : if (dump_file && (dump_flags & TDF_DETAILS))
1872 64 : dump_var_map (dump_file, map);
1873 :
1874 1293864 : liveinfo = calculate_live_ranges (map, false);
1875 :
1876 1293864 : if (dump_file && (dump_flags & TDF_DETAILS))
1877 64 : dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1878 :
1879 : /* Build a conflict graph. */
1880 1293864 : graph = build_ssa_conflict_graph (liveinfo);
1881 1293864 : delete_tree_live_info (liveinfo);
1882 1293864 : if (dump_file && (dump_flags & TDF_DETAILS))
1883 64 : ssa_conflicts_dump (dump_file, graph);
1884 :
1885 1293864 : sort_coalesce_list (cl, graph, map);
1886 :
1887 1293864 : if (dump_file && (dump_flags & TDF_DETAILS))
1888 : {
1889 64 : fprintf (dump_file, "\nAfter sorting:\n");
1890 64 : dump_coalesce_list (dump_file, cl);
1891 : }
1892 :
1893 : /* First, coalesce all live on entry variables to their base variable.
1894 : This will ensure the first use is coming from the correct location. */
1895 :
1896 1293864 : if (dump_file && (dump_flags & TDF_DETAILS))
1897 64 : dump_var_map (dump_file, map);
1898 :
1899 : /* Now coalesce everything in the list. */
1900 1293864 : coalesce_partitions (map, graph, cl,
1901 1293864 : ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1902 :
1903 1293864 : delete_coalesce_list (cl);
1904 :
1905 1293864 : if (map->bitint && flag_tree_coalesce_vars)
1906 2647 : coalesce_bitint (map, graph);
1907 :
1908 1293864 : ssa_conflicts_delete (graph);
1909 1477646 : }
|
