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 long long) allocated_words_num * sizeof (IRA_INT_TYPE)
 120             > (unsigned long long) 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       if (!allocnos_conflict_for_copy_p (a1, a2) && offset1 == offset2)
 423         {
 424           cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn,
 425                                      ira_curr_loop_tree_node);
 426           bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
 427           return true;
 428         }
 429       else
 430         return false;
 431     }
 432
 433   if (! IN_RANGE (allocno_preferenced_hard_regno,
 434                   0, FIRST_PSEUDO_REGISTER - 1))
 435     /* Can not be tied.  */
 436     return false;
 437   rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
 438   mode = ALLOCNO_MODE (a);
 439   aclass = ALLOCNO_CLASS (a);
 440   if (only_regs_p && insn != NULL_RTX
 441       && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode])
 442     /* It is already taken into account in ira-costs.c.  */
 443     return false;
 444   index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno];
 445   if (index < 0)
 446     /* Can not be tied.  It is not in the allocno class.  */
 447     return false;
 448   ira_init_register_move_cost_if_necessary (mode);
 449   if (HARD_REGISTER_P (reg1))
 450     cost = ira_register_move_cost[mode][aclass][rclass] * freq;
 451   else
 452     cost = ira_register_move_cost[mode][rclass][aclass] * freq;
 453   do
 454     {
 455       ira_allocate_and_set_costs
 456         (&ALLOCNO_HARD_REG_COSTS (a), aclass,
 457          ALLOCNO_CLASS_COST (a));
 458       ira_allocate_and_set_costs
 459         (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 0);
 460       ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
 461       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
 462       if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a))
 463         ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
 464       a = ira_parent_or_cap_allocno (a);
 465     }
 466   while (a != NULL);
 467   return true;
 468 }
 469
 470 /* Process all of the output registers of the current insn which are
 471    not bound (BOUND_P) and the input register REG (its operand number
 472    OP_NUM) which dies in the insn as if there were a move insn between
 473    them with frequency FREQ.  */
 474 static void
 475 process_reg_shuffles (rtx reg, int op_num, int freq, bool *bound_p)
 476 {
 477   int i;
 478   rtx another_reg;
 479
 480   gcc_assert (REG_SUBREG_P (reg));
 481   for (i = 0; i < recog_data.n_operands; i++)
 482     {
 483       another_reg = recog_data.operand[i];
 484
 485       if (!REG_SUBREG_P (another_reg) || op_num == i
 486           || recog_data.operand_type[i] != OP_OUT
 487           || bound_p[i])
 488         continue;
 489
 490       process_regs_for_copy (reg, another_reg, false, NULL_RTX, freq);
 491     }
 492 }
 493
 494 /* Process INSN and create allocno copies if necessary.  For example,
 495    it might be because INSN is a pseudo-register move or INSN is two
 496    operand insn.  */
 497 static void
 498 add_insn_allocno_copies (rtx insn)
 499 {
 500   rtx set, operand, dup;
 501   const char *str;
 502   bool commut_p, bound_p[MAX_RECOG_OPERANDS];
 503   int i, j, n, freq;
 504
 505   freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
 506   if (freq == 0)
 507     freq = 1;
 508   if ((set = single_set (insn)) != NULL_RTX
 509       && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
 510       && ! side_effects_p (set)
 511       && find_reg_note (insn, REG_DEAD,
 512                         REG_P (SET_SRC (set))
 513                         ? SET_SRC (set)
 514                         : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
 515     {
 516       process_regs_for_copy (SET_DEST (set), SET_SRC (set),
 517                              false, insn, freq);
 518       return;
 519     }
 520   /* Fast check of possibility of constraint or shuffle copies.  If
 521      there are no dead registers, there will be no such copies.  */
 522   if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
 523     return;
 524   extract_insn (insn);
 525   for (i = 0; i < recog_data.n_operands; i++)
 526     bound_p[i] = false;
 527   for (i = 0; i < recog_data.n_operands; i++)
 528     {
 529       operand = recog_data.operand[i];
 530       if (! REG_SUBREG_P (operand))
 531         continue;
 532       str = recog_data.constraints[i];
 533       while (*str == ' ' || *str == '\t')
 534         str++;
 535       for (j = 0, commut_p = false; j < 2; j++, commut_p = true)
 536         if ((n = get_dup_num (i, commut_p)) >= 0)
 537           {
 538             bound_p[n] = true;
 539             dup = recog_data.operand[n];
 540             if (REG_SUBREG_P (dup)
 541                 && find_reg_note (insn, REG_DEAD,
 542                                   REG_P (operand)
 543                                   ? operand
 544                                   : SUBREG_REG (operand)) != NULL_RTX)
 545               process_regs_for_copy (operand, dup, true, NULL_RTX, freq);
 546           }
 547     }
 548   for (i = 0; i < recog_data.n_operands; i++)
 549     {
 550       operand = recog_data.operand[i];
 551       if (REG_SUBREG_P (operand)
 552           && find_reg_note (insn, REG_DEAD,
 553                             REG_P (operand)
 554                             ? operand : SUBREG_REG (operand)) != NULL_RTX)
 555         /* If an operand dies, prefer its hard register for the output
 556            operands by decreasing the hard register cost or creating
 557            the corresponding allocno copies.  The cost will not
 558            correspond to a real move insn cost, so make the frequency
 559            smaller.  */
 560         process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8, bound_p);
 561     }
 562 }
 563
 564 /* Add copies originated from BB given by LOOP_TREE_NODE.  */
 565 static void
 566 add_copies (ira_loop_tree_node_t loop_tree_node)
 567 {
 568   basic_block bb;
 569   rtx insn;
 570
 571   bb = loop_tree_node->bb;
 572   if (bb == NULL)
 573     return;
 574   FOR_BB_INSNS (bb, insn)
 575     if (NONDEBUG_INSN_P (insn))
 576       add_insn_allocno_copies (insn);
 577 }
 578
 579 /* Propagate copies the corresponding allocnos on upper loop tree
 580    level.  */
 581 static void
 582 propagate_copies (void)
 583 {
 584   ira_copy_t cp;
 585   ira_copy_iterator ci;
 586   ira_allocno_t a1, a2, parent_a1, parent_a2;
 587
 588   FOR_EACH_COPY (cp, ci)
 589     {
 590       a1 = cp->first;
 591       a2 = cp->second;
 592       if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
 593         continue;
 594       ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
 595       parent_a1 = ira_parent_or_cap_allocno (a1);
 596       parent_a2 = ira_parent_or_cap_allocno (a2);
 597       ira_assert (parent_a1 != NULL && parent_a2 != NULL);
 598       if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2))
 599         ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
 600                               cp->constraint_p, cp->insn, cp->loop_tree_node);
 601     }
 602 }
 603
 604 /* Array used to collect all conflict allocnos for given allocno.  */
 605 static ira_object_t *collected_conflict_objects;
 606
 607 /* Build conflict vectors or bit conflict vectors (whatever is more
 608    profitable) for object OBJ from the conflict table.  */
 609 static void
 610 build_object_conflicts (ira_object_t obj)
 611 {
 612   int i, px, parent_num;
 613   ira_allocno_t parent_a, another_parent_a;
 614   ira_object_t parent_obj;
 615   ira_allocno_t a = OBJECT_ALLOCNO (obj);
 616   IRA_INT_TYPE *object_conflicts;
 617   minmax_set_iterator asi;
 618   int parent_min, parent_max ATTRIBUTE_UNUSED;
 619
 620   object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
 621   px = 0;
 622   FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
 623                               OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
 624     {
 625       ira_object_t another_obj = ira_object_id_map[i];
 626       ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
 627
 628       ira_assert (ira_reg_classes_intersect_p
 629                   [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
 630       collected_conflict_objects[px++] = another_obj;
 631     }
 632   if (ira_conflict_vector_profitable_p (obj, px))
 633     {
 634       ira_object_t *vec;
 635       ira_allocate_conflict_vec (obj, px);
 636       vec = OBJECT_CONFLICT_VEC (obj);
 637       memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px);
 638       vec[px] = NULL;
 639       OBJECT_NUM_CONFLICTS (obj) = px;
 640     }
 641   else
 642     {
 643       int conflict_bit_vec_words_num;
 644
 645       OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
 646       if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 647         conflict_bit_vec_words_num = 0;
 648       else
 649         conflict_bit_vec_words_num
 650           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 651              / IRA_INT_BITS);
 652       OBJECT_CONFLICT_ARRAY_SIZE (obj)
 653         = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
 654     }
 655
 656   parent_a = ira_parent_or_cap_allocno (a);
 657   if (parent_a == NULL)
 658     return;
 659   ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
 660   ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
 661   parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
 662   parent_num = OBJECT_CONFLICT_ID (parent_obj);
 663   parent_min = OBJECT_MIN (parent_obj);
 664   parent_max = OBJECT_MAX (parent_obj);
 665   FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
 666                               OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
 667     {
 668       ira_object_t another_obj = ira_object_id_map[i];
 669       ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
 670       int another_word = OBJECT_SUBWORD (another_obj);
 671
 672       ira_assert (ira_reg_classes_intersect_p
 673                   [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
 674
 675       another_parent_a = ira_parent_or_cap_allocno (another_a);
 676       if (another_parent_a == NULL)
 677         continue;
 678       ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
 679       ira_assert (ALLOCNO_CLASS (another_a)
 680                   == ALLOCNO_CLASS (another_parent_a));
 681       ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
 682                   == ALLOCNO_NUM_OBJECTS (another_parent_a));
 683       SET_MINMAX_SET_BIT (conflicts[parent_num],
 684                           OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
 685                                                               another_word)),
 686                           parent_min, parent_max);
 687     }
 688 }
 689
 690 /* Build conflict vectors or bit conflict vectors (whatever is more
 691    profitable) of all allocnos from the conflict table.  */
 692 static void
 693 build_conflicts (void)
 694 {
 695   int i;
 696   ira_allocno_t a, cap;
 697
 698   collected_conflict_objects
 699     = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
 700                                           * ira_objects_num);
 701   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
 702     for (a = ira_regno_allocno_map[i];
 703          a != NULL;
 704          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 705       {
 706         int j, nregs = ALLOCNO_NUM_OBJECTS (a);
 707         for (j = 0; j < nregs; j++)
 708           {
 709             ira_object_t obj = ALLOCNO_OBJECT (a, j);
 710             build_object_conflicts (obj);
 711             for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
 712               {
 713                 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
 714                 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
 715                 build_object_conflicts (cap_obj);
 716               }
 717           }
 718       }
 719   ira_free (collected_conflict_objects);
 720 }
 721
 722 \f
 723
 724 /* Print hard reg set SET with TITLE to FILE.  */
 725 static void
 726 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
 727 {
 728   int i, start;
 729
 730   fputs (title, file);
 731   for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 732     {
 733       if (TEST_HARD_REG_BIT (set, i))
 734         {
 735           if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
 736             start = i;
 737         }
 738       if (start >= 0
 739           && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
 740         {
 741           if (start == i - 1)
 742             fprintf (file, " %d", start);
 743           else if (start == i - 2)
 744             fprintf (file, " %d %d", start, start + 1);
 745           else
 746             fprintf (file, " %d-%d", start, i - 1);
 747           start = -1;
 748         }
 749     }
 750   putc ('\n', file);
 751 }
 752
 753 static void
 754 print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
 755 {
 756   HARD_REG_SET conflicting_hard_regs;
 757   basic_block bb;
 758   int n, i;
 759
 760   if (reg_p)
 761     fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
 762   else
 763     {
 764       fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 765       if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 766         fprintf (file, "b%d", bb->index);
 767       else
 768         fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 769       putc (')', file);
 770     }
 771
 772   fputs (" conflicts:", file);
 773   n = ALLOCNO_NUM_OBJECTS (a);
 774   for (i = 0; i < n; i++)
 775     {
 776       ira_object_t obj = ALLOCNO_OBJECT (a, i);
 777       ira_object_t conflict_obj;
 778       ira_object_conflict_iterator oci;
 779
 780       if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
 781         continue;
 782       if (n > 1)
 783         fprintf (file, "\n;;   subobject %d:", i);
 784       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
 785         {
 786           ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
 787           if (reg_p)
 788             fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
 789           else
 790             {
 791               fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a),
 792                        ALLOCNO_REGNO (conflict_a));
 793               if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
 794                 fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj));
 795               if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
 796                 fprintf (file, ",b%d", bb->index);
 797               else
 798                 fprintf (file, ",l%d",
 799                          ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop->num);
 800               putc (')', file);
 801             }
 802         }
 803       COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
 804       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 805       AND_HARD_REG_SET (conflicting_hard_regs,
 806                         reg_class_contents[ALLOCNO_CLASS (a)]);
 807       print_hard_reg_set (file, "\n;;     total conflict hard regs:",
 808                           conflicting_hard_regs);
 809
 810       COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_CONFLICT_HARD_REGS (obj));
 811       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 812       AND_HARD_REG_SET (conflicting_hard_regs,
 813                         reg_class_contents[ALLOCNO_CLASS (a)]);
 814       print_hard_reg_set (file, ";;     conflict hard regs:",
 815                           conflicting_hard_regs);
 816       putc ('\n', file);
 817     }
 818
 819 }
 820
 821 /* Print information about allocno or only regno (if REG_P) conflicts
 822    to FILE.  */
 823 static void
 824 print_conflicts (FILE *file, bool reg_p)
 825 {
 826   ira_allocno_t a;
 827   ira_allocno_iterator ai;
 828
 829   FOR_EACH_ALLOCNO (a, ai)
 830     print_allocno_conflicts (file, reg_p, a);
 831 }
 832
 833 /* Print information about allocno or only regno (if REG_P) conflicts
 834    to stderr.  */
 835 void
 836 ira_debug_conflicts (bool reg_p)
 837 {
 838   print_conflicts (stderr, reg_p);
 839 }
 840
 841 \f
 842
 843 /* Entry function which builds allocno conflicts and allocno copies
 844    and accumulate some allocno info on upper level regions.  */
 845 void
 846 ira_build_conflicts (void)
 847 {
 848   ira_allocno_t a;
 849   ira_allocno_iterator ai;
 850   HARD_REG_SET temp_hard_reg_set;
 851
 852   if (ira_conflicts_p)
 853     {
 854       ira_conflicts_p = build_conflict_bit_table ();
 855       if (ira_conflicts_p)
 856         {
 857           ira_object_t obj;
 858           ira_object_iterator oi;
 859
 860           build_conflicts ();
 861           ira_traverse_loop_tree (true, ira_loop_tree_root, NULL, add_copies);
 862           /* We need finished conflict table for the subsequent call.  */
 863           if (flag_ira_region == IRA_REGION_ALL
 864               || flag_ira_region == IRA_REGION_MIXED)
 865             propagate_copies ();
 866
 867           /* Now we can free memory for the conflict table (see function
 868              build_object_conflicts for details).  */
 869           FOR_EACH_OBJECT (obj, oi)
 870             {
 871               if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
 872                 ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]);
 873             }
 874           ira_free (conflicts);
 875         }
 876     }
 877   if (! targetm.class_likely_spilled_p (base_reg_class (VOIDmode, ADDRESS,
 878                                                         SCRATCH)))
 879     CLEAR_HARD_REG_SET (temp_hard_reg_set);
 880   else
 881     {
 882       COPY_HARD_REG_SET (temp_hard_reg_set,
 883                          reg_class_contents[base_reg_class (VOIDmode, ADDRESS, SCRATCH)]);
 884       AND_COMPL_HARD_REG_SET (temp_hard_reg_set, ira_no_alloc_regs);
 885       AND_HARD_REG_SET (temp_hard_reg_set, call_used_reg_set);
 886     }
 887   FOR_EACH_ALLOCNO (a, ai)
 888     {
 889       int i, n = ALLOCNO_NUM_OBJECTS (a);
 890
 891       for (i = 0; i < n; i++)
 892         {
 893           ira_object_t obj = ALLOCNO_OBJECT (a, i);
 894           reg_attrs *attrs = REG_ATTRS (regno_reg_rtx [ALLOCNO_REGNO (a)]);
 895           tree decl;
 896
 897           if ((! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 898               /* For debugging purposes don't put user defined variables in
 899                  callee-clobbered registers.  */
 900               || (optimize == 0
 901                   && attrs != NULL
 902                   && (decl = attrs->decl) != NULL
 903                   && VAR_OR_FUNCTION_DECL_P (decl)
 904                   && ! DECL_ARTIFICIAL (decl)))
 905             {
 906               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 907                                 call_used_reg_set);
 908               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 909                                 call_used_reg_set);
 910             }
 911           else if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 912             {
 913               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 914                                 no_caller_save_reg_set);
 915               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 916                                 temp_hard_reg_set);
 917               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 918                                 no_caller_save_reg_set);
 919               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 920                                 temp_hard_reg_set);
 921             }
 922
 923           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 924             {
 925               int regno;
 926
 927               /* Allocnos bigger than the saved part of call saved
 928                  regs must conflict with them.  */
 929               for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 930                 if (!TEST_HARD_REG_BIT (call_used_reg_set, regno)
 931                     && HARD_REGNO_CALL_PART_CLOBBERED (regno,
 932                                                        obj->allocno->mode))
 933                   {
 934                     SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno);
 935                     SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 936                                       regno);
 937                   }
 938             }
 939         }
 940     }
 941   if (optimize && ira_conflicts_p
 942       && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 943     print_conflicts (ira_dump_file, false);
 944 }