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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [ira-build.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Building internal representation for IRA.
2
   Copyright (C) 2006, 2007, 2008, 2009
3
   Free Software Foundation, Inc.
4
   Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify it under
9
the terms of the GNU General Public License as published by the Free
10
Software Foundation; either version 3, or (at your option) any later
11
version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14
WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
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 "rtl.h"
27
#include "tm_p.h"
28
#include "target.h"
29
#include "regs.h"
30
#include "flags.h"
31
#include "hard-reg-set.h"
32
#include "basic-block.h"
33
#include "insn-config.h"
34
#include "recog.h"
35
#include "toplev.h"
36
#include "params.h"
37
#include "df.h"
38
#include "output.h"
39
#include "reload.h"
40
#include "sparseset.h"
41
#include "ira-int.h"
42
 
43
static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx,
44
                                     ira_loop_tree_node_t);
45
 
46
/* The root of the loop tree corresponding to the all function.  */
47
ira_loop_tree_node_t ira_loop_tree_root;
48
 
49
/* Height of the loop tree.  */
50
int ira_loop_tree_height;
51
 
52
/* All nodes representing basic blocks are referred through the
53
   following array.  We can not use basic block member `aux' for this
54
   because it is used for insertion of insns on edges.  */
55
ira_loop_tree_node_t ira_bb_nodes;
56
 
57
/* All nodes representing loops are referred through the following
58
   array.  */
59
ira_loop_tree_node_t ira_loop_nodes;
60
 
61
/* Map regno -> allocnos with given regno (see comments for
62
   allocno member `next_regno_allocno').  */
63
ira_allocno_t *ira_regno_allocno_map;
64
 
65
/* Array of references to all allocnos.  The order number of the
66
   allocno corresponds to the index in the array.  Removed allocnos
67
   have NULL element value.  */
68
ira_allocno_t *ira_allocnos;
69
 
70
/* Sizes of the previous array.  */
71
int ira_allocnos_num;
72
 
73
/* Map conflict id -> allocno with given conflict id (see comments for
74
   allocno member `conflict_id').  */
75
ira_allocno_t *ira_conflict_id_allocno_map;
76
 
77
/* Array of references to all copies.  The order number of the copy
78
   corresponds to the index in the array.  Removed copies have NULL
79
   element value.  */
80
ira_copy_t *ira_copies;
81
 
82
/* Size of the previous array.  */
83
int ira_copies_num;
84
 
85
 
86
 
87
/* LAST_BASIC_BLOCK before generating additional insns because of live
88
   range splitting.  Emitting insns on a critical edge creates a new
89
   basic block.  */
90
static int last_basic_block_before_change;
91
 
92
/* The following function allocates the loop tree nodes.  If LOOPS_P
93
   is FALSE, the nodes corresponding to the loops (except the root
94
   which corresponds the all function) will be not allocated but nodes
95
   will still be allocated for basic blocks.  */
96
static void
97
create_loop_tree_nodes (bool loops_p)
98
{
99
  unsigned int i, j;
100
  int max_regno;
101
  bool skip_p;
102
  edge_iterator ei;
103
  edge e;
104
  VEC (edge, heap) *edges;
105
  loop_p loop;
106
 
107
  ira_bb_nodes
108
    = ((struct ira_loop_tree_node *)
109
       ira_allocate (sizeof (struct ira_loop_tree_node) * last_basic_block));
110
  last_basic_block_before_change = last_basic_block;
111
  for (i = 0; i < (unsigned int) last_basic_block; i++)
112
    {
113
      ira_bb_nodes[i].regno_allocno_map = NULL;
114
      memset (ira_bb_nodes[i].reg_pressure, 0,
115
              sizeof (ira_bb_nodes[i].reg_pressure));
116
      ira_bb_nodes[i].all_allocnos = NULL;
117
      ira_bb_nodes[i].modified_regnos = NULL;
118
      ira_bb_nodes[i].border_allocnos = NULL;
119
      ira_bb_nodes[i].local_copies = NULL;
120
    }
121
  ira_loop_nodes = ((struct ira_loop_tree_node *)
122
                    ira_allocate (sizeof (struct ira_loop_tree_node)
123
                                  * VEC_length (loop_p, ira_loops.larray)));
124
  max_regno = max_reg_num ();
125
  for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
126
    {
127
      if (loop != ira_loops.tree_root)
128
        {
129
          ira_loop_nodes[i].regno_allocno_map = NULL;
130
          if (! loops_p)
131
            continue;
132
          skip_p = false;
133
          FOR_EACH_EDGE (e, ei, loop->header->preds)
134
            if (e->src != loop->latch
135
                && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
136
              {
137
                skip_p = true;
138
                break;
139
              }
140
          if (skip_p)
141
            continue;
142
          edges = get_loop_exit_edges (loop);
143
          for (j = 0; VEC_iterate (edge, edges, j, e); j++)
144
            if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
145
              {
146
                skip_p = true;
147
                break;
148
              }
149
          VEC_free (edge, heap, edges);
150
          if (skip_p)
151
            continue;
152
        }
153
      ira_loop_nodes[i].regno_allocno_map
154
        = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
155
      memset (ira_loop_nodes[i].regno_allocno_map, 0,
156
              sizeof (ira_allocno_t) * max_regno);
157
      memset (ira_loop_nodes[i].reg_pressure, 0,
158
              sizeof (ira_loop_nodes[i].reg_pressure));
159
      ira_loop_nodes[i].all_allocnos = ira_allocate_bitmap ();
160
      ira_loop_nodes[i].modified_regnos = ira_allocate_bitmap ();
161
      ira_loop_nodes[i].border_allocnos = ira_allocate_bitmap ();
162
      ira_loop_nodes[i].local_copies = ira_allocate_bitmap ();
163
    }
164
}
165
 
166
/* The function returns TRUE if there are more one allocation
167
   region.  */
168
static bool
169
more_one_region_p (void)
170
{
171
  unsigned int i;
172
  loop_p loop;
173
 
174
  for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
175
    if (ira_loop_nodes[i].regno_allocno_map != NULL
176
        && ira_loop_tree_root != &ira_loop_nodes[i])
177
      return true;
178
  return false;
179
}
180
 
181
/* Free the loop tree node of a loop.  */
182
static void
183
finish_loop_tree_node (ira_loop_tree_node_t loop)
184
{
185
  if (loop->regno_allocno_map != NULL)
186
    {
187
      ira_assert (loop->bb == NULL);
188
      ira_free_bitmap (loop->local_copies);
189
      ira_free_bitmap (loop->border_allocnos);
190
      ira_free_bitmap (loop->modified_regnos);
191
      ira_free_bitmap (loop->all_allocnos);
192
      ira_free (loop->regno_allocno_map);
193
      loop->regno_allocno_map = NULL;
194
    }
195
}
196
 
197
/* Free the loop tree nodes.  */
198
static void
199
finish_loop_tree_nodes (void)
200
{
201
  unsigned int i;
202
  loop_p loop;
203
 
204
  for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
205
    finish_loop_tree_node (&ira_loop_nodes[i]);
206
  ira_free (ira_loop_nodes);
207
  for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
208
    {
209
      if (ira_bb_nodes[i].local_copies != NULL)
210
        ira_free_bitmap (ira_bb_nodes[i].local_copies);
211
      if (ira_bb_nodes[i].border_allocnos != NULL)
212
        ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
213
      if (ira_bb_nodes[i].modified_regnos != NULL)
214
        ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
215
      if (ira_bb_nodes[i].all_allocnos != NULL)
216
        ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
217
      if (ira_bb_nodes[i].regno_allocno_map != NULL)
218
        ira_free (ira_bb_nodes[i].regno_allocno_map);
219
    }
220
  ira_free (ira_bb_nodes);
221
}
222
 
223
 
224
 
225
/* The following recursive function adds LOOP to the loop tree
226
   hierarchy.  LOOP is added only once.  */
227
static void
228
add_loop_to_tree (struct loop *loop)
229
{
230
  struct loop *parent;
231
  ira_loop_tree_node_t loop_node, parent_node;
232
 
233
  /* We can not use loop node access macros here because of potential
234
     checking and because the nodes are not initialized enough
235
     yet.  */
236
  if (loop_outer (loop) != NULL)
237
    add_loop_to_tree (loop_outer (loop));
238
  if (ira_loop_nodes[loop->num].regno_allocno_map != NULL
239
      && ira_loop_nodes[loop->num].children == NULL)
240
    {
241
      /* We have not added loop node to the tree yet.  */
242
      loop_node = &ira_loop_nodes[loop->num];
243
      loop_node->loop = loop;
244
      loop_node->bb = NULL;
245
      for (parent = loop_outer (loop);
246
           parent != NULL;
247
           parent = loop_outer (parent))
248
        if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
249
          break;
250
      if (parent == NULL)
251
        {
252
          loop_node->next = NULL;
253
          loop_node->subloop_next = NULL;
254
          loop_node->parent = NULL;
255
        }
256
      else
257
        {
258
          parent_node = &ira_loop_nodes[parent->num];
259
          loop_node->next = parent_node->children;
260
          parent_node->children = loop_node;
261
          loop_node->subloop_next = parent_node->subloops;
262
          parent_node->subloops = loop_node;
263
          loop_node->parent = parent_node;
264
        }
265
    }
266
}
267
 
268
/* The following recursive function sets up levels of nodes of the
269
   tree given its root LOOP_NODE.  The enumeration starts with LEVEL.
270
   The function returns maximal value of level in the tree + 1.  */
271
static int
272
setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
273
{
274
  int height, max_height;
275
  ira_loop_tree_node_t subloop_node;
276
 
277
  ira_assert (loop_node->bb == NULL);
278
  loop_node->level = level;
279
  max_height = level + 1;
280
  for (subloop_node = loop_node->subloops;
281
       subloop_node != NULL;
282
       subloop_node = subloop_node->subloop_next)
283
    {
284
      ira_assert (subloop_node->bb == NULL);
285
      height = setup_loop_tree_level (subloop_node, level + 1);
286
      if (height > max_height)
287
        max_height = height;
288
    }
289
  return max_height;
290
}
291
 
292
/* Create the loop tree.  The algorithm is designed to provide correct
293
   order of loops (they are ordered by their last loop BB) and basic
294
   blocks in the chain formed by member next.  */
295
static void
296
form_loop_tree (void)
297
{
298
  unsigned int i;
299
  basic_block bb;
300
  struct loop *parent;
301
  ira_loop_tree_node_t bb_node, loop_node;
302
  loop_p loop;
303
 
304
  /* We can not use loop/bb node access macros because of potential
305
     checking and because the nodes are not initialized enough
306
     yet.  */
307
  for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
308
     if (ira_loop_nodes[i].regno_allocno_map != NULL)
309
       {
310
         ira_loop_nodes[i].children = NULL;
311
         ira_loop_nodes[i].subloops = NULL;
312
       }
313
  FOR_EACH_BB (bb)
314
    {
315
      bb_node = &ira_bb_nodes[bb->index];
316
      bb_node->bb = bb;
317
      bb_node->loop = NULL;
318
      bb_node->subloops = NULL;
319
      bb_node->children = NULL;
320
      bb_node->subloop_next = NULL;
321
      bb_node->next = NULL;
322
      for (parent = bb->loop_father;
323
           parent != NULL;
324
           parent = loop_outer (parent))
325
        if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
326
          break;
327
      add_loop_to_tree (parent);
328
      loop_node = &ira_loop_nodes[parent->num];
329
      bb_node->next = loop_node->children;
330
      bb_node->parent = loop_node;
331
      loop_node->children = bb_node;
332
    }
333
  ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (ira_loops.tree_root->num);
334
  ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
335
  ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
336
}
337
 
338
 
339
 
340
/* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
341
   tree nodes.  */
342
static void
343
rebuild_regno_allocno_maps (void)
344
{
345
  unsigned int l;
346
  int max_regno, regno;
347
  ira_allocno_t a;
348
  ira_loop_tree_node_t loop_tree_node;
349
  loop_p loop;
350
  ira_allocno_iterator ai;
351
 
352
  max_regno = max_reg_num ();
353
  for (l = 0; VEC_iterate (loop_p, ira_loops.larray, l, loop); l++)
354
    if (ira_loop_nodes[l].regno_allocno_map != NULL)
355
      {
356
        ira_free (ira_loop_nodes[l].regno_allocno_map);
357
        ira_loop_nodes[l].regno_allocno_map
358
          = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
359
                                            * max_regno);
360
        memset (ira_loop_nodes[l].regno_allocno_map, 0,
361
                sizeof (ira_allocno_t) * max_regno);
362
      }
363
  ira_free (ira_regno_allocno_map);
364
  ira_regno_allocno_map
365
    = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
366
  memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
367
  FOR_EACH_ALLOCNO (a, ai)
368
    {
369
      if (ALLOCNO_CAP_MEMBER (a) != NULL)
370
        /* Caps are not in the regno allocno maps.  */
371
        continue;
372
      regno = ALLOCNO_REGNO (a);
373
      loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
374
      ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
375
      ira_regno_allocno_map[regno] = a;
376
      if (loop_tree_node->regno_allocno_map[regno] == NULL)
377
        /* Remember that we can create temporary allocnos to break
378
           cycles in register shuffle.  */
379
        loop_tree_node->regno_allocno_map[regno] = a;
380
    }
381
}
382
 
383
 
384
 
385
/* Pools for allocnos and allocno live ranges.  */
386
static alloc_pool allocno_pool, allocno_live_range_pool;
387
 
388
/* Vec containing references to all created allocnos.  It is a
389
   container of array allocnos.  */
390
static VEC(ira_allocno_t,heap) *allocno_vec;
391
 
392
/* Vec containing references to all created allocnos.  It is a
393
   container of ira_conflict_id_allocno_map.  */
394
static VEC(ira_allocno_t,heap) *ira_conflict_id_allocno_map_vec;
395
 
396
/* Initialize data concerning allocnos.  */
397
static void
398
initiate_allocnos (void)
399
{
400
  allocno_live_range_pool
401
    = create_alloc_pool ("allocno live ranges",
402
                         sizeof (struct ira_allocno_live_range), 100);
403
  allocno_pool
404
    = create_alloc_pool ("allocnos", sizeof (struct ira_allocno), 100);
405
  allocno_vec = VEC_alloc (ira_allocno_t, heap, max_reg_num () * 2);
406
  ira_allocnos = NULL;
407
  ira_allocnos_num = 0;
408
  ira_conflict_id_allocno_map_vec
409
    = VEC_alloc (ira_allocno_t, heap, max_reg_num () * 2);
410
  ira_conflict_id_allocno_map = NULL;
411
  ira_regno_allocno_map
412
    = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t));
413
  memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
414
}
415
 
416
/* Create and return the allocno corresponding to REGNO in
417
   LOOP_TREE_NODE.  Add the allocno to the list of allocnos with the
418
   same regno if CAP_P is FALSE.  */
419
ira_allocno_t
420
ira_create_allocno (int regno, bool cap_p, ira_loop_tree_node_t loop_tree_node)
421
{
422
  ira_allocno_t a;
423
 
424
  a = (ira_allocno_t) pool_alloc (allocno_pool);
425
  ALLOCNO_REGNO (a) = regno;
426
  ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
427
  if (! cap_p)
428
    {
429
      ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
430
      ira_regno_allocno_map[regno] = a;
431
      if (loop_tree_node->regno_allocno_map[regno] == NULL)
432
        /* Remember that we can create temporary allocnos to break
433
           cycles in register shuffle on region borders (see
434
           ira-emit.c).  */
435
        loop_tree_node->regno_allocno_map[regno] = a;
436
    }
437
  ALLOCNO_CAP (a) = NULL;
438
  ALLOCNO_CAP_MEMBER (a) = NULL;
439
  ALLOCNO_NUM (a) = ira_allocnos_num;
440
  bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
441
  ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = NULL;
442
  ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
443
  COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
444
  COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
445
  ALLOCNO_NREFS (a) = 0;
446
  ALLOCNO_FREQ (a) = 0;
447
  ALLOCNO_HARD_REGNO (a) = -1;
448
  ALLOCNO_CALL_FREQ (a) = 0;
449
  ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
450
#ifdef STACK_REGS
451
  ALLOCNO_NO_STACK_REG_P (a) = false;
452
  ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
453
#endif
454
  ALLOCNO_MEM_OPTIMIZED_DEST (a) = NULL;
455
  ALLOCNO_MEM_OPTIMIZED_DEST_P (a) = false;
456
  ALLOCNO_SOMEWHERE_RENAMED_P (a) = false;
457
  ALLOCNO_CHILD_RENAMED_P (a) = false;
458
  ALLOCNO_DONT_REASSIGN_P (a) = false;
459
  ALLOCNO_BAD_SPILL_P (a) = false;
460
  ALLOCNO_IN_GRAPH_P (a) = false;
461
  ALLOCNO_ASSIGNED_P (a) = false;
462
  ALLOCNO_MAY_BE_SPILLED_P (a) = false;
463
  ALLOCNO_SPLAY_REMOVED_P (a) = false;
464
  ALLOCNO_CONFLICT_VEC_P (a) = false;
465
  ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
466
  ALLOCNO_COPIES (a) = NULL;
467
  ALLOCNO_HARD_REG_COSTS (a) = NULL;
468
  ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
469
  ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
470
  ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
471
  ALLOCNO_LEFT_CONFLICTS_SIZE (a) = -1;
472
  ALLOCNO_COVER_CLASS (a) = NO_REGS;
473
  ALLOCNO_UPDATED_COVER_CLASS_COST (a) = 0;
474
  ALLOCNO_COVER_CLASS_COST (a) = 0;
475
  ALLOCNO_MEMORY_COST (a) = 0;
476
  ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
477
  ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
478
  ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = NULL;
479
  ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
480
  ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
481
  ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
482
  ALLOCNO_LIVE_RANGES (a) = NULL;
483
  ALLOCNO_MIN (a) = INT_MAX;
484
  ALLOCNO_MAX (a) = -1;
485
  ALLOCNO_CONFLICT_ID (a) = ira_allocnos_num;
486
  VEC_safe_push (ira_allocno_t, heap, allocno_vec, a);
487
  ira_allocnos = VEC_address (ira_allocno_t, allocno_vec);
488
  ira_allocnos_num = VEC_length (ira_allocno_t, allocno_vec);
489
  VEC_safe_push (ira_allocno_t, heap, ira_conflict_id_allocno_map_vec, a);
490
  ira_conflict_id_allocno_map
491
    = VEC_address (ira_allocno_t, ira_conflict_id_allocno_map_vec);
492
  return a;
493
}
494
 
495
/* Set up cover class for A and update its conflict hard registers.  */
496
void
497
ira_set_allocno_cover_class (ira_allocno_t a, enum reg_class cover_class)
498
{
499
  ALLOCNO_COVER_CLASS (a) = cover_class;
500
  IOR_COMPL_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
501
                          reg_class_contents[cover_class]);
502
  IOR_COMPL_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
503
                          reg_class_contents[cover_class]);
504
}
505
 
506
/* Return TRUE if the conflict vector with NUM elements is more
507
   profitable than conflict bit vector for A.  */
508
bool
509
ira_conflict_vector_profitable_p (ira_allocno_t a, int num)
510
{
511
  int nw;
512
 
513
  if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
514
    /* We prefer bit vector in such case because it does not result in
515
       allocation.  */
516
    return false;
517
 
518
  nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS) / IRA_INT_BITS;
519
  return (2 * sizeof (ira_allocno_t) * (num + 1)
520
          < 3 * nw * sizeof (IRA_INT_TYPE));
521
}
522
 
523
/* Allocates and initialize the conflict vector of A for NUM
524
   conflicting allocnos.  */
525
void
526
ira_allocate_allocno_conflict_vec (ira_allocno_t a, int num)
527
{
528
  int size;
529
  ira_allocno_t *vec;
530
 
531
  ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
532
  num++; /* for NULL end marker  */
533
  size = sizeof (ira_allocno_t) * num;
534
  ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
535
  vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
536
  vec[0] = NULL;
537
  ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
538
  ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
539
  ALLOCNO_CONFLICT_VEC_P (a) = true;
540
}
541
 
542
/* Allocate and initialize the conflict bit vector of A.  */
543
static void
544
allocate_allocno_conflict_bit_vec (ira_allocno_t a)
545
{
546
  unsigned int size;
547
 
548
  ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
549
  size = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
550
          / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
551
  ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
552
  memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0, size);
553
  ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
554
  ALLOCNO_CONFLICT_VEC_P (a) = false;
555
}
556
 
557
/* Allocate and initialize the conflict vector or conflict bit vector
558
   of A for NUM conflicting allocnos whatever is more profitable.  */
559
void
560
ira_allocate_allocno_conflicts (ira_allocno_t a, int num)
561
{
562
  if (ira_conflict_vector_profitable_p (a, num))
563
    ira_allocate_allocno_conflict_vec (a, num);
564
  else
565
    allocate_allocno_conflict_bit_vec (a);
566
}
567
 
568
/* Add A2 to the conflicts of A1.  */
569
static void
570
add_to_allocno_conflicts (ira_allocno_t a1, ira_allocno_t a2)
571
{
572
  int num;
573
  unsigned int size;
574
 
575
  if (ALLOCNO_CONFLICT_VEC_P (a1))
576
    {
577
      ira_allocno_t *vec;
578
 
579
      num = ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1) + 2;
580
      if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1)
581
          >=  num * sizeof (ira_allocno_t))
582
        vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
583
      else
584
        {
585
          size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
586
          vec = (ira_allocno_t *) ira_allocate (size);
587
          memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
588
                  sizeof (ira_allocno_t) * ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1));
589
          ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
590
          ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
591
          ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
592
        }
593
      vec[num - 2] = a2;
594
      vec[num - 1] = NULL;
595
      ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1)++;
596
    }
597
  else
598
    {
599
      int nw, added_head_nw, id;
600
      IRA_INT_TYPE *vec;
601
 
602
      id = ALLOCNO_CONFLICT_ID (a2);
603
      vec = (IRA_INT_TYPE *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
604
      if (ALLOCNO_MIN (a1) > id)
605
        {
606
          /* Expand head of the bit vector.  */
607
          added_head_nw = (ALLOCNO_MIN (a1) - id - 1) / IRA_INT_BITS + 1;
608
          nw = (ALLOCNO_MAX (a1) - ALLOCNO_MIN (a1)) / IRA_INT_BITS + 1;
609
          size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
610
          if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) >= size)
611
            {
612
              memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
613
                       vec, nw * sizeof (IRA_INT_TYPE));
614
              memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
615
            }
616
          else
617
            {
618
              size
619
                = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
620
              vec = (IRA_INT_TYPE *) ira_allocate (size);
621
              memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
622
                      ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
623
                      nw * sizeof (IRA_INT_TYPE));
624
              memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
625
              memset ((char *) vec
626
                      + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
627
                      0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
628
              ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
629
              ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
630
              ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
631
            }
632
          ALLOCNO_MIN (a1) -= added_head_nw * IRA_INT_BITS;
633
        }
634
      else if (ALLOCNO_MAX (a1) < id)
635
        {
636
          nw = (id - ALLOCNO_MIN (a1)) / IRA_INT_BITS + 1;
637
          size = nw * sizeof (IRA_INT_TYPE);
638
          if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) < size)
639
            {
640
              /* Expand tail of the bit vector.  */
641
              size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
642
              vec = (IRA_INT_TYPE *) ira_allocate (size);
643
              memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
644
                      ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
645
              memset ((char *) vec + ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1),
646
                      0, size - ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
647
              ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
648
              ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
649
              ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
650
            }
651
          ALLOCNO_MAX (a1) = id;
652
        }
653
      SET_ALLOCNO_SET_BIT (vec, id, ALLOCNO_MIN (a1), ALLOCNO_MAX (a1));
654
    }
655
}
656
 
657
/* Add A1 to the conflicts of A2 and vise versa.  */
658
void
659
ira_add_allocno_conflict (ira_allocno_t a1, ira_allocno_t a2)
660
{
661
  add_to_allocno_conflicts (a1, a2);
662
  add_to_allocno_conflicts (a2, a1);
663
}
664
 
665
/* Clear all conflicts of allocno A.  */
666
static void
667
clear_allocno_conflicts (ira_allocno_t a)
668
{
669
  if (ALLOCNO_CONFLICT_VEC_P (a))
670
    {
671
      ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
672
      ((ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a))[0] = NULL;
673
    }
674
  else if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) != 0)
675
    {
676
      int nw;
677
 
678
      nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a)) / IRA_INT_BITS + 1;
679
      memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0,
680
              nw * sizeof (IRA_INT_TYPE));
681
    }
682
}
683
 
684
/* The array used to find duplications in conflict vectors of
685
   allocnos.  */
686
static int *allocno_conflict_check;
687
 
688
/* The value used to mark allocation presence in conflict vector of
689
   the current allocno.  */
690
static int curr_allocno_conflict_check_tick;
691
 
692
/* Remove duplications in conflict vector of A.  */
693
static void
694
compress_allocno_conflict_vec (ira_allocno_t a)
695
{
696
  ira_allocno_t *vec, conflict_a;
697
  int i, j;
698
 
699
  ira_assert (ALLOCNO_CONFLICT_VEC_P (a));
700
  vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
701
  curr_allocno_conflict_check_tick++;
702
  for (i = j = 0; (conflict_a = vec[i]) != NULL; i++)
703
    {
704
      if (allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
705
          != curr_allocno_conflict_check_tick)
706
        {
707
          allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
708
            = curr_allocno_conflict_check_tick;
709
          vec[j++] = conflict_a;
710
        }
711
    }
712
  ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = j;
713
  vec[j] = NULL;
714
}
715
 
716
/* Remove duplications in conflict vectors of all allocnos.  */
717
static void
718
compress_conflict_vecs (void)
719
{
720
  ira_allocno_t a;
721
  ira_allocno_iterator ai;
722
 
723
  allocno_conflict_check
724
    = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
725
  memset (allocno_conflict_check, 0, sizeof (int) * ira_allocnos_num);
726
  curr_allocno_conflict_check_tick = 0;
727
  FOR_EACH_ALLOCNO (a, ai)
728
    if (ALLOCNO_CONFLICT_VEC_P (a))
729
      compress_allocno_conflict_vec (a);
730
  ira_free (allocno_conflict_check);
731
}
732
 
733
/* This recursive function outputs allocno A and if it is a cap the
734
   function outputs its members.  */
735
void
736
ira_print_expanded_allocno (ira_allocno_t a)
737
{
738
  basic_block bb;
739
 
740
  fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
741
  if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
742
    fprintf (ira_dump_file, ",b%d", bb->index);
743
  else
744
    fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
745
  if (ALLOCNO_CAP_MEMBER (a) != NULL)
746
    {
747
      fprintf (ira_dump_file, ":");
748
      ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
749
    }
750
  fprintf (ira_dump_file, ")");
751
}
752
 
753
/* Create and return the cap representing allocno A in the
754
   parent loop.  */
755
static ira_allocno_t
756
create_cap_allocno (ira_allocno_t a)
757
{
758
  ira_allocno_t cap;
759
  ira_loop_tree_node_t parent;
760
  enum reg_class cover_class;
761
 
762
  ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
763
              && ALLOCNO_NEXT_COALESCED_ALLOCNO (a) == a);
764
  parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
765
  cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
766
  ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
767
  cover_class = ALLOCNO_COVER_CLASS (a);
768
  ira_set_allocno_cover_class (cap, cover_class);
769
  ALLOCNO_AVAILABLE_REGS_NUM (cap) = ALLOCNO_AVAILABLE_REGS_NUM (a);
770
  ALLOCNO_CAP_MEMBER (cap) = a;
771
  ALLOCNO_CAP (a) = cap;
772
  ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a);
773
  ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
774
  ira_allocate_and_copy_costs
775
    (&ALLOCNO_HARD_REG_COSTS (cap), cover_class, ALLOCNO_HARD_REG_COSTS (a));
776
  ira_allocate_and_copy_costs
777
    (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), cover_class,
778
     ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
779
  ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
780
  ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
781
  ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
782
  ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
783
  IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (cap),
784
                    ALLOCNO_CONFLICT_HARD_REGS (a));
785
  IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (cap),
786
                    ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
787
  ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
788
#ifdef STACK_REGS
789
  ALLOCNO_NO_STACK_REG_P (cap) = ALLOCNO_NO_STACK_REG_P (a);
790
  ALLOCNO_TOTAL_NO_STACK_REG_P (cap) = ALLOCNO_TOTAL_NO_STACK_REG_P (a);
791
#endif
792
  if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
793
    {
794
      fprintf (ira_dump_file, "    Creating cap ");
795
      ira_print_expanded_allocno (cap);
796
      fprintf (ira_dump_file, "\n");
797
    }
798
  return cap;
799
}
800
 
801
/* Create and return allocno live range with given attributes.  */
802
allocno_live_range_t
803
ira_create_allocno_live_range (ira_allocno_t a, int start, int finish,
804
                               allocno_live_range_t next)
805
{
806
  allocno_live_range_t p;
807
 
808
  p = (allocno_live_range_t) pool_alloc (allocno_live_range_pool);
809
  p->allocno = a;
810
  p->start = start;
811
  p->finish = finish;
812
  p->next = next;
813
  return p;
814
}
815
 
816
/* Copy allocno live range R and return the result.  */
817
static allocno_live_range_t
818
copy_allocno_live_range (allocno_live_range_t r)
819
{
820
  allocno_live_range_t p;
821
 
822
  p = (allocno_live_range_t) pool_alloc (allocno_live_range_pool);
823
  *p = *r;
824
  return p;
825
}
826
 
827
/* Copy allocno live range list given by its head R and return the
828
   result.  */
829
allocno_live_range_t
830
ira_copy_allocno_live_range_list (allocno_live_range_t r)
831
{
832
  allocno_live_range_t p, first, last;
833
 
834
  if (r == NULL)
835
    return NULL;
836
  for (first = last = NULL; r != NULL; r = r->next)
837
    {
838
      p = copy_allocno_live_range (r);
839
      if (first == NULL)
840
        first = p;
841
      else
842
        last->next = p;
843
      last = p;
844
    }
845
  return first;
846
}
847
 
848
/* Merge ranges R1 and R2 and returns the result.  The function
849
   maintains the order of ranges and tries to minimize number of the
850
   result ranges.  */
851
allocno_live_range_t
852
ira_merge_allocno_live_ranges (allocno_live_range_t r1,
853
                               allocno_live_range_t r2)
854
{
855
  allocno_live_range_t first, last, temp;
856
 
857
  if (r1 == NULL)
858
    return r2;
859
  if (r2 == NULL)
860
    return r1;
861
  for (first = last = NULL; r1 != NULL && r2 != NULL;)
862
    {
863
      if (r1->start < r2->start)
864
        {
865
          temp = r1;
866
          r1 = r2;
867
          r2 = temp;
868
        }
869
      if (r1->start <= r2->finish + 1)
870
        {
871
          /* Intersected ranges: merge r1 and r2 into r1.  */
872
          r1->start = r2->start;
873
          if (r1->finish < r2->finish)
874
            r1->finish = r2->finish;
875
          temp = r2;
876
          r2 = r2->next;
877
          ira_finish_allocno_live_range (temp);
878
          if (r2 == NULL)
879
            {
880
              /* To try to merge with subsequent ranges in r1.  */
881
              r2 = r1->next;
882
              r1->next = NULL;
883
            }
884
        }
885
      else
886
        {
887
          /* Add r1 to the result.  */
888
          if (first == NULL)
889
            first = last = r1;
890
          else
891
            {
892
              last->next = r1;
893
              last = r1;
894
            }
895
          r1 = r1->next;
896
          if (r1 == NULL)
897
            {
898
              /* To try to merge with subsequent ranges in r2.  */
899
              r1 = r2->next;
900
              r2->next = NULL;
901
            }
902
        }
903
    }
904
  if (r1 != NULL)
905
    {
906
      if (first == NULL)
907
        first = r1;
908
      else
909
        last->next = r1;
910
      ira_assert (r1->next == NULL);
911
    }
912
  else if (r2 != NULL)
913
    {
914
      if (first == NULL)
915
        first = r2;
916
      else
917
        last->next = r2;
918
      ira_assert (r2->next == NULL);
919
    }
920
  else
921
    {
922
      ira_assert (last->next == NULL);
923
    }
924
  return first;
925
}
926
 
927
/* Return TRUE if live ranges R1 and R2 intersect.  */
928
bool
929
ira_allocno_live_ranges_intersect_p (allocno_live_range_t r1,
930
                                     allocno_live_range_t r2)
931
{
932
  /* Remember the live ranges are always kept ordered.  */
933
  while (r1 != NULL && r2 != NULL)
934
    {
935
      if (r1->start > r2->finish)
936
        r1 = r1->next;
937
      else if (r2->start > r1->finish)
938
        r2 = r2->next;
939
      else
940
        return true;
941
    }
942
  return false;
943
}
944
 
945
/* Free allocno live range R.  */
946
void
947
ira_finish_allocno_live_range (allocno_live_range_t r)
948
{
949
  pool_free (allocno_live_range_pool, r);
950
}
951
 
952
/* Free list of allocno live ranges starting with R.  */
953
void
954
ira_finish_allocno_live_range_list (allocno_live_range_t r)
955
{
956
  allocno_live_range_t next_r;
957
 
958
  for (; r != NULL; r = next_r)
959
    {
960
      next_r = r->next;
961
      ira_finish_allocno_live_range (r);
962
    }
963
}
964
 
965
/* Free updated register costs of allocno A.  */
966
void
967
ira_free_allocno_updated_costs (ira_allocno_t a)
968
{
969
  enum reg_class cover_class;
970
 
971
  cover_class = ALLOCNO_COVER_CLASS (a);
972
  if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
973
    ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class);
974
  ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
975
  if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
976
    ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
977
                          cover_class);
978
  ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
979
}
980
 
981
/* Free the memory allocated for allocno A.  */
982
static void
983
finish_allocno (ira_allocno_t a)
984
{
985
  enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
986
 
987
  ira_allocnos[ALLOCNO_NUM (a)] = NULL;
988
  ira_conflict_id_allocno_map[ALLOCNO_CONFLICT_ID (a)] = NULL;
989
  if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
990
    ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a));
991
  if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
992
    ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), cover_class);
993
  if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
994
    ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class);
995
  if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
996
    ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class);
997
  if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
998
    ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
999
                          cover_class);
1000
  ira_finish_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
1001
  pool_free (allocno_pool, a);
1002
}
1003
 
1004
/* Free the memory allocated for all allocnos.  */
1005
static void
1006
finish_allocnos (void)
1007
{
1008
  ira_allocno_t a;
1009
  ira_allocno_iterator ai;
1010
 
1011
  FOR_EACH_ALLOCNO (a, ai)
1012
    finish_allocno (a);
1013
  ira_free (ira_regno_allocno_map);
1014
  VEC_free (ira_allocno_t, heap, ira_conflict_id_allocno_map_vec);
1015
  VEC_free (ira_allocno_t, heap, allocno_vec);
1016
  free_alloc_pool (allocno_pool);
1017
  free_alloc_pool (allocno_live_range_pool);
1018
}
1019
 
1020
 
1021
 
1022
/* Pools for copies.  */
1023
static alloc_pool copy_pool;
1024
 
1025
/* Vec containing references to all created copies.  It is a
1026
   container of array ira_copies.  */
1027
static VEC(ira_copy_t,heap) *copy_vec;
1028
 
1029
/* The function initializes data concerning allocno copies.  */
1030
static void
1031
initiate_copies (void)
1032
{
1033
  copy_pool
1034
    = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy), 100);
1035
  copy_vec = VEC_alloc (ira_copy_t, heap, get_max_uid ());
1036
  ira_copies = NULL;
1037
  ira_copies_num = 0;
1038
}
1039
 
1040
/* Return copy connecting A1 and A2 and originated from INSN of
1041
   LOOP_TREE_NODE if any.  */
1042
static ira_copy_t
1043
find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx insn,
1044
                   ira_loop_tree_node_t loop_tree_node)
1045
{
1046
  ira_copy_t cp, next_cp;
1047
  ira_allocno_t another_a;
1048
 
1049
  for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1050
    {
1051
      if (cp->first == a1)
1052
        {
1053
          next_cp = cp->next_first_allocno_copy;
1054
          another_a = cp->second;
1055
        }
1056
      else if (cp->second == a1)
1057
        {
1058
          next_cp = cp->next_second_allocno_copy;
1059
          another_a = cp->first;
1060
        }
1061
      else
1062
        gcc_unreachable ();
1063
      if (another_a == a2 && cp->insn == insn
1064
          && cp->loop_tree_node == loop_tree_node)
1065
        return cp;
1066
    }
1067
  return NULL;
1068
}
1069
 
1070
/* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1071
   SECOND, FREQ, CONSTRAINT_P, and INSN.  */
1072
ira_copy_t
1073
ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1074
                 bool constraint_p, rtx insn,
1075
                 ira_loop_tree_node_t loop_tree_node)
1076
{
1077
  ira_copy_t cp;
1078
 
1079
  cp = (ira_copy_t) pool_alloc (copy_pool);
1080
  cp->num = ira_copies_num;
1081
  cp->first = first;
1082
  cp->second = second;
1083
  cp->freq = freq;
1084
  cp->constraint_p = constraint_p;
1085
  cp->insn = insn;
1086
  cp->loop_tree_node = loop_tree_node;
1087
  VEC_safe_push (ira_copy_t, heap, copy_vec, cp);
1088
  ira_copies = VEC_address (ira_copy_t, copy_vec);
1089
  ira_copies_num = VEC_length (ira_copy_t, copy_vec);
1090
  return cp;
1091
}
1092
 
1093
/* Attach a copy CP to allocnos involved into the copy.  */
1094
void
1095
ira_add_allocno_copy_to_list (ira_copy_t cp)
1096
{
1097
  ira_allocno_t first = cp->first, second = cp->second;
1098
 
1099
  cp->prev_first_allocno_copy = NULL;
1100
  cp->prev_second_allocno_copy = NULL;
1101
  cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1102
  if (cp->next_first_allocno_copy != NULL)
1103
    {
1104
      if (cp->next_first_allocno_copy->first == first)
1105
        cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1106
      else
1107
        cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1108
    }
1109
  cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1110
  if (cp->next_second_allocno_copy != NULL)
1111
    {
1112
      if (cp->next_second_allocno_copy->second == second)
1113
        cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1114
      else
1115
        cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1116
    }
1117
  ALLOCNO_COPIES (first) = cp;
1118
  ALLOCNO_COPIES (second) = cp;
1119
}
1120
 
1121
/* Detach a copy CP from allocnos involved into the copy.  */
1122
void
1123
ira_remove_allocno_copy_from_list (ira_copy_t cp)
1124
{
1125
  ira_allocno_t first = cp->first, second = cp->second;
1126
  ira_copy_t prev, next;
1127
 
1128
  next = cp->next_first_allocno_copy;
1129
  prev = cp->prev_first_allocno_copy;
1130
  if (prev == NULL)
1131
    ALLOCNO_COPIES (first) = next;
1132
  else if (prev->first == first)
1133
    prev->next_first_allocno_copy = next;
1134
  else
1135
    prev->next_second_allocno_copy = next;
1136
  if (next != NULL)
1137
    {
1138
      if (next->first == first)
1139
        next->prev_first_allocno_copy = prev;
1140
      else
1141
        next->prev_second_allocno_copy = prev;
1142
    }
1143
  cp->prev_first_allocno_copy = cp->next_first_allocno_copy = NULL;
1144
 
1145
  next = cp->next_second_allocno_copy;
1146
  prev = cp->prev_second_allocno_copy;
1147
  if (prev == NULL)
1148
    ALLOCNO_COPIES (second) = next;
1149
  else if (prev->second == second)
1150
    prev->next_second_allocno_copy = next;
1151
  else
1152
    prev->next_first_allocno_copy = next;
1153
  if (next != NULL)
1154
    {
1155
      if (next->second == second)
1156
        next->prev_second_allocno_copy = prev;
1157
      else
1158
        next->prev_first_allocno_copy = prev;
1159
    }
1160
  cp->prev_second_allocno_copy = cp->next_second_allocno_copy = NULL;
1161
}
1162
 
1163
/* Make a copy CP a canonical copy where number of the
1164
   first allocno is less than the second one.  */
1165
void
1166
ira_swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1167
{
1168
  ira_allocno_t temp;
1169
  ira_copy_t temp_cp;
1170
 
1171
  if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1172
    return;
1173
 
1174
  temp = cp->first;
1175
  cp->first = cp->second;
1176
  cp->second = temp;
1177
 
1178
  temp_cp = cp->prev_first_allocno_copy;
1179
  cp->prev_first_allocno_copy = cp->prev_second_allocno_copy;
1180
  cp->prev_second_allocno_copy = temp_cp;
1181
 
1182
  temp_cp = cp->next_first_allocno_copy;
1183
  cp->next_first_allocno_copy = cp->next_second_allocno_copy;
1184
  cp->next_second_allocno_copy = temp_cp;
1185
}
1186
 
1187
/* Create (or update frequency if the copy already exists) and return
1188
   the copy of allocnos FIRST and SECOND with frequency FREQ
1189
   corresponding to move insn INSN (if any) and originated from
1190
   LOOP_TREE_NODE.  */
1191
ira_copy_t
1192
ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1193
                      bool constraint_p, rtx insn,
1194
                      ira_loop_tree_node_t loop_tree_node)
1195
{
1196
  ira_copy_t cp;
1197
 
1198
  if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1199
    {
1200
      cp->freq += freq;
1201
      return cp;
1202
    }
1203
  cp = ira_create_copy (first, second, freq, constraint_p, insn,
1204
                        loop_tree_node);
1205
  ira_assert (first != NULL && second != NULL);
1206
  ira_add_allocno_copy_to_list (cp);
1207
  ira_swap_allocno_copy_ends_if_necessary (cp);
1208
  return cp;
1209
}
1210
 
1211
/* Print info about copy CP into file F.  */
1212
static void
1213
print_copy (FILE *f, ira_copy_t cp)
1214
{
1215
  fprintf (f, "  cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1216
           ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1217
           ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1218
           cp->insn != NULL
1219
           ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1220
}
1221
 
1222
/* Print info about copy CP into stderr.  */
1223
void
1224
ira_debug_copy (ira_copy_t cp)
1225
{
1226
  print_copy (stderr, cp);
1227
}
1228
 
1229
/* Print info about all copies into file F.  */
1230
static void
1231
print_copies (FILE *f)
1232
{
1233
  ira_copy_t cp;
1234
  ira_copy_iterator ci;
1235
 
1236
  FOR_EACH_COPY (cp, ci)
1237
    print_copy (f, cp);
1238
}
1239
 
1240
/* Print info about all copies into stderr.  */
1241
void
1242
ira_debug_copies (void)
1243
{
1244
  print_copies (stderr);
1245
}
1246
 
1247
/* Print info about copies involving allocno A into file F.  */
1248
static void
1249
print_allocno_copies (FILE *f, ira_allocno_t a)
1250
{
1251
  ira_allocno_t another_a;
1252
  ira_copy_t cp, next_cp;
1253
 
1254
  fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1255
  for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1256
    {
1257
      if (cp->first == a)
1258
        {
1259
          next_cp = cp->next_first_allocno_copy;
1260
          another_a = cp->second;
1261
        }
1262
      else if (cp->second == a)
1263
        {
1264
          next_cp = cp->next_second_allocno_copy;
1265
          another_a = cp->first;
1266
        }
1267
      else
1268
        gcc_unreachable ();
1269
      fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1270
               ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1271
    }
1272
  fprintf (f, "\n");
1273
}
1274
 
1275
/* Print info about copies involving allocno A into stderr.  */
1276
void
1277
ira_debug_allocno_copies (ira_allocno_t a)
1278
{
1279
  print_allocno_copies (stderr, a);
1280
}
1281
 
1282
/* The function frees memory allocated for copy CP.  */
1283
static void
1284
finish_copy (ira_copy_t cp)
1285
{
1286
  pool_free (copy_pool, cp);
1287
}
1288
 
1289
 
1290
/* Free memory allocated for all copies.  */
1291
static void
1292
finish_copies (void)
1293
{
1294
  ira_copy_t cp;
1295
  ira_copy_iterator ci;
1296
 
1297
  FOR_EACH_COPY (cp, ci)
1298
    finish_copy (cp);
1299
  VEC_free (ira_copy_t, heap, copy_vec);
1300
  free_alloc_pool (copy_pool);
1301
}
1302
 
1303
 
1304
 
1305
/* Pools for cost vectors.  It is defined only for cover classes.  */
1306
static alloc_pool cost_vector_pool[N_REG_CLASSES];
1307
 
1308
/* The function initiates work with hard register cost vectors.  It
1309
   creates allocation pool for each cover class.  */
1310
static void
1311
initiate_cost_vectors (void)
1312
{
1313
  int i;
1314
  enum reg_class cover_class;
1315
 
1316
  for (i = 0; i < ira_reg_class_cover_size; i++)
1317
    {
1318
      cover_class = ira_reg_class_cover[i];
1319
      cost_vector_pool[cover_class]
1320
        = create_alloc_pool ("cost vectors",
1321
                             sizeof (int)
1322
                             * ira_class_hard_regs_num[cover_class],
1323
                             100);
1324
    }
1325
}
1326
 
1327
/* Allocate and return a cost vector VEC for COVER_CLASS.  */
1328
int *
1329
ira_allocate_cost_vector (enum reg_class cover_class)
1330
{
1331
  return (int *) pool_alloc (cost_vector_pool[cover_class]);
1332
}
1333
 
1334
/* Free a cost vector VEC for COVER_CLASS.  */
1335
void
1336
ira_free_cost_vector (int *vec, enum reg_class cover_class)
1337
{
1338
  ira_assert (vec != NULL);
1339
  pool_free (cost_vector_pool[cover_class], vec);
1340
}
1341
 
1342
/* Finish work with hard register cost vectors.  Release allocation
1343
   pool for each cover class.  */
1344
static void
1345
finish_cost_vectors (void)
1346
{
1347
  int i;
1348
  enum reg_class cover_class;
1349
 
1350
  for (i = 0; i < ira_reg_class_cover_size; i++)
1351
    {
1352
      cover_class = ira_reg_class_cover[i];
1353
      free_alloc_pool (cost_vector_pool[cover_class]);
1354
    }
1355
}
1356
 
1357
 
1358
 
1359
/* The current loop tree node and its regno allocno map.  */
1360
ira_loop_tree_node_t ira_curr_loop_tree_node;
1361
ira_allocno_t *ira_curr_regno_allocno_map;
1362
 
1363
/* This recursive function traverses loop tree with root LOOP_NODE
1364
   calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1365
   correspondingly in preorder and postorder.  The function sets up
1366
   IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP.  If BB_P,
1367
   basic block nodes of LOOP_NODE is also processed (before its
1368
   subloop nodes).  */
1369
void
1370
ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1371
                        void (*preorder_func) (ira_loop_tree_node_t),
1372
                        void (*postorder_func) (ira_loop_tree_node_t))
1373
{
1374
  ira_loop_tree_node_t subloop_node;
1375
 
1376
  ira_assert (loop_node->bb == NULL);
1377
  ira_curr_loop_tree_node = loop_node;
1378
  ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1379
 
1380
  if (preorder_func != NULL)
1381
    (*preorder_func) (loop_node);
1382
 
1383
  if (bb_p)
1384
    for (subloop_node = loop_node->children;
1385
         subloop_node != NULL;
1386
         subloop_node = subloop_node->next)
1387
      if (subloop_node->bb != NULL)
1388
        {
1389
          if (preorder_func != NULL)
1390
            (*preorder_func) (subloop_node);
1391
 
1392
          if (postorder_func != NULL)
1393
            (*postorder_func) (subloop_node);
1394
        }
1395
 
1396
  for (subloop_node = loop_node->subloops;
1397
       subloop_node != NULL;
1398
       subloop_node = subloop_node->subloop_next)
1399
    {
1400
      ira_assert (subloop_node->bb == NULL);
1401
      ira_traverse_loop_tree (bb_p, subloop_node,
1402
                              preorder_func, postorder_func);
1403
    }
1404
 
1405
  ira_curr_loop_tree_node = loop_node;
1406
  ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1407
 
1408
  if (postorder_func != NULL)
1409
    (*postorder_func) (loop_node);
1410
}
1411
 
1412
 
1413
 
1414
/* The basic block currently being processed.  */
1415
static basic_block curr_bb;
1416
 
1417
/* This recursive function creates allocnos corresponding to
1418
   pseudo-registers containing in X.  True OUTPUT_P means that X is
1419
   a lvalue.  */
1420
static void
1421
create_insn_allocnos (rtx x, bool output_p)
1422
{
1423
  int i, j;
1424
  const char *fmt;
1425
  enum rtx_code code = GET_CODE (x);
1426
 
1427
  if (code == REG)
1428
    {
1429
      int regno;
1430
 
1431
      if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1432
        {
1433
          ira_allocno_t a;
1434
 
1435
          if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1436
            a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1437
 
1438
          ALLOCNO_NREFS (a)++;
1439
          ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1440
          if (output_p)
1441
            bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1442
        }
1443
      return;
1444
    }
1445
  else if (code == SET)
1446
    {
1447
      create_insn_allocnos (SET_DEST (x), true);
1448
      create_insn_allocnos (SET_SRC (x), false);
1449
      return;
1450
    }
1451
  else if (code == CLOBBER)
1452
    {
1453
      create_insn_allocnos (XEXP (x, 0), true);
1454
      return;
1455
    }
1456
  else if (code == MEM)
1457
    {
1458
      create_insn_allocnos (XEXP (x, 0), false);
1459
      return;
1460
    }
1461
  else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1462
           code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1463
    {
1464
      create_insn_allocnos (XEXP (x, 0), true);
1465
      create_insn_allocnos (XEXP (x, 0), false);
1466
      return;
1467
    }
1468
 
1469
  fmt = GET_RTX_FORMAT (code);
1470
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1471
    {
1472
      if (fmt[i] == 'e')
1473
        create_insn_allocnos (XEXP (x, i), output_p);
1474
      else if (fmt[i] == 'E')
1475
        for (j = 0; j < XVECLEN (x, i); j++)
1476
          create_insn_allocnos (XVECEXP (x, i, j), output_p);
1477
    }
1478
}
1479
 
1480
/* Create allocnos corresponding to pseudo-registers living in the
1481
   basic block represented by the corresponding loop tree node
1482
   BB_NODE.  */
1483
static void
1484
create_bb_allocnos (ira_loop_tree_node_t bb_node)
1485
{
1486
  basic_block bb;
1487
  rtx insn;
1488
  unsigned int i;
1489
  bitmap_iterator bi;
1490
 
1491
  curr_bb = bb = bb_node->bb;
1492
  ira_assert (bb != NULL);
1493
  FOR_BB_INSNS_REVERSE (bb, insn)
1494
    if (NONDEBUG_INSN_P (insn))
1495
      create_insn_allocnos (PATTERN (insn), false);
1496
  /* It might be a allocno living through from one subloop to
1497
     another.  */
1498
  EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb), FIRST_PSEUDO_REGISTER, i, bi)
1499
    if (ira_curr_regno_allocno_map[i] == NULL)
1500
      ira_create_allocno (i, false, ira_curr_loop_tree_node);
1501
}
1502
 
1503
/* Create allocnos corresponding to pseudo-registers living on edge E
1504
   (a loop entry or exit).  Also mark the allocnos as living on the
1505
   loop border. */
1506
static void
1507
create_loop_allocnos (edge e)
1508
{
1509
  unsigned int i;
1510
  bitmap live_in_regs, border_allocnos;
1511
  bitmap_iterator bi;
1512
  ira_loop_tree_node_t parent;
1513
 
1514
  live_in_regs = DF_LR_IN (e->dest);
1515
  border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1516
  EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e->src),
1517
                             FIRST_PSEUDO_REGISTER, i, bi)
1518
    if (bitmap_bit_p (live_in_regs, i))
1519
      {
1520
        if (ira_curr_regno_allocno_map[i] == NULL)
1521
          {
1522
            /* The order of creations is important for right
1523
               ira_regno_allocno_map.  */
1524
            if ((parent = ira_curr_loop_tree_node->parent) != NULL
1525
                && parent->regno_allocno_map[i] == NULL)
1526
              ira_create_allocno (i, false, parent);
1527
            ira_create_allocno (i, false, ira_curr_loop_tree_node);
1528
          }
1529
        bitmap_set_bit (border_allocnos,
1530
                        ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1531
      }
1532
}
1533
 
1534
/* Create allocnos corresponding to pseudo-registers living in loop
1535
   represented by the corresponding loop tree node LOOP_NODE.  This
1536
   function is called by ira_traverse_loop_tree.  */
1537
static void
1538
create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1539
{
1540
  if (loop_node->bb != NULL)
1541
    create_bb_allocnos (loop_node);
1542
  else if (loop_node != ira_loop_tree_root)
1543
    {
1544
      int i;
1545
      edge_iterator ei;
1546
      edge e;
1547
      VEC (edge, heap) *edges;
1548
 
1549
      FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1550
        if (e->src != loop_node->loop->latch)
1551
          create_loop_allocnos (e);
1552
 
1553
      edges = get_loop_exit_edges (loop_node->loop);
1554
      for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1555
        create_loop_allocnos (e);
1556
      VEC_free (edge, heap, edges);
1557
    }
1558
}
1559
 
1560
/* Propagate information about allocnos modified inside the loop given
1561
   by its LOOP_TREE_NODE to its parent.  */
1562
static void
1563
propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1564
{
1565
  if (loop_tree_node == ira_loop_tree_root)
1566
    return;
1567
  ira_assert (loop_tree_node->bb == NULL);
1568
  bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1569
                   loop_tree_node->modified_regnos);
1570
}
1571
 
1572
/* Propagate new info about allocno A (see comments about accumulated
1573
   info in allocno definition) to the corresponding allocno on upper
1574
   loop tree level.  So allocnos on upper levels accumulate
1575
   information about the corresponding allocnos in nested regions.
1576
   The new info means allocno info finally calculated in this
1577
   file.  */
1578
static void
1579
propagate_allocno_info (void)
1580
{
1581
  int i;
1582
  ira_allocno_t a, parent_a;
1583
  ira_loop_tree_node_t parent;
1584
  enum reg_class cover_class;
1585
 
1586
  if (flag_ira_region != IRA_REGION_ALL
1587
      && flag_ira_region != IRA_REGION_MIXED)
1588
    return;
1589
  for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1590
    for (a = ira_regno_allocno_map[i];
1591
         a != NULL;
1592
         a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1593
      if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1594
          && (parent_a = parent->regno_allocno_map[i]) != NULL
1595
          /* There are no caps yet at this point.  So use
1596
             border_allocnos to find allocnos for the propagation.  */
1597
          && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
1598
                           ALLOCNO_NUM (a)))
1599
        {
1600
          if (! ALLOCNO_BAD_SPILL_P (a))
1601
            ALLOCNO_BAD_SPILL_P (parent_a) = false;
1602
          ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
1603
          ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1604
          ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
1605
#ifdef STACK_REGS
1606
          if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
1607
            ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
1608
#endif
1609
          IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
1610
                            ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1611
          ALLOCNO_CALLS_CROSSED_NUM (parent_a)
1612
            += ALLOCNO_CALLS_CROSSED_NUM (a);
1613
          ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
1614
            += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1615
          cover_class = ALLOCNO_COVER_CLASS (a);
1616
          ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
1617
          ira_allocate_and_accumulate_costs
1618
            (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
1619
             ALLOCNO_HARD_REG_COSTS (a));
1620
          ira_allocate_and_accumulate_costs
1621
            (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
1622
             cover_class,
1623
             ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1624
          ALLOCNO_COVER_CLASS_COST (parent_a)
1625
            += ALLOCNO_COVER_CLASS_COST (a);
1626
          ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
1627
        }
1628
}
1629
 
1630
/* Create allocnos corresponding to pseudo-registers in the current
1631
   function.  Traverse the loop tree for this.  */
1632
static void
1633
create_allocnos (void)
1634
{
1635
  /* We need to process BB first to correctly link allocnos by member
1636
     next_regno_allocno.  */
1637
  ira_traverse_loop_tree (true, ira_loop_tree_root,
1638
                          create_loop_tree_node_allocnos, NULL);
1639
  if (optimize)
1640
    ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
1641
                            propagate_modified_regnos);
1642
}
1643
 
1644
 
1645
 
1646
/* The page contains function to remove some regions from a separate
1647
   register allocation.  We remove regions whose separate allocation
1648
   will hardly improve the result.  As a result we speed up regional
1649
   register allocation.  */
1650
 
1651
/* The function changes allocno in range list given by R onto A.  */
1652
static void
1653
change_allocno_in_range_list (allocno_live_range_t r, ira_allocno_t a)
1654
{
1655
  for (; r != NULL; r = r->next)
1656
    r->allocno = a;
1657
}
1658
 
1659
/* Return TRUE if NODE represents a loop with low register
1660
   pressure.  */
1661
static bool
1662
low_pressure_loop_node_p (ira_loop_tree_node_t node)
1663
{
1664
  int i;
1665
  enum reg_class cover_class;
1666
 
1667
  if (node->bb != NULL)
1668
    return false;
1669
 
1670
  for (i = 0; i < ira_reg_class_cover_size; i++)
1671
    {
1672
      cover_class = ira_reg_class_cover[i];
1673
      if (node->reg_pressure[cover_class]
1674
          > ira_available_class_regs[cover_class])
1675
        return false;
1676
    }
1677
  return true;
1678
}
1679
 
1680
/* Sort loops for marking them for removal.  We put already marked
1681
   loops first, then less frequent loops next, and then outer loops
1682
   next.  */
1683
static int
1684
loop_compare_func (const void *v1p, const void *v2p)
1685
{
1686
  int diff;
1687
  ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
1688
  ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
1689
 
1690
  ira_assert (l1->parent != NULL && l2->parent != NULL);
1691
  if (l1->to_remove_p && ! l2->to_remove_p)
1692
    return -1;
1693
  if (! l1->to_remove_p && l2->to_remove_p)
1694
    return 1;
1695
  if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
1696
    return diff;
1697
  if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
1698
    return diff;
1699
  /* Make sorting stable.  */
1700
  return l1->loop->num - l2->loop->num;
1701
}
1702
 
1703
 
1704
/* Mark loops which should be removed from regional allocation.  We
1705
   remove a loop with low register pressure inside another loop with
1706
   register pressure.  In this case a separate allocation of the loop
1707
   hardly helps (for irregular register file architecture it could
1708
   help by choosing a better hard register in the loop but we prefer
1709
   faster allocation even in this case).  We also remove cheap loops
1710
   if there are more than IRA_MAX_LOOPS_NUM of them.  */
1711
static void
1712
mark_loops_for_removal (void)
1713
{
1714
  int i, n;
1715
  ira_loop_tree_node_t *sorted_loops;
1716
  loop_p loop;
1717
 
1718
  sorted_loops
1719
    = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
1720
                                             * VEC_length (loop_p,
1721
                                                           ira_loops.larray));
1722
  for (n = i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
1723
    if (ira_loop_nodes[i].regno_allocno_map != NULL)
1724
      {
1725
        if (ira_loop_nodes[i].parent == NULL)
1726
          {
1727
            /* Don't remove the root.  */
1728
            ira_loop_nodes[i].to_remove_p = false;
1729
            continue;
1730
          }
1731
        sorted_loops[n++] = &ira_loop_nodes[i];
1732
        ira_loop_nodes[i].to_remove_p
1733
          = (low_pressure_loop_node_p (ira_loop_nodes[i].parent)
1734
             && low_pressure_loop_node_p (&ira_loop_nodes[i]));
1735
      }
1736
  qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
1737
  for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++)
1738
    {
1739
      sorted_loops[i]->to_remove_p = true;
1740
      if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1741
        fprintf
1742
          (ira_dump_file,
1743
           "  Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
1744
           sorted_loops[i]->loop->num, sorted_loops[i]->loop->header->index,
1745
           sorted_loops[i]->loop->header->frequency,
1746
           loop_depth (sorted_loops[i]->loop),
1747
           low_pressure_loop_node_p (sorted_loops[i]->parent)
1748
           && low_pressure_loop_node_p (sorted_loops[i])
1749
           ? "low pressure" : "cheap loop");
1750
    }
1751
  ira_free (sorted_loops);
1752
}
1753
 
1754
/* Mark all loops but root for removing.  */
1755
static void
1756
mark_all_loops_for_removal (void)
1757
{
1758
  int i;
1759
  loop_p loop;
1760
 
1761
  for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
1762
    if (ira_loop_nodes[i].regno_allocno_map != NULL)
1763
      {
1764
        if (ira_loop_nodes[i].parent == NULL)
1765
          {
1766
            /* Don't remove the root.  */
1767
            ira_loop_nodes[i].to_remove_p = false;
1768
            continue;
1769
          }
1770
        ira_loop_nodes[i].to_remove_p = true;
1771
        if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1772
          fprintf
1773
            (ira_dump_file,
1774
             "  Mark loop %d (header %d, freq %d, depth %d) for removal\n",
1775
             ira_loop_nodes[i].loop->num,
1776
             ira_loop_nodes[i].loop->header->index,
1777
             ira_loop_nodes[i].loop->header->frequency,
1778
             loop_depth (ira_loop_nodes[i].loop));
1779
      }
1780
}
1781
 
1782
/* Definition of vector of loop tree nodes.  */
1783
DEF_VEC_P(ira_loop_tree_node_t);
1784
DEF_VEC_ALLOC_P(ira_loop_tree_node_t, heap);
1785
 
1786
/* Vec containing references to all removed loop tree nodes.  */
1787
static VEC(ira_loop_tree_node_t,heap) *removed_loop_vec;
1788
 
1789
/* Vec containing references to all children of loop tree nodes.  */
1790
static VEC(ira_loop_tree_node_t,heap) *children_vec;
1791
 
1792
/* Remove subregions of NODE if their separate allocation will not
1793
   improve the result.  */
1794
static void
1795
remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
1796
{
1797
  unsigned int start;
1798
  bool remove_p;
1799
  ira_loop_tree_node_t subnode;
1800
 
1801
  remove_p = node->to_remove_p;
1802
  if (! remove_p)
1803
    VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, node);
1804
  start = VEC_length (ira_loop_tree_node_t, children_vec);
1805
  for (subnode = node->children; subnode != NULL; subnode = subnode->next)
1806
    if (subnode->bb == NULL)
1807
      remove_uneccesary_loop_nodes_from_loop_tree (subnode);
1808
    else
1809
      VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, subnode);
1810
  node->children = node->subloops = NULL;
1811
  if (remove_p)
1812
    {
1813
      VEC_safe_push (ira_loop_tree_node_t, heap, removed_loop_vec, node);
1814
      return;
1815
    }
1816
  while (VEC_length (ira_loop_tree_node_t, children_vec) > start)
1817
    {
1818
      subnode = VEC_pop (ira_loop_tree_node_t, children_vec);
1819
      subnode->parent = node;
1820
      subnode->next = node->children;
1821
      node->children = subnode;
1822
      if (subnode->bb == NULL)
1823
        {
1824
          subnode->subloop_next = node->subloops;
1825
          node->subloops = subnode;
1826
        }
1827
    }
1828
}
1829
 
1830
/* Return TRUE if NODE is inside PARENT.  */
1831
static bool
1832
loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
1833
{
1834
  for (node = node->parent; node != NULL; node = node->parent)
1835
    if (node == parent)
1836
      return true;
1837
  return false;
1838
}
1839
 
1840
/* Sort allocnos according to their order in regno allocno list.  */
1841
static int
1842
regno_allocno_order_compare_func (const void *v1p, const void *v2p)
1843
{
1844
  ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1845
  ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1846
  ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
1847
  ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
1848
 
1849
  if (loop_is_inside_p (n1, n2))
1850
    return -1;
1851
  else if (loop_is_inside_p (n2, n1))
1852
    return 1;
1853
  /* If allocnos are equally good, sort by allocno numbers, so that
1854
     the results of qsort leave nothing to chance.  We put allocnos
1855
     with higher number first in the list because it is the original
1856
     order for allocnos from loops on the same levels.  */
1857
  return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
1858
}
1859
 
1860
/* This array is used to sort allocnos to restore allocno order in
1861
   the regno allocno list.  */
1862
static ira_allocno_t *regno_allocnos;
1863
 
1864
/* Restore allocno order for REGNO in the regno allocno list.  */
1865
static void
1866
ira_rebuild_regno_allocno_list (int regno)
1867
{
1868
  int i, n;
1869
  ira_allocno_t a;
1870
 
1871
  for (n = 0, a = ira_regno_allocno_map[regno];
1872
       a != NULL;
1873
       a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1874
    regno_allocnos[n++] = a;
1875
  ira_assert (n > 0);
1876
  qsort (regno_allocnos, n, sizeof (ira_allocno_t),
1877
         regno_allocno_order_compare_func);
1878
  for (i = 1; i < n; i++)
1879
    ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
1880
  ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
1881
  ira_regno_allocno_map[regno] = regno_allocnos[0];
1882
  if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1883
    fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
1884
}
1885
 
1886
/* Propagate info from allocno FROM_A to allocno A.  */
1887
static void
1888
propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
1889
{
1890
  enum reg_class cover_class;
1891
 
1892
  IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
1893
                    ALLOCNO_CONFLICT_HARD_REGS (from_a));
1894
#ifdef STACK_REGS
1895
  if (ALLOCNO_NO_STACK_REG_P (from_a))
1896
    ALLOCNO_NO_STACK_REG_P (a) = true;
1897
#endif
1898
  ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
1899
  ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
1900
  ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
1901
  IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
1902
                    ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from_a));
1903
  ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
1904
  ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
1905
    += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
1906
  if (! ALLOCNO_BAD_SPILL_P (from_a))
1907
    ALLOCNO_BAD_SPILL_P (a) = false;
1908
#ifdef STACK_REGS
1909
  if (ALLOCNO_TOTAL_NO_STACK_REG_P (from_a))
1910
    ALLOCNO_TOTAL_NO_STACK_REG_P (a) = true;
1911
#endif
1912
  cover_class = ALLOCNO_COVER_CLASS (from_a);
1913
  ira_assert (cover_class == ALLOCNO_COVER_CLASS (a));
1914
  ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
1915
                                     ALLOCNO_HARD_REG_COSTS (from_a));
1916
  ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1917
                                     cover_class,
1918
                                     ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
1919
  ALLOCNO_COVER_CLASS_COST (a) += ALLOCNO_COVER_CLASS_COST (from_a);
1920
  ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
1921
}
1922
 
1923
/* Remove allocnos from loops removed from the allocation
1924
   consideration.  */
1925
static void
1926
remove_unnecessary_allocnos (void)
1927
{
1928
  int regno;
1929
  bool merged_p, rebuild_p;
1930
  ira_allocno_t a, prev_a, next_a, parent_a;
1931
  ira_loop_tree_node_t a_node, parent;
1932
  allocno_live_range_t r;
1933
 
1934
  merged_p = false;
1935
  regno_allocnos = NULL;
1936
  for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1937
    {
1938
      rebuild_p = false;
1939
      for (prev_a = NULL, a = ira_regno_allocno_map[regno];
1940
           a != NULL;
1941
           a = next_a)
1942
        {
1943
          next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
1944
          a_node = ALLOCNO_LOOP_TREE_NODE (a);
1945
          if (! a_node->to_remove_p)
1946
            prev_a = a;
1947
          else
1948
            {
1949
              for (parent = a_node->parent;
1950
                   (parent_a = parent->regno_allocno_map[regno]) == NULL
1951
                     && parent->to_remove_p;
1952
                   parent = parent->parent)
1953
                ;
1954
              if (parent_a == NULL)
1955
                {
1956
                  /* There are no allocnos with the same regno in
1957
                     upper region -- just move the allocno to the
1958
                     upper region.  */
1959
                  prev_a = a;
1960
                  ALLOCNO_LOOP_TREE_NODE (a) = parent;
1961
                  parent->regno_allocno_map[regno] = a;
1962
                  bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
1963
                  rebuild_p = true;
1964
                }
1965
              else
1966
                {
1967
                  /* Remove the allocno and update info of allocno in
1968
                     the upper region.  */
1969
                  if (prev_a == NULL)
1970
                    ira_regno_allocno_map[regno] = next_a;
1971
                  else
1972
                    ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
1973
                  r = ALLOCNO_LIVE_RANGES (a);
1974
                  change_allocno_in_range_list (r, parent_a);
1975
                  ALLOCNO_LIVE_RANGES (parent_a)
1976
                    = ira_merge_allocno_live_ranges
1977
                      (r, ALLOCNO_LIVE_RANGES (parent_a));
1978
                  merged_p = true;
1979
                  ALLOCNO_LIVE_RANGES (a) = NULL;
1980
                  propagate_some_info_from_allocno (parent_a, a);
1981
                  /* Remove it from the corresponding regno allocno
1982
                     map to avoid info propagation of subsequent
1983
                     allocno into this already removed allocno.  */
1984
                  a_node->regno_allocno_map[regno] = NULL;
1985
                  finish_allocno (a);
1986
                }
1987
            }
1988
        }
1989
      if (rebuild_p)
1990
        /* We need to restore the order in regno allocno list.  */
1991
        {
1992
          if (regno_allocnos == NULL)
1993
            regno_allocnos
1994
              = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
1995
                                                * ira_allocnos_num);
1996
          ira_rebuild_regno_allocno_list (regno);
1997
        }
1998
    }
1999
  if (merged_p)
2000
    ira_rebuild_start_finish_chains ();
2001
  if (regno_allocnos != NULL)
2002
    ira_free (regno_allocnos);
2003
}
2004
 
2005
/* Remove allocnos from all loops but the root.  */
2006
static void
2007
remove_low_level_allocnos (void)
2008
{
2009
  int regno;
2010
  bool merged_p, propagate_p;
2011
  ira_allocno_t a, top_a;
2012
  ira_loop_tree_node_t a_node, parent;
2013
  allocno_live_range_t r;
2014
  ira_allocno_iterator ai;
2015
 
2016
  merged_p = false;
2017
  FOR_EACH_ALLOCNO (a, ai)
2018
    {
2019
      a_node = ALLOCNO_LOOP_TREE_NODE (a);
2020
      if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2021
        continue;
2022
      regno = ALLOCNO_REGNO (a);
2023
      if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2024
        {
2025
          ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2026
          ira_loop_tree_root->regno_allocno_map[regno] = a;
2027
          continue;
2028
        }
2029
      propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2030
      /* Remove the allocno and update info of allocno in the upper
2031
         region.  */
2032
      r = ALLOCNO_LIVE_RANGES (a);
2033
      change_allocno_in_range_list (r, top_a);
2034
      ALLOCNO_LIVE_RANGES (top_a)
2035
        = ira_merge_allocno_live_ranges (r, ALLOCNO_LIVE_RANGES (top_a));
2036
      merged_p = true;
2037
      ALLOCNO_LIVE_RANGES (a) = NULL;
2038
      if (propagate_p)
2039
        propagate_some_info_from_allocno (top_a, a);
2040
    }
2041
  FOR_EACH_ALLOCNO (a, ai)
2042
    {
2043
      a_node = ALLOCNO_LOOP_TREE_NODE (a);
2044
      if (a_node == ira_loop_tree_root)
2045
        continue;
2046
      parent = a_node->parent;
2047
      regno = ALLOCNO_REGNO (a);
2048
      if (ALLOCNO_CAP_MEMBER (a) != NULL)
2049
        ira_assert (ALLOCNO_CAP (a) != NULL);
2050
      else if (ALLOCNO_CAP (a) == NULL)
2051
        ira_assert (parent->regno_allocno_map[regno] != NULL);
2052
    }
2053
  FOR_EACH_ALLOCNO (a, ai)
2054
    {
2055
      regno = ALLOCNO_REGNO (a);
2056
      if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2057
        {
2058
          ira_regno_allocno_map[regno] = a;
2059
          ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2060
          ALLOCNO_CAP_MEMBER (a) = NULL;
2061
          COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
2062
                             ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2063
#ifdef STACK_REGS
2064
          if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2065
            ALLOCNO_NO_STACK_REG_P (a) = true;
2066
#endif
2067
        }
2068
      else
2069
        finish_allocno (a);
2070
    }
2071
  if (merged_p)
2072
    ira_rebuild_start_finish_chains ();
2073
}
2074
 
2075
/* Remove loops from consideration.  We remove all loops except for
2076
   root if ALL_P or loops for which a separate allocation will not
2077
   improve the result.  We have to do this after allocno creation and
2078
   their costs and cover class evaluation because only after that the
2079
   register pressure can be known and is calculated.  */
2080
static void
2081
remove_unnecessary_regions (bool all_p)
2082
{
2083
  if (all_p)
2084
    mark_all_loops_for_removal ();
2085
  else
2086
    mark_loops_for_removal ();
2087
  children_vec
2088
    = VEC_alloc (ira_loop_tree_node_t, heap,
2089
                 last_basic_block + VEC_length (loop_p, ira_loops.larray));
2090
  removed_loop_vec
2091
    = VEC_alloc (ira_loop_tree_node_t, heap,
2092
                 last_basic_block + VEC_length (loop_p, ira_loops.larray));
2093
  remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root) ;
2094
  VEC_free (ira_loop_tree_node_t, heap, children_vec);
2095
  if (all_p)
2096
    remove_low_level_allocnos ();
2097
  else
2098
    remove_unnecessary_allocnos ();
2099
  while (VEC_length (ira_loop_tree_node_t, removed_loop_vec) > 0)
2100
    finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t, removed_loop_vec));
2101
  VEC_free (ira_loop_tree_node_t, heap, removed_loop_vec);
2102
}
2103
 
2104
 
2105
 
2106
/* At this point true value of allocno attribute bad_spill_p means
2107
   that there is an insn where allocno occurs and where the allocno
2108
   can not be used as memory.  The function updates the attribute, now
2109
   it can be true only for allocnos which can not be used as memory in
2110
   an insn and in whose live ranges there is other allocno deaths.
2111
   Spilling allocnos with true value will not improve the code because
2112
   it will not make other allocnos colorable and additional reloads
2113
   for the corresponding pseudo will be generated in reload pass for
2114
   each insn it occurs.
2115
 
2116
   This is a trick mentioned in one classic article of Chaitin etc
2117
   which is frequently omitted in other implementations of RA based on
2118
   graph coloring.  */
2119
static void
2120
update_bad_spill_attribute (void)
2121
{
2122
  int i;
2123
  ira_allocno_t a;
2124
  ira_allocno_iterator ai;
2125
  allocno_live_range_t r;
2126
  enum reg_class cover_class;
2127
  bitmap_head dead_points[N_REG_CLASSES];
2128
 
2129
  for (i = 0; i < ira_reg_class_cover_size; i++)
2130
    {
2131
      cover_class = ira_reg_class_cover[i];
2132
      bitmap_initialize (&dead_points[cover_class], &reg_obstack);
2133
    }
2134
  FOR_EACH_ALLOCNO (a, ai)
2135
    {
2136
      cover_class = ALLOCNO_COVER_CLASS (a);
2137
      if (cover_class == NO_REGS)
2138
        continue;
2139
      for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2140
        bitmap_set_bit (&dead_points[cover_class], r->finish);
2141
    }
2142
  FOR_EACH_ALLOCNO (a, ai)
2143
    {
2144
      cover_class = ALLOCNO_COVER_CLASS (a);
2145
      if (cover_class == NO_REGS)
2146
        continue;
2147
      if (! ALLOCNO_BAD_SPILL_P (a))
2148
        continue;
2149
      for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2150
        {
2151
          for (i = r->start + 1; i < r->finish; i++)
2152
            if (bitmap_bit_p (&dead_points[cover_class], i))
2153
              break;
2154
          if (i < r->finish)
2155
            break;
2156
        }
2157
      if (r != NULL)
2158
        ALLOCNO_BAD_SPILL_P (a) = false;
2159
    }
2160
  for (i = 0; i < ira_reg_class_cover_size; i++)
2161
    {
2162
      cover_class = ira_reg_class_cover[i];
2163
      bitmap_clear (&dead_points[cover_class]);
2164
    }
2165
}
2166
 
2167
 
2168
 
2169
/* Set up minimal and maximal live range points for allocnos.  */
2170
static void
2171
setup_min_max_allocno_live_range_point (void)
2172
{
2173
  int i;
2174
  ira_allocno_t a, parent_a, cap;
2175
  ira_allocno_iterator ai;
2176
  allocno_live_range_t r;
2177
  ira_loop_tree_node_t parent;
2178
 
2179
  FOR_EACH_ALLOCNO (a, ai)
2180
    {
2181
      r = ALLOCNO_LIVE_RANGES (a);
2182
      if (r == NULL)
2183
        continue;
2184
      ALLOCNO_MAX (a) = r->finish;
2185
      for (; r->next != NULL; r = r->next)
2186
        ;
2187
      ALLOCNO_MIN (a) = r->start;
2188
    }
2189
  for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2190
    for (a = ira_regno_allocno_map[i];
2191
         a != NULL;
2192
         a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2193
      {
2194
        if (ALLOCNO_MAX (a) < 0)
2195
          continue;
2196
        ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2197
        /* Accumulation of range info.  */
2198
        if (ALLOCNO_CAP (a) != NULL)
2199
          {
2200
            for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2201
              {
2202
                if (ALLOCNO_MAX (cap) < ALLOCNO_MAX (a))
2203
                  ALLOCNO_MAX (cap) = ALLOCNO_MAX (a);
2204
                if (ALLOCNO_MIN (cap) > ALLOCNO_MIN (a))
2205
                  ALLOCNO_MIN (cap) = ALLOCNO_MIN (a);
2206
              }
2207
            continue;
2208
          }
2209
        if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2210
          continue;
2211
        parent_a = parent->regno_allocno_map[i];
2212
        if (ALLOCNO_MAX (parent_a) < ALLOCNO_MAX (a))
2213
          ALLOCNO_MAX (parent_a) = ALLOCNO_MAX (a);
2214
        if (ALLOCNO_MIN (parent_a) > ALLOCNO_MIN (a))
2215
          ALLOCNO_MIN (parent_a) = ALLOCNO_MIN (a);
2216
      }
2217
#ifdef ENABLE_IRA_CHECKING
2218
  FOR_EACH_ALLOCNO (a, ai)
2219
    {
2220
      if ((0 <= ALLOCNO_MIN (a) && ALLOCNO_MIN (a) <= ira_max_point)
2221
          && (0 <= ALLOCNO_MAX (a) && ALLOCNO_MAX (a) <= ira_max_point))
2222
        continue;
2223
      gcc_unreachable ();
2224
    }
2225
#endif
2226
}
2227
 
2228
/* Sort allocnos according to their live ranges.  Allocnos with
2229
   smaller cover class are put first unless we use priority coloring.
2230
   Allocnos with the same cove class are ordered according their start
2231
   (min).  Allocnos with the same start are ordered according their
2232
   finish (max).  */
2233
static int
2234
allocno_range_compare_func (const void *v1p, const void *v2p)
2235
{
2236
  int diff;
2237
  ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2238
  ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2239
 
2240
  if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2241
      && (diff = ALLOCNO_COVER_CLASS (a1) - ALLOCNO_COVER_CLASS (a2)) != 0)
2242
    return diff;
2243
  if ((diff = ALLOCNO_MIN (a1) - ALLOCNO_MIN (a2)) != 0)
2244
    return diff;
2245
  if ((diff = ALLOCNO_MAX (a1) - ALLOCNO_MAX (a2)) != 0)
2246
     return diff;
2247
  return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2248
}
2249
 
2250
/* Sort ira_conflict_id_allocno_map and set up conflict id of
2251
   allocnos.  */
2252
static void
2253
sort_conflict_id_allocno_map (void)
2254
{
2255
  int i, num;
2256
  ira_allocno_t a;
2257
  ira_allocno_iterator ai;
2258
 
2259
  num = 0;
2260
  FOR_EACH_ALLOCNO (a, ai)
2261
    ira_conflict_id_allocno_map[num++] = a;
2262
  qsort (ira_conflict_id_allocno_map, num, sizeof (ira_allocno_t),
2263
         allocno_range_compare_func);
2264
  for (i = 0; i < num; i++)
2265
    if ((a = ira_conflict_id_allocno_map[i]) != NULL)
2266
      ALLOCNO_CONFLICT_ID (a) = i;
2267
  for (i = num; i < ira_allocnos_num; i++)
2268
    ira_conflict_id_allocno_map[i] = NULL;
2269
}
2270
 
2271
/* Set up minimal and maximal conflict ids of allocnos with which
2272
   given allocno can conflict.  */
2273
static void
2274
setup_min_max_conflict_allocno_ids (void)
2275
{
2276
  int cover_class;
2277
  int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2278
  int *live_range_min, *last_lived;
2279
  ira_allocno_t a;
2280
 
2281
  live_range_min = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
2282
  cover_class = -1;
2283
  first_not_finished = -1;
2284
  for (i = 0; i < ira_allocnos_num; i++)
2285
    {
2286
      a = ira_conflict_id_allocno_map[i];
2287
      if (a == NULL)
2288
        continue;
2289
      if (cover_class < 0
2290
          || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2291
              && cover_class != (int) ALLOCNO_COVER_CLASS (a)))
2292
        {
2293
          cover_class = ALLOCNO_COVER_CLASS (a);
2294
          min = i;
2295
          first_not_finished = i;
2296
        }
2297
      else
2298
        {
2299
          start = ALLOCNO_MIN (a);
2300
          /* If we skip an allocno, the allocno with smaller ids will
2301
             be also skipped because of the secondary sorting the
2302
             range finishes (see function
2303
             allocno_range_compare_func).  */
2304
          while (first_not_finished < i
2305
                 && start > ALLOCNO_MAX (ira_conflict_id_allocno_map
2306
                                         [first_not_finished]))
2307
            first_not_finished++;
2308
          min = first_not_finished;
2309
        }
2310
      if (min == i)
2311
        /* We could increase min further in this case but it is good
2312
           enough.  */
2313
        min++;
2314
      live_range_min[i] = ALLOCNO_MIN (a);
2315
      ALLOCNO_MIN (a) = min;
2316
    }
2317
  last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2318
  cover_class = -1;
2319
  filled_area_start = -1;
2320
  for (i = ira_allocnos_num - 1; i >= 0; i--)
2321
    {
2322
      a = ira_conflict_id_allocno_map[i];
2323
      if (a == NULL)
2324
        continue;
2325
      if (cover_class < 0
2326
          || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2327
              && cover_class != (int) ALLOCNO_COVER_CLASS (a)))
2328
        {
2329
          cover_class = ALLOCNO_COVER_CLASS (a);
2330
          for (j = 0; j < ira_max_point; j++)
2331
            last_lived[j] = -1;
2332
          filled_area_start = ira_max_point;
2333
        }
2334
      min = live_range_min[i];
2335
      finish = ALLOCNO_MAX (a);
2336
      max = last_lived[finish];
2337
      if (max < 0)
2338
        /* We could decrease max further in this case but it is good
2339
           enough.  */
2340
        max = ALLOCNO_CONFLICT_ID (a) - 1;
2341
      ALLOCNO_MAX (a) = max;
2342
      /* In filling, we can go further A range finish to recognize
2343
         intersection quickly because if the finish of subsequently
2344
         processed allocno (it has smaller conflict id) range is
2345
         further A range finish than they are definitely intersected
2346
         (the reason for this is the allocnos with bigger conflict id
2347
         have their range starts not smaller than allocnos with
2348
         smaller ids.  */
2349
      for (j = min; j < filled_area_start; j++)
2350
        last_lived[j] = i;
2351
      filled_area_start = min;
2352
    }
2353
  ira_free (last_lived);
2354
  ira_free (live_range_min);
2355
}
2356
 
2357
 
2358
 
2359
static void
2360
create_caps (void)
2361
{
2362
  ira_allocno_t a;
2363
  ira_allocno_iterator ai;
2364
  ira_loop_tree_node_t loop_tree_node;
2365
 
2366
  FOR_EACH_ALLOCNO (a, ai)
2367
    {
2368
      if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2369
        continue;
2370
      if (ALLOCNO_CAP_MEMBER (a) != NULL)
2371
        create_cap_allocno (a);
2372
      else if (ALLOCNO_CAP (a) == NULL)
2373
        {
2374
          loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2375
          if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2376
            create_cap_allocno (a);
2377
        }
2378
    }
2379
}
2380
 
2381
 
2382
 
2383
/* The page contains code transforming more one region internal
2384
   representation (IR) to one region IR which is necessary for reload.
2385
   This transformation is called IR flattening.  We might just rebuild
2386
   the IR for one region but we don't do it because it takes a lot of
2387
   time.  */
2388
 
2389
/* Map: regno -> allocnos which will finally represent the regno for
2390
   IR with one region.  */
2391
static ira_allocno_t *regno_top_level_allocno_map;
2392
 
2393
/* Process all allocnos originated from pseudo REGNO and copy live
2394
   ranges, hard reg conflicts, and allocno stack reg attributes from
2395
   low level allocnos to final allocnos which are destinations of
2396
   removed stores at a loop exit.  Return true if we copied live
2397
   ranges.  */
2398
static bool
2399
copy_info_to_removed_store_destinations (int regno)
2400
{
2401
  ira_allocno_t a;
2402
  ira_allocno_t parent_a = NULL;
2403
  ira_loop_tree_node_t parent;
2404
  allocno_live_range_t r;
2405
  bool merged_p;
2406
 
2407
  merged_p = false;
2408
  for (a = ira_regno_allocno_map[regno];
2409
       a != NULL;
2410
       a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2411
    {
2412
      if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))])
2413
        /* This allocno will be removed.  */
2414
        continue;
2415
      /* Caps will be removed.  */
2416
      ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2417
      for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2418
           parent != NULL;
2419
           parent = parent->parent)
2420
        if ((parent_a = parent->regno_allocno_map[regno]) == NULL
2421
            || (parent_a == regno_top_level_allocno_map[REGNO (ALLOCNO_REG
2422
                                                               (parent_a))]
2423
                && ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)))
2424
          break;
2425
      if (parent == NULL || parent_a == NULL)
2426
        continue;
2427
      if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2428
        {
2429
          fprintf
2430
            (ira_dump_file,
2431
             "      Coping ranges of a%dr%d to a%dr%d: ",
2432
             ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
2433
             ALLOCNO_NUM (parent_a), REGNO (ALLOCNO_REG (parent_a)));
2434
          ira_print_live_range_list (ira_dump_file,
2435
                                     ALLOCNO_LIVE_RANGES (a));
2436
        }
2437
      r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
2438
      change_allocno_in_range_list (r, parent_a);
2439
      ALLOCNO_LIVE_RANGES (parent_a)
2440
        = ira_merge_allocno_live_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
2441
      IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
2442
                        ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2443
#ifdef STACK_REGS
2444
      if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2445
        ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
2446
#endif
2447
      ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2448
      ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2449
        += ALLOCNO_CALLS_CROSSED_NUM (a);
2450
      ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2451
        += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2452
      merged_p = true;
2453
    }
2454
  return merged_p;
2455
}
2456
 
2457
/* Flatten the IR.  In other words, this function transforms IR as if
2458
   it were built with one region (without loops).  We could make it
2459
   much simpler by rebuilding IR with one region, but unfortunately it
2460
   takes a lot of time.  MAX_REGNO_BEFORE_EMIT and
2461
   IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2462
   IRA_MAX_POINT before emitting insns on the loop borders.  */
2463
void
2464
ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
2465
{
2466
  int i, j, num;
2467
  bool keep_p;
2468
  int hard_regs_num;
2469
  bool new_pseudos_p, merged_p, mem_dest_p;
2470
  unsigned int n;
2471
  enum reg_class cover_class;
2472
  ira_allocno_t a, parent_a, first, second, node_first, node_second;
2473
  ira_copy_t cp;
2474
  ira_loop_tree_node_t parent, node;
2475
  allocno_live_range_t r;
2476
  ira_allocno_iterator ai;
2477
  ira_copy_iterator ci;
2478
  sparseset allocnos_live;
2479
 
2480
  regno_top_level_allocno_map
2481
    = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t));
2482
  memset (regno_top_level_allocno_map, 0,
2483
          max_reg_num () * sizeof (ira_allocno_t));
2484
  new_pseudos_p = merged_p = false;
2485
  FOR_EACH_ALLOCNO (a, ai)
2486
    {
2487
      if (ALLOCNO_CAP_MEMBER (a) != NULL)
2488
        /* Caps are not in the regno allocno maps and they are never
2489
           will be transformed into allocnos existing after IR
2490
           flattening.  */
2491
        continue;
2492
      COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
2493
                         ALLOCNO_CONFLICT_HARD_REGS (a));
2494
#ifdef STACK_REGS
2495
      ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
2496
#endif
2497
    }
2498
  /* Fix final allocno attributes.  */
2499
  for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2500
    {
2501
      mem_dest_p = false;
2502
      for (a = ira_regno_allocno_map[i];
2503
           a != NULL;
2504
           a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2505
        {
2506
          ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2507
          if (ALLOCNO_SOMEWHERE_RENAMED_P (a))
2508
            new_pseudos_p = true;
2509
          if (ALLOCNO_CAP (a) != NULL
2510
              || (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
2511
              || ((parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
2512
                  == NULL))
2513
            {
2514
              ALLOCNO_COPIES (a) = NULL;
2515
              regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2516
              continue;
2517
            }
2518
          ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
2519
 
2520
          if (ALLOCNO_MEM_OPTIMIZED_DEST (a) != NULL)
2521
            mem_dest_p = true;
2522
          if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (parent_a)))
2523
            {
2524
              IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
2525
                                ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2526
#ifdef STACK_REGS
2527
              if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2528
                ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
2529
#endif
2530
              if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2531
                {
2532
                  fprintf (ira_dump_file,
2533
                           "      Moving ranges of a%dr%d to a%dr%d: ",
2534
                           ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
2535
                           ALLOCNO_NUM (parent_a),
2536
                           REGNO (ALLOCNO_REG (parent_a)));
2537
                  ira_print_live_range_list (ira_dump_file,
2538
                                             ALLOCNO_LIVE_RANGES (a));
2539
                }
2540
              change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a), parent_a);
2541
              ALLOCNO_LIVE_RANGES (parent_a)
2542
                = ira_merge_allocno_live_ranges
2543
                  (ALLOCNO_LIVE_RANGES (a), ALLOCNO_LIVE_RANGES (parent_a));
2544
              merged_p = true;
2545
              ALLOCNO_LIVE_RANGES (a) = NULL;
2546
              ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2547
                = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2548
                   || ALLOCNO_MEM_OPTIMIZED_DEST_P (a));
2549
              continue;
2550
            }
2551
          new_pseudos_p = true;
2552
          for (;;)
2553
            {
2554
              ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
2555
              ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
2556
              ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
2557
              ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2558
                -= ALLOCNO_CALLS_CROSSED_NUM (a);
2559
              ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2560
                -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2561
              ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
2562
                          && ALLOCNO_NREFS (parent_a) >= 0
2563
                          && ALLOCNO_FREQ (parent_a) >= 0);
2564
              cover_class = ALLOCNO_COVER_CLASS (parent_a);
2565
              hard_regs_num = ira_class_hard_regs_num[cover_class];
2566
              if (ALLOCNO_HARD_REG_COSTS (a) != NULL
2567
                  && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
2568
                for (j = 0; j < hard_regs_num; j++)
2569
                  ALLOCNO_HARD_REG_COSTS (parent_a)[j]
2570
                    -= ALLOCNO_HARD_REG_COSTS (a)[j];
2571
              if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
2572
                  && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
2573
                for (j = 0; j < hard_regs_num; j++)
2574
                  ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
2575
                    -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
2576
              ALLOCNO_COVER_CLASS_COST (parent_a)
2577
                -= ALLOCNO_COVER_CLASS_COST (a);
2578
              ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
2579
              if (ALLOCNO_CAP (parent_a) != NULL
2580
                  || (parent
2581
                      = ALLOCNO_LOOP_TREE_NODE (parent_a)->parent) == NULL
2582
                  || (parent_a = (parent->regno_allocno_map
2583
                                  [ALLOCNO_REGNO (parent_a)])) == NULL)
2584
                break;
2585
            }
2586
          ALLOCNO_COPIES (a) = NULL;
2587
          regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2588
        }
2589
      if (mem_dest_p && copy_info_to_removed_store_destinations (i))
2590
        merged_p = true;
2591
    }
2592
  ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
2593
  if (merged_p || ira_max_point_before_emit != ira_max_point)
2594
    ira_rebuild_start_finish_chains ();
2595
  if (new_pseudos_p)
2596
    {
2597
      /* Rebuild conflicts.  */
2598
      FOR_EACH_ALLOCNO (a, ai)
2599
        {
2600
          if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2601
              || ALLOCNO_CAP_MEMBER (a) != NULL)
2602
            continue;
2603
          for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2604
            ira_assert (r->allocno == a);
2605
          clear_allocno_conflicts (a);
2606
        }
2607
      allocnos_live = sparseset_alloc (ira_allocnos_num);
2608
      for (i = 0; i < ira_max_point; i++)
2609
        {
2610
          for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
2611
            {
2612
              a = r->allocno;
2613
              if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2614
                  || ALLOCNO_CAP_MEMBER (a) != NULL)
2615
                continue;
2616
              num = ALLOCNO_NUM (a);
2617
              cover_class = ALLOCNO_COVER_CLASS (a);
2618
              sparseset_set_bit (allocnos_live, num);
2619
              EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, n)
2620
                {
2621
                  ira_allocno_t live_a = ira_allocnos[n];
2622
 
2623
                  if (ira_reg_classes_intersect_p
2624
                      [cover_class][ALLOCNO_COVER_CLASS (live_a)]
2625
                      /* Don't set up conflict for the allocno with itself.  */
2626
                      && num != (int) n)
2627
                    ira_add_allocno_conflict (a, live_a);
2628
                }
2629
            }
2630
 
2631
          for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
2632
            sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (r->allocno));
2633
        }
2634
      sparseset_free (allocnos_live);
2635
      compress_conflict_vecs ();
2636
    }
2637
  /* Mark some copies for removing and change allocnos in the rest
2638
     copies.  */
2639
  FOR_EACH_COPY (cp, ci)
2640
    {
2641
      if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
2642
          || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
2643
        {
2644
          if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2645
            fprintf
2646
              (ira_dump_file, "      Remove cp%d:%c%dr%d-%c%dr%d\n",
2647
               cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
2648
               ALLOCNO_NUM (cp->first), REGNO (ALLOCNO_REG (cp->first)),
2649
               ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
2650
               ALLOCNO_NUM (cp->second), REGNO (ALLOCNO_REG (cp->second)));
2651
          cp->loop_tree_node = NULL;
2652
          continue;
2653
        }
2654
      first = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->first))];
2655
      second = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->second))];
2656
      node = cp->loop_tree_node;
2657
      if (node == NULL)
2658
        keep_p = true; /* It copy generated in ira-emit.c.  */
2659
      else
2660
        {
2661
          /* Check that the copy was not propagated from level on
2662
             which we will have different pseudos.  */
2663
          node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
2664
          node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
2665
          keep_p = ((REGNO (ALLOCNO_REG (first))
2666
                     == REGNO (ALLOCNO_REG (node_first)))
2667
                     && (REGNO (ALLOCNO_REG (second))
2668
                         == REGNO (ALLOCNO_REG (node_second))));
2669
        }
2670
      if (keep_p)
2671
        {
2672
          cp->loop_tree_node = ira_loop_tree_root;
2673
          cp->first = first;
2674
          cp->second = second;
2675
        }
2676
      else
2677
        {
2678
          cp->loop_tree_node = NULL;
2679
          if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2680
            fprintf (ira_dump_file, "      Remove cp%d:a%dr%d-a%dr%d\n",
2681
                     cp->num, ALLOCNO_NUM (cp->first),
2682
                     REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
2683
                     REGNO (ALLOCNO_REG (cp->second)));
2684
        }
2685
    }
2686
  /* Remove unnecessary allocnos on lower levels of the loop tree.  */
2687
  FOR_EACH_ALLOCNO (a, ai)
2688
    {
2689
      if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2690
          || ALLOCNO_CAP_MEMBER (a) != NULL)
2691
        {
2692
          if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2693
            fprintf (ira_dump_file, "      Remove a%dr%d\n",
2694
                     ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
2695
          finish_allocno (a);
2696
          continue;
2697
        }
2698
      ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2699
      ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
2700
      ALLOCNO_CAP (a) = NULL;
2701
      /* Restore updated costs for assignments from reload.  */
2702
      ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
2703
      ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
2704
      if (! ALLOCNO_ASSIGNED_P (a))
2705
        ira_free_allocno_updated_costs (a);
2706
      ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2707
      ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2708
    }
2709
  /* Remove unnecessary copies.  */
2710
  FOR_EACH_COPY (cp, ci)
2711
    {
2712
      if (cp->loop_tree_node == NULL)
2713
        {
2714
          ira_copies[cp->num] = NULL;
2715
          finish_copy (cp);
2716
          continue;
2717
        }
2718
      ira_assert
2719
        (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
2720
         && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
2721
      ira_add_allocno_copy_to_list (cp);
2722
      ira_swap_allocno_copy_ends_if_necessary (cp);
2723
    }
2724
  rebuild_regno_allocno_maps ();
2725
  if (ira_max_point != ira_max_point_before_emit)
2726
    ira_compress_allocno_live_ranges ();
2727
  ira_free (regno_top_level_allocno_map);
2728
}
2729
 
2730
 
2731
 
2732
#ifdef ENABLE_IRA_CHECKING
2733
/* Check creation of all allocnos.  Allocnos on lower levels should
2734
   have allocnos or caps on all upper levels.  */
2735
static void
2736
check_allocno_creation (void)
2737
{
2738
  ira_allocno_t a;
2739
  ira_allocno_iterator ai;
2740
  ira_loop_tree_node_t loop_tree_node;
2741
 
2742
  FOR_EACH_ALLOCNO (a, ai)
2743
    {
2744
      loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2745
      ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
2746
                                ALLOCNO_NUM (a)));
2747
      if (loop_tree_node == ira_loop_tree_root)
2748
        continue;
2749
      if (ALLOCNO_CAP_MEMBER (a) != NULL)
2750
        ira_assert (ALLOCNO_CAP (a) != NULL);
2751
      else if (ALLOCNO_CAP (a) == NULL)
2752
        ira_assert (loop_tree_node->parent
2753
                    ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
2754
                    && bitmap_bit_p (loop_tree_node->border_allocnos,
2755
                                     ALLOCNO_NUM (a)));
2756
    }
2757
}
2758
#endif
2759
 
2760
/* Create a internal representation (IR) for IRA (allocnos, copies,
2761
   loop tree nodes).  If LOOPS_P is FALSE the nodes corresponding to
2762
   the loops (except the root which corresponds the all function) and
2763
   correspondingly allocnos for the loops will be not created.  Such
2764
   parameter value is used for Chaitin-Briggs coloring.  The function
2765
   returns TRUE if we generate loop structure (besides nodes
2766
   representing all function and the basic blocks) for regional
2767
   allocation.  A true return means that we really need to flatten IR
2768
   before the reload.  */
2769
bool
2770
ira_build (bool loops_p)
2771
{
2772
  df_analyze ();
2773
 
2774
  initiate_cost_vectors ();
2775
  initiate_allocnos ();
2776
  initiate_copies ();
2777
  create_loop_tree_nodes (loops_p);
2778
  form_loop_tree ();
2779
  create_allocnos ();
2780
  ira_costs ();
2781
  ira_create_allocno_live_ranges ();
2782
  remove_unnecessary_regions (false);
2783
  ira_compress_allocno_live_ranges ();
2784
  update_bad_spill_attribute ();
2785
  loops_p = more_one_region_p ();
2786
  if (loops_p)
2787
    {
2788
      propagate_allocno_info ();
2789
      create_caps ();
2790
    }
2791
  ira_tune_allocno_costs_and_cover_classes ();
2792
#ifdef ENABLE_IRA_CHECKING
2793
  check_allocno_creation ();
2794
#endif
2795
  setup_min_max_allocno_live_range_point ();
2796
  sort_conflict_id_allocno_map ();
2797
  setup_min_max_conflict_allocno_ids ();
2798
  ira_build_conflicts ();
2799
  if (! ira_conflicts_p)
2800
    {
2801
      ira_allocno_t a;
2802
      ira_allocno_iterator ai;
2803
 
2804
      /* Remove all regions but root one.  */
2805
      if (loops_p)
2806
        {
2807
          remove_unnecessary_regions (true);
2808
          loops_p = false;
2809
        }
2810
      /* We don't save hard registers around calls for fast allocation
2811
         -- add caller clobbered registers as conflicting ones to
2812
         allocno crossing calls.  */
2813
      FOR_EACH_ALLOCNO (a, ai)
2814
        if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2815
          {
2816
            IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
2817
                              call_used_reg_set);
2818
            IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
2819
                              call_used_reg_set);
2820
          }
2821
    }
2822
  if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2823
    print_copies (ira_dump_file);
2824
  if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2825
    {
2826
      int n, nr;
2827
      ira_allocno_t a;
2828
      allocno_live_range_t r;
2829
      ira_allocno_iterator ai;
2830
 
2831
      n = 0;
2832
      FOR_EACH_ALLOCNO (a, ai)
2833
        n += ALLOCNO_CONFLICT_ALLOCNOS_NUM (a);
2834
      nr = 0;
2835
      FOR_EACH_ALLOCNO (a, ai)
2836
        for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2837
          nr++;
2838
      fprintf (ira_dump_file, "  regions=%d, blocks=%d, points=%d\n",
2839
               VEC_length (loop_p, ira_loops.larray), n_basic_blocks,
2840
               ira_max_point);
2841
      fprintf (ira_dump_file,
2842
               "    allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2843
               ira_allocnos_num, ira_copies_num, n, nr);
2844
    }
2845
  return loops_p;
2846
}
2847
 
2848
/* Release the data created by function ira_build.  */
2849
void
2850
ira_destroy (void)
2851
{
2852
  finish_loop_tree_nodes ();
2853
  finish_copies ();
2854
  finish_allocnos ();
2855
  finish_cost_vectors ();
2856
  ira_finish_allocno_live_ranges ();
2857
}

powered by: WebSVN 2.1.0

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