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