gcc/ira-conflicts.c

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