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