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