Branch data Line data Source code
1 : : /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 : : Copyright (C) 2004-2024 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 : 8240256 : coalesce_pair_hasher::hash (const coalesce_pair *pair)
103 : : {
104 : 8240256 : hashval_t a = (hashval_t)(pair->first_element);
105 : 8240256 : hashval_t b = (hashval_t)(pair->second_element);
106 : :
107 : 1902447 : 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 : 2783693 : coalesce_pair_hasher::equal (const coalesce_pair *p1, const coalesce_pair *p2)
115 : : {
116 : 2783693 : return (p1->first_element == p2->first_element
117 : 2783693 : && 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 : 6053585 : coalesce_cost (int frequency, bool optimize_for_size)
150 : : {
151 : : /* Base costs on BB frequencies bounded by 1. */
152 : 6053585 : int cost = frequency;
153 : :
154 : 6053585 : if (!cost)
155 : 592305 : cost = 1;
156 : :
157 : 6049162 : if (optimize_for_size)
158 : 802926 : cost = 1;
159 : :
160 : 6053585 : return cost;
161 : : }
162 : :
163 : :
164 : : /* Return the cost of executing a copy instruction in basic block BB. */
165 : :
166 : : static inline int
167 : 698619 : coalesce_cost_bb (basic_block bb)
168 : : {
169 : 698619 : return coalesce_cost (bb->count.to_frequency (cfun),
170 : 698619 : 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 : 5350543 : coalesce_cost_edge (edge e)
178 : : {
179 : 5350543 : int mult = 1;
180 : :
181 : : /* Inserting copy on critical edge costs more than inserting it elsewhere. */
182 : 5350543 : if (EDGE_CRITICAL_P (e))
183 : : mult = 2;
184 : 5350543 : if (e->flags & EDGE_ABNORMAL)
185 : : return MUST_COALESCE_COST;
186 : 5350543 : if (e->flags & EDGE_EH)
187 : : {
188 : 139074 : edge e2;
189 : 139074 : edge_iterator ei;
190 : 173716 : FOR_EACH_EDGE (e2, ei, e->dest->preds)
191 : 169470 : 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 : 157885 : if (mult < 2)
197 : 157885 : 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 : 157885 : if (e2->flags & EDGE_EH)
202 : : {
203 : : mult = 5;
204 : : break;
205 : : }
206 : : }
207 : : }
208 : :
209 : 5350543 : return coalesce_cost (EDGE_FREQUENCY (e),
210 : 10701086 : 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 : 1485133 : pop_cost_one_pair (coalesce_list *cl, int *p1, int *p2)
220 : : {
221 : 1485133 : cost_one_pair *ptr;
222 : :
223 : 1485133 : ptr = cl->cost_one_list;
224 : 1485133 : if (!ptr)
225 : : return NO_BEST_COALESCE;
226 : :
227 : 239018 : *p1 = ptr->first_element;
228 : 239018 : *p2 = ptr->second_element;
229 : 239018 : cl->cost_one_list = ptr->next;
230 : :
231 : 239018 : 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 : 7079365 : pop_best_coalesce (coalesce_list *cl, int *p1, int *p2)
240 : : {
241 : 7079365 : coalesce_pair *node;
242 : 7079365 : int ret;
243 : :
244 : 7079365 : if (cl->sorted == NULL)
245 : 576430 : return pop_cost_one_pair (cl, p1, p2);
246 : :
247 : 6502935 : if (cl->num_sorted == 0)
248 : 908703 : return pop_cost_one_pair (cl, p1, p2);
249 : :
250 : 5594232 : node = cl->sorted[--(cl->num_sorted)];
251 : 5594232 : *p1 = node->first_element;
252 : 5594232 : *p2 = node->second_element;
253 : 5594232 : ret = node->cost;
254 : :
255 : 5594232 : return ret;
256 : : }
257 : :
258 : :
259 : : /* Create a new empty coalesce list object and return it. */
260 : :
261 : : static inline coalesce_list *
262 : 1421612 : create_coalesce_list (void)
263 : : {
264 : 1421612 : coalesce_list *list;
265 : 1421612 : unsigned size = num_ssa_names * 3;
266 : :
267 : 1421612 : if (size < 40)
268 : 1421612 : size = 40;
269 : :
270 : 1421612 : list = (coalesce_list *) xmalloc (sizeof (struct coalesce_list));
271 : 1421612 : list->list = new coalesce_table_type (size);
272 : 1421612 : list->sorted = NULL;
273 : 1421612 : list->num_sorted = 0;
274 : 1421612 : list->cost_one_list = NULL;
275 : 1421612 : gcc_obstack_init (&list->ob);
276 : 1421612 : return list;
277 : : }
278 : :
279 : :
280 : : /* Delete coalesce list CL. */
281 : :
282 : : static inline void
283 : 1421612 : delete_coalesce_list (coalesce_list *cl)
284 : : {
285 : 1421612 : gcc_assert (cl->cost_one_list == NULL);
286 : 1421612 : delete cl->list;
287 : 1421612 : cl->list = NULL;
288 : 1421612 : free (cl->sorted);
289 : 1421612 : gcc_assert (cl->num_sorted == 0);
290 : 1421612 : obstack_free (&cl->ob, NULL);
291 : 1421612 : free (cl);
292 : 1421612 : }
293 : :
294 : : /* Return the number of unique coalesce pairs in CL. */
295 : :
296 : : static inline int
297 : 6840347 : num_coalesce_pairs (coalesce_list *cl)
298 : : {
299 : 6840347 : 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 : 6337809 : find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
308 : : {
309 : 6337809 : struct coalesce_pair p;
310 : 6337809 : coalesce_pair **slot;
311 : 6337809 : unsigned int hash;
312 : :
313 : : /* Normalize so that p1 is the smaller value. */
314 : 6337809 : if (p2 < p1)
315 : : {
316 : 3616042 : p.first_element = p2;
317 : 3616042 : p.second_element = p1;
318 : : }
319 : : else
320 : : {
321 : 2721767 : p.first_element = p1;
322 : 2721767 : p.second_element = p2;
323 : : }
324 : :
325 : 6337809 : hash = coalesce_pair_hasher::hash (&p);
326 : 6337809 : slot = cl->list->find_slot_with_hash (&p, hash, create ? INSERT : NO_INSERT);
327 : 6337809 : if (!slot)
328 : : return NULL;
329 : :
330 : 6337809 : if (!*slot)
331 : : {
332 : 5594232 : struct coalesce_pair * pair = XOBNEW (&cl->ob, struct coalesce_pair);
333 : 5594232 : gcc_assert (cl->sorted == NULL);
334 : 5594232 : pair->first_element = p.first_element;
335 : 5594232 : pair->second_element = p.second_element;
336 : 5594232 : pair->cost = 0;
337 : 5594232 : pair->index = num_coalesce_pairs (cl);
338 : 5594232 : pair->conflict_count = 0;
339 : 5594232 : *slot = pair;
340 : : }
341 : :
342 : 6337809 : return (struct coalesce_pair *) *slot;
343 : : }
344 : :
345 : : static inline void
346 : 239018 : add_cost_one_coalesce (coalesce_list *cl, int p1, int p2)
347 : : {
348 : 239018 : cost_one_pair *pair;
349 : :
350 : 239018 : pair = XOBNEW (&cl->ob, cost_one_pair);
351 : 239018 : pair->first_element = p1;
352 : 239018 : pair->second_element = p2;
353 : 239018 : pair->next = cl->cost_one_list;
354 : 239018 : cl->cost_one_list = pair;
355 : 239018 : }
356 : :
357 : :
358 : : /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
359 : :
360 : : static inline void
361 : 6346972 : add_coalesce (coalesce_list *cl, int p1, int p2, int value)
362 : : {
363 : 6346972 : coalesce_pair *node;
364 : :
365 : 6346972 : gcc_assert (cl->sorted == NULL);
366 : 6346972 : if (p1 == p2)
367 : : return;
368 : :
369 : 6337809 : 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 : 6337809 : if (node->cost < MUST_COALESCE_COST - 1)
373 : : {
374 : 6337809 : if (value < MUST_COALESCE_COST - 1)
375 : 5806368 : node->cost += value;
376 : : else
377 : 531441 : 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 : 57728848 : initialize_conflict_count (coalesce_pair *p,
388 : : ssa_conflicts *conflicts,
389 : : var_map map)
390 : : {
391 : 57728848 : int p1 = var_to_partition (map, ssa_name (p->first_element));
392 : 57728848 : 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 : 57728848 : if (conflicts->conflicts[p1] && conflicts->conflicts[p2])
398 : 666127 : p->conflict_count = bitmap_count_unique_bits (conflicts->conflicts[p1],
399 : 666127 : conflicts->conflicts[p2]);
400 : 57062721 : else if (conflicts->conflicts[p1])
401 : 130721 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p1]);
402 : 56932000 : else if (conflicts->conflicts[p2])
403 : 125940 : p->conflict_count = bitmap_count_bits (conflicts->conflicts[p2]);
404 : : else
405 : 56806060 : p->conflict_count = 0;
406 : 57728848 : }
407 : :
408 : :
409 : : /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
410 : :
411 : : static int
412 : 157758636 : compare_pairs (const void *p1, const void *p2)
413 : : {
414 : 157758636 : coalesce_pair *const *const pp1 = (coalesce_pair *const *) p1;
415 : 157758636 : coalesce_pair *const *const pp2 = (coalesce_pair *const *) p2;
416 : 157758636 : int result;
417 : :
418 : 157758636 : 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 : 157758636 : if (result == 0)
423 : : {
424 : 68119887 : if (flag_expensive_optimizations)
425 : : {
426 : : /* Lazily initialize the conflict counts as it's fairly expensive
427 : : to compute. */
428 : 38611983 : if ((*pp2)->conflict_count == 0)
429 : 29015408 : initialize_conflict_count (*pp2, conflicts_, map_);
430 : 38611983 : if ((*pp1)->conflict_count == 0)
431 : 28713440 : initialize_conflict_count (*pp1, conflicts_, map_);
432 : :
433 : 38611983 : 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 : 68119887 : if (result == 0)
439 : 59514507 : result = (*pp2)->index - (*pp1)->index;
440 : : }
441 : :
442 : 157758636 : 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 : 1246115 : sort_coalesce_list (coalesce_list *cl, ssa_conflicts *conflicts, var_map map)
456 : : {
457 : 1246115 : unsigned x, num;
458 : 1246115 : coalesce_pair *p;
459 : 1246115 : coalesce_iterator_type ppi;
460 : :
461 : 1246115 : gcc_assert (cl->sorted == NULL);
462 : :
463 : 1246115 : num = num_coalesce_pairs (cl);
464 : 1246115 : cl->num_sorted = num;
465 : 1246115 : if (num == 0)
466 : 884837 : return;
467 : :
468 : : /* Allocate a vector for the pair pointers. */
469 : 674993 : cl->sorted = XNEWVEC (coalesce_pair *, num);
470 : :
471 : : /* Populate the vector with pointers to the pairs. */
472 : 674993 : x = 0;
473 : 6269225 : FOR_EACH_PARTITION_PAIR (p, ppi, cl)
474 : 5594232 : cl->sorted[x++] = p;
475 : 674993 : gcc_assert (x == num);
476 : :
477 : : /* Already sorted. */
478 : 674993 : 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 : 361278 : conflicts_ = conflicts;
485 : 361278 : map_ = map;
486 : 361278 : qsort (cl->sorted, num, sizeof (coalesce_pair *), compare_pairs);
487 : 361278 : conflicts_ = NULL;
488 : 361278 : map_ = NULL;
489 : : }
490 : :
491 : :
492 : : /* Send debug info for coalesce list CL to file F. */
493 : :
494 : : static void
495 : 32 : dump_coalesce_list (FILE *f, coalesce_list *cl)
496 : : {
497 : 32 : coalesce_pair *node;
498 : 32 : coalesce_iterator_type ppi;
499 : :
500 : 32 : int x;
501 : 32 : tree var;
502 : :
503 : 32 : if (cl->sorted == NULL)
504 : : {
505 : 18 : fprintf (f, "Coalesce List:\n");
506 : 18 : 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 : 32 : }
533 : :
534 : :
535 : : /* Return an empty new conflict graph for SIZE elements. */
536 : :
537 : : static inline ssa_conflicts *
538 : 1246115 : ssa_conflicts_new (unsigned size)
539 : : {
540 : 1246115 : ssa_conflicts *ptr;
541 : :
542 : 1246115 : ptr = XNEW (ssa_conflicts);
543 : 1246115 : bitmap_obstack_initialize (&ptr->obstack);
544 : 1246115 : ptr->conflicts.create (size);
545 : 1246115 : ptr->conflicts.safe_grow_cleared (size, true);
546 : 1246115 : return ptr;
547 : : }
548 : :
549 : :
550 : : /* Free storage for conflict graph PTR. */
551 : :
552 : : static inline void
553 : 1246115 : ssa_conflicts_delete (ssa_conflicts *ptr)
554 : : {
555 : 1246115 : bitmap_obstack_release (&ptr->obstack);
556 : 1246115 : ptr->conflicts.release ();
557 : 1246115 : free (ptr);
558 : 1246115 : }
559 : :
560 : :
561 : : /* Test if elements X and Y conflict in graph PTR. */
562 : :
563 : : static inline bool
564 : 5437341 : ssa_conflicts_test_p (ssa_conflicts *ptr, unsigned x, unsigned y)
565 : : {
566 : 5437341 : bitmap bx = ptr->conflicts[x];
567 : 5437341 : bitmap by = ptr->conflicts[y];
568 : :
569 : 5437341 : gcc_checking_assert (x != y);
570 : :
571 : 5437341 : if (bx)
572 : : /* Avoid the lookup if Y has no conflicts. */
573 : 1129999 : 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 : 2259056 : ssa_conflicts_add_one (ssa_conflicts *ptr, unsigned x, unsigned y)
583 : : {
584 : 2259056 : bitmap bx = ptr->conflicts[x];
585 : : /* If there are no conflicts yet, allocate the bitmap and set bit. */
586 : 2259056 : if (! bx)
587 : 1112476 : bx = ptr->conflicts[x] = BITMAP_ALLOC (&ptr->obstack);
588 : 2259056 : bitmap_set_bit (bx, y);
589 : 2259056 : }
590 : :
591 : :
592 : : /* Add conflicts between X and Y in graph PTR. */
593 : :
594 : : static inline void
595 : 1129528 : ssa_conflicts_add (ssa_conflicts *ptr, unsigned x, unsigned y)
596 : : {
597 : 1129528 : gcc_checking_assert (x != y);
598 : 1129528 : ssa_conflicts_add_one (ptr, x, y);
599 : 1129528 : ssa_conflicts_add_one (ptr, y, x);
600 : 1129528 : }
601 : :
602 : :
603 : : /* Merge all Y's conflict into X in graph PTR. */
604 : :
605 : : static inline void
606 : 5001711 : ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y)
607 : : {
608 : 5001711 : unsigned z;
609 : 5001711 : bitmap_iterator bi;
610 : 5001711 : bitmap bx = ptr->conflicts[x];
611 : 5001711 : bitmap by = ptr->conflicts[y];
612 : :
613 : 5001711 : gcc_checking_assert (x != y);
614 : 5001711 : if (! by)
615 : 4392601 : 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 : 1750316 : EXECUTE_IF_SET_IN_BITMAP (by, 0, z, bi)
621 : : {
622 : 1141206 : bitmap bz = ptr->conflicts[z];
623 : 1141206 : if (bz)
624 : : {
625 : 1141206 : bool was_there = bitmap_clear_bit (bz, y);
626 : 1141206 : gcc_checking_assert (was_there);
627 : 1141206 : bitmap_set_bit (bz, x);
628 : : }
629 : : }
630 : :
631 : 609110 : if (bx)
632 : : {
633 : : /* If X has conflicts, add Y's to X. */
634 : 511678 : bitmap_ior_into (bx, by);
635 : 511678 : BITMAP_FREE (by);
636 : 511678 : ptr->conflicts[y] = NULL;
637 : : }
638 : : else
639 : : {
640 : : /* If X has no conflicts, simply use Y's. */
641 : 97432 : ptr->conflicts[x] = by;
642 : 97432 : ptr->conflicts[y] = NULL;
643 : : }
644 : : }
645 : :
646 : :
647 : : /* Dump a conflicts graph. */
648 : :
649 : : static void
650 : 32 : ssa_conflicts_dump (FILE *file, ssa_conflicts *ptr)
651 : : {
652 : 32 : unsigned x;
653 : 32 : bitmap b;
654 : :
655 : 32 : fprintf (file, "\nConflict graph:\n");
656 : :
657 : 152 : FOR_EACH_VEC_ELT (ptr->conflicts, x, b)
658 : 88 : if (b)
659 : : {
660 : 0 : fprintf (file, "%d: ", x);
661 : 0 : dump_bitmap (file, b);
662 : : }
663 : 32 : }
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 : 1246115 : new_live_track (var_map map)
693 : : {
694 : 1246115 : live_track *ptr;
695 : 1246115 : int lim, x;
696 : :
697 : : /* Make sure there is a partition view in place. */
698 : 1246115 : gcc_assert (map->partition_to_base_index != NULL);
699 : :
700 : 1246115 : ptr = XNEW (live_track);
701 : 1246115 : ptr->map = map;
702 : 1246115 : lim = num_basevars (map);
703 : 1246115 : bitmap_obstack_initialize (&ptr->obstack);
704 : 1246115 : ptr->live_base_partitions = XNEWVEC (bitmap_head, lim);
705 : 1246115 : bitmap_initialize (&ptr->live_base_var, &ptr->obstack);
706 : 6511866 : for (x = 0; x < lim; x++)
707 : 5265751 : bitmap_initialize (&ptr->live_base_partitions[x], &ptr->obstack);
708 : 1246115 : return ptr;
709 : : }
710 : :
711 : :
712 : : /* This routine will free the memory associated with PTR. */
713 : :
714 : : static void
715 : 1246115 : delete_live_track (live_track *ptr)
716 : : {
717 : 1246115 : bitmap_obstack_release (&ptr->obstack);
718 : 1246115 : XDELETEVEC (ptr->live_base_partitions);
719 : 1246115 : XDELETE (ptr);
720 : 1246115 : }
721 : :
722 : :
723 : : /* This function will remove PARTITION from the live list in PTR. */
724 : :
725 : : static inline void
726 : 10202302 : live_track_remove_partition (live_track *ptr, int partition)
727 : : {
728 : 10202302 : int root;
729 : :
730 : 10202302 : root = basevar_index (ptr->map, partition);
731 : 10202302 : bitmap_clear_bit (&ptr->live_base_partitions[root], partition);
732 : : /* If the element list is empty, make the base variable not live either. */
733 : 10202302 : if (bitmap_empty_p (&ptr->live_base_partitions[root]))
734 : 9050137 : bitmap_clear_bit (&ptr->live_base_var, root);
735 : 10202302 : }
736 : :
737 : :
738 : : /* This function will adds PARTITION to the live list in PTR. */
739 : :
740 : : static inline void
741 : 42794404 : live_track_add_partition (live_track *ptr, int partition)
742 : : {
743 : 42794404 : int root;
744 : :
745 : 42794404 : 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 : 42794404 : if (bitmap_set_bit (&ptr->live_base_var, root))
749 : 32331477 : bitmap_clear (&ptr->live_base_partitions[root]);
750 : 42794404 : bitmap_set_bit (&ptr->live_base_partitions[root], partition);
751 : :
752 : 42794404 : }
753 : :
754 : :
755 : : /* Clear the live bit for VAR in PTR. */
756 : :
757 : : static inline void
758 : 634396 : live_track_clear_var (live_track *ptr, tree var)
759 : : {
760 : 634396 : int p;
761 : :
762 : 634396 : p = var_to_partition (ptr->map, var);
763 : 634396 : if (p != NO_PARTITION)
764 : 546969 : live_track_remove_partition (ptr, p);
765 : 634396 : }
766 : :
767 : :
768 : : /* Return TRUE if VAR is live in PTR. */
769 : :
770 : : static inline bool
771 : 2734197 : live_track_live_p (live_track *ptr, tree var)
772 : : {
773 : 2734197 : int p, root;
774 : :
775 : 2734197 : p = var_to_partition (ptr->map, var);
776 : 2734197 : if (p != NO_PARTITION)
777 : : {
778 : 2696276 : root = basevar_index (ptr->map, p);
779 : 2696276 : if (bitmap_bit_p (&ptr->live_base_var, root))
780 : 2696276 : 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 : 38100403 : live_track_process_use (live_track *ptr, tree use)
791 : : {
792 : 38100403 : int p;
793 : :
794 : 38100403 : p = var_to_partition (ptr->map, use);
795 : 38100403 : if (p == NO_PARTITION)
796 : : return;
797 : :
798 : : /* Mark as live in the appropriate live list. */
799 : 15270760 : 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 : 27158619 : live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph)
809 : : {
810 : 27158619 : int p, root;
811 : 27158619 : bitmap b;
812 : 27158619 : unsigned x;
813 : 27158619 : bitmap_iterator bi;
814 : :
815 : 27158619 : p = var_to_partition (ptr->map, def);
816 : 27158619 : if (p == NO_PARTITION)
817 : 17503286 : return;
818 : :
819 : : /* Clear the liveness bit. */
820 : 9655333 : live_track_remove_partition (ptr, p);
821 : :
822 : : /* If the bitmap isn't empty now, conflicts need to be added. */
823 : 9655333 : root = basevar_index (ptr->map, p);
824 : 9655333 : if (bitmap_bit_p (&ptr->live_base_var, root))
825 : : {
826 : 804359 : b = &ptr->live_base_partitions[root];
827 : 1933887 : EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
828 : 1129528 : 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 : 11085087 : live_track_init (live_track *ptr, bitmap init)
837 : : {
838 : 11085087 : unsigned p;
839 : 11085087 : bitmap_iterator bi;
840 : :
841 : : /* Mark all live on exit partitions. */
842 : 38608731 : EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
843 : 27523644 : live_track_add_partition (ptr, p);
844 : 11085087 : }
845 : :
846 : :
847 : : /* This routine will clear all live partitions in PTR. */
848 : :
849 : : static inline void
850 : 11085087 : 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 : 11085087 : 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 : 1246115 : build_ssa_conflict_graph (tree_live_info_p liveinfo)
866 : : {
867 : 1246115 : ssa_conflicts *graph;
868 : 1246115 : var_map map;
869 : 1246115 : basic_block bb;
870 : 1246115 : ssa_op_iter iter;
871 : 1246115 : live_track *live;
872 : 1246115 : 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 : 1246115 : if (flag_tree_coalesce_vars)
879 : 893581 : entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
880 : : else
881 : : entry = NULL;
882 : :
883 : 1246115 : map = live_var_map (liveinfo);
884 : 1246115 : graph = ssa_conflicts_new (num_var_partitions (map));
885 : :
886 : 1246115 : live = new_live_track (map);
887 : :
888 : 12331202 : for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
889 : : {
890 : : /* Start with live on exit temporaries. */
891 : 11085087 : live_track_init (live, live_on_exit (liveinfo, bb));
892 : :
893 : 11085087 : for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
894 : 169178079 : gsi_prev (&gsi))
895 : : {
896 : 79046496 : tree var;
897 : 79046496 : gimple *stmt = gsi_stmt (gsi);
898 : :
899 : : /* A copy between 2 partitions does not introduce an interference
900 : : by itself. If they did, you would never be able to coalesce
901 : : two things which are copied. If the two variables really do
902 : : conflict, they will conflict elsewhere in the program.
903 : :
904 : : This is handled by simply removing the SRC of the copy from the
905 : : live list, and processing the stmt normally. */
906 : 79046496 : if (is_gimple_assign (stmt))
907 : : {
908 : 27890557 : tree lhs = gimple_assign_lhs (stmt);
909 : 27890557 : tree rhs1 = gimple_assign_rhs1 (stmt);
910 : 27890557 : if (gimple_assign_copy_p (stmt)
911 : 7495044 : && TREE_CODE (lhs) == SSA_NAME
912 : 29014698 : && TREE_CODE (rhs1) == SSA_NAME)
913 : 634396 : live_track_clear_var (live, rhs1);
914 : : }
915 : 51155939 : else if (is_gimple_debug (stmt))
916 : 38668454 : continue;
917 : :
918 : 40378042 : if (map->bitint)
919 : : {
920 : 80310 : build_bitint_stmt_ssa_conflicts (stmt, live, graph, map->bitint,
921 : : live_track_process_def,
922 : : live_track_process_use);
923 : 80310 : continue;
924 : : }
925 : :
926 : : /* For stmts with more than one SSA_NAME definition pretend all the
927 : : SSA_NAME outputs but the first one are live at this point, so
928 : : that conflicts are added in between all those even when they are
929 : : actually not really live after the asm, because expansion might
930 : : copy those into pseudos after the asm and if multiple outputs
931 : : share the same partition, it might overwrite those that should
932 : : be live. E.g.
933 : : asm volatile (".." : "=r" (a) : "=r" (b) : "0" (a), "1" (a));
934 : : return a;
935 : : See PR70593. */
936 : 40297732 : bool first = true;
937 : 62122496 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
938 : 21824764 : if (first)
939 : : first = false;
940 : : else
941 : 18340 : live_track_process_use (live, var);
942 : :
943 : 62122496 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
944 : 21824764 : live_track_process_def (live, var, graph);
945 : :
946 : 75743512 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
947 : 35445780 : live_track_process_use (live, var);
948 : : }
949 : :
950 : : /* If result of a PHI is unused, looping over the statements will not
951 : : record any conflicts since the def was never live. Since the PHI node
952 : : is going to be translated out of SSA form, it will insert a copy.
953 : : There must be a conflict recorded between the result of the PHI and
954 : : any variables that are live. Otherwise the out-of-ssa translation
955 : : may create incorrect code. */
956 : 13824938 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
957 : 2739851 : gsi_next (&gsi))
958 : : {
959 : 2739851 : gphi *phi = gsi.phi ();
960 : 2739851 : tree result = PHI_RESULT (phi);
961 : 5479702 : if (virtual_operand_p (result))
962 : 5654 : continue;
963 : 2734197 : if (live_track_live_p (live, result))
964 : 2696276 : live_track_process_def (live, result, graph);
965 : : }
966 : :
967 : : /* Pretend there are defs for params' default defs at the start
968 : : of the (post-)entry block. This will prevent PARM_DECLs from
969 : : coalescing into the same partition. Although RESULT_DECLs'
970 : : default defs don't have a useful initial value, we have to
971 : : prevent them from coalescing with PARM_DECLs' default defs
972 : : too, otherwise assign_parms would attempt to assign different
973 : : RTL to the same partition. */
974 : 11085087 : if (bb == entry)
975 : : {
976 : : unsigned i;
977 : : tree var;
978 : :
979 : 49771859 : FOR_EACH_SSA_NAME (i, var, cfun)
980 : : {
981 : 31503129 : if (!SSA_NAME_IS_DEFAULT_DEF (var)
982 : 3769318 : || !SSA_NAME_VAR (var)
983 : 35272447 : || VAR_P (SSA_NAME_VAR (var)))
984 : 28901226 : continue;
985 : :
986 : 2601903 : live_track_process_def (live, var, graph);
987 : : /* Process a use too, so that it remains live and
988 : : conflicts with other parms' default defs, even unused
989 : : ones. */
990 : 2601903 : live_track_process_use (live, var);
991 : : }
992 : : }
993 : :
994 : 11085087 : live_track_clear_base_vars (live);
995 : : }
996 : :
997 : 1246115 : delete_live_track (live);
998 : 1246115 : return graph;
999 : : }
1000 : :
1001 : : /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
1002 : :
1003 : : static inline void
1004 : 0 : fail_abnormal_edge_coalesce (int x, int y)
1005 : : {
1006 : 0 : fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
1007 : 0 : fprintf (stderr, " which are marked as MUST COALESCE.\n");
1008 : 0 : print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
1009 : 0 : fprintf (stderr, " and ");
1010 : 0 : print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
1011 : :
1012 : 0 : internal_error ("SSA corruption");
1013 : : }
1014 : :
1015 : : /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
1016 : : and the DECL's default def is unused (i.e., it was introduced by
1017 : : create_default_def for out-of-ssa), mark VAR and the default def for
1018 : : coalescing. */
1019 : :
1020 : : static void
1021 : 29859244 : coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
1022 : : {
1023 : 29859244 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1024 : 26036914 : || !SSA_NAME_VAR (var)
1025 : 36196816 : || VAR_P (SSA_NAME_VAR (var)))
1026 : : return;
1027 : :
1028 : 156325 : tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var));
1029 : 156325 : if (!has_zero_uses (ssa))
1030 : : return;
1031 : :
1032 : 964 : add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var));
1033 : 964 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1034 : : /* Default defs will have their used_in_copy bits set at the beginning of
1035 : : populate_coalesce_list_for_outofssa. */
1036 : : }
1037 : :
1038 : :
1039 : : /* Given var_map MAP for a region, this function creates and returns a coalesce
1040 : : list as well as recording related ssa names in USED_IN_COPIES for use later
1041 : : in the out-of-ssa or live range computation process. */
1042 : :
1043 : : static coalesce_list *
1044 : 1421612 : create_coalesce_list_for_region (var_map map, bitmap used_in_copy)
1045 : : {
1046 : 1421612 : gimple_stmt_iterator gsi;
1047 : 1421612 : basic_block bb;
1048 : 1421612 : coalesce_list *cl = create_coalesce_list ();
1049 : 1421612 : gimple *stmt;
1050 : 1421612 : int v1, v2, cost;
1051 : :
1052 : 13279200 : for (unsigned j = 0; map->vec_bbs.iterate (j, &bb); ++j)
1053 : : {
1054 : 11857588 : tree arg;
1055 : :
1056 : 11857588 : for (gphi_iterator gpi = gsi_start_phis (bb);
1057 : 14598754 : !gsi_end_p (gpi);
1058 : 2741166 : gsi_next (&gpi))
1059 : : {
1060 : 2741166 : gphi *phi = gpi.phi ();
1061 : 2741166 : size_t i;
1062 : 2741166 : int ver;
1063 : 2741166 : tree res;
1064 : 2741166 : bool saw_copy = false;
1065 : :
1066 : 2741166 : res = gimple_phi_result (phi);
1067 : 5482332 : if (virtual_operand_p (res))
1068 : 6057 : continue;
1069 : 2735109 : ver = SSA_NAME_VERSION (res);
1070 : 2735109 : if (map->bitint && !bitmap_bit_p (map->bitint, ver))
1071 : 716 : continue;
1072 : :
1073 : : /* Register ssa_names and coalesces between the args and the result
1074 : : of all PHI. */
1075 : 9574302 : for (i = 0; i < gimple_phi_num_args (phi); i++)
1076 : : {
1077 : 6839909 : edge e = gimple_phi_arg_edge (phi, i);
1078 : 6839909 : arg = PHI_ARG_DEF (phi, i);
1079 : 6839909 : if (TREE_CODE (arg) != SSA_NAME)
1080 : 1295288 : continue;
1081 : :
1082 : 5544621 : if (gimple_can_coalesce_p (arg, res)
1083 : 5544621 : || (e->flags & EDGE_ABNORMAL))
1084 : : {
1085 : 5544333 : saw_copy = true;
1086 : 5544333 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1087 : 5544333 : if ((e->flags & EDGE_ABNORMAL) == 0)
1088 : : {
1089 : 5350543 : int cost = coalesce_cost_edge (e);
1090 : 5350543 : if (cost == 1 && has_single_use (arg))
1091 : 238054 : add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1092 : : else
1093 : 5112489 : add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1094 : : }
1095 : : }
1096 : : }
1097 : 2734393 : if (saw_copy)
1098 : 2657832 : bitmap_set_bit (used_in_copy, ver);
1099 : : }
1100 : :
1101 : 107909454 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1102 : : {
1103 : 84194278 : stmt = gsi_stmt (gsi);
1104 : :
1105 : 84194278 : if (is_gimple_debug (stmt))
1106 : 40196881 : continue;
1107 : :
1108 : : /* Check for copy coalesces. */
1109 : 43997397 : switch (gimple_code (stmt))
1110 : : {
1111 : 30087915 : case GIMPLE_ASSIGN:
1112 : 30087915 : {
1113 : 30087915 : tree lhs = gimple_assign_lhs (stmt);
1114 : 30087915 : tree rhs1 = gimple_assign_rhs1 (stmt);
1115 : 30087915 : if (gimple_assign_ssa_name_copy_p (stmt)
1116 : 30087915 : && gimple_can_coalesce_p (lhs, rhs1))
1117 : : {
1118 : 331477 : v1 = SSA_NAME_VERSION (lhs);
1119 : 331477 : v2 = SSA_NAME_VERSION (rhs1);
1120 : 331477 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1121 : : break;
1122 : 331443 : cost = coalesce_cost_bb (bb);
1123 : 331443 : add_coalesce (cl, v1, v2, cost);
1124 : 331443 : bitmap_set_bit (used_in_copy, v1);
1125 : 331443 : bitmap_set_bit (used_in_copy, v2);
1126 : : }
1127 : : }
1128 : : break;
1129 : :
1130 : 1392669 : case GIMPLE_RETURN:
1131 : 1392669 : {
1132 : 1392669 : tree res = DECL_RESULT (current_function_decl);
1133 : 1392669 : if (VOID_TYPE_P (TREE_TYPE (res))
1134 : 1392669 : || !is_gimple_reg (res))
1135 : : break;
1136 : 642455 : tree rhs1 = gimple_return_retval (as_a <greturn *> (stmt));
1137 : 642455 : if (!rhs1)
1138 : : break;
1139 : 637328 : tree lhs = ssa_default_def (cfun, res);
1140 : 637328 : if (map->bitint && !lhs)
1141 : : break;
1142 : 636888 : gcc_assert (lhs);
1143 : 636888 : if (TREE_CODE (rhs1) == SSA_NAME
1144 : 636888 : && gimple_can_coalesce_p (lhs, rhs1))
1145 : : {
1146 : 367174 : v1 = SSA_NAME_VERSION (lhs);
1147 : 367174 : v2 = SSA_NAME_VERSION (rhs1);
1148 : 367174 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1149 : : break;
1150 : 367174 : cost = coalesce_cost_bb (bb);
1151 : 367174 : add_coalesce (cl, v1, v2, cost);
1152 : 367174 : bitmap_set_bit (used_in_copy, v1);
1153 : 367174 : bitmap_set_bit (used_in_copy, v2);
1154 : : }
1155 : : break;
1156 : : }
1157 : :
1158 : 106173 : case GIMPLE_ASM:
1159 : 106173 : {
1160 : 106173 : gasm *asm_stmt = as_a <gasm *> (stmt);
1161 : 106173 : unsigned long noutputs, i;
1162 : 106173 : unsigned long ninputs;
1163 : 106173 : tree *outputs, link;
1164 : 106173 : noutputs = gimple_asm_noutputs (asm_stmt);
1165 : 106173 : ninputs = gimple_asm_ninputs (asm_stmt);
1166 : 106173 : outputs = (tree *) alloca (noutputs * sizeof (tree));
1167 : 178049 : for (i = 0; i < noutputs; ++i)
1168 : : {
1169 : 71876 : link = gimple_asm_output_op (asm_stmt, i);
1170 : 71876 : outputs[i] = TREE_VALUE (link);
1171 : : }
1172 : :
1173 : 158199 : for (i = 0; i < ninputs; ++i)
1174 : : {
1175 : 52026 : const char *constraint;
1176 : 52026 : tree input;
1177 : 52026 : char *end;
1178 : 52026 : unsigned long match;
1179 : :
1180 : 52026 : link = gimple_asm_input_op (asm_stmt, i);
1181 : 52026 : constraint
1182 : 52026 : = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1183 : 52026 : input = TREE_VALUE (link);
1184 : :
1185 : 52026 : if (TREE_CODE (input) != SSA_NAME)
1186 : 47071 : continue;
1187 : :
1188 : 14631 : match = strtoul (constraint, &end, 10);
1189 : 14631 : if (match >= noutputs || end == constraint)
1190 : 7860 : continue;
1191 : :
1192 : 6771 : if (TREE_CODE (outputs[match]) != SSA_NAME)
1193 : 1816 : continue;
1194 : :
1195 : 4955 : v1 = SSA_NAME_VERSION (outputs[match]);
1196 : 4955 : v2 = SSA_NAME_VERSION (input);
1197 : 4955 : if (map->bitint && !bitmap_bit_p (map->bitint, v1))
1198 : 0 : continue;
1199 : :
1200 : 4955 : if (gimple_can_coalesce_p (outputs[match], input))
1201 : : {
1202 : 4423 : cost = coalesce_cost (REG_BR_PROB_BASE,
1203 : 4423 : optimize_bb_for_size_p (bb));
1204 : 4423 : add_coalesce (cl, v1, v2, cost);
1205 : 4423 : bitmap_set_bit (used_in_copy, v1);
1206 : 4423 : bitmap_set_bit (used_in_copy, v2);
1207 : : }
1208 : : }
1209 : : break;
1210 : : }
1211 : :
1212 : : default:
1213 : : break;
1214 : : }
1215 : : }
1216 : : }
1217 : :
1218 : 1421612 : return cl;
1219 : : }
1220 : :
1221 : :
1222 : : /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1223 : :
1224 : : struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
1225 : : {
1226 : : static inline hashval_t hash (const tree_node *);
1227 : : static inline int equal (const tree_node *, const tree_node *);
1228 : : };
1229 : :
1230 : : inline hashval_t
1231 : 6153684 : ssa_name_var_hash::hash (const_tree n)
1232 : : {
1233 : 6153684 : return DECL_UID (SSA_NAME_VAR (n));
1234 : : }
1235 : :
1236 : : inline int
1237 : 4499381 : ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
1238 : : {
1239 : 8998762 : return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
1240 : : }
1241 : :
1242 : :
1243 : : /* This function populates coalesce list CL as well as recording related ssa
1244 : : names in USED_IN_COPIES for use later in the out-of-ssa process. */
1245 : :
1246 : : static void
1247 : 1416244 : populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy)
1248 : : {
1249 : 1416244 : tree var;
1250 : 1416244 : tree first;
1251 : 1416244 : int v1, v2, cost;
1252 : 1416244 : unsigned i;
1253 : :
1254 : : /* Process result decls and live on entry variables for entry into the
1255 : : coalesce list. */
1256 : 1416244 : first = NULL_TREE;
1257 : 67380431 : FOR_EACH_SSA_NAME (i, var, cfun)
1258 : : {
1259 : 91993956 : if (!virtual_operand_p (var))
1260 : : {
1261 : 29859244 : coalesce_with_default (var, cl, used_in_copy);
1262 : :
1263 : : /* Add coalesces between all the result decls. */
1264 : 29859244 : if (SSA_NAME_VAR (var)
1265 : 10159902 : && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1266 : : {
1267 : 654253 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1268 : 654253 : if (first == NULL_TREE)
1269 : : first = var;
1270 : : else
1271 : : {
1272 : 2 : gcc_assert (gimple_can_coalesce_p (var, first));
1273 : 2 : v1 = SSA_NAME_VERSION (first);
1274 : 2 : v2 = SSA_NAME_VERSION (var);
1275 : 2 : cost = coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
1276 : 2 : add_coalesce (cl, v1, v2, cost);
1277 : : }
1278 : : }
1279 : : /* Mark any default_def variables as being in the coalesce list
1280 : : since they will have to be coalesced with the base variable. If
1281 : : not marked as present, they won't be in the coalesce view. */
1282 : 29859244 : if (SSA_NAME_IS_DEFAULT_DEF (var)
1283 : 29859244 : && (!has_zero_uses (var)
1284 : 1850552 : || (SSA_NAME_VAR (var)
1285 : 1850552 : && !VAR_P (SSA_NAME_VAR (var)))))
1286 : 3573950 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1287 : : }
1288 : : }
1289 : :
1290 : : /* If this optimization is disabled, we need to coalesce all the
1291 : : names originating from the same SSA_NAME_VAR so debug info
1292 : : remains undisturbed. */
1293 : 1416244 : if (!flag_tree_coalesce_vars)
1294 : : {
1295 : 417640 : tree a;
1296 : 417640 : hash_table<ssa_name_var_hash> ssa_name_hash (10);
1297 : :
1298 : 13452630 : FOR_EACH_SSA_NAME (i, a, cfun)
1299 : : {
1300 : 12097993 : if (SSA_NAME_VAR (a)
1301 : 6310416 : && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1302 : 1705359 : && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
1303 : 227933 : || !VAR_P (SSA_NAME_VAR (a))))
1304 : : {
1305 : 1705136 : tree *slot = ssa_name_hash.find_slot (a, INSERT);
1306 : :
1307 : 1705136 : if (!*slot)
1308 : 1173695 : *slot = a;
1309 : : else
1310 : : {
1311 : : /* If the variable is a PARM_DECL or a RESULT_DECL, we
1312 : : _require_ that all the names originating from it be
1313 : : coalesced, because there must be a single partition
1314 : : containing all the names so that it can be assigned
1315 : : the canonical RTL location of the DECL safely.
1316 : : If in_lto_p, a function could have been compiled
1317 : : originally with optimizations and only the link
1318 : : performed at -O0, so we can't actually require it. */
1319 : 531441 : const int cost
1320 : 617052 : = (VAR_P (SSA_NAME_VAR (a)) || in_lto_p)
1321 : 531441 : ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
1322 : 1062882 : add_coalesce (cl, SSA_NAME_VERSION (a),
1323 : 531441 : SSA_NAME_VERSION (*slot), cost);
1324 : 531441 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a));
1325 : 531441 : bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot));
1326 : : }
1327 : : }
1328 : : }
1329 : 417640 : }
1330 : 1416244 : }
1331 : :
1332 : :
1333 : : /* Attempt to coalesce ssa versions X and Y together using the partition
1334 : : mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1335 : : DEBUG, if it is nun-NULL. */
1336 : :
1337 : : static inline bool
1338 : 6030967 : attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y,
1339 : : FILE *debug)
1340 : : {
1341 : 6030967 : int z;
1342 : 6030967 : tree var1, var2;
1343 : 6030967 : int p1, p2;
1344 : :
1345 : 6030967 : p1 = var_to_partition (map, ssa_name (x));
1346 : 6030967 : p2 = var_to_partition (map, ssa_name (y));
1347 : :
1348 : 6030967 : if (debug)
1349 : : {
1350 : 32 : fprintf (debug, "(%d)", x);
1351 : 32 : print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1352 : 32 : fprintf (debug, " & (%d)", y);
1353 : 32 : print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1354 : : }
1355 : :
1356 : 6030967 : if (p1 == p2)
1357 : : {
1358 : 593626 : if (debug)
1359 : 0 : fprintf (debug, ": Already Coalesced.\n");
1360 : 593626 : return true;
1361 : : }
1362 : :
1363 : 5437341 : if (debug)
1364 : 32 : fprintf (debug, " [map: %d, %d] ", p1, p2);
1365 : :
1366 : :
1367 : 5437341 : if (!ssa_conflicts_test_p (graph, p1, p2))
1368 : : {
1369 : 5001711 : var1 = partition_to_var (map, p1);
1370 : 5001711 : var2 = partition_to_var (map, p2);
1371 : :
1372 : 5001711 : z = var_union (map, var1, var2);
1373 : 5001711 : if (z == NO_PARTITION)
1374 : : {
1375 : 0 : if (debug)
1376 : 0 : fprintf (debug, ": Unable to perform partition union.\n");
1377 : 0 : return false;
1378 : : }
1379 : :
1380 : : /* z is the new combined partition. Remove the other partition from
1381 : : the list, and merge the conflicts. */
1382 : 5001711 : if (z == p1)
1383 : 4200858 : ssa_conflicts_merge (graph, p1, p2);
1384 : : else
1385 : 800853 : ssa_conflicts_merge (graph, p2, p1);
1386 : :
1387 : 5001711 : if (debug)
1388 : 32 : fprintf (debug, ": Success -> %d\n", z);
1389 : :
1390 : 5001711 : return true;
1391 : : }
1392 : :
1393 : 435630 : if (debug)
1394 : 0 : fprintf (debug, ": Fail due to conflict\n");
1395 : :
1396 : : return false;
1397 : : }
1398 : :
1399 : :
1400 : : /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1401 : : GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1402 : :
1403 : : static void
1404 : 1246115 : coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
1405 : : FILE *debug)
1406 : : {
1407 : 1246115 : int x = 0, y = 0;
1408 : 1246115 : tree var1, var2;
1409 : 1246115 : int cost;
1410 : 1246115 : basic_block bb;
1411 : 1246115 : edge e;
1412 : 1246115 : edge_iterator ei;
1413 : :
1414 : : /* First, coalesce all the copies across abnormal edges. These are not placed
1415 : : in the coalesce list because they do not need to be sorted, and simply
1416 : : consume extra memory/compilation time in large programs. */
1417 : :
1418 : 12331202 : FOR_EACH_BB_FN (bb, cfun)
1419 : : {
1420 : 27177931 : FOR_EACH_EDGE (e, ei, bb->preds)
1421 : 16092844 : if (e->flags & EDGE_ABNORMAL)
1422 : : {
1423 : 8066 : gphi_iterator gsi;
1424 : 201932 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1425 : 193866 : gsi_next (&gsi))
1426 : : {
1427 : 193866 : gphi *phi = gsi.phi ();
1428 : 193866 : tree res = PHI_RESULT (phi);
1429 : 387732 : if (virtual_operand_p (res))
1430 : 48 : continue;
1431 : 193818 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1432 : 193818 : if (SSA_NAME_IS_DEFAULT_DEF (arg)
1433 : 193818 : && (!SSA_NAME_VAR (arg)
1434 : 923 : || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1435 : 828 : continue;
1436 : :
1437 : 192990 : int v1 = SSA_NAME_VERSION (res);
1438 : 192990 : int v2 = SSA_NAME_VERSION (arg);
1439 : :
1440 : 192990 : if (debug)
1441 : 0 : fprintf (debug, "Abnormal coalesce: ");
1442 : :
1443 : 192990 : if (!attempt_coalesce (map, graph, v1, v2, debug))
1444 : 0 : fail_abnormal_edge_coalesce (v1, v2);
1445 : : }
1446 : : }
1447 : : }
1448 : :
1449 : : /* Now process the items in the coalesce list. */
1450 : :
1451 : 7079365 : while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1452 : : {
1453 : 5833250 : var1 = ssa_name (x);
1454 : 5833250 : var2 = ssa_name (y);
1455 : :
1456 : : /* Assert the coalesces have the same base variable. */
1457 : 5833250 : gcc_assert (gimple_can_coalesce_p (var1, var2));
1458 : :
1459 : 5833250 : if (debug)
1460 : 32 : fprintf (debug, "Coalesce list: ");
1461 : 5833250 : attempt_coalesce (map, graph, x, y, debug);
1462 : : }
1463 : 1246115 : }
1464 : :
1465 : :
1466 : : /* Output partition map MAP with coalescing plan PART to file F. */
1467 : :
1468 : : void
1469 : 50 : dump_part_var_map (FILE *f, partition part, var_map map)
1470 : : {
1471 : 50 : int t;
1472 : 50 : unsigned x, y;
1473 : 50 : int p;
1474 : :
1475 : 50 : fprintf (f, "\nCoalescible Partition map \n\n");
1476 : :
1477 : 138 : for (x = 0; x < map->num_partitions; x++)
1478 : : {
1479 : 88 : if (map->view_to_partition != NULL)
1480 : 88 : p = map->view_to_partition[x];
1481 : : else
1482 : 0 : p = x;
1483 : :
1484 : 88 : if (ssa_name (p) == NULL_TREE
1485 : 176 : || virtual_operand_p (ssa_name (p)))
1486 : 0 : continue;
1487 : :
1488 : : t = 0;
1489 : 1498 : for (y = 1; y < num_ssa_names; y++)
1490 : : {
1491 : 1410 : tree var = version_to_var (map, y);
1492 : 1410 : if (!var)
1493 : 950 : continue;
1494 : 460 : int q = var_to_partition (map, var);
1495 : 460 : p = partition_find (part, q);
1496 : 460 : gcc_assert (map->partition_to_base_index[q]
1497 : : == map->partition_to_base_index[p]);
1498 : :
1499 : 460 : if (p == (int)x)
1500 : : {
1501 : 88 : if (t++ == 0)
1502 : : {
1503 : 56 : fprintf (f, "Partition %d, base %d (", x,
1504 : : map->partition_to_base_index[q]);
1505 : 56 : print_generic_expr (f, partition_to_var (map, q), TDF_SLIM);
1506 : 56 : fprintf (f, " - ");
1507 : : }
1508 : 88 : fprintf (f, "%d ", y);
1509 : : }
1510 : : }
1511 : 88 : if (t != 0)
1512 : 56 : fprintf (f, ")\n");
1513 : : }
1514 : 50 : fprintf (f, "\n");
1515 : 50 : }
1516 : :
1517 : : /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
1518 : : coalescing together, false otherwise.
1519 : :
1520 : : This must stay consistent with compute_samebase_partition_bases and
1521 : : compute_optimized_partition_bases. */
1522 : :
1523 : : bool
1524 : 22439256 : gimple_can_coalesce_p (tree name1, tree name2)
1525 : : {
1526 : : /* First check the SSA_NAME's associated DECL. Without
1527 : : optimization, we only want to coalesce if they have the same DECL
1528 : : or both have no associated DECL. */
1529 : 22439256 : tree var1 = SSA_NAME_VAR (name1);
1530 : 22439256 : tree var2 = SSA_NAME_VAR (name2);
1531 : 22439256 : var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
1532 : 22439256 : var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
1533 : 22439256 : if (var1 != var2 && !flag_tree_coalesce_vars)
1534 : : return false;
1535 : :
1536 : : /* Now check the types. If the types are the same, then we should
1537 : : try to coalesce V1 and V2. */
1538 : 21970995 : tree t1 = TREE_TYPE (name1);
1539 : 21970995 : tree t2 = TREE_TYPE (name2);
1540 : 21970995 : if (t1 == t2)
1541 : : {
1542 : 20327087 : check_modes:
1543 : : /* If the base variables are the same, we're good: none of the
1544 : : other tests below could possibly fail. */
1545 : 21487274 : var1 = SSA_NAME_VAR (name1);
1546 : 21487274 : var2 = SSA_NAME_VAR (name2);
1547 : 21487274 : if (var1 == var2)
1548 : : return true;
1549 : :
1550 : : /* We don't want to coalesce two SSA names if one of the base
1551 : : variables is supposed to be a register while the other is
1552 : : supposed to be on the stack. Anonymous SSA names most often
1553 : : take registers, but when not optimizing, user variables
1554 : : should go on the stack, so coalescing them with the anonymous
1555 : : variable as the partition leader would end up assigning the
1556 : : user variable to a register. Don't do that! */
1557 : 4187042 : bool reg1 = use_register_for_decl (name1);
1558 : 4187042 : bool reg2 = use_register_for_decl (name2);
1559 : 4187042 : if (reg1 != reg2)
1560 : : return false;
1561 : :
1562 : : /* Check that the promoted modes and unsignedness are the same.
1563 : : We don't want to coalesce if the promoted modes would be
1564 : : different, or if they would sign-extend differently. Only
1565 : : PARM_DECLs and RESULT_DECLs have different promotion rules,
1566 : : so skip the test if both are variables, or both are anonymous
1567 : : SSA_NAMEs. */
1568 : 4187022 : int unsigned1, unsigned2;
1569 : 4187022 : return ((!var1 || VAR_P (var1)) && (!var2 || VAR_P (var2)))
1570 : 5911272 : || ((promote_ssa_mode (name1, &unsigned1)
1571 : 862125 : == promote_ssa_mode (name2, &unsigned2))
1572 : 862125 : && unsigned1 == unsigned2);
1573 : : }
1574 : :
1575 : : /* If alignment requirements are different, we can't coalesce. */
1576 : 3287816 : if (MINIMUM_ALIGNMENT (t1,
1577 : : var1 ? DECL_MODE (var1) : TYPE_MODE (t1),
1578 : : var1 ? LOCAL_DECL_ALIGNMENT (var1) : TYPE_ALIGN (t1))
1579 : 1643908 : != MINIMUM_ALIGNMENT (t2,
1580 : : var2 ? DECL_MODE (var2) : TYPE_MODE (t2),
1581 : : var2 ? LOCAL_DECL_ALIGNMENT (var2) : TYPE_ALIGN (t2)))
1582 : : return false;
1583 : :
1584 : : /* If the types are not the same, see whether they are compatible. This
1585 : : (for example) allows coalescing when the types are fundamentally the
1586 : : same, but just have different names. */
1587 : 1265881 : if (types_compatible_p (t1, t2))
1588 : 1160187 : goto check_modes;
1589 : :
1590 : : return false;
1591 : : }
1592 : :
1593 : : /* Fill in MAP's partition_to_base_index, with one index for each
1594 : : partition of SSA names USED_IN_COPIES and related by CL coalesce
1595 : : possibilities. This must match gimple_can_coalesce_p in the
1596 : : optimized case. */
1597 : :
1598 : : static void
1599 : 1421612 : compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
1600 : : coalesce_list *cl)
1601 : : {
1602 : 1421612 : int parts = num_var_partitions (map);
1603 : 1421612 : partition tentative = partition_new (parts);
1604 : :
1605 : : /* Partition the SSA versions so that, for each coalescible
1606 : : pair, both of its members are in the same partition in
1607 : : TENTATIVE. */
1608 : 1421612 : gcc_assert (!cl->sorted);
1609 : 1421612 : coalesce_pair *node;
1610 : 1421612 : coalesce_iterator_type ppi;
1611 : 12610076 : FOR_EACH_PARTITION_PAIR (node, ppi, cl)
1612 : : {
1613 : 5594232 : tree v1 = ssa_name (node->first_element);
1614 : 5594232 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1615 : 5594232 : tree v2 = ssa_name (node->second_element);
1616 : 5594232 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1617 : :
1618 : 5594232 : if (p1 == p2)
1619 : 456975 : continue;
1620 : :
1621 : 5137257 : partition_union (tentative, p1, p2);
1622 : : }
1623 : :
1624 : : /* We have to deal with cost one pairs too. */
1625 : 1660630 : for (cost_one_pair *co = cl->cost_one_list; co; co = co->next)
1626 : : {
1627 : 239018 : tree v1 = ssa_name (co->first_element);
1628 : 239018 : int p1 = partition_find (tentative, var_to_partition (map, v1));
1629 : 239018 : tree v2 = ssa_name (co->second_element);
1630 : 239018 : int p2 = partition_find (tentative, var_to_partition (map, v2));
1631 : :
1632 : 239018 : if (p1 == p2)
1633 : 15303 : continue;
1634 : :
1635 : 223715 : partition_union (tentative, p1, p2);
1636 : : }
1637 : :
1638 : : /* And also with abnormal edges. */
1639 : 1421612 : basic_block bb;
1640 : 1421612 : edge e;
1641 : 1421612 : unsigned i;
1642 : 1421612 : edge_iterator ei;
1643 : 13279200 : for (i = 0; map->vec_bbs.iterate (i, &bb); ++i)
1644 : : {
1645 : 28952874 : FOR_EACH_EDGE (e, ei, bb->preds)
1646 : 17095286 : if (e->flags & EDGE_ABNORMAL)
1647 : : {
1648 : 9721 : gphi_iterator gsi;
1649 : 203587 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1650 : 193866 : gsi_next (&gsi))
1651 : : {
1652 : 193866 : gphi *phi = gsi.phi ();
1653 : 193866 : tree res = PHI_RESULT (phi);
1654 : 387732 : if (virtual_operand_p (res))
1655 : 48 : continue;
1656 : 193818 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1657 : 193818 : if (SSA_NAME_IS_DEFAULT_DEF (arg)
1658 : 193818 : && (!SSA_NAME_VAR (arg)
1659 : 923 : || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
1660 : 828 : continue;
1661 : :
1662 : 192990 : int p1 = partition_find (tentative, var_to_partition (map, res));
1663 : 192990 : int p2 = partition_find (tentative, var_to_partition (map, arg));
1664 : :
1665 : 192990 : if (p1 == p2)
1666 : 191697 : continue;
1667 : :
1668 : 1293 : partition_union (tentative, p1, p2);
1669 : : }
1670 : : }
1671 : : }
1672 : :
1673 : 1421612 : if (map->bitint
1674 : 5368 : && flag_tree_coalesce_vars
1675 : 2693 : && (optimize > 1 || parts < 500))
1676 : 10117 : for (i = 0; i < (unsigned) parts; ++i)
1677 : : {
1678 : 7424 : tree s1 = partition_to_var (map, i);
1679 : 7424 : int p1 = partition_find (tentative, i);
1680 : 33970 : for (unsigned j = i + 1; j < (unsigned) parts; ++j)
1681 : : {
1682 : 26558 : tree s2 = partition_to_var (map, j);
1683 : 26558 : if (s1 == s2)
1684 : 0 : continue;
1685 : 26558 : if (tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1686 : 26558 : TYPE_SIZE (TREE_TYPE (s2))))
1687 : : {
1688 : 21439 : int p2 = partition_find (tentative, j);
1689 : :
1690 : 21439 : if (p1 == p2)
1691 : 16895 : continue;
1692 : :
1693 : 4544 : partition_union (tentative, p1, p2);
1694 : 4544 : if (partition_find (tentative, i) != p1)
1695 : : break;
1696 : : }
1697 : : }
1698 : : }
1699 : :
1700 : 1421612 : map->partition_to_base_index = XCNEWVEC (int, parts);
1701 : 1421612 : auto_vec<unsigned int> index_map (parts);
1702 : 1421612 : if (parts)
1703 : 1246115 : index_map.quick_grow (parts);
1704 : :
1705 : : const unsigned no_part = -1;
1706 : : unsigned count = parts;
1707 : 12054172 : while (count)
1708 : 10632560 : index_map[--count] = no_part;
1709 : :
1710 : : /* Initialize MAP's mapping from partition to base index, using
1711 : : as base indices an enumeration of the TENTATIVE partitions in
1712 : : which each SSA version ended up, so that we compute conflicts
1713 : : between all SSA versions that ended up in the same potential
1714 : : coalesce partition. */
1715 : 1421612 : bitmap_iterator bi;
1716 : 12054172 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1717 : : {
1718 : 10632560 : int pidx = var_to_partition (map, ssa_name (i));
1719 : 10632560 : int base = partition_find (tentative, pidx);
1720 : 10632560 : if (index_map[base] != no_part)
1721 : 5366809 : continue;
1722 : 5265751 : index_map[base] = count++;
1723 : : }
1724 : :
1725 : 1421612 : map->num_basevars = count;
1726 : :
1727 : 12054172 : EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
1728 : : {
1729 : 10632560 : int pidx = var_to_partition (map, ssa_name (i));
1730 : 10632560 : int base = partition_find (tentative, pidx);
1731 : 10632560 : gcc_assert (index_map[base] < count);
1732 : 10632560 : map->partition_to_base_index[pidx] = index_map[base];
1733 : : }
1734 : :
1735 : 1421612 : if (dump_file && (dump_flags & TDF_DETAILS))
1736 : 50 : dump_part_var_map (dump_file, tentative, map);
1737 : :
1738 : 1421612 : partition_delete (tentative);
1739 : 1421612 : }
1740 : :
1741 : : /* For the bitint lowering pass, try harder. Partitions which contain
1742 : : SSA_NAME default def of a PARM_DECL or have RESULT_DECL need to have
1743 : : compatible types because they will use that RESULT_DECL or PARM_DECL.
1744 : : Other partitions can have even incompatible _BitInt types, as long
1745 : : as they have the same size - those will use VAR_DECLs which are just
1746 : : arrays of the limbs. */
1747 : :
1748 : : static void
1749 : 2572 : coalesce_bitint (var_map map, ssa_conflicts *graph)
1750 : : {
1751 : 2572 : unsigned n = num_var_partitions (map);
1752 : 2572 : if (optimize <= 1 && n > 500)
1753 : 1720 : return;
1754 : :
1755 : 2572 : bool try_same_size = false;
1756 : 2572 : FILE *debug_file = (dump_flags & TDF_DETAILS) ? dump_file : NULL;
1757 : 9996 : for (unsigned i = 0; i < n; ++i)
1758 : : {
1759 : 7424 : tree s1 = partition_to_var (map, i);
1760 : 7424 : if ((unsigned) var_to_partition (map, s1) != i)
1761 : 2588 : continue;
1762 : 4836 : int v1 = SSA_NAME_VERSION (s1);
1763 : 14155 : for (unsigned j = i + 1; j < n; ++j)
1764 : : {
1765 : 9330 : tree s2 = partition_to_var (map, j);
1766 : 9330 : if (s1 == s2 || (unsigned) var_to_partition (map, s2) != j)
1767 : 1773 : continue;
1768 : 7557 : if (!types_compatible_p (TREE_TYPE (s1), TREE_TYPE (s2)))
1769 : : {
1770 : 3421 : if (!try_same_size
1771 : 4426 : && tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1772 : 1005 : TYPE_SIZE (TREE_TYPE (s2))))
1773 : : try_same_size = true;
1774 : 3421 : continue;
1775 : : }
1776 : 4136 : int v2 = SSA_NAME_VERSION (s2);
1777 : 4136 : if (attempt_coalesce (map, graph, v1, v2, debug_file)
1778 : 4136 : && partition_to_var (map, i) != s1)
1779 : : break;
1780 : : }
1781 : : }
1782 : :
1783 : 2572 : if (!try_same_size)
1784 : : return;
1785 : :
1786 : 852 : unsigned i;
1787 : 852 : bitmap_iterator bi;
1788 : 852 : bitmap same_type = NULL;
1789 : :
1790 : 3725 : EXECUTE_IF_SET_IN_BITMAP (map->bitint, 0, i, bi)
1791 : : {
1792 : 2873 : tree s = ssa_name (i);
1793 : 2873 : if (!SSA_NAME_VAR (s))
1794 : 1602 : continue;
1795 : 1486 : if (TREE_CODE (SSA_NAME_VAR (s)) != RESULT_DECL
1796 : 1271 : && (TREE_CODE (SSA_NAME_VAR (s)) != PARM_DECL
1797 : 1056 : || !SSA_NAME_IS_DEFAULT_DEF (s)))
1798 : 215 : continue;
1799 : 1056 : if (same_type == NULL)
1800 : 815 : same_type = BITMAP_ALLOC (NULL);
1801 : 1056 : int p = var_to_partition (map, s);
1802 : 1056 : bitmap_set_bit (same_type, p);
1803 : : }
1804 : :
1805 : 3725 : for (i = 0; i < n; ++i)
1806 : : {
1807 : 2873 : if (same_type && bitmap_bit_p (same_type, i))
1808 : 1056 : continue;
1809 : 1817 : tree s1 = partition_to_var (map, i);
1810 : 1817 : if ((unsigned) var_to_partition (map, s1) != i)
1811 : 837 : continue;
1812 : 980 : int v1 = SSA_NAME_VERSION (s1);
1813 : 5076 : for (unsigned j = i + 1; j < n; ++j)
1814 : : {
1815 : 4113 : if (same_type && bitmap_bit_p (same_type, j))
1816 : 1049 : continue;
1817 : :
1818 : 3064 : tree s2 = partition_to_var (map, j);
1819 : 3064 : if (s1 == s2 || (unsigned) var_to_partition (map, s2) != j)
1820 : 2091 : continue;
1821 : :
1822 : 973 : if (!tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (s1)),
1823 : 973 : TYPE_SIZE (TREE_TYPE (s2))))
1824 : 382 : continue;
1825 : :
1826 : 591 : int v2 = SSA_NAME_VERSION (s2);
1827 : 591 : if (attempt_coalesce (map, graph, v1, v2, debug_file)
1828 : 591 : && partition_to_var (map, i) != s1)
1829 : : break;
1830 : : }
1831 : : }
1832 : :
1833 : 852 : BITMAP_FREE (same_type);
1834 : : }
1835 : :
1836 : : /* Given an initial var_map MAP, coalesce variables and return a partition map
1837 : : with the resulting coalesce. Note that this function is called in either
1838 : : live range computation context or out-of-ssa context, indicated by MAP. */
1839 : :
1840 : : extern void
1841 : 1421612 : coalesce_ssa_name (var_map map)
1842 : : {
1843 : 1421612 : tree_live_info_p liveinfo;
1844 : 1421612 : ssa_conflicts *graph;
1845 : 1421612 : coalesce_list *cl;
1846 : 1421612 : auto_bitmap used_in_copies;
1847 : :
1848 : 1421612 : bitmap_tree_view (used_in_copies);
1849 : 1421612 : cl = create_coalesce_list_for_region (map, used_in_copies);
1850 : 1421612 : if (map->outofssa_p)
1851 : 1416244 : populate_coalesce_list_for_outofssa (cl, used_in_copies);
1852 : 1421612 : bitmap_list_view (used_in_copies);
1853 : 1421612 : if (map->bitint)
1854 : 5368 : bitmap_ior_into (used_in_copies, map->bitint);
1855 : :
1856 : 1421612 : if (dump_file && (dump_flags & TDF_DETAILS))
1857 : 50 : dump_var_map (dump_file, map);
1858 : :
1859 : 1421612 : partition_view_bitmap (map, used_in_copies);
1860 : :
1861 : 1421612 : compute_optimized_partition_bases (map, used_in_copies, cl);
1862 : :
1863 : 1421612 : if (num_var_partitions (map) < 1)
1864 : : {
1865 : 175497 : delete_coalesce_list (cl);
1866 : 175497 : return;
1867 : : }
1868 : :
1869 : 1246115 : if (dump_file && (dump_flags & TDF_DETAILS))
1870 : 32 : dump_var_map (dump_file, map);
1871 : :
1872 : 1246115 : liveinfo = calculate_live_ranges (map, false);
1873 : :
1874 : 1246115 : if (dump_file && (dump_flags & TDF_DETAILS))
1875 : 32 : dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1876 : :
1877 : : /* Build a conflict graph. */
1878 : 1246115 : graph = build_ssa_conflict_graph (liveinfo);
1879 : 1246115 : delete_tree_live_info (liveinfo);
1880 : 1246115 : if (dump_file && (dump_flags & TDF_DETAILS))
1881 : 32 : ssa_conflicts_dump (dump_file, graph);
1882 : :
1883 : 1246115 : sort_coalesce_list (cl, graph, map);
1884 : :
1885 : 1246115 : if (dump_file && (dump_flags & TDF_DETAILS))
1886 : : {
1887 : 32 : fprintf (dump_file, "\nAfter sorting:\n");
1888 : 32 : dump_coalesce_list (dump_file, cl);
1889 : : }
1890 : :
1891 : : /* First, coalesce all live on entry variables to their base variable.
1892 : : This will ensure the first use is coming from the correct location. */
1893 : :
1894 : 1246115 : if (dump_file && (dump_flags & TDF_DETAILS))
1895 : 32 : dump_var_map (dump_file, map);
1896 : :
1897 : : /* Now coalesce everything in the list. */
1898 : 1246115 : coalesce_partitions (map, graph, cl,
1899 : 1246115 : ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1900 : :
1901 : 1246115 : delete_coalesce_list (cl);
1902 : :
1903 : 1246115 : if (map->bitint && flag_tree_coalesce_vars)
1904 : 2572 : coalesce_bitint (map, graph);
1905 : :
1906 : 1246115 : ssa_conflicts_delete (graph);
1907 : 1421612 : }
|
