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