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, rtx insn, int freq)
 333 {
 334   int allocno_preferenced_hard_regno, cost, index, offset1, offset2;
 335   bool only_regs_p;
 336   ira_allocno_t a;
 337   enum reg_class rclass, cover_class;
 338   enum machine_mode mode;
 339   ira_copy_t cp;
 340
 341   gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
 342   only_regs_p = REG_P (reg1) && REG_P (reg2);
 343   reg1 = go_through_subreg (reg1, &offset1);
 344   reg2 = go_through_subreg (reg2, &offset2);
 345   /* Set up hard regno preferenced by allocno.  If allocno gets the
 346      hard regno the copy (or potential move) insn will be removed.  */
 347   if (HARD_REGISTER_P (reg1))
 348     {
 349       if (HARD_REGISTER_P (reg2))
 350         return false;
 351       allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
 352       a = ira_curr_regno_allocno_map[REGNO (reg2)];
 353     }
 354   else if (HARD_REGISTER_P (reg2))
 355     {
 356       allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
 357       a = ira_curr_regno_allocno_map[REGNO (reg1)];
 358     }
 359   else if (!CONFLICT_ALLOCNO_P (ira_curr_regno_allocno_map[REGNO (reg1)],
 360                                 ira_curr_regno_allocno_map[REGNO (reg2)])
 361            && offset1 == offset2)
 362     {
 363       cp = ira_add_allocno_copy (ira_curr_regno_allocno_map[REGNO (reg1)],
 364                                  ira_curr_regno_allocno_map[REGNO (reg2)],
 365                                  freq, insn, ira_curr_loop_tree_node);
 366       bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
 367       return true;
 368     }
 369   else
 370     return false;
 371   if (! IN_RANGE (allocno_preferenced_hard_regno, 0, FIRST_PSEUDO_REGISTER - 1))
 372     /* Can not be tied.  */
 373     return false;
 374   rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
 375   mode = ALLOCNO_MODE (a);
 376   cover_class = ALLOCNO_COVER_CLASS (a);
 377   if (! ira_class_subset_p[rclass][cover_class])
 378     return false;
 379   if (only_regs_p && insn != NULL_RTX
 380       && reg_class_size[rclass] <= (unsigned) CLASS_MAX_NREGS (rclass, mode))
 381     /* It is already taken into account in ira-costs.c.  */
 382     return false;
 383   index = ira_class_hard_reg_index[cover_class][allocno_preferenced_hard_regno];
 384   if (index < 0)
 385     /* Can not be tied.  It is not in the cover class.  */
 386     return false;
 387   if (HARD_REGISTER_P (reg1))
 388     cost = ira_register_move_cost[mode][cover_class][rclass] * freq;
 389   else
 390     cost = ira_register_move_cost[mode][rclass][cover_class] * freq;
 391   ira_allocate_and_set_costs
 392     (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
 393      ALLOCNO_COVER_CLASS_COST (a));
 394   ira_allocate_and_set_costs
 395     (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class, 0);
 396   ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
 397   ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
 398   return true;
 399 }
 400
 401 /* Process all of the output registers of the current insn and
 402    the input register REG (its operand number OP_NUM) which dies in the
 403    insn as if there were a move insn between them with frequency
 404    FREQ.  */
 405 static void
 406 process_reg_shuffles (rtx reg, int op_num, int freq)
 407 {
 408   int i;
 409   rtx another_reg;
 410
 411   gcc_assert (REG_SUBREG_P (reg));
 412   for (i = 0; i < recog_data.n_operands; i++)
 413     {
 414       another_reg = recog_data.operand[i];
 415
 416       if (!REG_SUBREG_P (another_reg) || op_num == i
 417           || recog_data.operand_type[i] != OP_OUT)
 418         continue;
 419
 420       process_regs_for_copy (reg, another_reg, NULL_RTX, freq);
 421     }
 422 }
 423
 424 /* Process INSN and create allocno copies if necessary.  For example,
 425    it might be because INSN is a pseudo-register move or INSN is two
 426    operand insn.  */
 427 static void
 428 add_insn_allocno_copies (rtx insn)
 429 {
 430   rtx set, operand, dup;
 431   const char *str;
 432   bool commut_p, bound_p;
 433   int i, j, freq;
 434
 435   freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
 436   if (freq == 0)
 437     freq = 1;
 438   if ((set = single_set (insn)) != NULL_RTX
 439       && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
 440       && ! side_effects_p (set)
 441       && find_reg_note (insn, REG_DEAD,
 442                         REG_P (SET_SRC (set))
 443                         ? SET_SRC (set)
 444                         : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
 445     process_regs_for_copy (SET_DEST (set), SET_SRC (set), insn, freq);
 446   else
 447     {
 448       extract_insn (insn);
 449       for (i = 0; i < recog_data.n_operands; i++)
 450         {
 451           operand = recog_data.operand[i];
 452           if (REG_SUBREG_P (operand)
 453               && find_reg_note (insn, REG_DEAD,
 454                                 REG_P (operand)
 455                                 ? operand : SUBREG_REG (operand)) != NULL_RTX)
 456             {
 457               str = recog_data.constraints[i];
 458               while (*str == ' ' && *str == '\t')
 459                 str++;
 460               bound_p = false;
 461               for (j = 0, commut_p = false; j < 2; j++, commut_p = true)
 462                 if ((dup = get_dup (i, commut_p)) != NULL_RTX
 463                     && REG_SUBREG_P (dup)
 464                     && process_regs_for_copy (operand, dup, NULL_RTX, freq))
 465                   bound_p = true;
 466               if (bound_p)
 467                 continue;
 468               /* If an operand dies, prefer its hard register for the
 469                  output operands by decreasing the hard register cost
 470                  or creating the corresponding allocno copies.  The
 471                  cost will not correspond to a real move insn cost, so
 472                  make the frequency smaller.  */
 473               process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8);
 474             }
 475         }
 476     }
 477 }
 478
 479 /* Add copies originated from BB given by LOOP_TREE_NODE.  */
 480 static void
 481 add_copies (ira_loop_tree_node_t loop_tree_node)
 482 {
 483   basic_block bb;
 484   rtx insn;
 485
 486   bb = loop_tree_node->bb;
 487   if (bb == NULL)
 488     return;
 489   FOR_BB_INSNS (bb, insn)
 490     if (INSN_P (insn))
 491       add_insn_allocno_copies (insn);
 492 }
 493
 494 /* Propagate copies the corresponding allocnos on upper loop tree
 495    level.  */
 496 static void
 497 propagate_copies (void)
 498 {
 499   ira_copy_t cp;
 500   ira_copy_iterator ci;
 501   ira_allocno_t a1, a2, parent_a1, parent_a2;
 502   ira_loop_tree_node_t parent;
 503
 504   FOR_EACH_COPY (cp, ci)
 505     {
 506       a1 = cp->first;
 507       a2 = cp->second;
 508       if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
 509         continue;
 510       ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
 511       parent = ALLOCNO_LOOP_TREE_NODE (a1)->parent;
 512       if ((parent_a1 = ALLOCNO_CAP (a1)) == NULL)
 513         parent_a1 = parent->regno_allocno_map[ALLOCNO_REGNO (a1)];
 514       if ((parent_a2 = ALLOCNO_CAP (a2)) == NULL)
 515         parent_a2 = parent->regno_allocno_map[ALLOCNO_REGNO (a2)];
 516       ira_assert (parent_a1 != NULL && parent_a2 != NULL);
 517       if (! CONFLICT_ALLOCNO_P (parent_a1, parent_a2))
 518         ira_add_allocno_copy (parent_a1, parent_a1, cp->freq,
 519                               cp->insn, cp->loop_tree_node);
 520     }
 521 }
 522
 523 /* Return TRUE if live ranges of allocnos A1 and A2 intersect.  It is
 524    used to find a conflict for new allocnos or allocnos with the
 525    different cover classes.  */
 526 bool
 527 ira_allocno_live_ranges_intersect_p (ira_allocno_t a1, ira_allocno_t a2)
 528 {
 529   allocno_live_range_t r1, r2;
 530
 531   if (a1 == a2)
 532     return false;
 533   if (ALLOCNO_REG (a1) != NULL && ALLOCNO_REG (a2) != NULL
 534       && (ORIGINAL_REGNO (ALLOCNO_REG (a1))
 535           == ORIGINAL_REGNO (ALLOCNO_REG (a2))))
 536     return false;
 537   /* Remember the ranges are always kept ordered.  */
 538   for (r1 = ALLOCNO_LIVE_RANGES (a1), r2 = ALLOCNO_LIVE_RANGES (a2);
 539        r1 != NULL && r2 != NULL;)
 540     {
 541       if (r1->start > r2->finish)
 542         r1 = r1->next;
 543       else if (r2->start > r1->finish)
 544         r2 = r2->next;
 545       else
 546         return true;
 547     }
 548   return false;
 549 }
 550
 551 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
 552    intersect.  This should be used when there is only one region.
 553    Currently this is used during reload.  */
 554 bool
 555 ira_pseudo_live_ranges_intersect_p (int regno1, int regno2)
 556 {
 557   ira_allocno_t a1, a2;
 558
 559   ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
 560               && regno2 >= FIRST_PSEUDO_REGISTER);
 561   /* Reg info caclulated by dataflow infrastructure can be different
 562      from one calculated by regclass.  */
 563   if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
 564       || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
 565     return false;
 566   return ira_allocno_live_ranges_intersect_p (a1, a2);
 567 }
 568
 569 /* Array used to collect all conflict allocnos for given allocno.  */
 570 static ira_allocno_t *collected_conflict_allocnos;
 571
 572 /* Build conflict vectors or bit conflict vectors (whatever is more
 573    profitable) for allocno A from the conflict table and propagate the
 574    conflicts to upper level allocno.  */
 575 static void
 576 build_allocno_conflicts (ira_allocno_t a)
 577 {
 578   int i, px, parent_num;
 579   int conflict_bit_vec_words_num;
 580   ira_loop_tree_node_t parent;
 581   ira_allocno_t parent_a, another_a, another_parent_a;
 582   ira_allocno_t *vec;
 583   IRA_INT_TYPE *allocno_conflicts;
 584   ira_allocno_set_iterator asi;
 585
 586   allocno_conflicts = conflicts[ALLOCNO_NUM (a)];
 587   px = 0;
 588   FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
 589                            ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
 590     {
 591       another_a = ira_conflict_id_allocno_map[i];
 592       ira_assert (ALLOCNO_COVER_CLASS (a)
 593                   == ALLOCNO_COVER_CLASS (another_a));
 594       collected_conflict_allocnos[px++] = another_a;
 595     }
 596   if (ira_conflict_vector_profitable_p (a, px))
 597     {
 598       ira_allocate_allocno_conflict_vec (a, px);
 599       vec = (ira_allocno_t*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
 600       memcpy (vec, collected_conflict_allocnos, sizeof (ira_allocno_t) * px);
 601       vec[px] = NULL;
 602       ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = px;
 603     }
 604   else
 605     {
 606       ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = conflicts[ALLOCNO_NUM (a)];
 607       if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
 608         conflict_bit_vec_words_num = 0;
 609       else
 610         conflict_bit_vec_words_num
 611           = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
 612              / IRA_INT_BITS);
 613       ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a)
 614         = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
 615     }
 616   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
 617   if ((parent_a = ALLOCNO_CAP (a)) == NULL
 618       && (parent == NULL
 619           || (parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
 620           == NULL))
 621     return;
 622   ira_assert (parent != NULL);
 623   ira_assert (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (parent_a));
 624   parent_num = ALLOCNO_NUM (parent_a);
 625   FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
 626                            ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
 627     {
 628       another_a = ira_conflict_id_allocno_map[i];
 629       ira_assert (ALLOCNO_COVER_CLASS (a)
 630                   == ALLOCNO_COVER_CLASS (another_a));
 631       if ((another_parent_a = ALLOCNO_CAP (another_a)) == NULL
 632           && (another_parent_a = (parent->regno_allocno_map
 633                                   [ALLOCNO_REGNO (another_a)])) == NULL)
 634         continue;
 635       ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
 636       ira_assert (ALLOCNO_COVER_CLASS (another_a)
 637                   == ALLOCNO_COVER_CLASS (another_parent_a));
 638       SET_ALLOCNO_SET_BIT (conflicts[parent_num],
 639                            ALLOCNO_CONFLICT_ID (another_parent_a),
 640                            ALLOCNO_MIN (parent_a),
 641                            ALLOCNO_MAX (parent_a));
 642     }
 643 }
 644
 645 /* Build conflict vectors or bit conflict vectors (whatever is more
 646    profitable) of all allocnos from the conflict table.  */
 647 static void
 648 build_conflicts (void)
 649 {
 650   int i;
 651   ira_allocno_t a, cap;
 652
 653   collected_conflict_allocnos
 654     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
 655                                       * ira_allocnos_num);
 656   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
 657     for (a = ira_regno_allocno_map[i];
 658          a != NULL;
 659          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 660       {
 661         build_allocno_conflicts (a);
 662         for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
 663           build_allocno_conflicts (cap);
 664       }
 665   ira_free (collected_conflict_allocnos);
 666 }
 667
 668 \f
 669
 670 /* Print hard reg set SET with TITLE to FILE.  */
 671 static void
 672 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
 673 {
 674   int i, start;
 675
 676   fprintf (file, title);
 677   for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 678     {
 679       if (TEST_HARD_REG_BIT (set, i))
 680         {
 681           if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
 682             start = i;
 683         }
 684       if (start >= 0
 685           && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
 686         {
 687           if (start == i - 1)
 688             fprintf (file, " %d", start);
 689           else if (start == i - 2)
 690             fprintf (file, " %d %d", start, start + 1);
 691           else
 692             fprintf (file, " %d-%d", start, i - 1);
 693           start = -1;
 694         }
 695     }
 696   fprintf (file, "\n");
 697 }
 698
 699 /* Print information about allocno or only regno (if REG_P) conflicts
 700    to FILE.  */
 701 static void
 702 print_conflicts (FILE *file, bool reg_p)
 703 {
 704   ira_allocno_t a;
 705   ira_allocno_iterator ai;
 706   HARD_REG_SET conflicting_hard_regs;
 707
 708   FOR_EACH_ALLOCNO (a, ai)
 709     {
 710       ira_allocno_t conflict_a;
 711       ira_allocno_conflict_iterator aci;
 712       basic_block bb;
 713
 714       if (reg_p)
 715         fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
 716       else
 717         {
 718           fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 719           if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 720             fprintf (file, "b%d", bb->index);
 721           else
 722             fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 723           fprintf (file, ")");
 724         }
 725       fprintf (file, " conflicts:");
 726       if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
 727         FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
 728           {
 729             if (reg_p)
 730               fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
 731             else
 732               {
 733                 fprintf (file, " a%d(r%d,", ALLOCNO_NUM (conflict_a),
 734                          ALLOCNO_REGNO (conflict_a));
 735                 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
 736                   fprintf (file, "b%d)", bb->index);
 737                 else
 738                   fprintf (file, "l%d)",
 739                            ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop->num);
 740               }
 741           }
 742       COPY_HARD_REG_SET (conflicting_hard_regs,
 743                          ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 744       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 745       AND_HARD_REG_SET (conflicting_hard_regs,
 746                         reg_class_contents[ALLOCNO_COVER_CLASS (a)]);
 747       print_hard_reg_set (file, "\n;;     total conflict hard regs:",
 748                           conflicting_hard_regs);
 749       COPY_HARD_REG_SET (conflicting_hard_regs,
 750                          ALLOCNO_CONFLICT_HARD_REGS (a));
 751       AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
 752       AND_HARD_REG_SET (conflicting_hard_regs,
 753                         reg_class_contents[ALLOCNO_COVER_CLASS (a)]);
 754       print_hard_reg_set (file, ";;     conflict hard regs:",
 755                           conflicting_hard_regs);
 756     }
 757   fprintf (file, "\n");
 758 }
 759
 760 /* Print information about allocno or only regno (if REG_P) conflicts
 761    to stderr.  */
 762 void
 763 ira_debug_conflicts (bool reg_p)
 764 {
 765   print_conflicts (stderr, reg_p);
 766 }
 767
 768 \f
 769
 770 /* Entry function which builds allocno conflicts and allocno copies
 771    and accumulate some allocno info on upper level regions.  */
 772 void
 773 ira_build_conflicts (void)
 774 {
 775   ira_allocno_t a;
 776   ira_allocno_iterator ai;
 777
 778   if (optimize)
 779     {
 780       build_conflict_bit_table ();
 781       build_conflicts ();
 782       ira_traverse_loop_tree (true, ira_loop_tree_root, NULL, add_copies);
 783       /* We need finished conflict table for the subsequent call.  */
 784       if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
 785           || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
 786         propagate_copies ();
 787       /* Now we can free memory for the conflict table (see function
 788          build_allocno_conflicts for details).  */
 789       FOR_EACH_ALLOCNO (a, ai)
 790         {
 791           if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != conflicts[ALLOCNO_NUM (a)])
 792             ira_free (conflicts[ALLOCNO_NUM (a)]);
 793         }
 794       ira_free (conflicts);
 795     }
 796   FOR_EACH_ALLOCNO (a, ai)
 797     {
 798       if (ALLOCNO_CALLS_CROSSED_NUM (a) == 0)
 799         continue;
 800       if (! flag_caller_saves)
 801         {
 802           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 803                             call_used_reg_set);
 804           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 805             IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 806                               call_used_reg_set);
 807         }
 808       else
 809         {
 810           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 811                             no_caller_save_reg_set);
 812           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 813             IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 814                               no_caller_save_reg_set);
 815         }
 816     }
 817   if (optimize && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 818     print_conflicts (ira_dump_file, false);
 819 }