gcc/ira-conflicts.c

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