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 referenced by use or def REF as live
 213    Store a 1 in hard_regs_live or allocnos_live for this register or
 214    the corresponding allocno, record how many consecutive hardware
 215    registers it actually needs.  */
 216
 217 static void
 218 mark_ref_live (struct df_ref *ref)
 219 {
 220   rtx reg;
 221   int regno;
 222
 223   reg = DF_REF_REG (ref);
 224   if (GET_CODE (reg) == SUBREG)
 225     reg = SUBREG_REG (reg);
 226   gcc_assert (REG_P (reg));
 227   regno = REGNO (reg);
 228
 229   if (regno >= FIRST_PSEUDO_REGISTER)
 230     {
 231       ira_allocno_t a = ira_curr_regno_allocno_map[regno];
 232
 233       if (a != NULL)
 234         {
 235           if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
 236             return;
 237           set_allocno_live (a);
 238         }
 239       make_regno_born (regno);
 240     }
 241   else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
 242     {
 243       int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
 244       enum reg_class cover_class;
 245
 246       while (regno < last)
 247         {
 248           if (! TEST_HARD_REG_BIT (hard_regs_live, regno)
 249               && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
 250             {
 251               cover_class = ira_class_translate[REGNO_REG_CLASS (regno)];
 252               if (cover_class != NO_REGS)
 253                 {
 254                   curr_reg_pressure[cover_class]++;
 255                   if (high_pressure_start_point[cover_class] < 0
 256                       && (curr_reg_pressure[cover_class]
 257                           > ira_available_class_regs[cover_class]))
 258                     high_pressure_start_point[cover_class] = curr_point;
 259                 }
 260               make_regno_born (regno);
 261               if (cover_class != NO_REGS
 262                   && (curr_bb_node->reg_pressure[cover_class]
 263                       < curr_reg_pressure[cover_class]))
 264                 curr_bb_node->reg_pressure[cover_class]
 265                   = curr_reg_pressure[cover_class];
 266             }
 267           regno++;
 268         }
 269     }
 270 }
 271
 272 /* Return true if the definition described by DEF conflicts with the
 273    instruction's inputs.  */
 274 static bool
 275 def_conflicts_with_inputs_p (struct df_ref *def)
 276 {
 277   /* Conservatively assume that the condition is true for all clobbers.  */
 278   return DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER);
 279 }
 280
 281 /* Mark the register referenced by definition DEF as dead, if the
 282    definition is a total one.  Store a 0 in hard_regs_live or
 283    allocnos_live for the register.  */
 284 static void
 285 mark_ref_dead (struct df_ref *def)
 286 {
 287   unsigned int i;
 288   rtx reg;
 289   int regno;
 290
 291   if (DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL)
 292       || DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
 293     return;
 294
 295   reg = DF_REF_REG (def);
 296   if (GET_CODE (reg) == SUBREG)
 297     reg = SUBREG_REG (reg);
 298   gcc_assert (REG_P (reg));
 299   regno = REGNO (reg);
 300
 301   if (regno >= FIRST_PSEUDO_REGISTER)
 302     {
 303       ira_allocno_t a = ira_curr_regno_allocno_map[regno];
 304
 305       if (a != NULL)
 306         {
 307           if (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
 308             return;
 309           clear_allocno_live (a);
 310         }
 311       make_regno_dead (regno);
 312     }
 313   else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
 314     {
 315       int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
 316       enum reg_class cover_class;
 317
 318       while (regno < last)
 319         {
 320           if (TEST_HARD_REG_BIT (hard_regs_live, regno))
 321             {
 322               cover_class = ira_class_translate[REGNO_REG_CLASS (regno)];
 323               if (cover_class != NO_REGS)
 324                 {
 325                   curr_reg_pressure[cover_class]--;
 326                   if (high_pressure_start_point[cover_class] >= 0
 327                       && (curr_reg_pressure[cover_class]
 328                           <= ira_available_class_regs[cover_class]))
 329                     {
 330                       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 331                         {
 332                           update_allocno_pressure_excess_length
 333                             (ira_allocnos[i]);
 334                         }
 335                       high_pressure_start_point[cover_class] = -1;
 336                     }
 337                   ira_assert (curr_reg_pressure[cover_class] >= 0);
 338                 }
 339               make_regno_dead (regno);
 340             }
 341           regno++;
 342         }
 343     }
 344 }
 345
 346 /* Checks that CONSTRAINTS permits to use only one hard register.  If
 347    it is so, the function returns the class of the hard register.
 348    Otherwise it returns NO_REGS.  */
 349 static enum reg_class
 350 single_reg_class (const char *constraints, rtx op, rtx equiv_const)
 351 {
 352   int ignore_p;
 353   enum reg_class cl, next_cl;
 354   int c;
 355
 356   cl = NO_REGS;
 357   for (ignore_p = false;
 358        (c = *constraints);
 359        constraints += CONSTRAINT_LEN (c, constraints))
 360     if (c == '#')
 361       ignore_p = true;
 362     else if (c == ',')
 363       ignore_p = false;
 364     else if (! ignore_p)
 365       switch (c)
 366         {
 367         case ' ':
 368         case '\t':
 369         case '=':
 370         case '+':
 371         case '*':
 372         case '&':
 373         case '%':
 374         case '!':
 375         case '?':
 376           break;
 377         case 'i':
 378           if (CONSTANT_P (op)
 379               || (equiv_const != NULL_RTX && CONSTANT_P (equiv_const)))
 380             return NO_REGS;
 381           break;
 382
 383         case 'n':
 384           if (GET_CODE (op) == CONST_INT
 385               || (GET_CODE (op) == CONST_DOUBLE && GET_MODE (op) == VOIDmode)
 386               || (equiv_const != NULL_RTX
 387                   && (GET_CODE (equiv_const) == CONST_INT
 388                       || (GET_CODE (equiv_const) == CONST_DOUBLE
 389                           && GET_MODE (equiv_const) == VOIDmode))))
 390             return NO_REGS;
 391           break;
 392
 393         case 's':
 394           if ((CONSTANT_P (op) && GET_CODE (op) != CONST_INT
 395                && (GET_CODE (op) != CONST_DOUBLE || GET_MODE (op) != VOIDmode))
 396               || (equiv_const != NULL_RTX
 397                   && CONSTANT_P (equiv_const)
 398                   && GET_CODE (equiv_const) != CONST_INT
 399                   && (GET_CODE (equiv_const) != CONST_DOUBLE
 400                       || GET_MODE (equiv_const) != VOIDmode)))
 401             return NO_REGS;
 402           break;
 403
 404         case 'I':
 405         case 'J':
 406         case 'K':
 407         case 'L':
 408         case 'M':
 409         case 'N':
 410         case 'O':
 411         case 'P':
 412           if ((GET_CODE (op) == CONST_INT
 413                && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, constraints))
 414               || (equiv_const != NULL_RTX
 415                   && GET_CODE (equiv_const) == CONST_INT
 416                   && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
 417                                                 c, constraints)))
 418             return NO_REGS;
 419           break;
 420
 421         case 'E':
 422         case 'F':
 423           if (GET_CODE (op) == CONST_DOUBLE
 424               || (GET_CODE (op) == CONST_VECTOR
 425                   && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT)
 426               || (equiv_const != NULL_RTX
 427                   && (GET_CODE (equiv_const) == CONST_DOUBLE
 428                       || (GET_CODE (equiv_const) == CONST_VECTOR
 429                           && (GET_MODE_CLASS (GET_MODE (equiv_const))
 430                               == MODE_VECTOR_FLOAT)))))
 431             return NO_REGS;
 432           break;
 433
 434         case 'G':
 435         case 'H':
 436           if ((GET_CODE (op) == CONST_DOUBLE
 437                && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, constraints))
 438               || (equiv_const != NULL_RTX
 439                   && GET_CODE (equiv_const) == CONST_DOUBLE
 440                   && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const,
 441                                                        c, constraints)))
 442             return NO_REGS;
 443           /* ??? what about memory */
 444         case 'r':
 445         case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
 446         case 'h': case 'j': case 'k': case 'l':
 447         case 'q': case 't': case 'u':
 448         case 'v': case 'w': case 'x': case 'y': case 'z':
 449         case 'A': case 'B': case 'C': case 'D':
 450         case 'Q': case 'R': case 'S': case 'T': case 'U':
 451         case 'W': case 'Y': case 'Z':
 452           next_cl = (c == 'r'
 453                      ? GENERAL_REGS
 454                      : REG_CLASS_FROM_CONSTRAINT (c, constraints));
 455           if ((cl != NO_REGS && next_cl != cl)
 456               || ira_available_class_regs[next_cl] > 1)
 457             return NO_REGS;
 458           cl = next_cl;
 459           break;
 460
 461         case '0': case '1': case '2': case '3': case '4':
 462         case '5': case '6': case '7': case '8': case '9':
 463           next_cl
 464             = single_reg_class (recog_data.constraints[c - '0'],
 465                                 recog_data.operand[c - '0'], NULL_RTX);
 466           if ((cl != NO_REGS && next_cl != cl) || next_cl == NO_REGS
 467               || ira_available_class_regs[next_cl] > 1)
 468             return NO_REGS;
 469           cl = next_cl;
 470           break;
 471
 472         default:
 473           return NO_REGS;
 474         }
 475   return cl;
 476 }
 477
 478 /* The function checks that operand OP_NUM of the current insn can use
 479    only one hard register.  If it is so, the function returns the
 480    class of the hard register.  Otherwise it returns NO_REGS.  */
 481 static enum reg_class
 482 single_reg_operand_class (int op_num)
 483 {
 484   if (op_num < 0 || recog_data.n_alternatives == 0)
 485     return NO_REGS;
 486   return single_reg_class (recog_data.constraints[op_num],
 487                            recog_data.operand[op_num], NULL_RTX);
 488 }
 489
 490 /* Processes input operands, if IN_P, or output operands otherwise of
 491    the current insn with FREQ to find allocno which can use only one
 492    hard register and makes other currently living allocnos conflicting
 493    with the hard register.  */
 494 static void
 495 process_single_reg_class_operands (bool in_p, int freq)
 496 {
 497   int i, regno, cost;
 498   unsigned int px;
 499   enum reg_class cl, cover_class;
 500   rtx operand;
 501   ira_allocno_t operand_a, a;
 502
 503   for (i = 0; i < recog_data.n_operands; i++)
 504     {
 505       operand = recog_data.operand[i];
 506       if (in_p && recog_data.operand_type[i] != OP_IN
 507           && recog_data.operand_type[i] != OP_INOUT)
 508         continue;
 509       if (! in_p && recog_data.operand_type[i] != OP_OUT
 510           && recog_data.operand_type[i] != OP_INOUT)
 511         continue;
 512       cl = single_reg_operand_class (i);
 513       if (cl == NO_REGS)
 514         continue;
 515
 516       operand_a = NULL;
 517
 518       if (GET_CODE (operand) == SUBREG)
 519         operand = SUBREG_REG (operand);
 520
 521       if (REG_P (operand)
 522           && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
 523         {
 524           enum machine_mode mode;
 525           enum reg_class cover_class;
 526
 527           operand_a = ira_curr_regno_allocno_map[regno];
 528           mode = ALLOCNO_MODE (operand_a);
 529           cover_class = ALLOCNO_COVER_CLASS (operand_a);
 530           if (ira_class_subset_p[cl][cover_class]
 531               && ira_class_hard_regs_num[cl] != 0
 532               && (ira_class_hard_reg_index[cover_class]
 533                   [ira_class_hard_regs[cl][0]]) >= 0
 534               && reg_class_size[cl] <= (unsigned) CLASS_MAX_NREGS (cl, mode))
 535             {
 536               /* ??? FREQ */
 537               cost = freq * (in_p
 538                              ? ira_register_move_cost[mode][cover_class][cl]
 539                              : ira_register_move_cost[mode][cl][cover_class]);
 540               ira_allocate_and_set_costs
 541                 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), cover_class, 0);
 542               ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
 543                 [ira_class_hard_reg_index
 544                  [cover_class][ira_class_hard_regs[cl][0]]]
 545                 -= cost;
 546             }
 547         }
 548
 549       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
 550         {
 551           a = ira_allocnos[px];
 552           cover_class = ALLOCNO_COVER_CLASS (a);
 553           if (a != operand_a)
 554             {
 555               /* We could increase costs of A instead of making it
 556                  conflicting with the hard register.  But it works worse
 557                  because it will be spilled in reload in anyway.  */
 558               IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 559                                 reg_class_contents[cl]);
 560               IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 561                                 reg_class_contents[cl]);
 562             }
 563         }
 564     }
 565 }
 566
 567 /* Process insns of the basic block given by its LOOP_TREE_NODE to
 568    update allocno live ranges, allocno hard register conflicts,
 569    intersected calls, and register pressure info for allocnos for the
 570    basic block for and regions containing the basic block.  */
 571 static void
 572 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
 573 {
 574   int i, freq;
 575   unsigned int j;
 576   basic_block bb;
 577   rtx insn;
 578   edge e;
 579   edge_iterator ei;
 580   bitmap_iterator bi;
 581   bitmap reg_live_out;
 582   unsigned int px;
 583
 584   bb = loop_tree_node->bb;
 585   if (bb != NULL)
 586     {
 587       for (i = 0; i < ira_reg_class_cover_size; i++)
 588         {
 589           curr_reg_pressure[ira_reg_class_cover[i]] = 0;
 590           high_pressure_start_point[ira_reg_class_cover[i]] = -1;
 591         }
 592       curr_bb_node = loop_tree_node;
 593       reg_live_out = DF_LR_OUT (bb);
 594       sparseset_clear (allocnos_live);
 595       REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
 596       AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
 597       AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
 598       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 599         if (TEST_HARD_REG_BIT (hard_regs_live, i))
 600           {
 601             enum reg_class cover_class;
 602
 603             cover_class = REGNO_REG_CLASS (i);
 604             if (cover_class == NO_REGS)
 605               continue;
 606             cover_class = ira_class_translate[cover_class];
 607             curr_reg_pressure[cover_class]++;
 608             if (curr_bb_node->reg_pressure[cover_class]
 609                 < curr_reg_pressure[cover_class])
 610               curr_bb_node->reg_pressure[cover_class]
 611                 = curr_reg_pressure[cover_class];
 612             ira_assert (curr_reg_pressure[cover_class]
 613                         <= ira_available_class_regs[cover_class]);
 614           }
 615       EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
 616         {
 617           ira_allocno_t a = ira_curr_regno_allocno_map[j];
 618
 619           if (a == NULL)
 620             continue;
 621           ira_assert (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)));
 622           set_allocno_live (a);
 623           make_regno_born (j);
 624         }
 625
 626       freq = REG_FREQ_FROM_BB (bb);
 627       if (freq == 0)
 628         freq = 1;
 629
 630       /* Scan the code of this basic block, noting which allocnos and
 631          hard regs are born or die.
 632
 633          Note that this loop treats uninitialized values as live until
 634          the beginning of the block.  For example, if an instruction
 635          uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
 636          set, FOO will remain live until the beginning of the block.
 637          Likewise if FOO is not set at all.  This is unnecessarily
 638          pessimistic, but it probably doesn't matter much in practice.  */
 639       FOR_BB_INSNS_REVERSE (bb, insn)
 640         {
 641           struct df_ref **def_rec, **use_rec;
 642           bool call_p;
 643
 644           if (! INSN_P (insn))
 645             continue;
 646
 647           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 648             fprintf (ira_dump_file, "   Insn %u(l%d): point = %d\n",
 649                      INSN_UID (insn), loop_tree_node->parent->loop->num,
 650                      curr_point);
 651
 652           /* Mark each defined value as live.  We need to do this for
 653              unused values because they still conflict with quantities
 654              that are live at the time of the definition.
 655
 656              Ignore DF_REF_MAY_CLOBBERs on a call instruction.  Such
 657              references represent the effect of the called function
 658              on a call-clobbered register.  Marking the register as
 659              live would stop us from allocating it to a call-crossing
 660              allocno.  */
 661           call_p = CALL_P (insn);
 662           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 663             if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
 664               mark_ref_live (*def_rec);
 665
 666           /* If INSN has multiple outputs, then any value used in one
 667              of the outputs conflicts with the other outputs.  Model this
 668              by making the used value live during the output phase.
 669
 670              It is unsafe to use !single_set here since it will ignore
 671              an unused output.  Just because an output is unused does
 672              not mean the compiler can assume the side effect will not
 673              occur.  Consider if ALLOCNO appears in the address of an
 674              output and we reload the output.  If we allocate ALLOCNO
 675              to the same hard register as an unused output we could
 676              set the hard register before the output reload insn.  */
 677           if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
 678             for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 679               {
 680                 int i;
 681                 rtx reg;
 682
 683                 reg = DF_REF_REG (*use_rec);
 684                 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
 685                   {
 686                     rtx set;
 687
 688                     set = XVECEXP (PATTERN (insn), 0, i);
 689                     if (GET_CODE (set) == SET
 690                         && reg_overlap_mentioned_p (reg, SET_DEST (set)))
 691                       {
 692                         /* After the previous loop, this is a no-op if
 693                            REG is contained within SET_DEST (SET).  */
 694                         mark_ref_live (*use_rec);
 695                         break;
 696                       }
 697                   }
 698               }
 699
 700           extract_insn (insn);
 701           process_single_reg_class_operands (false, freq);
 702
 703           /* See which defined values die here.  */
 704           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 705             if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
 706               mark_ref_dead (*def_rec);
 707
 708           if (call_p)
 709             {
 710               /* The current set of live allocnos are live across the call.  */
 711               EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 712                 {
 713                   ira_allocno_t a = ira_allocnos[i];
 714
 715                   ALLOCNO_CALL_FREQ (a) += freq;
 716                   ALLOCNO_CALLS_CROSSED_NUM (a)++;
 717                   /* Don't allocate allocnos that cross setjmps or any
 718                      call, if this function receives a nonlocal
 719                      goto.  */
 720                   if (cfun->has_nonlocal_label
 721                       || find_reg_note (insn, REG_SETJMP,
 722                                         NULL_RTX) != NULL_RTX)
 723                     {
 724                       SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a));
 725                       SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 726                     }
 727                 }
 728             }
 729
 730           curr_point++;
 731
 732           /* Mark each used value as live.  */
 733           for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 734             mark_ref_live (*use_rec);
 735
 736           /* If any defined values conflict with the inputs, mark those
 737              defined values as live.  */
 738           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 739             if (def_conflicts_with_inputs_p (*def_rec))
 740               mark_ref_live (*def_rec);
 741
 742           process_single_reg_class_operands (true, freq);
 743
 744           /* See which of the defined values we marked as live are dead
 745              before the instruction.  */
 746           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 747             if (def_conflicts_with_inputs_p (*def_rec))
 748               mark_ref_dead (*def_rec);
 749
 750           curr_point++;
 751         }
 752
 753       /* Allocnos can't go in stack regs at the start of a basic block
 754          that is reached by an abnormal edge. Likewise for call
 755          clobbered regs, because caller-save, fixup_abnormal_edges and
 756          possibly the table driven EH machinery are not quite ready to
 757          handle such allocnos live across such edges.  */
 758       FOR_EACH_EDGE (e, ei, bb->preds)
 759         if (e->flags & EDGE_ABNORMAL)
 760           break;
 761
 762       if (e != NULL)
 763         {
 764 #ifdef STACK_REGS
 765           EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
 766             {
 767               ALLOCNO_NO_STACK_REG_P (ira_allocnos[px]) = true;
 768               ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos[px]) = true;
 769             }
 770           for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
 771             make_regno_born (px);
 772 #endif
 773           /* No need to record conflicts for call clobbered regs if we
 774              have nonlocal labels around, as we don't ever try to
 775              allocate such regs in this case.  */
 776           if (!cfun->has_nonlocal_label)
 777             for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
 778               if (call_used_regs[px])
 779                 make_regno_born (px);
 780         }
 781
 782       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 783         {
 784           make_regno_dead (ALLOCNO_REGNO (ira_allocnos[i]));
 785         }
 786
 787       curr_point++;
 788
 789     }
 790   /* Propagate register pressure to upper loop tree nodes: */
 791   if (loop_tree_node != ira_loop_tree_root)
 792     for (i = 0; i < ira_reg_class_cover_size; i++)
 793       {
 794         enum reg_class cover_class;
 795
 796         cover_class = ira_reg_class_cover[i];
 797         if (loop_tree_node->reg_pressure[cover_class]
 798             > loop_tree_node->parent->reg_pressure[cover_class])
 799           loop_tree_node->parent->reg_pressure[cover_class]
 800             = loop_tree_node->reg_pressure[cover_class];
 801       }
 802 }
 803
 804 /* Create and set up IRA_START_POINT_RANGES and
 805    IRA_FINISH_POINT_RANGES.  */
 806 static void
 807 create_start_finish_chains (void)
 808 {
 809   ira_allocno_t a;
 810   ira_allocno_iterator ai;
 811   allocno_live_range_t r;
 812
 813   ira_start_point_ranges
 814     = (allocno_live_range_t *) ira_allocate (ira_max_point
 815                                              * sizeof (allocno_live_range_t));
 816   memset (ira_start_point_ranges, 0,
 817           ira_max_point * sizeof (allocno_live_range_t));
 818   ira_finish_point_ranges
 819     = (allocno_live_range_t *) ira_allocate (ira_max_point
 820                                              * sizeof (allocno_live_range_t));
 821   memset (ira_finish_point_ranges, 0,
 822           ira_max_point * sizeof (allocno_live_range_t));
 823   FOR_EACH_ALLOCNO (a, ai)
 824     {
 825       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
 826         {
 827           r->start_next = ira_start_point_ranges[r->start];
 828           ira_start_point_ranges[r->start] = r;
 829           r->finish_next = ira_finish_point_ranges[r->finish];
 830           ira_finish_point_ranges[r->finish] = r;
 831         }
 832     }
 833 }
 834
 835 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
 836    new live ranges and program points were added as a result if new
 837    insn generation.  */
 838 void
 839 ira_rebuild_start_finish_chains (void)
 840 {
 841   ira_free (ira_finish_point_ranges);
 842   ira_free (ira_start_point_ranges);
 843   create_start_finish_chains ();
 844 }
 845
 846 /* Print live ranges R to file F.  */
 847 void
 848 ira_print_live_range_list (FILE *f, allocno_live_range_t r)
 849 {
 850   for (; r != NULL; r = r->next)
 851     fprintf (f, " [%d..%d]", r->start, r->finish);
 852   fprintf (f, "\n");
 853 }
 854
 855 /* Print live ranges R to stderr.  */
 856 void
 857 ira_debug_live_range_list (allocno_live_range_t r)
 858 {
 859   ira_print_live_range_list (stderr, r);
 860 }
 861
 862 /* Print live ranges of allocno A to file F.  */
 863 static void
 864 print_allocno_live_ranges (FILE *f, ira_allocno_t a)
 865 {
 866   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 867   ira_print_live_range_list (f, ALLOCNO_LIVE_RANGES (a));
 868 }
 869
 870 /* Print live ranges of allocno A to stderr.  */
 871 void
 872 ira_debug_allocno_live_ranges (ira_allocno_t a)
 873 {
 874   print_allocno_live_ranges (stderr, a);
 875 }
 876
 877 /* Print live ranges of all allocnos to file F.  */
 878 static void
 879 print_live_ranges (FILE *f)
 880 {
 881   ira_allocno_t a;
 882   ira_allocno_iterator ai;
 883
 884   FOR_EACH_ALLOCNO (a, ai)
 885     print_allocno_live_ranges (f, a);
 886 }
 887
 888 /* Print live ranges of all allocnos to stderr.  */
 889 void
 890 ira_debug_live_ranges (void)
 891 {
 892   print_live_ranges (stderr);
 893 }
 894
 895 /* The main entry function creates live ranges, set up
 896    CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
 897    calculate register pressure info.  */
 898 void
 899 ira_create_allocno_live_ranges (void)
 900 {
 901   allocnos_live = sparseset_alloc (ira_allocnos_num);
 902   curr_point = 0;
 903   ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
 904                           process_bb_node_lives);
 905   ira_max_point = curr_point;
 906   create_start_finish_chains ();
 907   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 908     print_live_ranges (ira_dump_file);
 909   /* Clean up.  */
 910   sparseset_free (allocnos_live);
 911 }
 912
 913 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES.  */
 914 void
 915 ira_finish_allocno_live_ranges (void)
 916 {
 917   ira_free (ira_finish_point_ranges);
 918   ira_free (ira_start_point_ranges);
 919 }