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 "toplev.h"
  37 #include "params.h"
  38 #include "df.h"
  39 #include "sparseset.h"
  40 #include "ira-int.h"
  41 #include "addresses.h"
  42
  43 /* This file contains code responsible for allocno conflict creation,
  44    allocno copy creation and allocno info accumulation on upper level
  45    regions.  */
  46
  47 /* ira_allocnos_num array of arrays of bits, recording whether two
  48    allocno's conflict (can't go in the same hardware register).
  49
  50    Some arrays will be used as conflict bit vector of the
  51    corresponding allocnos see function build_object_conflicts.  */
  52 static IRA_INT_TYPE **conflicts;
  53
  54 /* Macro to test a conflict of C1 and C2 in `conflicts'.  */
  55 #define OBJECTS_CONFLICT_P(C1, C2)                                      \
  56   (OBJECT_MIN (C1) <= OBJECT_CONFLICT_ID (C2)                           \
  57    && OBJECT_CONFLICT_ID (C2) <= OBJECT_MAX (C1)                        \
  58    && TEST_MINMAX_SET_BIT (conflicts[OBJECT_CONFLICT_ID (C1)],          \
  59                            OBJECT_CONFLICT_ID (C2),                     \
  60                            OBJECT_MIN (C1), OBJECT_MAX (C1)))
  61
  62 \f
  63 /* Record a conflict between objects OBJ1 and OBJ2.  If necessary,
  64    canonicalize the conflict by recording it for lower-order subobjects
  65    of the corresponding allocnos. */
  66 static void
  67 record_object_conflict (ira_object_t obj1, ira_object_t obj2)
  68 {
  69   ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
  70   ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
  71   int w1 = OBJECT_SUBWORD (obj1);
  72   int w2 = OBJECT_SUBWORD (obj2);
  73   int id1, id2;
  74
  75   /* Canonicalize the conflict.  If two identically-numbered words
  76      conflict, always record this as a conflict between words 0.  That
  77      is the only information we need, and it is easier to test for if
  78      it is collected in each allocno's lowest-order object.  */
  79   if (w1 == w2 && w1 > 0)
  80     {
  81       obj1 = ALLOCNO_OBJECT (a1, 0);
  82       obj2 = ALLOCNO_OBJECT (a2, 0);
  83     }
  84   id1 = OBJECT_CONFLICT_ID (obj1);
  85   id2 = OBJECT_CONFLICT_ID (obj2);
  86
  87   SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1),
  88                       OBJECT_MAX (obj1));
  89   SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2),
  90                       OBJECT_MAX (obj2));
  91 }
  92
  93 /* Build allocno conflict table by processing allocno live ranges.
  94    Return true if the table was built.  The table is not built if it
  95    is too big.  */
  96 static bool
  97 build_conflict_bit_table (void)
  98 {
  99   int i;
 100   unsigned int j;
 101   enum reg_class cover_class;
 102   int object_set_words, allocated_words_num, conflict_bit_vec_words_num;
 103   live_range_t r;
 104   ira_allocno_t allocno;
 105   ira_allocno_iterator ai;
 106   sparseset objects_live;
 107   ira_object_t obj;
 108   ira_allocno_object_iterator aoi;
 109
 110   allocated_words_num = 0;
 111   FOR_EACH_ALLOCNO (allocno, ai)
 112     FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
 113       {
 114         if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 115           continue;
 116         conflict_bit_vec_words_num
 117           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 118              / IRA_INT_BITS);
 119         allocated_words_num += conflict_bit_vec_words_num;
 120         if ((unsigned long long) allocated_words_num * sizeof (IRA_INT_TYPE)
 121             > (unsigned long long) IRA_MAX_CONFLICT_TABLE_SIZE * 1024 * 1024)
 122           {
 123             if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
 124               fprintf
 125                 (ira_dump_file,
 126                  "+++Conflict table will be too big(>%dMB) -- don't use it\n",
 127                  IRA_MAX_CONFLICT_TABLE_SIZE);
 128             return false;
 129           }
 130       }
 131
 132   conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
 133                                               * ira_objects_num);
 134   allocated_words_num = 0;
 135   FOR_EACH_ALLOCNO (allocno, ai)
 136     FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
 137       {
 138         int id = OBJECT_CONFLICT_ID (obj);
 139         if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 140           {
 141             conflicts[id] = NULL;
 142             continue;
 143           }
 144         conflict_bit_vec_words_num
 145           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 146              / IRA_INT_BITS);
 147         allocated_words_num += conflict_bit_vec_words_num;
 148         conflicts[id]
 149           = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
 150                                            * conflict_bit_vec_words_num);
 151         memset (conflicts[id], 0,
 152                 sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
 153       }
 154
 155   object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
 156   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
 157     fprintf
 158       (ira_dump_file,
 159        "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n",
 160        (long) allocated_words_num * sizeof (IRA_INT_TYPE),
 161        (long) object_set_words * ira_objects_num * sizeof (IRA_INT_TYPE));
 162
 163   objects_live = sparseset_alloc (ira_objects_num);
 164   for (i = 0; i < ira_max_point; i++)
 165     {
 166       for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
 167         {
 168           ira_object_t obj = r->object;
 169           ira_allocno_t allocno = OBJECT_ALLOCNO (obj);
 170           int id = OBJECT_CONFLICT_ID (obj);
 171
 172           gcc_assert (id < ira_objects_num);
 173
 174           cover_class = ALLOCNO_COVER_CLASS (allocno);
 175           sparseset_set_bit (objects_live, id);
 176           EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
 177             {
 178               ira_object_t live_obj = ira_object_id_map[j];
 179               ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
 180               enum reg_class live_cover_class = ALLOCNO_COVER_CLASS (live_a);
 181
 182               if (ira_reg_classes_intersect_p[cover_class][live_cover_class]
 183                   /* Don't set up conflict for the allocno with itself.  */
 184                   && live_a != allocno)
 185                 {
 186                   record_object_conflict (obj, live_obj);
 187                 }
 188             }
 189         }
 190
 191       for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
 192         sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
 193     }
 194   sparseset_free (objects_live);
 195   return true;
 196 }
 197 \f
 198 /* Return true iff allocnos A1 and A2 cannot be allocated to the same
 199    register due to conflicts.  */
 200
 201 static bool
 202 allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2)
 203 {
 204   /* Due to the fact that we canonicalize conflicts (see
 205      record_object_conflict), we only need to test for conflicts of
 206      the lowest order words.  */
 207   ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0);
 208   ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0);
 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, cover_class;
 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, 0, FIRST_PSEUDO_REGISTER - 1))
 431     /* Can not be tied.  */
 432     return false;
 433   rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
 434   mode = ALLOCNO_MODE (a);
 435   cover_class = ALLOCNO_COVER_CLASS (a);
 436   if (only_regs_p && insn != NULL_RTX
 437       && reg_class_size[rclass] <= (unsigned) CLASS_MAX_NREGS (rclass, mode))
 438     /* It is already taken into account in ira-costs.c.  */
 439     return false;
 440   index = ira_class_hard_reg_index[cover_class][allocno_preferenced_hard_regno];
 441   if (index < 0)
 442     /* Can not be tied.  It is not in the cover class.  */
 443     return false;
 444   if (HARD_REGISTER_P (reg1))
 445     cost = ira_get_register_move_cost (mode, cover_class, rclass) * freq;
 446   else
 447     cost = ira_get_register_move_cost (mode, rclass, cover_class) * freq;
 448   do
 449     {
 450       ira_allocate_and_set_costs
 451         (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
 452          ALLOCNO_COVER_CLASS_COST (a));
 453       ira_allocate_and_set_costs
 454         (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class, 0);
 455       ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
 456       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
 457       if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_COVER_CLASS_COST (a))
 458         ALLOCNO_COVER_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
 459       a = ira_parent_or_cap_allocno (a);
 460     }
 461   while (a != NULL);
 462   return true;
 463 }
 464
 465 /* Process all of the output registers of the current insn which are
 466    not bound (BOUND_P) and the input register REG (its operand number
 467    OP_NUM) which dies in the insn as if there were a move insn between
 468    them with frequency FREQ.  */
 469 static void
 470 process_reg_shuffles (rtx reg, int op_num, int freq, bool *bound_p)
 471 {
 472   int i;
 473   rtx another_reg;
 474
 475   gcc_assert (REG_SUBREG_P (reg));
 476   for (i = 0; i < recog_data.n_operands; i++)
 477     {
 478       another_reg = recog_data.operand[i];
 479
 480       if (!REG_SUBREG_P (another_reg) || op_num == i
 481           || recog_data.operand_type[i] != OP_OUT
 482           || bound_p[i])
 483         continue;
 484
 485       process_regs_for_copy (reg, another_reg, false, NULL_RTX, freq);
 486     }
 487 }
 488
 489 /* Process INSN and create allocno copies if necessary.  For example,
 490    it might be because INSN is a pseudo-register move or INSN is two
 491    operand insn.  */
 492 static void
 493 add_insn_allocno_copies (rtx insn)
 494 {
 495   rtx set, operand, dup;
 496   const char *str;
 497   bool commut_p, bound_p[MAX_RECOG_OPERANDS];
 498   int i, j, n, freq;
 499
 500   freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
 501   if (freq == 0)
 502     freq = 1;
 503   if ((set = single_set (insn)) != NULL_RTX
 504       && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
 505       && ! side_effects_p (set)
 506       && find_reg_note (insn, REG_DEAD,
 507                         REG_P (SET_SRC (set))
 508                         ? SET_SRC (set)
 509                         : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
 510     {
 511       process_regs_for_copy (SET_DEST (set), SET_SRC (set), false, insn, freq);
 512       return;
 513     }
 514   /* Fast check of possibility of constraint or shuffle copies.  If
 515      there are no dead registers, there will be no such copies.  */
 516   if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
 517     return;
 518   extract_insn (insn);
 519   for (i = 0; i < recog_data.n_operands; i++)
 520     bound_p[i] = false;
 521   for (i = 0; i < recog_data.n_operands; i++)
 522     {
 523       operand = recog_data.operand[i];
 524       if (! REG_SUBREG_P (operand))
 525         continue;
 526       str = recog_data.constraints[i];
 527       while (*str == ' ' || *str == '\t')
 528         str++;
 529       for (j = 0, commut_p = false; j < 2; j++, commut_p = true)
 530         if ((n = get_dup_num (i, commut_p)) >= 0)
 531           {
 532             bound_p[n] = true;
 533             dup = recog_data.operand[n];
 534             if (REG_SUBREG_P (dup)
 535                 && find_reg_note (insn, REG_DEAD,
 536                                   REG_P (operand)
 537                                   ? operand
 538                                   : SUBREG_REG (operand)) != NULL_RTX)
 539               process_regs_for_copy (operand, dup, true, NULL_RTX, freq);
 540           }
 541     }
 542   for (i = 0; i < recog_data.n_operands; i++)
 543     {
 544       operand = recog_data.operand[i];
 545       if (REG_SUBREG_P (operand)
 546           && find_reg_note (insn, REG_DEAD,
 547                             REG_P (operand)
 548                             ? operand : SUBREG_REG (operand)) != NULL_RTX)
 549         /* If an operand dies, prefer its hard register for the output
 550            operands by decreasing the hard register cost or creating
 551            the corresponding allocno copies.  The cost will not
 552            correspond to a real move insn cost, so make the frequency
 553            smaller.  */
 554         process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8, bound_p);
 555     }
 556 }
 557
 558 /* Add copies originated from BB given by LOOP_TREE_NODE.  */
 559 static void
 560 add_copies (ira_loop_tree_node_t loop_tree_node)
 561 {
 562   basic_block bb;
 563   rtx insn;
 564
 565   bb = loop_tree_node->bb;
 566   if (bb == NULL)
 567     return;
 568   FOR_BB_INSNS (bb, insn)
 569     if (NONDEBUG_INSN_P (insn))
 570       add_insn_allocno_copies (insn);
 571 }
 572
 573 /* Propagate copies the corresponding allocnos on upper loop tree
 574    level.  */
 575 static void
 576 propagate_copies (void)
 577 {
 578   ira_copy_t cp;
 579   ira_copy_iterator ci;
 580   ira_allocno_t a1, a2, parent_a1, parent_a2;
 581
 582   FOR_EACH_COPY (cp, ci)
 583     {
 584       a1 = cp->first;
 585       a2 = cp->second;
 586       if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
 587         continue;
 588       ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
 589       parent_a1 = ira_parent_or_cap_allocno (a1);
 590       parent_a2 = ira_parent_or_cap_allocno (a2);
 591       ira_assert (parent_a1 != NULL && parent_a2 != NULL);
 592       if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2))
 593         ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
 594                               cp->constraint_p, cp->insn, cp->loop_tree_node);
 595     }
 596 }
 597
 598 /* Array used to collect all conflict allocnos for given allocno.  */
 599 static ira_object_t *collected_conflict_objects;
 600
 601 /* Build conflict vectors or bit conflict vectors (whatever is more
 602    profitable) for object OBJ from the conflict table.  */
 603 static void
 604 build_object_conflicts (ira_object_t obj)
 605 {
 606   int i, px, parent_num;
 607   ira_allocno_t parent_a, another_parent_a;
 608   ira_object_t parent_obj;
 609   ira_allocno_t a = OBJECT_ALLOCNO (obj);
 610   IRA_INT_TYPE *object_conflicts;
 611   minmax_set_iterator asi;
 612
 613   object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
 614   px = 0;
 615   FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
 616                               OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
 617     {
 618       ira_object_t another_obj = ira_object_id_map[i];
 619       ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
 620       ira_assert (ira_reg_classes_intersect_p
 621                   [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
 622       collected_conflict_objects[px++] = another_obj;
 623     }
 624   if (ira_conflict_vector_profitable_p (obj, px))
 625     {
 626       ira_object_t *vec;
 627       ira_allocate_conflict_vec (obj, px);
 628       vec = OBJECT_CONFLICT_VEC (obj);
 629       memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px);
 630       vec[px] = NULL;
 631       OBJECT_NUM_CONFLICTS (obj) = px;
 632     }
 633   else
 634     {
 635       int conflict_bit_vec_words_num;
 636       OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
 637       if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
 638         conflict_bit_vec_words_num = 0;
 639       else
 640         conflict_bit_vec_words_num
 641           = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 642              / IRA_INT_BITS);
 643       OBJECT_CONFLICT_ARRAY_SIZE (obj)
 644         = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
 645     }
 646
 647   parent_a = ira_parent_or_cap_allocno (a);
 648   if (parent_a == NULL)
 649     return;
 650   ira_assert (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (parent_a));
 651   ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
 652   parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
 653   parent_num = OBJECT_CONFLICT_ID (parent_obj);
 654   FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
 655                               OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
 656     {
 657       ira_object_t another_obj = ira_object_id_map[i];
 658       ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
 659       int another_word = OBJECT_SUBWORD (another_obj);
 660
 661       ira_assert (ira_reg_classes_intersect_p
 662                   [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
 663
 664       another_parent_a = ira_parent_or_cap_allocno (another_a);
 665       if (another_parent_a == NULL)
 666         continue;
 667       ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
 668       ira_assert (ALLOCNO_COVER_CLASS (another_a)
 669                   == ALLOCNO_COVER_CLASS (another_parent_a));
 670       ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
 671                   == ALLOCNO_NUM_OBJECTS (another_parent_a));
 672       SET_MINMAX_SET_BIT (conflicts[parent_num],
 673                           OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
 674                                                      another_word)),
 675                           OBJECT_MIN (parent_obj),
 676                           OBJECT_MAX (parent_obj));
 677     }
 678 }
 679
 680 /* Build conflict vectors or bit conflict vectors (whatever is more
 681    profitable) of all allocnos from the conflict table.  */
 682 static void
 683 build_conflicts (void)
 684 {
 685   int i;
 686   ira_allocno_t a, cap;
 687
 688   collected_conflict_objects
 689     = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
 690                                           * ira_objects_num);
 691   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
 692     for (a = ira_regno_allocno_map[i];
 693          a != NULL;
 694          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 695       {
 696         int j, nregs = ALLOCNO_NUM_OBJECTS (a);
 697         for (j = 0; j < nregs; j++)
 698           {
 699             ira_object_t obj = ALLOCNO_OBJECT (a, j);
 700             build_object_conflicts (obj);
 701             for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
 702               {
 703                 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
 704                 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
 705                 build_object_conflicts (cap_obj);
 706               }
 707           }
 708       }
 709   ira_free (collected_conflict_objects);
 710 }
 711
 712 \f
 713
 714 /* Print hard reg set SET with TITLE to FILE.  */
 715 static void
 716 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
 717 {
 718   int i, start;
 719
 720   fputs (title, file);
 721   for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 722     {
 723       if (TEST_HARD_REG_BIT (set, i))
 724         {
 725           if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
 726             start = i;
 727         }
 728       if (start >= 0
 729           && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
 730         {
 731           if (start == i - 1)
 732             fprintf (file, " %d", start);
 733           else if (start == i - 2)
 734             fprintf (file, " %d %d", start, start + 1);
 735           else
 736             fprintf (file, " %d-%d", start, i - 1);
 737           start = -1;
 738         }
 739     }
 740   putc ('\n', file);
 741 }
 742
 743 static void
 744 print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
 745 {
 746   HARD_REG_SET conflicting_hard_regs;
 747   basic_block bb;
 748   int n, i;
 749
 750   if (reg_p)
 751     fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
 752   else
 753     {
 754       fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 755       if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 756         fprintf (file, "b%d", bb->index);
 757       else
 758         fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 759       putc (')', file);
 760     }
 761
 762   fputs (" conflicts:", file);
 763   n = ALLOCNO_NUM_OBJECTS (a);
 764   for (i = 0; i < n; i++)
 765     {
 766       ira_object_t obj = ALLOCNO_OBJECT (a, i);
 767       ira_object_t conflict_obj;
 768       ira_object_conflict_iterator oci;
 769
 770       if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
 771         continue;
 772       if (n > 1)
 773         fprintf (file, "\n;;   subobject %d:", i);
 774       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
 775         {
 776           ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
 777           if (reg_p)
 778             fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
 779           else
 780             {
 781               fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a),
 782                        ALLOCNO_REGNO (conflict_a));
 783               if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
 784                 fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj));
 785               if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
 786                 fprintf (file, ",b%d", bb->index);
 787               else
 788                 fprintf (file, ",l%d",
 789                          ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop->num);
 790               putc (')', file);
 791             }
 792         }
 793       COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
 794       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 795       AND_HARD_REG_SET (conflicting_hard_regs,
 796                         reg_class_contents[ALLOCNO_COVER_CLASS (a)]);
 797       print_hard_reg_set (file, "\n;;     total conflict hard regs:",
 798                           conflicting_hard_regs);
 799
 800       COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_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_COVER_CLASS (a)]);
 804       print_hard_reg_set (file, ";;     conflict hard regs:",
 805                           conflicting_hard_regs);
 806       putc ('\n', file);
 807     }
 808
 809 }
 810
 811 /* Print information about allocno or only regno (if REG_P) conflicts
 812    to FILE.  */
 813 static void
 814 print_conflicts (FILE *file, bool reg_p)
 815 {
 816   ira_allocno_t a;
 817   ira_allocno_iterator ai;
 818
 819   FOR_EACH_ALLOCNO (a, ai)
 820     print_allocno_conflicts (file, reg_p, a);
 821 }
 822
 823 /* Print information about allocno or only regno (if REG_P) conflicts
 824    to stderr.  */
 825 void
 826 ira_debug_conflicts (bool reg_p)
 827 {
 828   print_conflicts (stderr, reg_p);
 829 }
 830
 831 \f
 832
 833 /* Entry function which builds allocno conflicts and allocno copies
 834    and accumulate some allocno info on upper level regions.  */
 835 void
 836 ira_build_conflicts (void)
 837 {
 838   ira_allocno_t a;
 839   ira_allocno_iterator ai;
 840   HARD_REG_SET temp_hard_reg_set;
 841
 842   if (ira_conflicts_p)
 843     {
 844       ira_conflicts_p = build_conflict_bit_table ();
 845       if (ira_conflicts_p)
 846         {
 847           ira_object_t obj;
 848           ira_object_iterator oi;
 849
 850           build_conflicts ();
 851           ira_traverse_loop_tree (true, ira_loop_tree_root, NULL, add_copies);
 852           /* We need finished conflict table for the subsequent call.  */
 853           if (flag_ira_region == IRA_REGION_ALL
 854               || flag_ira_region == IRA_REGION_MIXED)
 855             propagate_copies ();
 856
 857           /* Now we can free memory for the conflict table (see function
 858              build_object_conflicts for details).  */
 859           FOR_EACH_OBJECT (obj, oi)
 860             {
 861               if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
 862                 ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]);
 863             }
 864           ira_free (conflicts);
 865         }
 866     }
 867   if (! CLASS_LIKELY_SPILLED_P (base_reg_class (VOIDmode, ADDRESS, 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     }
 912   if (optimize && ira_conflicts_p
 913       && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 914     print_conflicts (ira_dump_file, false);
 915 }