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