gcc/ira-conflicts.c

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