gcc/ira-conflicts.c

   1 /* IRA conflict builder.
   2    Copyright (C) 2006, 2007, 2008, 2009
   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             if (address_operand (op, VOIDmode))
 252               return -1;
 253             break;
 254
 255           case 'g':
 256             return -1;
 257
 258           case 'r':
 259           case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
 260           case 'h': case 'j': case 'k': case 'l':
 261           case 'q': case 't': case 'u':
 262           case 'v': case 'w': case 'x': case 'y': case 'z':
 263           case 'A': case 'B': case 'C': case 'D':
 264           case 'Q': case 'R': case 'S': case 'T': case 'U':
 265           case 'W': case 'Y': case 'Z':
 266             {
 267               enum reg_class cl;
 268
 269               cl = (c == 'r'
 270                     ? GENERAL_REGS : REG_CLASS_FROM_CONSTRAINT (c, str));
 271               if (cl != NO_REGS)
 272                 return -1;
 273 #ifdef EXTRA_CONSTRAINT_STR
 274               else if (EXTRA_CONSTRAINT_STR (op, c, str))
 275                 return -1;
 276 #endif
 277               break;
 278             }
 279
 280           case '0': case '1': case '2': case '3': case '4':
 281           case '5': case '6': case '7': case '8': case '9':
 282             if (original != -1 && original != c)
 283               return -1;
 284             original = c;
 285             break;
 286           }
 287       str += CONSTRAINT_LEN (c, str);
 288     }
 289   if (original == -1)
 290     return -1;
 291   dup = original - '0';
 292   if (use_commut_op_p)
 293     {
 294       if (commutative_constraint_p (recog_data.constraints[dup]))
 295         dup++;
 296       else if (dup > 0
 297                && commutative_constraint_p (recog_data.constraints[dup -1]))
 298         dup--;
 299       else if (! commut_op_used_p)
 300         return -1;
 301     }
 302   return dup;
 303 }
 304
 305 /* Return the operand which should be, in any case, the same as
 306    operand with number OP_NUM.  If USE_COMMUT_OP_P is TRUE, the
 307    function makes temporarily commutative operand exchange before
 308    this.  */
 309 static rtx
 310 get_dup (int op_num, bool use_commut_op_p)
 311 {
 312   int n = get_dup_num (op_num, use_commut_op_p);
 313
 314   if (n < 0)
 315     return NULL_RTX;
 316   else
 317     return recog_data.operand[n];
 318 }
 319
 320 /* Check that X is REG or SUBREG of REG.  */
 321 #define REG_SUBREG_P(x)                                                 \
 322    (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
 323
 324 /* Return X if X is a REG, otherwise it should be SUBREG of REG and
 325    the function returns the reg in this case.  *OFFSET will be set to
 326    0 in the first case or the regno offset in the first case.  */
 327 static rtx
 328 go_through_subreg (rtx x, int *offset)
 329 {
 330   rtx reg;
 331
 332   *offset = 0;
 333   if (REG_P (x))
 334     return x;
 335   ira_assert (GET_CODE (x) == SUBREG);
 336   reg = SUBREG_REG (x);
 337   ira_assert (REG_P (reg));
 338   if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
 339     *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
 340                                    SUBREG_BYTE (x), GET_MODE (x));
 341   else
 342     *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x)));
 343   return reg;
 344 }
 345
 346 /* Process registers REG1 and REG2 in move INSN with execution
 347    frequency FREQ.  The function also processes the registers in a
 348    potential move insn (INSN == NULL in this case) with frequency
 349    FREQ.  The function can modify hard register costs of the
 350    corresponding allocnos or create a copy involving the corresponding
 351    allocnos.  The function does nothing if the both registers are hard
 352    registers.  When nothing is changed, the function returns
 353    FALSE.  */
 354 static bool
 355 process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p,
 356                        rtx insn, int freq)
 357 {
 358   int allocno_preferenced_hard_regno, cost, index, offset1, offset2;
 359   bool only_regs_p;
 360   ira_allocno_t a;
 361   enum reg_class rclass, cover_class;
 362   enum machine_mode mode;
 363   ira_copy_t cp;
 364   ira_loop_tree_node_t parent;
 365
 366   gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
 367   only_regs_p = REG_P (reg1) && REG_P (reg2);
 368   reg1 = go_through_subreg (reg1, &offset1);
 369   reg2 = go_through_subreg (reg2, &offset2);
 370   /* Set up hard regno preferenced by allocno.  If allocno gets the
 371      hard regno the copy (or potential move) insn will be removed.  */
 372   if (HARD_REGISTER_P (reg1))
 373     {
 374       if (HARD_REGISTER_P (reg2))
 375         return false;
 376       allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
 377       a = ira_curr_regno_allocno_map[REGNO (reg2)];
 378     }
 379   else if (HARD_REGISTER_P (reg2))
 380     {
 381       allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
 382       a = ira_curr_regno_allocno_map[REGNO (reg1)];
 383     }
 384   else if (!CONFLICT_ALLOCNO_P (ira_curr_regno_allocno_map[REGNO (reg1)],
 385                                 ira_curr_regno_allocno_map[REGNO (reg2)])
 386            && offset1 == offset2)
 387     {
 388       cp = ira_add_allocno_copy (ira_curr_regno_allocno_map[REGNO (reg1)],
 389                                  ira_curr_regno_allocno_map[REGNO (reg2)],
 390                                  freq, constraint_p, insn,
 391                                  ira_curr_loop_tree_node);
 392       bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
 393       return true;
 394     }
 395   else
 396     return false;
 397   if (! IN_RANGE (allocno_preferenced_hard_regno, 0, FIRST_PSEUDO_REGISTER - 1))
 398     /* Can not be tied.  */
 399     return false;
 400   rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
 401   mode = ALLOCNO_MODE (a);
 402   cover_class = ALLOCNO_COVER_CLASS (a);
 403   if (only_regs_p && insn != NULL_RTX
 404       && reg_class_size[rclass] <= (unsigned) CLASS_MAX_NREGS (rclass, mode))
 405     /* It is already taken into account in ira-costs.c.  */
 406     return false;
 407   index = ira_class_hard_reg_index[cover_class][allocno_preferenced_hard_regno];
 408   if (index < 0)
 409     /* Can not be tied.  It is not in the cover class.  */
 410     return false;
 411   if (HARD_REGISTER_P (reg1))
 412     cost = ira_get_register_move_cost (mode, cover_class, rclass) * freq;
 413   else
 414     cost = ira_get_register_move_cost (mode, rclass, cover_class) * freq;
 415   for (;;)
 416     {
 417       ira_allocate_and_set_costs
 418         (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
 419          ALLOCNO_COVER_CLASS_COST (a));
 420       ira_allocate_and_set_costs
 421         (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class, 0);
 422       ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
 423       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
 424       if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_COVER_CLASS_COST (a))
 425         ALLOCNO_COVER_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
 426       if (ALLOCNO_CAP (a) != NULL)
 427         a = ALLOCNO_CAP (a);
 428       else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
 429                || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
 430         break;
 431     }
 432   return true;
 433 }
 434
 435 /* Process all of the output registers of the current insn and
 436    the input register REG (its operand number OP_NUM) which dies in the
 437    insn as if there were a move insn between them with frequency
 438    FREQ.  */
 439 static void
 440 process_reg_shuffles (rtx reg, int op_num, int freq)
 441 {
 442   int i;
 443   rtx another_reg;
 444
 445   gcc_assert (REG_SUBREG_P (reg));
 446   for (i = 0; i < recog_data.n_operands; i++)
 447     {
 448       another_reg = recog_data.operand[i];
 449
 450       if (!REG_SUBREG_P (another_reg) || op_num == i
 451           || recog_data.operand_type[i] != OP_OUT)
 452         continue;
 453
 454       process_regs_for_copy (reg, another_reg, false, NULL_RTX, freq);
 455     }
 456 }
 457
 458 /* Process INSN and create allocno copies if necessary.  For example,
 459    it might be because INSN is a pseudo-register move or INSN is two
 460    operand insn.  */
 461 static void
 462 add_insn_allocno_copies (rtx insn)
 463 {
 464   rtx set, operand, dup;
 465   const char *str;
 466   bool commut_p, bound_p;
 467   int i, j, freq;
 468
 469   freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
 470   if (freq == 0)
 471     freq = 1;
 472   if ((set = single_set (insn)) != NULL_RTX
 473       && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
 474       && ! side_effects_p (set)
 475       && find_reg_note (insn, REG_DEAD,
 476                         REG_P (SET_SRC (set))
 477                         ? SET_SRC (set)
 478                         : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
 479     process_regs_for_copy (SET_DEST (set), SET_SRC (set), false, insn, freq);
 480   else
 481     {
 482       extract_insn (insn);
 483       for (i = 0; i < recog_data.n_operands; i++)
 484         {
 485           operand = recog_data.operand[i];
 486           if (REG_SUBREG_P (operand)
 487               && find_reg_note (insn, REG_DEAD,
 488                                 REG_P (operand)
 489                                 ? operand : SUBREG_REG (operand)) != NULL_RTX)
 490             {
 491               str = recog_data.constraints[i];
 492               while (*str == ' ' || *str == '\t')
 493                 str++;
 494               bound_p = false;
 495               for (j = 0, commut_p = false; j < 2; j++, commut_p = true)
 496                 if ((dup = get_dup (i, commut_p)) != NULL_RTX
 497                     && REG_SUBREG_P (dup)
 498                     && process_regs_for_copy (operand, dup, true,
 499                                               NULL_RTX, freq))
 500                   bound_p = true;
 501               if (bound_p)
 502                 continue;
 503               /* If an operand dies, prefer its hard register for the
 504                  output operands by decreasing the hard register cost
 505                  or creating the corresponding allocno copies.  The
 506                  cost will not correspond to a real move insn cost, so
 507                  make the frequency smaller.  */
 508               process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8);
 509             }
 510         }
 511     }
 512 }
 513
 514 /* Add copies originated from BB given by LOOP_TREE_NODE.  */
 515 static void
 516 add_copies (ira_loop_tree_node_t loop_tree_node)
 517 {
 518   basic_block bb;
 519   rtx insn;
 520
 521   bb = loop_tree_node->bb;
 522   if (bb == NULL)
 523     return;
 524   FOR_BB_INSNS (bb, insn)
 525     if (INSN_P (insn))
 526       add_insn_allocno_copies (insn);
 527 }
 528
 529 /* Propagate copies the corresponding allocnos on upper loop tree
 530    level.  */
 531 static void
 532 propagate_copies (void)
 533 {
 534   ira_copy_t cp;
 535   ira_copy_iterator ci;
 536   ira_allocno_t a1, a2, parent_a1, parent_a2;
 537   ira_loop_tree_node_t parent;
 538
 539   FOR_EACH_COPY (cp, ci)
 540     {
 541       a1 = cp->first;
 542       a2 = cp->second;
 543       if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
 544         continue;
 545       ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
 546       parent = ALLOCNO_LOOP_TREE_NODE (a1)->parent;
 547       if ((parent_a1 = ALLOCNO_CAP (a1)) == NULL)
 548         parent_a1 = parent->regno_allocno_map[ALLOCNO_REGNO (a1)];
 549       if ((parent_a2 = ALLOCNO_CAP (a2)) == NULL)
 550         parent_a2 = parent->regno_allocno_map[ALLOCNO_REGNO (a2)];
 551       ira_assert (parent_a1 != NULL && parent_a2 != NULL);
 552       if (! CONFLICT_ALLOCNO_P (parent_a1, parent_a2))
 553         ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
 554                               cp->constraint_p, cp->insn, cp->loop_tree_node);
 555     }
 556 }
 557
 558 /* Array used to collect all conflict allocnos for given allocno.  */
 559 static ira_allocno_t *collected_conflict_allocnos;
 560
 561 /* Build conflict vectors or bit conflict vectors (whatever is more
 562    profitable) for allocno A from the conflict table and propagate the
 563    conflicts to upper level allocno.  */
 564 static void
 565 build_allocno_conflicts (ira_allocno_t a)
 566 {
 567   int i, px, parent_num;
 568   int conflict_bit_vec_words_num;
 569   ira_loop_tree_node_t parent;
 570   ira_allocno_t parent_a, another_a, another_parent_a;
 571   ira_allocno_t *vec;
 572   IRA_INT_TYPE *allocno_conflicts;
 573   ira_allocno_set_iterator asi;
 574
 575   allocno_conflicts = conflicts[ALLOCNO_NUM (a)];
 576   px = 0;
 577   FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
 578                            ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
 579     {
 580       another_a = ira_conflict_id_allocno_map[i];
 581       ira_assert (ira_reg_classes_intersect_p
 582                   [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
 583       collected_conflict_allocnos[px++] = another_a;
 584     }
 585   if (ira_conflict_vector_profitable_p (a, px))
 586     {
 587       ira_allocate_allocno_conflict_vec (a, px);
 588       vec = (ira_allocno_t*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
 589       memcpy (vec, collected_conflict_allocnos, sizeof (ira_allocno_t) * px);
 590       vec[px] = NULL;
 591       ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = px;
 592     }
 593   else
 594     {
 595       ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = conflicts[ALLOCNO_NUM (a)];
 596       if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
 597         conflict_bit_vec_words_num = 0;
 598       else
 599         conflict_bit_vec_words_num
 600           = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
 601              / IRA_INT_BITS);
 602       ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a)
 603         = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
 604     }
 605   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
 606   if ((parent_a = ALLOCNO_CAP (a)) == NULL
 607       && (parent == NULL
 608           || (parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
 609           == NULL))
 610     return;
 611   ira_assert (parent != NULL);
 612   ira_assert (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (parent_a));
 613   parent_num = ALLOCNO_NUM (parent_a);
 614   FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
 615                            ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
 616     {
 617       another_a = ira_conflict_id_allocno_map[i];
 618       ira_assert (ira_reg_classes_intersect_p
 619                   [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
 620       if ((another_parent_a = ALLOCNO_CAP (another_a)) == NULL
 621           && (another_parent_a = (parent->regno_allocno_map
 622                                   [ALLOCNO_REGNO (another_a)])) == NULL)
 623         continue;
 624       ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
 625       ira_assert (ALLOCNO_COVER_CLASS (another_a)
 626                   == ALLOCNO_COVER_CLASS (another_parent_a));
 627       SET_ALLOCNO_SET_BIT (conflicts[parent_num],
 628                            ALLOCNO_CONFLICT_ID (another_parent_a),
 629                            ALLOCNO_MIN (parent_a),
 630                            ALLOCNO_MAX (parent_a));
 631     }
 632 }
 633
 634 /* Build conflict vectors or bit conflict vectors (whatever is more
 635    profitable) of all allocnos from the conflict table.  */
 636 static void
 637 build_conflicts (void)
 638 {
 639   int i;
 640   ira_allocno_t a, cap;
 641
 642   collected_conflict_allocnos
 643     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
 644                                       * ira_allocnos_num);
 645   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
 646     for (a = ira_regno_allocno_map[i];
 647          a != NULL;
 648          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 649       {
 650         build_allocno_conflicts (a);
 651         for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
 652           build_allocno_conflicts (cap);
 653       }
 654   ira_free (collected_conflict_allocnos);
 655 }
 656
 657 \f
 658
 659 /* Print hard reg set SET with TITLE to FILE.  */
 660 static void
 661 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
 662 {
 663   int i, start;
 664
 665   fprintf (file, title);
 666   for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 667     {
 668       if (TEST_HARD_REG_BIT (set, i))
 669         {
 670           if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
 671             start = i;
 672         }
 673       if (start >= 0
 674           && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
 675         {
 676           if (start == i - 1)
 677             fprintf (file, " %d", start);
 678           else if (start == i - 2)
 679             fprintf (file, " %d %d", start, start + 1);
 680           else
 681             fprintf (file, " %d-%d", start, i - 1);
 682           start = -1;
 683         }
 684     }
 685   fprintf (file, "\n");
 686 }
 687
 688 /* Print information about allocno or only regno (if REG_P) conflicts
 689    to FILE.  */
 690 static void
 691 print_conflicts (FILE *file, bool reg_p)
 692 {
 693   ira_allocno_t a;
 694   ira_allocno_iterator ai;
 695   HARD_REG_SET conflicting_hard_regs;
 696
 697   FOR_EACH_ALLOCNO (a, ai)
 698     {
 699       ira_allocno_t conflict_a;
 700       ira_allocno_conflict_iterator aci;
 701       basic_block bb;
 702
 703       if (reg_p)
 704         fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
 705       else
 706         {
 707           fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 708           if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 709             fprintf (file, "b%d", bb->index);
 710           else
 711             fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 712           fprintf (file, ")");
 713         }
 714       fprintf (file, " conflicts:");
 715       if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
 716         FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
 717           {
 718             if (reg_p)
 719               fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
 720             else
 721               {
 722                 fprintf (file, " a%d(r%d,", ALLOCNO_NUM (conflict_a),
 723                          ALLOCNO_REGNO (conflict_a));
 724                 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
 725                   fprintf (file, "b%d)", bb->index);
 726                 else
 727                   fprintf (file, "l%d)",
 728                            ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop->num);
 729               }
 730           }
 731       COPY_HARD_REG_SET (conflicting_hard_regs,
 732                          ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 733       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 734       AND_HARD_REG_SET (conflicting_hard_regs,
 735                         reg_class_contents[ALLOCNO_COVER_CLASS (a)]);
 736       print_hard_reg_set (file, "\n;;     total conflict hard regs:",
 737                           conflicting_hard_regs);
 738       COPY_HARD_REG_SET (conflicting_hard_regs,
 739                          ALLOCNO_CONFLICT_HARD_REGS (a));
 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, ";;     conflict hard regs:",
 744                           conflicting_hard_regs);
 745     }
 746   fprintf (file, "\n");
 747 }
 748
 749 /* Print information about allocno or only regno (if REG_P) conflicts
 750    to stderr.  */
 751 void
 752 ira_debug_conflicts (bool reg_p)
 753 {
 754   print_conflicts (stderr, reg_p);
 755 }
 756
 757 \f
 758
 759 /* Entry function which builds allocno conflicts and allocno copies
 760    and accumulate some allocno info on upper level regions.  */
 761 void
 762 ira_build_conflicts (void)
 763 {
 764   ira_allocno_t a;
 765   ira_allocno_iterator ai;
 766   HARD_REG_SET temp_hard_reg_set;
 767
 768   if (ira_conflicts_p)
 769     {
 770       ira_conflicts_p = build_conflict_bit_table ();
 771       if (ira_conflicts_p)
 772         {
 773           build_conflicts ();
 774           ira_traverse_loop_tree (true, ira_loop_tree_root, NULL, add_copies);
 775           /* We need finished conflict table for the subsequent call.  */
 776           if (flag_ira_region == IRA_REGION_ALL
 777               || flag_ira_region == IRA_REGION_MIXED)
 778             propagate_copies ();
 779           /* Now we can free memory for the conflict table (see function
 780              build_allocno_conflicts for details).  */
 781           FOR_EACH_ALLOCNO (a, ai)
 782             {
 783               if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a)
 784                   != conflicts[ALLOCNO_NUM (a)])
 785                 ira_free (conflicts[ALLOCNO_NUM (a)]);
 786             }
 787           ira_free (conflicts);
 788         }
 789     }
 790   if (! CLASS_LIKELY_SPILLED_P (base_reg_class (VOIDmode, ADDRESS, SCRATCH)))
 791     CLEAR_HARD_REG_SET (temp_hard_reg_set);
 792   else
 793     {
 794       COPY_HARD_REG_SET (temp_hard_reg_set,
 795                          reg_class_contents[base_reg_class (VOIDmode, ADDRESS, SCRATCH)]);
 796       AND_COMPL_HARD_REG_SET (temp_hard_reg_set, ira_no_alloc_regs);
 797       AND_HARD_REG_SET (temp_hard_reg_set, call_used_reg_set);
 798     }
 799   FOR_EACH_ALLOCNO (a, ai)
 800     {
 801       reg_attrs *attrs;
 802       tree decl;
 803
 804       if ((! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 805           /* For debugging purposes don't put user defined variables in
 806              callee-clobbered registers.  */
 807           || (optimize == 0
 808               && (attrs = REG_ATTRS (regno_reg_rtx [ALLOCNO_REGNO (a)])) != NULL
 809               && (decl = attrs->decl) != NULL
 810               && VAR_OR_FUNCTION_DECL_P (decl)
 811               && ! DECL_ARTIFICIAL (decl)))
 812         {
 813           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 814                             call_used_reg_set);
 815           IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 816                             call_used_reg_set);
 817         }
 818       else if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 819         {
 820           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 821                             no_caller_save_reg_set);
 822           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 823                             temp_hard_reg_set);
 824           IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 825                             no_caller_save_reg_set);
 826           IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 827                             temp_hard_reg_set);
 828         }
 829     }
 830   if (optimize && ira_conflicts_p
 831       && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 832     print_conflicts (ira_dump_file, false);
 833 }