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 static void make_regno_born (int);
  46 static void update_allocno_pressure_excess_length (allocno_t);
  47 static void make_regno_dead (int);
  48 static void make_regno_born_and_dead (int);
  49 static void set_allocno_live (allocno_t);
  50 static void clear_allocno_live (allocno_t);
  51 static void mark_reg_store (rtx, const_rtx, void *);
  52 static void mark_reg_clobber (rtx, const_rtx, void *);
  53 static void mark_reg_conflicts (rtx);
  54 static void mark_reg_death (rtx);
  55 static enum reg_class single_reg_class (const char *, rtx op, rtx);
  56 static enum reg_class single_reg_operand_class (int);
  57 static void process_single_reg_class_operands (int, int);
  58 static void process_bb_node_lives (loop_tree_node_t);
  59 static void create_start_finish_chains (void);
  60 static void print_allocno_live_ranges (FILE *, allocno_t);
  61 static void print_live_ranges (FILE *);
  62 static void propagate_new_allocno_info (allocno_t);
  63 static void propagate_new_info (void);
  64
  65 /* Program points are enumerated by number from range 0..MAX_POINT-1.
  66    There are approximately tow times more program points than insns.
  67    One program points correspond points between subsequent insns and
  68    other ones correspond to points after usage of input operands but
  69    before setting the output operands in insns.  */
  70 int max_point;
  71
  72 /* Arrays of size MAX_POINT mapping a program point to the allocno
  73    live ranges with given start/finish point.  */
  74 allocno_live_range_t *start_point_ranges, *finish_point_ranges;
  75
  76 /* Number of the current program point.  */
  77 static int curr_point;
  78
  79 /* Point where register pressure excess started or -1 if there is no
  80    register pressure excess.  Excess pressure for a register class at
  81    some point means that there are more allocnos of given register
  82    class living at the point than number of hard-registers of the
  83    class available for the allocation.  It is defined only for cover
  84    classes.  */
  85 static int high_pressure_start_point[N_REG_CLASSES];
  86
  87 /* Allocnos live at current point in the scan.  */
  88 static sparseset allocnos_live;
  89
  90 /* Set of hard regs (except eliminable ones) currently live.  */
  91 static HARD_REG_SET hard_regs_live;
  92
  93 /* The loop tree node corresponding to the current basic block.  */
  94 static loop_tree_node_t curr_bb_node;
  95
  96 /* The function processing birth of register REGNO.  It updates living
  97    hard regs and conflict hard regs for living allocnos or starts a
  98    new live range for the allocno corresponding to REGNO if it is
  99    necessary.  */
 100 static void
 101 make_regno_born (int regno)
 102 {
 103   unsigned int i;
 104   allocno_t a;
 105   allocno_live_range_t p;
 106
 107   if (regno < FIRST_PSEUDO_REGISTER)
 108     {
 109       SET_HARD_REG_BIT (hard_regs_live, regno);
 110       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 111         {
 112           SET_HARD_REG_BIT (ALLOCNO_CONFLICT_HARD_REGS (allocnos[i]), regno);
 113           SET_HARD_REG_BIT (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (allocnos[i]),
 114                             regno);
 115         }
 116       return;
 117     }
 118   a = ira_curr_regno_allocno_map[regno];
 119   if (a == NULL)
 120     return;
 121   if ((p = ALLOCNO_LIVE_RANGES (a)) == NULL
 122       || (p->finish != curr_point && p->finish + 1 != curr_point))
 123     ALLOCNO_LIVE_RANGES (a)
 124       = create_allocno_live_range (a, curr_point, -1, ALLOCNO_LIVE_RANGES (a));
 125 }
 126
 127 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for allocno A.  */
 128 static void
 129 update_allocno_pressure_excess_length (allocno_t a)
 130 {
 131   int start;
 132   enum reg_class cover_class;
 133   allocno_live_range_t p;
 134
 135   cover_class = ALLOCNO_COVER_CLASS (a);
 136   if (high_pressure_start_point[cover_class] < 0)
 137     return;
 138   p = ALLOCNO_LIVE_RANGES (a);
 139   ira_assert (p != NULL);
 140   start = (high_pressure_start_point[cover_class] > p->start
 141            ? high_pressure_start_point[cover_class] : p->start);
 142   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) += curr_point - start + 1;
 143 }
 144
 145 /* The function processing death of register REGNO.  It updates live
 146    hard regs or finish the current live range for the allocno
 147    corresponding to REGNO.  */
 148 static void
 149 make_regno_dead (int regno)
 150 {
 151   allocno_t a;
 152   allocno_live_range_t p;
 153
 154   if (regno < FIRST_PSEUDO_REGISTER)
 155     {
 156       CLEAR_HARD_REG_BIT (hard_regs_live, regno);
 157       return;
 158     }
 159   a = ira_curr_regno_allocno_map[regno];
 160   if (a == NULL)
 161     return;
 162   p = ALLOCNO_LIVE_RANGES (a);
 163   ira_assert (p != NULL);
 164   p->finish = curr_point;
 165   update_allocno_pressure_excess_length (a);
 166 }
 167
 168 /* The function processing birth and, right after then, death of
 169    register REGNO.  */
 170 static void
 171 make_regno_born_and_dead (int regno)
 172 {
 173   make_regno_born (regno);
 174   make_regno_dead (regno);
 175 }
 176
 177 /* The current register pressures for each cover class for the current
 178    basic block.  */
 179 static int curr_reg_pressure[N_REG_CLASSES];
 180
 181 /* The function marks allocno A as currently living and updates
 182    current register pressure, maximal register pressure for the
 183    current BB, start point of the register pressure excess, and
 184    conflicting hard registers of A.  */
 185 static void
 186 set_allocno_live (allocno_t a)
 187 {
 188   int nregs;
 189   enum reg_class cover_class;
 190
 191   if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
 192     return;
 193   sparseset_set_bit (allocnos_live, ALLOCNO_NUM (a));
 194   IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), hard_regs_live);
 195   IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), hard_regs_live);
 196   cover_class = ALLOCNO_COVER_CLASS (a);
 197   nregs = reg_class_nregs[cover_class][ALLOCNO_MODE (a)];
 198   curr_reg_pressure[cover_class] += nregs;
 199   if (high_pressure_start_point[cover_class] < 0
 200       && curr_reg_pressure[cover_class] > available_class_regs[cover_class])
 201     high_pressure_start_point[cover_class] = curr_point;
 202   if (curr_bb_node->reg_pressure[cover_class]
 203       < curr_reg_pressure[cover_class])
 204     curr_bb_node->reg_pressure[cover_class] = curr_reg_pressure[cover_class];
 205 }
 206
 207 /* The function marks allocno A as currently not living and updates
 208    current register pressure, start point of the register pressure
 209    excess, and register pressure excess length for living
 210    allocnos.  */
 211 static void
 212 clear_allocno_live (allocno_t a)
 213 {
 214   unsigned int i;
 215   enum reg_class cover_class;
 216
 217   if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
 218     {
 219       cover_class = ALLOCNO_COVER_CLASS (a);
 220       curr_reg_pressure[cover_class]
 221         -= reg_class_nregs[cover_class][ALLOCNO_MODE (a)];
 222       ira_assert (curr_reg_pressure[cover_class] >= 0);
 223       if (high_pressure_start_point[cover_class] >= 0
 224           && (curr_reg_pressure[cover_class]
 225               <= available_class_regs[cover_class]))
 226         {
 227           EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 228             {
 229               update_allocno_pressure_excess_length (allocnos[i]);
 230             }
 231           high_pressure_start_point[cover_class] = -1;
 232         }
 233     }
 234   sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (a));
 235 }
 236
 237 /* Record all regs that are set in any one insn.  Communication from
 238    mark_reg_{store,clobber}.  */
 239 static VEC(rtx, heap) *regs_set;
 240
 241 /* Handle the case where REG is set by the insn being scanned, during
 242    the scan to build live ranges and calculate reg pressure info.
 243    Store a 1 in hard_regs_live or allocnos_live for this register or
 244    the corresponding allocno, record how many consecutive hardware
 245    registers it actually needs.
 246
 247    Note that even if REG does not remain alive after this insn, we
 248    must mark it here as live, to ensure a conflict between REG and any
 249    other reg allocnos set in this insn that really do live.  This is
 250    because those other allocnos could be considered after this.
 251
 252    REG might actually be something other than a register; if so, we do
 253    nothing.
 254
 255    SETTER is 0 if this register was modified by an auto-increment
 256    (i.e., a REG_INC note was found for it).  */
 257 static void
 258 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
 259                 void *data ATTRIBUTE_UNUSED)
 260 {
 261   int regno;
 262
 263   if (GET_CODE (reg) == SUBREG)
 264     reg = SUBREG_REG (reg);
 265
 266   if (! REG_P (reg))
 267     return;
 268
 269   VEC_safe_push (rtx, heap, regs_set, reg);
 270
 271   regno = REGNO (reg);
 272
 273   if (regno >= FIRST_PSEUDO_REGISTER)
 274     {
 275       allocno_t a = ira_curr_regno_allocno_map[regno];
 276
 277       if (a != NULL)
 278         {
 279           if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
 280             return;
 281           set_allocno_live (a);
 282         }
 283       make_regno_born (regno);
 284     }
 285   else if (! TEST_HARD_REG_BIT (no_alloc_regs, regno))
 286     {
 287       int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
 288       enum reg_class cover_class;
 289
 290       while (regno < last)
 291         {
 292           if (! TEST_HARD_REG_BIT (hard_regs_live, regno)
 293               && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
 294             {
 295               cover_class = class_translate[REGNO_REG_CLASS (regno)];
 296               if (cover_class != NO_REGS)
 297                 {
 298                   curr_reg_pressure[cover_class]++;
 299                   if (high_pressure_start_point[cover_class] < 0
 300                       && (curr_reg_pressure[cover_class]
 301                           > available_class_regs[cover_class]))
 302                     high_pressure_start_point[cover_class] = curr_point;
 303                 }
 304               make_regno_born (regno);
 305               if (cover_class != NO_REGS
 306                   && (curr_bb_node->reg_pressure[cover_class]
 307                       < curr_reg_pressure[cover_class]))
 308                 curr_bb_node->reg_pressure[cover_class]
 309                   = curr_reg_pressure[cover_class];
 310             }
 311           regno++;
 312         }
 313     }
 314 }
 315
 316 /* Like mark_reg_store except notice just CLOBBERs; ignore SETs.  */
 317 static void
 318 mark_reg_clobber (rtx reg, const_rtx setter, void *data)
 319 {
 320   if (GET_CODE (setter) == CLOBBER)
 321     mark_reg_store (reg, setter, data);
 322 }
 323
 324 /* Record that hard register REG (if it is a hard register) has
 325    conflicts with all the allocno currently live or the corresponding
 326    allocno lives at just the current program point.  Do not mark REG
 327    (or the allocno) itself as live.  */
 328 static void
 329 mark_reg_conflicts (rtx reg)
 330 {
 331   int regno;
 332
 333   if (GET_CODE (reg) == SUBREG)
 334     reg = SUBREG_REG (reg);
 335
 336   if (! REG_P (reg))
 337     return;
 338
 339   regno = REGNO (reg);
 340
 341   if (regno >= FIRST_PSEUDO_REGISTER)
 342     make_regno_born_and_dead (regno);
 343   else if (! TEST_HARD_REG_BIT (no_alloc_regs, regno))
 344     {
 345       int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
 346
 347       while (regno < last)
 348         {
 349           make_regno_born_and_dead (regno);
 350           regno++;
 351         }
 352     }
 353 }
 354
 355 /* Mark REG (or the corresponding allocno) as being dead (following
 356    the insn being scanned now).  Store a 0 in hard_regs_live or
 357    allocnos_live for the register.  */
 358 static void
 359 mark_reg_death (rtx reg)
 360 {
 361   unsigned int i;
 362   int regno = REGNO (reg);
 363
 364   if (regno >= FIRST_PSEUDO_REGISTER)
 365     {
 366       allocno_t a = ira_curr_regno_allocno_map[regno];
 367
 368       if (a != NULL)
 369         {
 370           if (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
 371             return;
 372           clear_allocno_live (a);
 373         }
 374       make_regno_dead (regno);
 375     }
 376   else if (! TEST_HARD_REG_BIT (no_alloc_regs, regno))
 377     {
 378       int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
 379       enum reg_class cover_class;
 380
 381       while (regno < last)
 382         {
 383           if (TEST_HARD_REG_BIT (hard_regs_live, regno))
 384             {
 385               cover_class = class_translate[REGNO_REG_CLASS (regno)];
 386               if (cover_class != NO_REGS)
 387                 {
 388                   curr_reg_pressure[cover_class]--;
 389                   if (high_pressure_start_point[cover_class] >= 0
 390                       && (curr_reg_pressure[cover_class]
 391                           <= available_class_regs[cover_class]))
 392                     {
 393                       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 394                         {
 395                           update_allocno_pressure_excess_length (allocnos[i]);
 396                         }
 397                       high_pressure_start_point[cover_class] = -1;
 398                     }
 399                   ira_assert (curr_reg_pressure[cover_class] >= 0);
 400                 }
 401               make_regno_dead (regno);
 402             }
 403           regno++;
 404         }
 405     }
 406 }
 407
 408 /* The function checks that CONSTRAINTS permits to use only one hard
 409    register.  If it is so, the function returns the class of the hard
 410    register.  Otherwise it returns NO_REGS.  */
 411 static enum reg_class
 412 single_reg_class (const char *constraints, rtx op, rtx equiv_const)
 413 {
 414   int ignore_p;
 415   enum reg_class cl, next_cl;
 416   int c;
 417
 418   cl = NO_REGS;
 419   for (ignore_p = FALSE;
 420        (c = *constraints);
 421        constraints += CONSTRAINT_LEN (c, constraints))
 422     if (c == '#')
 423       ignore_p = TRUE;
 424     else if (c == ',')
 425       ignore_p = FALSE;
 426     else if (! ignore_p)
 427       switch (c)
 428         {
 429         case ' ':
 430         case '\t':
 431         case '=':
 432         case '+':
 433         case '*':
 434         case '&':
 435         case '%':
 436         case '!':
 437         case '?':
 438           break;
 439         case 'i':
 440           if (CONSTANT_P (op)
 441               || (equiv_const != NULL_RTX && CONSTANT_P (equiv_const)))
 442             return NO_REGS;
 443           break;
 444
 445         case 'n':
 446           if (GET_CODE (op) == CONST_INT
 447               || (GET_CODE (op) == CONST_DOUBLE && GET_MODE (op) == VOIDmode)
 448               || (equiv_const != NULL_RTX
 449                   && (GET_CODE (equiv_const) == CONST_INT
 450                       || (GET_CODE (equiv_const) == CONST_DOUBLE
 451                           && GET_MODE (equiv_const) == VOIDmode))))
 452             return NO_REGS;
 453           break;
 454
 455         case 's':
 456           if ((CONSTANT_P (op) && GET_CODE (op) != CONST_INT
 457                && (GET_CODE (op) != CONST_DOUBLE || GET_MODE (op) != VOIDmode))
 458               || (equiv_const != NULL_RTX
 459                   && CONSTANT_P (equiv_const)
 460                   && GET_CODE (equiv_const) != CONST_INT
 461                   && (GET_CODE (equiv_const) != CONST_DOUBLE
 462                       || GET_MODE (equiv_const) != VOIDmode)))
 463             return NO_REGS;
 464           break;
 465
 466         case 'I':
 467         case 'J':
 468         case 'K':
 469         case 'L':
 470         case 'M':
 471         case 'N':
 472         case 'O':
 473         case 'P':
 474           if ((GET_CODE (op) == CONST_INT
 475                && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, constraints))
 476               || (equiv_const != NULL_RTX
 477                   && GET_CODE (equiv_const) == CONST_INT
 478                   && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
 479                                                 c, constraints)))
 480             return NO_REGS;
 481           break;
 482
 483         case 'E':
 484         case 'F':
 485           if (GET_CODE (op) == CONST_DOUBLE
 486               || (GET_CODE (op) == CONST_VECTOR
 487                   && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT)
 488               || (equiv_const != NULL_RTX
 489                   && (GET_CODE (equiv_const) == CONST_DOUBLE
 490                       || (GET_CODE (equiv_const) == CONST_VECTOR
 491                           && (GET_MODE_CLASS (GET_MODE (equiv_const))
 492                               == MODE_VECTOR_FLOAT)))))
 493             return NO_REGS;
 494           break;
 495
 496         case 'G':
 497         case 'H':
 498           if ((GET_CODE (op) == CONST_DOUBLE
 499                && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, constraints))
 500               || (equiv_const != NULL_RTX
 501                   && GET_CODE (equiv_const) == CONST_DOUBLE
 502                   && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const,
 503                                                        c, constraints)))
 504             return NO_REGS;
 505           /* ??? what about memory */
 506         case 'r':
 507         case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
 508         case 'h': case 'j': case 'k': case 'l':
 509         case 'q': case 't': case 'u':
 510         case 'v': case 'w': case 'x': case 'y': case 'z':
 511         case 'A': case 'B': case 'C': case 'D':
 512         case 'Q': case 'R': case 'S': case 'T': case 'U':
 513         case 'W': case 'Y': case 'Z':
 514           next_cl = (c == 'r'
 515                      ? GENERAL_REGS
 516                      : REG_CLASS_FROM_CONSTRAINT (c, constraints));
 517           if ((cl != NO_REGS && next_cl != cl)
 518               || available_class_regs[next_cl] > 1)
 519             return NO_REGS;
 520           cl = next_cl;
 521           break;
 522
 523         case '0': case '1': case '2': case '3': case '4':
 524         case '5': case '6': case '7': case '8': case '9':
 525           next_cl
 526             = single_reg_class (recog_data.constraints[c - '0'],
 527                                 recog_data.operand[c - '0'], NULL_RTX);
 528           if ((cl != NO_REGS && next_cl != cl) || next_cl == NO_REGS
 529               || available_class_regs[next_cl] > 1)
 530             return NO_REGS;
 531           cl = next_cl;
 532           break;
 533
 534         default:
 535           return NO_REGS;
 536         }
 537   return cl;
 538 }
 539
 540 /* The function checks that operand OP_NUM of the current insn can use
 541    only one hard register.  If it is so, the function returns the
 542    class of the hard register.  Otherwise it returns NO_REGS.  */
 543 static enum reg_class
 544 single_reg_operand_class (int op_num)
 545 {
 546   if (op_num < 0 || recog_data.n_alternatives == 0)
 547     return NO_REGS;
 548   return single_reg_class (recog_data.constraints[op_num],
 549                            recog_data.operand[op_num], NULL_RTX);
 550 }
 551
 552 /* The function processes input operands, if IN_P, or output operands
 553    otherwise of the current insn with FREQ to find allocno which can
 554    use only one hard register and makes other currently living
 555    allocnos conflicting with the hard register.  */
 556 static void
 557 process_single_reg_class_operands (int in_p, int freq)
 558 {
 559   int i, regno, cost;
 560   unsigned int px;
 561   enum reg_class cl, cover_class;
 562   rtx operand;
 563   allocno_t operand_a, a;
 564
 565   for (i = 0; i < recog_data.n_operands; i++)
 566     {
 567       operand = recog_data.operand[i];
 568       if (in_p && recog_data.operand_type[i] != OP_IN
 569           && recog_data.operand_type[i] != OP_INOUT)
 570         continue;
 571       if (! in_p && recog_data.operand_type[i] != OP_OUT
 572           && recog_data.operand_type[i] != OP_INOUT)
 573         continue;
 574       cl = single_reg_operand_class (i);
 575       if (cl == NO_REGS)
 576         continue;
 577
 578       operand_a = NULL;
 579
 580       if (GET_CODE (operand) == SUBREG)
 581         operand = SUBREG_REG (operand);
 582
 583       if (REG_P (operand)
 584           && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
 585         {
 586           enum machine_mode mode;
 587           enum reg_class cover_class;
 588
 589           operand_a = ira_curr_regno_allocno_map[regno];
 590           mode = ALLOCNO_MODE (operand_a);
 591           cover_class = ALLOCNO_COVER_CLASS (operand_a);
 592           if (class_subset_p[cl][cover_class]
 593               && class_hard_regs_num[cl] != 0
 594               && class_hard_reg_index[cover_class][class_hard_regs[cl][0]] >= 0
 595               && reg_class_size[cl] <= (unsigned) CLASS_MAX_NREGS (cl, mode))
 596             {
 597               /* ??? FREQ */
 598               cost = freq * (in_p
 599                              ? register_move_cost[mode][cover_class][cl]
 600                              : register_move_cost[mode][cl][cover_class]);
 601               allocate_and_set_costs
 602                 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), cover_class, 0);
 603               ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
 604                 [class_hard_reg_index[cover_class][class_hard_regs[cl][0]]]
 605                 -= cost;
 606             }
 607         }
 608
 609       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
 610         {
 611           a = allocnos[px];
 612           cover_class = ALLOCNO_COVER_CLASS (a);
 613           if (a != operand_a)
 614             {
 615               /* We could increase costs of A instead of making it
 616                  conflicting with the hard register.  But it works worse
 617                  because it will be spilled in reload in anyway.  */
 618               IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 619                                 reg_class_contents[cl]);
 620               IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 621                                 reg_class_contents[cl]);
 622             }
 623         }
 624     }
 625 }
 626
 627 /* The function processes insns of the basic block given by its
 628    LOOP_TREE_NODE to update allocno live ranges, allocno hard register
 629    conflicts, intersected calls, and register pressure info for
 630    allocnos for the basic block for and regions containing the basic
 631    block.  */
 632 static void
 633 process_bb_node_lives (loop_tree_node_t loop_tree_node)
 634 {
 635   int i, index;
 636   unsigned int j;
 637   basic_block bb;
 638   rtx insn;
 639   edge e;
 640   edge_iterator ei;
 641   bitmap_iterator bi;
 642   bitmap reg_live_in;
 643   unsigned int px;
 644
 645   bb = loop_tree_node->bb;
 646   if (bb != NULL)
 647     {
 648       for (i = 0; i < reg_class_cover_size; i++)
 649         {
 650           curr_reg_pressure[reg_class_cover[i]] = 0;
 651           high_pressure_start_point[reg_class_cover[i]] = -1;
 652         }
 653       curr_bb_node = loop_tree_node;
 654       reg_live_in = DF_LR_IN (bb);
 655       sparseset_clear (allocnos_live);
 656       REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_in);
 657       AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
 658       AND_COMPL_HARD_REG_SET (hard_regs_live, no_alloc_regs);
 659       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 660         if (TEST_HARD_REG_BIT (hard_regs_live, i))
 661           {
 662             enum reg_class cover_class;
 663
 664             cover_class = REGNO_REG_CLASS (i);
 665             if (cover_class == NO_REGS)
 666               continue;
 667             cover_class = class_translate[cover_class];
 668             curr_reg_pressure[cover_class]++;
 669             if (curr_bb_node->reg_pressure[cover_class]
 670                 < curr_reg_pressure[cover_class])
 671               curr_bb_node->reg_pressure[cover_class]
 672                 = curr_reg_pressure[cover_class];
 673             ira_assert (curr_reg_pressure[cover_class]
 674                         <= available_class_regs[cover_class]);
 675           }
 676       EXECUTE_IF_SET_IN_BITMAP (reg_live_in, FIRST_PSEUDO_REGISTER, j, bi)
 677         {
 678           allocno_t a = ira_curr_regno_allocno_map[j];
 679
 680           if (a == NULL)
 681             continue;
 682           ira_assert (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)));
 683           set_allocno_live (a);
 684           make_regno_born (j);
 685         }
 686
 687 #ifdef EH_RETURN_DATA_REGNO
 688       if (bb_has_eh_pred (bb))
 689         {
 690           for (j = 0; ; ++j)
 691             {
 692               unsigned int regno = EH_RETURN_DATA_REGNO (j);
 693
 694               if (regno == INVALID_REGNUM)
 695                 break;
 696               make_regno_born_and_dead (regno);
 697             }
 698         }
 699 #endif
 700
 701       /* Allocnos can't go in stack regs at the start of a basic block
 702          that is reached by an abnormal edge. Likewise for call
 703          clobbered regs, because caller-save, fixup_abnormal_edges and
 704          possibly the table driven EH machinery are not quite ready to
 705          handle such allocnos live across such edges.  */
 706       FOR_EACH_EDGE (e, ei, bb->preds)
 707         if (e->flags & EDGE_ABNORMAL)
 708           break;
 709
 710       if (e != NULL)
 711         {
 712 #ifdef STACK_REGS
 713           EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
 714             {
 715               ALLOCNO_NO_STACK_REG_P (allocnos[px]) = TRUE;
 716               ALLOCNO_TOTAL_NO_STACK_REG_P (allocnos[px]) = TRUE;
 717             }
 718           for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
 719             make_regno_born_and_dead (px);
 720 #endif
 721           /* No need to record conflicts for call clobbered regs if we
 722              have nonlocal labels around, as we don't ever try to
 723              allocate such regs in this case.  */
 724           if (!cfun->has_nonlocal_label)
 725             for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
 726               if (call_used_regs[px])
 727                 make_regno_born_and_dead (px);
 728         }
 729
 730       /* Scan the code of this basic block, noting which allocnos and
 731          hard regs are born or die.  */
 732       FOR_BB_INSNS (bb, insn)
 733         {
 734           rtx link;
 735           int freq;
 736
 737           if (! INSN_P (insn))
 738             continue;
 739
 740           freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
 741           if (freq == 0)
 742             freq = 1;
 743
 744           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 745             fprintf (ira_dump_file, "   Insn %u(l%d): point = %d\n",
 746                      INSN_UID (insn), loop_tree_node->father->loop->num,
 747                      curr_point);
 748
 749           /* Check regs_set is an empty set.  */
 750           gcc_assert (VEC_empty (rtx, regs_set));
 751
 752           /* Mark any allocnos clobbered by INSN as live, so they
 753              conflict with the inputs.  */
 754           note_stores (PATTERN (insn), mark_reg_clobber, NULL);
 755
 756           extract_insn (insn);
 757           process_single_reg_class_operands (TRUE, freq);
 758
 759           /* Mark any allocnos dead after INSN as dead now.  */
 760           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
 761             if (REG_NOTE_KIND (link) == REG_DEAD)
 762               mark_reg_death (XEXP (link, 0));
 763
 764           curr_point++;
 765
 766           if (CALL_P (insn))
 767             {
 768               HARD_REG_SET clobbered_regs;
 769
 770               get_call_invalidated_used_regs (insn, &clobbered_regs, FALSE);
 771               IOR_HARD_REG_SET (crtl->emit.call_used_regs, clobbered_regs);
 772               EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 773                 {
 774                   allocno_t a = allocnos[i];
 775
 776                   ALLOCNO_CALL_FREQ (a) += freq;
 777                   index = add_regno_call (ALLOCNO_REGNO (a), insn);
 778                   if (ALLOCNO_CALLS_CROSSED_START (a) < 0)
 779                     ALLOCNO_CALLS_CROSSED_START (a) = index;
 780                   ALLOCNO_CALLS_CROSSED_NUM (a)++;
 781                   /* Don't allocate allocnos that cross calls, if this
 782                      function receives a nonlocal goto.  */
 783                   if (cfun->has_nonlocal_label)
 784                     {
 785                       SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a));
 786                       SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 787                     }
 788                 }
 789             }
 790
 791           /* Mark any allocnos set in INSN as live.  Clobbers are
 792              processed again, so they will conflict with the reg
 793              allocnos that are set.  */
 794           note_stores (PATTERN (insn), mark_reg_store, NULL);
 795
 796 #ifdef AUTO_INC_DEC
 797           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
 798             if (REG_NOTE_KIND (link) == REG_INC)
 799               mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
 800 #endif
 801
 802           /* If INSN has multiple outputs, then any allocno that dies
 803              here and is used inside of an output must conflict with
 804              the other outputs.
 805
 806              It is unsafe to use !single_set here since it will ignore
 807              an unused output.  Just because an output is unused does
 808              not mean the compiler can assume the side effect will not
 809              occur.  Consider if ALLOCNO appears in the address of an
 810              output and we reload the output.  If we allocate ALLOCNO
 811              to the same hard register as an unused output we could
 812              set the hard register before the output reload insn.  */
 813           if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
 814             for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
 815               if (REG_NOTE_KIND (link) == REG_DEAD)
 816                 {
 817                   int i;
 818                   int used_in_output = 0;
 819                   rtx reg = XEXP (link, 0);
 820
 821                   for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
 822                     {
 823                       rtx set = XVECEXP (PATTERN (insn), 0, i);
 824
 825                       if (GET_CODE (set) == SET
 826                           && ! REG_P (SET_DEST (set))
 827                           && ! rtx_equal_p (reg, SET_DEST (set))
 828                           && reg_overlap_mentioned_p (reg, SET_DEST (set)))
 829                         used_in_output = 1;
 830                     }
 831                   if (used_in_output)
 832                     mark_reg_conflicts (reg);
 833                 }
 834
 835           process_single_reg_class_operands (FALSE, freq);
 836
 837           /* Mark any allocnos set in INSN and then never used.  */
 838           while (! VEC_empty (rtx, regs_set))
 839             {
 840               rtx reg = VEC_pop (rtx, regs_set);
 841               rtx note = find_regno_note (insn, REG_UNUSED, REGNO (reg));
 842
 843               if (note)
 844                 mark_reg_death (XEXP (note, 0));
 845             }
 846           curr_point++;
 847         }
 848       EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 849        {
 850          make_regno_dead (ALLOCNO_REGNO (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 < reg_class_cover_size; i++)
 859       {
 860         enum reg_class cover_class;
 861
 862         cover_class = reg_class_cover[i];
 863         if (loop_tree_node->reg_pressure[cover_class]
 864             > loop_tree_node->father->reg_pressure[cover_class])
 865           loop_tree_node->father->reg_pressure[cover_class]
 866             = loop_tree_node->reg_pressure[cover_class];
 867       }
 868 }
 869
 870 /* The function creates and sets up START_POINT_RANGES and
 871    FINISH_POINT_RANGES.  */
 872 static void
 873 create_start_finish_chains (void)
 874 {
 875   allocno_t a;
 876   allocno_iterator ai;
 877   allocno_live_range_t r;
 878
 879   start_point_ranges
 880     = ira_allocate (max_point * sizeof (allocno_live_range_t));
 881   memset (start_point_ranges, 0, max_point * sizeof (allocno_live_range_t));
 882   finish_point_ranges
 883     = ira_allocate (max_point * sizeof (allocno_live_range_t));
 884   memset (finish_point_ranges, 0, max_point * sizeof (allocno_live_range_t));
 885   FOR_EACH_ALLOCNO (a, ai)
 886     {
 887       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
 888         {
 889           r->start_next = start_point_ranges[r->start];
 890           start_point_ranges[r->start] = r;
 891           r->finish_next = finish_point_ranges[r->finish];
 892           finish_point_ranges[r->finish] = r;
 893         }
 894     }
 895 }
 896
 897 /* The function is used to rebuild START_POINT_RANGES and
 898    FINISH_POINT_RANGES after new live ranges and program points were
 899    added as a result if new insn generation.  */
 900 void
 901 rebuild_start_finish_chains (void)
 902 {
 903   ira_free (finish_point_ranges);
 904   ira_free (start_point_ranges);
 905   create_start_finish_chains ();
 906 }
 907
 908 /* The function prints live ranges R to file F.  */
 909 void
 910 print_live_range_list (FILE *f, allocno_live_range_t r)
 911 {
 912   for (; r != NULL; r = r->next)
 913     fprintf (f, " [%d..%d]", r->start, r->finish);
 914   fprintf (f, "\n");
 915 }
 916
 917 /* The function prints live ranges R to stderr.  */
 918 void
 919 debug_live_range_list (allocno_live_range_t r)
 920 {
 921   print_live_range_list (stderr, r);
 922 }
 923
 924 /* The function prints live ranges of allocno A to file F.  */
 925 static void
 926 print_allocno_live_ranges (FILE *f, allocno_t a)
 927 {
 928   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 929   print_live_range_list (f, ALLOCNO_LIVE_RANGES (a));
 930 }
 931
 932 /* The function prints live ranges of allocno A to stderr.  */
 933 void
 934 debug_allocno_live_ranges (allocno_t a)
 935 {
 936   print_allocno_live_ranges (stderr, a);
 937 }
 938
 939 /* The function prints live ranges of all allocnos to file F.  */
 940 static void
 941 print_live_ranges (FILE *f)
 942 {
 943   allocno_t a;
 944   allocno_iterator ai;
 945
 946   FOR_EACH_ALLOCNO (a, ai)
 947     print_allocno_live_ranges (f, a);
 948 }
 949
 950 /* The function prints live ranges of all allocnos to stderr.  */
 951 void
 952 debug_live_ranges (void)
 953 {
 954   print_live_ranges (stderr);
 955 }
 956
 957 /* The function propagates new info about allocno A (see comments
 958    about accumulated info in allocno definition) to the corresponding
 959    allocno on upper loop tree level.  So allocnos on upper levels
 960    accumulate information about the corresponding allocnos in nested
 961    regions.  The new info means allocno info finally calculated in
 962    this file.  */
 963 static void
 964 propagate_new_allocno_info (allocno_t a)
 965 {
 966   int regno;
 967   allocno_t father_a;
 968   loop_tree_node_t father;
 969
 970   regno = ALLOCNO_REGNO (a);
 971   if ((father = ALLOCNO_LOOP_TREE_NODE (a)->father) != NULL
 972       && (father_a = father->regno_allocno_map[regno]) != NULL)
 973     {
 974       ALLOCNO_CALL_FREQ (father_a) += ALLOCNO_CALL_FREQ (a);
 975 #ifdef STACK_REGS
 976       if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
 977         ALLOCNO_TOTAL_NO_STACK_REG_P (father_a) = TRUE;
 978 #endif
 979       IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (father_a),
 980                         ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 981       if (ALLOCNO_CALLS_CROSSED_START (father_a) < 0
 982           || (ALLOCNO_CALLS_CROSSED_START (a) >= 0
 983               && (ALLOCNO_CALLS_CROSSED_START (father_a)
 984                   > ALLOCNO_CALLS_CROSSED_START (a))))
 985         ALLOCNO_CALLS_CROSSED_START (father_a)
 986           = ALLOCNO_CALLS_CROSSED_START (a);
 987       ALLOCNO_CALLS_CROSSED_NUM (father_a) += ALLOCNO_CALLS_CROSSED_NUM (a);
 988       ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (father_a)
 989         += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
 990     }
 991 }
 992
 993 /* The function propagates new info about allocnos to the
 994    corresponding allocnos on upper loop tree level.  */
 995 static void
 996 propagate_new_info (void)
 997 {
 998   int i;
 999   allocno_t a;
1000
1001   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1002     for (a = regno_allocno_map[i];
1003          a != NULL;
1004          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1005       propagate_new_allocno_info (a);
1006 }
1007
1008 /* The main entry function creates live ranges, set up
1009    CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
1010    calculate register pressure info.  */
1011 void
1012 create_allocno_live_ranges (void)
1013 {
1014   allocnos_live = sparseset_alloc (allocnos_num);
1015   /* Make a vector that mark_reg_{store,clobber} will store in.  */
1016   if (!regs_set)
1017     regs_set = VEC_alloc (rtx, heap, 10);
1018   curr_point = 0;
1019   traverse_loop_tree (TRUE, ira_loop_tree_root, NULL, process_bb_node_lives);
1020   max_point = curr_point;
1021   create_start_finish_chains ();
1022   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1023     print_live_ranges (ira_dump_file);
1024   propagate_new_info ();
1025   /* Clean up.  */
1026   sparseset_free (allocnos_live);
1027 }
1028
1029 /* The function frees arrays START_POINT_RANGES and
1030    FINISH_POINT_RANGES.  */
1031 void
1032 finish_allocno_live_ranges (void)
1033 {
1034   ira_free (finish_point_ranges);
1035   ira_free (start_point_ranges);
1036 }