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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-ssa-live.c] - Blame information for rev 154

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

Line No. Rev Author Line
1 38 julius
/* Liveness for SSA trees.
2
   Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
3
   Contributed by Andrew MacLeod <amacleod@redhat.com>
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 3, or (at your option)
10
any later version.
11
 
12
GCC is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public License for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "tree.h"
26
#include "flags.h"
27
#include "basic-block.h"
28
#include "function.h"
29
#include "diagnostic.h"
30
#include "bitmap.h"
31
#include "tree-flow.h"
32
#include "tree-gimple.h"
33
#include "tree-inline.h"
34
#include "varray.h"
35
#include "timevar.h"
36
#include "hashtab.h"
37
#include "tree-dump.h"
38
#include "tree-ssa-live.h"
39
#include "toplev.h"
40
#include "vecprim.h"
41
 
42
static void live_worklist (tree_live_info_p, int *, int);
43
static tree_live_info_p new_tree_live_info (var_map);
44
static inline void set_if_valid (var_map, bitmap, tree);
45
static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
46
                                         tree, basic_block);
47
static inline void register_ssa_partition (var_map, tree, bool);
48
static inline void add_conflicts_if_valid (tpa_p, conflict_graph,
49
                                           var_map, bitmap, tree);
50
static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool);
51
 
52
/* This is where the mapping from SSA version number to real storage variable
53
   is tracked.
54
 
55
   All SSA versions of the same variable may not ultimately be mapped back to
56
   the same real variable. In that instance, we need to detect the live
57
   range overlap, and give one of the variable new storage. The vector
58
   'partition_to_var' tracks which partition maps to which variable.
59
 
60
   Given a VAR, it is sometimes desirable to know which partition that VAR
61
   represents.  There is an additional field in the variable annotation to
62
   track that information.  */
63
 
64
/* Create a variable partition map of SIZE, initialize and return it.  */
65
 
66
var_map
67
init_var_map (int size)
68
{
69
  var_map map;
70
 
71
  map = (var_map) xmalloc (sizeof (struct _var_map));
72
  map->var_partition = partition_new (size);
73
  map->partition_to_var
74
              = (tree *)xmalloc (size * sizeof (tree));
75
  memset (map->partition_to_var, 0, size * sizeof (tree));
76
 
77
  map->partition_to_compact = NULL;
78
  map->compact_to_partition = NULL;
79
  map->num_partitions = size;
80
  map->partition_size = size;
81
  map->ref_count = NULL;
82
  return map;
83
}
84
 
85
 
86
/* Free memory associated with MAP.  */
87
 
88
void
89
delete_var_map (var_map map)
90
{
91
  free (map->partition_to_var);
92
  partition_delete (map->var_partition);
93
  if (map->partition_to_compact)
94
    free (map->partition_to_compact);
95
  if (map->compact_to_partition)
96
    free (map->compact_to_partition);
97
  if (map->ref_count)
98
    free (map->ref_count);
99
  free (map);
100
}
101
 
102
 
103
/* This function will combine the partitions in MAP for VAR1 and VAR2.  It
104
   Returns the partition which represents the new partition.  If the two
105
   partitions cannot be combined, NO_PARTITION is returned.  */
106
 
107
int
108
var_union (var_map map, tree var1, tree var2)
109
{
110
  int p1, p2, p3;
111
  tree root_var = NULL_TREE;
112
  tree other_var = NULL_TREE;
113
 
114
  /* This is independent of partition_to_compact. If partition_to_compact is
115
     on, then whichever one of these partitions is absorbed will never have a
116
     dereference into the partition_to_compact array any more.  */
117
 
118
  if (TREE_CODE (var1) == SSA_NAME)
119
    p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
120
  else
121
    {
122
      p1 = var_to_partition (map, var1);
123
      if (map->compact_to_partition)
124
        p1 = map->compact_to_partition[p1];
125
      root_var = var1;
126
    }
127
 
128
  if (TREE_CODE (var2) == SSA_NAME)
129
    p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
130
  else
131
    {
132
      p2 = var_to_partition (map, var2);
133
      if (map->compact_to_partition)
134
        p2 = map->compact_to_partition[p2];
135
 
136
      /* If there is no root_var set, or it's not a user variable, set the
137
         root_var to this one.  */
138
      if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
139
        {
140
          other_var = root_var;
141
          root_var = var2;
142
        }
143
      else
144
        other_var = var2;
145
    }
146
 
147
  gcc_assert (p1 != NO_PARTITION);
148
  gcc_assert (p2 != NO_PARTITION);
149
 
150
  if (p1 == p2)
151
    p3 = p1;
152
  else
153
    p3 = partition_union (map->var_partition, p1, p2);
154
 
155
  if (map->partition_to_compact)
156
    p3 = map->partition_to_compact[p3];
157
 
158
  if (root_var)
159
    change_partition_var (map, root_var, p3);
160
  if (other_var)
161
    change_partition_var (map, other_var, p3);
162
 
163
  return p3;
164
}
165
 
166
 
167
/* Compress the partition numbers in MAP such that they fall in the range
168
   0..(num_partitions-1) instead of wherever they turned out during
169
   the partitioning exercise.  This removes any references to unused
170
   partitions, thereby allowing bitmaps and other vectors to be much
171
   denser.  Compression type is controlled by FLAGS.
172
 
173
   This is implemented such that compaction doesn't affect partitioning.
174
   Ie., once partitions are created and possibly merged, running one
175
   or more different kind of compaction will not affect the partitions
176
   themselves.  Their index might change, but all the same variables will
177
   still be members of the same partition group.  This allows work on reduced
178
   sets, and no loss of information when a larger set is later desired.
179
 
180
   In particular, coalescing can work on partitions which have 2 or more
181
   definitions, and then 'recompact' later to include all the single
182
   definitions for assignment to program variables.  */
183
 
184
void
185
compact_var_map (var_map map, int flags)
186
{
187
  sbitmap used;
188
  int tmp, root, root_i;
189
  unsigned int x, limit, count;
190
  tree var;
191
  root_var_p rv = NULL;
192
 
193
  limit = map->partition_size;
194
  used = sbitmap_alloc (limit);
195
  sbitmap_zero (used);
196
 
197
  /* Already compressed? Abandon the old one.  */
198
  if (map->partition_to_compact)
199
    {
200
      free (map->partition_to_compact);
201
      map->partition_to_compact = NULL;
202
    }
203
  if (map->compact_to_partition)
204
    {
205
      free (map->compact_to_partition);
206
      map->compact_to_partition = NULL;
207
    }
208
 
209
  map->num_partitions = map->partition_size;
210
 
211
  if (flags & VARMAP_NO_SINGLE_DEFS)
212
    rv = root_var_init (map);
213
 
214
  map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
215
  memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
216
 
217
  /* Find out which partitions are actually referenced.  */
218
  count = 0;
219
  for (x = 0; x < limit; x++)
220
    {
221
      tmp = partition_find (map->var_partition, x);
222
      if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
223
        {
224
          /* It is referenced, check to see if there is more than one version
225
             in the root_var table, if one is available.  */
226
          if (rv)
227
            {
228
              root = root_var_find (rv, tmp);
229
              root_i = root_var_first_partition (rv, root);
230
              /* If there is only one, don't include this in the compaction.  */
231
              if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE)
232
                continue;
233
            }
234
          SET_BIT (used, tmp);
235
          count++;
236
        }
237
    }
238
 
239
  /* Build a compacted partitioning.  */
240
  if (count != limit)
241
    {
242
      sbitmap_iterator sbi;
243
 
244
      map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
245
      count = 0;
246
      /* SSA renaming begins at 1, so skip 0 when compacting.  */
247
      EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi)
248
        {
249
          map->partition_to_compact[x] = count;
250
          map->compact_to_partition[count] = x;
251
          var = map->partition_to_var[x];
252
          if (TREE_CODE (var) != SSA_NAME)
253
            change_partition_var (map, var, count);
254
          count++;
255
        }
256
    }
257
  else
258
    {
259
      free (map->partition_to_compact);
260
      map->partition_to_compact = NULL;
261
    }
262
 
263
  map->num_partitions = count;
264
 
265
  if (rv)
266
    root_var_delete (rv);
267
  sbitmap_free (used);
268
}
269
 
270
 
271
/* This function is used to change the representative variable in MAP for VAR's
272
   partition from an SSA_NAME variable to a regular variable.  This allows
273
   partitions to be mapped back to real variables.  */
274
 
275
void
276
change_partition_var (var_map map, tree var, int part)
277
{
278
  var_ann_t ann;
279
 
280
  gcc_assert (TREE_CODE (var) != SSA_NAME);
281
 
282
  ann = var_ann (var);
283
  ann->out_of_ssa_tag = 1;
284
  VAR_ANN_PARTITION (ann) = part;
285
  if (map->compact_to_partition)
286
    map->partition_to_var[map->compact_to_partition[part]] = var;
287
}
288
 
289
static inline void mark_all_vars_used (tree *);
290
 
291
/* Helper function for mark_all_vars_used, called via walk_tree.  */
292
 
293
static tree
294
mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
295
                      void *data ATTRIBUTE_UNUSED)
296
{
297
  tree t = *tp;
298
 
299
  if (TREE_CODE (t) == SSA_NAME)
300
    t = SSA_NAME_VAR (t);
301
 
302
  /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
303
     fields that do not contain vars.  */
304
  if (TREE_CODE (t) == TARGET_MEM_REF)
305
    {
306
      mark_all_vars_used (&TMR_SYMBOL (t));
307
      mark_all_vars_used (&TMR_BASE (t));
308
      mark_all_vars_used (&TMR_INDEX (t));
309
      *walk_subtrees = 0;
310
      return NULL;
311
    }
312
 
313
  /* Only need to mark VAR_DECLS; parameters and return results are not
314
     eliminated as unused.  */
315
  if (TREE_CODE (t) == VAR_DECL)
316
    set_is_used (t);
317
 
318
  if (IS_TYPE_OR_DECL_P (t))
319
    *walk_subtrees = 0;
320
 
321
  return NULL;
322
}
323
 
324
/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
325
   eliminated during the tree->rtl conversion process.  */
326
 
327
static inline void
328
mark_all_vars_used (tree *expr_p)
329
{
330
  walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
331
}
332
 
333
 
334
/* Remove local variables that are not referenced in the IL.  */
335
 
336
void
337
remove_unused_locals (void)
338
{
339
  basic_block bb;
340
  tree t, *cell;
341
 
342
  /* Assume all locals are unused.  */
343
  for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
344
    {
345
      tree var = TREE_VALUE (t);
346
      if (TREE_CODE (var) != FUNCTION_DECL
347
          && var_ann (var))
348
        var_ann (var)->used = false;
349
    }
350
 
351
  /* Walk the CFG marking all referenced symbols.  */
352
  FOR_EACH_BB (bb)
353
    {
354
      block_stmt_iterator bsi;
355
      tree phi, def;
356
 
357
      /* Walk the statements.  */
358
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
359
        mark_all_vars_used (bsi_stmt_ptr (bsi));
360
 
361
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
362
        {
363
          use_operand_p arg_p;
364
          ssa_op_iter i;
365
 
366
          /* No point processing globals.  */
367
          if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
368
            continue;
369
 
370
          def = PHI_RESULT (phi);
371
          mark_all_vars_used (&def);
372
 
373
          FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
374
            {
375
              tree arg = USE_FROM_PTR (arg_p);
376
              mark_all_vars_used (&arg);
377
            }
378
        }
379
    }
380
 
381
  /* Remove unmarked vars and clear used flag.  */
382
  for (cell = &cfun->unexpanded_var_list; *cell; )
383
    {
384
      tree var = TREE_VALUE (*cell);
385
      var_ann_t ann;
386
 
387
      if (TREE_CODE (var) != FUNCTION_DECL
388
          && (!(ann = var_ann (var))
389
              || !ann->used))
390
        {
391
          *cell = TREE_CHAIN (*cell);
392
          continue;
393
        }
394
 
395
      cell = &TREE_CHAIN (*cell);
396
    }
397
}
398
 
399
/* This function looks through the program and uses FLAGS to determine what
400
   SSA versioned variables are given entries in a new partition table.  This
401
   new partition map is returned.  */
402
 
403
var_map
404
create_ssa_var_map (int flags)
405
{
406
  block_stmt_iterator bsi;
407
  basic_block bb;
408
  tree dest, use;
409
  tree stmt;
410
  var_map map;
411
  ssa_op_iter iter;
412
#ifdef ENABLE_CHECKING
413
  bitmap used_in_real_ops;
414
  bitmap used_in_virtual_ops;
415
#endif
416
 
417
  map = init_var_map (num_ssa_names + 1);
418
 
419
#ifdef ENABLE_CHECKING
420
  used_in_real_ops = BITMAP_ALLOC (NULL);
421
  used_in_virtual_ops = BITMAP_ALLOC (NULL);
422
#endif
423
 
424
  if (flags & SSA_VAR_MAP_REF_COUNT)
425
    {
426
      map->ref_count
427
        = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
428
      memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
429
    }
430
 
431
  FOR_EACH_BB (bb)
432
    {
433
      tree phi, arg;
434
 
435
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
436
        {
437
          int i;
438
          register_ssa_partition (map, PHI_RESULT (phi), false);
439
          for (i = 0; i < PHI_NUM_ARGS (phi); i++)
440
            {
441
              arg = PHI_ARG_DEF (phi, i);
442
              if (TREE_CODE (arg) == SSA_NAME)
443
                register_ssa_partition (map, arg, true);
444
 
445
              mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
446
            }
447
        }
448
 
449
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
450
        {
451
          stmt = bsi_stmt (bsi);
452
 
453
          /* Register USE and DEF operands in each statement.  */
454
          FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
455
            {
456
              register_ssa_partition (map, use, true);
457
 
458
#ifdef ENABLE_CHECKING
459
              bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use)));
460
#endif
461
            }
462
 
463
          FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF)
464
            {
465
              register_ssa_partition (map, dest, false);
466
 
467
#ifdef ENABLE_CHECKING
468
              bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest)));
469
#endif
470
            }
471
 
472
#ifdef ENABLE_CHECKING
473
          /* Validate that virtual ops don't get used in funny ways.  */
474
          FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter,
475
                                     SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
476
            {
477
              bitmap_set_bit (used_in_virtual_ops,
478
                              DECL_UID (SSA_NAME_VAR (use)));
479
            }
480
 
481
#endif /* ENABLE_CHECKING */
482
 
483
          mark_all_vars_used (bsi_stmt_ptr (bsi));
484
        }
485
    }
486
 
487
#if defined ENABLE_CHECKING
488
  {
489
    unsigned i;
490
    bitmap both = BITMAP_ALLOC (NULL);
491
    bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
492
    if (!bitmap_empty_p (both))
493
      {
494
        bitmap_iterator bi;
495
 
496
        EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
497
          fprintf (stderr, "Variable %s used in real and virtual operands\n",
498
                   get_name (referenced_var (i)));
499
        internal_error ("SSA corruption");
500
      }
501
 
502
    BITMAP_FREE (used_in_real_ops);
503
    BITMAP_FREE (used_in_virtual_ops);
504
    BITMAP_FREE (both);
505
  }
506
#endif
507
 
508
  return map;
509
}
510
 
511
 
512
/* Allocate and return a new live range information object base on MAP.  */
513
 
514
static tree_live_info_p
515
new_tree_live_info (var_map map)
516
{
517
  tree_live_info_p live;
518
  unsigned x;
519
 
520
  live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
521
  live->map = map;
522
  live->num_blocks = last_basic_block;
523
 
524
  live->global = BITMAP_ALLOC (NULL);
525
 
526
  live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
527
  for (x = 0; x < num_var_partitions (map); x++)
528
    live->livein[x] = BITMAP_ALLOC (NULL);
529
 
530
  /* liveout is deferred until it is actually requested.  */
531
  live->liveout = NULL;
532
  return live;
533
}
534
 
535
 
536
/* Free storage for live range info object LIVE.  */
537
 
538
void
539
delete_tree_live_info (tree_live_info_p live)
540
{
541
  int x;
542
  if (live->liveout)
543
    {
544
      for (x = live->num_blocks - 1; x >= 0; x--)
545
        BITMAP_FREE (live->liveout[x]);
546
      free (live->liveout);
547
    }
548
  if (live->livein)
549
    {
550
      for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
551
        BITMAP_FREE (live->livein[x]);
552
      free (live->livein);
553
    }
554
  if (live->global)
555
    BITMAP_FREE (live->global);
556
 
557
  free (live);
558
}
559
 
560
 
561
/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
562
   for partition I.  STACK is a varray used for temporary memory which is
563
   passed in rather than being allocated on every call.  */
564
 
565
static void
566
live_worklist (tree_live_info_p live, int *stack, int i)
567
{
568
  unsigned b;
569
  tree var;
570
  basic_block def_bb = NULL;
571
  edge e;
572
  var_map map = live->map;
573
  edge_iterator ei;
574
  bitmap_iterator bi;
575
  int *tos = stack;
576
 
577
  var = partition_to_var (map, i);
578
  if (SSA_NAME_DEF_STMT (var))
579
    def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
580
 
581
  EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
582
    {
583
      *tos++ = b;
584
    }
585
 
586
  while (tos != stack)
587
    {
588
      b = *--tos;
589
 
590
      FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
591
        if (e->src != ENTRY_BLOCK_PTR)
592
          {
593
            /* Its not live on entry to the block its defined in.  */
594
            if (e->src == def_bb)
595
              continue;
596
            if (!bitmap_bit_p (live->livein[i], e->src->index))
597
              {
598
                bitmap_set_bit (live->livein[i], e->src->index);
599
                *tos++ = e->src->index;
600
              }
601
          }
602
    }
603
}
604
 
605
 
606
/* If VAR is in a partition of MAP, set the bit for that partition in VEC.  */
607
 
608
static inline void
609
set_if_valid (var_map map, bitmap vec, tree var)
610
{
611
  int p = var_to_partition (map, var);
612
  if (p != NO_PARTITION)
613
    bitmap_set_bit (vec, p);
614
}
615
 
616
 
617
/* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
618
   global bit for it in the LIVE object.  BB is the block being processed.  */
619
 
620
static inline void
621
add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
622
                      tree var, basic_block bb)
623
{
624
  int p = var_to_partition (live->map, var);
625
  if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
626
    return;
627
  if (!bitmap_bit_p (def_vec, p))
628
    {
629
      bitmap_set_bit (live->livein[p], bb->index);
630
      bitmap_set_bit (live->global, p);
631
    }
632
}
633
 
634
 
635
/* Given partition map MAP, calculate all the live on entry bitmaps for
636
   each basic block.  Return a live info object.  */
637
 
638
tree_live_info_p
639
calculate_live_on_entry (var_map map)
640
{
641
  tree_live_info_p live;
642
  unsigned i;
643
  basic_block bb;
644
  bitmap saw_def;
645
  tree phi, var, stmt;
646
  tree op;
647
  edge e;
648
  int *stack;
649
  block_stmt_iterator bsi;
650
  ssa_op_iter iter;
651
  bitmap_iterator bi;
652
#ifdef ENABLE_CHECKING
653
  int num;
654
  edge_iterator ei;
655
#endif
656
 
657
  saw_def = BITMAP_ALLOC (NULL);
658
 
659
  live = new_tree_live_info (map);
660
 
661
  FOR_EACH_BB (bb)
662
    {
663
      bitmap_clear (saw_def);
664
 
665
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
666
        {
667
          for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
668
            {
669
              var = PHI_ARG_DEF (phi, i);
670
              if (!phi_ssa_name_p (var))
671
                continue;
672
              stmt = SSA_NAME_DEF_STMT (var);
673
              e = EDGE_PRED (bb, i);
674
 
675
              /* Any uses in PHIs which either don't have def's or are not
676
                 defined in the block from which the def comes, will be live
677
                 on entry to that block.  */
678
              if (!stmt || e->src != bb_for_stmt (stmt))
679
                add_livein_if_notdef (live, saw_def, var, e->src);
680
            }
681
        }
682
 
683
      /* Don't mark PHI results as defined until all the PHI nodes have
684
         been processed. If the PHI sequence is:
685
            a_3 = PHI <a_1, a_2>
686
            b_3 = PHI <b_1, a_3>
687
         The a_3 referred to in b_3's PHI node is the one incoming on the
688
         edge, *not* the PHI node just seen.  */
689
 
690
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
691
        {
692
          var = PHI_RESULT (phi);
693
          set_if_valid (map, saw_def, var);
694
        }
695
 
696
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
697
        {
698
          stmt = bsi_stmt (bsi);
699
 
700
          FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
701
            {
702
              add_livein_if_notdef (live, saw_def, op, bb);
703
            }
704
 
705
          FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
706
            {
707
              set_if_valid (map, saw_def, op);
708
            }
709
        }
710
    }
711
 
712
  stack = XNEWVEC (int, last_basic_block);
713
  EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
714
    {
715
      live_worklist (live, stack, i);
716
    }
717
  free (stack);
718
 
719
#ifdef ENABLE_CHECKING
720
   /* Check for live on entry partitions and report those with a DEF in
721
      the program. This will typically mean an optimization has done
722
      something wrong.  */
723
 
724
  bb = ENTRY_BLOCK_PTR;
725
  num = 0;
726
  FOR_EACH_EDGE (e, ei, bb->succs)
727
    {
728
      int entry_block = e->dest->index;
729
      if (e->dest == EXIT_BLOCK_PTR)
730
        continue;
731
      for (i = 0; i < (unsigned)num_var_partitions (map); i++)
732
        {
733
          basic_block tmp;
734
          tree d;
735
          var = partition_to_var (map, i);
736
          stmt = SSA_NAME_DEF_STMT (var);
737
          tmp = bb_for_stmt (stmt);
738
          d = default_def (SSA_NAME_VAR (var));
739
 
740
          if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
741
            {
742
              if (!IS_EMPTY_STMT (stmt))
743
                {
744
                  num++;
745
                  print_generic_expr (stderr, var, TDF_SLIM);
746
                  fprintf (stderr, " is defined ");
747
                  if (tmp)
748
                    fprintf (stderr, " in BB%d, ", tmp->index);
749
                  fprintf (stderr, "by:\n");
750
                  print_generic_expr (stderr, stmt, TDF_SLIM);
751
                  fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
752
                           entry_block);
753
                  fprintf (stderr, " So it appears to have multiple defs.\n");
754
                }
755
              else
756
                {
757
                  if (d != var)
758
                    {
759
                      num++;
760
                      print_generic_expr (stderr, var, TDF_SLIM);
761
                      fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
762
                      if (d)
763
                        {
764
                          fprintf (stderr, " but is not the default def of ");
765
                          print_generic_expr (stderr, d, TDF_SLIM);
766
                          fprintf (stderr, "\n");
767
                        }
768
                      else
769
                        fprintf (stderr, " and there is no default def.\n");
770
                    }
771
                }
772
            }
773
          else
774
            if (d == var)
775
              {
776
                /* The only way this var shouldn't be marked live on entry is
777
                   if it occurs in a PHI argument of the block.  */
778
                int z, ok = 0;
779
                for (phi = phi_nodes (e->dest);
780
                     phi && !ok;
781
                     phi = PHI_CHAIN (phi))
782
                  {
783
                    for (z = 0; z < PHI_NUM_ARGS (phi); z++)
784
                      if (var == PHI_ARG_DEF (phi, z))
785
                        {
786
                          ok = 1;
787
                          break;
788
                        }
789
                  }
790
                if (ok)
791
                  continue;
792
                num++;
793
                print_generic_expr (stderr, var, TDF_SLIM);
794
                fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
795
                         entry_block);
796
                fprintf (stderr, "but it is a default def so it should be.\n");
797
              }
798
        }
799
    }
800
  gcc_assert (num <= 0);
801
#endif
802
 
803
  BITMAP_FREE (saw_def);
804
 
805
  return live;
806
}
807
 
808
 
809
/* Calculate the live on exit vectors based on the entry info in LIVEINFO.  */
810
 
811
void
812
calculate_live_on_exit (tree_live_info_p liveinfo)
813
{
814
  unsigned b;
815
  unsigned i, x;
816
  bitmap *on_exit;
817
  basic_block bb;
818
  edge e;
819
  tree t, phi;
820
  bitmap on_entry;
821
  var_map map = liveinfo->map;
822
 
823
  on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
824
  for (x = 0; x < (unsigned)last_basic_block; x++)
825
    on_exit[x] = BITMAP_ALLOC (NULL);
826
 
827
  /* Set all the live-on-exit bits for uses in PHIs.  */
828
  FOR_EACH_BB (bb)
829
    {
830
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
831
        for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
832
          {
833
            t = PHI_ARG_DEF (phi, i);
834
            e = PHI_ARG_EDGE (phi, i);
835
            if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
836
              continue;
837
            set_if_valid (map, on_exit[e->src->index], t);
838
          }
839
    }
840
 
841
  /* Set live on exit for all predecessors of live on entry's.  */
842
  for (i = 0; i < num_var_partitions (map); i++)
843
    {
844
      bitmap_iterator bi;
845
 
846
      on_entry = live_entry_blocks (liveinfo, i);
847
      EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
848
        {
849
          edge_iterator ei;
850
          FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
851
            if (e->src != ENTRY_BLOCK_PTR)
852
              bitmap_set_bit (on_exit[e->src->index], i);
853
        }
854
    }
855
 
856
  liveinfo->liveout = on_exit;
857
}
858
 
859
 
860
/* Initialize a tree_partition_associator object using MAP.  */
861
 
862
static tpa_p
863
tpa_init (var_map map)
864
{
865
  tpa_p tpa;
866
  int num_partitions = num_var_partitions (map);
867
  int x;
868
 
869
  if (num_partitions == 0)
870
    return NULL;
871
 
872
  tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
873
  tpa->num_trees = 0;
874
  tpa->uncompressed_num = -1;
875
  tpa->map = map;
876
  tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
877
  memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
878
 
879
  tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
880
  memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
881
 
882
  x = MAX (40, (num_partitions / 20));
883
  tpa->trees = VEC_alloc (tree, heap, x);
884
  tpa->first_partition = VEC_alloc (int, heap, x);
885
 
886
  return tpa;
887
 
888
}
889
 
890
 
891
/* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA.  */
892
 
893
void
894
tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
895
{
896
  int i;
897
 
898
  i = tpa_first_partition (tpa, tree_index);
899
  if (i == partition_index)
900
    {
901
      VEC_replace (int, tpa->first_partition, tree_index,
902
                   tpa->next_partition[i]);
903
    }
904
  else
905
    {
906
      for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
907
        {
908
          if (tpa->next_partition[i] == partition_index)
909
            {
910
              tpa->next_partition[i] = tpa->next_partition[partition_index];
911
              break;
912
            }
913
        }
914
    }
915
}
916
 
917
 
918
/* Free the memory used by tree_partition_associator object TPA.  */
919
 
920
void
921
tpa_delete (tpa_p tpa)
922
{
923
  if (!tpa)
924
    return;
925
 
926
  VEC_free (tree, heap, tpa->trees);
927
  VEC_free (int, heap, tpa->first_partition);
928
  free (tpa->partition_to_tree_map);
929
  free (tpa->next_partition);
930
  free (tpa);
931
}
932
 
933
 
934
/* This function will remove any tree entries from TPA which have only a single
935
   element.  This will help keep the size of the conflict graph down.  The
936
   function returns the number of remaining tree lists.  */
937
 
938
int
939
tpa_compact (tpa_p tpa)
940
{
941
  int last, x, y, first, swap_i;
942
  tree swap_t;
943
 
944
  /* Find the last list which has more than 1 partition.  */
945
  for (last = tpa->num_trees - 1; last > 0; last--)
946
    {
947
      first = tpa_first_partition (tpa, last);
948
      if (tpa_next_partition (tpa, first) != NO_PARTITION)
949
        break;
950
    }
951
 
952
  x = 0;
953
  while (x < last)
954
    {
955
      first = tpa_first_partition (tpa, x);
956
 
957
      /* If there is not more than one partition, swap with the current end
958
         of the tree list.  */
959
      if (tpa_next_partition (tpa, first) == NO_PARTITION)
960
        {
961
          swap_t = VEC_index (tree, tpa->trees, last);
962
          swap_i = VEC_index (int, tpa->first_partition, last);
963
 
964
          /* Update the last entry. Since it is known to only have one
965
             partition, there is nothing else to update.  */
966
          VEC_replace (tree, tpa->trees, last,
967
                       VEC_index (tree, tpa->trees, x));
968
          VEC_replace (int, tpa->first_partition, last,
969
                       VEC_index (int, tpa->first_partition, x));
970
          tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
971
 
972
          /* Since this list is known to have more than one partition, update
973
             the list owner entries.  */
974
          VEC_replace (tree, tpa->trees, x, swap_t);
975
          VEC_replace (int, tpa->first_partition, x, swap_i);
976
          for (y = tpa_first_partition (tpa, x);
977
               y != NO_PARTITION;
978
               y = tpa_next_partition (tpa, y))
979
            tpa->partition_to_tree_map[y] = x;
980
 
981
          /* Ensure last is a list with more than one partition.  */
982
          last--;
983
          for (; last > x; last--)
984
            {
985
              first = tpa_first_partition (tpa, last);
986
              if (tpa_next_partition (tpa, first) != NO_PARTITION)
987
                break;
988
            }
989
        }
990
      x++;
991
    }
992
 
993
  first = tpa_first_partition (tpa, x);
994
  if (tpa_next_partition (tpa, first) != NO_PARTITION)
995
    x++;
996
  tpa->uncompressed_num = tpa->num_trees;
997
  tpa->num_trees = x;
998
  return last;
999
}
1000
 
1001
 
1002
/* Initialize a root_var object with SSA partitions from MAP which are based
1003
   on each root variable.  */
1004
 
1005
root_var_p
1006
root_var_init (var_map map)
1007
{
1008
  root_var_p rv;
1009
  int num_partitions = num_var_partitions (map);
1010
  int x, p;
1011
  tree t;
1012
  var_ann_t ann;
1013
  sbitmap seen;
1014
 
1015
  rv = tpa_init (map);
1016
  if (!rv)
1017
    return NULL;
1018
 
1019
  seen = sbitmap_alloc (num_partitions);
1020
  sbitmap_zero (seen);
1021
 
1022
  /* Start at the end and work towards the front. This will provide a list
1023
     that is ordered from smallest to largest.  */
1024
  for (x = num_partitions - 1; x >= 0; x--)
1025
    {
1026
      t = partition_to_var (map, x);
1027
 
1028
      /* The var map may not be compacted yet, so check for NULL.  */
1029
      if (!t)
1030
        continue;
1031
 
1032
      p = var_to_partition (map, t);
1033
 
1034
      gcc_assert (p != NO_PARTITION);
1035
 
1036
      /* Make sure we only put coalesced partitions into the list once.  */
1037
      if (TEST_BIT (seen, p))
1038
        continue;
1039
      SET_BIT (seen, p);
1040
      if (TREE_CODE (t) == SSA_NAME)
1041
        t = SSA_NAME_VAR (t);
1042
      ann = var_ann (t);
1043
      if (ann->root_var_processed)
1044
        {
1045
          rv->next_partition[p] = VEC_index (int, rv->first_partition,
1046
                                             VAR_ANN_ROOT_INDEX (ann));
1047
          VEC_replace (int, rv->first_partition, VAR_ANN_ROOT_INDEX (ann), p);
1048
        }
1049
      else
1050
        {
1051
          ann->root_var_processed = 1;
1052
          VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
1053
          VEC_safe_push (tree, heap, rv->trees, t);
1054
          VEC_safe_push (int, heap, rv->first_partition, p);
1055
        }
1056
      rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
1057
    }
1058
 
1059
  /* Reset the out_of_ssa_tag flag on each variable for later use.  */
1060
  for (x = 0; x < rv->num_trees; x++)
1061
    {
1062
      t = VEC_index (tree, rv->trees, x);
1063
      var_ann (t)->root_var_processed = 0;
1064
    }
1065
 
1066
  sbitmap_free (seen);
1067
  return rv;
1068
}
1069
 
1070
 
1071
/* Initialize a type_var structure which associates all the partitions in MAP
1072
   of the same type to the type node's index.  Volatiles are ignored.  */
1073
 
1074
type_var_p
1075
type_var_init (var_map map)
1076
{
1077
  type_var_p tv;
1078
  int x, y, p;
1079
  int num_partitions = num_var_partitions (map);
1080
  tree t;
1081
  sbitmap seen;
1082
 
1083
  tv = tpa_init (map);
1084
  if (!tv)
1085
    return NULL;
1086
 
1087
  seen = sbitmap_alloc (num_partitions);
1088
  sbitmap_zero (seen);
1089
 
1090
  for (x = num_partitions - 1; x >= 0; x--)
1091
    {
1092
      t = partition_to_var (map, x);
1093
 
1094
      /* Disallow coalescing of these types of variables.  */
1095
      if (!t
1096
          || TREE_THIS_VOLATILE (t)
1097
          || TREE_CODE (t) == RESULT_DECL
1098
          || TREE_CODE (t) == PARM_DECL
1099
          || (DECL_P (t)
1100
              && (DECL_REGISTER (t)
1101
                  || !DECL_IGNORED_P (t)
1102
                  || DECL_RTL_SET_P (t))))
1103
        continue;
1104
 
1105
      p = var_to_partition (map, t);
1106
 
1107
      gcc_assert (p != NO_PARTITION);
1108
 
1109
      /* If partitions have been coalesced, only add the representative
1110
         for the partition to the list once.  */
1111
      if (TEST_BIT (seen, p))
1112
        continue;
1113
      SET_BIT (seen, p);
1114
      t = TREE_TYPE (t);
1115
 
1116
      /* Find the list for this type.  */
1117
      for (y = 0; y < tv->num_trees; y++)
1118
        if (t == VEC_index (tree, tv->trees, y))
1119
          break;
1120
      if (y == tv->num_trees)
1121
        {
1122
          tv->num_trees++;
1123
          VEC_safe_push (tree, heap, tv->trees, t);
1124
          VEC_safe_push (int, heap, tv->first_partition, p);
1125
        }
1126
      else
1127
        {
1128
          tv->next_partition[p] = VEC_index (int, tv->first_partition, y);
1129
          VEC_replace (int, tv->first_partition, y, p);
1130
        }
1131
      tv->partition_to_tree_map[p] = y;
1132
    }
1133
  sbitmap_free (seen);
1134
  return tv;
1135
}
1136
 
1137
 
1138
/* Create a new coalesce list object from MAP and return it.  */
1139
 
1140
coalesce_list_p
1141
create_coalesce_list (var_map map)
1142
{
1143
  coalesce_list_p list;
1144
 
1145
  list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
1146
 
1147
  list->map = map;
1148
  list->add_mode = true;
1149
  list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
1150
                                             sizeof (struct partition_pair_d));
1151
  return list;
1152
}
1153
 
1154
 
1155
/* Delete coalesce list CL.  */
1156
 
1157
void
1158
delete_coalesce_list (coalesce_list_p cl)
1159
{
1160
  free (cl->list);
1161
  free (cl);
1162
}
1163
 
1164
 
1165
/* Find a matching coalesce pair object in CL for partitions P1 and P2.  If
1166
   one isn't found, return NULL if CREATE is false, otherwise create a new
1167
   coalesce pair object and return it.  */
1168
 
1169
static partition_pair_p
1170
find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
1171
{
1172
  partition_pair_p node, tmp;
1173
  int s;
1174
 
1175
  /* Normalize so that p1 is the smaller value.  */
1176
  if (p2 < p1)
1177
    {
1178
      s = p1;
1179
      p1 = p2;
1180
      p2 = s;
1181
    }
1182
 
1183
  tmp = NULL;
1184
 
1185
  /* The list is sorted such that if we find a value greater than p2,
1186
     p2 is not in the list.  */
1187
  for (node = cl->list[p1]; node; node = node->next)
1188
    {
1189
      if (node->second_partition == p2)
1190
        return node;
1191
      else
1192
        if (node->second_partition > p2)
1193
          break;
1194
     tmp = node;
1195
    }
1196
 
1197
  if (!create)
1198
    return NULL;
1199
 
1200
  node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
1201
  node->first_partition = p1;
1202
  node->second_partition = p2;
1203
  node->cost = 0;
1204
 
1205
  if (tmp != NULL)
1206
    {
1207
      node->next = tmp->next;
1208
      tmp->next = node;
1209
    }
1210
  else
1211
    {
1212
      /* This is now the first node in the list.  */
1213
      node->next = cl->list[p1];
1214
      cl->list[p1] = node;
1215
    }
1216
 
1217
  return node;
1218
}
1219
 
1220
/* Return cost of execution of copy instruction with FREQUENCY
1221
   possibly on CRITICAL edge and in HOT basic block.  */
1222
int
1223
coalesce_cost (int frequency, bool hot, bool critical)
1224
{
1225
  /* Base costs on BB frequencies bounded by 1.  */
1226
  int cost = frequency;
1227
 
1228
  if (!cost)
1229
    cost = 1;
1230
  if (optimize_size || hot)
1231
    cost = 1;
1232
  /* Inserting copy on critical edge costs more
1233
     than inserting it elsewhere.  */
1234
  if (critical)
1235
    cost *= 2;
1236
  return cost;
1237
}
1238
 
1239
/* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE.  */
1240
 
1241
void
1242
add_coalesce (coalesce_list_p cl, int p1, int p2,
1243
              int value)
1244
{
1245
  partition_pair_p node;
1246
 
1247
  gcc_assert (cl->add_mode);
1248
 
1249
  if (p1 == p2)
1250
    return;
1251
 
1252
  node = find_partition_pair (cl, p1, p2, true);
1253
 
1254
  node->cost += value;
1255
}
1256
 
1257
 
1258
/* Comparison function to allow qsort to sort P1 and P2 in descending order.  */
1259
 
1260
static
1261
int compare_pairs (const void *p1, const void *p2)
1262
{
1263
#if 0
1264
  partition_pair_p * pp1 = (partition_pair_p *) p1;
1265
  partition_pair_p * pp2 = (partition_pair_p *) p2;
1266
  int result;
1267
 
1268
  result = (* pp2)->cost - (* pp1)->cost;
1269
  /* Issue 128204: Cygwin vs Linux host differences:
1270
     If the costs are the same, use the partition indicies in order to
1271
     obtain a stable, reproducible sort.  Otherwise the ordering will
1272
     be at the mercy of the host's qsort library function implementation.  */
1273
  if (result == 0)
1274
    {
1275
      result = (* pp2)->first_partition - (* pp1)->first_partition;
1276
      if (result == 0)
1277
        result = (* pp2)->second_partition - (* pp1)->second_partition;
1278
    }
1279
 
1280
  return result;
1281
#else  
1282
  return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
1283
#endif
1284
}
1285
 
1286
 
1287
/* Prepare CL for removal of preferred pairs.  When finished, list element
1288
 
1289
   to least important.  */
1290
 
1291
void
1292
sort_coalesce_list (coalesce_list_p cl)
1293
{
1294
  unsigned x, num, count;
1295
  partition_pair_p chain, p;
1296
  partition_pair_p  *list;
1297
 
1298
  gcc_assert (cl->add_mode);
1299
 
1300
  cl->add_mode = false;
1301
 
1302
  /* Compact the array of lists to a single list, and count the elements.  */
1303
  num = 0;
1304
  chain = NULL;
1305
  for (x = 0; x < num_var_partitions (cl->map); x++)
1306
    if (cl->list[x] != NULL)
1307
      {
1308
        for (p = cl->list[x]; p->next != NULL; p = p->next)
1309
          num++;
1310
        num++;
1311
        p->next = chain;
1312
        chain = cl->list[x];
1313
        cl->list[x] = NULL;
1314
      }
1315
 
1316
  /* Only call qsort if there are more than 2 items.  */
1317
  if (num > 2)
1318
    {
1319
      list = XNEWVEC (partition_pair_p, num);
1320
      count = 0;
1321
      for (p = chain; p != NULL; p = p->next)
1322
        list[count++] = p;
1323
 
1324
      gcc_assert (count == num);
1325
 
1326
      qsort (list, count, sizeof (partition_pair_p), compare_pairs);
1327
 
1328
      p = list[0];
1329
      for (x = 1; x < num; x++)
1330
        {
1331
          p->next = list[x];
1332
          p = list[x];
1333
        }
1334
      p->next = NULL;
1335
      cl->list[0] = list[0];
1336
      free (list);
1337
    }
1338
  else
1339
    {
1340
      cl->list[0] = chain;
1341
      if (num == 2)
1342
        {
1343
          /* Simply swap the two elements if they are in the wrong order.  */
1344
          if (chain->cost < chain->next->cost)
1345
            {
1346
              cl->list[0] = chain->next;
1347
              cl->list[0]->next = chain;
1348
              chain->next = NULL;
1349
            }
1350
        }
1351
    }
1352
}
1353
 
1354
 
1355
/* Retrieve the best remaining pair to coalesce from CL.  Returns the 2
1356
   partitions via P1 and P2.  Their calculated cost is returned by the function.
1357
   NO_BEST_COALESCE is returned if the coalesce list is empty.  */
1358
 
1359
static int
1360
pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
1361
{
1362
  partition_pair_p node;
1363
  int ret;
1364
 
1365
  gcc_assert (!cl->add_mode);
1366
 
1367
  node = cl->list[0];
1368
  if (!node)
1369
    return NO_BEST_COALESCE;
1370
 
1371
  cl->list[0] = node->next;
1372
 
1373
  *p1 = node->first_partition;
1374
  *p2 = node->second_partition;
1375
  ret = node->cost;
1376
  free (node);
1377
 
1378
  return ret;
1379
}
1380
 
1381
 
1382
/* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
1383
   VAR and any other live partitions in VEC which are associated via TPA.
1384
   Reset the live bit in VEC.  */
1385
 
1386
static inline void
1387
add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
1388
                        var_map map, bitmap vec, tree var)
1389
{
1390
  int p, y, first;
1391
  p = var_to_partition (map, var);
1392
  if (p != NO_PARTITION)
1393
    {
1394
      bitmap_clear_bit (vec, p);
1395
      first = tpa_find_tree (tpa, p);
1396
      /* If find returns nothing, this object isn't interesting.  */
1397
      if (first == TPA_NONE)
1398
        return;
1399
      /* Only add interferences between objects in the same list.  */
1400
      for (y = tpa_first_partition (tpa, first);
1401
           y != TPA_NONE;
1402
           y = tpa_next_partition (tpa, y))
1403
        {
1404
          if (bitmap_bit_p (vec, y))
1405
            conflict_graph_add (graph, p, y);
1406
        }
1407
    }
1408
}
1409
 
1410
/* Return a conflict graph for the information contained in LIVE_INFO.  Only
1411
   conflicts between items in the same TPA list are added.  If optional
1412
   coalesce list CL is passed in, any copies encountered are added.  */
1413
 
1414
conflict_graph
1415
build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
1416
                           coalesce_list_p cl)
1417
{
1418
  conflict_graph graph;
1419
  var_map map;
1420
  bitmap live;
1421
  unsigned x, y, i;
1422
  basic_block bb;
1423
  int *partition_link, *tpa_nodes;
1424
  VEC(int,heap) *tpa_to_clear;
1425
  unsigned l;
1426
  ssa_op_iter iter;
1427
  bitmap_iterator bi;
1428
 
1429
  map = live_var_map (liveinfo);
1430
  graph = conflict_graph_new (num_var_partitions (map));
1431
 
1432
  if (tpa_num_trees (tpa) == 0)
1433
    return graph;
1434
 
1435
  live = BITMAP_ALLOC (NULL);
1436
 
1437
  partition_link = XCNEWVEC (int, num_var_partitions (map) + 1);
1438
  tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa));
1439
  tpa_to_clear = VEC_alloc (int, heap, 50);
1440
 
1441
  FOR_EACH_BB (bb)
1442
    {
1443
      block_stmt_iterator bsi;
1444
      tree phi;
1445
      int idx;
1446
 
1447
      /* Start with live on exit temporaries.  */
1448
      bitmap_copy (live, live_on_exit (liveinfo, bb));
1449
 
1450
      for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1451
        {
1452
          bool is_a_copy = false;
1453
          tree stmt = bsi_stmt (bsi);
1454
 
1455
          /* A copy between 2 partitions does not introduce an interference
1456
             by itself.  If they did, you would never be able to coalesce
1457
             two things which are copied.  If the two variables really do
1458
             conflict, they will conflict elsewhere in the program.
1459
 
1460
             This is handled specially here since we may also be interested
1461
             in copies between real variables and SSA_NAME variables.  We may
1462
             be interested in trying to coalesce SSA_NAME variables with
1463
             root variables in some cases.  */
1464
 
1465
          if (TREE_CODE (stmt) == MODIFY_EXPR)
1466
            {
1467
              tree lhs = TREE_OPERAND (stmt, 0);
1468
              tree rhs = TREE_OPERAND (stmt, 1);
1469
              int p1, p2;
1470
              int bit;
1471
 
1472
              if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
1473
                p1 = var_to_partition (map, lhs);
1474
              else
1475
                p1 = NO_PARTITION;
1476
 
1477
              if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
1478
                p2 = var_to_partition (map, rhs);
1479
              else
1480
                p2 = NO_PARTITION;
1481
 
1482
              if (p1 != NO_PARTITION && p2 != NO_PARTITION)
1483
                {
1484
                  is_a_copy = true;
1485
                  bit = bitmap_bit_p (live, p2);
1486
                  /* If the RHS is live, make it not live while we add
1487
                     the conflicts, then make it live again.  */
1488
                  if (bit)
1489
                    bitmap_clear_bit (live, p2);
1490
                  add_conflicts_if_valid (tpa, graph, map, live, lhs);
1491
                  if (bit)
1492
                    bitmap_set_bit (live, p2);
1493
                  if (cl)
1494
                    add_coalesce (cl, p1, p2,
1495
                                  coalesce_cost (bb->frequency,
1496
                                                 maybe_hot_bb_p (bb), false));
1497
                  set_if_valid (map, live, rhs);
1498
                }
1499
            }
1500
 
1501
          if (!is_a_copy)
1502
            {
1503
              tree var;
1504
              FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
1505
                {
1506
                  add_conflicts_if_valid (tpa, graph, map, live, var);
1507
                }
1508
 
1509
              FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1510
                {
1511
                  set_if_valid (map, live, var);
1512
                }
1513
            }
1514
        }
1515
 
1516
      /* If result of a PHI is unused, then the loops over the statements
1517
         will not record any conflicts.  However, since the PHI node is
1518
         going to be translated out of SSA form we must record a conflict
1519
         between the result of the PHI and any variables with are live.
1520
         Otherwise the out-of-ssa translation may create incorrect code.  */
1521
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1522
        {
1523
          tree result = PHI_RESULT (phi);
1524
          int p = var_to_partition (map, result);
1525
 
1526
          if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
1527
            add_conflicts_if_valid (tpa, graph, map, live, result);
1528
        }
1529
 
1530
      /* Anything which is still live at this point interferes.
1531
         In order to implement this efficiently, only conflicts between
1532
         partitions which have the same TPA root need be added.
1533
         TPA roots which have been seen are tracked in 'tpa_nodes'.  A nonzero
1534
         entry points to an index into 'partition_link', which then indexes
1535
         into itself forming a linked list of partitions sharing a tpa root
1536
         which have been seen as live up to this point.  Since partitions start
1537
         at index zero, all entries in partition_link are (partition + 1).
1538
 
1539
         Conflicts are added between the current partition and any already seen.
1540
         tpa_clear contains all the tpa_roots processed, and these are the only
1541
         entries which need to be zero'd out for a clean restart.  */
1542
 
1543
      EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
1544
        {
1545
          i = tpa_find_tree (tpa, x);
1546
          if (i != (unsigned)TPA_NONE)
1547
            {
1548
              int start = tpa_nodes[i];
1549
              /* If start is 0, a new root reference list is being started.
1550
                 Register it to be cleared.  */
1551
              if (!start)
1552
                VEC_safe_push (int, heap, tpa_to_clear, i);
1553
 
1554
              /* Add interferences to other tpa members seen.  */
1555
              for (y = start; y != 0; y = partition_link[y])
1556
                conflict_graph_add (graph, x, y - 1);
1557
              tpa_nodes[i] = x + 1;
1558
              partition_link[x + 1] = start;
1559
            }
1560
        }
1561
 
1562
        /* Now clear the used tpa root references.  */
1563
        for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++)
1564
          tpa_nodes[idx] = 0;
1565
        VEC_truncate (int, tpa_to_clear, 0);
1566
    }
1567
 
1568
  free (tpa_nodes);
1569
  free (partition_link);
1570
  VEC_free (int, heap, tpa_to_clear);
1571
  BITMAP_FREE (live);
1572
  return graph;
1573
}
1574
 
1575
 
1576
/* This routine will attempt to coalesce the elements in TPA subject to the
1577
   conflicts found in GRAPH.  If optional coalesce_list CL is provided,
1578
   only coalesces specified within the coalesce list are attempted.  Otherwise
1579
   an attempt is made to coalesce as many partitions within each TPA grouping
1580
   as possible.  If DEBUG is provided, debug output will be sent there.  */
1581
 
1582
void
1583
coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
1584
                      coalesce_list_p cl, FILE *debug)
1585
{
1586
  int x, y, z, w;
1587
  tree var, tmp;
1588
 
1589
  /* Attempt to coalesce any items in a coalesce list.  */
1590
  if (cl)
1591
    {
1592
      while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
1593
        {
1594
          if (debug)
1595
            {
1596
              fprintf (debug, "Coalesce list: (%d)", x);
1597
              print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
1598
              fprintf (debug, " & (%d)", y);
1599
              print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
1600
            }
1601
 
1602
          w = tpa_find_tree (tpa, x);
1603
          z = tpa_find_tree (tpa, y);
1604
          if (w != z || w == TPA_NONE || z == TPA_NONE)
1605
            {
1606
              if (debug)
1607
                {
1608
                  if (w != z)
1609
                    fprintf (debug, ": Fail, Non-matching TPA's\n");
1610
                  if (w == TPA_NONE)
1611
                    fprintf (debug, ": Fail %d non TPA.\n", x);
1612
                  else
1613
                    fprintf (debug, ": Fail %d non TPA.\n", y);
1614
                }
1615
              continue;
1616
            }
1617
          var = partition_to_var (map, x);
1618
          tmp = partition_to_var (map, y);
1619
          x = var_to_partition (map, var);
1620
          y = var_to_partition (map, tmp);
1621
          if (debug)
1622
            fprintf (debug, " [map: %d, %d] ", x, y);
1623
          if (x == y)
1624
            {
1625
              if (debug)
1626
                fprintf (debug, ": Already Coalesced.\n");
1627
              continue;
1628
            }
1629
          if (!conflict_graph_conflict_p (graph, x, y))
1630
            {
1631
              z = var_union (map, var, tmp);
1632
              if (z == NO_PARTITION)
1633
                {
1634
                  if (debug)
1635
                    fprintf (debug, ": Unable to perform partition union.\n");
1636
                  continue;
1637
                }
1638
 
1639
              /* z is the new combined partition. We need to remove the other
1640
                 partition from the list. Set x to be that other partition.  */
1641
              if (z == x)
1642
                {
1643
                  conflict_graph_merge_regs (graph, x, y);
1644
                  w = tpa_find_tree (tpa, y);
1645
                  tpa_remove_partition (tpa, w, y);
1646
                }
1647
              else
1648
                {
1649
                  conflict_graph_merge_regs (graph, y, x);
1650
                  w = tpa_find_tree (tpa, x);
1651
                  tpa_remove_partition (tpa, w, x);
1652
                }
1653
 
1654
              if (debug)
1655
                fprintf (debug, ": Success -> %d\n", z);
1656
            }
1657
          else
1658
            if (debug)
1659
              fprintf (debug, ": Fail due to conflict\n");
1660
        }
1661
      /* If using a coalesce list, don't try to coalesce anything else.  */
1662
      return;
1663
    }
1664
 
1665
  for (x = 0; x < tpa_num_trees (tpa); x++)
1666
    {
1667
      while (tpa_first_partition (tpa, x) != TPA_NONE)
1668
        {
1669
          int p1, p2;
1670
          /* Coalesce first partition with anything that doesn't conflict.  */
1671
          y = tpa_first_partition (tpa, x);
1672
          tpa_remove_partition (tpa, x, y);
1673
 
1674
          var = partition_to_var (map, y);
1675
          /* p1 is the partition representative to which y belongs.  */
1676
          p1 = var_to_partition (map, var);
1677
 
1678
          for (z = tpa_next_partition (tpa, y);
1679
               z != TPA_NONE;
1680
               z = tpa_next_partition (tpa, z))
1681
            {
1682
              tmp = partition_to_var (map, z);
1683
              /* p2 is the partition representative to which z belongs.  */
1684
              p2 = var_to_partition (map, tmp);
1685
              if (debug)
1686
                {
1687
                  fprintf (debug, "Coalesce : ");
1688
                  print_generic_expr (debug, var, TDF_SLIM);
1689
                  fprintf (debug, " &");
1690
                  print_generic_expr (debug, tmp, TDF_SLIM);
1691
                  fprintf (debug, "  (%d ,%d)", p1, p2);
1692
                }
1693
 
1694
              /* If partitions are already merged, don't check for conflict.  */
1695
              if (tmp == var)
1696
                {
1697
                  tpa_remove_partition (tpa, x, z);
1698
                  if (debug)
1699
                    fprintf (debug, ": Already coalesced\n");
1700
                }
1701
              else
1702
                if (!conflict_graph_conflict_p (graph, p1, p2))
1703
                  {
1704
                    int v;
1705
                    if (tpa_find_tree (tpa, y) == TPA_NONE
1706
                        || tpa_find_tree (tpa, z) == TPA_NONE)
1707
                      {
1708
                        if (debug)
1709
                          fprintf (debug, ": Fail non-TPA member\n");
1710
                        continue;
1711
                      }
1712
                    if ((v = var_union (map, var, tmp)) == NO_PARTITION)
1713
                      {
1714
                        if (debug)
1715
                          fprintf (debug, ": Fail cannot combine partitions\n");
1716
                        continue;
1717
                      }
1718
 
1719
                    tpa_remove_partition (tpa, x, z);
1720
                    if (v == p1)
1721
                      conflict_graph_merge_regs (graph, v, z);
1722
                    else
1723
                      {
1724
                        /* Update the first partition's representative.  */
1725
                        conflict_graph_merge_regs (graph, v, y);
1726
                        p1 = v;
1727
                      }
1728
 
1729
                    /* The root variable of the partition may be changed
1730
                       now.  */
1731
                    var = partition_to_var (map, p1);
1732
 
1733
                    if (debug)
1734
                      fprintf (debug, ": Success -> %d\n", v);
1735
                  }
1736
                else
1737
                  if (debug)
1738
                    fprintf (debug, ": Fail, Conflict\n");
1739
            }
1740
        }
1741
    }
1742
}
1743
 
1744
 
1745
/* Send debug info for coalesce list CL to file F.  */
1746
 
1747
void
1748
dump_coalesce_list (FILE *f, coalesce_list_p cl)
1749
{
1750
  partition_pair_p node;
1751
  int x, num;
1752
  tree var;
1753
 
1754
  if (cl->add_mode)
1755
    {
1756
      fprintf (f, "Coalesce List:\n");
1757
      num = num_var_partitions (cl->map);
1758
      for (x = 0; x < num; x++)
1759
        {
1760
          node = cl->list[x];
1761
          if (node)
1762
            {
1763
              fprintf (f, "[");
1764
              print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
1765
              fprintf (f, "] - ");
1766
              for ( ; node; node = node->next)
1767
                {
1768
                  var = partition_to_var (cl->map, node->second_partition);
1769
                  print_generic_expr (f, var, TDF_SLIM);
1770
                  fprintf (f, "(%1d), ", node->cost);
1771
                }
1772
              fprintf (f, "\n");
1773
            }
1774
        }
1775
    }
1776
  else
1777
    {
1778
      fprintf (f, "Sorted Coalesce list:\n");
1779
      for (node = cl->list[0]; node; node = node->next)
1780
        {
1781
          fprintf (f, "(%d) ", node->cost);
1782
          var = partition_to_var (cl->map, node->first_partition);
1783
          print_generic_expr (f, var, TDF_SLIM);
1784
          fprintf (f, " : ");
1785
          var = partition_to_var (cl->map, node->second_partition);
1786
          print_generic_expr (f, var, TDF_SLIM);
1787
          fprintf (f, "\n");
1788
        }
1789
    }
1790
}
1791
 
1792
 
1793
/* Output tree_partition_associator object TPA to file F..  */
1794
 
1795
void
1796
tpa_dump (FILE *f, tpa_p tpa)
1797
{
1798
  int x, i;
1799
 
1800
  if (!tpa)
1801
    return;
1802
 
1803
  for (x = 0; x < tpa_num_trees (tpa); x++)
1804
    {
1805
      print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
1806
      fprintf (f, " : (");
1807
      for (i = tpa_first_partition (tpa, x);
1808
           i != TPA_NONE;
1809
           i = tpa_next_partition (tpa, i))
1810
        {
1811
          fprintf (f, "(%d)",i);
1812
          print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
1813
          fprintf (f, " ");
1814
 
1815
#ifdef ENABLE_CHECKING
1816
          if (tpa_find_tree (tpa, i) != x)
1817
            fprintf (f, "**find tree incorrectly set** ");
1818
#endif
1819
 
1820
        }
1821
      fprintf (f, ")\n");
1822
    }
1823
  fflush (f);
1824
}
1825
 
1826
 
1827
/* Output partition map MAP to file F.  */
1828
 
1829
void
1830
dump_var_map (FILE *f, var_map map)
1831
{
1832
  int t;
1833
  unsigned x, y;
1834
  int p;
1835
 
1836
  fprintf (f, "\nPartition map \n\n");
1837
 
1838
  for (x = 0; x < map->num_partitions; x++)
1839
    {
1840
      if (map->compact_to_partition != NULL)
1841
        p = map->compact_to_partition[x];
1842
      else
1843
        p = x;
1844
 
1845
      if (map->partition_to_var[p] == NULL_TREE)
1846
        continue;
1847
 
1848
      t = 0;
1849
      for (y = 1; y < num_ssa_names; y++)
1850
        {
1851
          p = partition_find (map->var_partition, y);
1852
          if (map->partition_to_compact)
1853
            p = map->partition_to_compact[p];
1854
          if (p == (int)x)
1855
            {
1856
              if (t++ == 0)
1857
                {
1858
                  fprintf(f, "Partition %d (", x);
1859
                  print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1860
                  fprintf (f, " - ");
1861
                }
1862
              fprintf (f, "%d ", y);
1863
            }
1864
        }
1865
      if (t != 0)
1866
        fprintf (f, ")\n");
1867
    }
1868
  fprintf (f, "\n");
1869
}
1870
 
1871
 
1872
/* Output live range info LIVE to file F, controlled by FLAG.  */
1873
 
1874
void
1875
dump_live_info (FILE *f, tree_live_info_p live, int flag)
1876
{
1877
  basic_block bb;
1878
  unsigned i;
1879
  var_map map = live->map;
1880
  bitmap_iterator bi;
1881
 
1882
  if ((flag & LIVEDUMP_ENTRY) && live->livein)
1883
    {
1884
      FOR_EACH_BB (bb)
1885
        {
1886
          fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1887
          for (i = 0; i < num_var_partitions (map); i++)
1888
            {
1889
              if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
1890
                {
1891
                  print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1892
                  fprintf (f, "  ");
1893
                }
1894
            }
1895
          fprintf (f, "\n");
1896
        }
1897
    }
1898
 
1899
  if ((flag & LIVEDUMP_EXIT) && live->liveout)
1900
    {
1901
      FOR_EACH_BB (bb)
1902
        {
1903
          fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1904
          EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1905
            {
1906
              print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1907
              fprintf (f, "  ");
1908
            }
1909
          fprintf (f, "\n");
1910
        }
1911
    }
1912
}
1913
 
1914
#ifdef ENABLE_CHECKING
1915
void
1916
register_ssa_partition_check (tree ssa_var)
1917
{
1918
  gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1919
  if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1920
    {
1921
      fprintf (stderr, "Illegally registering a virtual SSA name :");
1922
      print_generic_expr (stderr, ssa_var, TDF_SLIM);
1923
      fprintf (stderr, " in the SSA->Normal phase.\n");
1924
      internal_error ("SSA corruption");
1925
    }
1926
}
1927
#endif

powered by: WebSVN 2.1.0

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