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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-ssa-coalesce.c] - Blame information for rev 692

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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