gcc/ira-conflicts.c

   1 /* IRA conflict builder.
   2    Copyright (C) 2006-2014 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 "basic-block.h"
  32 #include "insn-config.h"
  33 #include "recog.h"
  34 #include "diagnostic-core.h"
  35 #include "params.h"
  36 #include "df.h"
  37 #include "sparseset.h"
  38 #include "ira-int.h"
  39 #include "addresses.h"
  40
  41 /* This file contains code responsible for allocno conflict creation,
  42    allocno copy creation and allocno info accumulation on upper level
  43    regions.  */
  44
  45 /* ira_allocnos_num array of arrays of bits, recording whether two
  46    allocno's conflict (can't go in the same hardware register).
  47
  48    Some arrays will be used as conflict bit vector of the
  49    corresponding allocnos see function build_object_conflicts.  */
  50 static IRA_INT_TYPE **conflicts;
  51
  52 /* Macro to test a conflict of C1 and C2 in `conflicts'.  */
  53 #define OBJECTS_CONFLICT_P(C1, C2)                                      \
  54   (OBJECT_MIN (C1) <= OBJECT_CONFLICT_ID (C2)                           \
  55    && OBJECT_CONFLICT_ID (C2) <= OBJECT_MAX (C1)                        \
  56    && TEST_MINMAX_SET_BIT (conflicts[OBJECT_CONFLICT_ID (C1)],          \
  57                            OBJECT_CONFLICT_ID (C2),                     \
  58                            OBJECT_MIN (C1), OBJECT_MAX (C1)))
  59
  60 \f
  61 /* Record a conflict between objects OBJ1 and OBJ2.  If necessary,
  62    canonicalize the conflict by recording it for lower-order subobjects
  63    of the corresponding allocnos. */
  64 static void
  65 record_object_conflict (ira_object_t obj1, ira_object_t obj2)
  66 {
  67   ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
  68   ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
  69   int w1 = OBJECT_SUBWORD (obj1);
  70   int w2 = OBJECT_SUBWORD (obj2);
  71   int id1, id2;
  72
  73   /* Canonicalize the conflict.  If two identically-numbered words
  74      conflict, always record this as a conflict between words 0.  That
  75      is the only information we need, and it is easier to test for if
  76      it is collected in each allocno's lowest-order object.  */
  77   if (w1 == w2 && w1 > 0)
  78     {
  79       obj1 = ALLOCNO_OBJECT (a1, 0);
  80       obj2 = ALLOCNO_OBJECT (a2, 0);
  81     }
  82   id1 = OBJECT_CONFLICT_ID (obj1);
  83   id2 = OBJECT_CONFLICT_ID (obj2);
  84
  85   SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1),
  86                       OBJECT_MAX (obj1));
  87   SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2),
  88                       OBJECT_MAX (obj2));
  89 }
  90
  91 /* Build allocno conflict table by processing allocno live ranges.
  92    Return true if the table was built.  The table is not built if it
  93    is too big.  */
  94 static bool
  95 build_conflict_bit_table (void)
  96 {
  97   int i;
  98   unsigned int j;
  99   enum reg_class aclass;
 100   int object_set_words, allocated_words_num, conflict_bit_vec_words_num;
 101   live_range_t r;
 102   ira_allocno_t allocno;
 103   ira_allocno_iterator ai;
 104   sparseset objects_live;
 105   ira_object_t obj;
 106   ira_allocno_object_iterator aoi;
 107
 108   allocated_words_num = 0;
 109   FOR_EACH_ALLOCNO (allocno, ai)
 110     FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
 111       {
 112         if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 113           continue;
 114         conflict_bit_vec_words_num
 115           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 116              / IRA_INT_BITS);
 117         allocated_words_num += conflict_bit_vec_words_num;
 118         if ((unsigned HOST_WIDEST_INT) allocated_words_num * sizeof (IRA_INT_TYPE)
 119             > (unsigned HOST_WIDEST_INT) IRA_MAX_CONFLICT_TABLE_SIZE * 1024 * 1024)
 120           {
 121             if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
 122               fprintf
 123                 (ira_dump_file,
 124                  "+++Conflict table will be too big(>%dMB) -- don't use it\n",
 125                  IRA_MAX_CONFLICT_TABLE_SIZE);
 126             return false;
 127           }
 128       }
 129
 130   conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
 131                                               * ira_objects_num);
 132   allocated_words_num = 0;
 133   FOR_EACH_ALLOCNO (allocno, ai)
 134     FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
 135       {
 136         int id = OBJECT_CONFLICT_ID (obj);
 137         if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 138           {
 139             conflicts[id] = NULL;
 140             continue;
 141           }
 142         conflict_bit_vec_words_num
 143           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 144              / IRA_INT_BITS);
 145         allocated_words_num += conflict_bit_vec_words_num;
 146         conflicts[id]
 147           = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
 148                                            * conflict_bit_vec_words_num);
 149         memset (conflicts[id], 0,
 150                 sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
 151       }
 152
 153   object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
 154   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
 155     fprintf
 156       (ira_dump_file,
 157        "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n",
 158        (long) allocated_words_num * sizeof (IRA_INT_TYPE),
 159        (long) object_set_words * ira_objects_num * sizeof (IRA_INT_TYPE));
 160
 161   objects_live = sparseset_alloc (ira_objects_num);
 162   for (i = 0; i < ira_max_point; i++)
 163     {
 164       for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
 165         {
 166           ira_object_t obj = r->object;
 167           ira_allocno_t allocno = OBJECT_ALLOCNO (obj);
 168           int id = OBJECT_CONFLICT_ID (obj);
 169
 170           gcc_assert (id < ira_objects_num);
 171
 172           aclass = ALLOCNO_CLASS (allocno);
 173           sparseset_set_bit (objects_live, id);
 174           EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
 175             {
 176               ira_object_t live_obj = ira_object_id_map[j];
 177               ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
 178               enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
 179
 180               if (ira_reg_classes_intersect_p[aclass][live_aclass]
 181                   /* Don't set up conflict for the allocno with itself.  */
 182                   && live_a != allocno)
 183                 {
 184                   record_object_conflict (obj, live_obj);
 185                 }
 186             }
 187         }
 188
 189       for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
 190         sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
 191     }
 192   sparseset_free (objects_live);
 193   return true;
 194 }
 195 \f
 196 /* Return true iff allocnos A1 and A2 cannot be allocated to the same
 197    register due to conflicts.  */
 198
 199 static bool
 200 allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2)
 201 {
 202   /* Due to the fact that we canonicalize conflicts (see
 203      record_object_conflict), we only need to test for conflicts of
 204      the lowest order words.  */
 205   ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0);
 206   ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0);
 207
 208   return OBJECTS_CONFLICT_P (obj1, obj2);
 209 }
 210
 211 /* Check that X is REG or SUBREG of REG.  */
 212 #define REG_SUBREG_P(x)                                                 \
 213    (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
 214
 215 /* Return X if X is a REG, otherwise it should be SUBREG of REG and
 216    the function returns the reg in this case.  *OFFSET will be set to
 217    0 in the first case or the regno offset in the first case.  */
 218 static rtx
 219 go_through_subreg (rtx x, int *offset)
 220 {
 221   rtx reg;
 222
 223   *offset = 0;
 224   if (REG_P (x))
 225     return x;
 226   ira_assert (GET_CODE (x) == SUBREG);
 227   reg = SUBREG_REG (x);
 228   ira_assert (REG_P (reg));
 229   if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
 230     *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
 231                                    SUBREG_BYTE (x), GET_MODE (x));
 232   else
 233     *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x)));
 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, 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   enum 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_RTX, 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)
 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_RTX,
 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;
 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           rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
 750
 751           if ((! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 752               /* For debugging purposes don't put user defined variables in
 753                  callee-clobbered registers.  However, do allow parameters
 754                  in callee-clobbered registers to improve debugging.  This
 755                  is a bit of a fragile hack.  */
 756               || (optimize == 0
 757                   && REG_USERVAR_P (allocno_reg)
 758                   && ! reg_is_parm_p (allocno_reg)))
 759             {
 760               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 761                                 call_used_reg_set);
 762               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 763                                 call_used_reg_set);
 764             }
 765           else if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 766             {
 767               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 768                                 no_caller_save_reg_set);
 769               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 770                                 temp_hard_reg_set);
 771               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 772                                 no_caller_save_reg_set);
 773               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 774                                 temp_hard_reg_set);
 775             }
 776
 777           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 778             {
 779               int regno;
 780
 781               /* Allocnos bigger than the saved part of call saved
 782                  regs must conflict with them.  */
 783               for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 784                 if (!TEST_HARD_REG_BIT (call_used_reg_set, regno)
 785                     && HARD_REGNO_CALL_PART_CLOBBERED (regno,
 786                                                        obj->allocno->mode))
 787                   {
 788                     SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno);
 789                     SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 790                                       regno);
 791                   }
 792             }
 793         }
 794     }
 795   if (optimize && ira_conflicts_p
 796       && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 797     print_conflicts (ira_dump_file, false);
 798 }