gcc/ira-conflicts.c

   1 /* IRA conflict builder.
   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 /* This file contains code responsible for allocno conflict creation,
  42    allocno copy creation and allocno info accumulation on upper level
  43    regions.  */
  44
  45 /* ira_allocnos_num array of arrays of bits, recording whether two
  46    allocno's conflict (can't go in the same hardware register).
  47
  48    Some arrays will be used as conflict bit vector of the
  49    corresponding allocnos see function build_allocno_conflicts.  */
  50 static IRA_INT_TYPE **conflicts;
  51
  52 /* Macro to test a conflict of A1 and A2 in `conflicts'.  */
  53 #define CONFLICT_ALLOCNO_P(A1, A2)                                      \
  54   (ALLOCNO_MIN (A1) <= ALLOCNO_CONFLICT_ID (A2)                         \
  55    && ALLOCNO_CONFLICT_ID (A2) <= ALLOCNO_MAX (A1)                      \
  56    && TEST_ALLOCNO_SET_BIT (conflicts[ALLOCNO_NUM (A1)],                \
  57                             ALLOCNO_CONFLICT_ID (A2),                   \
  58                             ALLOCNO_MIN (A1),                           \
  59                             ALLOCNO_MAX (A1)))
  60
  61 \f
  62
  63 /* Build allocno conflict table by processing allocno live ranges.  */
  64 static void
  65 build_conflict_bit_table (void)
  66 {
  67   int i, num, id, allocated_words_num, conflict_bit_vec_words_num;
  68   unsigned int j;
  69   enum reg_class cover_class;
  70   ira_allocno_t allocno, live_a;
  71   allocno_live_range_t r;
  72   ira_allocno_iterator ai;
  73   sparseset allocnos_live;
  74   int allocno_set_words;
  75
  76   allocno_set_words = (ira_allocnos_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
  77   allocnos_live = sparseset_alloc (ira_allocnos_num);
  78   conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
  79                                               * ira_allocnos_num);
  80   allocated_words_num = 0;
  81   FOR_EACH_ALLOCNO (allocno, ai)
  82     {
  83       num = ALLOCNO_NUM (allocno);
  84       if (ALLOCNO_MAX (allocno) < ALLOCNO_MIN (allocno))
  85         {
  86           conflicts[num] = NULL;
  87           continue;
  88         }
  89       conflict_bit_vec_words_num
  90         = ((ALLOCNO_MAX (allocno) - ALLOCNO_MIN (allocno) + IRA_INT_BITS)
  91            / IRA_INT_BITS);
  92       allocated_words_num += conflict_bit_vec_words_num;
  93       conflicts[num]
  94         = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
  95                                          * conflict_bit_vec_words_num);
  96       memset (conflicts[num], 0,
  97               sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
  98     }
  99   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
 100     fprintf
 101       (ira_dump_file,
 102        "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n",
 103        (long) allocated_words_num * sizeof (IRA_INT_TYPE),
 104        (long) allocno_set_words * ira_allocnos_num * sizeof (IRA_INT_TYPE));
 105   for (i = 0; i < ira_max_point; i++)
 106     {
 107       for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
 108         {
 109           allocno = r->allocno;
 110           num = ALLOCNO_NUM (allocno);
 111           id = ALLOCNO_CONFLICT_ID (allocno);
 112           cover_class = ALLOCNO_COVER_CLASS (allocno);
 113           sparseset_set_bit (allocnos_live, num);
 114           EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, j)
 115             {
 116               live_a = ira_allocnos[j];
 117               if (ira_reg_classes_intersect_p
 118                   [cover_class][ALLOCNO_COVER_CLASS (live_a)]
 119                   /* Don't set up conflict for the allocno with itself.  */
 120                   && num != (int) j)
 121                 {
 122                   SET_ALLOCNO_SET_BIT (conflicts[num],
 123                                        ALLOCNO_CONFLICT_ID (live_a),
 124                                        ALLOCNO_MIN (allocno),
 125                                        ALLOCNO_MAX (allocno));
 126                   SET_ALLOCNO_SET_BIT (conflicts[j], id,
 127                                        ALLOCNO_MIN (live_a),
 128                                        ALLOCNO_MAX (live_a));
 129                 }
 130             }
 131         }
 132
 133       for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
 134         sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (r->allocno));
 135     }
 136   sparseset_free (allocnos_live);
 137 }
 138
 139 \f
 140
 141 /* Return TRUE if the operand constraint STR is commutative.  */
 142 static bool
 143 commutative_constraint_p (const char *str)
 144 {
 145   bool ignore_p;
 146   int c;
 147
 148   for (ignore_p = false;;)
 149     {
 150       c = *str;
 151       if (c == '\0')
 152         break;
 153       str += CONSTRAINT_LEN (c, str);
 154       if (c == '#')
 155         ignore_p = true;
 156       else if (c == ',')
 157         ignore_p = false;
 158       else if (! ignore_p)
 159         {
 160           /* Usually `%' is the first constraint character but the
 161              documentation does not require this.  */
 162           if (c == '%')
 163             return true;
 164         }
 165     }
 166   return false;
 167 }
 168
 169 /* Return the number of the operand which should be the same in any
 170    case as operand with number OP_NUM (or negative value if there is
 171    no such operand).  If USE_COMMUT_OP_P is TRUE, the function makes
 172    temporarily commutative operand exchange before this.  The function
 173    takes only really possible alternatives into consideration.  */
 174 static int
 175 get_dup_num (int op_num, bool use_commut_op_p)
 176 {
 177   int curr_alt, c, original, dup;
 178   bool ignore_p, commut_op_used_p;
 179   const char *str;
 180   rtx op;
 181
 182   if (op_num < 0 || recog_data.n_alternatives == 0)
 183     return -1;
 184   op = recog_data.operand[op_num];
 185   commut_op_used_p = true;
 186   if (use_commut_op_p)
 187     {
 188       if (commutative_constraint_p (recog_data.constraints[op_num]))
 189         op_num++;
 190       else if (op_num > 0 && commutative_constraint_p (recog_data.constraints
 191                                                        [op_num - 1]))
 192         op_num--;
 193       else
 194         commut_op_used_p = false;
 195     }
 196   str = recog_data.constraints[op_num];
 197   for (ignore_p = false, original = -1, curr_alt = 0;;)
 198     {
 199       c = *str;
 200       if (c == '\0')
 201         break;
 202       if (c == '#')
 203         ignore_p = true;
 204       else if (c == ',')
 205         {
 206           curr_alt++;
 207           ignore_p = false;
 208         }
 209       else if (! ignore_p)
 210         switch (c)
 211           {
 212           case 'X':
 213             return -1;
 214
 215           case 'm':
 216           case 'o':
 217             /* Accept a register which might be placed in memory.  */
 218             return -1;
 219             break;
 220
 221           case 'V':
 222           case '<':
 223           case '>':
 224             break;
 225
 226           case 'p':
 227             GO_IF_LEGITIMATE_ADDRESS (VOIDmode, op, win_p);
 228             break;
 229
 230           win_p:
 231             return -1;
 232
 233           case 'g':
 234             return -1;
 235
 236           case 'r':
 237           case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
 238           case 'h': case 'j': case 'k': case 'l':
 239           case 'q': case 't': case 'u':
 240           case 'v': case 'w': case 'x': case 'y': case 'z':
 241           case 'A': case 'B': case 'C': case 'D':
 242           case 'Q': case 'R': case 'S': case 'T': case 'U':
 243           case 'W': case 'Y': case 'Z':
 244             {
 245               enum reg_class cl;
 246
 247               cl = (c == 'r'
 248                     ? GENERAL_REGS : REG_CLASS_FROM_CONSTRAINT (c, str));
 249               if (cl != NO_REGS)
 250                 return -1;
 251 #ifdef EXTRA_CONSTRAINT_STR
 252               else if (EXTRA_CONSTRAINT_STR (op, c, str))
 253                 return -1;
 254 #endif
 255               break;
 256             }
 257
 258           case '0': case '1': case '2': case '3': case '4':
 259           case '5': case '6': case '7': case '8': case '9':
 260             if (original != -1 && original != c)
 261               return -1;
 262             original = c;
 263             break;
 264           }
 265       str += CONSTRAINT_LEN (c, str);
 266     }
 267   if (original == -1)
 268     return -1;
 269   dup = original - '0';
 270   if (use_commut_op_p)
 271     {
 272       if (commutative_constraint_p (recog_data.constraints[dup]))
 273         dup++;
 274       else if (dup > 0
 275                && commutative_constraint_p (recog_data.constraints[dup -1]))
 276         dup--;
 277       else if (! commut_op_used_p)
 278         return -1;
 279     }
 280   return dup;
 281 }
 282
 283 /* Return the operand which should be, in any case, the same as
 284    operand with number OP_NUM.  If USE_COMMUT_OP_P is TRUE, the
 285    function makes temporarily commutative operand exchange before
 286    this.  */
 287 static rtx
 288 get_dup (int op_num, bool use_commut_op_p)
 289 {
 290   int n = get_dup_num (op_num, use_commut_op_p);
 291
 292   if (n < 0)
 293     return NULL_RTX;
 294   else
 295     return recog_data.operand[n];
 296 }
 297
 298 /* Check that X is REG or SUBREG of REG.  */
 299 #define REG_SUBREG_P(x)                                                 \
 300    (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
 301
 302 /* Return X if X is a REG, otherwise it should be SUBREG of REG and
 303    the function returns the reg in this case.  *OFFSET will be set to
 304    0 in the first case or the regno offset in the first case.  */
 305 static rtx
 306 go_through_subreg (rtx x, int *offset)
 307 {
 308   rtx reg;
 309
 310   *offset = 0;
 311   if (REG_P (x))
 312     return x;
 313   ira_assert (GET_CODE (x) == SUBREG);
 314   reg = SUBREG_REG (x);
 315   ira_assert (REG_P (reg));
 316   if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
 317     *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
 318                                    SUBREG_BYTE (x), GET_MODE (x));
 319   else
 320     *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x)));
 321   return reg;
 322 }
 323
 324 /* Process registers REG1 and REG2 in move INSN with execution
 325    frequency FREQ.  The function also processes the registers in a
 326    potential move insn (INSN == NULL in this case) with frequency
 327    FREQ.  The function can modify hard register costs of the
 328    corresponding allocnos or create a copy involving the corresponding
 329    allocnos.  The function does nothing if the both registers are hard
 330    registers.  When nothing is changed, the function returns
 331    FALSE.  */
 332 static bool
 333 process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p,
 334                        rtx insn, int freq)
 335 {
 336   int allocno_preferenced_hard_regno, cost, index, offset1, offset2;
 337   bool only_regs_p;
 338   ira_allocno_t a;
 339   enum reg_class rclass, cover_class;
 340   enum machine_mode mode;
 341   ira_copy_t cp;
 342   ira_loop_tree_node_t parent;
 343
 344   gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
 345   only_regs_p = REG_P (reg1) && REG_P (reg2);
 346   reg1 = go_through_subreg (reg1, &offset1);
 347   reg2 = go_through_subreg (reg2, &offset2);
 348   /* Set up hard regno preferenced by allocno.  If allocno gets the
 349      hard regno the copy (or potential move) insn will be removed.  */
 350   if (HARD_REGISTER_P (reg1))
 351     {
 352       if (HARD_REGISTER_P (reg2))
 353         return false;
 354       allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
 355       a = ira_curr_regno_allocno_map[REGNO (reg2)];
 356     }
 357   else if (HARD_REGISTER_P (reg2))
 358     {
 359       allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
 360       a = ira_curr_regno_allocno_map[REGNO (reg1)];
 361     }
 362   else if (!CONFLICT_ALLOCNO_P (ira_curr_regno_allocno_map[REGNO (reg1)],
 363                                 ira_curr_regno_allocno_map[REGNO (reg2)])
 364            && offset1 == offset2)
 365     {
 366       cp = ira_add_allocno_copy (ira_curr_regno_allocno_map[REGNO (reg1)],
 367                                  ira_curr_regno_allocno_map[REGNO (reg2)],
 368                                  freq, constraint_p, insn,
 369                                  ira_curr_loop_tree_node);
 370       bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
 371       return true;
 372     }
 373   else
 374     return false;
 375   if (! IN_RANGE (allocno_preferenced_hard_regno, 0, FIRST_PSEUDO_REGISTER - 1))
 376     /* Can not be tied.  */
 377     return false;
 378   rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
 379   mode = ALLOCNO_MODE (a);
 380   cover_class = ALLOCNO_COVER_CLASS (a);
 381   if (only_regs_p && insn != NULL_RTX
 382       && reg_class_size[rclass] <= (unsigned) CLASS_MAX_NREGS (rclass, mode))
 383     /* It is already taken into account in ira-costs.c.  */
 384     return false;
 385   index = ira_class_hard_reg_index[cover_class][allocno_preferenced_hard_regno];
 386   if (index < 0)
 387     /* Can not be tied.  It is not in the cover class.  */
 388     return false;
 389   if (HARD_REGISTER_P (reg1))
 390     cost = ira_register_move_cost[mode][cover_class][rclass] * freq;
 391   else
 392     cost = ira_register_move_cost[mode][rclass][cover_class] * freq;
 393   for (;;)
 394     {
 395       ira_allocate_and_set_costs
 396         (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
 397          ALLOCNO_COVER_CLASS_COST (a));
 398       ira_allocate_and_set_costs
 399         (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class, 0);
 400       ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
 401       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
 402       if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_COVER_CLASS_COST (a))
 403         ALLOCNO_COVER_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
 404       if (ALLOCNO_CAP (a) != NULL)
 405         a = ALLOCNO_CAP (a);
 406       else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
 407                || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
 408         break;
 409     }
 410   return true;
 411 }
 412
 413 /* Process all of the output registers of the current insn and
 414    the input register REG (its operand number OP_NUM) which dies in the
 415    insn as if there were a move insn between them with frequency
 416    FREQ.  */
 417 static void
 418 process_reg_shuffles (rtx reg, int op_num, int freq)
 419 {
 420   int i;
 421   rtx another_reg;
 422
 423   gcc_assert (REG_SUBREG_P (reg));
 424   for (i = 0; i < recog_data.n_operands; i++)
 425     {
 426       another_reg = recog_data.operand[i];
 427
 428       if (!REG_SUBREG_P (another_reg) || op_num == i
 429           || recog_data.operand_type[i] != OP_OUT)
 430         continue;
 431
 432       process_regs_for_copy (reg, another_reg, false, NULL_RTX, freq);
 433     }
 434 }
 435
 436 /* Process INSN and create allocno copies if necessary.  For example,
 437    it might be because INSN is a pseudo-register move or INSN is two
 438    operand insn.  */
 439 static void
 440 add_insn_allocno_copies (rtx insn)
 441 {
 442   rtx set, operand, dup;
 443   const char *str;
 444   bool commut_p, bound_p;
 445   int i, j, freq;
 446
 447   freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
 448   if (freq == 0)
 449     freq = 1;
 450   if ((set = single_set (insn)) != NULL_RTX
 451       && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
 452       && ! side_effects_p (set)
 453       && find_reg_note (insn, REG_DEAD,
 454                         REG_P (SET_SRC (set))
 455                         ? SET_SRC (set)
 456                         : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
 457     process_regs_for_copy (SET_DEST (set), SET_SRC (set), false, insn, freq);
 458   else
 459     {
 460       extract_insn (insn);
 461       for (i = 0; i < recog_data.n_operands; i++)
 462         {
 463           operand = recog_data.operand[i];
 464           if (REG_SUBREG_P (operand)
 465               && find_reg_note (insn, REG_DEAD,
 466                                 REG_P (operand)
 467                                 ? operand : SUBREG_REG (operand)) != NULL_RTX)
 468             {
 469               str = recog_data.constraints[i];
 470               while (*str == ' ' && *str == '\t')
 471                 str++;
 472               bound_p = false;
 473               for (j = 0, commut_p = false; j < 2; j++, commut_p = true)
 474                 if ((dup = get_dup (i, commut_p)) != NULL_RTX
 475                     && REG_SUBREG_P (dup)
 476                     && process_regs_for_copy (operand, dup, true,
 477                                               NULL_RTX, freq))
 478                   bound_p = true;
 479               if (bound_p)
 480                 continue;
 481               /* If an operand dies, prefer its hard register for the
 482                  output operands by decreasing the hard register cost
 483                  or creating the corresponding allocno copies.  The
 484                  cost will not correspond to a real move insn cost, so
 485                  make the frequency smaller.  */
 486               process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8);
 487             }
 488         }
 489     }
 490 }
 491
 492 /* Add copies originated from BB given by LOOP_TREE_NODE.  */
 493 static void
 494 add_copies (ira_loop_tree_node_t loop_tree_node)
 495 {
 496   basic_block bb;
 497   rtx insn;
 498
 499   bb = loop_tree_node->bb;
 500   if (bb == NULL)
 501     return;
 502   FOR_BB_INSNS (bb, insn)
 503     if (INSN_P (insn))
 504       add_insn_allocno_copies (insn);
 505 }
 506
 507 /* Propagate copies the corresponding allocnos on upper loop tree
 508    level.  */
 509 static void
 510 propagate_copies (void)
 511 {
 512   ira_copy_t cp;
 513   ira_copy_iterator ci;
 514   ira_allocno_t a1, a2, parent_a1, parent_a2;
 515   ira_loop_tree_node_t parent;
 516
 517   FOR_EACH_COPY (cp, ci)
 518     {
 519       a1 = cp->first;
 520       a2 = cp->second;
 521       if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
 522         continue;
 523       ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
 524       parent = ALLOCNO_LOOP_TREE_NODE (a1)->parent;
 525       if ((parent_a1 = ALLOCNO_CAP (a1)) == NULL)
 526         parent_a1 = parent->regno_allocno_map[ALLOCNO_REGNO (a1)];
 527       if ((parent_a2 = ALLOCNO_CAP (a2)) == NULL)
 528         parent_a2 = parent->regno_allocno_map[ALLOCNO_REGNO (a2)];
 529       ira_assert (parent_a1 != NULL && parent_a2 != NULL);
 530       if (! CONFLICT_ALLOCNO_P (parent_a1, parent_a2))
 531         ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
 532                               cp->constraint_p, cp->insn, cp->loop_tree_node);
 533     }
 534 }
 535
 536 /* Array used to collect all conflict allocnos for given allocno.  */
 537 static ira_allocno_t *collected_conflict_allocnos;
 538
 539 /* Build conflict vectors or bit conflict vectors (whatever is more
 540    profitable) for allocno A from the conflict table and propagate the
 541    conflicts to upper level allocno.  */
 542 static void
 543 build_allocno_conflicts (ira_allocno_t a)
 544 {
 545   int i, px, parent_num;
 546   int conflict_bit_vec_words_num;
 547   ira_loop_tree_node_t parent;
 548   ira_allocno_t parent_a, another_a, another_parent_a;
 549   ira_allocno_t *vec;
 550   IRA_INT_TYPE *allocno_conflicts;
 551   ira_allocno_set_iterator asi;
 552
 553   allocno_conflicts = conflicts[ALLOCNO_NUM (a)];
 554   px = 0;
 555   FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
 556                            ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
 557     {
 558       another_a = ira_conflict_id_allocno_map[i];
 559       ira_assert (ira_reg_classes_intersect_p
 560                   [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
 561       collected_conflict_allocnos[px++] = another_a;
 562     }
 563   if (ira_conflict_vector_profitable_p (a, px))
 564     {
 565       ira_allocate_allocno_conflict_vec (a, px);
 566       vec = (ira_allocno_t*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
 567       memcpy (vec, collected_conflict_allocnos, sizeof (ira_allocno_t) * px);
 568       vec[px] = NULL;
 569       ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = px;
 570     }
 571   else
 572     {
 573       ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = conflicts[ALLOCNO_NUM (a)];
 574       if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
 575         conflict_bit_vec_words_num = 0;
 576       else
 577         conflict_bit_vec_words_num
 578           = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
 579              / IRA_INT_BITS);
 580       ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a)
 581         = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
 582     }
 583   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
 584   if ((parent_a = ALLOCNO_CAP (a)) == NULL
 585       && (parent == NULL
 586           || (parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
 587           == NULL))
 588     return;
 589   ira_assert (parent != NULL);
 590   ira_assert (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (parent_a));
 591   parent_num = ALLOCNO_NUM (parent_a);
 592   FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
 593                            ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
 594     {
 595       another_a = ira_conflict_id_allocno_map[i];
 596       ira_assert (ira_reg_classes_intersect_p
 597                   [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
 598       if ((another_parent_a = ALLOCNO_CAP (another_a)) == NULL
 599           && (another_parent_a = (parent->regno_allocno_map
 600                                   [ALLOCNO_REGNO (another_a)])) == NULL)
 601         continue;
 602       ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
 603       ira_assert (ALLOCNO_COVER_CLASS (another_a)
 604                   == ALLOCNO_COVER_CLASS (another_parent_a));
 605       SET_ALLOCNO_SET_BIT (conflicts[parent_num],
 606                            ALLOCNO_CONFLICT_ID (another_parent_a),
 607                            ALLOCNO_MIN (parent_a),
 608                            ALLOCNO_MAX (parent_a));
 609     }
 610 }
 611
 612 /* Build conflict vectors or bit conflict vectors (whatever is more
 613    profitable) of all allocnos from the conflict table.  */
 614 static void
 615 build_conflicts (void)
 616 {
 617   int i;
 618   ira_allocno_t a, cap;
 619
 620   collected_conflict_allocnos
 621     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
 622                                       * ira_allocnos_num);
 623   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
 624     for (a = ira_regno_allocno_map[i];
 625          a != NULL;
 626          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 627       {
 628         build_allocno_conflicts (a);
 629         for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
 630           build_allocno_conflicts (cap);
 631       }
 632   ira_free (collected_conflict_allocnos);
 633 }
 634
 635 \f
 636
 637 /* Print hard reg set SET with TITLE to FILE.  */
 638 static void
 639 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
 640 {
 641   int i, start;
 642
 643   fprintf (file, title);
 644   for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 645     {
 646       if (TEST_HARD_REG_BIT (set, i))
 647         {
 648           if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
 649             start = i;
 650         }
 651       if (start >= 0
 652           && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
 653         {
 654           if (start == i - 1)
 655             fprintf (file, " %d", start);
 656           else if (start == i - 2)
 657             fprintf (file, " %d %d", start, start + 1);
 658           else
 659             fprintf (file, " %d-%d", start, i - 1);
 660           start = -1;
 661         }
 662     }
 663   fprintf (file, "\n");
 664 }
 665
 666 /* Print information about allocno or only regno (if REG_P) conflicts
 667    to FILE.  */
 668 static void
 669 print_conflicts (FILE *file, bool reg_p)
 670 {
 671   ira_allocno_t a;
 672   ira_allocno_iterator ai;
 673   HARD_REG_SET conflicting_hard_regs;
 674
 675   FOR_EACH_ALLOCNO (a, ai)
 676     {
 677       ira_allocno_t conflict_a;
 678       ira_allocno_conflict_iterator aci;
 679       basic_block bb;
 680
 681       if (reg_p)
 682         fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
 683       else
 684         {
 685           fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 686           if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 687             fprintf (file, "b%d", bb->index);
 688           else
 689             fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 690           fprintf (file, ")");
 691         }
 692       fprintf (file, " conflicts:");
 693       if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
 694         FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
 695           {
 696             if (reg_p)
 697               fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
 698             else
 699               {
 700                 fprintf (file, " a%d(r%d,", ALLOCNO_NUM (conflict_a),
 701                          ALLOCNO_REGNO (conflict_a));
 702                 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
 703                   fprintf (file, "b%d)", bb->index);
 704                 else
 705                   fprintf (file, "l%d)",
 706                            ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop->num);
 707               }
 708           }
 709       COPY_HARD_REG_SET (conflicting_hard_regs,
 710                          ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 711       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 712       AND_HARD_REG_SET (conflicting_hard_regs,
 713                         reg_class_contents[ALLOCNO_COVER_CLASS (a)]);
 714       print_hard_reg_set (file, "\n;;     total conflict hard regs:",
 715                           conflicting_hard_regs);
 716       COPY_HARD_REG_SET (conflicting_hard_regs,
 717                          ALLOCNO_CONFLICT_HARD_REGS (a));
 718       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 719       AND_HARD_REG_SET (conflicting_hard_regs,
 720                         reg_class_contents[ALLOCNO_COVER_CLASS (a)]);
 721       print_hard_reg_set (file, ";;     conflict hard regs:",
 722                           conflicting_hard_regs);
 723     }
 724   fprintf (file, "\n");
 725 }
 726
 727 /* Print information about allocno or only regno (if REG_P) conflicts
 728    to stderr.  */
 729 void
 730 ira_debug_conflicts (bool reg_p)
 731 {
 732   print_conflicts (stderr, reg_p);
 733 }
 734
 735 \f
 736
 737 /* Entry function which builds allocno conflicts and allocno copies
 738    and accumulate some allocno info on upper level regions.  */
 739 void
 740 ira_build_conflicts (void)
 741 {
 742   ira_allocno_t a;
 743   ira_allocno_iterator ai;
 744   HARD_REG_SET temp_hard_reg_set;
 745
 746   if (optimize)
 747     {
 748       build_conflict_bit_table ();
 749       build_conflicts ();
 750       ira_traverse_loop_tree (true, ira_loop_tree_root, NULL, add_copies);
 751       /* We need finished conflict table for the subsequent call.  */
 752       if (flag_ira_region == IRA_REGION_ALL
 753           || flag_ira_region == IRA_REGION_MIXED)
 754         propagate_copies ();
 755       /* Now we can free memory for the conflict table (see function
 756          build_allocno_conflicts for details).  */
 757       FOR_EACH_ALLOCNO (a, ai)
 758         {
 759           if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != conflicts[ALLOCNO_NUM (a)])
 760             ira_free (conflicts[ALLOCNO_NUM (a)]);
 761         }
 762       ira_free (conflicts);
 763     }
 764   if (! CLASS_LIKELY_SPILLED_P (BASE_REG_CLASS))
 765     CLEAR_HARD_REG_SET (temp_hard_reg_set);
 766   else
 767     {
 768       COPY_HARD_REG_SET (temp_hard_reg_set, reg_class_contents[BASE_REG_CLASS]);
 769       AND_COMPL_HARD_REG_SET (temp_hard_reg_set, ira_no_alloc_regs);
 770       AND_HARD_REG_SET (temp_hard_reg_set, call_used_reg_set);
 771     }
 772   FOR_EACH_ALLOCNO (a, ai)
 773     {
 774       if (ALLOCNO_CALLS_CROSSED_NUM (a) == 0)
 775         continue;
 776       if (! flag_caller_saves)
 777         {
 778           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 779                             call_used_reg_set);
 780           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 781             IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 782                               call_used_reg_set);
 783         }
 784       else
 785         {
 786           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 787                             no_caller_save_reg_set);
 788           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 789                             temp_hard_reg_set);
 790           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 791             {
 792               IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 793                                 no_caller_save_reg_set);
 794               IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 795                                 temp_hard_reg_set);
 796             }
 797         }
 798     }
 799   if (optimize && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 800     print_conflicts (ira_dump_file, false);
 801 }