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 8908495 : coalesce_pair_hasher::hash (const coalesce_pair *pair)
103 : {
104 8908495 : hashval_t a = (hashval_t)(pair->first_element);
105 8908495 : hashval_t b = (hashval_t)(pair->second_element);
106 :
107 2041931 : 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 2861216 : coalesce_pair_hasher::equal (const coalesce_pair *p1, const coalesce_pair *p2)
115 : {
116 2861216 : return (p1->first_element == p2->first_element
117 2861216 : && 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 6558424 : coalesce_cost (int frequency, bool optimize_for_size)
150 : {
151 : /* Base costs on BB frequencies bounded by 1. */
152 6558424 : int cost = frequency;
153 :
154 6558424 : if (!cost)
155 582888 : cost = 1;
156 :
157 6552219 : if (optimize_for_size)
158 825844 : cost = 1;
159 :
160 6558424 : return cost;
161 : }
162 :
163 :
164 : /* Return the cost of executing a copy instruction in basic block BB. */
165 :
166 : static inline int
167 768589 : coalesce_cost_bb (basic_block bb)
168 : {
169 768589 : return coalesce_cost (bb->count.to_frequency (cfun),
170 768589 : 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 5783630 : coalesce_cost_edge (edge e)
178 : {
179 5783630 : int mult = 1;
180 :
181 : /* Inserting copy on critical edge costs more than inserting it elsewhere. */
182 5783630 : if (EDGE_CRITICAL_P (e))
183 : mult = 2;
184 5783630 : if (e->flags & EDGE_ABNORMAL)
185 : return MUST_COALESCE_COST;
186 5783630 : if (e->flags & EDGE_EH)
187 : {
188 40065 : edge e2;
189 40065 : edge_iterator ei;
190 127565 : FOR_EACH_EDGE (e2, ei, e->dest->preds)
191 122514 : 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 111703 : if (mult < 2)
197 : 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 111703 : if (e2->flags & EDGE_EH)
202 : {
203 : mult = 5;
204 : break;
205 : }
206 : }
207 : }
208 :
209 5783630 : return coalesce_cost (EDGE_FREQUENCY (e),
210 11567260 : 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 1610741 : pop_cost_one_pair (coalesce_list *cl, int *p1, int *p2)
220 : {
221 1610741 : cost_one_pair *ptr;
222 :
223 1610741 : ptr = cl->cost_one_list;
224 1610741 : if (!ptr)
225 : return NO_BEST_COALESCE;
226 :
227 281424 : *p1 = ptr->first_element;
228 281424 : *p2 = ptr->second_element;
229 281424 : cl->cost_one_list = ptr->next;
230 :
231 281424 : 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 7808862 : pop_best_coalesce (coalesce_list *cl, int *p1, int *p2)
240 : {
241 7808862 : coalesce_pair *node;
242 7808862 : int ret;
243 :
244 7808862 : if (cl->sorted == NULL)
245 613100 : return pop_cost_one_pair (cl, p1, p2);
246 :
247 7195762 : if (cl->num_sorted == 0)
248 997641 : return pop_cost_one_pair (cl, p1, p2);
249 :
250 6198121 : node = cl->sorted[--(cl->num_sorted)];
251 6198121 : *p1 = node->first_element;
252 6198121 : *p2 = node->second_element;
253 6198121 : ret = node->cost;
254 :
255 6198121 : return ret;
256 : }
257 :
258 :
259 : /* Create a new empty coalesce list object and return it. */
260 :
261 : static inline coalesce_list *
262 1521587 : create_coalesce_list (void)
263 : {
264 1521587 : coalesce_list *list;
265 1521587 : unsigned size = num_ssa_names * 3;
266 :
267 1521587 : if (size < 40)
268 1521587 : size = 40;
269 :
270 1521587 : list = (coalesce_list *) xmalloc (sizeof (struct coalesce_list));
271 1521587 : list->list = new coalesce_table_type (size);
272 1521587 : list->sorted = NULL;
273 1521587 : list->num_sorted = 0;
274 1521587 : list->cost_one_list = NULL;
275 1521587 : gcc_obstack_init (&list->ob);
276 1521587 : return list;
277 : }
278 :
279 :
280 : /* Delete coalesce list CL. */
281 :
282 : static inline void
283 1521587 : delete_coalesce_list (coalesce_list *cl)
284 : {
285 1521587 : gcc_assert (cl->cost_one_list == NULL);
286 1521587 : delete cl->list;
287 1521587 : cl->list = NULL;
288 1521587 : free (cl->sorted);
289 1521587 : gcc_assert (cl->num_sorted == 0);
290 1521587 : obstack_free (&cl->ob, NULL);
291 1521587 : free (cl);
292 1521587 : }
293 :
294 : /* Return the number of unique coalesce pairs in CL. */
295 :
296 : static inline int
297 7527438 : num_coalesce_pairs (coalesce_list *cl)
298 : {
299 7527438 : 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 6866564 : find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
308 : {
309 6866564 : struct coalesce_pair p;
310 6866564 : coalesce_pair **slot;
311 6866564 : unsigned int hash;
312 :
313 : /* Normalize so that p1 is the smaller value. */
314 6866564 : if (p2 < p1)
315 : {
316 : p.first_element = p2;
317 : p.second_element = p1;
318 : }
319 : else
320 : {
321 2893143 : p.first_element = p1;
322 2893143 : p.second_element = p2;
323 : }
324 :
325 6866564 : hash = coalesce_pair_hasher::hash (&p);
326 6866564 : slot = cl->list->find_slot_with_hash (&p, hash, create ? INSERT : NO_INSERT);
327 6866564 : if (!slot)
328 : return NULL;
329 :
330 6866564 : if (!*slot)
331 : {
332 6198121 : struct coalesce_pair * pair = XOBNEW (&cl->ob, struct coalesce_pair);
333 6198121 : gcc_assert (cl->sorted == NULL);
334 6198121 : pair->first_element = p.first_element;
335 6198121 : pair->second_element = p.second_element;
336 6198121 : pair->cost = 0;
337 6198121 : pair->index = num_coalesce_pairs (cl);
338 6198121 : pair->conflict_count = 0;
339 6198121 : *slot = pair;
340 : }
341 :
342 6866564 : return (struct coalesce_pair *) *slot;
343 : }
344 :
345 : static inline void
346 281424 : add_cost_one_coalesce (coalesce_list *cl, int p1, int p2)
347 : {
348 281424 : cost_one_pair *pair;
349 :
350 281424 : pair = XOBNEW (&cl->ob, cost_one_pair);
351 281424 : pair->first_element = p1;
352 281424 : pair->second_element = p2;
353 281424 : pair->next = cl->cost_one_list;
354 281424 : cl->cost_one_list = pair;
355 281424 : }
356 :
357 :
358 : /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
359 :
360 : static inline void
361 6876299 : add_coalesce (coalesce_list *cl, int p1, int p2, int value)
362 : {
363 6876299 : coalesce_pair *node;
364 :
365 6876299 : gcc_assert (cl->sorted == NULL);
366 6876299 : if (p1 == p2)
367 : return;
368 :
369 6866564 : 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 6866564 : if (node->cost < MUST_COALESCE_COST - 1)
373 : {
374 6866564 : if (value < MUST_COALESCE_COST - 1)
375 6268075 : node->cost += value;
376 : else
377 598489 : 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 59259297 : initialize_conflict_count (coalesce_pair *p,
388 : ssa_conflicts *conflicts,
389 : var_map map)
390 : {
391 59259297 : int p1 = var_to_partition (map, ssa_name (p->first_element));
392 59259297 : 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 59259297 : if (conflicts->conflicts[p1] && conflicts->conflicts[p2])
398 834023 : p->conflict_count = bitmap_count_unique_bits (conflicts->conflicts[p1],
399 834023 : conflicts->conflicts[p2]);
400 58425274 : else if (conflicts->conflicts[p1])
401 136431 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p1]);
402 58288843 : else if (conflicts->conflicts[p2])
403 143165 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p2]);
404 : else
405 58145678 : p->conflict_count = 0;
406 59259297 : }
407 :
408 :
409 : /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
410 :
411 : static int
412 177253756 : compare_pairs (const void *p1, const void *p2)
413 : {
414 177253756 : coalesce_pair *const *const pp1 = (coalesce_pair *const *) p1;
415 177253756 : coalesce_pair *const *const pp2 = (coalesce_pair *const *) p2;
416 177253756 : int result;
417 :
418 177253756 : 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 177253756 : if (result == 0)
423 : {
424 76700485 : if (flag_expensive_optimizations)
425 : {
426 : /* Lazily initialize the conflict counts as it's fairly expensive
427 : to compute. */
428 42176576 : if ((*pp2)->conflict_count == 0)
429 29795263 : initialize_conflict_count (*pp2, conflicts_, map_);
430 42176576 : if ((*pp1)->conflict_count == 0)
431 29464034 : initialize_conflict_count (*pp1, conflicts_, map_);
432 :
433 42176576 : 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 76700485 : if (result == 0)
439 66049754 : result = (*pp2)->index - (*pp1)->index;
440 : }
441 :
442 177253756 : 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 1329317 : sort_coalesce_list (coalesce_list *cl, ssa_conflicts *conflicts, var_map map)
456 : {
457 1329317 : unsigned x, num;
458 1329317 : coalesce_pair *p;
459 1329317 : coalesce_iterator_type ppi;
460 :
461 1329317 : gcc_assert (cl->sorted == NULL);
462 :
463 1329317 : num = num_coalesce_pairs (cl);
464 1329317 : cl->num_sorted = num;
465 1329317 : if (num == 0)
466 937263 : return;
467 :
468 : /* Allocate a vector for the pair pointers. */
469 722133 : cl->sorted = XNEWVEC (coalesce_pair *, num);
470 :
471 : /* Populate the vector with pointers to the pairs. */
472 722133 : x = 0;
473 6920254 : FOR_EACH_PARTITION_PAIR (p, ppi, cl)
474 6198121 : cl->sorted[x++] = p;
475 722133 : gcc_assert (x == num);
476 :
477 : /* Already sorted. */
478 722133 : 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 392054 : conflicts_ = conflicts;
485 392054 : map_ = map;
486 392054 : qsort (cl->sorted, num, sizeof (coalesce_pair *), compare_pairs);
487 392054 : conflicts_ = NULL;
488 392054 : 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 42 : for (x = cl->num_sorted - 1 ; x >=0; x--)
521 : {
522 28 : node = cl->sorted[x];
523 28 : fprintf (f, "(%d, %d) ", node->cost, node->conflict_count);
524 28 : var = ssa_name (node->first_element);
525 28 : print_generic_expr (f, var, TDF_SLIM);
526 28 : fprintf (f, " <-> ");
527 28 : var = ssa_name (node->second_element);
528 28 : print_generic_expr (f, var, TDF_SLIM);
529 28 : 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 1329317 : ssa_conflicts_new (unsigned size)
539 : {
540 1329317 : ssa_conflicts *ptr;
541 :
542 1329317 : ptr = XNEW (ssa_conflicts);
543 1329317 : bitmap_obstack_initialize (&ptr->obstack);
544 1329317 : ptr->conflicts.create (size);
545 1329317 : ptr->conflicts.safe_grow_cleared (size, true);
546 1329317 : return ptr;
547 : }
548 :
549 :
550 : /* Free storage for conflict graph PTR. */
551 :
552 : static inline void
553 1329317 : ssa_conflicts_delete (ssa_conflicts *ptr)
554 : {
555 1329317 : bitmap_obstack_release (&ptr->obstack);
556 1329317 : ptr->conflicts.release ();
557 1329317 : free (ptr);
558 1329317 : }
559 :
560 :
561 : /* Test if elements X and Y conflict in graph PTR. */
562 :
563 : static inline bool
564 6027794 : ssa_conflicts_test_p (ssa_conflicts *ptr, unsigned x, unsigned y)
565 : {
566 6027794 : bitmap bx = ptr->conflicts[x];
567 6027794 : bitmap by = ptr->conflicts[y];
568 :
569 6027794 : gcc_checking_assert (x != y);
570 :
571 6027794 : if (bx)
572 : /* Avoid the lookup if Y has no conflicts. */
573 1353512 : 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 3317702 : ssa_conflicts_add_one (ssa_conflicts *ptr, unsigned x, unsigned y)
583 : {
584 3317702 : bitmap bx = ptr->conflicts[x];
585 : /* If there are no conflicts yet, allocate the bitmap and set bit. */
586 3317702 : if (! bx)
587 1336906 : bx = ptr->conflicts[x] = BITMAP_ALLOC (&ptr->obstack);
588 3317702 : bitmap_set_bit (bx, y);
589 3317702 : }
590 :
591 :
592 : /* Add conflicts between X and Y in graph PTR. */
593 :
594 : static inline void
595 1658851 : ssa_conflicts_add (ssa_conflicts *ptr, unsigned x, unsigned y)
596 : {
597 1658851 : gcc_checking_assert (x != y);
598 1658851 : ssa_conflicts_add_one (ptr, x, y);
599 1658851 : ssa_conflicts_add_one (ptr, y, x);
600 1658851 : }
601 :
602 :
603 : /* Merge all Y's conflict into X in graph PTR. */
604 :
605 : static inline void
606 5506872 : ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y)
607 : {
608 5506872 : unsigned z;
609 5506872 : bitmap_iterator bi;
610 5506872 : bitmap bx = ptr->conflicts[x];
611 5506872 : bitmap by = ptr->conflicts[y];
612 :
613 5506872 : gcc_checking_assert (x != y);
614 5506872 : if (! by)
615 4763349 : 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 2602332 : EXECUTE_IF_SET_IN_BITMAP (by, 0, z, bi)
621 : {
622 1858809 : bitmap bz = ptr->conflicts[z];
623 1858809 : if (bz)
624 : {
625 1858809 : bool was_there = bitmap_clear_bit (bz, y);
626 1858809 : gcc_checking_assert (was_there);
627 1858809 : bitmap_set_bit (bz, x);
628 : }
629 : }
630 :
631 743523 : if (bx)
632 : {
633 : /* If X has conflicts, add Y's to X. */
634 629377 : bitmap_ior_into (bx, by);
635 629377 : BITMAP_FREE (by);
636 629377 : ptr->conflicts[y] = NULL;
637 : }
638 : else
639 : {
640 : /* If X has no conflicts, simply use Y's. */
641 114146 : ptr->conflicts[x] = by;
642 114146 : 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 243 : FOR_EACH_VEC_ELT (ptr->conflicts, x, b)
658 115 : 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 1329317 : new_live_track (var_map map)
693 : {
694 1329317 : live_track *ptr;
695 1329317 : int lim, x;
696 :
697 : /* Make sure there is a partition view in place. */
698 1329317 : gcc_assert (map->partition_to_base_index != NULL);
699 :
700 1329317 : ptr = XNEW (live_track);
701 1329317 : ptr->map = map;
702 1329317 : lim = num_basevars (map);
703 1329317 : bitmap_obstack_initialize (&ptr->obstack);
704 1329317 : ptr->live_base_partitions = XNEWVEC (bitmap_head, lim);
705 1329317 : bitmap_initialize (&ptr->live_base_var, &ptr->obstack);
706 6944739 : for (x = 0; x < lim; x++)
707 5615422 : bitmap_initialize (&ptr->live_base_partitions[x], &ptr->obstack);
708 1329317 : return ptr;
709 : }
710 :
711 :
712 : /* This routine will free the memory associated with PTR. */
713 :
714 : static void
715 1329317 : delete_live_track (live_track *ptr)
716 : {
717 1329317 : bitmap_obstack_release (&ptr->obstack);
718 1329317 : XDELETEVEC (ptr->live_base_partitions);
719 1329317 : XDELETE (ptr);
720 1329317 : }
721 :
722 :
723 : /* This function will remove PARTITION from the live list in PTR. */
724 :
725 : static inline void
726 11131963 : live_track_remove_partition (live_track *ptr, int partition)
727 : {
728 11131963 : int root;
729 :
730 11131963 : root = basevar_index (ptr->map, partition);
731 11131963 : bitmap_clear_bit (&ptr->live_base_partitions[root], partition);
732 : /* If the element list is empty, make the base variable not live either. */
733 11131963 : if (bitmap_empty_p (&ptr->live_base_partitions[root]))
734 9743758 : bitmap_clear_bit (&ptr->live_base_var, root);
735 11131963 : }
736 :
737 :
738 : /* This function will adds PARTITION to the live list in PTR. */
739 :
740 : static inline void
741 47527828 : live_track_add_partition (live_track *ptr, int partition)
742 : {
743 47527828 : int root;
744 :
745 47527828 : 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 47527828 : if (bitmap_set_bit (&ptr->live_base_var, root))
749 35144348 : bitmap_clear (&ptr->live_base_partitions[root]);
750 47527828 : bitmap_set_bit (&ptr->live_base_partitions[root], partition);
751 :
752 47527828 : }
753 :
754 :
755 : /* Clear the live bit for VAR in PTR. */
756 :
757 : static inline void
758 718624 : live_track_clear_var (live_track *ptr, tree var)
759 : {
760 718624 : int p;
761 :
762 718624 : p = var_to_partition (ptr->map, var);
763 718624 : if (p != NO_PARTITION)
764 618084 : live_track_remove_partition (ptr, p);
765 718624 : }
766 :
767 :
768 : /* Return TRUE if VAR is live in PTR. */
769 :
770 : static inline bool
771 2956402 : live_track_live_p (live_track *ptr, tree var)
772 : {
773 2956402 : int p, root;
774 :
775 2956402 : p = var_to_partition (ptr->map, var);
776 2956402 : if (p != NO_PARTITION)
777 : {
778 2916264 : root = basevar_index (ptr->map, p);
779 2916264 : if (bitmap_bit_p (&ptr->live_base_var, root))
780 2916264 : 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 42000311 : live_track_process_use (live_track *ptr, tree use)
791 : {
792 42000311 : int p;
793 :
794 42000311 : p = var_to_partition (ptr->map, use);
795 42000311 : if (p == NO_PARTITION)
796 : return;
797 :
798 : /* Mark as live in the appropriate live list. */
799 16780142 : 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 29531435 : live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph)
809 : {
810 29531435 : int p, root;
811 29531435 : bitmap b;
812 29531435 : unsigned x;
813 29531435 : bitmap_iterator bi;
814 :
815 29531435 : p = var_to_partition (ptr->map, def);
816 29531435 : if (p == NO_PARTITION)
817 19017556 : return;
818 :
819 : /* Clear the liveness bit. */
820 10513879 : live_track_remove_partition (ptr, p);
821 :
822 : /* If the bitmap isn't empty now, conflicts need to be added. */
823 10513879 : root = basevar_index (ptr->map, p);
824 10513879 : if (bitmap_bit_p (&ptr->live_base_var, root))
825 : {
826 987544 : b = &ptr->live_base_partitions[root];
827 2646395 : EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
828 1658851 : 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 12120512 : live_track_init (live_track *ptr, bitmap init)
837 : {
838 12120512 : unsigned p;
839 12120512 : bitmap_iterator bi;
840 :
841 : /* Mark all live on exit partitions. */
842 42868198 : EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
843 30747686 : live_track_add_partition (ptr, p);
844 12120512 : }
845 :
846 :
847 : /* This routine will clear all live partitions in PTR. */
848 :
849 : static inline void
850 12120512 : 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 12120512 : 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 1329317 : build_ssa_conflict_graph (tree_live_info_p liveinfo)
866 : {
867 1329317 : ssa_conflicts *graph;
868 1329317 : var_map map;
869 1329317 : basic_block bb;
870 1329317 : ssa_op_iter iter;
871 1329317 : live_track *live;
872 1329317 : 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 1329317 : if (flag_tree_coalesce_vars)
879 948676 : entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
880 : else
881 : entry = NULL;
882 :
883 1329317 : map = live_var_map (liveinfo);
884 1329317 : graph = ssa_conflicts_new (num_var_partitions (map));
885 :
886 1329317 : live = new_live_track (map);
887 :
888 14779146 : for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
889 : {
890 : /* Start with live on exit temporaries. */
891 12120512 : live_track_init (live, live_on_exit (liveinfo, bb));
892 :
893 120579699 : for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
894 108117525 : gsi_prev (&gsi))
895 : {
896 96338675 : tree var;
897 96338675 : gimple *stmt = gsi_stmt (gsi);
898 :
899 96338675 : if (is_gimple_debug (stmt))
900 52209263 : continue;
901 :
902 44129412 : if (map->bitint)
903 : {
904 84248 : 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 84248 : 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 44045164 : if (is_gimple_assign (stmt))
919 : {
920 30412198 : tree lhs = gimple_assign_lhs (stmt);
921 30412198 : tree rhs1 = gimple_assign_rhs1 (stmt);
922 30412198 : if (gimple_assign_copy_p (stmt)
923 8278684 : && TREE_CODE (lhs) == SSA_NAME
924 31677078 : && TREE_CODE (rhs1) == SSA_NAME)
925 718579 : 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 44045164 : bool first = true;
939 67909759 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
940 23864595 : if (first)
941 : first = false;
942 : else
943 18466 : live_track_process_use (live, var);
944 :
945 67909759 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
946 23864595 : live_track_process_def (live, var, graph);
947 :
948 83277958 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
949 39232794 : 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 15082619 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
959 2962107 : gsi_next (&gsi))
960 : {
961 2962107 : gphi *phi = gsi.phi ();
962 2962107 : tree result = PHI_RESULT (phi);
963 5924214 : if (virtual_operand_p (result))
964 5705 : continue;
965 2956402 : if (live_track_live_p (live, result))
966 2916264 : 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 12120512 : if (bb == entry)
977 : {
978 : unsigned i;
979 : tree var;
980 :
981 56296577 : FOR_EACH_SSA_NAME (i, var, cfun)
982 : {
983 34406489 : if (!SSA_NAME_IS_DEFAULT_DEF (var)
984 3951501 : || !SSA_NAME_VAR (var)
985 38357990 : || VAR_P (SSA_NAME_VAR (var)))
986 31693582 : continue;
987 :
988 2712907 : 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 2712907 : live_track_process_use (live, var);
993 : }
994 : }
995 :
996 12120512 : live_track_clear_base_vars (live);
997 : }
998 :
999 1329317 : delete_live_track (live);
1000 1329317 : 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 32394458 : coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
1024 : {
1025 32394458 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1026 28390192 : || !SSA_NAME_VAR (var)
1027 39259689 : || VAR_P (SSA_NAME_VAR (var)))
1028 : return;
1029 :
1030 158033 : tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var));
1031 158033 : if (!has_zero_uses (ssa))
1032 : return;
1033 :
1034 810 : add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var));
1035 810 : 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 1521587 : create_coalesce_list_for_region (var_map map, bitmap used_in_copy)
1047 : {
1048 1521587 : gimple_stmt_iterator gsi;
1049 1521587 : basic_block bb;
1050 1521587 : coalesce_list *cl = create_coalesce_list ();
1051 1521587 : gimple *stmt;
1052 1521587 : int v1, v2, cost;
1053 :
1054 15974608 : for (unsigned j = 0; map->vec_bbs.iterate (j, &bb); ++j)
1055 : {
1056 12931434 : tree arg;
1057 :
1058 12931434 : for (gphi_iterator gpi = gsi_start_phis (bb);
1059 15894813 : !gsi_end_p (gpi);
1060 2963379 : gsi_next (&gpi))
1061 : {
1062 2963379 : gphi *phi = gpi.phi ();
1063 2963379 : size_t i;
1064 2963379 : int ver;
1065 2963379 : tree res;
1066 2963379 : bool saw_copy = false;
1067 :
1068 2963379 : res = gimple_phi_result (phi);
1069 5926758 : if (virtual_operand_p (res))
1070 6108 : continue;
1071 2957271 : ver = SSA_NAME_VERSION (res);
1072 2957271 : if (map->bitint && !bitmap_bit_p (map->bitint, ver))
1073 767 : continue;
1074 :
1075 : /* Register ssa_names and coalesces between the args and the result
1076 : of all PHI. */
1077 10215863 : for (i = 0; i < gimple_phi_num_args (phi); i++)
1078 : {
1079 7259359 : edge e = gimple_phi_arg_edge (phi, i);
1080 7259359 : arg = PHI_ARG_DEF (phi, i);
1081 7259359 : if (TREE_CODE (arg) != SSA_NAME)
1082 1280746 : continue;
1083 :
1084 5978613 : if (gimple_can_coalesce_p (arg, res)
1085 5978613 : || (e->flags & EDGE_ABNORMAL))
1086 : {
1087 5978297 : saw_copy = true;
1088 5978297 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1089 5978297 : if ((e->flags & EDGE_ABNORMAL) == 0)
1090 : {
1091 5783630 : int cost = coalesce_cost_edge (e);
1092 5783630 : if (cost == 1 && has_single_use (arg))
1093 280614 : add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1094 : else
1095 5503016 : add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1096 : }
1097 : }
1098 : }
1099 2956504 : if (saw_copy)
1100 2882661 : bitmap_set_bit (used_in_copy, ver);
1101 : }
1102 :
1103 127737106 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1104 : {
1105 101874238 : stmt = gsi_stmt (gsi);
1106 :
1107 101874238 : if (is_gimple_debug (stmt))
1108 53912440 : continue;
1109 :
1110 : /* Check for copy coalesces. */
1111 47961798 : switch (gimple_code (stmt))
1112 : {
1113 32779807 : case GIMPLE_ASSIGN:
1114 32779807 : {
1115 32779807 : tree lhs = gimple_assign_lhs (stmt);
1116 32779807 : tree rhs1 = gimple_assign_rhs1 (stmt);
1117 32779807 : if (gimple_assign_ssa_name_copy_p (stmt)
1118 32779807 : && gimple_can_coalesce_p (lhs, rhs1))
1119 : {
1120 383663 : v1 = SSA_NAME_VERSION (lhs);
1121 383663 : v2 = SSA_NAME_VERSION (rhs1);
1122 383663 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1123 : break;
1124 383588 : cost = coalesce_cost_bb (bb);
1125 383588 : add_coalesce (cl, v1, v2, cost);
1126 383588 : bitmap_set_bit (used_in_copy, v1);
1127 383588 : bitmap_set_bit (used_in_copy, v2);
1128 : }
1129 : }
1130 : break;
1131 :
1132 1488868 : case GIMPLE_RETURN:
1133 1488868 : {
1134 1488868 : tree res = DECL_RESULT (current_function_decl);
1135 1488868 : if (VOID_TYPE_P (TREE_TYPE (res))
1136 1488868 : || !is_gimple_reg (res))
1137 : break;
1138 677440 : tree rhs1 = gimple_return_retval (as_a <greturn *> (stmt));
1139 677440 : if (!rhs1)
1140 : break;
1141 672223 : tree lhs = ssa_default_def (cfun, res);
1142 672223 : if (map->bitint && !lhs)
1143 : break;
1144 671645 : gcc_assert (lhs);
1145 671645 : if (TREE_CODE (rhs1) == SSA_NAME
1146 671645 : && gimple_can_coalesce_p (lhs, rhs1))
1147 : {
1148 385001 : v1 = SSA_NAME_VERSION (lhs);
1149 385001 : v2 = SSA_NAME_VERSION (rhs1);
1150 385001 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1151 : break;
1152 385001 : cost = coalesce_cost_bb (bb);
1153 385001 : add_coalesce (cl, v1, v2, cost);
1154 385001 : bitmap_set_bit (used_in_copy, v1);
1155 385001 : bitmap_set_bit (used_in_copy, v2);
1156 : }
1157 : break;
1158 : }
1159 :
1160 96583 : case GIMPLE_ASM:
1161 96583 : {
1162 96583 : gasm *asm_stmt = as_a <gasm *> (stmt);
1163 96583 : unsigned long noutputs, i;
1164 96583 : unsigned long ninputs;
1165 96583 : tree *outputs, link;
1166 96583 : noutputs = gimple_asm_noutputs (asm_stmt);
1167 96583 : ninputs = gimple_asm_ninputs (asm_stmt);
1168 96583 : outputs = (tree *) alloca (noutputs * sizeof (tree));
1169 176536 : for (i = 0; i < noutputs; ++i)
1170 : {
1171 79953 : link = gimple_asm_output_op (asm_stmt, i);
1172 79953 : outputs[i] = TREE_VALUE (link);
1173 : }
1174 :
1175 155556 : for (i = 0; i < ninputs; ++i)
1176 : {
1177 58973 : const char *constraint;
1178 58973 : tree input;
1179 58973 : char *end;
1180 58973 : unsigned long match;
1181 :
1182 58973 : link = gimple_asm_input_op (asm_stmt, i);
1183 58973 : constraint
1184 58973 : = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1185 58973 : input = TREE_VALUE (link);
1186 :
1187 58973 : if (TREE_CODE (input) != SSA_NAME)
1188 52358 : continue;
1189 :
1190 16457 : match = strtoul (constraint, &end, 10);
1191 16457 : if (match >= noutputs || end == constraint)
1192 8151 : continue;
1193 :
1194 8306 : if (TREE_CODE (outputs[match]) != SSA_NAME)
1195 1691 : continue;
1196 :
1197 6615 : v1 = SSA_NAME_VERSION (outputs[match]);
1198 6615 : v2 = SSA_NAME_VERSION (input);
1199 6615 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1200 0 : continue;
1201 :
1202 6615 : if (gimple_can_coalesce_p (outputs[match], input))
1203 : {
1204 6205 : cost = coalesce_cost (REG_BR_PROB_BASE,
1205 6205 : optimize_bb_for_size_p (bb));
1206 6205 : add_coalesce (cl, v1, v2, cost);
1207 6205 : bitmap_set_bit (used_in_copy, v1);
1208 6205 : bitmap_set_bit (used_in_copy, v2);
1209 : }
1210 : }
1211 : break;
1212 : }
1213 :
1214 : default:
1215 : break;
1216 : }
1217 : }
1218 : }
1219 :
1220 1521587 : 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 7154285 : ssa_name_var_hash::hash (const_tree n)
1234 : {
1235 7154285 : return DECL_UID (SSA_NAME_VAR (n));
1236 : }
1237 :
1238 : inline int
1239 5410637 : ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
1240 : {
1241 10821274 : 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 1515899 : populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy)
1250 : {
1251 1515899 : tree var;
1252 1515899 : tree first;
1253 1515899 : int v1, v2, cost;
1254 1515899 : unsigned i;
1255 :
1256 : /* Process result decls and live on entry variables for entry into the
1257 : coalesce list. */
1258 1515899 : first = NULL_TREE;
1259 75119372 : FOR_EACH_SSA_NAME (i, var, cfun)
1260 : {
1261 99830132 : if (!virtual_operand_p (var))
1262 : {
1263 32394458 : coalesce_with_default (var, cl, used_in_copy);
1264 :
1265 : /* Add coalesces between all the result decls. */
1266 32394458 : if (SSA_NAME_VAR (var)
1267 10869497 : && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1268 : {
1269 689282 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1270 689282 : 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 32394458 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1285 32394458 : && (!has_zero_uses (var)
1286 1926665 : || (SSA_NAME_VAR (var)
1287 1926665 : && !VAR_P (SSA_NAME_VAR (var)))))
1288 3750608 : 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 1515899 : if (!flag_tree_coalesce_vars)
1296 : {
1297 453278 : tree a;
1298 453278 : hash_table<ssa_name_var_hash> ssa_name_hash (10);
1299 :
1300 14820645 : FOR_EACH_SSA_NAME (i, a, cfun)
1301 : {
1302 12979359 : if (SSA_NAME_VAR (a)
1303 6788668 : && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1304 1848598 : && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
1305 251149 : || !VAR_P (SSA_NAME_VAR (a))))
1306 : {
1307 1848567 : tree *slot = ssa_name_hash.find_slot (a, INSERT);
1308 :
1309 1848567 : if (!*slot)
1310 1250078 : *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 598489 : const int cost
1322 686477 : = (VAR_P (SSA_NAME_VAR (a)) || in_lto_p)
1323 598489 : ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
1324 1196978 : add_coalesce (cl, SSA_NAME_VERSION (a),
1325 598489 : SSA_NAME_VERSION (*slot), cost);
1326 598489 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a));
1327 598489 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot));
1328 : }
1329 : }
1330 : }
1331 453278 : }
1332 1515899 : }
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 6678961 : attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y,
1341 : FILE *debug)
1342 : {
1343 6678961 : int z;
1344 6678961 : tree var1, var2;
1345 6678961 : int p1, p2;
1346 :
1347 6678961 : p1 = var_to_partition (map, ssa_name (x));
1348 6678961 : p2 = var_to_partition (map, ssa_name (y));
1349 :
1350 6678961 : if (debug)
1351 : {
1352 28 : fprintf (debug, "(%d)", x);
1353 28 : print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1354 28 : fprintf (debug, " & (%d)", y);
1355 28 : print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1356 : }
1357 :
1358 6678961 : if (p1 == p2)
1359 : {
1360 651167 : if (debug)
1361 0 : fprintf (debug, ": Already Coalesced.\n");
1362 : return true;
1363 : }
1364 :
1365 6027794 : if (debug)
1366 28 : fprintf (debug, " [map: %d, %d] ", p1, p2);
1367 :
1368 :
1369 6027794 : if (!ssa_conflicts_test_p (graph, p1, p2))
1370 : {
1371 5506872 : var1 = partition_to_var (map, p1);
1372 5506872 : var2 = partition_to_var (map, p2);
1373 :
1374 5506872 : z = var_union (map, var1, var2);
1375 5506872 : if (z == NO_PARTITION)
1376 : {
1377 0 : if (debug)
1378 0 : fprintf (debug, ": Unable to perform partition union.\n");
1379 : return false;
1380 : }
1381 :
1382 : /* z is the new combined partition. Remove the other partition from
1383 : the list, and merge the conflicts. */
1384 5506872 : if (z == p1)
1385 4632783 : ssa_conflicts_merge (graph, p1, p2);
1386 : else
1387 874089 : ssa_conflicts_merge (graph, p2, p1);
1388 :
1389 5506872 : if (debug)
1390 28 : fprintf (debug, ": Success -> %d\n", z);
1391 :
1392 : return true;
1393 : }
1394 :
1395 520922 : 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 1329317 : coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
1407 : FILE *debug)
1408 : {
1409 1329317 : int x = 0, y = 0;
1410 1329317 : tree var1, var2;
1411 1329317 : int cost;
1412 1329317 : basic_block bb;
1413 1329317 : edge e;
1414 1329317 : 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 13449829 : FOR_EACH_BB_FN (bb, cfun)
1421 : {
1422 29735480 : FOR_EACH_EDGE (e, ei, bb->preds)
1423 17614968 : if (e->flags & EDGE_ABNORMAL)
1424 : {
1425 8730 : gphi_iterator gsi;
1426 203533 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1427 194803 : gsi_next (&gsi))
1428 : {
1429 194803 : gphi *phi = gsi.phi ();
1430 194803 : tree res = PHI_RESULT (phi);
1431 389606 : if (virtual_operand_p (res))
1432 108 : continue;
1433 194695 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1434 194695 : if (SSA_NAME_IS_DEFAULT_DEF (arg)
1435 194695 : && (!SSA_NAME_VAR (arg)
1436 935 : || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1437 830 : continue;
1438 :
1439 193865 : int v1 = SSA_NAME_VERSION (res);
1440 193865 : int v2 = SSA_NAME_VERSION (arg);
1441 :
1442 193865 : if (debug)
1443 0 : fprintf (debug, "Abnormal coalesce: ");
1444 :
1445 193865 : 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 7808862 : while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1454 : {
1455 6479545 : var1 = ssa_name (x);
1456 6479545 : var2 = ssa_name (y);
1457 :
1458 : /* Assert the coalesces have the same base variable. */
1459 6479545 : gcc_assert (gimple_can_coalesce_p (var1, var2));
1460 :
1461 6479545 : if (debug)
1462 28 : fprintf (debug, "Coalesce list: ");
1463 6479545 : attempt_coalesce (map, graph, x, y, debug);
1464 : }
1465 1329317 : }
1466 :
1467 :
1468 : /* Output partition map MAP with coalescing plan PART to file F. */
1469 :
1470 : void
1471 111 : dump_part_var_map (FILE *f, partition part, var_map map)
1472 : {
1473 111 : int t;
1474 111 : unsigned x, y;
1475 111 : int p;
1476 :
1477 111 : fprintf (f, "\nCoalescible Partition map \n\n");
1478 :
1479 337 : for (x = 0; x < map->num_partitions; x++)
1480 : {
1481 115 : if (map->view_to_partition != NULL)
1482 115 : p = map->view_to_partition[x];
1483 : else
1484 0 : p = x;
1485 :
1486 115 : if (ssa_name (p) == NULL_TREE
1487 230 : || virtual_operand_p (ssa_name (p)))
1488 0 : continue;
1489 :
1490 : t = 0;
1491 1510 : for (y = 1; y < num_ssa_names; y++)
1492 : {
1493 1395 : tree var = version_to_var (map, y);
1494 1395 : if (!var)
1495 988 : continue;
1496 407 : int q = var_to_partition (map, var);
1497 407 : p = partition_find (part, q);
1498 407 : gcc_assert (map->partition_to_base_index[q]
1499 : == map->partition_to_base_index[p]);
1500 :
1501 407 : if (p == (int)x)
1502 : {
1503 115 : if (t++ == 0)
1504 : {
1505 87 : fprintf (f, "Partition %d, base %d (", x,
1506 : map->partition_to_base_index[q]);
1507 87 : print_generic_expr (f, partition_to_var (map, q), TDF_SLIM);
1508 87 : fprintf (f, " - ");
1509 : }
1510 115 : fprintf (f, "%d ", y);
1511 : }
1512 : }
1513 115 : if (t != 0)
1514 87 : fprintf (f, ")\n");
1515 : }
1516 111 : fprintf (f, "\n");
1517 111 : }
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 25057275 : 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 25057275 : tree var1 = SSA_NAME_VAR (name1);
1532 25057275 : tree var2 = SSA_NAME_VAR (name2);
1533 25057275 : var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
1534 25057275 : var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
1535 25057275 : 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 24547898 : tree t1 = TREE_TYPE (name1);
1541 24547898 : tree t2 = TREE_TYPE (name2);
1542 24547898 : if (t1 == t2)
1543 : {
1544 22506895 : check_modes:
1545 : /* If the base variables are the same, we're good: none of the
1546 : other tests below could possibly fail. */
1547 23959296 : var1 = SSA_NAME_VAR (name1);
1548 23959296 : var2 = SSA_NAME_VAR (name2);
1549 23959296 : 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 4553692 : bool reg1 = use_register_for_decl (name1);
1560 4553692 : bool reg2 = use_register_for_decl (name2);
1561 4553692 : 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 4553647 : int unsigned1, unsigned2;
1571 4553647 : return ((!var1 || VAR_P (var1)) && (!var2 || VAR_P (var2)))
1572 6383103 : || ((promote_ssa_mode (name1, &unsigned1)
1573 914728 : == promote_ssa_mode (name2, &unsigned2))
1574 914728 : && unsigned1 == unsigned2);
1575 : }
1576 :
1577 : /* If alignment requirements are different, we can't coalesce. */
1578 4082006 : if (MINIMUM_ALIGNMENT (t1,
1579 : var1 ? DECL_MODE (var1) : TYPE_MODE (t1),
1580 : var1 ? LOCAL_DECL_ALIGNMENT (var1) : TYPE_ALIGN (t1))
1581 2041003 : != 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 1599348 : if (types_compatible_p (t1, t2))
1590 1452401 : 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 1521587 : compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1602 : coalesce_list *cl)
1603 : {
1604 1521587 : int parts = num_var_partitions (map);
1605 1521587 : 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 1521587 : gcc_assert (!cl->sorted);
1611 1521587 : coalesce_pair *node;
1612 1521587 : coalesce_iterator_type ppi;
1613 7719708 : FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1614 : {
1615 6198121 : tree v1 = ssa_name (node->first_element);
1616 6198121 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1617 6198121 : tree v2 = ssa_name (node->second_element);
1618 6198121 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1619 :
1620 6198121 : if (p1 == p2)
1621 525492 : continue;
1622 :
1623 5672629 : partition_union (tentative, p1, p2);
1624 : }
1625 :
1626 : /* We have to deal with cost one pairs too. */
1627 1803011 : for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1628 : {
1629 281424 : tree v1 = ssa_name (co->first_element);
1630 281424 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1631 281424 : tree v2 = ssa_name (co->second_element);
1632 281424 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1633 :
1634 281424 : if (p1 == p2)
1635 18461 : continue;
1636 :
1637 262963 : partition_union (tentative, p1, p2);
1638 : }
1639 :
1640 : /* And also with abnormal edges. */
1641 1521587 : basic_block bb;
1642 1521587 : edge e;
1643 1521587 : unsigned i;
1644 1521587 : edge_iterator ei;
1645 14453021 : for (i = 0; map->vec_bbs.iterate (i, &bb); ++i)
1646 : {
1647 31602525 : FOR_EACH_EDGE (e, ei, bb->preds)
1648 18671091 : if (e->flags & EDGE_ABNORMAL)
1649 : {
1650 10427 : gphi_iterator gsi;
1651 205230 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1652 194803 : gsi_next (&gsi))
1653 : {
1654 194803 : gphi *phi = gsi.phi ();
1655 194803 : tree res = PHI_RESULT (phi);
1656 389606 : if (virtual_operand_p (res))
1657 108 : continue;
1658 194695 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1659 194695 : if (SSA_NAME_IS_DEFAULT_DEF (arg)
1660 194695 : && (!SSA_NAME_VAR (arg)
1661 935 : || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1662 830 : continue;
1663 :
1664 193865 : int p1 = partition_find (tentative, var_to_partition (map, res));
1665 193865 : int p2 = partition_find (tentative, var_to_partition (map, arg));
1666 :
1667 193865 : if (p1 == p2)
1668 192376 : continue;
1669 :
1670 1489 : partition_union (tentative, p1, p2);
1671 : }
1672 : }
1673 : }
1674 :
1675 1521587 : if (map->bitint
1676 5688 : && flag_tree_coalesce_vars
1677 2916 : && (optimize > 1 || parts < 500))
1678 11041 : for (i = 0; i < (unsigned) parts; ++i)
1679 : {
1680 8125 : tree s1 = partition_to_var (map, i);
1681 8125 : int p1 = partition_find (tentative, i);
1682 37148 : for (unsigned j = i + 1; j < (unsigned) parts; ++j)
1683 : {
1684 29041 : tree s2 = partition_to_var (map, j);
1685 29041 : if (s1 == s2)
1686 0 : continue;
1687 29041 : if (tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1688 29041 : TYPE_SIZE (TREE_TYPE (s2))))
1689 : {
1690 22813 : int p2 = partition_find (tentative, j);
1691 :
1692 22813 : if (p1 == p2)
1693 17880 : continue;
1694 :
1695 4933 : partition_union (tentative, p1, p2);
1696 4933 : if (partition_find (tentative, i) != p1)
1697 : break;
1698 : }
1699 : }
1700 : }
1701 :
1702 1521587 : map->partition_to_base_index = XCNEWVEC (int, parts);
1703 1521587 : auto_vec<unsigned int> index_map (parts);
1704 1521587 : if (parts)
1705 1329317 : index_map.quick_grow (parts);
1706 :
1707 1521587 : const unsigned no_part = -1;
1708 1521587 : unsigned count = parts;
1709 13079023 : while (count)
1710 11557436 : 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 1521587 : bitmap_iterator bi;
1718 13079023 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1719 : {
1720 11557436 : int pidx = var_to_partition (map, ssa_name (i));
1721 11557436 : int base = partition_find (tentative, pidx);
1722 11557436 : if (index_map[base] != no_part)
1723 5942014 : continue;
1724 5615422 : index_map[base] = count++;
1725 : }
1726 :
1727 1521587 : map->num_basevars = count;
1728 :
1729 13079023 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1730 : {
1731 11557436 : int pidx = var_to_partition (map, ssa_name (i));
1732 11557436 : int base = partition_find (tentative, pidx);
1733 11557436 : gcc_assert (index_map[base] < count);
1734 11557436 : map->partition_to_base_index[pidx] = index_map[base];
1735 : }
1736 :
1737 1521587 : if (dump_file && (dump_flags & TDF_DETAILS))
1738 111 : dump_part_var_map (dump_file, tentative, map);
1739 :
1740 1521587 : partition_delete (tentative);
1741 1521587 : }
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 2771 : coalesce_bitint (var_map map, ssa_conflicts *graph)
1752 : {
1753 2771 : unsigned n = num_var_partitions (map);
1754 2771 : if (optimize <= 1 && n > 500)
1755 1890 : return;
1756 :
1757 2771 : bool try_same_size = false;
1758 2771 : FILE *debug_file = (dump_flags & TDF_DETAILS) ? dump_file : NULL;
1759 10896 : for (unsigned i = 0; i < n; ++i)
1760 : {
1761 8125 : tree s1 = partition_to_var (map, i);
1762 8125 : if ((unsigned) var_to_partition (map, s1) != i)
1763 2744 : continue;
1764 5381 : int v1 = SSA_NAME_VERSION (s1);
1765 16708 : for (unsigned j = i + 1; j < n; ++j)
1766 : {
1767 11335 : tree s2 = partition_to_var (map, j);
1768 11335 : if (s1 == s2 || (unsigned) var_to_partition (map, s2) != j)
1769 2136 : continue;
1770 9199 : if (!types_compatible_p (TREE_TYPE (s1), TREE_TYPE (s2)))
1771 : {
1772 4288 : if (!try_same_size
1773 5993 : && tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1774 1705 : TYPE_SIZE (TREE_TYPE (s2))))
1775 : try_same_size = true;
1776 4288 : continue;
1777 : }
1778 4911 : int v2 = SSA_NAME_VERSION (s2);
1779 4911 : if (attempt_coalesce (map, graph, v1, v2, debug_file)
1780 4911 : && partition_to_var (map, i) != s1)
1781 : break;
1782 : }
1783 : }
1784 :
1785 2771 : if (!try_same_size)
1786 : return;
1787 :
1788 881 : unsigned i;
1789 881 : bitmap_iterator bi;
1790 881 : bitmap same_type = NULL;
1791 :
1792 3949 : EXECUTE_IF_SET_IN_BITMAP (map->bitint, 0, i, bi)
1793 : {
1794 3068 : tree s = ssa_name (i);
1795 3068 : if (!SSA_NAME_VAR (s))
1796 1682 : continue;
1797 1625 : if (TREE_CODE (SSA_NAME_VAR (s)) != RESULT_DECL
1798 1386 : && (TREE_CODE (SSA_NAME_VAR (s)) != PARM_DECL
1799 1147 : || !SSA_NAME_IS_DEFAULT_DEF (s)))
1800 239 : continue;
1801 1147 : if (same_type == NULL)
1802 839 : same_type = BITMAP_ALLOC (NULL);
1803 1147 : int p = var_to_partition (map, s);
1804 1147 : bitmap_set_bit (same_type, p);
1805 : }
1806 :
1807 3949 : for (i = 0; i < n; ++i)
1808 : {
1809 3068 : if (same_type && bitmap_bit_p (same_type, i))
1810 1147 : continue;
1811 1921 : tree s1 = partition_to_var (map, i);
1812 1921 : if ((unsigned) var_to_partition (map, s1) != i)
1813 884 : continue;
1814 1037 : int v1 = SSA_NAME_VERSION (s1);
1815 5523 : for (unsigned j = i + 1; j < n; ++j)
1816 : {
1817 4503 : if (same_type && bitmap_bit_p (same_type, j))
1818 1207 : continue;
1819 :
1820 3296 : tree s2 = partition_to_var (map, j);
1821 3296 : if (s1 == s2 || (unsigned) var_to_partition (map, s2) != j)
1822 2232 : continue;
1823 :
1824 1064 : if (!tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1825 1064 : TYPE_SIZE (TREE_TYPE (s2))))
1826 424 : continue;
1827 :
1828 640 : int v2 = SSA_NAME_VERSION (s2);
1829 640 : if (attempt_coalesce (map, graph, v1, v2, debug_file)
1830 640 : && partition_to_var (map, i) != s1)
1831 : break;
1832 : }
1833 : }
1834 :
1835 881 : 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 1521587 : coalesce_ssa_name (var_map map)
1844 : {
1845 1521587 : tree_live_info_p liveinfo;
1846 1521587 : ssa_conflicts *graph;
1847 1521587 : coalesce_list *cl;
1848 1521587 : auto_bitmap used_in_copies;
1849 :
1850 1521587 : bitmap_tree_view (used_in_copies);
1851 1521587 : cl = create_coalesce_list_for_region (map, used_in_copies);
1852 1521587 : if (map->outofssa_p)
1853 1515899 : populate_coalesce_list_for_outofssa (cl, used_in_copies);
1854 1521587 : bitmap_list_view (used_in_copies);
1855 1521587 : if (map->bitint)
1856 5688 : bitmap_ior_into (used_in_copies, map->bitint);
1857 :
1858 1521587 : if (dump_file && (dump_flags & TDF_DETAILS))
1859 111 : dump_var_map (dump_file, map);
1860 :
1861 1521587 : partition_view_bitmap (map, used_in_copies);
1862 :
1863 1521587 : compute_optimized_partition_bases (map, used_in_copies, cl);
1864 :
1865 1521587 : if (num_var_partitions (map) < 1)
1866 : {
1867 192270 : delete_coalesce_list (cl);
1868 192270 : return;
1869 : }
1870 :
1871 1329317 : if (dump_file && (dump_flags & TDF_DETAILS))
1872 64 : dump_var_map (dump_file, map);
1873 :
1874 1329317 : liveinfo = calculate_live_ranges (map, false);
1875 :
1876 1329317 : if (dump_file && (dump_flags & TDF_DETAILS))
1877 64 : dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1878 :
1879 : /* Build a conflict graph. */
1880 1329317 : graph = build_ssa_conflict_graph (liveinfo);
1881 1329317 : delete_tree_live_info (liveinfo);
1882 1329317 : if (dump_file && (dump_flags & TDF_DETAILS))
1883 64 : ssa_conflicts_dump (dump_file, graph);
1884 :
1885 1329317 : sort_coalesce_list (cl, graph, map);
1886 :
1887 1329317 : 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 1329317 : if (dump_file && (dump_flags & TDF_DETAILS))
1897 64 : dump_var_map (dump_file, map);
1898 :
1899 : /* Now coalesce everything in the list. */
1900 1329317 : coalesce_partitions (map, graph, cl,
1901 1329317 : ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1902 :
1903 1329317 : delete_coalesce_list (cl);
1904 :
1905 1329317 : if (map->bitint && flag_tree_coalesce_vars)
1906 2771 : coalesce_bitint (map, graph);
1907 :
1908 1329317 : ssa_conflicts_delete (graph);
1909 1521587 : }
|
