contrib/gcc-5.0/gcc/ira-conflicts.c

   1 /* IRA conflict builder.
   2    Copyright (C) 2006-2015 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "regs.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "target.h"
  29 #include "flags.h"
  30 #include "hard-reg-set.h"
  31 #include "predict.h"
  32 #include "vec.h"
  33 #include "hashtab.h"
  34 #include "hash-set.h"
  35 #include "machmode.h"
  36 #include "input.h"
  37 #include "function.h"
  38 #include "basic-block.h"
  39 #include "insn-config.h"
  40 #include "recog.h"
  41 #include "diagnostic-core.h"
  42 #include "params.h"
  43 #include "df.h"
  44 #include "sparseset.h"
  45 #include "ira-int.h"
  46 #include "addresses.h"
  47
  48 /* This file contains code responsible for allocno conflict creation,
  49    allocno copy creation and allocno info accumulation on upper level
  50    regions.  */
  51
  52 /* ira_allocnos_num array of arrays of bits, recording whether two
  53    allocno's conflict (can't go in the same hardware register).
  54
  55    Some arrays will be used as conflict bit vector of the
  56    corresponding allocnos see function build_object_conflicts.  */
  57 static IRA_INT_TYPE **conflicts;
  58
  59 /* Macro to test a conflict of C1 and C2 in `conflicts'.  */
  60 #define OBJECTS_CONFLICT_P(C1, C2)                                      \
  61   (OBJECT_MIN (C1) <= OBJECT_CONFLICT_ID (C2)                           \
  62    && OBJECT_CONFLICT_ID (C2) <= OBJECT_MAX (C1)                        \
  63    && TEST_MINMAX_SET_BIT (conflicts[OBJECT_CONFLICT_ID (C1)],          \
  64                            OBJECT_CONFLICT_ID (C2),                     \
  65                            OBJECT_MIN (C1), OBJECT_MAX (C1)))
  66
  67 \f
  68 /* Record a conflict between objects OBJ1 and OBJ2.  If necessary,
  69    canonicalize the conflict by recording it for lower-order subobjects
  70    of the corresponding allocnos.  */
  71 static void
  72 record_object_conflict (ira_object_t obj1, ira_object_t obj2)
  73 {
  74   ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
  75   ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
  76   int w1 = OBJECT_SUBWORD (obj1);
  77   int w2 = OBJECT_SUBWORD (obj2);
  78   int id1, id2;
  79
  80   /* Canonicalize the conflict.  If two identically-numbered words
  81      conflict, always record this as a conflict between words 0.  That
  82      is the only information we need, and it is easier to test for if
  83      it is collected in each allocno's lowest-order object.  */
  84   if (w1 == w2 && w1 > 0)
  85     {
  86       obj1 = ALLOCNO_OBJECT (a1, 0);
  87       obj2 = ALLOCNO_OBJECT (a2, 0);
  88     }
  89   id1 = OBJECT_CONFLICT_ID (obj1);
  90   id2 = OBJECT_CONFLICT_ID (obj2);
  91
  92   SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1),
  93                       OBJECT_MAX (obj1));
  94   SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2),
  95                       OBJECT_MAX (obj2));
  96 }
  97
  98 /* Build allocno conflict table by processing allocno live ranges.
  99    Return true if the table was built.  The table is not built if it
 100    is too big.  */
 101 static bool
 102 build_conflict_bit_table (void)
 103 {
 104   int i;
 105   unsigned int j;
 106   enum reg_class aclass;
 107   int object_set_words, allocated_words_num, conflict_bit_vec_words_num;
 108   live_range_t r;
 109   ira_allocno_t allocno;
 110   ira_allocno_iterator ai;
 111   sparseset objects_live;
 112   ira_object_t obj;
 113   ira_allocno_object_iterator aoi;
 114
 115   allocated_words_num = 0;
 116   FOR_EACH_ALLOCNO (allocno, ai)
 117     FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
 118       {
 119         if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 120           continue;
 121         conflict_bit_vec_words_num
 122           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 123              / IRA_INT_BITS);
 124         allocated_words_num += conflict_bit_vec_words_num;
 125         if ((uint64_t) allocated_words_num * sizeof (IRA_INT_TYPE)
 126             > (uint64_t) IRA_MAX_CONFLICT_TABLE_SIZE * 1024 * 1024)
 127           {
 128             if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
 129               fprintf
 130                 (ira_dump_file,
 131                  "+++Conflict table will be too big(>%dMB) -- don't use it\n",
 132                  IRA_MAX_CONFLICT_TABLE_SIZE);
 133             return false;
 134           }
 135       }
 136
 137   conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
 138                                               * ira_objects_num);
 139   allocated_words_num = 0;
 140   FOR_EACH_ALLOCNO (allocno, ai)
 141     FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
 142       {
 143         int id = OBJECT_CONFLICT_ID (obj);
 144         if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 145           {
 146             conflicts[id] = NULL;
 147             continue;
 148           }
 149         conflict_bit_vec_words_num
 150           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 151              / IRA_INT_BITS);
 152         allocated_words_num += conflict_bit_vec_words_num;
 153         conflicts[id]
 154           = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
 155                                            * conflict_bit_vec_words_num);
 156         memset (conflicts[id], 0,
 157                 sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
 158       }
 159
 160   object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
 161   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
 162     fprintf
 163       (ira_dump_file,
 164        "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n",
 165        (long) allocated_words_num * sizeof (IRA_INT_TYPE),
 166        (long) object_set_words * ira_objects_num * sizeof (IRA_INT_TYPE));
 167
 168   objects_live = sparseset_alloc (ira_objects_num);
 169   for (i = 0; i < ira_max_point; i++)
 170     {
 171       for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
 172         {
 173           ira_object_t obj = r->object;
 174           ira_allocno_t allocno = OBJECT_ALLOCNO (obj);
 175           int id = OBJECT_CONFLICT_ID (obj);
 176
 177           gcc_assert (id < ira_objects_num);
 178
 179           aclass = ALLOCNO_CLASS (allocno);
 180           EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
 181             {
 182               ira_object_t live_obj = ira_object_id_map[j];
 183               ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
 184               enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
 185
 186               if (ira_reg_classes_intersect_p[aclass][live_aclass]
 187                   /* Don't set up conflict for the allocno with itself.  */
 188                   && live_a != allocno)
 189                 {
 190                   record_object_conflict (obj, live_obj);
 191                 }
 192             }
 193           sparseset_set_bit (objects_live, id);
 194         }
 195
 196       for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
 197         sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
 198     }
 199   sparseset_free (objects_live);
 200   return true;
 201 }
 202 \f
 203 /* Return true iff allocnos A1 and A2 cannot be allocated to the same
 204    register due to conflicts.  */
 205
 206 static bool
 207 allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2)
 208 {
 209   /* Due to the fact that we canonicalize conflicts (see
 210      record_object_conflict), we only need to test for conflicts of
 211      the lowest order words.  */
 212   ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0);
 213   ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0);
 214
 215   return OBJECTS_CONFLICT_P (obj1, obj2);
 216 }
 217
 218 /* Check that X is REG or SUBREG of REG.  */
 219 #define REG_SUBREG_P(x)                                                 \
 220    (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
 221
 222 /* Return X if X is a REG, otherwise it should be SUBREG of REG and
 223    the function returns the reg in this case.  *OFFSET will be set to
 224    0 in the first case or the regno offset in the first case.  */
 225 static rtx
 226 go_through_subreg (rtx x, int *offset)
 227 {
 228   rtx reg;
 229
 230   *offset = 0;
 231   if (REG_P (x))
 232     return x;
 233   ira_assert (GET_CODE (x) == SUBREG);
 234   reg = SUBREG_REG (x);
 235   ira_assert (REG_P (reg));
 236   if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
 237     *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
 238                                    SUBREG_BYTE (x), GET_MODE (x));
 239   else
 240     *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x)));
 241   return reg;
 242 }
 243
 244 /* Process registers REG1 and REG2 in move INSN with execution
 245    frequency FREQ.  The function also processes the registers in a
 246    potential move insn (INSN == NULL in this case) with frequency
 247    FREQ.  The function can modify hard register costs of the
 248    corresponding allocnos or create a copy involving the corresponding
 249    allocnos.  The function does nothing if the both registers are hard
 250    registers.  When nothing is changed, the function returns
 251    FALSE.  */
 252 static bool
 253 process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p,
 254                        rtx_insn *insn, int freq)
 255 {
 256   int allocno_preferenced_hard_regno, cost, index, offset1, offset2;
 257   bool only_regs_p;
 258   ira_allocno_t a;
 259   reg_class_t rclass, aclass;
 260   machine_mode mode;
 261   ira_copy_t cp;
 262
 263   gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
 264   only_regs_p = REG_P (reg1) && REG_P (reg2);
 265   reg1 = go_through_subreg (reg1, &offset1);
 266   reg2 = go_through_subreg (reg2, &offset2);
 267   /* Set up hard regno preferenced by allocno.  If allocno gets the
 268      hard regno the copy (or potential move) insn will be removed.  */
 269   if (HARD_REGISTER_P (reg1))
 270     {
 271       if (HARD_REGISTER_P (reg2))
 272         return false;
 273       allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
 274       a = ira_curr_regno_allocno_map[REGNO (reg2)];
 275     }
 276   else if (HARD_REGISTER_P (reg2))
 277     {
 278       allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
 279       a = ira_curr_regno_allocno_map[REGNO (reg1)];
 280     }
 281   else
 282     {
 283       ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)];
 284       ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)];
 285
 286       if (!allocnos_conflict_for_copy_p (a1, a2) && offset1 == offset2)
 287         {
 288           cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn,
 289                                      ira_curr_loop_tree_node);
 290           bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
 291           return true;
 292         }
 293       else
 294         return false;
 295     }
 296
 297   if (! IN_RANGE (allocno_preferenced_hard_regno,
 298                   0, FIRST_PSEUDO_REGISTER - 1))
 299     /* Can not be tied.  */
 300     return false;
 301   rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
 302   mode = ALLOCNO_MODE (a);
 303   aclass = ALLOCNO_CLASS (a);
 304   if (only_regs_p && insn != NULL_RTX
 305       && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode])
 306     /* It is already taken into account in ira-costs.c.  */
 307     return false;
 308   index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno];
 309   if (index < 0)
 310     /* Can not be tied.  It is not in the allocno class.  */
 311     return false;
 312   ira_init_register_move_cost_if_necessary (mode);
 313   if (HARD_REGISTER_P (reg1))
 314     cost = ira_register_move_cost[mode][aclass][rclass] * freq;
 315   else
 316     cost = ira_register_move_cost[mode][rclass][aclass] * freq;
 317   do
 318     {
 319       ira_allocate_and_set_costs
 320         (&ALLOCNO_HARD_REG_COSTS (a), aclass,
 321          ALLOCNO_CLASS_COST (a));
 322       ira_allocate_and_set_costs
 323         (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 0);
 324       ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
 325       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
 326       if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a))
 327         ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
 328       ira_add_allocno_pref (a, allocno_preferenced_hard_regno, freq);
 329       a = ira_parent_or_cap_allocno (a);
 330     }
 331   while (a != NULL);
 332   return true;
 333 }
 334
 335 /* Process all of the output registers of the current insn which are
 336    not bound (BOUND_P) and the input register REG (its operand number
 337    OP_NUM) which dies in the insn as if there were a move insn between
 338    them with frequency FREQ.  */
 339 static void
 340 process_reg_shuffles (rtx reg, int op_num, int freq, bool *bound_p)
 341 {
 342   int i;
 343   rtx another_reg;
 344
 345   gcc_assert (REG_SUBREG_P (reg));
 346   for (i = 0; i < recog_data.n_operands; i++)
 347     {
 348       another_reg = recog_data.operand[i];
 349
 350       if (!REG_SUBREG_P (another_reg) || op_num == i
 351           || recog_data.operand_type[i] != OP_OUT
 352           || bound_p[i])
 353         continue;
 354
 355       process_regs_for_copy (reg, another_reg, false, NULL, freq);
 356     }
 357 }
 358
 359 /* Process INSN and create allocno copies if necessary.  For example,
 360    it might be because INSN is a pseudo-register move or INSN is two
 361    operand insn.  */
 362 static void
 363 add_insn_allocno_copies (rtx_insn *insn)
 364 {
 365   rtx set, operand, dup;
 366   bool bound_p[MAX_RECOG_OPERANDS];
 367   int i, n, freq;
 368   HARD_REG_SET alts;
 369
 370   freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
 371   if (freq == 0)
 372     freq = 1;
 373   if ((set = single_set (insn)) != NULL_RTX
 374       && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
 375       && ! side_effects_p (set)
 376       && find_reg_note (insn, REG_DEAD,
 377                         REG_P (SET_SRC (set))
 378                         ? SET_SRC (set)
 379                         : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
 380     {
 381       process_regs_for_copy (SET_SRC (set), SET_DEST (set),
 382                              false, insn, freq);
 383       return;
 384     }
 385   /* Fast check of possibility of constraint or shuffle copies.  If
 386      there are no dead registers, there will be no such copies.  */
 387   if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
 388     return;
 389   ira_setup_alts (insn, alts);
 390   for (i = 0; i < recog_data.n_operands; i++)
 391     bound_p[i] = false;
 392   for (i = 0; i < recog_data.n_operands; i++)
 393     {
 394       operand = recog_data.operand[i];
 395       if (! REG_SUBREG_P (operand))
 396         continue;
 397       if ((n = ira_get_dup_out_num (i, alts)) >= 0)
 398         {
 399           bound_p[n] = true;
 400           dup = recog_data.operand[n];
 401           if (REG_SUBREG_P (dup)
 402               && find_reg_note (insn, REG_DEAD,
 403                                 REG_P (operand)
 404                                 ? operand
 405                                 : SUBREG_REG (operand)) != NULL_RTX)
 406             process_regs_for_copy (operand, dup, true, NULL,
 407                                    freq);
 408         }
 409     }
 410   for (i = 0; i < recog_data.n_operands; i++)
 411     {
 412       operand = recog_data.operand[i];
 413       if (REG_SUBREG_P (operand)
 414           && find_reg_note (insn, REG_DEAD,
 415                             REG_P (operand)
 416                             ? operand : SUBREG_REG (operand)) != NULL_RTX)
 417         /* If an operand dies, prefer its hard register for the output
 418            operands by decreasing the hard register cost or creating
 419            the corresponding allocno copies.  The cost will not
 420            correspond to a real move insn cost, so make the frequency
 421            smaller.  */
 422         process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8, bound_p);
 423     }
 424 }
 425
 426 /* Add copies originated from BB given by LOOP_TREE_NODE.  */
 427 static void
 428 add_copies (ira_loop_tree_node_t loop_tree_node)
 429 {
 430   basic_block bb;
 431   rtx_insn *insn;
 432
 433   bb = loop_tree_node->bb;
 434   if (bb == NULL)
 435     return;
 436   FOR_BB_INSNS (bb, insn)
 437     if (NONDEBUG_INSN_P (insn))
 438       add_insn_allocno_copies (insn);
 439 }
 440
 441 /* Propagate copies the corresponding allocnos on upper loop tree
 442    level.  */
 443 static void
 444 propagate_copies (void)
 445 {
 446   ira_copy_t cp;
 447   ira_copy_iterator ci;
 448   ira_allocno_t a1, a2, parent_a1, parent_a2;
 449
 450   FOR_EACH_COPY (cp, ci)
 451     {
 452       a1 = cp->first;
 453       a2 = cp->second;
 454       if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
 455         continue;
 456       ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
 457       parent_a1 = ira_parent_or_cap_allocno (a1);
 458       parent_a2 = ira_parent_or_cap_allocno (a2);
 459       ira_assert (parent_a1 != NULL && parent_a2 != NULL);
 460       if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2))
 461         ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
 462                               cp->constraint_p, cp->insn, cp->loop_tree_node);
 463     }
 464 }
 465
 466 /* Array used to collect all conflict allocnos for given allocno.  */
 467 static ira_object_t *collected_conflict_objects;
 468
 469 /* Build conflict vectors or bit conflict vectors (whatever is more
 470    profitable) for object OBJ from the conflict table.  */
 471 static void
 472 build_object_conflicts (ira_object_t obj)
 473 {
 474   int i, px, parent_num;
 475   ira_allocno_t parent_a, another_parent_a;
 476   ira_object_t parent_obj;
 477   ira_allocno_t a = OBJECT_ALLOCNO (obj);
 478   IRA_INT_TYPE *object_conflicts;
 479   minmax_set_iterator asi;
 480   int parent_min, parent_max ATTRIBUTE_UNUSED;
 481
 482   object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
 483   px = 0;
 484   FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
 485                               OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
 486     {
 487       ira_object_t another_obj = ira_object_id_map[i];
 488       ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
 489
 490       ira_assert (ira_reg_classes_intersect_p
 491                   [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
 492       collected_conflict_objects[px++] = another_obj;
 493     }
 494   if (ira_conflict_vector_profitable_p (obj, px))
 495     {
 496       ira_object_t *vec;
 497       ira_allocate_conflict_vec (obj, px);
 498       vec = OBJECT_CONFLICT_VEC (obj);
 499       memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px);
 500       vec[px] = NULL;
 501       OBJECT_NUM_CONFLICTS (obj) = px;
 502     }
 503   else
 504     {
 505       int conflict_bit_vec_words_num;
 506
 507       OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
 508       if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 509         conflict_bit_vec_words_num = 0;
 510       else
 511         conflict_bit_vec_words_num
 512           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 513              / IRA_INT_BITS);
 514       OBJECT_CONFLICT_ARRAY_SIZE (obj)
 515         = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
 516     }
 517
 518   parent_a = ira_parent_or_cap_allocno (a);
 519   if (parent_a == NULL)
 520     return;
 521   ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
 522   ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
 523   parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
 524   parent_num = OBJECT_CONFLICT_ID (parent_obj);
 525   parent_min = OBJECT_MIN (parent_obj);
 526   parent_max = OBJECT_MAX (parent_obj);
 527   FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
 528                               OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
 529     {
 530       ira_object_t another_obj = ira_object_id_map[i];
 531       ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
 532       int another_word = OBJECT_SUBWORD (another_obj);
 533
 534       ira_assert (ira_reg_classes_intersect_p
 535                   [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
 536
 537       another_parent_a = ira_parent_or_cap_allocno (another_a);
 538       if (another_parent_a == NULL)
 539         continue;
 540       ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
 541       ira_assert (ALLOCNO_CLASS (another_a)
 542                   == ALLOCNO_CLASS (another_parent_a));
 543       ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
 544                   == ALLOCNO_NUM_OBJECTS (another_parent_a));
 545       SET_MINMAX_SET_BIT (conflicts[parent_num],
 546                           OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
 547                                                               another_word)),
 548                           parent_min, parent_max);
 549     }
 550 }
 551
 552 /* Build conflict vectors or bit conflict vectors (whatever is more
 553    profitable) of all allocnos from the conflict table.  */
 554 static void
 555 build_conflicts (void)
 556 {
 557   int i;
 558   ira_allocno_t a, cap;
 559
 560   collected_conflict_objects
 561     = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
 562                                           * ira_objects_num);
 563   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
 564     for (a = ira_regno_allocno_map[i];
 565          a != NULL;
 566          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 567       {
 568         int j, nregs = ALLOCNO_NUM_OBJECTS (a);
 569         for (j = 0; j < nregs; j++)
 570           {
 571             ira_object_t obj = ALLOCNO_OBJECT (a, j);
 572             build_object_conflicts (obj);
 573             for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
 574               {
 575                 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
 576                 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
 577                 build_object_conflicts (cap_obj);
 578               }
 579           }
 580       }
 581   ira_free (collected_conflict_objects);
 582 }
 583
 584 \f
 585
 586 /* Print hard reg set SET with TITLE to FILE.  */
 587 static void
 588 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
 589 {
 590   int i, start;
 591
 592   fputs (title, file);
 593   for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 594     {
 595       if (TEST_HARD_REG_BIT (set, i))
 596         {
 597           if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
 598             start = i;
 599         }
 600       if (start >= 0
 601           && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
 602         {
 603           if (start == i - 1)
 604             fprintf (file, " %d", start);
 605           else if (start == i - 2)
 606             fprintf (file, " %d %d", start, start + 1);
 607           else
 608             fprintf (file, " %d-%d", start, i - 1);
 609           start = -1;
 610         }
 611     }
 612   putc ('\n', file);
 613 }
 614
 615 static void
 616 print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
 617 {
 618   HARD_REG_SET conflicting_hard_regs;
 619   basic_block bb;
 620   int n, i;
 621
 622   if (reg_p)
 623     fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
 624   else
 625     {
 626       fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 627       if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 628         fprintf (file, "b%d", bb->index);
 629       else
 630         fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
 631       putc (')', file);
 632     }
 633
 634   fputs (" conflicts:", file);
 635   n = ALLOCNO_NUM_OBJECTS (a);
 636   for (i = 0; i < n; i++)
 637     {
 638       ira_object_t obj = ALLOCNO_OBJECT (a, i);
 639       ira_object_t conflict_obj;
 640       ira_object_conflict_iterator oci;
 641
 642       if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
 643         continue;
 644       if (n > 1)
 645         fprintf (file, "\n;;   subobject %d:", i);
 646       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
 647         {
 648           ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
 649           if (reg_p)
 650             fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
 651           else
 652             {
 653               fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a),
 654                        ALLOCNO_REGNO (conflict_a));
 655               if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
 656                 fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj));
 657               if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
 658                 fprintf (file, ",b%d", bb->index);
 659               else
 660                 fprintf (file, ",l%d",
 661                          ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num);
 662               putc (')', file);
 663             }
 664         }
 665       COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
 666       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 667       AND_HARD_REG_SET (conflicting_hard_regs,
 668                         reg_class_contents[ALLOCNO_CLASS (a)]);
 669       print_hard_reg_set (file, "\n;;     total conflict hard regs:",
 670                           conflicting_hard_regs);
 671
 672       COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_CONFLICT_HARD_REGS (obj));
 673       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 674       AND_HARD_REG_SET (conflicting_hard_regs,
 675                         reg_class_contents[ALLOCNO_CLASS (a)]);
 676       print_hard_reg_set (file, ";;     conflict hard regs:",
 677                           conflicting_hard_regs);
 678       putc ('\n', file);
 679     }
 680
 681 }
 682
 683 /* Print information about allocno or only regno (if REG_P) conflicts
 684    to FILE.  */
 685 static void
 686 print_conflicts (FILE *file, bool reg_p)
 687 {
 688   ira_allocno_t a;
 689   ira_allocno_iterator ai;
 690
 691   FOR_EACH_ALLOCNO (a, ai)
 692     print_allocno_conflicts (file, reg_p, a);
 693 }
 694
 695 /* Print information about allocno or only regno (if REG_P) conflicts
 696    to stderr.  */
 697 void
 698 ira_debug_conflicts (bool reg_p)
 699 {
 700   print_conflicts (stderr, reg_p);
 701 }
 702
 703 \f
 704
 705 /* Entry function which builds allocno conflicts and allocno copies
 706    and accumulate some allocno info on upper level regions.  */
 707 void
 708 ira_build_conflicts (void)
 709 {
 710   enum reg_class base;
 711   ira_allocno_t a;
 712   ira_allocno_iterator ai;
 713   HARD_REG_SET temp_hard_reg_set;
 714
 715   if (ira_conflicts_p)
 716     {
 717       ira_conflicts_p = build_conflict_bit_table ();
 718       if (ira_conflicts_p)
 719         {
 720           ira_object_t obj;
 721           ira_object_iterator oi;
 722
 723           build_conflicts ();
 724           ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL);
 725           /* We need finished conflict table for the subsequent call.  */
 726           if (flag_ira_region == IRA_REGION_ALL
 727               || flag_ira_region == IRA_REGION_MIXED)
 728             propagate_copies ();
 729
 730           /* Now we can free memory for the conflict table (see function
 731              build_object_conflicts for details).  */
 732           FOR_EACH_OBJECT (obj, oi)
 733             {
 734               if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
 735                 ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]);
 736             }
 737           ira_free (conflicts);
 738         }
 739     }
 740   base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, ADDRESS, SCRATCH);
 741   if (! targetm.class_likely_spilled_p (base))
 742     CLEAR_HARD_REG_SET (temp_hard_reg_set);
 743   else
 744     {
 745       COPY_HARD_REG_SET (temp_hard_reg_set, reg_class_contents[base]);
 746       AND_COMPL_HARD_REG_SET (temp_hard_reg_set, ira_no_alloc_regs);
 747       AND_HARD_REG_SET (temp_hard_reg_set, call_used_reg_set);
 748     }
 749   FOR_EACH_ALLOCNO (a, ai)
 750     {
 751       int i, n = ALLOCNO_NUM_OBJECTS (a);
 752
 753       for (i = 0; i < n; i++)
 754         {
 755           ira_object_t obj = ALLOCNO_OBJECT (a, i);
 756           rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
 757
 758           if ((! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 759               /* For debugging purposes don't put user defined variables in
 760                  callee-clobbered registers.  However, do allow parameters
 761                  in callee-clobbered registers to improve debugging.  This
 762                  is a bit of a fragile hack.  */
 763               || (optimize == 0
 764                   && REG_USERVAR_P (allocno_reg)
 765                   && ! reg_is_parm_p (allocno_reg)))
 766             {
 767               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 768                                 call_used_reg_set);
 769               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 770                                 call_used_reg_set);
 771             }
 772           else if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 773             {
 774               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 775                                 no_caller_save_reg_set);
 776               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 777                                 temp_hard_reg_set);
 778               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 779                                 no_caller_save_reg_set);
 780               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 781                                 temp_hard_reg_set);
 782             }
 783
 784           /* Now we deal with paradoxical subreg cases where certain registers
 785              cannot be accessed in the widest mode.  */
 786           machine_mode outer_mode = ALLOCNO_WMODE (a);
 787           machine_mode inner_mode = ALLOCNO_MODE (a);
 788           if (GET_MODE_SIZE (outer_mode) > GET_MODE_SIZE (inner_mode))
 789             {
 790               enum reg_class aclass = ALLOCNO_CLASS (a);
 791               for (int j = ira_class_hard_regs_num[aclass] - 1; j >= 0; --j)
 792                 {
 793                    int inner_regno = ira_class_hard_regs[aclass][j];
 794                    int outer_regno = simplify_subreg_regno (inner_regno,
 795                                                             inner_mode, 0,
 796                                                             outer_mode);
 797                    if (outer_regno < 0
 798                        || !in_hard_reg_set_p (reg_class_contents[aclass],
 799                                               outer_mode, outer_regno))
 800                      SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj),
 801                                        inner_regno);
 802                 }
 803             }
 804
 805           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 806             {
 807               int regno;
 808
 809               /* Allocnos bigger than the saved part of call saved
 810                  regs must conflict with them.  */
 811               for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 812                 if (!TEST_HARD_REG_BIT (call_used_reg_set, regno)
 813                     && HARD_REGNO_CALL_PART_CLOBBERED (regno,
 814                                                        obj->allocno->mode))
 815                   {
 816                     SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno);
 817                     SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 818                                       regno);
 819                   }
 820             }
 821         }
 822     }
 823   if (optimize && ira_conflicts_p
 824       && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 825     print_conflicts (ira_dump_file, false);
 826 }