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