Mercurial > hg > CbC > CbC_gcc
comparison gcc/tree-ssa-coalesce.c @ 0:a06113de4d67
first commit
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 17 Jul 2009 14:47:48 +0900 |
parents | |
children | 77e2b8dfacca |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a06113de4d67 |
---|---|
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 } |