|
0
|
1 /* Coalesce SSA_NAMES together for the out-of-ssa pass.
|
|
|
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
|
|
|
3 Free Software Foundation, Inc.
|
|
|
4 Contributed by Andrew MacLeod <amacleod@redhat.com>
|
|
|
5
|
|
|
6 This file is part of GCC.
|
|
|
7
|
|
|
8 GCC is free software; you can redistribute it and/or modify
|
|
|
9 it under the terms of the GNU General Public License as published by
|
|
|
10 the Free Software Foundation; either version 3, or (at your option)
|
|
|
11 any later version.
|
|
|
12
|
|
|
13 GCC is distributed in the hope that it will be useful,
|
|
|
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
16 GNU General Public License for more details.
|
|
|
17
|
|
|
18 You should have received a copy of the GNU General Public License
|
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
|
21
|
|
|
22 #include "config.h"
|
|
|
23 #include "system.h"
|
|
|
24 #include "coretypes.h"
|
|
|
25 #include "tm.h"
|
|
|
26 #include "tree.h"
|
|
|
27 #include "flags.h"
|
|
|
28 #include "diagnostic.h"
|
|
|
29 #include "bitmap.h"
|
|
|
30 #include "tree-flow.h"
|
|
|
31 #include "hashtab.h"
|
|
|
32 #include "tree-dump.h"
|
|
|
33 #include "tree-ssa-live.h"
|
|
|
34 #include "toplev.h"
|
|
|
35
|
|
|
36
|
|
|
37 /* This set of routines implements a coalesce_list. This is an object which
|
|
|
38 is used to track pairs of ssa_names which are desirable to coalesce
|
|
|
39 together to avoid copies. Costs are associated with each pair, and when
|
|
|
40 all desired information has been collected, the object can be used to
|
|
|
41 order the pairs for processing. */
|
|
|
42
|
|
|
43 /* This structure defines a pair entry. */
|
|
|
44
|
|
|
45 typedef struct coalesce_pair
|
|
|
46 {
|
|
|
47 int first_element;
|
|
|
48 int second_element;
|
|
|
49 int cost;
|
|
|
50 } * coalesce_pair_p;
|
|
|
51 typedef const struct coalesce_pair *const_coalesce_pair_p;
|
|
|
52
|
|
|
53 typedef struct cost_one_pair_d
|
|
|
54 {
|
|
|
55 int first_element;
|
|
|
56 int second_element;
|
|
|
57 struct cost_one_pair_d *next;
|
|
|
58 } * cost_one_pair_p;
|
|
|
59
|
|
|
60 /* This structure maintains the list of coalesce pairs. */
|
|
|
61
|
|
|
62 typedef struct coalesce_list_d
|
|
|
63 {
|
|
|
64 htab_t list; /* Hash table. */
|
|
|
65 coalesce_pair_p *sorted; /* List when sorted. */
|
|
|
66 int num_sorted; /* Number in the sorted list. */
|
|
|
67 cost_one_pair_p cost_one_list;/* Single use coalesces with cost 1. */
|
|
|
68 } *coalesce_list_p;
|
|
|
69
|
|
|
70 #define NO_BEST_COALESCE -1
|
|
|
71 #define MUST_COALESCE_COST INT_MAX
|
|
|
72
|
|
|
73
|
|
|
74 /* Return cost of execution of copy instruction with FREQUENCY
|
|
|
75 possibly on CRITICAL edge and in HOT basic block. */
|
|
|
76
|
|
|
77 static inline int
|
|
|
78 coalesce_cost (int frequency, bool optimize_for_size, bool critical)
|
|
|
79 {
|
|
|
80 /* Base costs on BB frequencies bounded by 1. */
|
|
|
81 int cost = frequency;
|
|
|
82
|
|
|
83 if (!cost)
|
|
|
84 cost = 1;
|
|
|
85
|
|
|
86 if (optimize_for_size)
|
|
|
87 cost = 1;
|
|
|
88
|
|
|
89 /* Inserting copy on critical edge costs more than inserting it elsewhere. */
|
|
|
90 if (critical)
|
|
|
91 cost *= 2;
|
|
|
92 return cost;
|
|
|
93 }
|
|
|
94
|
|
|
95
|
|
|
96 /* Return the cost of executing a copy instruction in basic block BB. */
|
|
|
97
|
|
|
98 static inline int
|
|
|
99 coalesce_cost_bb (basic_block bb)
|
|
|
100 {
|
|
|
101 return coalesce_cost (bb->frequency, optimize_bb_for_size_p (bb), false);
|
|
|
102 }
|
|
|
103
|
|
|
104
|
|
|
105 /* Return the cost of executing a copy instruction on edge E. */
|
|
|
106
|
|
|
107 static inline int
|
|
|
108 coalesce_cost_edge (edge e)
|
|
|
109 {
|
|
|
110 if (e->flags & EDGE_ABNORMAL)
|
|
|
111 return MUST_COALESCE_COST;
|
|
|
112
|
|
|
113 return coalesce_cost (EDGE_FREQUENCY (e),
|
|
|
114 optimize_edge_for_size_p (e),
|
|
|
115 EDGE_CRITICAL_P (e));
|
|
|
116 }
|
|
|
117
|
|
|
118
|
|
|
119 /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
|
|
|
120 2 elements via P1 and P2. 1 is returned by the function if there is a pair,
|
|
|
121 NO_BEST_COALESCE is returned if there aren't any. */
|
|
|
122
|
|
|
123 static inline int
|
|
|
124 pop_cost_one_pair (coalesce_list_p cl, int *p1, int *p2)
|
|
|
125 {
|
|
|
126 cost_one_pair_p ptr;
|
|
|
127
|
|
|
128 ptr = cl->cost_one_list;
|
|
|
129 if (!ptr)
|
|
|
130 return NO_BEST_COALESCE;
|
|
|
131
|
|
|
132 *p1 = ptr->first_element;
|
|
|
133 *p2 = ptr->second_element;
|
|
|
134 cl->cost_one_list = ptr->next;
|
|
|
135
|
|
|
136 free (ptr);
|
|
|
137
|
|
|
138 return 1;
|
|
|
139 }
|
|
|
140
|
|
|
141 /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
|
|
|
142 2 elements via P1 and P2. Their calculated cost is returned by the function.
|
|
|
143 NO_BEST_COALESCE is returned if the coalesce list is empty. */
|
|
|
144
|
|
|
145 static inline int
|
|
|
146 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
|
|
|
147 {
|
|
|
148 coalesce_pair_p node;
|
|
|
149 int ret;
|
|
|
150
|
|
|
151 if (cl->sorted == NULL)
|
|
|
152 return pop_cost_one_pair (cl, p1, p2);
|
|
|
153
|
|
|
154 if (cl->num_sorted == 0)
|
|
|
155 return pop_cost_one_pair (cl, p1, p2);
|
|
|
156
|
|
|
157 node = cl->sorted[--(cl->num_sorted)];
|
|
|
158 *p1 = node->first_element;
|
|
|
159 *p2 = node->second_element;
|
|
|
160 ret = node->cost;
|
|
|
161 free (node);
|
|
|
162
|
|
|
163 return ret;
|
|
|
164 }
|
|
|
165
|
|
|
166
|
|
|
167 #define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
|
|
|
168
|
|
|
169 /* Hash function for coalesce list. Calculate hash for PAIR. */
|
|
|
170
|
|
|
171 static unsigned int
|
|
|
172 coalesce_pair_map_hash (const void *pair)
|
|
|
173 {
|
|
|
174 hashval_t a = (hashval_t)(((const_coalesce_pair_p)pair)->first_element);
|
|
|
175 hashval_t b = (hashval_t)(((const_coalesce_pair_p)pair)->second_element);
|
|
|
176
|
|
|
177 return COALESCE_HASH_FN (a,b);
|
|
|
178 }
|
|
|
179
|
|
|
180
|
|
|
181 /* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2,
|
|
|
182 returning TRUE if the two pairs are equivalent. */
|
|
|
183
|
|
|
184 static int
|
|
|
185 coalesce_pair_map_eq (const void *pair1, const void *pair2)
|
|
|
186 {
|
|
|
187 const_coalesce_pair_p const p1 = (const_coalesce_pair_p) pair1;
|
|
|
188 const_coalesce_pair_p const p2 = (const_coalesce_pair_p) pair2;
|
|
|
189
|
|
|
190 return (p1->first_element == p2->first_element
|
|
|
191 && p1->second_element == p2->second_element);
|
|
|
192 }
|
|
|
193
|
|
|
194
|
|
|
195 /* Create a new empty coalesce list object and return it. */
|
|
|
196
|
|
|
197 static inline coalesce_list_p
|
|
|
198 create_coalesce_list (void)
|
|
|
199 {
|
|
|
200 coalesce_list_p list;
|
|
|
201 unsigned size = num_ssa_names * 3;
|
|
|
202
|
|
|
203 if (size < 40)
|
|
|
204 size = 40;
|
|
|
205
|
|
|
206 list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
|
|
|
207 list->list = htab_create (size, coalesce_pair_map_hash,
|
|
|
208 coalesce_pair_map_eq, NULL);
|
|
|
209 list->sorted = NULL;
|
|
|
210 list->num_sorted = 0;
|
|
|
211 list->cost_one_list = NULL;
|
|
|
212 return list;
|
|
|
213 }
|
|
|
214
|
|
|
215
|
|
|
216 /* Delete coalesce list CL. */
|
|
|
217
|
|
|
218 static inline void
|
|
|
219 delete_coalesce_list (coalesce_list_p cl)
|
|
|
220 {
|
|
|
221 gcc_assert (cl->cost_one_list == NULL);
|
|
|
222 htab_delete (cl->list);
|
|
|
223 if (cl->sorted)
|
|
|
224 free (cl->sorted);
|
|
|
225 gcc_assert (cl->num_sorted == 0);
|
|
|
226 free (cl);
|
|
|
227 }
|
|
|
228
|
|
|
229
|
|
|
230 /* Find a matching coalesce pair object in CL for the pair P1 and P2. If
|
|
|
231 one isn't found, return NULL if CREATE is false, otherwise create a new
|
|
|
232 coalesce pair object and return it. */
|
|
|
233
|
|
|
234 static coalesce_pair_p
|
|
|
235 find_coalesce_pair (coalesce_list_p cl, int p1, int p2, bool create)
|
|
|
236 {
|
|
|
237 struct coalesce_pair p, *pair;
|
|
|
238 void **slot;
|
|
|
239 unsigned int hash;
|
|
|
240
|
|
|
241 /* Normalize so that p1 is the smaller value. */
|
|
|
242 if (p2 < p1)
|
|
|
243 {
|
|
|
244 p.first_element = p2;
|
|
|
245 p.second_element = p1;
|
|
|
246 }
|
|
|
247 else
|
|
|
248 {
|
|
|
249 p.first_element = p1;
|
|
|
250 p.second_element = p2;
|
|
|
251 }
|
|
|
252
|
|
|
253
|
|
|
254 hash = coalesce_pair_map_hash (&p);
|
|
|
255 pair = (struct coalesce_pair *) htab_find_with_hash (cl->list, &p, hash);
|
|
|
256
|
|
|
257 if (create && !pair)
|
|
|
258 {
|
|
|
259 gcc_assert (cl->sorted == NULL);
|
|
|
260 pair = XNEW (struct coalesce_pair);
|
|
|
261 pair->first_element = p.first_element;
|
|
|
262 pair->second_element = p.second_element;
|
|
|
263 pair->cost = 0;
|
|
|
264 slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT);
|
|
|
265 *(struct coalesce_pair **)slot = pair;
|
|
|
266 }
|
|
|
267
|
|
|
268 return pair;
|
|
|
269 }
|
|
|
270
|
|
|
271 static inline void
|
|
|
272 add_cost_one_coalesce (coalesce_list_p cl, int p1, int p2)
|
|
|
273 {
|
|
|
274 cost_one_pair_p pair;
|
|
|
275
|
|
|
276 pair = XNEW (struct cost_one_pair_d);
|
|
|
277 pair->first_element = p1;
|
|
|
278 pair->second_element = p2;
|
|
|
279 pair->next = cl->cost_one_list;
|
|
|
280 cl->cost_one_list = pair;
|
|
|
281 }
|
|
|
282
|
|
|
283
|
|
|
284 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
|
|
|
285
|
|
|
286 static inline void
|
|
|
287 add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
|
|
|
288 {
|
|
|
289 coalesce_pair_p node;
|
|
|
290
|
|
|
291 gcc_assert (cl->sorted == NULL);
|
|
|
292 if (p1 == p2)
|
|
|
293 return;
|
|
|
294
|
|
|
295 node = find_coalesce_pair (cl, p1, p2, true);
|
|
|
296
|
|
|
297 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
|
|
|
298 if (node->cost < MUST_COALESCE_COST - 1)
|
|
|
299 {
|
|
|
300 if (value < MUST_COALESCE_COST - 1)
|
|
|
301 node->cost += value;
|
|
|
302 else
|
|
|
303 node->cost = value;
|
|
|
304 }
|
|
|
305 }
|
|
|
306
|
|
|
307
|
|
|
308 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
|
|
|
309
|
|
|
310 static int
|
|
|
311 compare_pairs (const void *p1, const void *p2)
|
|
|
312 {
|
|
|
313 const_coalesce_pair_p const *const pp1 = (const_coalesce_pair_p const *) p1;
|
|
|
314 const_coalesce_pair_p const *const pp2 = (const_coalesce_pair_p const *) p2;
|
|
|
315 int result;
|
|
|
316
|
|
|
317 result = (* pp2)->cost - (* pp1)->cost;
|
|
|
318 /* Since qsort does not guarantee stability we use the elements
|
|
|
319 as a secondary key. This provides us with independence from
|
|
|
320 the host's implementation of the sorting algorithm. */
|
|
|
321 if (result == 0)
|
|
|
322 {
|
|
|
323 result = (* pp2)->first_element - (* pp1)->first_element;
|
|
|
324 if (result == 0)
|
|
|
325 result = (* pp2)->second_element - (* pp1)->second_element;
|
|
|
326 }
|
|
|
327
|
|
|
328 return result;
|
|
|
329 }
|
|
|
330
|
|
|
331
|
|
|
332 /* Return the number of unique coalesce pairs in CL. */
|
|
|
333
|
|
|
334 static inline int
|
|
|
335 num_coalesce_pairs (coalesce_list_p cl)
|
|
|
336 {
|
|
|
337 return htab_elements (cl->list);
|
|
|
338 }
|
|
|
339
|
|
|
340
|
|
|
341 /* Iterator over hash table pairs. */
|
|
|
342 typedef struct
|
|
|
343 {
|
|
|
344 htab_iterator hti;
|
|
|
345 } coalesce_pair_iterator;
|
|
|
346
|
|
|
347
|
|
|
348 /* Return first partition pair from list CL, initializing iterator ITER. */
|
|
|
349
|
|
|
350 static inline coalesce_pair_p
|
|
|
351 first_coalesce_pair (coalesce_list_p cl, coalesce_pair_iterator *iter)
|
|
|
352 {
|
|
|
353 coalesce_pair_p pair;
|
|
|
354
|
|
|
355 pair = (coalesce_pair_p) first_htab_element (&(iter->hti), cl->list);
|
|
|
356 return pair;
|
|
|
357 }
|
|
|
358
|
|
|
359
|
|
|
360 /* Return TRUE if there are no more partitions in for ITER to process. */
|
|
|
361
|
|
|
362 static inline bool
|
|
|
363 end_coalesce_pair_p (coalesce_pair_iterator *iter)
|
|
|
364 {
|
|
|
365 return end_htab_p (&(iter->hti));
|
|
|
366 }
|
|
|
367
|
|
|
368
|
|
|
369 /* Return the next partition pair to be visited by ITER. */
|
|
|
370
|
|
|
371 static inline coalesce_pair_p
|
|
|
372 next_coalesce_pair (coalesce_pair_iterator *iter)
|
|
|
373 {
|
|
|
374 coalesce_pair_p pair;
|
|
|
375
|
|
|
376 pair = (coalesce_pair_p) next_htab_element (&(iter->hti));
|
|
|
377 return pair;
|
|
|
378 }
|
|
|
379
|
|
|
380
|
|
|
381 /* Iterate over CL using ITER, returning values in PAIR. */
|
|
|
382
|
|
|
383 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
|
|
|
384 for ((PAIR) = first_coalesce_pair ((CL), &(ITER)); \
|
|
|
385 !end_coalesce_pair_p (&(ITER)); \
|
|
|
386 (PAIR) = next_coalesce_pair (&(ITER)))
|
|
|
387
|
|
|
388
|
|
|
389 /* Prepare CL for removal of preferred pairs. When finished they are sorted
|
|
|
390 in order from most important coalesce to least important. */
|
|
|
391
|
|
|
392 static void
|
|
|
393 sort_coalesce_list (coalesce_list_p cl)
|
|
|
394 {
|
|
|
395 unsigned x, num;
|
|
|
396 coalesce_pair_p p;
|
|
|
397 coalesce_pair_iterator ppi;
|
|
|
398
|
|
|
399 gcc_assert (cl->sorted == NULL);
|
|
|
400
|
|
|
401 num = num_coalesce_pairs (cl);
|
|
|
402 cl->num_sorted = num;
|
|
|
403 if (num == 0)
|
|
|
404 return;
|
|
|
405
|
|
|
406 /* Allocate a vector for the pair pointers. */
|
|
|
407 cl->sorted = XNEWVEC (coalesce_pair_p, num);
|
|
|
408
|
|
|
409 /* Populate the vector with pointers to the pairs. */
|
|
|
410 x = 0;
|
|
|
411 FOR_EACH_PARTITION_PAIR (p, ppi, cl)
|
|
|
412 cl->sorted[x++] = p;
|
|
|
413 gcc_assert (x == num);
|
|
|
414
|
|
|
415 /* Already sorted. */
|
|
|
416 if (num == 1)
|
|
|
417 return;
|
|
|
418
|
|
|
419 /* If there are only 2, just pick swap them if the order isn't correct. */
|
|
|
420 if (num == 2)
|
|
|
421 {
|
|
|
422 if (cl->sorted[0]->cost > cl->sorted[1]->cost)
|
|
|
423 {
|
|
|
424 p = cl->sorted[0];
|
|
|
425 cl->sorted[0] = cl->sorted[1];
|
|
|
426 cl->sorted[1] = p;
|
|
|
427 }
|
|
|
428 return;
|
|
|
429 }
|
|
|
430
|
|
|
431 /* Only call qsort if there are more than 2 items. */
|
|
|
432 if (num > 2)
|
|
|
433 qsort (cl->sorted, num, sizeof (coalesce_pair_p), compare_pairs);
|
|
|
434 }
|
|
|
435
|
|
|
436
|
|
|
437 /* Send debug info for coalesce list CL to file F. */
|
|
|
438
|
|
|
439 static void
|
|
|
440 dump_coalesce_list (FILE *f, coalesce_list_p cl)
|
|
|
441 {
|
|
|
442 coalesce_pair_p node;
|
|
|
443 coalesce_pair_iterator ppi;
|
|
|
444 int x;
|
|
|
445 tree var;
|
|
|
446
|
|
|
447 if (cl->sorted == NULL)
|
|
|
448 {
|
|
|
449 fprintf (f, "Coalesce List:\n");
|
|
|
450 FOR_EACH_PARTITION_PAIR (node, ppi, cl)
|
|
|
451 {
|
|
|
452 tree var1 = ssa_name (node->first_element);
|
|
|
453 tree var2 = ssa_name (node->second_element);
|
|
|
454 print_generic_expr (f, var1, TDF_SLIM);
|
|
|
455 fprintf (f, " <-> ");
|
|
|
456 print_generic_expr (f, var2, TDF_SLIM);
|
|
|
457 fprintf (f, " (%1d), ", node->cost);
|
|
|
458 fprintf (f, "\n");
|
|
|
459 }
|
|
|
460 }
|
|
|
461 else
|
|
|
462 {
|
|
|
463 fprintf (f, "Sorted Coalesce list:\n");
|
|
|
464 for (x = cl->num_sorted - 1 ; x >=0; x--)
|
|
|
465 {
|
|
|
466 node = cl->sorted[x];
|
|
|
467 fprintf (f, "(%d) ", node->cost);
|
|
|
468 var = ssa_name (node->first_element);
|
|
|
469 print_generic_expr (f, var, TDF_SLIM);
|
|
|
470 fprintf (f, " <-> ");
|
|
|
471 var = ssa_name (node->second_element);
|
|
|
472 print_generic_expr (f, var, TDF_SLIM);
|
|
|
473 fprintf (f, "\n");
|
|
|
474 }
|
|
|
475 }
|
|
|
476 }
|
|
|
477
|
|
|
478
|
|
|
479 /* This represents a conflict graph. Implemented as an array of bitmaps.
|
|
|
480 A full matrix is used for conflicts rather than just upper triangular form.
|
|
|
481 this make sit much simpler and faster to perform conflict merges. */
|
|
|
482
|
|
|
483 typedef struct ssa_conflicts_d
|
|
|
484 {
|
|
|
485 unsigned size;
|
|
|
486 bitmap *conflicts;
|
|
|
487 } * ssa_conflicts_p;
|
|
|
488
|
|
|
489
|
|
|
490 /* Return an empty new conflict graph for SIZE elements. */
|
|
|
491
|
|
|
492 static inline ssa_conflicts_p
|
|
|
493 ssa_conflicts_new (unsigned size)
|
|
|
494 {
|
|
|
495 ssa_conflicts_p ptr;
|
|
|
496
|
|
|
497 ptr = XNEW (struct ssa_conflicts_d);
|
|
|
498 ptr->conflicts = XCNEWVEC (bitmap, size);
|
|
|
499 ptr->size = size;
|
|
|
500 return ptr;
|
|
|
501 }
|
|
|
502
|
|
|
503
|
|
|
504 /* Free storage for conflict graph PTR. */
|
|
|
505
|
|
|
506 static inline void
|
|
|
507 ssa_conflicts_delete (ssa_conflicts_p ptr)
|
|
|
508 {
|
|
|
509 unsigned x;
|
|
|
510 for (x = 0; x < ptr->size; x++)
|
|
|
511 if (ptr->conflicts[x])
|
|
|
512 BITMAP_FREE (ptr->conflicts[x]);
|
|
|
513
|
|
|
514 free (ptr->conflicts);
|
|
|
515 free (ptr);
|
|
|
516 }
|
|
|
517
|
|
|
518
|
|
|
519 /* Test if elements X and Y conflict in graph PTR. */
|
|
|
520
|
|
|
521 static inline bool
|
|
|
522 ssa_conflicts_test_p (ssa_conflicts_p ptr, unsigned x, unsigned y)
|
|
|
523 {
|
|
|
524 bitmap b;
|
|
|
525
|
|
|
526 #ifdef ENABLE_CHECKING
|
|
|
527 gcc_assert (x < ptr->size);
|
|
|
528 gcc_assert (y < ptr->size);
|
|
|
529 gcc_assert (x != y);
|
|
|
530 #endif
|
|
|
531
|
|
|
532 b = ptr->conflicts[x];
|
|
|
533 if (b)
|
|
|
534 /* Avoid the lookup if Y has no conflicts. */
|
|
|
535 return ptr->conflicts[y] ? bitmap_bit_p (b, y) : false;
|
|
|
536 else
|
|
|
537 return false;
|
|
|
538 }
|
|
|
539
|
|
|
540
|
|
|
541 /* Add a conflict with Y to the bitmap for X in graph PTR. */
|
|
|
542
|
|
|
543 static inline void
|
|
|
544 ssa_conflicts_add_one (ssa_conflicts_p ptr, unsigned x, unsigned y)
|
|
|
545 {
|
|
|
546 /* If there are no conflicts yet, allocate the bitmap and set bit. */
|
|
|
547 if (!ptr->conflicts[x])
|
|
|
548 ptr->conflicts[x] = BITMAP_ALLOC (NULL);
|
|
|
549 bitmap_set_bit (ptr->conflicts[x], y);
|
|
|
550 }
|
|
|
551
|
|
|
552
|
|
|
553 /* Add conflicts between X and Y in graph PTR. */
|
|
|
554
|
|
|
555 static inline void
|
|
|
556 ssa_conflicts_add (ssa_conflicts_p ptr, unsigned x, unsigned y)
|
|
|
557 {
|
|
|
558 #ifdef ENABLE_CHECKING
|
|
|
559 gcc_assert (x < ptr->size);
|
|
|
560 gcc_assert (y < ptr->size);
|
|
|
561 gcc_assert (x != y);
|
|
|
562 #endif
|
|
|
563 ssa_conflicts_add_one (ptr, x, y);
|
|
|
564 ssa_conflicts_add_one (ptr, y, x);
|
|
|
565 }
|
|
|
566
|
|
|
567
|
|
|
568 /* Merge all Y's conflict into X in graph PTR. */
|
|
|
569
|
|
|
570 static inline void
|
|
|
571 ssa_conflicts_merge (ssa_conflicts_p ptr, unsigned x, unsigned y)
|
|
|
572 {
|
|
|
573 unsigned z;
|
|
|
574 bitmap_iterator bi;
|
|
|
575
|
|
|
576 gcc_assert (x != y);
|
|
|
577 if (!(ptr->conflicts[y]))
|
|
|
578 return;
|
|
|
579
|
|
|
580 /* Add a conflict between X and every one Y has. If the bitmap doesn't
|
|
|
581 exist, then it has already been coalesced, and we don't need to add a
|
|
|
582 conflict. */
|
|
|
583 EXECUTE_IF_SET_IN_BITMAP (ptr->conflicts[y], 0, z, bi)
|
|
|
584 if (ptr->conflicts[z])
|
|
|
585 bitmap_set_bit (ptr->conflicts[z], x);
|
|
|
586
|
|
|
587 if (ptr->conflicts[x])
|
|
|
588 {
|
|
|
589 /* If X has conflicts, add Y's to X. */
|
|
|
590 bitmap_ior_into (ptr->conflicts[x], ptr->conflicts[y]);
|
|
|
591 BITMAP_FREE (ptr->conflicts[y]);
|
|
|
592 }
|
|
|
593 else
|
|
|
594 {
|
|
|
595 /* If X has no conflicts, simply use Y's. */
|
|
|
596 ptr->conflicts[x] = ptr->conflicts[y];
|
|
|
597 ptr->conflicts[y] = NULL;
|
|
|
598 }
|
|
|
599 }
|
|
|
600
|
|
|
601
|
|
|
602 /* Dump a conflicts graph. */
|
|
|
603
|
|
|
604 static void
|
|
|
605 ssa_conflicts_dump (FILE *file, ssa_conflicts_p ptr)
|
|
|
606 {
|
|
|
607 unsigned x;
|
|
|
608
|
|
|
609 fprintf (file, "\nConflict graph:\n");
|
|
|
610
|
|
|
611 for (x = 0; x < ptr->size; x++)
|
|
|
612 if (ptr->conflicts[x])
|
|
|
613 {
|
|
|
614 fprintf (dump_file, "%d: ", x);
|
|
|
615 dump_bitmap (file, ptr->conflicts[x]);
|
|
|
616 }
|
|
|
617 }
|
|
|
618
|
|
|
619
|
|
|
620 /* This structure is used to efficiently record the current status of live
|
|
|
621 SSA_NAMES when building a conflict graph.
|
|
|
622 LIVE_BASE_VAR has a bit set for each base variable which has at least one
|
|
|
623 ssa version live.
|
|
|
624 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
|
|
|
625 index, and is used to track what partitions of each base variable are
|
|
|
626 live. This makes it easy to add conflicts between just live partitions
|
|
|
627 with the same base variable.
|
|
|
628 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
|
|
|
629 marked as being live. This delays clearing of these bitmaps until
|
|
|
630 they are actually needed again. */
|
|
|
631
|
|
|
632 typedef struct live_track_d
|
|
|
633 {
|
|
|
634 bitmap live_base_var; /* Indicates if a basevar is live. */
|
|
|
635 bitmap *live_base_partitions; /* Live partitions for each basevar. */
|
|
|
636 var_map map; /* Var_map being used for partition mapping. */
|
|
|
637 } * live_track_p;
|
|
|
638
|
|
|
639
|
|
|
640 /* This routine will create a new live track structure based on the partitions
|
|
|
641 in MAP. */
|
|
|
642
|
|
|
643 static live_track_p
|
|
|
644 new_live_track (var_map map)
|
|
|
645 {
|
|
|
646 live_track_p ptr;
|
|
|
647 int lim, x;
|
|
|
648
|
|
|
649 /* Make sure there is a partition view in place. */
|
|
|
650 gcc_assert (map->partition_to_base_index != NULL);
|
|
|
651
|
|
|
652 ptr = (live_track_p) xmalloc (sizeof (struct live_track_d));
|
|
|
653 ptr->map = map;
|
|
|
654 lim = num_basevars (map);
|
|
|
655 ptr->live_base_partitions = (bitmap *) xmalloc(sizeof (bitmap *) * lim);
|
|
|
656 ptr->live_base_var = BITMAP_ALLOC (NULL);
|
|
|
657 for (x = 0; x < lim; x++)
|
|
|
658 ptr->live_base_partitions[x] = BITMAP_ALLOC (NULL);
|
|
|
659 return ptr;
|
|
|
660 }
|
|
|
661
|
|
|
662
|
|
|
663 /* This routine will free the memory associated with PTR. */
|
|
|
664
|
|
|
665 static void
|
|
|
666 delete_live_track (live_track_p ptr)
|
|
|
667 {
|
|
|
668 int x, lim;
|
|
|
669
|
|
|
670 lim = num_basevars (ptr->map);
|
|
|
671 for (x = 0; x < lim; x++)
|
|
|
672 BITMAP_FREE (ptr->live_base_partitions[x]);
|
|
|
673 BITMAP_FREE (ptr->live_base_var);
|
|
|
674 free (ptr->live_base_partitions);
|
|
|
675 free (ptr);
|
|
|
676 }
|
|
|
677
|
|
|
678
|
|
|
679 /* This function will remove PARTITION from the live list in PTR. */
|
|
|
680
|
|
|
681 static inline void
|
|
|
682 live_track_remove_partition (live_track_p ptr, int partition)
|
|
|
683 {
|
|
|
684 int root;
|
|
|
685
|
|
|
686 root = basevar_index (ptr->map, partition);
|
|
|
687 bitmap_clear_bit (ptr->live_base_partitions[root], partition);
|
|
|
688 /* If the element list is empty, make the base variable not live either. */
|
|
|
689 if (bitmap_empty_p (ptr->live_base_partitions[root]))
|
|
|
690 bitmap_clear_bit (ptr->live_base_var, root);
|
|
|
691 }
|
|
|
692
|
|
|
693
|
|
|
694 /* This function will adds PARTITION to the live list in PTR. */
|
|
|
695
|
|
|
696 static inline void
|
|
|
697 live_track_add_partition (live_track_p ptr, int partition)
|
|
|
698 {
|
|
|
699 int root;
|
|
|
700
|
|
|
701 root = basevar_index (ptr->map, partition);
|
|
|
702 /* If this base var wasn't live before, it is now. Clear the element list
|
|
|
703 since it was delayed until needed. */
|
|
|
704 if (!bitmap_bit_p (ptr->live_base_var, root))
|
|
|
705 {
|
|
|
706 bitmap_set_bit (ptr->live_base_var, root);
|
|
|
707 bitmap_clear (ptr->live_base_partitions[root]);
|
|
|
708 }
|
|
|
709 bitmap_set_bit (ptr->live_base_partitions[root], partition);
|
|
|
710
|
|
|
711 }
|
|
|
712
|
|
|
713
|
|
|
714 /* Clear the live bit for VAR in PTR. */
|
|
|
715
|
|
|
716 static inline void
|
|
|
717 live_track_clear_var (live_track_p ptr, tree var)
|
|
|
718 {
|
|
|
719 int p;
|
|
|
720
|
|
|
721 p = var_to_partition (ptr->map, var);
|
|
|
722 if (p != NO_PARTITION)
|
|
|
723 live_track_remove_partition (ptr, p);
|
|
|
724 }
|
|
|
725
|
|
|
726
|
|
|
727 /* Return TRUE if VAR is live in PTR. */
|
|
|
728
|
|
|
729 static inline bool
|
|
|
730 live_track_live_p (live_track_p ptr, tree var)
|
|
|
731 {
|
|
|
732 int p, root;
|
|
|
733
|
|
|
734 p = var_to_partition (ptr->map, var);
|
|
|
735 if (p != NO_PARTITION)
|
|
|
736 {
|
|
|
737 root = basevar_index (ptr->map, p);
|
|
|
738 if (bitmap_bit_p (ptr->live_base_var, root))
|
|
|
739 return bitmap_bit_p (ptr->live_base_partitions[root], p);
|
|
|
740 }
|
|
|
741 return false;
|
|
|
742 }
|
|
|
743
|
|
|
744
|
|
|
745 /* This routine will add USE to PTR. USE will be marked as live in both the
|
|
|
746 ssa live map and the live bitmap for the root of USE. */
|
|
|
747
|
|
|
748 static inline void
|
|
|
749 live_track_process_use (live_track_p ptr, tree use)
|
|
|
750 {
|
|
|
751 int p;
|
|
|
752
|
|
|
753 p = var_to_partition (ptr->map, use);
|
|
|
754 if (p == NO_PARTITION)
|
|
|
755 return;
|
|
|
756
|
|
|
757 /* Mark as live in the appropriate live list. */
|
|
|
758 live_track_add_partition (ptr, p);
|
|
|
759 }
|
|
|
760
|
|
|
761
|
|
|
762 /* This routine will process a DEF in PTR. DEF will be removed from the live
|
|
|
763 lists, and if there are any other live partitions with the same base
|
|
|
764 variable, conflicts will be added to GRAPH. */
|
|
|
765
|
|
|
766 static inline void
|
|
|
767 live_track_process_def (live_track_p ptr, tree def, ssa_conflicts_p graph)
|
|
|
768 {
|
|
|
769 int p, root;
|
|
|
770 bitmap b;
|
|
|
771 unsigned x;
|
|
|
772 bitmap_iterator bi;
|
|
|
773
|
|
|
774 p = var_to_partition (ptr->map, def);
|
|
|
775 if (p == NO_PARTITION)
|
|
|
776 return;
|
|
|
777
|
|
|
778 /* Clear the liveness bit. */
|
|
|
779 live_track_remove_partition (ptr, p);
|
|
|
780
|
|
|
781 /* If the bitmap isn't empty now, conflicts need to be added. */
|
|
|
782 root = basevar_index (ptr->map, p);
|
|
|
783 if (bitmap_bit_p (ptr->live_base_var, root))
|
|
|
784 {
|
|
|
785 b = ptr->live_base_partitions[root];
|
|
|
786 EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
|
|
|
787 ssa_conflicts_add (graph, p, x);
|
|
|
788 }
|
|
|
789 }
|
|
|
790
|
|
|
791
|
|
|
792 /* Initialize PTR with the partitions set in INIT. */
|
|
|
793
|
|
|
794 static inline void
|
|
|
795 live_track_init (live_track_p ptr, bitmap init)
|
|
|
796 {
|
|
|
797 unsigned p;
|
|
|
798 bitmap_iterator bi;
|
|
|
799
|
|
|
800 /* Mark all live on exit partitions. */
|
|
|
801 EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
|
|
|
802 live_track_add_partition (ptr, p);
|
|
|
803 }
|
|
|
804
|
|
|
805
|
|
|
806 /* This routine will clear all live partitions in PTR. */
|
|
|
807
|
|
|
808 static inline void
|
|
|
809 live_track_clear_base_vars (live_track_p ptr)
|
|
|
810 {
|
|
|
811 /* Simply clear the live base list. Anything marked as live in the element
|
|
|
812 lists will be cleared later if/when the base variable ever comes alive
|
|
|
813 again. */
|
|
|
814 bitmap_clear (ptr->live_base_var);
|
|
|
815 }
|
|
|
816
|
|
|
817
|
|
|
818 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
|
|
|
819 partition view of the var_map liveinfo is based on get entries in the
|
|
|
820 conflict graph. Only conflicts between ssa_name partitions with the same
|
|
|
821 base variable are added. */
|
|
|
822
|
|
|
823 static ssa_conflicts_p
|
|
|
824 build_ssa_conflict_graph (tree_live_info_p liveinfo)
|
|
|
825 {
|
|
|
826 ssa_conflicts_p graph;
|
|
|
827 var_map map;
|
|
|
828 basic_block bb;
|
|
|
829 ssa_op_iter iter;
|
|
|
830 live_track_p live;
|
|
|
831
|
|
|
832 map = live_var_map (liveinfo);
|
|
|
833 graph = ssa_conflicts_new (num_var_partitions (map));
|
|
|
834
|
|
|
835 live = new_live_track (map);
|
|
|
836
|
|
|
837 FOR_EACH_BB (bb)
|
|
|
838 {
|
|
|
839 gimple_stmt_iterator gsi;
|
|
|
840
|
|
|
841 /* Start with live on exit temporaries. */
|
|
|
842 live_track_init (live, live_on_exit (liveinfo, bb));
|
|
|
843
|
|
|
844 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
|
|
|
845 {
|
|
|
846 tree var;
|
|
|
847 gimple stmt = gsi_stmt (gsi);
|
|
|
848
|
|
|
849 /* A copy between 2 partitions does not introduce an interference
|
|
|
850 by itself. If they did, you would never be able to coalesce
|
|
|
851 two things which are copied. If the two variables really do
|
|
|
852 conflict, they will conflict elsewhere in the program.
|
|
|
853
|
|
|
854 This is handled by simply removing the SRC of the copy from the
|
|
|
855 live list, and processing the stmt normally. */
|
|
|
856 if (is_gimple_assign (stmt))
|
|
|
857 {
|
|
|
858 tree lhs = gimple_assign_lhs (stmt);
|
|
|
859 tree rhs1 = gimple_assign_rhs1 (stmt);
|
|
|
860 if (gimple_assign_copy_p (stmt)
|
|
|
861 && TREE_CODE (lhs) == SSA_NAME
|
|
|
862 && TREE_CODE (rhs1) == SSA_NAME)
|
|
|
863 live_track_clear_var (live, rhs1);
|
|
|
864 }
|
|
|
865
|
|
|
866 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
|
|
|
867 live_track_process_def (live, var, graph);
|
|
|
868
|
|
|
869 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
|
|
|
870 live_track_process_use (live, var);
|
|
|
871 }
|
|
|
872
|
|
|
873 /* If result of a PHI is unused, looping over the statements will not
|
|
|
874 record any conflicts since the def was never live. Since the PHI node
|
|
|
875 is going to be translated out of SSA form, it will insert a copy.
|
|
|
876 There must be a conflict recorded between the result of the PHI and
|
|
|
877 any variables that are live. Otherwise the out-of-ssa translation
|
|
|
878 may create incorrect code. */
|
|
|
879 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
880 {
|
|
|
881 gimple phi = gsi_stmt (gsi);
|
|
|
882 tree result = PHI_RESULT (phi);
|
|
|
883 if (live_track_live_p (live, result))
|
|
|
884 live_track_process_def (live, result, graph);
|
|
|
885 }
|
|
|
886
|
|
|
887 live_track_clear_base_vars (live);
|
|
|
888 }
|
|
|
889
|
|
|
890 delete_live_track (live);
|
|
|
891 return graph;
|
|
|
892 }
|
|
|
893
|
|
|
894
|
|
|
895 /* Shortcut routine to print messages to file F of the form:
|
|
|
896 "STR1 EXPR1 STR2 EXPR2 STR3." */
|
|
|
897
|
|
|
898 static inline void
|
|
|
899 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
|
|
|
900 tree expr2, const char *str3)
|
|
|
901 {
|
|
|
902 fprintf (f, "%s", str1);
|
|
|
903 print_generic_expr (f, expr1, TDF_SLIM);
|
|
|
904 fprintf (f, "%s", str2);
|
|
|
905 print_generic_expr (f, expr2, TDF_SLIM);
|
|
|
906 fprintf (f, "%s", str3);
|
|
|
907 }
|
|
|
908
|
|
|
909
|
|
|
910 /* Called if a coalesce across and abnormal edge cannot be performed. PHI is
|
|
|
911 the phi node at fault, I is the argument index at fault. A message is
|
|
|
912 printed and compilation is then terminated. */
|
|
|
913
|
|
|
914 static inline void
|
|
|
915 abnormal_corrupt (gimple phi, int i)
|
|
|
916 {
|
|
|
917 edge e = gimple_phi_arg_edge (phi, i);
|
|
|
918 tree res = gimple_phi_result (phi);
|
|
|
919 tree arg = gimple_phi_arg_def (phi, i);
|
|
|
920
|
|
|
921 fprintf (stderr, " Corrupt SSA across abnormal edge BB%d->BB%d\n",
|
|
|
922 e->src->index, e->dest->index);
|
|
|
923 fprintf (stderr, "Argument %d (", i);
|
|
|
924 print_generic_expr (stderr, arg, TDF_SLIM);
|
|
|
925 if (TREE_CODE (arg) != SSA_NAME)
|
|
|
926 fprintf (stderr, ") is not an SSA_NAME.\n");
|
|
|
927 else
|
|
|
928 {
|
|
|
929 gcc_assert (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg));
|
|
|
930 fprintf (stderr, ") does not have the same base variable as the result ");
|
|
|
931 print_generic_stmt (stderr, res, TDF_SLIM);
|
|
|
932 }
|
|
|
933
|
|
|
934 internal_error ("SSA corruption");
|
|
|
935 }
|
|
|
936
|
|
|
937
|
|
|
938 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
|
|
|
939
|
|
|
940 static inline void
|
|
|
941 fail_abnormal_edge_coalesce (int x, int y)
|
|
|
942 {
|
|
|
943 fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
|
|
|
944 fprintf (stderr, " which are marked as MUST COALESCE.\n");
|
|
|
945 print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
|
|
|
946 fprintf (stderr, " and ");
|
|
|
947 print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
|
|
|
948
|
|
|
949 internal_error ("SSA corruption");
|
|
|
950 }
|
|
|
951
|
|
|
952
|
|
|
953 /* This function creates a var_map for the current function as well as creating
|
|
|
954 a coalesce list for use later in the out of ssa process. */
|
|
|
955
|
|
|
956 static var_map
|
|
|
957 create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
|
|
|
958 {
|
|
|
959 gimple_stmt_iterator gsi;
|
|
|
960 basic_block bb;
|
|
|
961 tree var;
|
|
|
962 gimple stmt;
|
|
|
963 tree first;
|
|
|
964 var_map map;
|
|
|
965 ssa_op_iter iter;
|
|
|
966 int v1, v2, cost;
|
|
|
967 unsigned i;
|
|
|
968
|
|
|
969 #ifdef ENABLE_CHECKING
|
|
|
970 bitmap used_in_real_ops;
|
|
|
971 bitmap used_in_virtual_ops;
|
|
|
972
|
|
|
973 used_in_real_ops = BITMAP_ALLOC (NULL);
|
|
|
974 used_in_virtual_ops = BITMAP_ALLOC (NULL);
|
|
|
975 #endif
|
|
|
976
|
|
|
977 map = init_var_map (num_ssa_names + 1);
|
|
|
978
|
|
|
979 FOR_EACH_BB (bb)
|
|
|
980 {
|
|
|
981 tree arg;
|
|
|
982
|
|
|
983 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
984 {
|
|
|
985 gimple phi = gsi_stmt (gsi);
|
|
|
986 size_t i;
|
|
|
987 int ver;
|
|
|
988 tree res;
|
|
|
989 bool saw_copy = false;
|
|
|
990
|
|
|
991 res = gimple_phi_result (phi);
|
|
|
992 ver = SSA_NAME_VERSION (res);
|
|
|
993 register_ssa_partition (map, res);
|
|
|
994
|
|
|
995 /* Register ssa_names and coalesces between the args and the result
|
|
|
996 of all PHI. */
|
|
|
997 for (i = 0; i < gimple_phi_num_args (phi); i++)
|
|
|
998 {
|
|
|
999 edge e = gimple_phi_arg_edge (phi, i);
|
|
|
1000 arg = PHI_ARG_DEF (phi, i);
|
|
|
1001 if (TREE_CODE (arg) == SSA_NAME)
|
|
|
1002 register_ssa_partition (map, arg);
|
|
|
1003 if (TREE_CODE (arg) == SSA_NAME
|
|
|
1004 && SSA_NAME_VAR (arg) == SSA_NAME_VAR (res))
|
|
|
1005 {
|
|
|
1006 saw_copy = true;
|
|
|
1007 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
|
|
|
1008 if ((e->flags & EDGE_ABNORMAL) == 0)
|
|
|
1009 {
|
|
|
1010 int cost = coalesce_cost_edge (e);
|
|
|
1011 if (cost == 1 && has_single_use (arg))
|
|
|
1012 add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
|
|
|
1013 else
|
|
|
1014 add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
|
|
|
1015 }
|
|
|
1016 }
|
|
|
1017 else
|
|
|
1018 if (e->flags & EDGE_ABNORMAL)
|
|
|
1019 abnormal_corrupt (phi, i);
|
|
|
1020 }
|
|
|
1021 if (saw_copy)
|
|
|
1022 bitmap_set_bit (used_in_copy, ver);
|
|
|
1023 }
|
|
|
1024
|
|
|
1025 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1026 {
|
|
|
1027 stmt = gsi_stmt (gsi);
|
|
|
1028
|
|
|
1029 /* Register USE and DEF operands in each statement. */
|
|
|
1030 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
|
|
|
1031 register_ssa_partition (map, var);
|
|
|
1032
|
|
|
1033 /* Check for copy coalesces. */
|
|
|
1034 switch (gimple_code (stmt))
|
|
|
1035 {
|
|
|
1036 case GIMPLE_ASSIGN:
|
|
|
1037 {
|
|
|
1038 tree lhs = gimple_assign_lhs (stmt);
|
|
|
1039 tree rhs1 = gimple_assign_rhs1 (stmt);
|
|
|
1040
|
|
|
1041 if (gimple_assign_copy_p (stmt)
|
|
|
1042 && TREE_CODE (lhs) == SSA_NAME
|
|
|
1043 && TREE_CODE (rhs1) == SSA_NAME
|
|
|
1044 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs1))
|
|
|
1045 {
|
|
|
1046 v1 = SSA_NAME_VERSION (lhs);
|
|
|
1047 v2 = SSA_NAME_VERSION (rhs1);
|
|
|
1048 cost = coalesce_cost_bb (bb);
|
|
|
1049 add_coalesce (cl, v1, v2, cost);
|
|
|
1050 bitmap_set_bit (used_in_copy, v1);
|
|
|
1051 bitmap_set_bit (used_in_copy, v2);
|
|
|
1052 }
|
|
|
1053 }
|
|
|
1054 break;
|
|
|
1055
|
|
|
1056 case GIMPLE_ASM:
|
|
|
1057 {
|
|
|
1058 unsigned long noutputs, i;
|
|
|
1059 unsigned long ninputs;
|
|
|
1060 tree *outputs, link;
|
|
|
1061 noutputs = gimple_asm_noutputs (stmt);
|
|
|
1062 ninputs = gimple_asm_ninputs (stmt);
|
|
|
1063 outputs = (tree *) alloca (noutputs * sizeof (tree));
|
|
|
1064 for (i = 0; i < noutputs; ++i) {
|
|
|
1065 link = gimple_asm_output_op (stmt, i);
|
|
|
1066 outputs[i] = TREE_VALUE (link);
|
|
|
1067 }
|
|
|
1068
|
|
|
1069 for (i = 0; i < ninputs; ++i)
|
|
|
1070 {
|
|
|
1071 const char *constraint;
|
|
|
1072 tree input;
|
|
|
1073 char *end;
|
|
|
1074 unsigned long match;
|
|
|
1075
|
|
|
1076 link = gimple_asm_input_op (stmt, i);
|
|
|
1077 constraint
|
|
|
1078 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
|
|
|
1079 input = TREE_VALUE (link);
|
|
|
1080
|
|
|
1081 if (TREE_CODE (input) != SSA_NAME)
|
|
|
1082 continue;
|
|
|
1083
|
|
|
1084 match = strtoul (constraint, &end, 10);
|
|
|
1085 if (match >= noutputs || end == constraint)
|
|
|
1086 continue;
|
|
|
1087
|
|
|
1088 if (TREE_CODE (outputs[match]) != SSA_NAME)
|
|
|
1089 continue;
|
|
|
1090
|
|
|
1091 v1 = SSA_NAME_VERSION (outputs[match]);
|
|
|
1092 v2 = SSA_NAME_VERSION (input);
|
|
|
1093
|
|
|
1094 if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input))
|
|
|
1095 {
|
|
|
1096 cost = coalesce_cost (REG_BR_PROB_BASE,
|
|
|
1097 optimize_bb_for_size_p (bb),
|
|
|
1098 false);
|
|
|
1099 add_coalesce (cl, v1, v2, cost);
|
|
|
1100 bitmap_set_bit (used_in_copy, v1);
|
|
|
1101 bitmap_set_bit (used_in_copy, v2);
|
|
|
1102 }
|
|
|
1103 }
|
|
|
1104 break;
|
|
|
1105 }
|
|
|
1106
|
|
|
1107 default:
|
|
|
1108 break;
|
|
|
1109 }
|
|
|
1110
|
|
|
1111 #ifdef ENABLE_CHECKING
|
|
|
1112 /* Mark real uses and defs. */
|
|
|
1113 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
|
|
|
1114 bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var)));
|
|
|
1115
|
|
|
1116 /* Validate that virtual ops don't get used in funny ways. */
|
|
|
1117 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS)
|
|
|
1118 {
|
|
|
1119 bitmap_set_bit (used_in_virtual_ops,
|
|
|
1120 DECL_UID (SSA_NAME_VAR (var)));
|
|
|
1121 }
|
|
|
1122
|
|
|
1123 #endif /* ENABLE_CHECKING */
|
|
|
1124 }
|
|
|
1125 }
|
|
|
1126
|
|
|
1127 /* Now process result decls and live on entry variables for entry into
|
|
|
1128 the coalesce list. */
|
|
|
1129 first = NULL_TREE;
|
|
|
1130 for (i = 1; i < num_ssa_names; i++)
|
|
|
1131 {
|
|
|
1132 var = map->partition_to_var[i];
|
|
|
1133 if (var != NULL_TREE)
|
|
|
1134 {
|
|
|
1135 /* Add coalesces between all the result decls. */
|
|
|
1136 if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
|
|
|
1137 {
|
|
|
1138 if (first == NULL_TREE)
|
|
|
1139 first = var;
|
|
|
1140 else
|
|
|
1141 {
|
|
|
1142 gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first));
|
|
|
1143 v1 = SSA_NAME_VERSION (first);
|
|
|
1144 v2 = SSA_NAME_VERSION (var);
|
|
|
1145 bitmap_set_bit (used_in_copy, v1);
|
|
|
1146 bitmap_set_bit (used_in_copy, v2);
|
|
|
1147 cost = coalesce_cost_bb (EXIT_BLOCK_PTR);
|
|
|
1148 add_coalesce (cl, v1, v2, cost);
|
|
|
1149 }
|
|
|
1150 }
|
|
|
1151 /* Mark any default_def variables as being in the coalesce list
|
|
|
1152 since they will have to be coalesced with the base variable. If
|
|
|
1153 not marked as present, they won't be in the coalesce view. */
|
|
|
1154 if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
|
|
|
1155 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
|
|
|
1156 }
|
|
|
1157 }
|
|
|
1158
|
|
|
1159 #if defined ENABLE_CHECKING
|
|
|
1160 {
|
|
|
1161 unsigned i;
|
|
|
1162 bitmap both = BITMAP_ALLOC (NULL);
|
|
|
1163 bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
|
|
|
1164 if (!bitmap_empty_p (both))
|
|
|
1165 {
|
|
|
1166 bitmap_iterator bi;
|
|
|
1167
|
|
|
1168 EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
|
|
|
1169 fprintf (stderr, "Variable %s used in real and virtual operands\n",
|
|
|
1170 get_name (referenced_var (i)));
|
|
|
1171 internal_error ("SSA corruption");
|
|
|
1172 }
|
|
|
1173
|
|
|
1174 BITMAP_FREE (used_in_real_ops);
|
|
|
1175 BITMAP_FREE (used_in_virtual_ops);
|
|
|
1176 BITMAP_FREE (both);
|
|
|
1177 }
|
|
|
1178 #endif
|
|
|
1179
|
|
|
1180 return map;
|
|
|
1181 }
|
|
|
1182
|
|
|
1183
|
|
|
1184 /* Attempt to coalesce ssa versions X and Y together using the partition
|
|
|
1185 mapping in MAP and checking conflicts in GRAPH. Output any debug info to
|
|
|
1186 DEBUG, if it is nun-NULL. */
|
|
|
1187
|
|
|
1188 static inline bool
|
|
|
1189 attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
|
|
|
1190 FILE *debug)
|
|
|
1191 {
|
|
|
1192 int z;
|
|
|
1193 tree var1, var2;
|
|
|
1194 int p1, p2;
|
|
|
1195
|
|
|
1196 p1 = var_to_partition (map, ssa_name (x));
|
|
|
1197 p2 = var_to_partition (map, ssa_name (y));
|
|
|
1198
|
|
|
1199 if (debug)
|
|
|
1200 {
|
|
|
1201 fprintf (debug, "(%d)", x);
|
|
|
1202 print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
|
|
|
1203 fprintf (debug, " & (%d)", y);
|
|
|
1204 print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
|
|
|
1205 }
|
|
|
1206
|
|
|
1207 if (p1 == p2)
|
|
|
1208 {
|
|
|
1209 if (debug)
|
|
|
1210 fprintf (debug, ": Already Coalesced.\n");
|
|
|
1211 return true;
|
|
|
1212 }
|
|
|
1213
|
|
|
1214 if (debug)
|
|
|
1215 fprintf (debug, " [map: %d, %d] ", p1, p2);
|
|
|
1216
|
|
|
1217
|
|
|
1218 if (!ssa_conflicts_test_p (graph, p1, p2))
|
|
|
1219 {
|
|
|
1220 var1 = partition_to_var (map, p1);
|
|
|
1221 var2 = partition_to_var (map, p2);
|
|
|
1222 z = var_union (map, var1, var2);
|
|
|
1223 if (z == NO_PARTITION)
|
|
|
1224 {
|
|
|
1225 if (debug)
|
|
|
1226 fprintf (debug, ": Unable to perform partition union.\n");
|
|
|
1227 return false;
|
|
|
1228 }
|
|
|
1229
|
|
|
1230 /* z is the new combined partition. Remove the other partition from
|
|
|
1231 the list, and merge the conflicts. */
|
|
|
1232 if (z == p1)
|
|
|
1233 ssa_conflicts_merge (graph, p1, p2);
|
|
|
1234 else
|
|
|
1235 ssa_conflicts_merge (graph, p2, p1);
|
|
|
1236
|
|
|
1237 if (debug)
|
|
|
1238 fprintf (debug, ": Success -> %d\n", z);
|
|
|
1239 return true;
|
|
|
1240 }
|
|
|
1241
|
|
|
1242 if (debug)
|
|
|
1243 fprintf (debug, ": Fail due to conflict\n");
|
|
|
1244
|
|
|
1245 return false;
|
|
|
1246 }
|
|
|
1247
|
|
|
1248
|
|
|
1249 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
|
|
|
1250 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
|
|
|
1251
|
|
|
1252 static void
|
|
|
1253 coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
|
|
|
1254 FILE *debug)
|
|
|
1255 {
|
|
|
1256 int x = 0, y = 0;
|
|
|
1257 tree var1, var2;
|
|
|
1258 int cost;
|
|
|
1259 basic_block bb;
|
|
|
1260 edge e;
|
|
|
1261 edge_iterator ei;
|
|
|
1262
|
|
|
1263 /* First, coalesce all the copies across abnormal edges. These are not placed
|
|
|
1264 in the coalesce list because they do not need to be sorted, and simply
|
|
|
1265 consume extra memory/compilation time in large programs. */
|
|
|
1266
|
|
|
1267 FOR_EACH_BB (bb)
|
|
|
1268 {
|
|
|
1269 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1270 if (e->flags & EDGE_ABNORMAL)
|
|
|
1271 {
|
|
|
1272 gimple_stmt_iterator gsi;
|
|
|
1273 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
|
|
|
1274 gsi_next (&gsi))
|
|
|
1275 {
|
|
|
1276 gimple phi = gsi_stmt (gsi);
|
|
|
1277 tree res = PHI_RESULT (phi);
|
|
|
1278 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
|
|
|
1279 int v1 = SSA_NAME_VERSION (res);
|
|
|
1280 int v2 = SSA_NAME_VERSION (arg);
|
|
|
1281
|
|
|
1282 if (SSA_NAME_VAR (arg) != SSA_NAME_VAR (res))
|
|
|
1283 abnormal_corrupt (phi, e->dest_idx);
|
|
|
1284
|
|
|
1285 if (debug)
|
|
|
1286 fprintf (debug, "Abnormal coalesce: ");
|
|
|
1287
|
|
|
1288 if (!attempt_coalesce (map, graph, v1, v2, debug))
|
|
|
1289 fail_abnormal_edge_coalesce (v1, v2);
|
|
|
1290 }
|
|
|
1291 }
|
|
|
1292 }
|
|
|
1293
|
|
|
1294 /* Now process the items in the coalesce list. */
|
|
|
1295
|
|
|
1296 while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
|
|
|
1297 {
|
|
|
1298 var1 = ssa_name (x);
|
|
|
1299 var2 = ssa_name (y);
|
|
|
1300
|
|
|
1301 /* Assert the coalesces have the same base variable. */
|
|
|
1302 gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2));
|
|
|
1303
|
|
|
1304 if (debug)
|
|
|
1305 fprintf (debug, "Coalesce list: ");
|
|
|
1306 attempt_coalesce (map, graph, x, y, debug);
|
|
|
1307 }
|
|
|
1308 }
|
|
|
1309
|
|
|
1310 /* Returns a hash code for P. */
|
|
|
1311
|
|
|
1312 static hashval_t
|
|
|
1313 hash_ssa_name_by_var (const void *p)
|
|
|
1314 {
|
|
|
1315 const_tree n = (const_tree) p;
|
|
|
1316 return (hashval_t) htab_hash_pointer (SSA_NAME_VAR (n));
|
|
|
1317 }
|
|
|
1318
|
|
|
1319 /* Returns nonzero if P1 and P2 are equal. */
|
|
|
1320
|
|
|
1321 static int
|
|
|
1322 eq_ssa_name_by_var (const void *p1, const void *p2)
|
|
|
1323 {
|
|
|
1324 const_tree n1 = (const_tree) p1;
|
|
|
1325 const_tree n2 = (const_tree) p2;
|
|
|
1326 return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
|
|
|
1327 }
|
|
|
1328
|
|
|
1329 /* Reduce the number of copies by coalescing variables in the function. Return
|
|
|
1330 a partition map with the resulting coalesces. */
|
|
|
1331
|
|
|
1332 extern var_map
|
|
|
1333 coalesce_ssa_name (void)
|
|
|
1334 {
|
|
|
1335 unsigned num, x;
|
|
|
1336 tree_live_info_p liveinfo;
|
|
|
1337 ssa_conflicts_p graph;
|
|
|
1338 coalesce_list_p cl;
|
|
|
1339 bitmap used_in_copies = BITMAP_ALLOC (NULL);
|
|
|
1340 var_map map;
|
|
|
1341 unsigned int i;
|
|
|
1342 static htab_t ssa_name_hash;
|
|
|
1343
|
|
|
1344 cl = create_coalesce_list ();
|
|
|
1345 map = create_outofssa_var_map (cl, used_in_copies);
|
|
|
1346
|
|
|
1347 /* We need to coalesce all names originating same SSA_NAME_VAR
|
|
|
1348 so debug info remains undisturbed. */
|
|
|
1349 if (!optimize)
|
|
|
1350 {
|
|
|
1351 ssa_name_hash = htab_create (10, hash_ssa_name_by_var,
|
|
|
1352 eq_ssa_name_by_var, NULL);
|
|
|
1353 for (i = 1; i < num_ssa_names; i++)
|
|
|
1354 {
|
|
|
1355 tree a = ssa_name (i);
|
|
|
1356
|
|
|
1357 if (a && SSA_NAME_VAR (a) && !DECL_ARTIFICIAL (SSA_NAME_VAR (a)))
|
|
|
1358 {
|
|
|
1359 tree *slot = (tree *) htab_find_slot (ssa_name_hash, a, INSERT);
|
|
|
1360
|
|
|
1361 if (!*slot)
|
|
|
1362 *slot = a;
|
|
|
1363 else
|
|
|
1364 {
|
|
|
1365 add_coalesce (cl, SSA_NAME_VERSION (a), SSA_NAME_VERSION (*slot),
|
|
|
1366 MUST_COALESCE_COST - 1);
|
|
|
1367 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a));
|
|
|
1368 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot));
|
|
|
1369 }
|
|
|
1370 }
|
|
|
1371 }
|
|
|
1372 htab_delete (ssa_name_hash);
|
|
|
1373 }
|
|
|
1374 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1375 dump_var_map (dump_file, map);
|
|
|
1376
|
|
|
1377 /* Don't calculate live ranges for variables not in the coalesce list. */
|
|
|
1378 partition_view_bitmap (map, used_in_copies, true);
|
|
|
1379 BITMAP_FREE (used_in_copies);
|
|
|
1380
|
|
|
1381 if (num_var_partitions (map) < 1)
|
|
|
1382 {
|
|
|
1383 delete_coalesce_list (cl);
|
|
|
1384 return map;
|
|
|
1385 }
|
|
|
1386
|
|
|
1387 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1388 dump_var_map (dump_file, map);
|
|
|
1389
|
|
|
1390 liveinfo = calculate_live_ranges (map);
|
|
|
1391
|
|
|
1392 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1393 dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
|
|
|
1394
|
|
|
1395 /* Build a conflict graph. */
|
|
|
1396 graph = build_ssa_conflict_graph (liveinfo);
|
|
|
1397 delete_tree_live_info (liveinfo);
|
|
|
1398 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1399 ssa_conflicts_dump (dump_file, graph);
|
|
|
1400
|
|
|
1401 sort_coalesce_list (cl);
|
|
|
1402
|
|
|
1403 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1404 {
|
|
|
1405 fprintf (dump_file, "\nAfter sorting:\n");
|
|
|
1406 dump_coalesce_list (dump_file, cl);
|
|
|
1407 }
|
|
|
1408
|
|
|
1409 /* First, coalesce all live on entry variables to their base variable.
|
|
|
1410 This will ensure the first use is coming from the correct location. */
|
|
|
1411
|
|
|
1412 num = num_var_partitions (map);
|
|
|
1413 for (x = 0 ; x < num; x++)
|
|
|
1414 {
|
|
|
1415 tree var = partition_to_var (map, x);
|
|
|
1416 tree root;
|
|
|
1417
|
|
|
1418 if (TREE_CODE (var) != SSA_NAME)
|
|
|
1419 continue;
|
|
|
1420
|
|
|
1421 root = SSA_NAME_VAR (var);
|
|
|
1422 if (gimple_default_def (cfun, root) == var)
|
|
|
1423 {
|
|
|
1424 /* This root variable should have not already been assigned
|
|
|
1425 to another partition which is not coalesced with this one. */
|
|
|
1426 gcc_assert (!var_ann (root)->out_of_ssa_tag);
|
|
|
1427
|
|
|
1428 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1429 {
|
|
|
1430 print_exprs (dump_file, "Must coalesce ", var,
|
|
|
1431 " with the root variable ", root, ".\n");
|
|
|
1432 }
|
|
|
1433 change_partition_var (map, root, x);
|
|
|
1434 }
|
|
|
1435 }
|
|
|
1436
|
|
|
1437 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1438 dump_var_map (dump_file, map);
|
|
|
1439
|
|
|
1440 /* Now coalesce everything in the list. */
|
|
|
1441 coalesce_partitions (map, graph, cl,
|
|
|
1442 ((dump_flags & TDF_DETAILS) ? dump_file
|
|
|
1443 : NULL));
|
|
|
1444
|
|
|
1445 delete_coalesce_list (cl);
|
|
|
1446 ssa_conflicts_delete (graph);
|
|
|
1447
|
|
|
1448 return map;
|
|
|
1449 }
|
