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
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
72typedef struct coalesce_pair
73{
74  int first_element;
75  int second_element;
76  int cost;
77} * coalesce_pair_p;
78typedef const struct coalesce_pair *const_coalesce_pair_p;
79
80/* Coalesce pair hashtable helpers.  */
81
82struct 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
92inline hashval_t
93coalesce_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
104inline bool
105coalesce_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
111typedef hash_table<coalesce_pair_hasher> coalesce_table_type;
112typedef coalesce_table_type::iterator coalesce_iterator_type;
113
114
115typedef 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
124typedef 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
138static inline int
139coalesce_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
156static inline int
157coalesce_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
165static inline int
166coalesce_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
207static inline int
208pop_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
229static inline int
230pop_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
253static inline coalesce_list_p
254create_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
273static inline void
274delete_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
289static coalesce_pair_p
290find_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
326static inline void
327add_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
341static inline void
342add_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
365static int
366compare_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
389static inline int
390num_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
405static void
406sort_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
452static void
453dump_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
497typedef 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
505static inline ssa_conflicts_p
506ssa_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
520static inline void
521ssa_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
531static inline bool
532ssa_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
549static inline void
550ssa_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
562static inline void
563ssa_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
573static inline void
574ssa_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
613static void
614ssa_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
642typedef 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
654static live_track_p
655new_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
677static void
678delete_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
688static inline void
689live_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
703static inline void
704live_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
720static inline void
721live_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
733static inline bool
734live_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
752static inline void
753live_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
770static inline void
771live_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
798static inline void
799live_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
812static inline void
813live_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
827static ssa_conflicts_p
828build_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
904static inline void
905print_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
918static inline void
919fail_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
934static var_map
935create_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
1127static inline bool
1128attempt_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
1191static void
1192coalesce_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
1254struct 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
1262inline hashval_t
1263ssa_name_var_hash::hash (const_tree n)
1264{
1265  return DECL_UID (SSA_NAME_VAR (n));
1266}
1267
1268inline int
1269ssa_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
1278extern var_map
1279coalesce_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}
1382