gcc/ira-conflicts.c

   1 /* IRA conflict builder.
   2    Copyright (C) 2006-2013 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 /* Return TRUE if the operand constraint STR is commutative.  */
 212 static bool
 213 commutative_constraint_p (const char *str)
 214 {
 215   int curr_alt, c;
 216   bool ignore_p;
 217
 218   for (ignore_p = false, curr_alt = 0;;)
 219     {
 220       c = *str;
 221       if (c == '\0')
 222         break;
 223       str += CONSTRAINT_LEN (c, str);
 224       if (c == '#' || !recog_data.alternative_enabled_p[curr_alt])
 225         ignore_p = true;
 226       else if (c == ',')
 227         {
 228           curr_alt++;
 229           ignore_p = false;
 230         }
 231       else if (! ignore_p)
 232         {
 233           /* Usually `%' is the first constraint character but the
 234              documentation does not require this.  */
 235           if (c == '%')
 236             return true;
 237         }
 238     }
 239   return false;
 240 }
 241
 242 /* Return the number of the operand which should be the same in any
 243    case as operand with number OP_NUM (or negative value if there is
 244    no such operand).  If USE_COMMUT_OP_P is TRUE, the function makes
 245    temporarily commutative operand exchange before this.  The function
 246    takes only really possible alternatives into consideration.  */
 247 static int
 248 get_dup_num (int op_num, bool use_commut_op_p)
 249 {
 250   int curr_alt, c, original, dup;
 251   bool ignore_p, commut_op_used_p;
 252   const char *str;
 253   rtx op;
 254
 255   if (op_num < 0 || recog_data.n_alternatives == 0)
 256     return -1;
 257   op = recog_data.operand[op_num];
 258   commut_op_used_p = true;
 259   if (use_commut_op_p)
 260     {
 261       if (commutative_constraint_p (recog_data.constraints[op_num]))
 262         op_num++;
 263       else if (op_num > 0 && commutative_constraint_p (recog_data.constraints
 264                                                        [op_num - 1]))
 265         op_num--;
 266       else
 267         commut_op_used_p = false;
 268     }
 269   str = recog_data.constraints[op_num];
 270   for (ignore_p = false, original = -1, curr_alt = 0;;)
 271     {
 272       c = *str;
 273       if (c == '\0')
 274         break;
 275       if (c == '#' || !recog_data.alternative_enabled_p[curr_alt])
 276         ignore_p = true;
 277       else if (c == ',')
 278         {
 279           curr_alt++;
 280           ignore_p = false;
 281         }
 282       else if (! ignore_p)
 283         switch (c)
 284           {
 285           case 'X':
 286             return -1;
 287
 288           case 'm':
 289           case 'o':
 290             /* Accept a register which might be placed in memory.  */
 291             return -1;
 292             break;
 293
 294           case 'V':
 295           case '<':
 296           case '>':
 297             break;
 298
 299           case 'p':
 300             if (address_operand (op, VOIDmode))
 301               return -1;
 302             break;
 303
 304           case 'g':
 305             return -1;
 306
 307           case 'r':
 308           case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
 309           case 'h': case 'j': case 'k': case 'l':
 310           case 'q': case 't': case 'u':
 311           case 'v': case 'w': case 'x': case 'y': case 'z':
 312           case 'A': case 'B': case 'C': case 'D':
 313           case 'Q': case 'R': case 'S': case 'T': case 'U':
 314           case 'W': case 'Y': case 'Z':
 315             {
 316               enum reg_class cl;
 317
 318               cl = (c == 'r'
 319                     ? GENERAL_REGS : REG_CLASS_FROM_CONSTRAINT (c, str));
 320               if (cl != NO_REGS)
 321                 return -1;
 322 #ifdef EXTRA_CONSTRAINT_STR
 323               else if (EXTRA_CONSTRAINT_STR (op, c, str))
 324                 return -1;
 325 #endif
 326               break;
 327             }
 328
 329           case '0': case '1': case '2': case '3': case '4':
 330           case '5': case '6': case '7': case '8': case '9':
 331             if (original != -1 && original != c)
 332               return -1;
 333             original = c;
 334             break;
 335           }
 336       str += CONSTRAINT_LEN (c, str);
 337     }
 338   if (original == -1)
 339     return -1;
 340   dup = original - '0';
 341   if (use_commut_op_p)
 342     {
 343       if (commutative_constraint_p (recog_data.constraints[dup]))
 344         dup++;
 345       else if (dup > 0
 346                && commutative_constraint_p (recog_data.constraints[dup -1]))
 347         dup--;
 348       else if (! commut_op_used_p)
 349         return -1;
 350     }
 351   return dup;
 352 }
 353
 354 /* Check that X is REG or SUBREG of REG.  */
 355 #define REG_SUBREG_P(x)                                                 \
 356    (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
 357
 358 /* Return X if X is a REG, otherwise it should be SUBREG of REG and
 359    the function returns the reg in this case.  *OFFSET will be set to
 360    0 in the first case or the regno offset in the first case.  */
 361 static rtx
 362 go_through_subreg (rtx x, int *offset)
 363 {
 364   rtx reg;
 365
 366   *offset = 0;
 367   if (REG_P (x))
 368     return x;
 369   ira_assert (GET_CODE (x) == SUBREG);
 370   reg = SUBREG_REG (x);
 371   ira_assert (REG_P (reg));
 372   if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
 373     *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
 374                                    SUBREG_BYTE (x), GET_MODE (x));
 375   else
 376     *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x)));
 377   return reg;
 378 }
 379
 380 /* Process registers REG1 and REG2 in move INSN with execution
 381    frequency FREQ.  The function also processes the registers in a
 382    potential move insn (INSN == NULL in this case) with frequency
 383    FREQ.  The function can modify hard register costs of the
 384    corresponding allocnos or create a copy involving the corresponding
 385    allocnos.  The function does nothing if the both registers are hard
 386    registers.  When nothing is changed, the function returns
 387    FALSE.  */
 388 static bool
 389 process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p,
 390                        rtx insn, int freq)
 391 {
 392   int allocno_preferenced_hard_regno, cost, index, offset1, offset2;
 393   bool only_regs_p;
 394   ira_allocno_t a;
 395   reg_class_t rclass, aclass;
 396   enum machine_mode mode;
 397   ira_copy_t cp;
 398
 399   gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
 400   only_regs_p = REG_P (reg1) && REG_P (reg2);
 401   reg1 = go_through_subreg (reg1, &offset1);
 402   reg2 = go_through_subreg (reg2, &offset2);
 403   /* Set up hard regno preferenced by allocno.  If allocno gets the
 404      hard regno the copy (or potential move) insn will be removed.  */
 405   if (HARD_REGISTER_P (reg1))
 406     {
 407       if (HARD_REGISTER_P (reg2))
 408         return false;
 409       allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
 410       a = ira_curr_regno_allocno_map[REGNO (reg2)];
 411     }
 412   else if (HARD_REGISTER_P (reg2))
 413     {
 414       allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
 415       a = ira_curr_regno_allocno_map[REGNO (reg1)];
 416     }
 417   else
 418     {
 419       ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)];
 420       ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)];
 421
 422       if (!allocnos_conflict_for_copy_p (a1, a2) && offset1 == offset2)
 423         {
 424           cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn,
 425                                      ira_curr_loop_tree_node);
 426           bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
 427           return true;
 428         }
 429       else
 430         return false;
 431     }
 432
 433   if (! IN_RANGE (allocno_preferenced_hard_regno,
 434                   0, FIRST_PSEUDO_REGISTER - 1))
 435     /* Can not be tied.  */
 436     return false;
 437   rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
 438   mode = ALLOCNO_MODE (a);
 439   aclass = ALLOCNO_CLASS (a);
 440   if (only_regs_p && insn != NULL_RTX
 441       && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode])
 442     /* It is already taken into account in ira-costs.c.  */
 443     return false;
 444   index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno];
 445   if (index < 0)
 446     /* Can not be tied.  It is not in the allocno class.  */
 447     return false;
 448   ira_init_register_move_cost_if_necessary (mode);
 449   if (HARD_REGISTER_P (reg1))
 450     cost = ira_register_move_cost[mode][aclass][rclass] * freq;
 451   else
 452     cost = ira_register_move_cost[mode][rclass][aclass] * freq;
 453   do
 454     {
 455       ira_allocate_and_set_costs
 456         (&ALLOCNO_HARD_REG_COSTS (a), aclass,
 457          ALLOCNO_CLASS_COST (a));
 458       ira_allocate_and_set_costs
 459         (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 0);
 460       ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
 461       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
 462       if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a))
 463         ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
 464       a = ira_parent_or_cap_allocno (a);
 465     }
 466   while (a != NULL);
 467   return true;
 468 }
 469
 470 /* Process all of the output registers of the current insn which are
 471    not bound (BOUND_P) and the input register REG (its operand number
 472    OP_NUM) which dies in the insn as if there were a move insn between
 473    them with frequency FREQ.  */
 474 static void
 475 process_reg_shuffles (rtx reg, int op_num, int freq, bool *bound_p)
 476 {
 477   int i;
 478   rtx another_reg;
 479
 480   gcc_assert (REG_SUBREG_P (reg));
 481   for (i = 0; i < recog_data.n_operands; i++)
 482     {
 483       another_reg = recog_data.operand[i];
 484
 485       if (!REG_SUBREG_P (another_reg) || op_num == i
 486           || recog_data.operand_type[i] != OP_OUT
 487           || bound_p[i])
 488         continue;
 489
 490       process_regs_for_copy (reg, another_reg, false, NULL_RTX, freq);
 491     }
 492 }
 493
 494 /* Process INSN and create allocno copies if necessary.  For example,
 495    it might be because INSN is a pseudo-register move or INSN is two
 496    operand insn.  */
 497 static void
 498 add_insn_allocno_copies (rtx insn)
 499 {
 500   rtx set, operand, dup;
 501   const char *str;
 502   bool commut_p, bound_p[MAX_RECOG_OPERANDS];
 503   int i, j, n, freq;
 504
 505   freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
 506   if (freq == 0)
 507     freq = 1;
 508   if ((set = single_set (insn)) != NULL_RTX
 509       && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
 510       && ! side_effects_p (set)
 511       && find_reg_note (insn, REG_DEAD,
 512                         REG_P (SET_SRC (set))
 513                         ? SET_SRC (set)
 514                         : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
 515     {
 516       process_regs_for_copy (SET_DEST (set), SET_SRC (set),
 517                              false, insn, freq);
 518       return;
 519     }
 520   /* Fast check of possibility of constraint or shuffle copies.  If
 521      there are no dead registers, there will be no such copies.  */
 522   if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
 523     return;
 524   extract_insn (insn);
 525   for (i = 0; i < recog_data.n_operands; i++)
 526     bound_p[i] = false;
 527   for (i = 0; i < recog_data.n_operands; i++)
 528     {
 529       operand = recog_data.operand[i];
 530       if (! REG_SUBREG_P (operand))
 531         continue;
 532       str = recog_data.constraints[i];
 533       while (*str == ' ' || *str == '\t')
 534         str++;
 535       for (j = 0, commut_p = false; j < 2; j++, commut_p = true)
 536         if ((n = get_dup_num (i, commut_p)) >= 0)
 537           {
 538             bound_p[n] = true;
 539             dup = recog_data.operand[n];
 540             if (REG_SUBREG_P (dup)
 541                 && find_reg_note (insn, REG_DEAD,
 542                                   REG_P (operand)
 543                                   ? operand
 544                                   : SUBREG_REG (operand)) != NULL_RTX)
 545               process_regs_for_copy (operand, dup, true, NULL_RTX, freq);
 546           }
 547     }
 548   for (i = 0; i < recog_data.n_operands; i++)
 549     {
 550       operand = recog_data.operand[i];
 551       if (REG_SUBREG_P (operand)
 552           && find_reg_note (insn, REG_DEAD,
 553                             REG_P (operand)
 554                             ? operand : SUBREG_REG (operand)) != NULL_RTX)
 555         /* If an operand dies, prefer its hard register for the output
 556            operands by decreasing the hard register cost or creating
 557            the corresponding allocno copies.  The cost will not
 558            correspond to a real move insn cost, so make the frequency
 559            smaller.  */
 560         process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8, bound_p);
 561     }
 562 }
 563
 564 /* Add copies originated from BB given by LOOP_TREE_NODE.  */
 565 static void
 566 add_copies (ira_loop_tree_node_t loop_tree_node)
 567 {
 568   basic_block bb;
 569   rtx insn;
 570
 571   bb = loop_tree_node->bb;
 572   if (bb == NULL)
 573     return;
 574   FOR_BB_INSNS (bb, insn)
 575     if (NONDEBUG_INSN_P (insn))
 576       add_insn_allocno_copies (insn);
 577 }
 578
 579 /* Propagate copies the corresponding allocnos on upper loop tree
 580    level.  */
 581 static void
 582 propagate_copies (void)
 583 {
 584   ira_copy_t cp;
 585   ira_copy_iterator ci;
 586   ira_allocno_t a1, a2, parent_a1, parent_a2;
 587
 588   FOR_EACH_COPY (cp, ci)
 589     {
 590       a1 = cp->first;
 591       a2 = cp->second;
 592       if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
 593         continue;
 594       ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
 595       parent_a1 = ira_parent_or_cap_allocno (a1);
 596       parent_a2 = ira_parent_or_cap_allocno (a2);
 597       ira_assert (parent_a1 != NULL && parent_a2 != NULL);
 598       if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2))
 599         ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
 600                               cp->constraint_p, cp->insn, cp->loop_tree_node);
 601     }
 602 }
 603
 604 /* Array used to collect all conflict allocnos for given allocno.  */
 605 static ira_object_t *collected_conflict_objects;
 606
 607 /* Build conflict vectors or bit conflict vectors (whatever is more
 608    profitable) for object OBJ from the conflict table.  */
 609 static void
 610 build_object_conflicts (ira_object_t obj)
 611 {
 612   int i, px, parent_num;
 613   ira_allocno_t parent_a, another_parent_a;
 614   ira_object_t parent_obj;
 615   ira_allocno_t a = OBJECT_ALLOCNO (obj);
 616   IRA_INT_TYPE *object_conflicts;
 617   minmax_set_iterator asi;
 618   int parent_min, parent_max ATTRIBUTE_UNUSED;
 619
 620   object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
 621   px = 0;
 622   FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
 623                               OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
 624     {
 625       ira_object_t another_obj = ira_object_id_map[i];
 626       ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
 627
 628       ira_assert (ira_reg_classes_intersect_p
 629                   [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
 630       collected_conflict_objects[px++] = another_obj;
 631     }
 632   if (ira_conflict_vector_profitable_p (obj, px))
 633     {
 634       ira_object_t *vec;
 635       ira_allocate_conflict_vec (obj, px);
 636       vec = OBJECT_CONFLICT_VEC (obj);
 637       memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px);
 638       vec[px] = NULL;
 639       OBJECT_NUM_CONFLICTS (obj) = px;
 640     }
 641   else
 642     {
 643       int conflict_bit_vec_words_num;
 644
 645       OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
 646       if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 647         conflict_bit_vec_words_num = 0;
 648       else
 649         conflict_bit_vec_words_num
 650           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 651              / IRA_INT_BITS);
 652       OBJECT_CONFLICT_ARRAY_SIZE (obj)
 653         = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
 654     }
 655
 656   parent_a = ira_parent_or_cap_allocno (a);
 657   if (parent_a == NULL)
 658     return;
 659   ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
 660   ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
 661   parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
 662   parent_num = OBJECT_CONFLICT_ID (parent_obj);
 663   parent_min = OBJECT_MIN (parent_obj);
 664   parent_max = OBJECT_MAX (parent_obj);
 665   FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
 666                               OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
 667     {
 668       ira_object_t another_obj = ira_object_id_map[i];
 669       ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
 670       int another_word = OBJECT_SUBWORD (another_obj);
 671
 672       ira_assert (ira_reg_classes_intersect_p
 673                   [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
 674
 675       another_parent_a = ira_parent_or_cap_allocno (another_a);
 676       if (another_parent_a == NULL)
 677         continue;
 678       ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
 679       ira_assert (ALLOCNO_CLASS (another_a)
 680                   == ALLOCNO_CLASS (another_parent_a));
 681       ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
 682                   == ALLOCNO_NUM_OBJECTS (another_parent_a));
 683       SET_MINMAX_SET_BIT (conflicts[parent_num],
 684                           OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
 685                                                               another_word)),
 686                           parent_min, parent_max);
 687     }
 688 }
 689
 690 /* Build conflict vectors or bit conflict vectors (whatever is more
 691    profitable) of all allocnos from the conflict table.  */
 692 static void
 693 build_conflicts (void)
 694 {
 695   int i;
 696   ira_allocno_t a, cap;
 697
 698   collected_conflict_objects
 699     = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
 700                                           * ira_objects_num);
 701   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
 702     for (a = ira_regno_allocno_map[i];
 703          a != NULL;
 704          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 705       {
 706         int j, nregs = ALLOCNO_NUM_OBJECTS (a);
 707         for (j = 0; j < nregs; j++)
 708           {
 709             ira_object_t obj = ALLOCNO_OBJECT (a, j);
 710             build_object_conflicts (obj);
 711             for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
 712               {
 713                 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
 714                 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
 715                 build_object_conflicts (cap_obj);
 716               }
 717           }
 718       }
 719   ira_free (collected_conflict_objects);
 720 }
 721
 722 \f
 723
 724 /* Print hard reg set SET with TITLE to FILE.  */
 725 static void
 726 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
 727 {
 728   int i, start;
 729
 730   fputs (title, file);
 731   for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 732     {
 733       if (TEST_HARD_REG_BIT (set, i))
 734         {
 735           if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
 736             start = i;
 737         }
 738       if (start >= 0
 739           && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
 740         {
 741           if (start == i - 1)
 742             fprintf (file, " %d", start);
 743           else if (start == i - 2)
 744             fprintf (file, " %d %d", start, start + 1);
 745           else
 746             fprintf (file, " %d-%d", start, i - 1);
 747           start = -1;
 748         }
 749     }
 750   putc ('\n', file);
 751 }
 752
 753 static void
 754 print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
 755 {
 756   HARD_REG_SET conflicting_hard_regs;
 757   basic_block bb;
 758   int n, i;
 759
 760   if (reg_p)
 761     fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
 762   else
 763     {
 764       fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 765       if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 766         fprintf (file, "b%d", bb->index);
 767       else
 768         fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
 769       putc (')', file);
 770     }
 771
 772   fputs (" conflicts:", file);
 773   n = ALLOCNO_NUM_OBJECTS (a);
 774   for (i = 0; i < n; i++)
 775     {
 776       ira_object_t obj = ALLOCNO_OBJECT (a, i);
 777       ira_object_t conflict_obj;
 778       ira_object_conflict_iterator oci;
 779
 780       if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
 781         continue;
 782       if (n > 1)
 783         fprintf (file, "\n;;   subobject %d:", i);
 784       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
 785         {
 786           ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
 787           if (reg_p)
 788             fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
 789           else
 790             {
 791               fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a),
 792                        ALLOCNO_REGNO (conflict_a));
 793               if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
 794                 fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj));
 795               if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
 796                 fprintf (file, ",b%d", bb->index);
 797               else
 798                 fprintf (file, ",l%d",
 799                          ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num);
 800               putc (')', file);
 801             }
 802         }
 803       COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
 804       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 805       AND_HARD_REG_SET (conflicting_hard_regs,
 806                         reg_class_contents[ALLOCNO_CLASS (a)]);
 807       print_hard_reg_set (file, "\n;;     total conflict hard regs:",
 808                           conflicting_hard_regs);
 809
 810       COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_CONFLICT_HARD_REGS (obj));
 811       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 812       AND_HARD_REG_SET (conflicting_hard_regs,
 813                         reg_class_contents[ALLOCNO_CLASS (a)]);
 814       print_hard_reg_set (file, ";;     conflict hard regs:",
 815                           conflicting_hard_regs);
 816       putc ('\n', file);
 817     }
 818
 819 }
 820
 821 /* Print information about allocno or only regno (if REG_P) conflicts
 822    to FILE.  */
 823 static void
 824 print_conflicts (FILE *file, bool reg_p)
 825 {
 826   ira_allocno_t a;
 827   ira_allocno_iterator ai;
 828
 829   FOR_EACH_ALLOCNO (a, ai)
 830     print_allocno_conflicts (file, reg_p, a);
 831 }
 832
 833 /* Print information about allocno or only regno (if REG_P) conflicts
 834    to stderr.  */
 835 void
 836 ira_debug_conflicts (bool reg_p)
 837 {
 838   print_conflicts (stderr, reg_p);
 839 }
 840
 841 \f
 842
 843 /* Entry function which builds allocno conflicts and allocno copies
 844    and accumulate some allocno info on upper level regions.  */
 845 void
 846 ira_build_conflicts (void)
 847 {
 848   enum reg_class base;
 849   ira_allocno_t a;
 850   ira_allocno_iterator ai;
 851   HARD_REG_SET temp_hard_reg_set;
 852
 853   if (ira_conflicts_p)
 854     {
 855       ira_conflicts_p = build_conflict_bit_table ();
 856       if (ira_conflicts_p)
 857         {
 858           ira_object_t obj;
 859           ira_object_iterator oi;
 860
 861           build_conflicts ();
 862           ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL);
 863           /* We need finished conflict table for the subsequent call.  */
 864           if (flag_ira_region == IRA_REGION_ALL
 865               || flag_ira_region == IRA_REGION_MIXED)
 866             propagate_copies ();
 867
 868           /* Now we can free memory for the conflict table (see function
 869              build_object_conflicts for details).  */
 870           FOR_EACH_OBJECT (obj, oi)
 871             {
 872               if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
 873                 ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]);
 874             }
 875           ira_free (conflicts);
 876         }
 877     }
 878   base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, ADDRESS, SCRATCH);
 879   if (! targetm.class_likely_spilled_p (base))
 880     CLEAR_HARD_REG_SET (temp_hard_reg_set);
 881   else
 882     {
 883       COPY_HARD_REG_SET (temp_hard_reg_set, reg_class_contents[base]);
 884       AND_COMPL_HARD_REG_SET (temp_hard_reg_set, ira_no_alloc_regs);
 885       AND_HARD_REG_SET (temp_hard_reg_set, call_used_reg_set);
 886     }
 887   FOR_EACH_ALLOCNO (a, ai)
 888     {
 889       int i, n = ALLOCNO_NUM_OBJECTS (a);
 890
 891       for (i = 0; i < n; i++)
 892         {
 893           ira_object_t obj = ALLOCNO_OBJECT (a, i);
 894           rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
 895
 896           if ((! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 897               /* For debugging purposes don't put user defined variables in
 898                  callee-clobbered registers.  However, do allow parameters
 899                  in callee-clobbered registers to improve debugging.  This
 900                  is a bit of a fragile hack.  */
 901               || (optimize == 0
 902                   && REG_USERVAR_P (allocno_reg)
 903                   && ! reg_is_parm_p (allocno_reg)))
 904             {
 905               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 906                                 call_used_reg_set);
 907               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 908                                 call_used_reg_set);
 909             }
 910           else if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 911             {
 912               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 913                                 no_caller_save_reg_set);
 914               IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 915                                 temp_hard_reg_set);
 916               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 917                                 no_caller_save_reg_set);
 918               IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 919                                 temp_hard_reg_set);
 920             }
 921
 922           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 923             {
 924               int regno;
 925
 926               /* Allocnos bigger than the saved part of call saved
 927                  regs must conflict with them.  */
 928               for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 929                 if (!TEST_HARD_REG_BIT (call_used_reg_set, regno)
 930                     && HARD_REGNO_CALL_PART_CLOBBERED (regno,
 931                                                        obj->allocno->mode))
 932                   {
 933                     SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno);
 934                     SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 935                                       regno);
 936                   }
 937             }
 938         }
 939     }
 940   if (optimize && ira_conflicts_p
 941       && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 942     print_conflicts (ira_dump_file, false);
 943 }