gcc/ira-lives.c

   1 /* 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                       /* There is no register pressure problem if all of the
 809                          regs in this class are fixed.  */
 810                       && ira_available_class_regs[cl] != 0
 811                       && (ira_available_class_regs[cl]
 812                           <= ira_reg_class_nregs[cl][mode]))
 813                     IOR_HARD_REG_SET (*set, reg_class_contents[cl]);
 814                   break;
 815                 }
 816         }
 817     }
 818 }
 819 /* Processes input operands, if IN_P, or output operands otherwise of
 820    the current insn with FREQ to find allocno which can use only one
 821    hard register and makes other currently living allocnos conflicting
 822    with the hard register.  */
 823 static void
 824 process_single_reg_class_operands (bool in_p, int freq)
 825 {
 826   int i, regno, cost;
 827   unsigned int px;
 828   enum reg_class cl;
 829   rtx operand;
 830   ira_allocno_t operand_a, a;
 831
 832   for (i = 0; i < recog_data.n_operands; i++)
 833     {
 834       operand = recog_data.operand[i];
 835       if (in_p && recog_data.operand_type[i] != OP_IN
 836           && recog_data.operand_type[i] != OP_INOUT)
 837         continue;
 838       if (! in_p && recog_data.operand_type[i] != OP_OUT
 839           && recog_data.operand_type[i] != OP_INOUT)
 840         continue;
 841       cl = single_reg_operand_class (i);
 842       if (cl == NO_REGS)
 843         continue;
 844
 845       operand_a = NULL;
 846
 847       if (GET_CODE (operand) == SUBREG)
 848         operand = SUBREG_REG (operand);
 849
 850       if (REG_P (operand)
 851           && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
 852         {
 853           enum machine_mode mode;
 854           enum reg_class cover_class;
 855
 856           operand_a = ira_curr_regno_allocno_map[regno];
 857           mode = ALLOCNO_MODE (operand_a);
 858           cover_class = ALLOCNO_COVER_CLASS (operand_a);
 859           if (ira_class_subset_p[cl][cover_class]
 860               && ira_class_hard_regs_num[cl] != 0
 861               && (ira_class_hard_reg_index[cover_class]
 862                   [ira_class_hard_regs[cl][0]]) >= 0
 863               && reg_class_size[cl] <= (unsigned) CLASS_MAX_NREGS (cl, mode))
 864             {
 865               int i, size;
 866               cost
 867                 = (freq
 868                    * (in_p
 869                       ? ira_get_register_move_cost (mode, cover_class, cl)
 870                       : ira_get_register_move_cost (mode, cl, cover_class)));
 871               ira_allocate_and_set_costs
 872                 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), cover_class, 0);
 873               size = ira_reg_class_nregs[cover_class][mode];
 874               for (i = 0; i < size; i++)
 875                 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
 876                   [ira_class_hard_reg_index
 877                    [cover_class][ira_class_hard_regs[cl][i]]]
 878                   -= cost;
 879             }
 880         }
 881
 882       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
 883         {
 884           a = ira_allocnos[px];
 885           if (a != operand_a)
 886             {
 887               /* We could increase costs of A instead of making it
 888                  conflicting with the hard register.  But it works worse
 889                  because it will be spilled in reload in anyway.  */
 890               IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 891                                 reg_class_contents[cl]);
 892               IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 893                                 reg_class_contents[cl]);
 894             }
 895         }
 896     }
 897 }
 898
 899 /* Return true when one of the predecessor edges of BB is marked with
 900    EDGE_ABNORMAL_CALL or EDGE_EH.  */
 901 static bool
 902 bb_has_abnormal_call_pred (basic_block bb)
 903 {
 904   edge e;
 905   edge_iterator ei;
 906
 907   FOR_EACH_EDGE (e, ei, bb->preds)
 908     {
 909       if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
 910         return true;
 911     }
 912   return false;
 913 }
 914
 915 /* Process insns of the basic block given by its LOOP_TREE_NODE to
 916    update allocno live ranges, allocno hard register conflicts,
 917    intersected calls, and register pressure info for allocnos for the
 918    basic block for and regions containing the basic block.  */
 919 static void
 920 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
 921 {
 922   int i, freq;
 923   unsigned int j;
 924   basic_block bb;
 925   rtx insn;
 926   bitmap_iterator bi;
 927   bitmap reg_live_out;
 928   unsigned int px;
 929   bool set_p;
 930
 931   bb = loop_tree_node->bb;
 932   if (bb != NULL)
 933     {
 934       for (i = 0; i < ira_reg_class_cover_size; i++)
 935         {
 936           curr_reg_pressure[ira_reg_class_cover[i]] = 0;
 937           high_pressure_start_point[ira_reg_class_cover[i]] = -1;
 938         }
 939       curr_bb_node = loop_tree_node;
 940       reg_live_out = DF_LR_OUT (bb);
 941       sparseset_clear (allocnos_live);
 942       REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
 943       AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
 944       AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
 945       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 946         if (TEST_HARD_REG_BIT (hard_regs_live, i))
 947           {
 948             enum reg_class cover_class, cl;
 949
 950             cover_class = ira_class_translate[REGNO_REG_CLASS (i)];
 951             for (j = 0;
 952                  (cl = ira_reg_class_super_classes[cover_class][j])
 953                    != LIM_REG_CLASSES;
 954                  j++)
 955               {
 956                 curr_reg_pressure[cl]++;
 957                 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
 958                   curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
 959                 ira_assert (curr_reg_pressure[cl]
 960                             <= ira_available_class_regs[cl]);
 961               }
 962           }
 963       EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
 964         {
 965           ira_allocno_t a = ira_curr_regno_allocno_map[j];
 966
 967           if (a == NULL)
 968             continue;
 969           ira_assert (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)));
 970           set_allocno_live (a);
 971           make_regno_born (j);
 972         }
 973
 974       freq = REG_FREQ_FROM_BB (bb);
 975       if (freq == 0)
 976         freq = 1;
 977
 978       /* Invalidate all allocno_saved_at_call entries.  */
 979       last_call_num++;
 980
 981       /* Scan the code of this basic block, noting which allocnos and
 982          hard regs are born or die.
 983
 984          Note that this loop treats uninitialized values as live until
 985          the beginning of the block.  For example, if an instruction
 986          uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
 987          set, FOO will remain live until the beginning of the block.
 988          Likewise if FOO is not set at all.  This is unnecessarily
 989          pessimistic, but it probably doesn't matter much in practice.  */
 990       FOR_BB_INSNS_REVERSE (bb, insn)
 991         {
 992           df_ref *def_rec, *use_rec;
 993           bool call_p;
 994
 995           if (!NONDEBUG_INSN_P (insn))
 996             continue;
 997
 998           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 999             fprintf (ira_dump_file, "   Insn %u(l%d): point = %d\n",
1000                      INSN_UID (insn), loop_tree_node->parent->loop->num,
1001                      curr_point);
1002
1003           /* Mark each defined value as live.  We need to do this for
1004              unused values because they still conflict with quantities
1005              that are live at the time of the definition.
1006
1007              Ignore DF_REF_MAY_CLOBBERs on a call instruction.  Such
1008              references represent the effect of the called function
1009              on a call-clobbered register.  Marking the register as
1010              live would stop us from allocating it to a call-crossing
1011              allocno.  */
1012           call_p = CALL_P (insn);
1013           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1014             if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1015               mark_ref_live (*def_rec);
1016
1017           /* If INSN has multiple outputs, then any value used in one
1018              of the outputs conflicts with the other outputs.  Model this
1019              by making the used value live during the output phase.
1020
1021              It is unsafe to use !single_set here since it will ignore
1022              an unused output.  Just because an output is unused does
1023              not mean the compiler can assume the side effect will not
1024              occur.  Consider if ALLOCNO appears in the address of an
1025              output and we reload the output.  If we allocate ALLOCNO
1026              to the same hard register as an unused output we could
1027              set the hard register before the output reload insn.  */
1028           if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1029             for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1030               {
1031                 int i;
1032                 rtx reg;
1033
1034                 reg = DF_REF_REG (*use_rec);
1035                 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1036                   {
1037                     rtx set;
1038
1039                     set = XVECEXP (PATTERN (insn), 0, i);
1040                     if (GET_CODE (set) == SET
1041                         && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1042                       {
1043                         /* After the previous loop, this is a no-op if
1044                            REG is contained within SET_DEST (SET).  */
1045                         mark_ref_live (*use_rec);
1046                         break;
1047                       }
1048                   }
1049               }
1050
1051           extract_insn (insn);
1052           preprocess_constraints ();
1053           process_single_reg_class_operands (false, freq);
1054
1055           /* See which defined values die here.  */
1056           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1057             if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1058               mark_ref_dead (*def_rec);
1059
1060           if (call_p)
1061             {
1062               last_call_num++;
1063               /* The current set of live allocnos are live across the call.  */
1064               EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1065                 {
1066                   ira_allocno_t a = ira_allocnos[i];
1067
1068                   if (allocno_saved_at_call[i] != last_call_num)
1069                     /* Here we are mimicking caller-save.c behaviour
1070                        which does not save hard register at a call if
1071                        it was saved on previous call in the same basic
1072                        block and the hard register was not mentioned
1073                        between the two calls.  */
1074                     ALLOCNO_CALL_FREQ (a) += freq;
1075                   /* Mark it as saved at the next call.  */
1076                   allocno_saved_at_call[i] = last_call_num + 1;
1077                   ALLOCNO_CALLS_CROSSED_NUM (a)++;
1078                   /* Don't allocate allocnos that cross setjmps or any
1079                      call, if this function receives a nonlocal
1080                      goto.  */
1081                   if (cfun->has_nonlocal_label
1082                       || find_reg_note (insn, REG_SETJMP,
1083                                         NULL_RTX) != NULL_RTX)
1084                     {
1085                       SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a));
1086                       SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1087                     }
1088                   if (can_throw_internal (insn))
1089                     {
1090                       IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
1091                                         call_used_reg_set);
1092                       IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
1093                                         call_used_reg_set);
1094                     }
1095                 }
1096             }
1097
1098           make_early_clobber_and_input_conflicts ();
1099
1100           curr_point++;
1101
1102           /* Mark each used value as live.  */
1103           for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1104             mark_ref_live (*use_rec);
1105
1106           process_single_reg_class_operands (true, freq);
1107
1108           set_p = mark_hard_reg_early_clobbers (insn, true);
1109
1110           if (set_p)
1111             {
1112               mark_hard_reg_early_clobbers (insn, false);
1113
1114               /* Mark each hard reg as live again.  For example, a
1115                  hard register can be in clobber and in an insn
1116                  input.  */
1117               for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1118                 {
1119                   rtx ureg = DF_REF_REG (*use_rec);
1120
1121                   if (GET_CODE (ureg) == SUBREG)
1122                     ureg = SUBREG_REG (ureg);
1123                   if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1124                     continue;
1125
1126                   mark_ref_live (*use_rec);
1127                 }
1128             }
1129
1130           curr_point++;
1131         }
1132
1133 #ifdef EH_RETURN_DATA_REGNO
1134       if (bb_has_eh_pred (bb))
1135         for (j = 0; ; ++j)
1136           {
1137             unsigned int regno = EH_RETURN_DATA_REGNO (j);
1138             if (regno == INVALID_REGNUM)
1139               break;
1140             make_regno_born (regno);
1141           }
1142 #endif
1143
1144       /* Allocnos can't go in stack regs at the start of a basic block
1145          that is reached by an abnormal edge. Likewise for call
1146          clobbered regs, because caller-save, fixup_abnormal_edges and
1147          possibly the table driven EH machinery are not quite ready to
1148          handle such allocnos live across such edges.  */
1149       if (bb_has_abnormal_pred (bb))
1150         {
1151 #ifdef STACK_REGS
1152           EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
1153             {
1154               ALLOCNO_NO_STACK_REG_P (ira_allocnos[px]) = true;
1155               ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos[px]) = true;
1156             }
1157           for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1158             make_regno_born (px);
1159 #endif
1160           /* No need to record conflicts for call clobbered regs if we
1161              have nonlocal labels around, as we don't ever try to
1162              allocate such regs in this case.  */
1163           if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
1164             for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1165               if (call_used_regs[px])
1166                 make_regno_born (px);
1167         }
1168
1169       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1170         {
1171           make_regno_dead (ALLOCNO_REGNO (ira_allocnos[i]));
1172         }
1173
1174       curr_point++;
1175
1176     }
1177   /* Propagate register pressure to upper loop tree nodes: */
1178   if (loop_tree_node != ira_loop_tree_root)
1179     for (i = 0; i < ira_reg_class_cover_size; i++)
1180       {
1181         enum reg_class cover_class;
1182
1183         cover_class = ira_reg_class_cover[i];
1184         if (loop_tree_node->reg_pressure[cover_class]
1185             > loop_tree_node->parent->reg_pressure[cover_class])
1186           loop_tree_node->parent->reg_pressure[cover_class]
1187             = loop_tree_node->reg_pressure[cover_class];
1188       }
1189 }
1190
1191 /* Create and set up IRA_START_POINT_RANGES and
1192    IRA_FINISH_POINT_RANGES.  */
1193 static void
1194 create_start_finish_chains (void)
1195 {
1196   ira_allocno_t a;
1197   ira_allocno_iterator ai;
1198   allocno_live_range_t r;
1199
1200   ira_start_point_ranges
1201     = (allocno_live_range_t *) ira_allocate (ira_max_point
1202                                              * sizeof (allocno_live_range_t));
1203   memset (ira_start_point_ranges, 0,
1204           ira_max_point * sizeof (allocno_live_range_t));
1205   ira_finish_point_ranges
1206     = (allocno_live_range_t *) ira_allocate (ira_max_point
1207                                              * sizeof (allocno_live_range_t));
1208   memset (ira_finish_point_ranges, 0,
1209           ira_max_point * sizeof (allocno_live_range_t));
1210   FOR_EACH_ALLOCNO (a, ai)
1211     {
1212       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1213         {
1214           r->start_next = ira_start_point_ranges[r->start];
1215           ira_start_point_ranges[r->start] = r;
1216           r->finish_next = ira_finish_point_ranges[r->finish];
1217           ira_finish_point_ranges[r->finish] = r;
1218         }
1219     }
1220 }
1221
1222 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1223    new live ranges and program points were added as a result if new
1224    insn generation.  */
1225 void
1226 ira_rebuild_start_finish_chains (void)
1227 {
1228   ira_free (ira_finish_point_ranges);
1229   ira_free (ira_start_point_ranges);
1230   create_start_finish_chains ();
1231 }
1232
1233 /* Compress allocno live ranges by removing program points where
1234    nothing happens.  */
1235 static void
1236 remove_some_program_points_and_update_live_ranges (void)
1237 {
1238   unsigned i;
1239   int n;
1240   int *map;
1241   ira_allocno_t a;
1242   ira_allocno_iterator ai;
1243   allocno_live_range_t r;
1244   bitmap born_or_died;
1245   bitmap_iterator bi;
1246
1247   born_or_died = ira_allocate_bitmap ();
1248   FOR_EACH_ALLOCNO (a, ai)
1249     {
1250       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1251         {
1252           ira_assert (r->start <= r->finish);
1253           bitmap_set_bit (born_or_died, r->start);
1254           bitmap_set_bit (born_or_died, r->finish);
1255         }
1256     }
1257   map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1258   n = 0;
1259   EXECUTE_IF_SET_IN_BITMAP(born_or_died, 0, i, bi)
1260     {
1261       map[i] = n++;
1262     }
1263   ira_free_bitmap (born_or_died);
1264   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1265     fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1266              ira_max_point, n, 100 * n / ira_max_point);
1267   ira_max_point = n;
1268   FOR_EACH_ALLOCNO (a, ai)
1269     {
1270       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1271         {
1272           r->start = map[r->start];
1273           r->finish = map[r->finish];
1274         }
1275     }
1276   ira_free (map);
1277 }
1278
1279 /* Print live ranges R to file F.  */
1280 void
1281 ira_print_live_range_list (FILE *f, allocno_live_range_t r)
1282 {
1283   for (; r != NULL; r = r->next)
1284     fprintf (f, " [%d..%d]", r->start, r->finish);
1285   fprintf (f, "\n");
1286 }
1287
1288 /* Print live ranges R to stderr.  */
1289 void
1290 ira_debug_live_range_list (allocno_live_range_t r)
1291 {
1292   ira_print_live_range_list (stderr, r);
1293 }
1294
1295 /* Print live ranges of allocno A to file F.  */
1296 static void
1297 print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1298 {
1299   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1300   ira_print_live_range_list (f, ALLOCNO_LIVE_RANGES (a));
1301 }
1302
1303 /* Print live ranges of allocno A to stderr.  */
1304 void
1305 ira_debug_allocno_live_ranges (ira_allocno_t a)
1306 {
1307   print_allocno_live_ranges (stderr, a);
1308 }
1309
1310 /* Print live ranges of all allocnos to file F.  */
1311 static void
1312 print_live_ranges (FILE *f)
1313 {
1314   ira_allocno_t a;
1315   ira_allocno_iterator ai;
1316
1317   FOR_EACH_ALLOCNO (a, ai)
1318     print_allocno_live_ranges (f, a);
1319 }
1320
1321 /* Print live ranges of all allocnos to stderr.  */
1322 void
1323 ira_debug_live_ranges (void)
1324 {
1325   print_live_ranges (stderr);
1326 }
1327
1328 /* The main entry function creates live ranges, set up
1329    CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
1330    calculate register pressure info.  */
1331 void
1332 ira_create_allocno_live_ranges (void)
1333 {
1334   allocnos_live = sparseset_alloc (ira_allocnos_num);
1335   curr_point = 0;
1336   last_call_num = 0;
1337   allocno_saved_at_call
1338     = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1339   memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
1340   ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1341                           process_bb_node_lives);
1342   ira_max_point = curr_point;
1343   create_start_finish_chains ();
1344   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1345     print_live_ranges (ira_dump_file);
1346   /* Clean up.  */
1347   ira_free (allocno_saved_at_call);
1348   sparseset_free (allocnos_live);
1349 }
1350
1351 /* Compress allocno live ranges.  */
1352 void
1353 ira_compress_allocno_live_ranges (void)
1354 {
1355   remove_some_program_points_and_update_live_ranges ();
1356   ira_rebuild_start_finish_chains ();
1357   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1358     {
1359       fprintf (ira_dump_file, "Ranges after the compression:\n");
1360       print_live_ranges (ira_dump_file);
1361     }
1362 }
1363
1364 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES.  */
1365 void
1366 ira_finish_allocno_live_ranges (void)
1367 {
1368   ira_free (ira_finish_point_ranges);
1369   ira_free (ira_start_point_ranges);
1370 }