OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [tree-ssa-coalesce.c] - Blame information for rev 280

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.