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 (struct 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 (struct 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 /* Mark early clobber registers of the current INSN as live (if
 353    LIVE_P) or dead.  Return true if there are such registers.  */
 354 static bool
 355 mark_early_clobbers (rtx insn, bool live_p)
 356 {
 357   int alt;
 358   int def;
 359   struct df_ref **def_rec;
 360   bool set_p = false;
 361   bool asm_p = asm_noperands (PATTERN (insn)) >= 0;
 362
 363   if (asm_p)
 364     for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 365       if (DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MUST_CLOBBER))
 366         {
 367           if (live_p)
 368             mark_ref_live (*def_rec);
 369           else
 370             mark_ref_dead (*def_rec);
 371           set_p = true;
 372         }
 373
 374   for (def = 0; def < recog_data.n_operands; def++)
 375     {
 376       rtx dreg = recog_data.operand[def];
 377
 378       if (GET_CODE (dreg) == SUBREG)
 379         dreg = SUBREG_REG (dreg);
 380       if (! REG_P (dreg))
 381         continue;
 382
 383       for (alt = 0; alt < recog_data.n_alternatives; alt++)
 384         if ((recog_op_alt[def][alt].earlyclobber)
 385             && (recog_op_alt[def][alt].cl != NO_REGS))
 386           break;
 387
 388       if (alt >= recog_data.n_alternatives)
 389         continue;
 390
 391       if (live_p)
 392         mark_reg_live (dreg);
 393       else
 394         mark_reg_dead (dreg);
 395       set_p = true;
 396     }
 397   return set_p;
 398 }
 399
 400 /* Checks that CONSTRAINTS permits to use only one hard register.  If
 401    it is so, the function returns the class of the hard register.
 402    Otherwise it returns NO_REGS.  */
 403 static enum reg_class
 404 single_reg_class (const char *constraints, rtx op, rtx equiv_const)
 405 {
 406   int ignore_p;
 407   enum reg_class cl, next_cl;
 408   int c;
 409
 410   cl = NO_REGS;
 411   for (ignore_p = false;
 412        (c = *constraints);
 413        constraints += CONSTRAINT_LEN (c, constraints))
 414     if (c == '#')
 415       ignore_p = true;
 416     else if (c == ',')
 417       ignore_p = false;
 418     else if (! ignore_p)
 419       switch (c)
 420         {
 421         case ' ':
 422         case '\t':
 423         case '=':
 424         case '+':
 425         case '*':
 426         case '&':
 427         case '%':
 428         case '!':
 429         case '?':
 430           break;
 431         case 'i':
 432           if (CONSTANT_P (op)
 433               || (equiv_const != NULL_RTX && CONSTANT_P (equiv_const)))
 434             return NO_REGS;
 435           break;
 436
 437         case 'n':
 438           if (GET_CODE (op) == CONST_INT
 439               || (GET_CODE (op) == CONST_DOUBLE && GET_MODE (op) == VOIDmode)
 440               || (equiv_const != NULL_RTX
 441                   && (GET_CODE (equiv_const) == CONST_INT
 442                       || (GET_CODE (equiv_const) == CONST_DOUBLE
 443                           && GET_MODE (equiv_const) == VOIDmode))))
 444             return NO_REGS;
 445           break;
 446
 447         case 's':
 448           if ((CONSTANT_P (op) && GET_CODE (op) != CONST_INT
 449                && (GET_CODE (op) != CONST_DOUBLE || GET_MODE (op) != VOIDmode))
 450               || (equiv_const != NULL_RTX
 451                   && CONSTANT_P (equiv_const)
 452                   && GET_CODE (equiv_const) != CONST_INT
 453                   && (GET_CODE (equiv_const) != CONST_DOUBLE
 454                       || GET_MODE (equiv_const) != VOIDmode)))
 455             return NO_REGS;
 456           break;
 457
 458         case 'I':
 459         case 'J':
 460         case 'K':
 461         case 'L':
 462         case 'M':
 463         case 'N':
 464         case 'O':
 465         case 'P':
 466           if ((GET_CODE (op) == CONST_INT
 467                && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, constraints))
 468               || (equiv_const != NULL_RTX
 469                   && GET_CODE (equiv_const) == CONST_INT
 470                   && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
 471                                                 c, constraints)))
 472             return NO_REGS;
 473           break;
 474
 475         case 'E':
 476         case 'F':
 477           if (GET_CODE (op) == CONST_DOUBLE
 478               || (GET_CODE (op) == CONST_VECTOR
 479                   && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT)
 480               || (equiv_const != NULL_RTX
 481                   && (GET_CODE (equiv_const) == CONST_DOUBLE
 482                       || (GET_CODE (equiv_const) == CONST_VECTOR
 483                           && (GET_MODE_CLASS (GET_MODE (equiv_const))
 484                               == MODE_VECTOR_FLOAT)))))
 485             return NO_REGS;
 486           break;
 487
 488         case 'G':
 489         case 'H':
 490           if ((GET_CODE (op) == CONST_DOUBLE
 491                && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, constraints))
 492               || (equiv_const != NULL_RTX
 493                   && GET_CODE (equiv_const) == CONST_DOUBLE
 494                   && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const,
 495                                                        c, constraints)))
 496             return NO_REGS;
 497           /* ??? what about memory */
 498         case 'r':
 499         case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
 500         case 'h': case 'j': case 'k': case 'l':
 501         case 'q': case 't': case 'u':
 502         case 'v': case 'w': case 'x': case 'y': case 'z':
 503         case 'A': case 'B': case 'C': case 'D':
 504         case 'Q': case 'R': case 'S': case 'T': case 'U':
 505         case 'W': case 'Y': case 'Z':
 506           next_cl = (c == 'r'
 507                      ? GENERAL_REGS
 508                      : REG_CLASS_FROM_CONSTRAINT (c, constraints));
 509           if ((cl != NO_REGS && next_cl != cl)
 510               || ira_available_class_regs[next_cl] > 1)
 511             return NO_REGS;
 512           cl = next_cl;
 513           break;
 514
 515         case '0': case '1': case '2': case '3': case '4':
 516         case '5': case '6': case '7': case '8': case '9':
 517           next_cl
 518             = single_reg_class (recog_data.constraints[c - '0'],
 519                                 recog_data.operand[c - '0'], NULL_RTX);
 520           if ((cl != NO_REGS && next_cl != cl) || next_cl == NO_REGS
 521               || ira_available_class_regs[next_cl] > 1)
 522             return NO_REGS;
 523           cl = next_cl;
 524           break;
 525
 526         default:
 527           return NO_REGS;
 528         }
 529   return cl;
 530 }
 531
 532 /* The function checks that operand OP_NUM of the current insn can use
 533    only one hard register.  If it is so, the function returns the
 534    class of the hard register.  Otherwise it returns NO_REGS.  */
 535 static enum reg_class
 536 single_reg_operand_class (int op_num)
 537 {
 538   if (op_num < 0 || recog_data.n_alternatives == 0)
 539     return NO_REGS;
 540   return single_reg_class (recog_data.constraints[op_num],
 541                            recog_data.operand[op_num], NULL_RTX);
 542 }
 543
 544 /* Processes input operands, if IN_P, or output operands otherwise of
 545    the current insn with FREQ to find allocno which can use only one
 546    hard register and makes other currently living allocnos conflicting
 547    with the hard register.  */
 548 static void
 549 process_single_reg_class_operands (bool in_p, int freq)
 550 {
 551   int i, regno, cost;
 552   unsigned int px;
 553   enum reg_class cl, cover_class;
 554   rtx operand;
 555   ira_allocno_t operand_a, a;
 556
 557   for (i = 0; i < recog_data.n_operands; i++)
 558     {
 559       operand = recog_data.operand[i];
 560       if (in_p && recog_data.operand_type[i] != OP_IN
 561           && recog_data.operand_type[i] != OP_INOUT)
 562         continue;
 563       if (! in_p && recog_data.operand_type[i] != OP_OUT
 564           && recog_data.operand_type[i] != OP_INOUT)
 565         continue;
 566       cl = single_reg_operand_class (i);
 567       if (cl == NO_REGS)
 568         continue;
 569
 570       operand_a = NULL;
 571
 572       if (GET_CODE (operand) == SUBREG)
 573         operand = SUBREG_REG (operand);
 574
 575       if (REG_P (operand)
 576           && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
 577         {
 578           enum machine_mode mode;
 579           enum reg_class cover_class;
 580
 581           operand_a = ira_curr_regno_allocno_map[regno];
 582           mode = ALLOCNO_MODE (operand_a);
 583           cover_class = ALLOCNO_COVER_CLASS (operand_a);
 584           if (ira_class_subset_p[cl][cover_class]
 585               && ira_class_hard_regs_num[cl] != 0
 586               && (ira_class_hard_reg_index[cover_class]
 587                   [ira_class_hard_regs[cl][0]]) >= 0
 588               && reg_class_size[cl] <= (unsigned) CLASS_MAX_NREGS (cl, mode))
 589             {
 590               /* ??? FREQ */
 591               cost = freq * (in_p
 592                              ? ira_register_move_cost[mode][cover_class][cl]
 593                              : ira_register_move_cost[mode][cl][cover_class]);
 594               ira_allocate_and_set_costs
 595                 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), cover_class, 0);
 596               ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
 597                 [ira_class_hard_reg_index
 598                  [cover_class][ira_class_hard_regs[cl][0]]]
 599                 -= cost;
 600             }
 601         }
 602
 603       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
 604         {
 605           a = ira_allocnos[px];
 606           cover_class = ALLOCNO_COVER_CLASS (a);
 607           if (a != operand_a)
 608             {
 609               /* We could increase costs of A instead of making it
 610                  conflicting with the hard register.  But it works worse
 611                  because it will be spilled in reload in anyway.  */
 612               IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 613                                 reg_class_contents[cl]);
 614               IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 615                                 reg_class_contents[cl]);
 616             }
 617         }
 618     }
 619 }
 620
 621 /* Process insns of the basic block given by its LOOP_TREE_NODE to
 622    update allocno live ranges, allocno hard register conflicts,
 623    intersected calls, and register pressure info for allocnos for the
 624    basic block for and regions containing the basic block.  */
 625 static void
 626 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
 627 {
 628   int i, freq;
 629   unsigned int j;
 630   basic_block bb;
 631   rtx insn;
 632   edge e;
 633   edge_iterator ei;
 634   bitmap_iterator bi;
 635   bitmap reg_live_out;
 636   unsigned int px;
 637   bool set_p;
 638
 639   bb = loop_tree_node->bb;
 640   if (bb != NULL)
 641     {
 642       for (i = 0; i < ira_reg_class_cover_size; i++)
 643         {
 644           curr_reg_pressure[ira_reg_class_cover[i]] = 0;
 645           high_pressure_start_point[ira_reg_class_cover[i]] = -1;
 646         }
 647       curr_bb_node = loop_tree_node;
 648       reg_live_out = DF_LR_OUT (bb);
 649       sparseset_clear (allocnos_live);
 650       REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
 651       AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
 652       AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
 653       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 654         if (TEST_HARD_REG_BIT (hard_regs_live, i))
 655           {
 656             enum reg_class cover_class;
 657
 658             cover_class = REGNO_REG_CLASS (i);
 659             if (cover_class == NO_REGS)
 660               continue;
 661             cover_class = ira_class_translate[cover_class];
 662             curr_reg_pressure[cover_class]++;
 663             if (curr_bb_node->reg_pressure[cover_class]
 664                 < curr_reg_pressure[cover_class])
 665               curr_bb_node->reg_pressure[cover_class]
 666                 = curr_reg_pressure[cover_class];
 667             ira_assert (curr_reg_pressure[cover_class]
 668                         <= ira_available_class_regs[cover_class]);
 669           }
 670       EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
 671         {
 672           ira_allocno_t a = ira_curr_regno_allocno_map[j];
 673
 674           if (a == NULL)
 675             continue;
 676           ira_assert (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)));
 677           set_allocno_live (a);
 678           make_regno_born (j);
 679         }
 680
 681       freq = REG_FREQ_FROM_BB (bb);
 682       if (freq == 0)
 683         freq = 1;
 684
 685       /* Scan the code of this basic block, noting which allocnos and
 686          hard regs are born or die.
 687
 688          Note that this loop treats uninitialized values as live until
 689          the beginning of the block.  For example, if an instruction
 690          uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
 691          set, FOO will remain live until the beginning of the block.
 692          Likewise if FOO is not set at all.  This is unnecessarily
 693          pessimistic, but it probably doesn't matter much in practice.  */
 694       FOR_BB_INSNS_REVERSE (bb, insn)
 695         {
 696           struct df_ref **def_rec, **use_rec;
 697           bool call_p;
 698
 699           if (! INSN_P (insn))
 700             continue;
 701
 702           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 703             fprintf (ira_dump_file, "   Insn %u(l%d): point = %d\n",
 704                      INSN_UID (insn), loop_tree_node->parent->loop->num,
 705                      curr_point);
 706
 707           /* Mark each defined value as live.  We need to do this for
 708              unused values because they still conflict with quantities
 709              that are live at the time of the definition.
 710
 711              Ignore DF_REF_MAY_CLOBBERs on a call instruction.  Such
 712              references represent the effect of the called function
 713              on a call-clobbered register.  Marking the register as
 714              live would stop us from allocating it to a call-crossing
 715              allocno.  */
 716           call_p = CALL_P (insn);
 717           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 718             if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
 719               mark_ref_live (*def_rec);
 720
 721           /* If INSN has multiple outputs, then any value used in one
 722              of the outputs conflicts with the other outputs.  Model this
 723              by making the used value live during the output phase.
 724
 725              It is unsafe to use !single_set here since it will ignore
 726              an unused output.  Just because an output is unused does
 727              not mean the compiler can assume the side effect will not
 728              occur.  Consider if ALLOCNO appears in the address of an
 729              output and we reload the output.  If we allocate ALLOCNO
 730              to the same hard register as an unused output we could
 731              set the hard register before the output reload insn.  */
 732           if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
 733             for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 734               {
 735                 int i;
 736                 rtx reg;
 737
 738                 reg = DF_REF_REG (*use_rec);
 739                 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
 740                   {
 741                     rtx set;
 742
 743                     set = XVECEXP (PATTERN (insn), 0, i);
 744                     if (GET_CODE (set) == SET
 745                         && reg_overlap_mentioned_p (reg, SET_DEST (set)))
 746                       {
 747                         /* After the previous loop, this is a no-op if
 748                            REG is contained within SET_DEST (SET).  */
 749                         mark_ref_live (*use_rec);
 750                         break;
 751                       }
 752                   }
 753               }
 754
 755           extract_insn (insn);
 756           preprocess_constraints ();
 757           process_single_reg_class_operands (false, freq);
 758
 759           /* See which defined values die here.  */
 760           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 761             if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
 762               mark_ref_dead (*def_rec);
 763
 764           if (call_p)
 765             {
 766               /* The current set of live allocnos are live across the call.  */
 767               EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 768                 {
 769                   ira_allocno_t a = ira_allocnos[i];
 770
 771                   ALLOCNO_CALL_FREQ (a) += freq;
 772                   ALLOCNO_CALLS_CROSSED_NUM (a)++;
 773                   /* Don't allocate allocnos that cross setjmps or any
 774                      call, if this function receives a nonlocal
 775                      goto.  */
 776                   if (cfun->has_nonlocal_label
 777                       || find_reg_note (insn, REG_SETJMP,
 778                                         NULL_RTX) != NULL_RTX)
 779                     {
 780                       SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a));
 781                       SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 782                     }
 783                 }
 784             }
 785
 786           curr_point++;
 787
 788           /* Mark each used value as live.  */
 789           for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 790             mark_ref_live (*use_rec);
 791
 792           set_p = mark_early_clobbers (insn, true);
 793
 794           process_single_reg_class_operands (true, freq);
 795
 796           if (set_p)
 797             mark_early_clobbers (insn, false);
 798
 799           curr_point++;
 800         }
 801
 802       /* Allocnos can't go in stack regs at the start of a basic block
 803          that is reached by an abnormal edge. Likewise for call
 804          clobbered regs, because caller-save, fixup_abnormal_edges and
 805          possibly the table driven EH machinery are not quite ready to
 806          handle such allocnos live across such edges.  */
 807       FOR_EACH_EDGE (e, ei, bb->preds)
 808         if (e->flags & EDGE_ABNORMAL)
 809           break;
 810
 811       if (e != NULL)
 812         {
 813 #ifdef STACK_REGS
 814           EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
 815             {
 816               ALLOCNO_NO_STACK_REG_P (ira_allocnos[px]) = true;
 817               ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos[px]) = true;
 818             }
 819           for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
 820             make_regno_born (px);
 821 #endif
 822           /* No need to record conflicts for call clobbered regs if we
 823              have nonlocal labels around, as we don't ever try to
 824              allocate such regs in this case.  */
 825           if (!cfun->has_nonlocal_label)
 826             for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
 827               if (call_used_regs[px])
 828                 make_regno_born (px);
 829         }
 830
 831       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 832         {
 833           make_regno_dead (ALLOCNO_REGNO (ira_allocnos[i]));
 834         }
 835
 836       curr_point++;
 837
 838     }
 839   /* Propagate register pressure to upper loop tree nodes: */
 840   if (loop_tree_node != ira_loop_tree_root)
 841     for (i = 0; i < ira_reg_class_cover_size; i++)
 842       {
 843         enum reg_class cover_class;
 844
 845         cover_class = ira_reg_class_cover[i];
 846         if (loop_tree_node->reg_pressure[cover_class]
 847             > loop_tree_node->parent->reg_pressure[cover_class])
 848           loop_tree_node->parent->reg_pressure[cover_class]
 849             = loop_tree_node->reg_pressure[cover_class];
 850       }
 851 }
 852
 853 /* Create and set up IRA_START_POINT_RANGES and
 854    IRA_FINISH_POINT_RANGES.  */
 855 static void
 856 create_start_finish_chains (void)
 857 {
 858   ira_allocno_t a;
 859   ira_allocno_iterator ai;
 860   allocno_live_range_t r;
 861
 862   ira_start_point_ranges
 863     = (allocno_live_range_t *) ira_allocate (ira_max_point
 864                                              * sizeof (allocno_live_range_t));
 865   memset (ira_start_point_ranges, 0,
 866           ira_max_point * sizeof (allocno_live_range_t));
 867   ira_finish_point_ranges
 868     = (allocno_live_range_t *) ira_allocate (ira_max_point
 869                                              * sizeof (allocno_live_range_t));
 870   memset (ira_finish_point_ranges, 0,
 871           ira_max_point * sizeof (allocno_live_range_t));
 872   FOR_EACH_ALLOCNO (a, ai)
 873     {
 874       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
 875         {
 876           r->start_next = ira_start_point_ranges[r->start];
 877           ira_start_point_ranges[r->start] = r;
 878           r->finish_next = ira_finish_point_ranges[r->finish];
 879           ira_finish_point_ranges[r->finish] = r;
 880         }
 881     }
 882 }
 883
 884 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
 885    new live ranges and program points were added as a result if new
 886    insn generation.  */
 887 void
 888 ira_rebuild_start_finish_chains (void)
 889 {
 890   ira_free (ira_finish_point_ranges);
 891   ira_free (ira_start_point_ranges);
 892   create_start_finish_chains ();
 893 }
 894
 895 /* Compress allocno live ranges by removing program points where
 896    nothing happens.  */
 897 static void
 898 remove_some_program_points_and_update_live_ranges (void)
 899 {
 900   unsigned i;
 901   int n;
 902   int *map;
 903   ira_allocno_t a;
 904   ira_allocno_iterator ai;
 905   allocno_live_range_t r;
 906   bitmap born_or_died;
 907   bitmap_iterator bi;
 908
 909   born_or_died = ira_allocate_bitmap ();
 910   FOR_EACH_ALLOCNO (a, ai)
 911     {
 912       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
 913         {
 914           ira_assert (r->start <= r->finish);
 915           bitmap_set_bit (born_or_died, r->start);
 916           bitmap_set_bit (born_or_died, r->finish);
 917         }
 918     }
 919   map = (int *) ira_allocate (sizeof (int) * ira_max_point);
 920   n = 0;
 921   EXECUTE_IF_SET_IN_BITMAP(born_or_died, 0, i, bi)
 922     {
 923       map[i] = n++;
 924     }
 925   ira_free_bitmap (born_or_died);
 926   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
 927     fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
 928              ira_max_point, n, 100 * n / ira_max_point);
 929   ira_max_point = n;
 930   FOR_EACH_ALLOCNO (a, ai)
 931     {
 932       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
 933         {
 934           r->start = map[r->start];
 935           r->finish = map[r->finish];
 936         }
 937     }
 938   ira_free (map);
 939 }
 940
 941 /* Print live ranges R to file F.  */
 942 void
 943 ira_print_live_range_list (FILE *f, allocno_live_range_t r)
 944 {
 945   for (; r != NULL; r = r->next)
 946     fprintf (f, " [%d..%d]", r->start, r->finish);
 947   fprintf (f, "\n");
 948 }
 949
 950 /* Print live ranges R to stderr.  */
 951 void
 952 ira_debug_live_range_list (allocno_live_range_t r)
 953 {
 954   ira_print_live_range_list (stderr, r);
 955 }
 956
 957 /* Print live ranges of allocno A to file F.  */
 958 static void
 959 print_allocno_live_ranges (FILE *f, ira_allocno_t a)
 960 {
 961   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 962   ira_print_live_range_list (f, ALLOCNO_LIVE_RANGES (a));
 963 }
 964
 965 /* Print live ranges of allocno A to stderr.  */
 966 void
 967 ira_debug_allocno_live_ranges (ira_allocno_t a)
 968 {
 969   print_allocno_live_ranges (stderr, a);
 970 }
 971
 972 /* Print live ranges of all allocnos to file F.  */
 973 static void
 974 print_live_ranges (FILE *f)
 975 {
 976   ira_allocno_t a;
 977   ira_allocno_iterator ai;
 978
 979   FOR_EACH_ALLOCNO (a, ai)
 980     print_allocno_live_ranges (f, a);
 981 }
 982
 983 /* Print live ranges of all allocnos to stderr.  */
 984 void
 985 ira_debug_live_ranges (void)
 986 {
 987   print_live_ranges (stderr);
 988 }
 989
 990 /* The main entry function creates live ranges, set up
 991    CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
 992    calculate register pressure info.  */
 993 void
 994 ira_create_allocno_live_ranges (void)
 995 {
 996   allocnos_live = sparseset_alloc (ira_allocnos_num);
 997   curr_point = 0;
 998   ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
 999                           process_bb_node_lives);
1000   ira_max_point = curr_point;
1001   create_start_finish_chains ();
1002   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1003     print_live_ranges (ira_dump_file);
1004   /* Clean up.  */
1005   sparseset_free (allocnos_live);
1006 }
1007
1008 /* Compress allocno live ranges.  */
1009 void
1010 ira_compress_allocno_live_ranges (void)
1011 {
1012   remove_some_program_points_and_update_live_ranges ();
1013   ira_rebuild_start_finish_chains ();
1014   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1015     {
1016       fprintf (ira_dump_file, "Ranges after the compression:\n");
1017       print_live_ranges (ira_dump_file);
1018     }
1019 }
1020
1021 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES.  */
1022 void
1023 ira_finish_allocno_live_ranges (void)
1024 {
1025   ira_free (ira_finish_point_ranges);
1026   ira_free (ira_start_point_ranges);
1027 }