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