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