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