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

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