gcc/ira-lives.c

   1 /* IRA processing allocno lives to build allocno live ranges.
   2    Copyright (C) 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "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       if (use == def || recog_data.operand_type[use] == OP_OUT)
 503         continue;
 504
 505       if (recog_op_alt[use][alt].anything_ok)
 506         use_cl = ALL_REGS;
 507       else
 508         use_cl = recog_op_alt[use][alt].cl;
 509
 510       advance_p = check_and_make_def_use_conflict (dreg, def_cl, use,
 511                                                    use_cl, advance_p);
 512
 513       if ((use_match = recog_op_alt[use][alt].matches) >= 0)
 514         {
 515           if (use_match == def)
 516             continue;
 517
 518           if (recog_op_alt[use_match][alt].anything_ok)
 519             use_cl = ALL_REGS;
 520           else
 521             use_cl = recog_op_alt[use_match][alt].cl;
 522           advance_p = check_and_make_def_use_conflict (dreg, def_cl, use,
 523                                                        use_cl, advance_p);
 524         }
 525     }
 526 }
 527
 528 /* Make conflicts of early clobber pseudo registers of the current
 529    insn with its inputs.  Avoid introducing unnecessary conflicts by
 530    checking classes of the constraints and pseudos because otherwise
 531    significant code degradation is possible for some targets.  */
 532 static void
 533 make_early_clobber_and_input_conflicts (void)
 534 {
 535   int alt;
 536   int def, def_match;
 537   enum reg_class def_cl;
 538
 539   for (alt = 0; alt < recog_data.n_alternatives; alt++)
 540     for (def = 0; def < recog_data.n_operands; def++)
 541       {
 542         def_cl = NO_REGS;
 543         if (recog_op_alt[def][alt].earlyclobber)
 544           {
 545             if (recog_op_alt[def][alt].anything_ok)
 546               def_cl = ALL_REGS;
 547             else
 548               def_cl = recog_op_alt[def][alt].cl;
 549             check_and_make_def_conflict (alt, def, def_cl);
 550           }
 551         if ((def_match = recog_op_alt[def][alt].matches) >= 0
 552             && (recog_op_alt[def_match][alt].earlyclobber
 553                 || recog_op_alt[def][alt].earlyclobber))
 554           {
 555             if (recog_op_alt[def_match][alt].anything_ok)
 556               def_cl = ALL_REGS;
 557             else
 558               def_cl = recog_op_alt[def_match][alt].cl;
 559             check_and_make_def_conflict (alt, def, def_cl);
 560           }
 561       }
 562 }
 563
 564 /* Mark early clobber hard registers of the current INSN as live (if
 565    LIVE_P) or dead.  Return true if there are such registers.  */
 566 static bool
 567 mark_hard_reg_early_clobbers (rtx insn, bool live_p)
 568 {
 569   df_ref *def_rec;
 570   bool set_p = false;
 571
 572   for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 573     if (DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MUST_CLOBBER))
 574       {
 575         rtx dreg = DF_REF_REG (*def_rec);
 576
 577         if (GET_CODE (dreg) == SUBREG)
 578           dreg = SUBREG_REG (dreg);
 579         if (! REG_P (dreg) || REGNO (dreg) >= FIRST_PSEUDO_REGISTER)
 580           continue;
 581
 582         /* Hard register clobbers are believed to be early clobber
 583            because there is no way to say that non-operand hard
 584            register clobbers are not early ones.  */
 585         if (live_p)
 586           mark_ref_live (*def_rec);
 587         else
 588           mark_ref_dead (*def_rec);
 589         set_p = true;
 590       }
 591
 592   return set_p;
 593 }
 594
 595 /* Checks that CONSTRAINTS permits to use only one hard register.  If
 596    it is so, the function returns the class of the hard register.
 597    Otherwise it returns NO_REGS.  */
 598 static enum reg_class
 599 single_reg_class (const char *constraints, rtx op, rtx equiv_const)
 600 {
 601   int ignore_p;
 602   enum reg_class cl, next_cl;
 603   int c;
 604
 605   cl = NO_REGS;
 606   for (ignore_p = false;
 607        (c = *constraints);
 608        constraints += CONSTRAINT_LEN (c, constraints))
 609     if (c == '#')
 610       ignore_p = true;
 611     else if (c == ',')
 612       ignore_p = false;
 613     else if (! ignore_p)
 614       switch (c)
 615         {
 616         case ' ':
 617         case '\t':
 618         case '=':
 619         case '+':
 620         case '*':
 621         case '&':
 622         case '%':
 623         case '!':
 624         case '?':
 625           break;
 626         case 'i':
 627           if (CONSTANT_P (op)
 628               || (equiv_const != NULL_RTX && CONSTANT_P (equiv_const)))
 629             return NO_REGS;
 630           break;
 631
 632         case 'n':
 633           if (CONST_INT_P (op)
 634               || (GET_CODE (op) == CONST_DOUBLE && GET_MODE (op) == VOIDmode)
 635               || (equiv_const != NULL_RTX
 636                   && (CONST_INT_P (equiv_const)
 637                       || (GET_CODE (equiv_const) == CONST_DOUBLE
 638                           && GET_MODE (equiv_const) == VOIDmode))))
 639             return NO_REGS;
 640           break;
 641
 642         case 's':
 643           if ((CONSTANT_P (op) && !CONST_INT_P (op)
 644                && (GET_CODE (op) != CONST_DOUBLE || GET_MODE (op) != VOIDmode))
 645               || (equiv_const != NULL_RTX
 646                   && CONSTANT_P (equiv_const)
 647                   && !CONST_INT_P (equiv_const)
 648                   && (GET_CODE (equiv_const) != CONST_DOUBLE
 649                       || GET_MODE (equiv_const) != VOIDmode)))
 650             return NO_REGS;
 651           break;
 652
 653         case 'I':
 654         case 'J':
 655         case 'K':
 656         case 'L':
 657         case 'M':
 658         case 'N':
 659         case 'O':
 660         case 'P':
 661           if ((CONST_INT_P (op)
 662                && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, constraints))
 663               || (equiv_const != NULL_RTX
 664                   && CONST_INT_P (equiv_const)
 665                   && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
 666                                                 c, constraints)))
 667             return NO_REGS;
 668           break;
 669
 670         case 'E':
 671         case 'F':
 672           if (GET_CODE (op) == CONST_DOUBLE
 673               || (GET_CODE (op) == CONST_VECTOR
 674                   && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT)
 675               || (equiv_const != NULL_RTX
 676                   && (GET_CODE (equiv_const) == CONST_DOUBLE
 677                       || (GET_CODE (equiv_const) == CONST_VECTOR
 678                           && (GET_MODE_CLASS (GET_MODE (equiv_const))
 679                               == MODE_VECTOR_FLOAT)))))
 680             return NO_REGS;
 681           break;
 682
 683         case 'G':
 684         case 'H':
 685           if ((GET_CODE (op) == CONST_DOUBLE
 686                && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, constraints))
 687               || (equiv_const != NULL_RTX
 688                   && GET_CODE (equiv_const) == CONST_DOUBLE
 689                   && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const,
 690                                                        c, constraints)))
 691             return NO_REGS;
 692           /* ??? what about memory */
 693         case 'r':
 694         case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
 695         case 'h': case 'j': case 'k': case 'l':
 696         case 'q': case 't': case 'u':
 697         case 'v': case 'w': case 'x': case 'y': case 'z':
 698         case 'A': case 'B': case 'C': case 'D':
 699         case 'Q': case 'R': case 'S': case 'T': case 'U':
 700         case 'W': case 'Y': case 'Z':
 701           next_cl = (c == 'r'
 702                      ? GENERAL_REGS
 703                      : REG_CLASS_FROM_CONSTRAINT (c, constraints));
 704           if ((cl != NO_REGS && next_cl != cl)
 705               || (ira_available_class_regs[next_cl]
 706                   > ira_reg_class_nregs[next_cl][GET_MODE (op)]))
 707             return NO_REGS;
 708           cl = next_cl;
 709           break;
 710
 711         case '0': case '1': case '2': case '3': case '4':
 712         case '5': case '6': case '7': case '8': case '9':
 713           next_cl
 714             = single_reg_class (recog_data.constraints[c - '0'],
 715                                 recog_data.operand[c - '0'], NULL_RTX);
 716           if ((cl != NO_REGS && next_cl != cl)
 717               || next_cl == NO_REGS
 718               || (ira_available_class_regs[next_cl]
 719                   > ira_reg_class_nregs[next_cl][GET_MODE (op)]))
 720             return NO_REGS;
 721           cl = next_cl;
 722           break;
 723
 724         default:
 725           return NO_REGS;
 726         }
 727   return cl;
 728 }
 729
 730 /* The function checks that operand OP_NUM of the current insn can use
 731    only one hard register.  If it is so, the function returns the
 732    class of the hard register.  Otherwise it returns NO_REGS.  */
 733 static enum reg_class
 734 single_reg_operand_class (int op_num)
 735 {
 736   if (op_num < 0 || recog_data.n_alternatives == 0)
 737     return NO_REGS;
 738   return single_reg_class (recog_data.constraints[op_num],
 739                            recog_data.operand[op_num], NULL_RTX);
 740 }
 741
 742 /* The function sets up hard register set *SET to hard registers which
 743    might be used by insn reloads because the constraints are too
 744    strict.  */
 745 void
 746 ira_implicitly_set_insn_hard_regs (HARD_REG_SET *set)
 747 {
 748   int i, c, regno = 0;
 749   bool ignore_p;
 750   enum reg_class cl;
 751   rtx op;
 752   enum machine_mode mode;
 753
 754   CLEAR_HARD_REG_SET (*set);
 755   for (i = 0; i < recog_data.n_operands; i++)
 756     {
 757       op = recog_data.operand[i];
 758
 759       if (GET_CODE (op) == SUBREG)
 760         op = SUBREG_REG (op);
 761
 762       if (GET_CODE (op) == SCRATCH
 763           || (REG_P (op) && (regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER))
 764         {
 765           const char *p = recog_data.constraints[i];
 766
 767           mode = (GET_CODE (op) == SCRATCH
 768                   ? GET_MODE (op) : PSEUDO_REGNO_MODE (regno));
 769           cl = NO_REGS;
 770           for (ignore_p = false; (c = *p); p += CONSTRAINT_LEN (c, p))
 771             if (c == '#')
 772               ignore_p = true;
 773             else if (c == ',')
 774               ignore_p = false;
 775             else if (! ignore_p)
 776               switch (c)
 777                 {
 778                 case 'r':
 779                 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
 780                 case 'h': case 'j': case 'k': case 'l':
 781                 case 'q': case 't': case 'u':
 782                 case 'v': case 'w': case 'x': case 'y': case 'z':
 783                 case 'A': case 'B': case 'C': case 'D':
 784                 case 'Q': case 'R': case 'S': case 'T': case 'U':
 785                 case 'W': case 'Y': case 'Z':
 786                   cl = (c == 'r'
 787                         ? GENERAL_REGS
 788                         : REG_CLASS_FROM_CONSTRAINT (c, p));
 789                   if (cl != NO_REGS
 790                       && (ira_available_class_regs[cl]
 791                           <= ira_reg_class_nregs[cl][mode]))
 792                     IOR_HARD_REG_SET (*set, reg_class_contents[cl]);
 793                   break;
 794                 }
 795         }
 796     }
 797 }
 798 /* Processes input operands, if IN_P, or output operands otherwise of
 799    the current insn with FREQ to find allocno which can use only one
 800    hard register and makes other currently living allocnos conflicting
 801    with the hard register.  */
 802 static void
 803 process_single_reg_class_operands (bool in_p, int freq)
 804 {
 805   int i, regno, cost;
 806   unsigned int px;
 807   enum reg_class cl, cover_class;
 808   rtx operand;
 809   ira_allocno_t operand_a, a;
 810
 811   for (i = 0; i < recog_data.n_operands; i++)
 812     {
 813       operand = recog_data.operand[i];
 814       if (in_p && recog_data.operand_type[i] != OP_IN
 815           && recog_data.operand_type[i] != OP_INOUT)
 816         continue;
 817       if (! in_p && recog_data.operand_type[i] != OP_OUT
 818           && recog_data.operand_type[i] != OP_INOUT)
 819         continue;
 820       cl = single_reg_operand_class (i);
 821       if (cl == NO_REGS)
 822         continue;
 823
 824       operand_a = NULL;
 825
 826       if (GET_CODE (operand) == SUBREG)
 827         operand = SUBREG_REG (operand);
 828
 829       if (REG_P (operand)
 830           && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
 831         {
 832           enum machine_mode mode;
 833           enum reg_class cover_class;
 834
 835           operand_a = ira_curr_regno_allocno_map[regno];
 836           mode = ALLOCNO_MODE (operand_a);
 837           cover_class = ALLOCNO_COVER_CLASS (operand_a);
 838           if (ira_class_subset_p[cl][cover_class]
 839               && ira_class_hard_regs_num[cl] != 0
 840               && (ira_class_hard_reg_index[cover_class]
 841                   [ira_class_hard_regs[cl][0]]) >= 0
 842               && reg_class_size[cl] <= (unsigned) CLASS_MAX_NREGS (cl, mode))
 843             {
 844               int i, size;
 845               cost
 846                 = (freq
 847                    * (in_p
 848                       ? ira_get_register_move_cost (mode, cover_class, cl)
 849                       : ira_get_register_move_cost (mode, cl, cover_class)));
 850               ira_allocate_and_set_costs
 851                 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), cover_class, 0);
 852               size = ira_reg_class_nregs[cover_class][mode];
 853               for (i = 0; i < size; i++)
 854                 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
 855                   [ira_class_hard_reg_index
 856                    [cover_class][ira_class_hard_regs[cl][i]]]
 857                   -= cost;
 858             }
 859         }
 860
 861       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
 862         {
 863           a = ira_allocnos[px];
 864           cover_class = ALLOCNO_COVER_CLASS (a);
 865           if (a != operand_a)
 866             {
 867               /* We could increase costs of A instead of making it
 868                  conflicting with the hard register.  But it works worse
 869                  because it will be spilled in reload in anyway.  */
 870               IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 871                                 reg_class_contents[cl]);
 872               IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 873                                 reg_class_contents[cl]);
 874             }
 875         }
 876     }
 877 }
 878
 879 /* Return true when one of the predecessor edges of BB is marked with
 880    EDGE_ABNORMAL_CALL or EDGE_EH.  */
 881 static bool
 882 bb_has_abnormal_call_pred (basic_block bb)
 883 {
 884   edge e;
 885   edge_iterator ei;
 886
 887   FOR_EACH_EDGE (e, ei, bb->preds)
 888     {
 889       if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
 890         return true;
 891     }
 892   return false;
 893 }
 894
 895 /* Process insns of the basic block given by its LOOP_TREE_NODE to
 896    update allocno live ranges, allocno hard register conflicts,
 897    intersected calls, and register pressure info for allocnos for the
 898    basic block for and regions containing the basic block.  */
 899 static void
 900 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
 901 {
 902   int i, freq;
 903   unsigned int j;
 904   basic_block bb;
 905   rtx insn;
 906   bitmap_iterator bi;
 907   bitmap reg_live_out;
 908   unsigned int px;
 909   bool set_p;
 910
 911   bb = loop_tree_node->bb;
 912   if (bb != NULL)
 913     {
 914       for (i = 0; i < ira_reg_class_cover_size; i++)
 915         {
 916           curr_reg_pressure[ira_reg_class_cover[i]] = 0;
 917           high_pressure_start_point[ira_reg_class_cover[i]] = -1;
 918         }
 919       curr_bb_node = loop_tree_node;
 920       reg_live_out = DF_LR_OUT (bb);
 921       sparseset_clear (allocnos_live);
 922       REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
 923       AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
 924       AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
 925       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 926         if (TEST_HARD_REG_BIT (hard_regs_live, i))
 927           {
 928             enum reg_class cover_class, cl;
 929
 930             cover_class = ira_class_translate[REGNO_REG_CLASS (i)];
 931             for (j = 0;
 932                  (cl = ira_reg_class_super_classes[cover_class][j])
 933                    != LIM_REG_CLASSES;
 934                  j++)
 935               {
 936                 curr_reg_pressure[cl]++;
 937                 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
 938                   curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
 939                 ira_assert (curr_reg_pressure[cl]
 940                             <= ira_available_class_regs[cl]);
 941               }
 942           }
 943       EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
 944         {
 945           ira_allocno_t a = ira_curr_regno_allocno_map[j];
 946
 947           if (a == NULL)
 948             continue;
 949           ira_assert (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)));
 950           set_allocno_live (a);
 951           make_regno_born (j);
 952         }
 953
 954       freq = REG_FREQ_FROM_BB (bb);
 955       if (freq == 0)
 956         freq = 1;
 957
 958       /* Invalidate all allocno_saved_at_call entries.  */
 959       last_call_num++;
 960
 961       /* Scan the code of this basic block, noting which allocnos and
 962          hard regs are born or die.
 963
 964          Note that this loop treats uninitialized values as live until
 965          the beginning of the block.  For example, if an instruction
 966          uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
 967          set, FOO will remain live until the beginning of the block.
 968          Likewise if FOO is not set at all.  This is unnecessarily
 969          pessimistic, but it probably doesn't matter much in practice.  */
 970       FOR_BB_INSNS_REVERSE (bb, insn)
 971         {
 972           df_ref *def_rec, *use_rec;
 973           bool call_p;
 974
 975           if (!NONDEBUG_INSN_P (insn))
 976             continue;
 977
 978           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 979             fprintf (ira_dump_file, "   Insn %u(l%d): point = %d\n",
 980                      INSN_UID (insn), loop_tree_node->parent->loop->num,
 981                      curr_point);
 982
 983           /* Mark each defined value as live.  We need to do this for
 984              unused values because they still conflict with quantities
 985              that are live at the time of the definition.
 986
 987              Ignore DF_REF_MAY_CLOBBERs on a call instruction.  Such
 988              references represent the effect of the called function
 989              on a call-clobbered register.  Marking the register as
 990              live would stop us from allocating it to a call-crossing
 991              allocno.  */
 992           call_p = CALL_P (insn);
 993           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 994             if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
 995               mark_ref_live (*def_rec);
 996
 997           /* If INSN has multiple outputs, then any value used in one
 998              of the outputs conflicts with the other outputs.  Model this
 999              by making the used value live during the output phase.
1000
1001              It is unsafe to use !single_set here since it will ignore
1002              an unused output.  Just because an output is unused does
1003              not mean the compiler can assume the side effect will not
1004              occur.  Consider if ALLOCNO appears in the address of an
1005              output and we reload the output.  If we allocate ALLOCNO
1006              to the same hard register as an unused output we could
1007              set the hard register before the output reload insn.  */
1008           if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1009             for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1010               {
1011                 int i;
1012                 rtx reg;
1013
1014                 reg = DF_REF_REG (*use_rec);
1015                 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1016                   {
1017                     rtx set;
1018
1019                     set = XVECEXP (PATTERN (insn), 0, i);
1020                     if (GET_CODE (set) == SET
1021                         && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1022                       {
1023                         /* After the previous loop, this is a no-op if
1024                            REG is contained within SET_DEST (SET).  */
1025                         mark_ref_live (*use_rec);
1026                         break;
1027                       }
1028                   }
1029               }
1030
1031           extract_insn (insn);
1032           preprocess_constraints ();
1033           process_single_reg_class_operands (false, freq);
1034
1035           /* See which defined values die here.  */
1036           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1037             if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1038               mark_ref_dead (*def_rec);
1039
1040           if (call_p)
1041             {
1042               last_call_num++;
1043               /* The current set of live allocnos are live across the call.  */
1044               EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1045                 {
1046                   ira_allocno_t a = ira_allocnos[i];
1047
1048                   if (allocno_saved_at_call[i] != last_call_num)
1049                     /* Here we are mimicking caller-save.c behaviour
1050                        which does not save hard register at a call if
1051                        it was saved on previous call in the same basic
1052                        block and the hard register was not mentioned
1053                        between the two calls.  */
1054                     ALLOCNO_CALL_FREQ (a) += freq;
1055                   /* Mark it as saved at the next call.  */
1056                   allocno_saved_at_call[i] = last_call_num + 1;
1057                   ALLOCNO_CALLS_CROSSED_NUM (a)++;
1058                   /* Don't allocate allocnos that cross setjmps or any
1059                      call, if this function receives a nonlocal
1060                      goto.  */
1061                   if (cfun->has_nonlocal_label
1062                       || find_reg_note (insn, REG_SETJMP,
1063                                         NULL_RTX) != NULL_RTX)
1064                     {
1065                       SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a));
1066                       SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1067                     }
1068                   if (can_throw_internal (insn))
1069                     {
1070                       IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
1071                                         call_used_reg_set);
1072                       IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
1073                                         call_used_reg_set);
1074                     }
1075                 }
1076             }
1077
1078           make_early_clobber_and_input_conflicts ();
1079
1080           curr_point++;
1081
1082           /* Mark each used value as live.  */
1083           for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1084             mark_ref_live (*use_rec);
1085
1086           process_single_reg_class_operands (true, freq);
1087
1088           set_p = mark_hard_reg_early_clobbers (insn, true);
1089
1090           if (set_p)
1091             {
1092               mark_hard_reg_early_clobbers (insn, false);
1093
1094               /* Mark each hard reg as live again.  For example, a
1095                  hard register can be in clobber and in an insn
1096                  input.  */
1097               for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1098                 {
1099                   rtx ureg = DF_REF_REG (*use_rec);
1100
1101                   if (GET_CODE (ureg) == SUBREG)
1102                     ureg = SUBREG_REG (ureg);
1103                   if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1104                     continue;
1105
1106                   mark_ref_live (*use_rec);
1107                 }
1108             }
1109
1110           curr_point++;
1111         }
1112
1113 #ifdef EH_RETURN_DATA_REGNO
1114       if (bb_has_eh_pred (bb))
1115         for (j = 0; ; ++j)
1116           {
1117             unsigned int regno = EH_RETURN_DATA_REGNO (j);
1118             if (regno == INVALID_REGNUM)
1119               break;
1120             make_regno_born (regno);
1121           }
1122 #endif
1123
1124       /* Allocnos can't go in stack regs at the start of a basic block
1125          that is reached by an abnormal edge. Likewise for call
1126          clobbered regs, because caller-save, fixup_abnormal_edges and
1127          possibly the table driven EH machinery are not quite ready to
1128          handle such allocnos live across such edges.  */
1129       if (bb_has_abnormal_pred (bb))
1130         {
1131 #ifdef STACK_REGS
1132           EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
1133             {
1134               ALLOCNO_NO_STACK_REG_P (ira_allocnos[px]) = true;
1135               ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos[px]) = true;
1136             }
1137           for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1138             make_regno_born (px);
1139 #endif
1140           /* No need to record conflicts for call clobbered regs if we
1141              have nonlocal labels around, as we don't ever try to
1142              allocate such regs in this case.  */
1143           if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
1144             for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1145               if (call_used_regs[px])
1146                 make_regno_born (px);
1147         }
1148
1149       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1150         {
1151           make_regno_dead (ALLOCNO_REGNO (ira_allocnos[i]));
1152         }
1153
1154       curr_point++;
1155
1156     }
1157   /* Propagate register pressure to upper loop tree nodes: */
1158   if (loop_tree_node != ira_loop_tree_root)
1159     for (i = 0; i < ira_reg_class_cover_size; i++)
1160       {
1161         enum reg_class cover_class;
1162
1163         cover_class = ira_reg_class_cover[i];
1164         if (loop_tree_node->reg_pressure[cover_class]
1165             > loop_tree_node->parent->reg_pressure[cover_class])
1166           loop_tree_node->parent->reg_pressure[cover_class]
1167             = loop_tree_node->reg_pressure[cover_class];
1168       }
1169 }
1170
1171 /* Create and set up IRA_START_POINT_RANGES and
1172    IRA_FINISH_POINT_RANGES.  */
1173 static void
1174 create_start_finish_chains (void)
1175 {
1176   ira_allocno_t a;
1177   ira_allocno_iterator ai;
1178   allocno_live_range_t r;
1179
1180   ira_start_point_ranges
1181     = (allocno_live_range_t *) ira_allocate (ira_max_point
1182                                              * sizeof (allocno_live_range_t));
1183   memset (ira_start_point_ranges, 0,
1184           ira_max_point * sizeof (allocno_live_range_t));
1185   ira_finish_point_ranges
1186     = (allocno_live_range_t *) ira_allocate (ira_max_point
1187                                              * sizeof (allocno_live_range_t));
1188   memset (ira_finish_point_ranges, 0,
1189           ira_max_point * sizeof (allocno_live_range_t));
1190   FOR_EACH_ALLOCNO (a, ai)
1191     {
1192       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1193         {
1194           r->start_next = ira_start_point_ranges[r->start];
1195           ira_start_point_ranges[r->start] = r;
1196           r->finish_next = ira_finish_point_ranges[r->finish];
1197           ira_finish_point_ranges[r->finish] = r;
1198         }
1199     }
1200 }
1201
1202 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1203    new live ranges and program points were added as a result if new
1204    insn generation.  */
1205 void
1206 ira_rebuild_start_finish_chains (void)
1207 {
1208   ira_free (ira_finish_point_ranges);
1209   ira_free (ira_start_point_ranges);
1210   create_start_finish_chains ();
1211 }
1212
1213 /* Compress allocno live ranges by removing program points where
1214    nothing happens.  */
1215 static void
1216 remove_some_program_points_and_update_live_ranges (void)
1217 {
1218   unsigned i;
1219   int n;
1220   int *map;
1221   ira_allocno_t a;
1222   ira_allocno_iterator ai;
1223   allocno_live_range_t r;
1224   bitmap born_or_died;
1225   bitmap_iterator bi;
1226
1227   born_or_died = ira_allocate_bitmap ();
1228   FOR_EACH_ALLOCNO (a, ai)
1229     {
1230       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1231         {
1232           ira_assert (r->start <= r->finish);
1233           bitmap_set_bit (born_or_died, r->start);
1234           bitmap_set_bit (born_or_died, r->finish);
1235         }
1236     }
1237   map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1238   n = 0;
1239   EXECUTE_IF_SET_IN_BITMAP(born_or_died, 0, i, bi)
1240     {
1241       map[i] = n++;
1242     }
1243   ira_free_bitmap (born_or_died);
1244   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1245     fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1246              ira_max_point, n, 100 * n / ira_max_point);
1247   ira_max_point = n;
1248   FOR_EACH_ALLOCNO (a, ai)
1249     {
1250       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1251         {
1252           r->start = map[r->start];
1253           r->finish = map[r->finish];
1254         }
1255     }
1256   ira_free (map);
1257 }
1258
1259 /* Print live ranges R to file F.  */
1260 void
1261 ira_print_live_range_list (FILE *f, allocno_live_range_t r)
1262 {
1263   for (; r != NULL; r = r->next)
1264     fprintf (f, " [%d..%d]", r->start, r->finish);
1265   fprintf (f, "\n");
1266 }
1267
1268 /* Print live ranges R to stderr.  */
1269 void
1270 ira_debug_live_range_list (allocno_live_range_t r)
1271 {
1272   ira_print_live_range_list (stderr, r);
1273 }
1274
1275 /* Print live ranges of allocno A to file F.  */
1276 static void
1277 print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1278 {
1279   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1280   ira_print_live_range_list (f, ALLOCNO_LIVE_RANGES (a));
1281 }
1282
1283 /* Print live ranges of allocno A to stderr.  */
1284 void
1285 ira_debug_allocno_live_ranges (ira_allocno_t a)
1286 {
1287   print_allocno_live_ranges (stderr, a);
1288 }
1289
1290 /* Print live ranges of all allocnos to file F.  */
1291 static void
1292 print_live_ranges (FILE *f)
1293 {
1294   ira_allocno_t a;
1295   ira_allocno_iterator ai;
1296
1297   FOR_EACH_ALLOCNO (a, ai)
1298     print_allocno_live_ranges (f, a);
1299 }
1300
1301 /* Print live ranges of all allocnos to stderr.  */
1302 void
1303 ira_debug_live_ranges (void)
1304 {
1305   print_live_ranges (stderr);
1306 }
1307
1308 /* The main entry function creates live ranges, set up
1309    CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
1310    calculate register pressure info.  */
1311 void
1312 ira_create_allocno_live_ranges (void)
1313 {
1314   allocnos_live = sparseset_alloc (ira_allocnos_num);
1315   curr_point = 0;
1316   last_call_num = 0;
1317   allocno_saved_at_call
1318     = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1319   memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
1320   ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1321                           process_bb_node_lives);
1322   ira_max_point = curr_point;
1323   create_start_finish_chains ();
1324   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1325     print_live_ranges (ira_dump_file);
1326   /* Clean up.  */
1327   ira_free (allocno_saved_at_call);
1328   sparseset_free (allocnos_live);
1329 }
1330
1331 /* Compress allocno live ranges.  */
1332 void
1333 ira_compress_allocno_live_ranges (void)
1334 {
1335   remove_some_program_points_and_update_live_ranges ();
1336   ira_rebuild_start_finish_chains ();
1337   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1338     {
1339       fprintf (ira_dump_file, "Ranges after the compression:\n");
1340       print_live_ranges (ira_dump_file);
1341     }
1342 }
1343
1344 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES.  */
1345 void
1346 ira_finish_allocno_live_ranges (void)
1347 {
1348   ira_free (ira_finish_point_ranges);
1349   ira_free (ira_start_point_ranges);
1350 }