Branch data Line data Source code
1 : : /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 : : Copyright (C) 2004-2025 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 : 8953639 : coalesce_pair_hasher::hash (const coalesce_pair *pair)
103 : : {
104 : 8953639 : hashval_t a = (hashval_t)(pair->first_element);
105 : 8953639 : hashval_t b = (hashval_t)(pair->second_element);
106 : :
107 : 2104386 : 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 : 3038482 : coalesce_pair_hasher::equal (const coalesce_pair *p1, const coalesce_pair *p2)
115 : : {
116 : 3038482 : return (p1->first_element == p2->first_element
117 : 3038482 : && 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 : 6551034 : coalesce_cost (int frequency, bool optimize_for_size)
150 : : {
151 : : /* Base costs on BB frequencies bounded by 1. */
152 : 6551034 : int cost = frequency;
153 : :
154 : 6551034 : if (!cost)
155 : 627758 : cost = 1;
156 : :
157 : 6546613 : if (optimize_for_size)
158 : 858082 : cost = 1;
159 : :
160 : 6551034 : return cost;
161 : : }
162 : :
163 : :
164 : : /* Return the cost of executing a copy instruction in basic block BB. */
165 : :
166 : : static inline int
167 : 725411 : coalesce_cost_bb (basic_block bb)
168 : : {
169 : 725411 : return coalesce_cost (bb->count.to_frequency (cfun),
170 : 725411 : 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 : 5821202 : coalesce_cost_edge (edge e)
178 : : {
179 : 5821202 : int mult = 1;
180 : :
181 : : /* Inserting copy on critical edge costs more than inserting it elsewhere. */
182 : 5821202 : if (EDGE_CRITICAL_P (e))
183 : : mult = 2;
184 : 5821202 : if (e->flags & EDGE_ABNORMAL)
185 : : return MUST_COALESCE_COST;
186 : 5821202 : if (e->flags & EDGE_EH)
187 : : {
188 : 150273 : edge e2;
189 : 150273 : edge_iterator ei;
190 : 190180 : FOR_EACH_EDGE (e2, ei, e->dest->preds)
191 : 185272 : 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 : 171672 : if (mult < 2)
197 : 171672 : 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 : 171672 : if (e2->flags & EDGE_EH)
202 : : {
203 : : mult = 5;
204 : : break;
205 : : }
206 : : }
207 : : }
208 : :
209 : 5821202 : return coalesce_cost (EDGE_FREQUENCY (e),
210 : 11642404 : 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 : 1529631 : pop_cost_one_pair (coalesce_list *cl, int *p1, int *p2)
220 : : {
221 : 1529631 : cost_one_pair *ptr;
222 : :
223 : 1529631 : ptr = cl->cost_one_list;
224 : 1529631 : if (!ptr)
225 : : return NO_BEST_COALESCE;
226 : :
227 : 257180 : *p1 = ptr->first_element;
228 : 257180 : *p2 = ptr->second_element;
229 : 257180 : cl->cost_one_list = ptr->next;
230 : :
231 : 257180 : 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 : 7594030 : pop_best_coalesce (coalesce_list *cl, int *p1, int *p2)
240 : : {
241 : 7594030 : coalesce_pair *node;
242 : 7594030 : int ret;
243 : :
244 : 7594030 : if (cl->sorted == NULL)
245 : 587055 : return pop_cost_one_pair (cl, p1, p2);
246 : :
247 : 7006975 : if (cl->num_sorted == 0)
248 : 942576 : return pop_cost_one_pair (cl, p1, p2);
249 : :
250 : 6064399 : node = cl->sorted[--(cl->num_sorted)];
251 : 6064399 : *p1 = node->first_element;
252 : 6064399 : *p2 = node->second_element;
253 : 6064399 : ret = node->cost;
254 : :
255 : 6064399 : return ret;
256 : : }
257 : :
258 : :
259 : : /* Create a new empty coalesce list object and return it. */
260 : :
261 : : static inline coalesce_list *
262 : 1456099 : create_coalesce_list (void)
263 : : {
264 : 1456099 : coalesce_list *list;
265 : 1456099 : unsigned size = num_ssa_names * 3;
266 : :
267 : 1456099 : if (size < 40)
268 : 1456099 : size = 40;
269 : :
270 : 1456099 : list = (coalesce_list *) xmalloc (sizeof (struct coalesce_list));
271 : 1456099 : list->list = new coalesce_table_type (size);
272 : 1456099 : list->sorted = NULL;
273 : 1456099 : list->num_sorted = 0;
274 : 1456099 : list->cost_one_list = NULL;
275 : 1456099 : gcc_obstack_init (&list->ob);
276 : 1456099 : return list;
277 : : }
278 : :
279 : :
280 : : /* Delete coalesce list CL. */
281 : :
282 : : static inline void
283 : 1456099 : delete_coalesce_list (coalesce_list *cl)
284 : : {
285 : 1456099 : gcc_assert (cl->cost_one_list == NULL);
286 : 1456099 : delete cl->list;
287 : 1456099 : cl->list = NULL;
288 : 1456099 : free (cl->sorted);
289 : 1456099 : gcc_assert (cl->num_sorted == 0);
290 : 1456099 : obstack_free (&cl->ob, NULL);
291 : 1456099 : free (cl);
292 : 1456099 : }
293 : :
294 : : /* Return the number of unique coalesce pairs in CL. */
295 : :
296 : : static inline int
297 : 7336850 : num_coalesce_pairs (coalesce_list *cl)
298 : : {
299 : 7336850 : 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 : 6849253 : find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
308 : : {
309 : 6849253 : struct coalesce_pair p;
310 : 6849253 : coalesce_pair **slot;
311 : 6849253 : unsigned int hash;
312 : :
313 : : /* Normalize so that p1 is the smaller value. */
314 : 6849253 : if (p2 < p1)
315 : : {
316 : 3921164 : p.first_element = p2;
317 : 3921164 : p.second_element = p1;
318 : : }
319 : : else
320 : : {
321 : 2928089 : p.first_element = p1;
322 : 2928089 : p.second_element = p2;
323 : : }
324 : :
325 : 6849253 : hash = coalesce_pair_hasher::hash (&p);
326 : 6849253 : slot = cl->list->find_slot_with_hash (&p, hash, create ? INSERT : NO_INSERT);
327 : 6849253 : if (!slot)
328 : : return NULL;
329 : :
330 : 6849253 : if (!*slot)
331 : : {
332 : 6064399 : struct coalesce_pair * pair = XOBNEW (&cl->ob, struct coalesce_pair);
333 : 6064399 : gcc_assert (cl->sorted == NULL);
334 : 6064399 : pair->first_element = p.first_element;
335 : 6064399 : pair->second_element = p.second_element;
336 : 6064399 : pair->cost = 0;
337 : 6064399 : pair->index = num_coalesce_pairs (cl);
338 : 6064399 : pair->conflict_count = 0;
339 : 6064399 : *slot = pair;
340 : : }
341 : :
342 : 6849253 : return (struct coalesce_pair *) *slot;
343 : : }
344 : :
345 : : static inline void
346 : 257180 : add_cost_one_coalesce (coalesce_list *cl, int p1, int p2)
347 : : {
348 : 257180 : cost_one_pair *pair;
349 : :
350 : 257180 : pair = XOBNEW (&cl->ob, cost_one_pair);
351 : 257180 : pair->first_element = p1;
352 : 257180 : pair->second_element = p2;
353 : 257180 : pair->next = cl->cost_one_list;
354 : 257180 : cl->cost_one_list = pair;
355 : 257180 : }
356 : :
357 : :
358 : : /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
359 : :
360 : : static inline void
361 : 6858758 : add_coalesce (coalesce_list *cl, int p1, int p2, int value)
362 : : {
363 : 6858758 : coalesce_pair *node;
364 : :
365 : 6858758 : gcc_assert (cl->sorted == NULL);
366 : 6858758 : if (p1 == p2)
367 : : return;
368 : :
369 : 6849253 : 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 : 6849253 : if (node->cost < MUST_COALESCE_COST - 1)
373 : : {
374 : 6849253 : if (value < MUST_COALESCE_COST - 1)
375 : 6285111 : node->cost += value;
376 : : else
377 : 564142 : 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 : 61262087 : initialize_conflict_count (coalesce_pair *p,
388 : : ssa_conflicts *conflicts,
389 : : var_map map)
390 : : {
391 : 61262087 : int p1 = var_to_partition (map, ssa_name (p->first_element));
392 : 61262087 : 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 : 61262087 : if (conflicts->conflicts[p1] && conflicts->conflicts[p2])
398 : 716641 : p->conflict_count = bitmap_count_unique_bits (conflicts->conflicts[p1],
399 : 716641 : conflicts->conflicts[p2]);
400 : 60545446 : else if (conflicts->conflicts[p1])
401 : 143354 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p1]);
402 : 60402092 : else if (conflicts->conflicts[p2])
403 : 136399 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p2]);
404 : : else
405 : 60265693 : p->conflict_count = 0;
406 : 61262087 : }
407 : :
408 : :
409 : : /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
410 : :
411 : : static int
412 : 173823392 : compare_pairs (const void *p1, const void *p2)
413 : : {
414 : 173823392 : coalesce_pair *const *const pp1 = (coalesce_pair *const *) p1;
415 : 173823392 : coalesce_pair *const *const pp2 = (coalesce_pair *const *) p2;
416 : 173823392 : int result;
417 : :
418 : 173823392 : 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 : 173823392 : if (result == 0)
423 : : {
424 : 73539296 : if (flag_expensive_optimizations)
425 : : {
426 : : /* Lazily initialize the conflict counts as it's fairly expensive
427 : : to compute. */
428 : 40827280 : if ((*pp2)->conflict_count == 0)
429 : 30797527 : initialize_conflict_count (*pp2, conflicts_, map_);
430 : 40827280 : if ((*pp1)->conflict_count == 0)
431 : 30464560 : initialize_conflict_count (*pp1, conflicts_, map_);
432 : :
433 : 40827280 : 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 : 73539296 : if (result == 0)
439 : 64444486 : result = (*pp2)->index - (*pp1)->index;
440 : : }
441 : :
442 : 173823392 : 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 : 1272451 : sort_coalesce_list (coalesce_list *cl, ssa_conflicts *conflicts, var_map map)
456 : : {
457 : 1272451 : unsigned x, num;
458 : 1272451 : coalesce_pair *p;
459 : 1272451 : coalesce_iterator_type ppi;
460 : :
461 : 1272451 : gcc_assert (cl->sorted == NULL);
462 : :
463 : 1272451 : num = num_coalesce_pairs (cl);
464 : 1272451 : cl->num_sorted = num;
465 : 1272451 : if (num == 0)
466 : 895843 : return;
467 : :
468 : : /* Allocate a vector for the pair pointers. */
469 : 690870 : cl->sorted = XNEWVEC (coalesce_pair *, num);
470 : :
471 : : /* Populate the vector with pointers to the pairs. */
472 : 690870 : x = 0;
473 : 6755269 : FOR_EACH_PARTITION_PAIR (p, ppi, cl)
474 : 6064399 : cl->sorted[x++] = p;
475 : 690870 : gcc_assert (x == num);
476 : :
477 : : /* Already sorted. */
478 : 690870 : 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 : 376608 : conflicts_ = conflicts;
485 : 376608 : map_ = map;
486 : 376608 : qsort (cl->sorted, num, sizeof (coalesce_pair *), compare_pairs);
487 : 376608 : conflicts_ = NULL;
488 : 376608 : 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 : 1272451 : ssa_conflicts_new (unsigned size)
539 : : {
540 : 1272451 : ssa_conflicts *ptr;
541 : :
542 : 1272451 : ptr = XNEW (ssa_conflicts);
543 : 1272451 : bitmap_obstack_initialize (&ptr->obstack);
544 : 1272451 : ptr->conflicts.create (size);
545 : 1272451 : ptr->conflicts.safe_grow_cleared (size, true);
546 : 1272451 : return ptr;
547 : : }
548 : :
549 : :
550 : : /* Free storage for conflict graph PTR. */
551 : :
552 : : static inline void
553 : 1272451 : ssa_conflicts_delete (ssa_conflicts *ptr)
554 : : {
555 : 1272451 : bitmap_obstack_release (&ptr->obstack);
556 : 1272451 : ptr->conflicts.release ();
557 : 1272451 : free (ptr);
558 : 1272451 : }
559 : :
560 : :
561 : : /* Test if elements X and Y conflict in graph PTR. */
562 : :
563 : : static inline bool
564 : 5879012 : ssa_conflicts_test_p (ssa_conflicts *ptr, unsigned x, unsigned y)
565 : : {
566 : 5879012 : bitmap bx = ptr->conflicts[x];
567 : 5879012 : bitmap by = ptr->conflicts[y];
568 : :
569 : 5879012 : gcc_checking_assert (x != y);
570 : :
571 : 5879012 : if (bx)
572 : : /* Avoid the lookup if Y has no conflicts. */
573 : 1232338 : 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 : 2439894 : ssa_conflicts_add_one (ssa_conflicts *ptr, unsigned x, unsigned y)
583 : : {
584 : 2439894 : bitmap bx = ptr->conflicts[x];
585 : : /* If there are no conflicts yet, allocate the bitmap and set bit. */
586 : 2439894 : if (! bx)
587 : 1203750 : bx = ptr->conflicts[x] = BITMAP_ALLOC (&ptr->obstack);
588 : 2439894 : bitmap_set_bit (bx, y);
589 : 2439894 : }
590 : :
591 : :
592 : : /* Add conflicts between X and Y in graph PTR. */
593 : :
594 : : static inline void
595 : 1219947 : ssa_conflicts_add (ssa_conflicts *ptr, unsigned x, unsigned y)
596 : : {
597 : 1219947 : gcc_checking_assert (x != y);
598 : 1219947 : ssa_conflicts_add_one (ptr, x, y);
599 : 1219947 : ssa_conflicts_add_one (ptr, y, x);
600 : 1219947 : }
601 : :
602 : :
603 : : /* Merge all Y's conflict into X in graph PTR. */
604 : :
605 : : static inline void
606 : 5402687 : ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y)
607 : : {
608 : 5402687 : unsigned z;
609 : 5402687 : bitmap_iterator bi;
610 : 5402687 : bitmap bx = ptr->conflicts[x];
611 : 5402687 : bitmap by = ptr->conflicts[y];
612 : :
613 : 5402687 : gcc_checking_assert (x != y);
614 : 5402687 : if (! by)
615 : 4746278 : 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 : 1879428 : EXECUTE_IF_SET_IN_BITMAP (by, 0, z, bi)
621 : : {
622 : 1223019 : bitmap bz = ptr->conflicts[z];
623 : 1223019 : if (bz)
624 : : {
625 : 1223019 : bool was_there = bitmap_clear_bit (bz, y);
626 : 1223019 : gcc_checking_assert (was_there);
627 : 1223019 : bitmap_set_bit (bz, x);
628 : : }
629 : : }
630 : :
631 : 656409 : if (bx)
632 : : {
633 : : /* If X has conflicts, add Y's to X. */
634 : 552557 : bitmap_ior_into (bx, by);
635 : 552557 : BITMAP_FREE (by);
636 : 552557 : ptr->conflicts[y] = NULL;
637 : : }
638 : : else
639 : : {
640 : : /* If X has no conflicts, simply use Y's. */
641 : 103852 : ptr->conflicts[x] = by;
642 : 103852 : 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 : 1272451 : new_live_track (var_map map)
693 : : {
694 : 1272451 : live_track *ptr;
695 : 1272451 : int lim, x;
696 : :
697 : : /* Make sure there is a partition view in place. */
698 : 1272451 : gcc_assert (map->partition_to_base_index != NULL);
699 : :
700 : 1272451 : ptr = XNEW (live_track);
701 : 1272451 : ptr->map = map;
702 : 1272451 : lim = num_basevars (map);
703 : 1272451 : bitmap_obstack_initialize (&ptr->obstack);
704 : 1272451 : ptr->live_base_partitions = XNEWVEC (bitmap_head, lim);
705 : 1272451 : bitmap_initialize (&ptr->live_base_var, &ptr->obstack);
706 : 6714639 : for (x = 0; x < lim; x++)
707 : 5442188 : bitmap_initialize (&ptr->live_base_partitions[x], &ptr->obstack);
708 : 1272451 : return ptr;
709 : : }
710 : :
711 : :
712 : : /* This routine will free the memory associated with PTR. */
713 : :
714 : : static void
715 : 1272451 : delete_live_track (live_track *ptr)
716 : : {
717 : 1272451 : bitmap_obstack_release (&ptr->obstack);
718 : 1272451 : XDELETEVEC (ptr->live_base_partitions);
719 : 1272451 : XDELETE (ptr);
720 : 1272451 : }
721 : :
722 : :
723 : : /* This function will remove PARTITION from the live list in PTR. */
724 : :
725 : : static inline void
726 : 10834060 : live_track_remove_partition (live_track *ptr, int partition)
727 : : {
728 : 10834060 : int root;
729 : :
730 : 10834060 : root = basevar_index (ptr->map, partition);
731 : 10834060 : bitmap_clear_bit (&ptr->live_base_partitions[root], partition);
732 : : /* If the element list is empty, make the base variable not live either. */
733 : 10834060 : if (bitmap_empty_p (&ptr->live_base_partitions[root]))
734 : 9585743 : bitmap_clear_bit (&ptr->live_base_var, root);
735 : 10834060 : }
736 : :
737 : :
738 : : /* This function will adds PARTITION to the live list in PTR. */
739 : :
740 : : static inline void
741 : 46052206 : live_track_add_partition (live_track *ptr, int partition)
742 : : {
743 : 46052206 : int root;
744 : :
745 : 46052206 : 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 : 46052206 : if (bitmap_set_bit (&ptr->live_base_var, root))
749 : 34739230 : bitmap_clear (&ptr->live_base_partitions[root]);
750 : 46052206 : bitmap_set_bit (&ptr->live_base_partitions[root], partition);
751 : :
752 : 46052206 : }
753 : :
754 : :
755 : : /* Clear the live bit for VAR in PTR. */
756 : :
757 : : static inline void
758 : 676511 : live_track_clear_var (live_track *ptr, tree var)
759 : : {
760 : 676511 : int p;
761 : :
762 : 676511 : p = var_to_partition (ptr->map, var);
763 : 676511 : if (p != NO_PARTITION)
764 : 581409 : live_track_remove_partition (ptr, p);
765 : 676511 : }
766 : :
767 : :
768 : : /* Return TRUE if VAR is live in PTR. */
769 : :
770 : : static inline bool
771 : 2978195 : live_track_live_p (live_track *ptr, tree var)
772 : : {
773 : 2978195 : int p, root;
774 : :
775 : 2978195 : p = var_to_partition (ptr->map, var);
776 : 2978195 : if (p != NO_PARTITION)
777 : : {
778 : 2935825 : root = basevar_index (ptr->map, p);
779 : 2935825 : if (bitmap_bit_p (&ptr->live_base_var, root))
780 : 2935825 : 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 : 40356999 : live_track_process_use (live_track *ptr, tree use)
791 : : {
792 : 40356999 : int p;
793 : :
794 : 40356999 : p = var_to_partition (ptr->map, use);
795 : 40356999 : if (p == NO_PARTITION)
796 : : return;
797 : :
798 : : /* Mark as live in the appropriate live list. */
799 : 16267270 : 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 : 28611725 : live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph)
809 : : {
810 : 28611725 : int p, root;
811 : 28611725 : bitmap b;
812 : 28611725 : unsigned x;
813 : 28611725 : bitmap_iterator bi;
814 : :
815 : 28611725 : p = var_to_partition (ptr->map, def);
816 : 28611725 : if (p == NO_PARTITION)
817 : 18359074 : return;
818 : :
819 : : /* Clear the liveness bit. */
820 : 10252651 : live_track_remove_partition (ptr, p);
821 : :
822 : : /* If the bitmap isn't empty now, conflicts need to be added. */
823 : 10252651 : root = basevar_index (ptr->map, p);
824 : 10252651 : if (bitmap_bit_p (&ptr->live_base_var, root))
825 : : {
826 : 874912 : b = &ptr->live_base_partitions[root];
827 : 2094859 : EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
828 : 1219947 : 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 : 11785314 : live_track_init (live_track *ptr, bitmap init)
837 : : {
838 : 11785314 : unsigned p;
839 : 11785314 : bitmap_iterator bi;
840 : :
841 : : /* Mark all live on exit partitions. */
842 : 41570250 : EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
843 : 29784936 : live_track_add_partition (ptr, p);
844 : 11785314 : }
845 : :
846 : :
847 : : /* This routine will clear all live partitions in PTR. */
848 : :
849 : : static inline void
850 : 11785314 : 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 : 11785314 : 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 : 1272451 : build_ssa_conflict_graph (tree_live_info_p liveinfo)
866 : : {
867 : 1272451 : ssa_conflicts *graph;
868 : 1272451 : var_map map;
869 : 1272451 : basic_block bb;
870 : 1272451 : ssa_op_iter iter;
871 : 1272451 : live_track *live;
872 : 1272451 : 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 : 1272451 : if (flag_tree_coalesce_vars)
879 : 914013 : entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
880 : : else
881 : : entry = NULL;
882 : :
883 : 1272451 : map = live_var_map (liveinfo);
884 : 1272451 : graph = ssa_conflicts_new (num_var_partitions (map));
885 : :
886 : 1272451 : live = new_live_track (map);
887 : :
888 : 13057765 : for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
889 : : {
890 : : /* Start with live on exit temporaries. */
891 : 11785314 : live_track_init (live, live_on_exit (liveinfo, bb));
892 : :
893 : 11785314 : for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
894 : 190062538 : gsi_prev (&gsi))
895 : : {
896 : 89138612 : tree var;
897 : 89138612 : gimple *stmt = gsi_stmt (gsi);
898 : :
899 : 89138612 : if (is_gimple_debug (stmt))
900 : 46336894 : continue;
901 : :
902 : 42801718 : if (map->bitint)
903 : : {
904 : 81485 : 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 : 81485 : 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 : 42720233 : if (is_gimple_assign (stmt))
919 : : {
920 : 29588075 : tree lhs = gimple_assign_lhs (stmt);
921 : 29588075 : tree rhs1 = gimple_assign_rhs1 (stmt);
922 : 29588075 : if (gimple_assign_copy_p (stmt)
923 : 7945936 : && TREE_CODE (lhs) == SSA_NAME
924 : 30779107 : && TREE_CODE (rhs1) == SSA_NAME)
925 : 676472 : 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 : 42720233 : bool first = true;
939 : 65716883 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
940 : 22996650 : if (first)
941 : : first = false;
942 : : else
943 : 18206 : live_track_process_use (live, var);
944 : :
945 : 65716883 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
946 : 22996650 : live_track_process_def (live, var, graph);
947 : :
948 : 80381246 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
949 : 37661013 : 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 : 14769165 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
959 : 2983851 : gsi_next (&gsi))
960 : : {
961 : 2983851 : gphi *phi = gsi.phi ();
962 : 2983851 : tree result = PHI_RESULT (phi);
963 : 5967702 : if (virtual_operand_p (result))
964 : 5656 : continue;
965 : 2978195 : if (live_track_live_p (live, result))
966 : 2935825 : 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 : 11785314 : if (bb == entry)
977 : : {
978 : : unsigned i;
979 : : tree var;
980 : :
981 : 53809672 : FOR_EACH_SSA_NAME (i, var, cfun)
982 : : {
983 : 33627491 : if (!SSA_NAME_IS_DEFAULT_DEF (var)
984 : 3866337 : || !SSA_NAME_VAR (var)
985 : 37493828 : || VAR_P (SSA_NAME_VAR (var)))
986 : 30984466 : continue;
987 : :
988 : 2643025 : 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 : 2643025 : live_track_process_use (live, var);
993 : : }
994 : : }
995 : :
996 : 11785314 : live_track_clear_base_vars (live);
997 : : }
998 : :
999 : 1272451 : delete_live_track (live);
1000 : 1272451 : 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 : 31390842 : coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
1024 : : {
1025 : 31390842 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1026 : 27485208 : || !SSA_NAME_VAR (var)
1027 : 38141606 : || VAR_P (SSA_NAME_VAR (var)))
1028 : : return;
1029 : :
1030 : 161314 : tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var));
1031 : 161314 : if (!has_zero_uses (ssa))
1032 : : return;
1033 : :
1034 : 762 : add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var));
1035 : 762 : 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 : 1456099 : create_coalesce_list_for_region (var_map map, bitmap used_in_copy)
1047 : : {
1048 : 1456099 : gimple_stmt_iterator gsi;
1049 : 1456099 : basic_block bb;
1050 : 1456099 : coalesce_list *cl = create_coalesce_list ();
1051 : 1456099 : gimple *stmt;
1052 : 1456099 : int v1, v2, cost;
1053 : :
1054 : 14050945 : for (unsigned j = 0; map->vec_bbs.iterate (j, &bb); ++j)
1055 : : {
1056 : 12594846 : tree arg;
1057 : :
1058 : 12594846 : for (gphi_iterator gpi = gsi_start_phis (bb);
1059 : 15580040 : !gsi_end_p (gpi);
1060 : 2985194 : gsi_next (&gpi))
1061 : : {
1062 : 2985194 : gphi *phi = gpi.phi ();
1063 : 2985194 : size_t i;
1064 : 2985194 : int ver;
1065 : 2985194 : tree res;
1066 : 2985194 : bool saw_copy = false;
1067 : :
1068 : 2985194 : res = gimple_phi_result (phi);
1069 : 5970388 : if (virtual_operand_p (res))
1070 : 6059 : continue;
1071 : 2979135 : ver = SSA_NAME_VERSION (res);
1072 : 2979135 : if (map->bitint && !bitmap_bit_p (map->bitint, ver))
1073 : 717 : continue;
1074 : :
1075 : : /* Register ssa_names and coalesces between the args and the result
1076 : : of all PHI. */
1077 : 10391654 : for (i = 0; i < gimple_phi_num_args (phi); i++)
1078 : : {
1079 : 7413236 : edge e = gimple_phi_arg_edge (phi, i);
1080 : 7413236 : arg = PHI_ARG_DEF (phi, i);
1081 : 7413236 : if (TREE_CODE (arg) != SSA_NAME)
1082 : 1397821 : continue;
1083 : :
1084 : 6015415 : if (gimple_can_coalesce_p (arg, res)
1085 : 6015415 : || (e->flags & EDGE_ABNORMAL))
1086 : : {
1087 : 6015146 : saw_copy = true;
1088 : 6015146 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1089 : 6015146 : if ((e->flags & EDGE_ABNORMAL) == 0)
1090 : : {
1091 : 5821202 : int cost = coalesce_cost_edge (e);
1092 : 5821202 : if (cost == 1 && has_single_use (arg))
1093 : 256418 : add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1094 : : else
1095 : 5564784 : add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1096 : : }
1097 : : }
1098 : : }
1099 : 2978418 : if (saw_copy)
1100 : 2890448 : bitmap_set_bit (used_in_copy, ver);
1101 : : }
1102 : :
1103 : 120103394 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1104 : : {
1105 : 94913702 : stmt = gsi_stmt (gsi);
1106 : :
1107 : 94913702 : if (is_gimple_debug (stmt))
1108 : 48367310 : continue;
1109 : :
1110 : : /* Check for copy coalesces. */
1111 : 46546392 : switch (gimple_code (stmt))
1112 : : {
1113 : 31890923 : case GIMPLE_ASSIGN:
1114 : 31890923 : {
1115 : 31890923 : tree lhs = gimple_assign_lhs (stmt);
1116 : 31890923 : tree rhs1 = gimple_assign_rhs1 (stmt);
1117 : 31890923 : if (gimple_assign_ssa_name_copy_p (stmt)
1118 : 31890923 : && gimple_can_coalesce_p (lhs, rhs1))
1119 : : {
1120 : 355358 : v1 = SSA_NAME_VERSION (lhs);
1121 : 355358 : v2 = SSA_NAME_VERSION (rhs1);
1122 : 355358 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1123 : : break;
1124 : 355316 : cost = coalesce_cost_bb (bb);
1125 : 355316 : add_coalesce (cl, v1, v2, cost);
1126 : 355316 : bitmap_set_bit (used_in_copy, v1);
1127 : 355316 : bitmap_set_bit (used_in_copy, v2);
1128 : : }
1129 : : }
1130 : : break;
1131 : :
1132 : 1424251 : case GIMPLE_RETURN:
1133 : 1424251 : {
1134 : 1424251 : tree res = DECL_RESULT (current_function_decl);
1135 : 1424251 : if (VOID_TYPE_P (TREE_TYPE (res))
1136 : 1424251 : || !is_gimple_reg (res))
1137 : : break;
1138 : 647449 : tree rhs1 = gimple_return_retval (as_a <greturn *> (stmt));
1139 : 647449 : if (!rhs1)
1140 : : break;
1141 : 642292 : tree lhs = ssa_default_def (cfun, res);
1142 : 642292 : if (map->bitint && !lhs)
1143 : : break;
1144 : 641822 : gcc_assert (lhs);
1145 : 641822 : if (TREE_CODE (rhs1) == SSA_NAME
1146 : 641822 : && gimple_can_coalesce_p (lhs, rhs1))
1147 : : {
1148 : 370095 : v1 = SSA_NAME_VERSION (lhs);
1149 : 370095 : v2 = SSA_NAME_VERSION (rhs1);
1150 : 370095 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1151 : : break;
1152 : 370095 : cost = coalesce_cost_bb (bb);
1153 : 370095 : add_coalesce (cl, v1, v2, cost);
1154 : 370095 : bitmap_set_bit (used_in_copy, v1);
1155 : 370095 : bitmap_set_bit (used_in_copy, v2);
1156 : : }
1157 : : break;
1158 : : }
1159 : :
1160 : 106635 : case GIMPLE_ASM:
1161 : 106635 : {
1162 : 106635 : gasm *asm_stmt = as_a <gasm *> (stmt);
1163 : 106635 : unsigned long noutputs, i;
1164 : 106635 : unsigned long ninputs;
1165 : 106635 : tree *outputs, link;
1166 : 106635 : noutputs = gimple_asm_noutputs (asm_stmt);
1167 : 106635 : ninputs = gimple_asm_ninputs (asm_stmt);
1168 : 106635 : outputs = (tree *) alloca (noutputs * sizeof (tree));
1169 : 178375 : for (i = 0; i < noutputs; ++i)
1170 : : {
1171 : 71740 : link = gimple_asm_output_op (asm_stmt, i);
1172 : 71740 : outputs[i] = TREE_VALUE (link);
1173 : : }
1174 : :
1175 : 158711 : for (i = 0; i < ninputs; ++i)
1176 : : {
1177 : 52076 : const char *constraint;
1178 : 52076 : tree input;
1179 : 52076 : char *end;
1180 : 52076 : unsigned long match;
1181 : :
1182 : 52076 : link = gimple_asm_input_op (asm_stmt, i);
1183 : 52076 : constraint
1184 : 52076 : = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1185 : 52076 : input = TREE_VALUE (link);
1186 : :
1187 : 52076 : if (TREE_CODE (input) != SSA_NAME)
1188 : 47166 : continue;
1189 : :
1190 : 14539 : match = strtoul (constraint, &end, 10);
1191 : 14539 : if (match >= noutputs || end == constraint)
1192 : 7855 : continue;
1193 : :
1194 : 6684 : if (TREE_CODE (outputs[match]) != SSA_NAME)
1195 : 1774 : continue;
1196 : :
1197 : 4910 : v1 = SSA_NAME_VERSION (outputs[match]);
1198 : 4910 : v2 = SSA_NAME_VERSION (input);
1199 : 4910 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1200 : 0 : continue;
1201 : :
1202 : 4910 : if (gimple_can_coalesce_p (outputs[match], input))
1203 : : {
1204 : 4421 : cost = coalesce_cost (REG_BR_PROB_BASE,
1205 : 4421 : optimize_bb_for_size_p (bb));
1206 : 4421 : add_coalesce (cl, v1, v2, cost);
1207 : 4421 : bitmap_set_bit (used_in_copy, v1);
1208 : 4421 : bitmap_set_bit (used_in_copy, v2);
1209 : : }
1210 : : }
1211 : : break;
1212 : : }
1213 : :
1214 : : default:
1215 : : break;
1216 : : }
1217 : : }
1218 : : }
1219 : :
1220 : 1456099 : 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 : 6634838 : ssa_name_var_hash::hash (const_tree n)
1234 : : {
1235 : 6634838 : return DECL_UID (SSA_NAME_VAR (n));
1236 : : }
1237 : :
1238 : : inline int
1239 : 4816374 : ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
1240 : : {
1241 : 9632748 : 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 : 1450629 : populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy)
1250 : : {
1251 : 1450629 : tree var;
1252 : 1450629 : tree first;
1253 : 1450629 : int v1, v2, cost;
1254 : 1450629 : unsigned i;
1255 : :
1256 : : /* Process result decls and live on entry variables for entry into the
1257 : : coalesce list. */
1258 : 1450629 : first = NULL_TREE;
1259 : 72008119 : FOR_EACH_SSA_NAME (i, var, cfun)
1260 : : {
1261 : 97039638 : if (!virtual_operand_p (var))
1262 : : {
1263 : 31390842 : coalesce_with_default (var, cl, used_in_copy);
1264 : :
1265 : : /* Add coalesces between all the result decls. */
1266 : 31390842 : if (SSA_NAME_VAR (var)
1267 : 10656398 : && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1268 : : {
1269 : 659205 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1270 : 659205 : 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 : 31390842 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1285 : 31390842 : && (!has_zero_uses (var)
1286 : 1895281 : || (SSA_NAME_VAR (var)
1287 : 1895281 : && !VAR_P (SSA_NAME_VAR (var)))))
1288 : 3627934 : 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 : 1450629 : if (!flag_tree_coalesce_vars)
1296 : : {
1297 : 426553 : tree a;
1298 : 426553 : hash_table<ssa_name_var_hash> ssa_name_hash (10);
1299 : :
1300 : 13748395 : FOR_EACH_SSA_NAME (i, a, cfun)
1301 : : {
1302 : 12404452 : if (SSA_NAME_VAR (a)
1303 : 6463391 : && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1304 : 1755782 : && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
1305 : 234102 : || !VAR_P (SSA_NAME_VAR (a))))
1306 : : {
1307 : 1755748 : tree *slot = ssa_name_hash.find_slot (a, INSERT);
1308 : :
1309 : 1755748 : if (!*slot)
1310 : 1191606 : *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 : 564142 : const int cost
1322 : 649938 : = (VAR_P (SSA_NAME_VAR (a)) || in_lto_p)
1323 : 564142 : ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
1324 : 1128284 : add_coalesce (cl, SSA_NAME_VERSION (a),
1325 : 564142 : SSA_NAME_VERSION (*slot), cost);
1326 : 564142 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a));
1327 : 564142 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot));
1328 : : }
1329 : : }
1330 : : }
1331 : 426553 : }
1332 : 1450629 : }
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 : 6519500 : attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y,
1341 : : FILE *debug)
1342 : : {
1343 : 6519500 : int z;
1344 : 6519500 : tree var1, var2;
1345 : 6519500 : int p1, p2;
1346 : :
1347 : 6519500 : p1 = var_to_partition (map, ssa_name (x));
1348 : 6519500 : p2 = var_to_partition (map, ssa_name (y));
1349 : :
1350 : 6519500 : 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 : 6519500 : if (p1 == p2)
1359 : : {
1360 : 640488 : if (debug)
1361 : 0 : fprintf (debug, ": Already Coalesced.\n");
1362 : 640488 : return true;
1363 : : }
1364 : :
1365 : 5879012 : if (debug)
1366 : 32 : fprintf (debug, " [map: %d, %d] ", p1, p2);
1367 : :
1368 : :
1369 : 5879012 : if (!ssa_conflicts_test_p (graph, p1, p2))
1370 : : {
1371 : 5402687 : var1 = partition_to_var (map, p1);
1372 : 5402687 : var2 = partition_to_var (map, p2);
1373 : :
1374 : 5402687 : z = var_union (map, var1, var2);
1375 : 5402687 : 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 : 5402687 : if (z == p1)
1385 : 4503963 : ssa_conflicts_merge (graph, p1, p2);
1386 : : else
1387 : 898724 : ssa_conflicts_merge (graph, p2, p1);
1388 : :
1389 : 5402687 : if (debug)
1390 : 32 : fprintf (debug, ": Success -> %d\n", z);
1391 : :
1392 : 5402687 : return true;
1393 : : }
1394 : :
1395 : 476325 : 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 : 1272451 : coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
1407 : : FILE *debug)
1408 : : {
1409 : 1272451 : int x = 0, y = 0;
1410 : 1272451 : tree var1, var2;
1411 : 1272451 : int cost;
1412 : 1272451 : basic_block bb;
1413 : 1272451 : edge e;
1414 : 1272451 : 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 : 13057765 : FOR_EACH_BB_FN (bb, cfun)
1421 : : {
1422 : 28945090 : FOR_EACH_EDGE (e, ei, bb->preds)
1423 : 17159776 : if (e->flags & EDGE_ABNORMAL)
1424 : : {
1425 : 8301 : gphi_iterator gsi;
1426 : 202321 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1427 : 194020 : gsi_next (&gsi))
1428 : : {
1429 : 194020 : gphi *phi = gsi.phi ();
1430 : 194020 : tree res = PHI_RESULT (phi);
1431 : 388040 : if (virtual_operand_p (res))
1432 : 48 : continue;
1433 : 193972 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1434 : 193972 : if (SSA_NAME_IS_DEFAULT_DEF (arg)
1435 : 193972 : && (!SSA_NAME_VAR (arg)
1436 : 939 : || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1437 : 836 : continue;
1438 : :
1439 : 193136 : int v1 = SSA_NAME_VERSION (res);
1440 : 193136 : int v2 = SSA_NAME_VERSION (arg);
1441 : :
1442 : 193136 : if (debug)
1443 : 0 : fprintf (debug, "Abnormal coalesce: ");
1444 : :
1445 : 193136 : 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 : 7594030 : while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1454 : : {
1455 : 6321579 : var1 = ssa_name (x);
1456 : 6321579 : var2 = ssa_name (y);
1457 : :
1458 : : /* Assert the coalesces have the same base variable. */
1459 : 6321579 : gcc_assert (gimple_can_coalesce_p (var1, var2));
1460 : :
1461 : 6321579 : if (debug)
1462 : 32 : fprintf (debug, "Coalesce list: ");
1463 : 6321579 : attempt_coalesce (map, graph, x, y, debug);
1464 : : }
1465 : 1272451 : }
1466 : :
1467 : :
1468 : : /* Output partition map MAP with coalescing plan PART to file F. */
1469 : :
1470 : : void
1471 : 103 : dump_part_var_map (FILE *f, partition part, var_map map)
1472 : : {
1473 : 103 : int t;
1474 : 103 : unsigned x, y;
1475 : 103 : int p;
1476 : :
1477 : 103 : fprintf (f, "\nCoalescible Partition map \n\n");
1478 : :
1479 : 223 : 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 : 103 : fprintf (f, "\n");
1517 : 103 : }
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 : 24420107 : 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 : 24420107 : tree var1 = SSA_NAME_VAR (name1);
1532 : 24420107 : tree var2 = SSA_NAME_VAR (name2);
1533 : 24420107 : var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
1534 : 24420107 : var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
1535 : 24420107 : 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 : 23933008 : tree t1 = TREE_TYPE (name1);
1541 : 23933008 : tree t2 = TREE_TYPE (name2);
1542 : 23933008 : if (t1 == t2)
1543 : : {
1544 : 22003067 : check_modes:
1545 : : /* If the base variables are the same, we're good: none of the
1546 : : other tests below could possibly fail. */
1547 : 23349450 : var1 = SSA_NAME_VAR (name1);
1548 : 23349450 : var2 = SSA_NAME_VAR (name2);
1549 : 23349450 : 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 : 4450841 : bool reg1 = use_register_for_decl (name1);
1560 : 4450841 : bool reg2 = use_register_for_decl (name2);
1561 : 4450841 : 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 : 4450820 : int unsigned1, unsigned2;
1571 : 4450820 : return ((!var1 || VAR_P (var1)) && (!var2 || VAR_P (var2)))
1572 : 6209768 : || ((promote_ssa_mode (name1, &unsigned1)
1573 : 879474 : == promote_ssa_mode (name2, &unsigned2))
1574 : 879474 : && unsigned1 == unsigned2);
1575 : : }
1576 : :
1577 : : /* If alignment requirements are different, we can't coalesce. */
1578 : 3859882 : if (MINIMUM_ALIGNMENT (t1,
1579 : : var1 ? DECL_MODE (var1) : TYPE_MODE (t1),
1580 : : var1 ? LOCAL_DECL_ALIGNMENT (var1) : TYPE_ALIGN (t1))
1581 : 1929941 : != 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 : 1470912 : if (types_compatible_p (t1, t2))
1590 : 1346383 : 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 : 1456099 : compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1602 : : coalesce_list *cl)
1603 : : {
1604 : 1456099 : int parts = num_var_partitions (map);
1605 : 1456099 : 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 : 1456099 : gcc_assert (!cl->sorted);
1611 : 1456099 : coalesce_pair *node;
1612 : 1456099 : coalesce_iterator_type ppi;
1613 : 13584897 : FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1614 : : {
1615 : 6064399 : tree v1 = ssa_name (node->first_element);
1616 : 6064399 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1617 : 6064399 : tree v2 = ssa_name (node->second_element);
1618 : 6064399 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1619 : :
1620 : 6064399 : if (p1 == p2)
1621 : 511689 : continue;
1622 : :
1623 : 5552710 : partition_union (tentative, p1, p2);
1624 : : }
1625 : :
1626 : : /* We have to deal with cost one pairs too. */
1627 : 1713279 : for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1628 : : {
1629 : 257180 : tree v1 = ssa_name (co->first_element);
1630 : 257180 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1631 : 257180 : tree v2 = ssa_name (co->second_element);
1632 : 257180 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1633 : :
1634 : 257180 : if (p1 == p2)
1635 : 15143 : continue;
1636 : :
1637 : 242037 : partition_union (tentative, p1, p2);
1638 : : }
1639 : :
1640 : : /* And also with abnormal edges. */
1641 : 1456099 : basic_block bb;
1642 : 1456099 : edge e;
1643 : 1456099 : unsigned i;
1644 : 1456099 : edge_iterator ei;
1645 : 14050945 : for (i = 0; map->vec_bbs.iterate (i, &bb); ++i)
1646 : : {
1647 : 30812069 : FOR_EACH_EDGE (e, ei, bb->preds)
1648 : 18217223 : if (e->flags & EDGE_ABNORMAL)
1649 : : {
1650 : 9983 : gphi_iterator gsi;
1651 : 204003 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1652 : 194020 : gsi_next (&gsi))
1653 : : {
1654 : 194020 : gphi *phi = gsi.phi ();
1655 : 194020 : tree res = PHI_RESULT (phi);
1656 : 388040 : if (virtual_operand_p (res))
1657 : 48 : continue;
1658 : 193972 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1659 : 193972 : if (SSA_NAME_IS_DEFAULT_DEF (arg)
1660 : 193972 : && (!SSA_NAME_VAR (arg)
1661 : 939 : || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1662 : 836 : continue;
1663 : :
1664 : 193136 : int p1 = partition_find (tentative, var_to_partition (map, res));
1665 : 193136 : int p2 = partition_find (tentative, var_to_partition (map, arg));
1666 : :
1667 : 193136 : if (p1 == p2)
1668 : 191768 : continue;
1669 : :
1670 : 1368 : partition_union (tentative, p1, p2);
1671 : : }
1672 : : }
1673 : : }
1674 : :
1675 : 1456099 : if (map->bitint
1676 : 5470 : && flag_tree_coalesce_vars
1677 : 2757 : && (optimize > 1 || parts < 500))
1678 : 10307 : for (i = 0; i < (unsigned) parts; ++i)
1679 : : {
1680 : 7550 : tree s1 = partition_to_var (map, i);
1681 : 7550 : int p1 = partition_find (tentative, i);
1682 : 34319 : for (unsigned j = i + 1; j < (unsigned) parts; ++j)
1683 : : {
1684 : 26785 : tree s2 = partition_to_var (map, j);
1685 : 26785 : if (s1 == s2)
1686 : 0 : continue;
1687 : 26785 : if (tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1688 : 26785 : TYPE_SIZE (TREE_TYPE (s2))))
1689 : : {
1690 : 21600 : int p2 = partition_find (tentative, j);
1691 : :
1692 : 21600 : if (p1 == p2)
1693 : 17002 : continue;
1694 : :
1695 : 4598 : partition_union (tentative, p1, p2);
1696 : 4598 : if (partition_find (tentative, i) != p1)
1697 : : break;
1698 : : }
1699 : : }
1700 : : }
1701 : :
1702 : 1456099 : map->partition_to_base_index = XCNEWVEC (int, parts);
1703 : 1456099 : auto_vec<unsigned int> index_map (parts);
1704 : 1456099 : if (parts)
1705 : 1272451 : index_map.quick_grow (parts);
1706 : :
1707 : : const unsigned no_part = -1;
1708 : : unsigned count = parts;
1709 : 12699000 : while (count)
1710 : 11242901 : 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 : 1456099 : bitmap_iterator bi;
1718 : 12699000 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1719 : : {
1720 : 11242901 : int pidx = var_to_partition (map, ssa_name (i));
1721 : 11242901 : int base = partition_find (tentative, pidx);
1722 : 11242901 : if (index_map[base] != no_part)
1723 : 5800713 : continue;
1724 : 5442188 : index_map[base] = count++;
1725 : : }
1726 : :
1727 : 1456099 : map->num_basevars = count;
1728 : :
1729 : 12699000 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1730 : : {
1731 : 11242901 : int pidx = var_to_partition (map, ssa_name (i));
1732 : 11242901 : int base = partition_find (tentative, pidx);
1733 : 11242901 : gcc_assert (index_map[base] < count);
1734 : 11242901 : map->partition_to_base_index[pidx] = index_map[base];
1735 : : }
1736 : :
1737 : 1456099 : if (dump_file && (dump_flags & TDF_DETAILS))
1738 : 103 : dump_part_var_map (dump_file, tentative, map);
1739 : :
1740 : 1456099 : partition_delete (tentative);
1741 : 1456099 : }
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 : 2626 : coalesce_bitint (var_map map, ssa_conflicts *graph)
1752 : : {
1753 : 2626 : unsigned n = num_var_partitions (map);
1754 : 2626 : if (optimize <= 1 && n > 500)
1755 : 1771 : return;
1756 : :
1757 : 2626 : bool try_same_size = false;
1758 : 2626 : FILE *debug_file = (dump_flags & TDF_DETAILS) ? dump_file : NULL;
1759 : 10176 : for (unsigned i = 0; i < n; ++i)
1760 : : {
1761 : 7550 : tree s1 = partition_to_var (map, i);
1762 : 7550 : if ((unsigned) var_to_partition (map, s1) != i)
1763 : 2607 : continue;
1764 : 4943 : int v1 = SSA_NAME_VERSION (s1);
1765 : 14367 : for (unsigned j = i + 1; j < n; ++j)
1766 : : {
1767 : 9434 : tree s2 = partition_to_var (map, j);
1768 : 9434 : if (s1 == s2 || (unsigned) var_to_partition (map, s2) != j)
1769 : 1781 : continue;
1770 : 7653 : if (!types_compatible_p (TREE_TYPE (s1), TREE_TYPE (s2)))
1771 : : {
1772 : 3466 : if (!try_same_size
1773 : 4499 : && tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1774 : 1033 : TYPE_SIZE (TREE_TYPE (s2))))
1775 : : try_same_size = true;
1776 : 3466 : continue;
1777 : : }
1778 : 4187 : int v2 = SSA_NAME_VERSION (s2);
1779 : 4187 : if (attempt_coalesce (map, graph, v1, v2, debug_file)
1780 : 4187 : && partition_to_var (map, i) != s1)
1781 : : break;
1782 : : }
1783 : : }
1784 : :
1785 : 2626 : if (!try_same_size)
1786 : : return;
1787 : :
1788 : 855 : unsigned i;
1789 : 855 : bitmap_iterator bi;
1790 : 855 : bitmap same_type = NULL;
1791 : :
1792 : 3742 : EXECUTE_IF_SET_IN_BITMAP (map->bitint, 0, i, bi)
1793 : : {
1794 : 2887 : tree s = ssa_name (i);
1795 : 2887 : if (!SSA_NAME_VAR (s))
1796 : 1610 : continue;
1797 : 1493 : if (TREE_CODE (SSA_NAME_VAR (s)) != RESULT_DECL
1798 : 1277 : && (TREE_CODE (SSA_NAME_VAR (s)) != PARM_DECL
1799 : 1061 : || !SSA_NAME_IS_DEFAULT_DEF (s)))
1800 : 216 : continue;
1801 : 1061 : if (same_type == NULL)
1802 : 816 : same_type = BITMAP_ALLOC (NULL);
1803 : 1061 : int p = var_to_partition (map, s);
1804 : 1061 : bitmap_set_bit (same_type, p);
1805 : : }
1806 : :
1807 : 3742 : for (i = 0; i < n; ++i)
1808 : : {
1809 : 2887 : if (same_type && bitmap_bit_p (same_type, i))
1810 : 1061 : continue;
1811 : 1826 : tree s1 = partition_to_var (map, i);
1812 : 1826 : if ((unsigned) var_to_partition (map, s1) != i)
1813 : 841 : continue;
1814 : 985 : int v1 = SSA_NAME_VERSION (s1);
1815 : 5097 : for (unsigned j = i + 1; j < n; ++j)
1816 : : {
1817 : 4130 : if (same_type && bitmap_bit_p (same_type, j))
1818 : 1049 : continue;
1819 : :
1820 : 3081 : tree s2 = partition_to_var (map, j);
1821 : 3081 : if (s1 == s2 || (unsigned) var_to_partition (map, s2) != j)
1822 : 2101 : continue;
1823 : :
1824 : 980 : if (!tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1825 : 980 : TYPE_SIZE (TREE_TYPE (s2))))
1826 : 382 : continue;
1827 : :
1828 : 598 : int v2 = SSA_NAME_VERSION (s2);
1829 : 598 : if (attempt_coalesce (map, graph, v1, v2, debug_file)
1830 : 598 : && partition_to_var (map, i) != s1)
1831 : : break;
1832 : : }
1833 : : }
1834 : :
1835 : 855 : 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 : 1456099 : coalesce_ssa_name (var_map map)
1844 : : {
1845 : 1456099 : tree_live_info_p liveinfo;
1846 : 1456099 : ssa_conflicts *graph;
1847 : 1456099 : coalesce_list *cl;
1848 : 1456099 : auto_bitmap used_in_copies;
1849 : :
1850 : 1456099 : bitmap_tree_view (used_in_copies);
1851 : 1456099 : cl = create_coalesce_list_for_region (map, used_in_copies);
1852 : 1456099 : if (map->outofssa_p)
1853 : 1450629 : populate_coalesce_list_for_outofssa (cl, used_in_copies);
1854 : 1456099 : bitmap_list_view (used_in_copies);
1855 : 1456099 : if (map->bitint)
1856 : 5470 : bitmap_ior_into (used_in_copies, map->bitint);
1857 : :
1858 : 1456099 : if (dump_file && (dump_flags & TDF_DETAILS))
1859 : 103 : dump_var_map (dump_file, map);
1860 : :
1861 : 1456099 : partition_view_bitmap (map, used_in_copies);
1862 : :
1863 : 1456099 : compute_optimized_partition_bases (map, used_in_copies, cl);
1864 : :
1865 : 1456099 : if (num_var_partitions (map) < 1)
1866 : : {
1867 : 183648 : delete_coalesce_list (cl);
1868 : 183648 : return;
1869 : : }
1870 : :
1871 : 1272451 : if (dump_file && (dump_flags & TDF_DETAILS))
1872 : 64 : dump_var_map (dump_file, map);
1873 : :
1874 : 1272451 : liveinfo = calculate_live_ranges (map, false);
1875 : :
1876 : 1272451 : if (dump_file && (dump_flags & TDF_DETAILS))
1877 : 64 : dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1878 : :
1879 : : /* Build a conflict graph. */
1880 : 1272451 : graph = build_ssa_conflict_graph (liveinfo);
1881 : 1272451 : delete_tree_live_info (liveinfo);
1882 : 1272451 : if (dump_file && (dump_flags & TDF_DETAILS))
1883 : 64 : ssa_conflicts_dump (dump_file, graph);
1884 : :
1885 : 1272451 : sort_coalesce_list (cl, graph, map);
1886 : :
1887 : 1272451 : 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 : 1272451 : if (dump_file && (dump_flags & TDF_DETAILS))
1897 : 64 : dump_var_map (dump_file, map);
1898 : :
1899 : : /* Now coalesce everything in the list. */
1900 : 1272451 : coalesce_partitions (map, graph, cl,
1901 : 1272451 : ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1902 : :
1903 : 1272451 : delete_coalesce_list (cl);
1904 : :
1905 : 1272451 : if (map->bitint && flag_tree_coalesce_vars)
1906 : 2626 : coalesce_bitint (map, graph);
1907 : :
1908 : 1272451 : ssa_conflicts_delete (graph);
1909 : 1456099 : }
|
