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