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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [ira-lives.c] - Blame information for rev 859

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

Line No. Rev Author Line
1 280 jeremybenn
/* IRA processing allocno lives to build allocno live ranges.
2
   Copyright (C) 2006, 2007, 2008, 2009, 2010
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 "regs.h"
27
#include "rtl.h"
28
#include "tm_p.h"
29
#include "target.h"
30
#include "flags.h"
31
#include "except.h"
32
#include "hard-reg-set.h"
33
#include "basic-block.h"
34
#include "insn-config.h"
35
#include "recog.h"
36
#include "toplev.h"
37
#include "params.h"
38
#include "df.h"
39
#include "sparseset.h"
40
#include "ira-int.h"
41
 
42
/* The code in this file is similar to one in global but the code
43
   works on the allocno basis and creates live ranges instead of
44
   pseudo-register conflicts.  */
45
 
46
/* Program points are enumerated by numbers from range
47
   0..IRA_MAX_POINT-1.  There are approximately two times more program
48
   points than insns.  Program points are places in the program where
49
   liveness info can be changed.  In most general case (there are more
50
   complicated cases too) some program points correspond to places
51
   where input operand dies and other ones correspond to places where
52
   output operands are born.  */
53
int ira_max_point;
54
 
55
/* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
56
   live ranges with given start/finish point.  */
57
allocno_live_range_t *ira_start_point_ranges, *ira_finish_point_ranges;
58
 
59
/* Number of the current program point.  */
60
static int curr_point;
61
 
62
/* Point where register pressure excess started or -1 if there is no
63
   register pressure excess.  Excess pressure for a register class at
64
   some point means that there are more allocnos of given register
65
   class living at the point than number of hard-registers of the
66
   class available for the allocation.  It is defined only for cover
67
   classes.  */
68
static int high_pressure_start_point[N_REG_CLASSES];
69
 
70
/* Allocnos live at current point in the scan.  */
71
static sparseset allocnos_live;
72
 
73
/* Set of hard regs (except eliminable ones) currently live.  */
74
static HARD_REG_SET hard_regs_live;
75
 
76
/* The loop tree node corresponding to the current basic block.  */
77
static ira_loop_tree_node_t curr_bb_node;
78
 
79
/* The number of the last processed call.  */
80
static int last_call_num;
81
/* The number of last call at which given allocno was saved.  */
82
static int *allocno_saved_at_call;
83
 
84
/* The function processing birth of register REGNO.  It updates living
85
   hard regs and conflict hard regs for living allocnos or starts a
86
   new live range for the allocno corresponding to REGNO if it is
87
   necessary.  */
88
static void
89
make_regno_born (int regno)
90
{
91
  unsigned int i;
92
  ira_allocno_t a;
93
  allocno_live_range_t p;
94
 
95
  if (regno < FIRST_PSEUDO_REGISTER)
96
    {
97
      SET_HARD_REG_BIT (hard_regs_live, regno);
98
      EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
99
        {
100
          SET_HARD_REG_BIT (ALLOCNO_CONFLICT_HARD_REGS (ira_allocnos[i]),
101
                            regno);
102
          SET_HARD_REG_BIT (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (ira_allocnos[i]),
103
                            regno);
104
        }
105
      return;
106
    }
107
  a = ira_curr_regno_allocno_map[regno];
108
  if (a == NULL)
109
    return;
110
  if ((p = ALLOCNO_LIVE_RANGES (a)) == NULL
111
      || (p->finish != curr_point && p->finish + 1 != curr_point))
112
    ALLOCNO_LIVE_RANGES (a)
113
      = ira_create_allocno_live_range (a, curr_point, -1,
114
                                       ALLOCNO_LIVE_RANGES (a));
115
}
116
 
117
/* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for allocno A.  */
118
static void
119
update_allocno_pressure_excess_length (ira_allocno_t a)
120
{
121
  int start, i;
122
  enum reg_class cover_class, cl;
123
  allocno_live_range_t p;
124
 
125
  cover_class = ALLOCNO_COVER_CLASS (a);
126
  for (i = 0;
127
       (cl = ira_reg_class_super_classes[cover_class][i]) != LIM_REG_CLASSES;
128
       i++)
129
    {
130
      if (high_pressure_start_point[cl] < 0)
131
        continue;
132
      p = ALLOCNO_LIVE_RANGES (a);
133
      ira_assert (p != NULL);
134
      start = (high_pressure_start_point[cl] > p->start
135
               ? high_pressure_start_point[cl] : p->start);
136
      ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) += curr_point - start + 1;
137
    }
138
}
139
 
140
/* Process the death of register REGNO.  This updates hard_regs_live
141
   or finishes the current live range for the allocno corresponding to
142
   REGNO.  */
143
static void
144
make_regno_dead (int regno)
145
{
146
  ira_allocno_t a;
147
  allocno_live_range_t p;
148
 
149
  if (regno < FIRST_PSEUDO_REGISTER)
150
    {
151
      CLEAR_HARD_REG_BIT (hard_regs_live, regno);
152
      return;
153
    }
154
  a = ira_curr_regno_allocno_map[regno];
155
  if (a == NULL)
156
    return;
157
  p = ALLOCNO_LIVE_RANGES (a);
158
  ira_assert (p != NULL);
159
  p->finish = curr_point;
160
  update_allocno_pressure_excess_length (a);
161
}
162
 
163
/* The current register pressures for each cover class for the current
164
   basic block.  */
165
static int curr_reg_pressure[N_REG_CLASSES];
166
 
167
/* Mark allocno A as currently living and update current register
168
   pressure, maximal register pressure for the current BB, start point
169
   of the register pressure excess, and conflicting hard registers of
170
   A.  */
171
static void
172
set_allocno_live (ira_allocno_t a)
173
{
174
  int i;
175
  enum reg_class cover_class, cl;
176
 
177
  /* Invalidate because it is referenced.  */
178
  allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
179
  if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
180
    return;
181
  sparseset_set_bit (allocnos_live, ALLOCNO_NUM (a));
182
  IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), hard_regs_live);
183
  IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), hard_regs_live);
184
  cover_class = ALLOCNO_COVER_CLASS (a);
185
  for (i = 0;
186
       (cl = ira_reg_class_super_classes[cover_class][i]) != LIM_REG_CLASSES;
187
       i++)
188
    {
189
      curr_reg_pressure[cl] += ira_reg_class_nregs[cl][ALLOCNO_MODE (a)];
190
      if (high_pressure_start_point[cl] < 0
191
          && (curr_reg_pressure[cl] > ira_available_class_regs[cl]))
192
        high_pressure_start_point[cl] = curr_point;
193
      if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
194
        curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
195
    }
196
}
197
 
198
/* Mark allocno A as currently not living and update current register
199
   pressure, start point of the register pressure excess, and register
200
   pressure excess length for living allocnos.  */
201
static void
202
clear_allocno_live (ira_allocno_t a)
203
{
204
  int i;
205
  unsigned int j;
206
  enum reg_class cover_class, cl;
207
  bool set_p;
208
 
209
  /* Invalidate because it is referenced.  */
210
  allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
211
  if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
212
    {
213
      cover_class = ALLOCNO_COVER_CLASS (a);
214
      set_p = false;
215
      for (i = 0;
216
           (cl = ira_reg_class_super_classes[cover_class][i])
217
             != LIM_REG_CLASSES;
218
           i++)
219
        {
220
          curr_reg_pressure[cl] -= ira_reg_class_nregs[cl][ALLOCNO_MODE (a)];
221
          ira_assert (curr_reg_pressure[cl] >= 0);
222
          if (high_pressure_start_point[cl] >= 0
223
              && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
224
            set_p = true;
225
        }
226
      if (set_p)
227
        {
228
          EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, j)
229
            update_allocno_pressure_excess_length (ira_allocnos[j]);
230
          for (i = 0;
231
               (cl = ira_reg_class_super_classes[cover_class][i])
232
                 != LIM_REG_CLASSES;
233
               i++)
234
            if (high_pressure_start_point[cl] >= 0
235
                && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
236
              high_pressure_start_point[cl] = -1;
237
 
238
        }
239
    }
240
  sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (a));
241
}
242
 
243
/* Mark the register REG as live.  Store a 1 in hard_regs_live or
244
   allocnos_live for this register or the corresponding allocno,
245
   record how many consecutive hardware registers it actually
246
   needs.  */
247
static void
248
mark_reg_live (rtx reg)
249
{
250
  int i, regno;
251
 
252
  gcc_assert (REG_P (reg));
253
  regno = REGNO (reg);
254
 
255
  if (regno >= FIRST_PSEUDO_REGISTER)
256
    {
257
      ira_allocno_t a = ira_curr_regno_allocno_map[regno];
258
 
259
      if (a != NULL)
260
        {
261
          if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
262
            {
263
              /* Invalidate because it is referenced.  */
264
              allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
265
              return;
266
            }
267
          set_allocno_live (a);
268
        }
269
      make_regno_born (regno);
270
    }
271
  else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
272
    {
273
      int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
274
      enum reg_class cover_class, cl;
275
 
276
      while (regno < last)
277
        {
278
          if (! TEST_HARD_REG_BIT (hard_regs_live, regno)
279
              && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
280
            {
281
              cover_class = ira_hard_regno_cover_class[regno];
282
              for (i = 0;
283
                   (cl = ira_reg_class_super_classes[cover_class][i])
284
                     != LIM_REG_CLASSES;
285
                   i++)
286
                {
287
                  curr_reg_pressure[cl]++;
288
                  if (high_pressure_start_point[cl] < 0
289
                      && (curr_reg_pressure[cl]
290
                          > ira_available_class_regs[cl]))
291
                    high_pressure_start_point[cl] = curr_point;
292
                }
293
              make_regno_born (regno);
294
              for (i = 0;
295
                   (cl = ira_reg_class_super_classes[cover_class][i])
296
                     != LIM_REG_CLASSES;
297
                   i++)
298
                {
299
                  if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
300
                    curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
301
                }
302
            }
303
          regno++;
304
        }
305
    }
306
}
307
 
308
/* Mark the register referenced by use or def REF as live.  */
309
static void
310
mark_ref_live (df_ref ref)
311
{
312
  rtx reg;
313
 
314
  reg = DF_REF_REG (ref);
315
  if (GET_CODE (reg) == SUBREG)
316
    reg = SUBREG_REG (reg);
317
  mark_reg_live (reg);
318
}
319
 
320
/* Mark the register REG as dead.  Store a 0 in hard_regs_live or
321
   allocnos_live for the register.  */
322
static void
323
mark_reg_dead (rtx reg)
324
{
325
  int regno;
326
 
327
  gcc_assert (REG_P (reg));
328
  regno = REGNO (reg);
329
 
330
  if (regno >= FIRST_PSEUDO_REGISTER)
331
    {
332
      ira_allocno_t a = ira_curr_regno_allocno_map[regno];
333
 
334
      if (a != NULL)
335
        {
336
          if (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
337
            {
338
              /* Invalidate because it is referenced.  */
339
              allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
340
              return;
341
            }
342
          clear_allocno_live (a);
343
        }
344
      make_regno_dead (regno);
345
    }
346
  else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
347
    {
348
      int i;
349
      unsigned int j;
350
      int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
351
      enum reg_class cover_class, cl;
352
      bool set_p;
353
 
354
      while (regno < last)
355
        {
356
          if (TEST_HARD_REG_BIT (hard_regs_live, regno))
357
            {
358
              set_p = false;
359
              cover_class = ira_hard_regno_cover_class[regno];
360
              for (i = 0;
361
                   (cl = ira_reg_class_super_classes[cover_class][i])
362
                     != LIM_REG_CLASSES;
363
                   i++)
364
                {
365
                  curr_reg_pressure[cl]--;
366
                  if (high_pressure_start_point[cl] >= 0
367
                      && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
368
                    set_p = true;
369
                  ira_assert (curr_reg_pressure[cl] >= 0);
370
                }
371
              if (set_p)
372
                {
373
                  EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, j)
374
                    update_allocno_pressure_excess_length (ira_allocnos[j]);
375
                  for (i = 0;
376
                       (cl = ira_reg_class_super_classes[cover_class][i])
377
                         != LIM_REG_CLASSES;
378
                       i++)
379
                    if (high_pressure_start_point[cl] >= 0
380
                        && (curr_reg_pressure[cl]
381
                            <= ira_available_class_regs[cl]))
382
                      high_pressure_start_point[cl] = -1;
383
                }
384
              make_regno_dead (regno);
385
            }
386
          regno++;
387
        }
388
    }
389
}
390
 
391
/* Mark the register referenced by definition DEF as dead, if the
392
   definition is a total one.  */
393
static void
394
mark_ref_dead (df_ref def)
395
{
396
  rtx reg;
397
 
398
  if (DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL)
399
      || DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
400
    return;
401
 
402
  reg = DF_REF_REG (def);
403
  if (GET_CODE (reg) == SUBREG)
404
    reg = SUBREG_REG (reg);
405
  mark_reg_dead (reg);
406
}
407
 
408
/* Make pseudo REG conflicting with pseudo DREG, if the 1st pseudo
409
   class is intersected with class CL.  Advance the current program
410
   point before making the conflict if ADVANCE_P.  Return TRUE if we
411
   will need to advance the current program point.  */
412
static bool
413
make_pseudo_conflict (rtx reg, enum reg_class cl, rtx dreg, bool advance_p)
414
{
415
  ira_allocno_t a;
416
 
417
  if (GET_CODE (reg) == SUBREG)
418
    reg = SUBREG_REG (reg);
419
 
420
  if (! REG_P (reg) || REGNO (reg) < FIRST_PSEUDO_REGISTER)
421
    return advance_p;
422
 
423
  a = ira_curr_regno_allocno_map[REGNO (reg)];
424
  if (! reg_classes_intersect_p (cl, ALLOCNO_COVER_CLASS (a)))
425
    return advance_p;
426
 
427
  if (advance_p)
428
    curr_point++;
429
 
430
  mark_reg_live (reg);
431
  mark_reg_live (dreg);
432
  mark_reg_dead (reg);
433
  mark_reg_dead (dreg);
434
 
435
  return false;
436
}
437
 
438
/* Check and make if necessary conflicts for pseudo DREG of class
439
   DEF_CL of the current insn with input operand USE of class USE_CL.
440
   Advance the current program point before making the conflict if
441
   ADVANCE_P.  Return TRUE if we will need to advance the current
442
   program point.  */
443
static bool
444
check_and_make_def_use_conflict (rtx dreg, enum reg_class def_cl,
445
                                 int use, enum reg_class use_cl,
446
                                 bool advance_p)
447
{
448
  if (! reg_classes_intersect_p (def_cl, use_cl))
449
    return advance_p;
450
 
451
  advance_p = make_pseudo_conflict (recog_data.operand[use],
452
                                    use_cl, dreg, advance_p);
453
  /* Reload may end up swapping commutative operands, so you
454
     have to take both orderings into account.  The
455
     constraints for the two operands can be completely
456
     different.  (Indeed, if the constraints for the two
457
     operands are the same for all alternatives, there's no
458
     point marking them as commutative.)  */
459
  if (use < recog_data.n_operands - 1
460
      && recog_data.constraints[use][0] == '%')
461
    advance_p
462
      = make_pseudo_conflict (recog_data.operand[use + 1],
463
                              use_cl, dreg, advance_p);
464
  if (use >= 1
465
      && recog_data.constraints[use - 1][0] == '%')
466
    advance_p
467
      = make_pseudo_conflict (recog_data.operand[use - 1],
468
                              use_cl, dreg, advance_p);
469
  return advance_p;
470
}
471
 
472
/* Check and make if necessary conflicts for definition DEF of class
473
   DEF_CL of the current insn with input operands.  Process only
474
   constraints of alternative ALT.  */
475
static void
476
check_and_make_def_conflict (int alt, int def, enum reg_class def_cl)
477
{
478
  int use, use_match;
479
  ira_allocno_t a;
480
  enum reg_class use_cl, acl;
481
  bool advance_p;
482
  rtx dreg = recog_data.operand[def];
483
 
484
  if (def_cl == NO_REGS)
485
    return;
486
 
487
  if (GET_CODE (dreg) == SUBREG)
488
    dreg = SUBREG_REG (dreg);
489
 
490
  if (! REG_P (dreg) || REGNO (dreg) < FIRST_PSEUDO_REGISTER)
491
    return;
492
 
493
  a = ira_curr_regno_allocno_map[REGNO (dreg)];
494
  acl = ALLOCNO_COVER_CLASS (a);
495
  if (! reg_classes_intersect_p (acl, def_cl))
496
    return;
497
 
498
  advance_p = true;
499
 
500
  for (use = 0; use < recog_data.n_operands; use++)
501
    {
502
      int alt1;
503
 
504
      if (use == def || recog_data.operand_type[use] == OP_OUT)
505
        continue;
506
 
507
      if (recog_op_alt[use][alt].anything_ok)
508
        use_cl = ALL_REGS;
509
      else
510
        use_cl = recog_op_alt[use][alt].cl;
511
 
512
      /* If there's any alternative that allows USE to match DEF, do not
513
         record a conflict.  If that causes us to create an invalid
514
         instruction due to the earlyclobber, reload must fix it up.  */
515
      for (alt1 = 0; alt1 < recog_data.n_alternatives; alt1++)
516
        if (recog_op_alt[use][alt1].matches == def
517
            || (use < recog_data.n_operands - 1
518
                && recog_data.constraints[use][0] == '%'
519
                && recog_op_alt[use + 1][alt1].matches == def)
520
            || (use >= 1
521
                && recog_data.constraints[use - 1][0] == '%'
522
                && recog_op_alt[use - 1][alt1].matches == def))
523
          break;
524
 
525
      if (alt1 < recog_data.n_alternatives)
526
        continue;
527
 
528
      advance_p = check_and_make_def_use_conflict (dreg, def_cl, use,
529
                                                   use_cl, advance_p);
530
 
531
      if ((use_match = recog_op_alt[use][alt].matches) >= 0)
532
        {
533
          if (use_match == def)
534
            continue;
535
 
536
          if (recog_op_alt[use_match][alt].anything_ok)
537
            use_cl = ALL_REGS;
538
          else
539
            use_cl = recog_op_alt[use_match][alt].cl;
540
          advance_p = check_and_make_def_use_conflict (dreg, def_cl, use,
541
                                                       use_cl, advance_p);
542
        }
543
    }
544
}
545
 
546
/* Make conflicts of early clobber pseudo registers of the current
547
   insn with its inputs.  Avoid introducing unnecessary conflicts by
548
   checking classes of the constraints and pseudos because otherwise
549
   significant code degradation is possible for some targets.  */
550
static void
551
make_early_clobber_and_input_conflicts (void)
552
{
553
  int alt;
554
  int def, def_match;
555
  enum reg_class def_cl;
556
 
557
  for (alt = 0; alt < recog_data.n_alternatives; alt++)
558
    for (def = 0; def < recog_data.n_operands; def++)
559
      {
560
        def_cl = NO_REGS;
561
        if (recog_op_alt[def][alt].earlyclobber)
562
          {
563
            if (recog_op_alt[def][alt].anything_ok)
564
              def_cl = ALL_REGS;
565
            else
566
              def_cl = recog_op_alt[def][alt].cl;
567
            check_and_make_def_conflict (alt, def, def_cl);
568
          }
569
        if ((def_match = recog_op_alt[def][alt].matches) >= 0
570
            && (recog_op_alt[def_match][alt].earlyclobber
571
                || recog_op_alt[def][alt].earlyclobber))
572
          {
573
            if (recog_op_alt[def_match][alt].anything_ok)
574
              def_cl = ALL_REGS;
575
            else
576
              def_cl = recog_op_alt[def_match][alt].cl;
577
            check_and_make_def_conflict (alt, def, def_cl);
578
          }
579
      }
580
}
581
 
582
/* Mark early clobber hard registers of the current INSN as live (if
583
   LIVE_P) or dead.  Return true if there are such registers.  */
584
static bool
585
mark_hard_reg_early_clobbers (rtx insn, bool live_p)
586
{
587
  df_ref *def_rec;
588
  bool set_p = false;
589
 
590
  for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
591
    if (DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MUST_CLOBBER))
592
      {
593
        rtx dreg = DF_REF_REG (*def_rec);
594
 
595
        if (GET_CODE (dreg) == SUBREG)
596
          dreg = SUBREG_REG (dreg);
597
        if (! REG_P (dreg) || REGNO (dreg) >= FIRST_PSEUDO_REGISTER)
598
          continue;
599
 
600
        /* Hard register clobbers are believed to be early clobber
601
           because there is no way to say that non-operand hard
602
           register clobbers are not early ones.  */
603
        if (live_p)
604
          mark_ref_live (*def_rec);
605
        else
606
          mark_ref_dead (*def_rec);
607
        set_p = true;
608
      }
609
 
610
  return set_p;
611
}
612
 
613
/* Checks that CONSTRAINTS permits to use only one hard register.  If
614
   it is so, the function returns the class of the hard register.
615
   Otherwise it returns NO_REGS.  */
616
static enum reg_class
617
single_reg_class (const char *constraints, rtx op, rtx equiv_const)
618
{
619
  int ignore_p;
620
  enum reg_class cl, next_cl;
621
  int c;
622
 
623
  cl = NO_REGS;
624
  for (ignore_p = false;
625
       (c = *constraints);
626
       constraints += CONSTRAINT_LEN (c, constraints))
627
    if (c == '#')
628
      ignore_p = true;
629
    else if (c == ',')
630
      ignore_p = false;
631
    else if (! ignore_p)
632
      switch (c)
633
        {
634
        case ' ':
635
        case '\t':
636
        case '=':
637
        case '+':
638
        case '*':
639
        case '&':
640
        case '%':
641
        case '!':
642
        case '?':
643
          break;
644
        case 'i':
645
          if (CONSTANT_P (op)
646
              || (equiv_const != NULL_RTX && CONSTANT_P (equiv_const)))
647
            return NO_REGS;
648
          break;
649
 
650
        case 'n':
651
          if (CONST_INT_P (op)
652
              || (GET_CODE (op) == CONST_DOUBLE && GET_MODE (op) == VOIDmode)
653
              || (equiv_const != NULL_RTX
654
                  && (CONST_INT_P (equiv_const)
655
                      || (GET_CODE (equiv_const) == CONST_DOUBLE
656
                          && GET_MODE (equiv_const) == VOIDmode))))
657
            return NO_REGS;
658
          break;
659
 
660
        case 's':
661
          if ((CONSTANT_P (op) && !CONST_INT_P (op)
662
               && (GET_CODE (op) != CONST_DOUBLE || GET_MODE (op) != VOIDmode))
663
              || (equiv_const != NULL_RTX
664
                  && CONSTANT_P (equiv_const)
665
                  && !CONST_INT_P (equiv_const)
666
                  && (GET_CODE (equiv_const) != CONST_DOUBLE
667
                      || GET_MODE (equiv_const) != VOIDmode)))
668
            return NO_REGS;
669
          break;
670
 
671
        case 'I':
672
        case 'J':
673
        case 'K':
674
        case 'L':
675
        case 'M':
676
        case 'N':
677
        case 'O':
678
        case 'P':
679
          if ((CONST_INT_P (op)
680
               && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, constraints))
681
              || (equiv_const != NULL_RTX
682
                  && CONST_INT_P (equiv_const)
683
                  && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
684
                                                c, constraints)))
685
            return NO_REGS;
686
          break;
687
 
688
        case 'E':
689
        case 'F':
690
          if (GET_CODE (op) == CONST_DOUBLE
691
              || (GET_CODE (op) == CONST_VECTOR
692
                  && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT)
693
              || (equiv_const != NULL_RTX
694
                  && (GET_CODE (equiv_const) == CONST_DOUBLE
695
                      || (GET_CODE (equiv_const) == CONST_VECTOR
696
                          && (GET_MODE_CLASS (GET_MODE (equiv_const))
697
                              == MODE_VECTOR_FLOAT)))))
698
            return NO_REGS;
699
          break;
700
 
701
        case 'G':
702
        case 'H':
703
          if ((GET_CODE (op) == CONST_DOUBLE
704
               && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, constraints))
705
              || (equiv_const != NULL_RTX
706
                  && GET_CODE (equiv_const) == CONST_DOUBLE
707
                  && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const,
708
                                                       c, constraints)))
709
            return NO_REGS;
710
          /* ??? what about memory */
711
        case 'r':
712
        case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
713
        case 'h': case 'j': case 'k': case 'l':
714
        case 'q': case 't': case 'u':
715
        case 'v': case 'w': case 'x': case 'y': case 'z':
716
        case 'A': case 'B': case 'C': case 'D':
717
        case 'Q': case 'R': case 'S': case 'T': case 'U':
718
        case 'W': case 'Y': case 'Z':
719
          next_cl = (c == 'r'
720
                     ? GENERAL_REGS
721
                     : REG_CLASS_FROM_CONSTRAINT (c, constraints));
722
          if ((cl != NO_REGS && next_cl != cl)
723
              || (ira_available_class_regs[next_cl]
724
                  > ira_reg_class_nregs[next_cl][GET_MODE (op)]))
725
            return NO_REGS;
726
          cl = next_cl;
727
          break;
728
 
729
        case '0': case '1': case '2': case '3': case '4':
730
        case '5': case '6': case '7': case '8': case '9':
731
          next_cl
732
            = single_reg_class (recog_data.constraints[c - '0'],
733
                                recog_data.operand[c - '0'], NULL_RTX);
734
          if ((cl != NO_REGS && next_cl != cl)
735
              || next_cl == NO_REGS
736
              || (ira_available_class_regs[next_cl]
737
                  > ira_reg_class_nregs[next_cl][GET_MODE (op)]))
738
            return NO_REGS;
739
          cl = next_cl;
740
          break;
741
 
742
        default:
743
          return NO_REGS;
744
        }
745
  return cl;
746
}
747
 
748
/* The function checks that operand OP_NUM of the current insn can use
749
   only one hard register.  If it is so, the function returns the
750
   class of the hard register.  Otherwise it returns NO_REGS.  */
751
static enum reg_class
752
single_reg_operand_class (int op_num)
753
{
754
  if (op_num < 0 || recog_data.n_alternatives == 0)
755
    return NO_REGS;
756
  return single_reg_class (recog_data.constraints[op_num],
757
                           recog_data.operand[op_num], NULL_RTX);
758
}
759
 
760
/* The function sets up hard register set *SET to hard registers which
761
   might be used by insn reloads because the constraints are too
762
   strict.  */
763
void
764
ira_implicitly_set_insn_hard_regs (HARD_REG_SET *set)
765
{
766
  int i, c, regno = 0;
767
  bool ignore_p;
768
  enum reg_class cl;
769
  rtx op;
770
  enum machine_mode mode;
771
 
772
  CLEAR_HARD_REG_SET (*set);
773
  for (i = 0; i < recog_data.n_operands; i++)
774
    {
775
      op = recog_data.operand[i];
776
 
777
      if (GET_CODE (op) == SUBREG)
778
        op = SUBREG_REG (op);
779
 
780
      if (GET_CODE (op) == SCRATCH
781
          || (REG_P (op) && (regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER))
782
        {
783
          const char *p = recog_data.constraints[i];
784
 
785
          mode = (GET_CODE (op) == SCRATCH
786
                  ? GET_MODE (op) : PSEUDO_REGNO_MODE (regno));
787
          cl = NO_REGS;
788
          for (ignore_p = false; (c = *p); p += CONSTRAINT_LEN (c, p))
789
            if (c == '#')
790
              ignore_p = true;
791
            else if (c == ',')
792
              ignore_p = false;
793
            else if (! ignore_p)
794
              switch (c)
795
                {
796
                case 'r':
797
                case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
798
                case 'h': case 'j': case 'k': case 'l':
799
                case 'q': case 't': case 'u':
800
                case 'v': case 'w': case 'x': case 'y': case 'z':
801
                case 'A': case 'B': case 'C': case 'D':
802
                case 'Q': case 'R': case 'S': case 'T': case 'U':
803
                case 'W': case 'Y': case 'Z':
804
                  cl = (c == 'r'
805
                        ? GENERAL_REGS
806
                        : REG_CLASS_FROM_CONSTRAINT (c, p));
807
                  if (cl != NO_REGS
808
                      && (ira_available_class_regs[cl]
809
                          <= ira_reg_class_nregs[cl][mode]))
810
                    IOR_HARD_REG_SET (*set, reg_class_contents[cl]);
811
                  break;
812
                }
813
        }
814
    }
815
}
816
/* Processes input operands, if IN_P, or output operands otherwise of
817
   the current insn with FREQ to find allocno which can use only one
818
   hard register and makes other currently living allocnos conflicting
819
   with the hard register.  */
820
static void
821
process_single_reg_class_operands (bool in_p, int freq)
822
{
823
  int i, regno, cost;
824
  unsigned int px;
825
  enum reg_class cl;
826
  rtx operand;
827
  ira_allocno_t operand_a, a;
828
 
829
  for (i = 0; i < recog_data.n_operands; i++)
830
    {
831
      operand = recog_data.operand[i];
832
      if (in_p && recog_data.operand_type[i] != OP_IN
833
          && recog_data.operand_type[i] != OP_INOUT)
834
        continue;
835
      if (! in_p && recog_data.operand_type[i] != OP_OUT
836
          && recog_data.operand_type[i] != OP_INOUT)
837
        continue;
838
      cl = single_reg_operand_class (i);
839
      if (cl == NO_REGS)
840
        continue;
841
 
842
      operand_a = NULL;
843
 
844
      if (GET_CODE (operand) == SUBREG)
845
        operand = SUBREG_REG (operand);
846
 
847
      if (REG_P (operand)
848
          && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
849
        {
850
          enum machine_mode mode;
851
          enum reg_class cover_class;
852
 
853
          operand_a = ira_curr_regno_allocno_map[regno];
854
          mode = ALLOCNO_MODE (operand_a);
855
          cover_class = ALLOCNO_COVER_CLASS (operand_a);
856
          if (ira_class_subset_p[cl][cover_class]
857
              && ira_class_hard_regs_num[cl] != 0
858
              && (ira_class_hard_reg_index[cover_class]
859
                  [ira_class_hard_regs[cl][0]]) >= 0
860
              && reg_class_size[cl] <= (unsigned) CLASS_MAX_NREGS (cl, mode))
861
            {
862
              int i, size;
863
              cost
864
                = (freq
865
                   * (in_p
866
                      ? ira_get_register_move_cost (mode, cover_class, cl)
867
                      : ira_get_register_move_cost (mode, cl, cover_class)));
868
              ira_allocate_and_set_costs
869
                (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), cover_class, 0);
870
              size = ira_reg_class_nregs[cover_class][mode];
871
              for (i = 0; i < size; i++)
872
                ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
873
                  [ira_class_hard_reg_index
874
                   [cover_class][ira_class_hard_regs[cl][i]]]
875
                  -= cost;
876
            }
877
        }
878
 
879
      EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
880
        {
881
          a = ira_allocnos[px];
882
          if (a != operand_a)
883
            {
884
              /* We could increase costs of A instead of making it
885
                 conflicting with the hard register.  But it works worse
886
                 because it will be spilled in reload in anyway.  */
887
              IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
888
                                reg_class_contents[cl]);
889
              IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
890
                                reg_class_contents[cl]);
891
            }
892
        }
893
    }
894
}
895
 
896
/* Return true when one of the predecessor edges of BB is marked with
897
   EDGE_ABNORMAL_CALL or EDGE_EH.  */
898
static bool
899
bb_has_abnormal_call_pred (basic_block bb)
900
{
901
  edge e;
902
  edge_iterator ei;
903
 
904
  FOR_EACH_EDGE (e, ei, bb->preds)
905
    {
906
      if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
907
        return true;
908
    }
909
  return false;
910
}
911
 
912
/* Process insns of the basic block given by its LOOP_TREE_NODE to
913
   update allocno live ranges, allocno hard register conflicts,
914
   intersected calls, and register pressure info for allocnos for the
915
   basic block for and regions containing the basic block.  */
916
static void
917
process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
918
{
919
  int i, freq;
920
  unsigned int j;
921
  basic_block bb;
922
  rtx insn;
923
  bitmap_iterator bi;
924
  bitmap reg_live_out;
925
  unsigned int px;
926
  bool set_p;
927
 
928
  bb = loop_tree_node->bb;
929
  if (bb != NULL)
930
    {
931
      for (i = 0; i < ira_reg_class_cover_size; i++)
932
        {
933
          curr_reg_pressure[ira_reg_class_cover[i]] = 0;
934
          high_pressure_start_point[ira_reg_class_cover[i]] = -1;
935
        }
936
      curr_bb_node = loop_tree_node;
937
      reg_live_out = DF_LR_OUT (bb);
938
      sparseset_clear (allocnos_live);
939
      REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
940
      AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
941
      AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
942
      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
943
        if (TEST_HARD_REG_BIT (hard_regs_live, i))
944
          {
945
            enum reg_class cover_class, cl;
946
 
947
            cover_class = ira_class_translate[REGNO_REG_CLASS (i)];
948
            for (j = 0;
949
                 (cl = ira_reg_class_super_classes[cover_class][j])
950
                   != LIM_REG_CLASSES;
951
                 j++)
952
              {
953
                curr_reg_pressure[cl]++;
954
                if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
955
                  curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
956
                ira_assert (curr_reg_pressure[cl]
957
                            <= ira_available_class_regs[cl]);
958
              }
959
          }
960
      EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
961
        {
962
          ira_allocno_t a = ira_curr_regno_allocno_map[j];
963
 
964
          if (a == NULL)
965
            continue;
966
          ira_assert (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)));
967
          set_allocno_live (a);
968
          make_regno_born (j);
969
        }
970
 
971
      freq = REG_FREQ_FROM_BB (bb);
972
      if (freq == 0)
973
        freq = 1;
974
 
975
      /* Invalidate all allocno_saved_at_call entries.  */
976
      last_call_num++;
977
 
978
      /* Scan the code of this basic block, noting which allocnos and
979
         hard regs are born or die.
980
 
981
         Note that this loop treats uninitialized values as live until
982
         the beginning of the block.  For example, if an instruction
983
         uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
984
         set, FOO will remain live until the beginning of the block.
985
         Likewise if FOO is not set at all.  This is unnecessarily
986
         pessimistic, but it probably doesn't matter much in practice.  */
987
      FOR_BB_INSNS_REVERSE (bb, insn)
988
        {
989
          df_ref *def_rec, *use_rec;
990
          bool call_p;
991
 
992
          if (!NONDEBUG_INSN_P (insn))
993
            continue;
994
 
995
          if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
996
            fprintf (ira_dump_file, "   Insn %u(l%d): point = %d\n",
997
                     INSN_UID (insn), loop_tree_node->parent->loop->num,
998
                     curr_point);
999
 
1000
          /* Mark each defined value as live.  We need to do this for
1001
             unused values because they still conflict with quantities
1002
             that are live at the time of the definition.
1003
 
1004
             Ignore DF_REF_MAY_CLOBBERs on a call instruction.  Such
1005
             references represent the effect of the called function
1006
             on a call-clobbered register.  Marking the register as
1007
             live would stop us from allocating it to a call-crossing
1008
             allocno.  */
1009
          call_p = CALL_P (insn);
1010
          for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1011
            if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1012
              mark_ref_live (*def_rec);
1013
 
1014
          /* If INSN has multiple outputs, then any value used in one
1015
             of the outputs conflicts with the other outputs.  Model this
1016
             by making the used value live during the output phase.
1017
 
1018
             It is unsafe to use !single_set here since it will ignore
1019
             an unused output.  Just because an output is unused does
1020
             not mean the compiler can assume the side effect will not
1021
             occur.  Consider if ALLOCNO appears in the address of an
1022
             output and we reload the output.  If we allocate ALLOCNO
1023
             to the same hard register as an unused output we could
1024
             set the hard register before the output reload insn.  */
1025
          if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1026
            for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1027
              {
1028
                int i;
1029
                rtx reg;
1030
 
1031
                reg = DF_REF_REG (*use_rec);
1032
                for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1033
                  {
1034
                    rtx set;
1035
 
1036
                    set = XVECEXP (PATTERN (insn), 0, i);
1037
                    if (GET_CODE (set) == SET
1038
                        && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1039
                      {
1040
                        /* After the previous loop, this is a no-op if
1041
                           REG is contained within SET_DEST (SET).  */
1042
                        mark_ref_live (*use_rec);
1043
                        break;
1044
                      }
1045
                  }
1046
              }
1047
 
1048
          extract_insn (insn);
1049
          preprocess_constraints ();
1050
          process_single_reg_class_operands (false, freq);
1051
 
1052
          /* See which defined values die here.  */
1053
          for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1054
            if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1055
              mark_ref_dead (*def_rec);
1056
 
1057
          if (call_p)
1058
            {
1059
              last_call_num++;
1060
              /* The current set of live allocnos are live across the call.  */
1061
              EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1062
                {
1063
                  ira_allocno_t a = ira_allocnos[i];
1064
 
1065
                  if (allocno_saved_at_call[i] != last_call_num)
1066
                    /* Here we are mimicking caller-save.c behaviour
1067
                       which does not save hard register at a call if
1068
                       it was saved on previous call in the same basic
1069
                       block and the hard register was not mentioned
1070
                       between the two calls.  */
1071
                    ALLOCNO_CALL_FREQ (a) += freq;
1072
                  /* Mark it as saved at the next call.  */
1073
                  allocno_saved_at_call[i] = last_call_num + 1;
1074
                  ALLOCNO_CALLS_CROSSED_NUM (a)++;
1075
                  /* Don't allocate allocnos that cross setjmps or any
1076
                     call, if this function receives a nonlocal
1077
                     goto.  */
1078
                  if (cfun->has_nonlocal_label
1079
                      || find_reg_note (insn, REG_SETJMP,
1080
                                        NULL_RTX) != NULL_RTX)
1081
                    {
1082
                      SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a));
1083
                      SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1084
                    }
1085
                  if (can_throw_internal (insn))
1086
                    {
1087
                      IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
1088
                                        call_used_reg_set);
1089
                      IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
1090
                                        call_used_reg_set);
1091
                    }
1092
                }
1093
            }
1094
 
1095
          make_early_clobber_and_input_conflicts ();
1096
 
1097
          curr_point++;
1098
 
1099
          /* Mark each used value as live.  */
1100
          for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1101
            mark_ref_live (*use_rec);
1102
 
1103
          process_single_reg_class_operands (true, freq);
1104
 
1105
          set_p = mark_hard_reg_early_clobbers (insn, true);
1106
 
1107
          if (set_p)
1108
            {
1109
              mark_hard_reg_early_clobbers (insn, false);
1110
 
1111
              /* Mark each hard reg as live again.  For example, a
1112
                 hard register can be in clobber and in an insn
1113
                 input.  */
1114
              for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1115
                {
1116
                  rtx ureg = DF_REF_REG (*use_rec);
1117
 
1118
                  if (GET_CODE (ureg) == SUBREG)
1119
                    ureg = SUBREG_REG (ureg);
1120
                  if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1121
                    continue;
1122
 
1123
                  mark_ref_live (*use_rec);
1124
                }
1125
            }
1126
 
1127
          curr_point++;
1128
        }
1129
 
1130
#ifdef EH_RETURN_DATA_REGNO
1131
      if (bb_has_eh_pred (bb))
1132
        for (j = 0; ; ++j)
1133
          {
1134
            unsigned int regno = EH_RETURN_DATA_REGNO (j);
1135
            if (regno == INVALID_REGNUM)
1136
              break;
1137
            make_regno_born (regno);
1138
          }
1139
#endif
1140
 
1141
      /* Allocnos can't go in stack regs at the start of a basic block
1142
         that is reached by an abnormal edge. Likewise for call
1143
         clobbered regs, because caller-save, fixup_abnormal_edges and
1144
         possibly the table driven EH machinery are not quite ready to
1145
         handle such allocnos live across such edges.  */
1146
      if (bb_has_abnormal_pred (bb))
1147
        {
1148
#ifdef STACK_REGS
1149
          EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
1150
            {
1151
              ALLOCNO_NO_STACK_REG_P (ira_allocnos[px]) = true;
1152
              ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos[px]) = true;
1153
            }
1154
          for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1155
            make_regno_born (px);
1156
#endif
1157
          /* No need to record conflicts for call clobbered regs if we
1158
             have nonlocal labels around, as we don't ever try to
1159
             allocate such regs in this case.  */
1160
          if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
1161
            for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1162
              if (call_used_regs[px])
1163
                make_regno_born (px);
1164
        }
1165
 
1166
      EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1167
        {
1168
          make_regno_dead (ALLOCNO_REGNO (ira_allocnos[i]));
1169
        }
1170
 
1171
      curr_point++;
1172
 
1173
    }
1174
  /* Propagate register pressure to upper loop tree nodes: */
1175
  if (loop_tree_node != ira_loop_tree_root)
1176
    for (i = 0; i < ira_reg_class_cover_size; i++)
1177
      {
1178
        enum reg_class cover_class;
1179
 
1180
        cover_class = ira_reg_class_cover[i];
1181
        if (loop_tree_node->reg_pressure[cover_class]
1182
            > loop_tree_node->parent->reg_pressure[cover_class])
1183
          loop_tree_node->parent->reg_pressure[cover_class]
1184
            = loop_tree_node->reg_pressure[cover_class];
1185
      }
1186
}
1187
 
1188
/* Create and set up IRA_START_POINT_RANGES and
1189
   IRA_FINISH_POINT_RANGES.  */
1190
static void
1191
create_start_finish_chains (void)
1192
{
1193
  ira_allocno_t a;
1194
  ira_allocno_iterator ai;
1195
  allocno_live_range_t r;
1196
 
1197
  ira_start_point_ranges
1198
    = (allocno_live_range_t *) ira_allocate (ira_max_point
1199
                                             * sizeof (allocno_live_range_t));
1200
  memset (ira_start_point_ranges, 0,
1201
          ira_max_point * sizeof (allocno_live_range_t));
1202
  ira_finish_point_ranges
1203
    = (allocno_live_range_t *) ira_allocate (ira_max_point
1204
                                             * sizeof (allocno_live_range_t));
1205
  memset (ira_finish_point_ranges, 0,
1206
          ira_max_point * sizeof (allocno_live_range_t));
1207
  FOR_EACH_ALLOCNO (a, ai)
1208
    {
1209
      for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1210
        {
1211
          r->start_next = ira_start_point_ranges[r->start];
1212
          ira_start_point_ranges[r->start] = r;
1213
          r->finish_next = ira_finish_point_ranges[r->finish];
1214
          ira_finish_point_ranges[r->finish] = r;
1215
        }
1216
    }
1217
}
1218
 
1219
/* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1220
   new live ranges and program points were added as a result if new
1221
   insn generation.  */
1222
void
1223
ira_rebuild_start_finish_chains (void)
1224
{
1225
  ira_free (ira_finish_point_ranges);
1226
  ira_free (ira_start_point_ranges);
1227
  create_start_finish_chains ();
1228
}
1229
 
1230
/* Compress allocno live ranges by removing program points where
1231
   nothing happens.  */
1232
static void
1233
remove_some_program_points_and_update_live_ranges (void)
1234
{
1235
  unsigned i;
1236
  int n;
1237
  int *map;
1238
  ira_allocno_t a;
1239
  ira_allocno_iterator ai;
1240
  allocno_live_range_t r;
1241
  bitmap born_or_died;
1242
  bitmap_iterator bi;
1243
 
1244
  born_or_died = ira_allocate_bitmap ();
1245
  FOR_EACH_ALLOCNO (a, ai)
1246
    {
1247
      for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1248
        {
1249
          ira_assert (r->start <= r->finish);
1250
          bitmap_set_bit (born_or_died, r->start);
1251
          bitmap_set_bit (born_or_died, r->finish);
1252
        }
1253
    }
1254
  map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1255
  n = 0;
1256
  EXECUTE_IF_SET_IN_BITMAP(born_or_died, 0, i, bi)
1257
    {
1258
      map[i] = n++;
1259
    }
1260
  ira_free_bitmap (born_or_died);
1261
  if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1262
    fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1263
             ira_max_point, n, 100 * n / ira_max_point);
1264
  ira_max_point = n;
1265
  FOR_EACH_ALLOCNO (a, ai)
1266
    {
1267
      for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1268
        {
1269
          r->start = map[r->start];
1270
          r->finish = map[r->finish];
1271
        }
1272
    }
1273
  ira_free (map);
1274
}
1275
 
1276
/* Print live ranges R to file F.  */
1277
void
1278
ira_print_live_range_list (FILE *f, allocno_live_range_t r)
1279
{
1280
  for (; r != NULL; r = r->next)
1281
    fprintf (f, " [%d..%d]", r->start, r->finish);
1282
  fprintf (f, "\n");
1283
}
1284
 
1285
/* Print live ranges R to stderr.  */
1286
void
1287
ira_debug_live_range_list (allocno_live_range_t r)
1288
{
1289
  ira_print_live_range_list (stderr, r);
1290
}
1291
 
1292
/* Print live ranges of allocno A to file F.  */
1293
static void
1294
print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1295
{
1296
  fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1297
  ira_print_live_range_list (f, ALLOCNO_LIVE_RANGES (a));
1298
}
1299
 
1300
/* Print live ranges of allocno A to stderr.  */
1301
void
1302
ira_debug_allocno_live_ranges (ira_allocno_t a)
1303
{
1304
  print_allocno_live_ranges (stderr, a);
1305
}
1306
 
1307
/* Print live ranges of all allocnos to file F.  */
1308
static void
1309
print_live_ranges (FILE *f)
1310
{
1311
  ira_allocno_t a;
1312
  ira_allocno_iterator ai;
1313
 
1314
  FOR_EACH_ALLOCNO (a, ai)
1315
    print_allocno_live_ranges (f, a);
1316
}
1317
 
1318
/* Print live ranges of all allocnos to stderr.  */
1319
void
1320
ira_debug_live_ranges (void)
1321
{
1322
  print_live_ranges (stderr);
1323
}
1324
 
1325
/* The main entry function creates live ranges, set up
1326
   CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
1327
   calculate register pressure info.  */
1328
void
1329
ira_create_allocno_live_ranges (void)
1330
{
1331
  allocnos_live = sparseset_alloc (ira_allocnos_num);
1332
  curr_point = 0;
1333
  last_call_num = 0;
1334
  allocno_saved_at_call
1335
    = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1336
  memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
1337
  ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1338
                          process_bb_node_lives);
1339
  ira_max_point = curr_point;
1340
  create_start_finish_chains ();
1341
  if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1342
    print_live_ranges (ira_dump_file);
1343
  /* Clean up.  */
1344
  ira_free (allocno_saved_at_call);
1345
  sparseset_free (allocnos_live);
1346
}
1347
 
1348
/* Compress allocno live ranges.  */
1349
void
1350
ira_compress_allocno_live_ranges (void)
1351
{
1352
  remove_some_program_points_and_update_live_ranges ();
1353
  ira_rebuild_start_finish_chains ();
1354
  if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1355
    {
1356
      fprintf (ira_dump_file, "Ranges after the compression:\n");
1357
      print_live_ranges (ira_dump_file);
1358
    }
1359
}
1360
 
1361
/* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES.  */
1362
void
1363
ira_finish_allocno_live_ranges (void)
1364
{
1365
  ira_free (ira_finish_point_ranges);
1366
  ira_free (ira_start_point_ranges);
1367
}

powered by: WebSVN 2.1.0

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