gcc/ira-lives.c

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