gcc/ira-conflicts.c

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