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 8632071 : coalesce_pair_hasher::hash (const coalesce_pair *pair)
103 : {
104 8632071 : hashval_t a = (hashval_t)(pair->first_element);
105 8632071 : hashval_t b = (hashval_t)(pair->second_element);
106 :
107 2033222 : 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 2806082 : coalesce_pair_hasher::equal (const coalesce_pair *p1, const coalesce_pair *p2)
115 : {
116 2806082 : return (p1->first_element == p2->first_element
117 2806082 : && 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 6307036 : coalesce_cost (int frequency, bool optimize_for_size)
150 : {
151 : /* Base costs on BB frequencies bounded by 1. */
152 6307036 : int cost = frequency;
153 :
154 6307036 : if (!cost)
155 574614 : cost = 1;
156 :
157 6301987 : if (optimize_for_size)
158 803246 : cost = 1;
159 :
160 6307036 : return cost;
161 : }
162 :
163 :
164 : /* Return the cost of executing a copy instruction in basic block BB. */
165 :
166 : static inline int
167 748648 : coalesce_cost_bb (basic_block bb)
168 : {
169 748648 : return coalesce_cost (bb->count.to_frequency (cfun),
170 748648 : 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 5553339 : coalesce_cost_edge (edge e)
178 : {
179 5553339 : int mult = 1;
180 :
181 : /* Inserting copy on critical edge costs more than inserting it elsewhere. */
182 5553339 : if (EDGE_CRITICAL_P (e))
183 : mult = 2;
184 5553339 : if (e->flags & EDGE_ABNORMAL)
185 : return MUST_COALESCE_COST;
186 5553339 : if (e->flags & EDGE_EH)
187 : {
188 38450 : edge e2;
189 38450 : edge_iterator ei;
190 88763 : FOR_EACH_EDGE (e2, ei, e->dest->preds)
191 84314 : 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 74427 : if (mult < 2)
197 74427 : 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 74427 : if (e2->flags & EDGE_EH)
202 : {
203 : mult = 5;
204 : break;
205 : }
206 : }
207 : }
208 :
209 5553339 : return coalesce_cost (EDGE_FREQUENCY (e),
210 11106678 : 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 1575726 : pop_cost_one_pair (coalesce_list *cl, int *p1, int *p2)
220 : {
221 1575726 : cost_one_pair *ptr;
222 :
223 1575726 : ptr = cl->cost_one_list;
224 1575726 : if (!ptr)
225 : return NO_BEST_COALESCE;
226 :
227 275625 : *p1 = ptr->first_element;
228 275625 : *p2 = ptr->second_element;
229 275625 : cl->cost_one_list = ptr->next;
230 :
231 275625 : 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 7548355 : pop_best_coalesce (coalesce_list *cl, int *p1, int *p2)
240 : {
241 7548355 : coalesce_pair *node;
242 7548355 : int ret;
243 :
244 7548355 : if (cl->sorted == NULL)
245 601008 : return pop_cost_one_pair (cl, p1, p2);
246 :
247 6947347 : if (cl->num_sorted == 0)
248 974718 : return pop_cost_one_pair (cl, p1, p2);
249 :
250 5972629 : node = cl->sorted[--(cl->num_sorted)];
251 5972629 : *p1 = node->first_element;
252 5972629 : *p2 = node->second_element;
253 5972629 : ret = node->cost;
254 :
255 5972629 : return ret;
256 : }
257 :
258 :
259 : /* Create a new empty coalesce list object and return it. */
260 :
261 : static inline coalesce_list *
262 1486418 : create_coalesce_list (void)
263 : {
264 1486418 : coalesce_list *list;
265 1486418 : unsigned size = num_ssa_names * 3;
266 :
267 1486418 : if (size < 40)
268 1486418 : size = 40;
269 :
270 1486418 : list = (coalesce_list *) xmalloc (sizeof (struct coalesce_list));
271 1486418 : list->list = new coalesce_table_type (size);
272 1486418 : list->sorted = NULL;
273 1486418 : list->num_sorted = 0;
274 1486418 : list->cost_one_list = NULL;
275 1486418 : gcc_obstack_init (&list->ob);
276 1486418 : return list;
277 : }
278 :
279 :
280 : /* Delete coalesce list CL. */
281 :
282 : static inline void
283 1486418 : delete_coalesce_list (coalesce_list *cl)
284 : {
285 1486418 : gcc_assert (cl->cost_one_list == NULL);
286 1486418 : delete cl->list;
287 1486418 : cl->list = NULL;
288 1486418 : free (cl->sorted);
289 1486418 : gcc_assert (cl->num_sorted == 0);
290 1486418 : obstack_free (&cl->ob, NULL);
291 1486418 : free (cl);
292 1486418 : }
293 :
294 : /* Return the number of unique coalesce pairs in CL. */
295 :
296 : static inline int
297 7272730 : num_coalesce_pairs (coalesce_list *cl)
298 : {
299 7272730 : 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 6598849 : find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
308 : {
309 6598849 : struct coalesce_pair p;
310 6598849 : coalesce_pair **slot;
311 6598849 : unsigned int hash;
312 :
313 : /* Normalize so that p1 is the smaller value. */
314 6598849 : if (p2 < p1)
315 : {
316 3841433 : p.first_element = p2;
317 3841433 : p.second_element = p1;
318 : }
319 : else
320 : {
321 2757416 : p.first_element = p1;
322 2757416 : p.second_element = p2;
323 : }
324 :
325 6598849 : hash = coalesce_pair_hasher::hash (&p);
326 6598849 : slot = cl->list->find_slot_with_hash (&p, hash, create ? INSERT : NO_INSERT);
327 6598849 : if (!slot)
328 : return NULL;
329 :
330 6598849 : if (!*slot)
331 : {
332 5972629 : struct coalesce_pair * pair = XOBNEW (&cl->ob, struct coalesce_pair);
333 5972629 : gcc_assert (cl->sorted == NULL);
334 5972629 : pair->first_element = p.first_element;
335 5972629 : pair->second_element = p.second_element;
336 5972629 : pair->cost = 0;
337 5972629 : pair->index = num_coalesce_pairs (cl);
338 5972629 : pair->conflict_count = 0;
339 5972629 : *slot = pair;
340 : }
341 :
342 6598849 : return (struct coalesce_pair *) *slot;
343 : }
344 :
345 : static inline void
346 275625 : add_cost_one_coalesce (coalesce_list *cl, int p1, int p2)
347 : {
348 275625 : cost_one_pair *pair;
349 :
350 275625 : pair = XOBNEW (&cl->ob, cost_one_pair);
351 275625 : pair->first_element = p1;
352 275625 : pair->second_element = p2;
353 275625 : pair->next = cl->cost_one_list;
354 275625 : cl->cost_one_list = pair;
355 275625 : }
356 :
357 :
358 : /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
359 :
360 : static inline void
361 6608166 : add_coalesce (coalesce_list *cl, int p1, int p2, int value)
362 : {
363 6608166 : coalesce_pair *node;
364 :
365 6608166 : gcc_assert (cl->sorted == NULL);
366 6608166 : if (p1 == p2)
367 : return;
368 :
369 6598849 : 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 6598849 : if (node->cost < MUST_COALESCE_COST - 1)
373 : {
374 6598849 : if (value < MUST_COALESCE_COST - 1)
375 6022865 : node->cost += value;
376 : else
377 575984 : 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 57121554 : initialize_conflict_count (coalesce_pair *p,
388 : ssa_conflicts *conflicts,
389 : var_map map)
390 : {
391 57121554 : int p1 = var_to_partition (map, ssa_name (p->first_element));
392 57121554 : 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 57121554 : if (conflicts->conflicts[p1] && conflicts->conflicts[p2])
398 808260 : p->conflict_count = bitmap_count_unique_bits (conflicts->conflicts[p1],
399 808260 : conflicts->conflicts[p2]);
400 56313294 : else if (conflicts->conflicts[p1])
401 132987 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p1]);
402 56180307 : else if (conflicts->conflicts[p2])
403 141336 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p2]);
404 : else
405 56038971 : p->conflict_count = 0;
406 57121554 : }
407 :
408 :
409 : /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
410 :
411 : static int
412 169894197 : compare_pairs (const void *p1, const void *p2)
413 : {
414 169894197 : coalesce_pair *const *const pp1 = (coalesce_pair *const *) p1;
415 169894197 : coalesce_pair *const *const pp2 = (coalesce_pair *const *) p2;
416 169894197 : int result;
417 :
418 169894197 : 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 169894197 : if (result == 0)
423 : {
424 73048495 : if (flag_expensive_optimizations)
425 : {
426 : /* Lazily initialize the conflict counts as it's fairly expensive
427 : to compute. */
428 40010363 : if ((*pp2)->conflict_count == 0)
429 28731983 : initialize_conflict_count (*pp2, conflicts_, map_);
430 40010363 : if ((*pp1)->conflict_count == 0)
431 28389571 : initialize_conflict_count (*pp1, conflicts_, map_);
432 :
433 40010363 : 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 73048495 : if (result == 0)
439 63226104 : result = (*pp2)->index - (*pp1)->index;
440 : }
441 :
442 169894197 : 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 1300101 : sort_coalesce_list (coalesce_list *cl, ssa_conflicts *conflicts, var_map map)
456 : {
457 1300101 : unsigned x, num;
458 1300101 : coalesce_pair *p;
459 1300101 : coalesce_iterator_type ppi;
460 :
461 1300101 : gcc_assert (cl->sorted == NULL);
462 :
463 1300101 : num = num_coalesce_pairs (cl);
464 1300101 : cl->num_sorted = num;
465 1300101 : if (num == 0)
466 920074 : return;
467 :
468 : /* Allocate a vector for the pair pointers. */
469 704951 : cl->sorted = XNEWVEC (coalesce_pair *, num);
470 :
471 : /* Populate the vector with pointers to the pairs. */
472 704951 : x = 0;
473 6677580 : FOR_EACH_PARTITION_PAIR (p, ppi, cl)
474 5972629 : cl->sorted[x++] = p;
475 704951 : gcc_assert (x == num);
476 :
477 : /* Already sorted. */
478 704951 : 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 380027 : conflicts_ = conflicts;
485 380027 : map_ = map;
486 380027 : qsort (cl->sorted, num, sizeof (coalesce_pair *), compare_pairs);
487 380027 : conflicts_ = NULL;
488 380027 : 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 1300101 : ssa_conflicts_new (unsigned size)
539 : {
540 1300101 : ssa_conflicts *ptr;
541 :
542 1300101 : ptr = XNEW (ssa_conflicts);
543 1300101 : bitmap_obstack_initialize (&ptr->obstack);
544 1300101 : ptr->conflicts.create (size);
545 1300101 : ptr->conflicts.safe_grow_cleared (size, true);
546 1300101 : return ptr;
547 : }
548 :
549 :
550 : /* Free storage for conflict graph PTR. */
551 :
552 : static inline void
553 1300101 : ssa_conflicts_delete (ssa_conflicts *ptr)
554 : {
555 1300101 : bitmap_obstack_release (&ptr->obstack);
556 1300101 : ptr->conflicts.release ();
557 1300101 : free (ptr);
558 1300101 : }
559 :
560 :
561 : /* Test if elements X and Y conflict in graph PTR. */
562 :
563 : static inline bool
564 5823756 : ssa_conflicts_test_p (ssa_conflicts *ptr, unsigned x, unsigned y)
565 : {
566 5823756 : bitmap bx = ptr->conflicts[x];
567 5823756 : bitmap by = ptr->conflicts[y];
568 :
569 5823756 : gcc_checking_assert (x != y);
570 :
571 5823756 : if (bx)
572 : /* Avoid the lookup if Y has no conflicts. */
573 1309727 : 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 3102254 : ssa_conflicts_add_one (ssa_conflicts *ptr, unsigned x, unsigned y)
583 : {
584 3102254 : bitmap bx = ptr->conflicts[x];
585 : /* If there are no conflicts yet, allocate the bitmap and set bit. */
586 3102254 : if (! bx)
587 1293245 : bx = ptr->conflicts[x] = BITMAP_ALLOC (&ptr->obstack);
588 3102254 : bitmap_set_bit (bx, y);
589 3102254 : }
590 :
591 :
592 : /* Add conflicts between X and Y in graph PTR. */
593 :
594 : static inline void
595 1551127 : ssa_conflicts_add (ssa_conflicts *ptr, unsigned x, unsigned y)
596 : {
597 1551127 : gcc_checking_assert (x != y);
598 1551127 : ssa_conflicts_add_one (ptr, x, y);
599 1551127 : ssa_conflicts_add_one (ptr, y, x);
600 1551127 : }
601 :
602 :
603 : /* Merge all Y's conflict into X in graph PTR. */
604 :
605 : static inline void
606 5321694 : ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y)
607 : {
608 5321694 : unsigned z;
609 5321694 : bitmap_iterator bi;
610 5321694 : bitmap bx = ptr->conflicts[x];
611 5321694 : bitmap by = ptr->conflicts[y];
612 :
613 5321694 : gcc_checking_assert (x != y);
614 5321694 : if (! by)
615 4602619 : 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 2420592 : EXECUTE_IF_SET_IN_BITMAP (by, 0, z, bi)
621 : {
622 1701517 : bitmap bz = ptr->conflicts[z];
623 1701517 : if (bz)
624 : {
625 1701517 : bool was_there = bitmap_clear_bit (bz, y);
626 1701517 : gcc_checking_assert (was_there);
627 1701517 : bitmap_set_bit (bz, x);
628 : }
629 : }
630 :
631 719075 : if (bx)
632 : {
633 : /* If X has conflicts, add Y's to X. */
634 607957 : bitmap_ior_into (bx, by);
635 607957 : BITMAP_FREE (by);
636 607957 : ptr->conflicts[y] = NULL;
637 : }
638 : else
639 : {
640 : /* If X has no conflicts, simply use Y's. */
641 111118 : ptr->conflicts[x] = by;
642 111118 : 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 1300101 : new_live_track (var_map map)
693 : {
694 1300101 : live_track *ptr;
695 1300101 : int lim, x;
696 :
697 : /* Make sure there is a partition view in place. */
698 1300101 : gcc_assert (map->partition_to_base_index != NULL);
699 :
700 1300101 : ptr = XNEW (live_track);
701 1300101 : ptr->map = map;
702 1300101 : lim = num_basevars (map);
703 1300101 : bitmap_obstack_initialize (&ptr->obstack);
704 1300101 : ptr->live_base_partitions = XNEWVEC (bitmap_head, lim);
705 1300101 : bitmap_initialize (&ptr->live_base_var, &ptr->obstack);
706 6787767 : for (x = 0; x < lim; x++)
707 5487666 : bitmap_initialize (&ptr->live_base_partitions[x], &ptr->obstack);
708 1300101 : return ptr;
709 : }
710 :
711 :
712 : /* This routine will free the memory associated with PTR. */
713 :
714 : static void
715 1300101 : delete_live_track (live_track *ptr)
716 : {
717 1300101 : bitmap_obstack_release (&ptr->obstack);
718 1300101 : XDELETEVEC (ptr->live_base_partitions);
719 1300101 : XDELETE (ptr);
720 1300101 : }
721 :
722 :
723 : /* This function will remove PARTITION from the live list in PTR. */
724 :
725 : static inline void
726 10822021 : live_track_remove_partition (live_track *ptr, int partition)
727 : {
728 10822021 : int root;
729 :
730 10822021 : root = basevar_index (ptr->map, partition);
731 10822021 : bitmap_clear_bit (&ptr->live_base_partitions[root], partition);
732 : /* If the element list is empty, make the base variable not live either. */
733 10822021 : if (bitmap_empty_p (&ptr->live_base_partitions[root]))
734 9486211 : bitmap_clear_bit (&ptr->live_base_var, root);
735 10822021 : }
736 :
737 :
738 : /* This function will adds PARTITION to the live list in PTR. */
739 :
740 : static inline void
741 45844050 : live_track_add_partition (live_track *ptr, int partition)
742 : {
743 45844050 : int root;
744 :
745 45844050 : 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 45844050 : if (bitmap_set_bit (&ptr->live_base_var, root))
749 33883826 : bitmap_clear (&ptr->live_base_partitions[root]);
750 45844050 : bitmap_set_bit (&ptr->live_base_partitions[root], partition);
751 :
752 45844050 : }
753 :
754 :
755 : /* Clear the live bit for VAR in PTR. */
756 :
757 : static inline void
758 695012 : live_track_clear_var (live_track *ptr, tree var)
759 : {
760 695012 : int p;
761 :
762 695012 : p = var_to_partition (ptr->map, var);
763 695012 : if (p != NO_PARTITION)
764 598414 : live_track_remove_partition (ptr, p);
765 695012 : }
766 :
767 :
768 : /* Return TRUE if VAR is live in PTR. */
769 :
770 : static inline bool
771 2856404 : live_track_live_p (live_track *ptr, tree var)
772 : {
773 2856404 : int p, root;
774 :
775 2856404 : p = var_to_partition (ptr->map, var);
776 2856404 : if (p != NO_PARTITION)
777 : {
778 2817380 : root = basevar_index (ptr->map, p);
779 2817380 : if (bitmap_bit_p (&ptr->live_base_var, root))
780 2817380 : 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 40557280 : live_track_process_use (live_track *ptr, tree use)
791 : {
792 40557280 : int p;
793 :
794 40557280 : p = var_to_partition (ptr->map, use);
795 40557280 : if (p == NO_PARTITION)
796 : return;
797 :
798 : /* Mark as live in the appropriate live list. */
799 16343993 : 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 28521553 : live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph)
809 : {
810 28521553 : int p, root;
811 28521553 : bitmap b;
812 28521553 : unsigned x;
813 28521553 : bitmap_iterator bi;
814 :
815 28521553 : p = var_to_partition (ptr->map, def);
816 28521553 : if (p == NO_PARTITION)
817 18297946 : return;
818 :
819 : /* Clear the liveness bit. */
820 10223607 : live_track_remove_partition (ptr, p);
821 :
822 : /* If the bitmap isn't empty now, conflicts need to be added. */
823 10223607 : root = basevar_index (ptr->map, p);
824 10223607 : if (bitmap_bit_p (&ptr->live_base_var, root))
825 : {
826 949625 : b = &ptr->live_base_partitions[root];
827 2500752 : EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
828 1551127 : 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 11777880 : live_track_init (live_track *ptr, bitmap init)
837 : {
838 11777880 : unsigned p;
839 11777880 : bitmap_iterator bi;
840 :
841 : /* Mark all live on exit partitions. */
842 41277937 : EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
843 29500057 : live_track_add_partition (ptr, p);
844 11777880 : }
845 :
846 :
847 : /* This routine will clear all live partitions in PTR. */
848 :
849 : static inline void
850 11777880 : 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 11777880 : 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 1300101 : build_ssa_conflict_graph (tree_live_info_p liveinfo)
866 : {
867 1300101 : ssa_conflicts *graph;
868 1300101 : var_map map;
869 1300101 : basic_block bb;
870 1300101 : ssa_op_iter iter;
871 1300101 : live_track *live;
872 1300101 : 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 1300101 : if (flag_tree_coalesce_vars)
879 933878 : entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
880 : else
881 : entry = NULL;
882 :
883 1300101 : map = live_var_map (liveinfo);
884 1300101 : graph = ssa_conflicts_new (num_var_partitions (map));
885 :
886 1300101 : live = new_live_track (map);
887 :
888 13077981 : for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
889 : {
890 : /* Start with live on exit temporaries. */
891 11777880 : live_track_init (live, live_on_exit (liveinfo, bb));
892 :
893 11777880 : for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
894 192027206 : gsi_prev (&gsi))
895 : {
896 90124663 : tree var;
897 90124663 : gimple *stmt = gsi_stmt (gsi);
898 :
899 90124663 : if (is_gimple_debug (stmt))
900 47462240 : continue;
901 :
902 42662423 : if (map->bitint)
903 : {
904 82130 : 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 82130 : 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 42580293 : if (is_gimple_assign (stmt))
919 : {
920 29287790 : tree lhs = gimple_assign_lhs (stmt);
921 29287790 : tree rhs1 = gimple_assign_rhs1 (stmt);
922 29287790 : if (gimple_assign_copy_p (stmt)
923 8049530 : && TREE_CODE (lhs) == SSA_NAME
924 30509349 : && TREE_CODE (rhs1) == SSA_NAME)
925 694981 : 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 42580293 : bool first = true;
939 65569608 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
940 22989315 : if (first)
941 : first = false;
942 : else
943 18528 : live_track_process_use (live, var);
944 :
945 65569608 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
946 22989315 : live_track_process_def (live, var, graph);
947 :
948 80405631 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
949 37825338 : 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 14639940 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
959 2862060 : gsi_next (&gsi))
960 : {
961 2862060 : gphi *phi = gsi.phi ();
962 2862060 : tree result = PHI_RESULT (phi);
963 5724120 : if (virtual_operand_p (result))
964 5656 : continue;
965 2856404 : if (live_track_live_p (live, result))
966 2817380 : 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 11777880 : if (bb == entry)
977 : {
978 : unsigned i;
979 : tree var;
980 :
981 54184202 : FOR_EACH_SSA_NAME (i, var, cfun)
982 : {
983 33183577 : if (!SSA_NAME_IS_DEFAULT_DEF (var)
984 3895470 : || !SSA_NAME_VAR (var)
985 37079047 : || VAR_P (SSA_NAME_VAR (var)))
986 30505241 : continue;
987 :
988 2678336 : 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 2678336 : live_track_process_use (live, var);
993 : }
994 : }
995 :
996 11777880 : live_track_clear_base_vars (live);
997 : }
998 :
999 1300101 : delete_live_track (live);
1000 1300101 : 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 31314429 : coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
1024 : {
1025 31314429 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1026 27383677 : || !SSA_NAME_VAR (var)
1027 38006843 : || VAR_P (SSA_NAME_VAR (var)))
1028 : return;
1029 :
1030 156796 : tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var));
1031 156796 : 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 1486418 : create_coalesce_list_for_region (var_map map, bitmap used_in_copy)
1047 : {
1048 1486418 : gimple_stmt_iterator gsi;
1049 1486418 : basic_block bb;
1050 1486418 : coalesce_list *cl = create_coalesce_list ();
1051 1486418 : gimple *stmt;
1052 1486418 : int v1, v2, cost;
1053 :
1054 14061160 : for (unsigned j = 0; map->vec_bbs.iterate (j, &bb); ++j)
1055 : {
1056 12574742 : tree arg;
1057 :
1058 12574742 : for (gphi_iterator gpi = gsi_start_phis (bb);
1059 15438110 : !gsi_end_p (gpi);
1060 2863368 : gsi_next (&gpi))
1061 : {
1062 2863368 : gphi *phi = gpi.phi ();
1063 2863368 : size_t i;
1064 2863368 : int ver;
1065 2863368 : tree res;
1066 2863368 : bool saw_copy = false;
1067 :
1068 2863368 : res = gimple_phi_result (phi);
1069 5726736 : if (virtual_operand_p (res))
1070 6059 : continue;
1071 2857309 : ver = SSA_NAME_VERSION (res);
1072 2857309 : if (map->bitint && !bitmap_bit_p (map->bitint, ver))
1073 752 : continue;
1074 :
1075 : /* Register ssa_names and coalesces between the args and the result
1076 : of all PHI. */
1077 9832432 : for (i = 0; i < gimple_phi_num_args (phi); i++)
1078 : {
1079 6975875 : edge e = gimple_phi_arg_edge (phi, i);
1080 6975875 : arg = PHI_ARG_DEF (phi, i);
1081 6975875 : if (TREE_CODE (arg) != SSA_NAME)
1082 1227767 : continue;
1083 :
1084 5748108 : if (gimple_can_coalesce_p (arg, res)
1085 5748108 : || (e->flags & EDGE_ABNORMAL))
1086 : {
1087 5747806 : saw_copy = true;
1088 5747806 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1089 5747806 : if ((e->flags & EDGE_ABNORMAL) == 0)
1090 : {
1091 5553339 : int cost = coalesce_cost_edge (e);
1092 5553339 : if (cost == 1 && has_single_use (arg))
1093 274854 : add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1094 : else
1095 5278485 : add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1096 : }
1097 : }
1098 : }
1099 2856557 : if (saw_copy)
1100 2786984 : bitmap_set_bit (used_in_copy, ver);
1101 : }
1102 :
1103 120868234 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1104 : {
1105 95718750 : stmt = gsi_stmt (gsi);
1106 :
1107 95718750 : if (is_gimple_debug (stmt))
1108 49306134 : continue;
1109 :
1110 : /* Check for copy coalesces. */
1111 46412616 : switch (gimple_code (stmt))
1112 : {
1113 31601574 : case GIMPLE_ASSIGN:
1114 31601574 : {
1115 31601574 : tree lhs = gimple_assign_lhs (stmt);
1116 31601574 : tree rhs1 = gimple_assign_rhs1 (stmt);
1117 31601574 : if (gimple_assign_ssa_name_copy_p (stmt)
1118 31601574 : && gimple_can_coalesce_p (lhs, rhs1))
1119 : {
1120 368829 : v1 = SSA_NAME_VERSION (lhs);
1121 368829 : v2 = SSA_NAME_VERSION (rhs1);
1122 368829 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1123 : break;
1124 368763 : cost = coalesce_cost_bb (bb);
1125 368763 : add_coalesce (cl, v1, v2, cost);
1126 368763 : bitmap_set_bit (used_in_copy, v1);
1127 368763 : bitmap_set_bit (used_in_copy, v2);
1128 : }
1129 : }
1130 : break;
1131 :
1132 1454160 : case GIMPLE_RETURN:
1133 1454160 : {
1134 1454160 : tree res = DECL_RESULT (current_function_decl);
1135 1454160 : if (VOID_TYPE_P (TREE_TYPE (res))
1136 1454160 : || !is_gimple_reg (res))
1137 : break;
1138 664707 : tree rhs1 = gimple_return_retval (as_a <greturn *> (stmt));
1139 664707 : if (!rhs1)
1140 : break;
1141 659502 : tree lhs = ssa_default_def (cfun, res);
1142 659502 : if (map->bitint && !lhs)
1143 : break;
1144 659021 : gcc_assert (lhs);
1145 659021 : if (TREE_CODE (rhs1) == SSA_NAME
1146 659021 : && gimple_can_coalesce_p (lhs, rhs1))
1147 : {
1148 379885 : v1 = SSA_NAME_VERSION (lhs);
1149 379885 : v2 = SSA_NAME_VERSION (rhs1);
1150 379885 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1151 : break;
1152 379885 : cost = coalesce_cost_bb (bb);
1153 379885 : add_coalesce (cl, v1, v2, cost);
1154 379885 : bitmap_set_bit (used_in_copy, v1);
1155 379885 : bitmap_set_bit (used_in_copy, v2);
1156 : }
1157 : break;
1158 : }
1159 :
1160 110187 : case GIMPLE_ASM:
1161 110187 : {
1162 110187 : gasm *asm_stmt = as_a <gasm *> (stmt);
1163 110187 : unsigned long noutputs, i;
1164 110187 : unsigned long ninputs;
1165 110187 : tree *outputs, link;
1166 110187 : noutputs = gimple_asm_noutputs (asm_stmt);
1167 110187 : ninputs = gimple_asm_ninputs (asm_stmt);
1168 110187 : outputs = (tree *) alloca (noutputs * sizeof (tree));
1169 187201 : for (i = 0; i < noutputs; ++i)
1170 : {
1171 77014 : link = gimple_asm_output_op (asm_stmt, i);
1172 77014 : outputs[i] = TREE_VALUE (link);
1173 : }
1174 :
1175 166208 : for (i = 0; i < ninputs; ++i)
1176 : {
1177 56021 : const char *constraint;
1178 56021 : tree input;
1179 56021 : char *end;
1180 56021 : unsigned long match;
1181 :
1182 56021 : link = gimple_asm_input_op (asm_stmt, i);
1183 56021 : constraint
1184 56021 : = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1185 56021 : input = TREE_VALUE (link);
1186 :
1187 56021 : if (TREE_CODE (input) != SSA_NAME)
1188 50517 : continue;
1189 :
1190 15252 : match = strtoul (constraint, &end, 10);
1191 15252 : if (match >= noutputs || end == constraint)
1192 8016 : continue;
1193 :
1194 7236 : if (TREE_CODE (outputs[match]) != SSA_NAME)
1195 1732 : continue;
1196 :
1197 5504 : v1 = SSA_NAME_VERSION (outputs[match]);
1198 5504 : v2 = SSA_NAME_VERSION (input);
1199 5504 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1200 0 : continue;
1201 :
1202 5504 : if (gimple_can_coalesce_p (outputs[match], input))
1203 : {
1204 5049 : cost = coalesce_cost (REG_BR_PROB_BASE,
1205 5049 : optimize_bb_for_size_p (bb));
1206 5049 : add_coalesce (cl, v1, v2, cost);
1207 5049 : bitmap_set_bit (used_in_copy, v1);
1208 5049 : bitmap_set_bit (used_in_copy, v2);
1209 : }
1210 : }
1211 : break;
1212 : }
1213 :
1214 : default:
1215 : break;
1216 : }
1217 : }
1218 : }
1219 :
1220 1486418 : 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 6812137 : ssa_name_var_hash::hash (const_tree n)
1234 : {
1235 6812137 : return DECL_UID (SSA_NAME_VAR (n));
1236 : }
1237 :
1238 : inline int
1239 5019270 : ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
1240 : {
1241 10038540 : 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 1480896 : populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy)
1250 : {
1251 1480896 : tree var;
1252 1480896 : tree first;
1253 1480896 : int v1, v2, cost;
1254 1480896 : unsigned i;
1255 :
1256 : /* Process result decls and live on entry variables for entry into the
1257 : coalesce list. */
1258 1480896 : first = NULL_TREE;
1259 72675898 : FOR_EACH_SSA_NAME (i, var, cfun)
1260 : {
1261 96637198 : if (!virtual_operand_p (var))
1262 : {
1263 31314429 : coalesce_with_default (var, cl, used_in_copy);
1264 :
1265 : /* Add coalesces between all the result decls. */
1266 31314429 : if (SSA_NAME_VAR (var)
1267 10623166 : && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1268 : {
1269 676593 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1270 676593 : 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 31314429 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1285 31314429 : && (!has_zero_uses (var)
1286 1899598 : || (SSA_NAME_VAR (var)
1287 1899598 : && !VAR_P (SSA_NAME_VAR (var)))))
1288 3678618 : 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 1480896 : if (!flag_tree_coalesce_vars)
1296 : {
1297 435053 : tree a;
1298 435053 : hash_table<ssa_name_var_hash> ssa_name_hash (10);
1299 :
1300 14014636 : FOR_EACH_SSA_NAME (i, a, cfun)
1301 : {
1302 12660440 : if (SSA_NAME_VAR (a)
1303 6613486 : && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1304 1787174 : && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
1305 238206 : || !VAR_P (SSA_NAME_VAR (a))))
1306 : {
1307 1787143 : tree *slot = ssa_name_hash.find_slot (a, INSERT);
1308 :
1309 1787143 : if (!*slot)
1310 1211159 : *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 575984 : const int cost
1322 662554 : = (VAR_P (SSA_NAME_VAR (a)) || in_lto_p)
1323 575984 : ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
1324 1151968 : add_coalesce (cl, SSA_NAME_VERSION (a),
1325 575984 : SSA_NAME_VERSION (*slot), cost);
1326 575984 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a));
1327 575984 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot));
1328 : }
1329 : }
1330 : }
1331 435053 : }
1332 1480896 : }
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 6446729 : attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y,
1341 : FILE *debug)
1342 : {
1343 6446729 : int z;
1344 6446729 : tree var1, var2;
1345 6446729 : int p1, p2;
1346 :
1347 6446729 : p1 = var_to_partition (map, ssa_name (x));
1348 6446729 : p2 = var_to_partition (map, ssa_name (y));
1349 :
1350 6446729 : 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 6446729 : if (p1 == p2)
1359 : {
1360 622973 : if (debug)
1361 0 : fprintf (debug, ": Already Coalesced.\n");
1362 622973 : return true;
1363 : }
1364 :
1365 5823756 : if (debug)
1366 32 : fprintf (debug, " [map: %d, %d] ", p1, p2);
1367 :
1368 :
1369 5823756 : if (!ssa_conflicts_test_p (graph, p1, p2))
1370 : {
1371 5321694 : var1 = partition_to_var (map, p1);
1372 5321694 : var2 = partition_to_var (map, p2);
1373 :
1374 5321694 : z = var_union (map, var1, var2);
1375 5321694 : 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 5321694 : if (z == p1)
1385 4475875 : ssa_conflicts_merge (graph, p1, p2);
1386 : else
1387 845819 : ssa_conflicts_merge (graph, p2, p1);
1388 :
1389 5321694 : if (debug)
1390 32 : fprintf (debug, ": Success -> %d\n", z);
1391 :
1392 5321694 : return true;
1393 : }
1394 :
1395 502062 : 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 1300101 : coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
1407 : FILE *debug)
1408 : {
1409 1300101 : int x = 0, y = 0;
1410 1300101 : tree var1, var2;
1411 1300101 : int cost;
1412 1300101 : basic_block bb;
1413 1300101 : edge e;
1414 1300101 : 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 13077981 : FOR_EACH_BB_FN (bb, cfun)
1421 : {
1422 28919354 : FOR_EACH_EDGE (e, ei, bb->preds)
1423 17141474 : if (e->flags & EDGE_ABNORMAL)
1424 : {
1425 8542 : gphi_iterator gsi;
1426 203085 : 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 7548355 : while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1454 : {
1455 6248254 : var1 = ssa_name (x);
1456 6248254 : var2 = ssa_name (y);
1457 :
1458 : /* Assert the coalesces have the same base variable. */
1459 6248254 : gcc_assert (gimple_can_coalesce_p (var1, var2));
1460 :
1461 6248254 : if (debug)
1462 32 : fprintf (debug, "Coalesce list: ");
1463 6248254 : attempt_coalesce (map, graph, x, y, debug);
1464 : }
1465 1300101 : }
1466 :
1467 :
1468 : /* Output partition map MAP with coalescing plan PART to file F. */
1469 :
1470 : void
1471 114 : dump_part_var_map (FILE *f, partition part, var_map map)
1472 : {
1473 114 : int t;
1474 114 : unsigned x, y;
1475 114 : int p;
1476 :
1477 114 : fprintf (f, "\nCoalescible Partition map \n\n");
1478 :
1479 234 : 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 114 : fprintf (f, "\n");
1517 114 : }
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 24237605 : 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 24237605 : tree var1 = SSA_NAME_VAR (name1);
1532 24237605 : tree var2 = SSA_NAME_VAR (name2);
1533 24237605 : var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
1534 24237605 : var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
1535 24237605 : 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 23742812 : tree t1 = TREE_TYPE (name1);
1541 23742812 : tree t2 = TREE_TYPE (name2);
1542 23742812 : if (t1 == t2)
1543 : {
1544 21728571 : check_modes:
1545 : /* If the base variables are the same, we're good: none of the
1546 : other tests below could possibly fail. */
1547 23123500 : var1 = SSA_NAME_VAR (name1);
1548 23123500 : var2 = SSA_NAME_VAR (name2);
1549 23123500 : 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 4419509 : bool reg1 = use_register_for_decl (name1);
1560 4419509 : bool reg2 = use_register_for_decl (name2);
1561 4419509 : 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 4419487 : int unsigned1, unsigned2;
1571 4419487 : return ((!var1 || VAR_P (var1)) && (!var2 || VAR_P (var2)))
1572 6216939 : || ((promote_ssa_mode (name1, &unsigned1)
1573 898726 : == promote_ssa_mode (name2, &unsigned2))
1574 898726 : && unsigned1 == unsigned2);
1575 : }
1576 :
1577 : /* If alignment requirements are different, we can't coalesce. */
1578 4028482 : if (MINIMUM_ALIGNMENT (t1,
1579 : var1 ? DECL_MODE (var1) : TYPE_MODE (t1),
1580 : var1 ? LOCAL_DECL_ALIGNMENT (var1) : TYPE_ALIGN (t1))
1581 2014241 : != 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 1535730 : if (types_compatible_p (t1, t2))
1590 1394929 : 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 1486418 : compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1602 : coalesce_list *cl)
1603 : {
1604 1486418 : int parts = num_var_partitions (map);
1605 1486418 : 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 1486418 : gcc_assert (!cl->sorted);
1611 1486418 : coalesce_pair *node;
1612 1486418 : coalesce_iterator_type ppi;
1613 13431676 : FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1614 : {
1615 5972629 : tree v1 = ssa_name (node->first_element);
1616 5972629 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1617 5972629 : tree v2 = ssa_name (node->second_element);
1618 5972629 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1619 :
1620 5972629 : if (p1 == p2)
1621 495009 : continue;
1622 :
1623 5477620 : partition_union (tentative, p1, p2);
1624 : }
1625 :
1626 : /* We have to deal with cost one pairs too. */
1627 1762043 : for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1628 : {
1629 275625 : tree v1 = ssa_name (co->first_element);
1630 275625 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1631 275625 : tree v2 = ssa_name (co->second_element);
1632 275625 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1633 :
1634 275625 : if (p1 == p2)
1635 17621 : continue;
1636 :
1637 258004 : partition_union (tentative, p1, p2);
1638 : }
1639 :
1640 : /* And also with abnormal edges. */
1641 1486418 : basic_block bb;
1642 1486418 : edge e;
1643 1486418 : unsigned i;
1644 1486418 : edge_iterator ei;
1645 14061160 : for (i = 0; map->vec_bbs.iterate (i, &bb); ++i)
1646 : {
1647 30756191 : FOR_EACH_EDGE (e, ei, bb->preds)
1648 18181449 : if (e->flags & EDGE_ABNORMAL)
1649 : {
1650 10241 : gphi_iterator gsi;
1651 204784 : 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 1486418 : if (map->bitint
1676 5522 : && flag_tree_coalesce_vars
1677 2793 : && (optimize > 1 || parts < 500))
1678 10420 : for (i = 0; i < (unsigned) parts; ++i)
1679 : {
1680 7627 : tree s1 = partition_to_var (map, i);
1681 7627 : int p1 = partition_find (tentative, i);
1682 34389 : for (unsigned j = i + 1; j < (unsigned) parts; ++j)
1683 : {
1684 26780 : tree s2 = partition_to_var (map, j);
1685 26780 : if (s1 == s2)
1686 0 : continue;
1687 26780 : if (tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1688 26780 : TYPE_SIZE (TREE_TYPE (s2))))
1689 : {
1690 21581 : int p2 = partition_find (tentative, j);
1691 :
1692 21581 : if (p1 == p2)
1693 16935 : continue;
1694 :
1695 4646 : partition_union (tentative, p1, p2);
1696 4646 : if (partition_find (tentative, i) != p1)
1697 : break;
1698 : }
1699 : }
1700 : }
1701 :
1702 1486418 : map->partition_to_base_index = XCNEWVEC (int, parts);
1703 1486418 : auto_vec<unsigned int> index_map (parts);
1704 1486418 : if (parts)
1705 1300101 : index_map.quick_grow (parts);
1706 :
1707 : const unsigned no_part = -1;
1708 : unsigned count = parts;
1709 12715769 : while (count)
1710 11229351 : 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 1486418 : bitmap_iterator bi;
1718 12715769 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1719 : {
1720 11229351 : int pidx = var_to_partition (map, ssa_name (i));
1721 11229351 : int base = partition_find (tentative, pidx);
1722 11229351 : if (index_map[base] != no_part)
1723 5741685 : continue;
1724 5487666 : index_map[base] = count++;
1725 : }
1726 :
1727 1486418 : map->num_basevars = count;
1728 :
1729 12715769 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1730 : {
1731 11229351 : int pidx = var_to_partition (map, ssa_name (i));
1732 11229351 : int base = partition_find (tentative, pidx);
1733 11229351 : gcc_assert (index_map[base] < count);
1734 11229351 : map->partition_to_base_index[pidx] = index_map[base];
1735 : }
1736 :
1737 1486418 : if (dump_file && (dump_flags & TDF_DETAILS))
1738 114 : dump_part_var_map (dump_file, tentative, map);
1739 :
1740 1486418 : partition_delete (tentative);
1741 1486418 : }
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 2656 : coalesce_bitint (var_map map, ssa_conflicts *graph)
1752 : {
1753 2656 : unsigned n = num_var_partitions (map);
1754 2656 : if (optimize <= 1 && n > 500)
1755 1793 : return;
1756 :
1757 2656 : bool try_same_size = false;
1758 2656 : FILE *debug_file = (dump_flags & TDF_DETAILS) ? dump_file : NULL;
1759 10283 : for (unsigned i = 0; i < n; ++i)
1760 : {
1761 7627 : tree s1 = partition_to_var (map, i);
1762 7627 : if ((unsigned) var_to_partition (map, s1) != i)
1763 2610 : continue;
1764 5017 : int v1 = SSA_NAME_VERSION (s1);
1765 14590 : for (unsigned j = i + 1; j < n; ++j)
1766 : {
1767 9581 : tree s2 = partition_to_var (map, j);
1768 9581 : if (s1 == s2 || (unsigned) var_to_partition (map, s2) != j)
1769 1817 : continue;
1770 7764 : if (!types_compatible_p (TREE_TYPE (s1), TREE_TYPE (s2)))
1771 : {
1772 3533 : if (!try_same_size
1773 4574 : && tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1774 1041 : TYPE_SIZE (TREE_TYPE (s2))))
1775 : try_same_size = true;
1776 3533 : continue;
1777 : }
1778 4231 : int v2 = SSA_NAME_VERSION (s2);
1779 4231 : if (attempt_coalesce (map, graph, v1, v2, debug_file)
1780 4231 : && partition_to_var (map, i) != s1)
1781 : break;
1782 : }
1783 : }
1784 :
1785 2656 : if (!try_same_size)
1786 : return;
1787 :
1788 863 : unsigned i;
1789 863 : bitmap_iterator bi;
1790 863 : bitmap same_type = NULL;
1791 :
1792 3798 : EXECUTE_IF_SET_IN_BITMAP (map->bitint, 0, i, bi)
1793 : {
1794 2935 : tree s = ssa_name (i);
1795 2935 : if (!SSA_NAME_VAR (s))
1796 1617 : continue;
1797 1533 : if (TREE_CODE (SSA_NAME_VAR (s)) != RESULT_DECL
1798 1318 : && (TREE_CODE (SSA_NAME_VAR (s)) != PARM_DECL
1799 1103 : || !SSA_NAME_IS_DEFAULT_DEF (s)))
1800 215 : continue;
1801 1103 : if (same_type == NULL)
1802 823 : same_type = BITMAP_ALLOC (NULL);
1803 1103 : int p = var_to_partition (map, s);
1804 1103 : bitmap_set_bit (same_type, p);
1805 : }
1806 :
1807 3798 : for (i = 0; i < n; ++i)
1808 : {
1809 2935 : if (same_type && bitmap_bit_p (same_type, i))
1810 1103 : 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 863 : 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 1486418 : coalesce_ssa_name (var_map map)
1844 : {
1845 1486418 : tree_live_info_p liveinfo;
1846 1486418 : ssa_conflicts *graph;
1847 1486418 : coalesce_list *cl;
1848 1486418 : auto_bitmap used_in_copies;
1849 :
1850 1486418 : bitmap_tree_view (used_in_copies);
1851 1486418 : cl = create_coalesce_list_for_region (map, used_in_copies);
1852 1486418 : if (map->outofssa_p)
1853 1480896 : populate_coalesce_list_for_outofssa (cl, used_in_copies);
1854 1486418 : bitmap_list_view (used_in_copies);
1855 1486418 : if (map->bitint)
1856 5522 : bitmap_ior_into (used_in_copies, map->bitint);
1857 :
1858 1486418 : if (dump_file && (dump_flags & TDF_DETAILS))
1859 114 : dump_var_map (dump_file, map);
1860 :
1861 1486418 : partition_view_bitmap (map, used_in_copies);
1862 :
1863 1486418 : compute_optimized_partition_bases (map, used_in_copies, cl);
1864 :
1865 1486418 : if (num_var_partitions (map) < 1)
1866 : {
1867 186317 : delete_coalesce_list (cl);
1868 186317 : return;
1869 : }
1870 :
1871 1300101 : if (dump_file && (dump_flags & TDF_DETAILS))
1872 64 : dump_var_map (dump_file, map);
1873 :
1874 1300101 : liveinfo = calculate_live_ranges (map, false);
1875 :
1876 1300101 : if (dump_file && (dump_flags & TDF_DETAILS))
1877 64 : dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1878 :
1879 : /* Build a conflict graph. */
1880 1300101 : graph = build_ssa_conflict_graph (liveinfo);
1881 1300101 : delete_tree_live_info (liveinfo);
1882 1300101 : if (dump_file && (dump_flags & TDF_DETAILS))
1883 64 : ssa_conflicts_dump (dump_file, graph);
1884 :
1885 1300101 : sort_coalesce_list (cl, graph, map);
1886 :
1887 1300101 : 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 1300101 : if (dump_file && (dump_flags & TDF_DETAILS))
1897 64 : dump_var_map (dump_file, map);
1898 :
1899 : /* Now coalesce everything in the list. */
1900 1300101 : coalesce_partitions (map, graph, cl,
1901 1300101 : ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1902 :
1903 1300101 : delete_coalesce_list (cl);
1904 :
1905 1300101 : if (map->bitint && flag_tree_coalesce_vars)
1906 2656 : coalesce_bitint (map, graph);
1907 :
1908 1300101 : ssa_conflicts_delete (graph);
1909 1486418 : }
|
