gcc/ira-conflicts.c

   1 /* IRA conflict builder.
   2    Copyright (C) 2006, 2007
   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 2, 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 COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "regs.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "target.h"
  31 #include "flags.h"
  32 #include "hard-reg-set.h"
  33 #include "basic-block.h"
  34 #include "insn-config.h"
  35 #include "recog.h"
  36 #include "toplev.h"
  37 #include "params.h"
  38 #include "df.h"
  39 #include "ira-int.h"
  40
  41 /* The file contains code is analogous to one in global but the code
  42    works on the allocno basis.  */
  43
  44 static void build_conflict_bit_table (void);
  45 static void mirror_conflicts (void);
  46 static int commutative_constraint_p (const char *);
  47 static int get_dup_num (int, int);
  48 static rtx get_dup (int, int);
  49 static void add_insn_allocno_copies (rtx);
  50 static void add_copies (loop_tree_node_t);
  51 static void propagate_allocno_info (allocno_t);
  52 static void propagate_info (void);
  53 static void remove_conflict_allocno_copies (void);
  54 static void build_allocno_conflict_vects (void);
  55 static void propagate_modified_regnos (loop_tree_node_t);
  56 static void print_hard_reg_set (FILE *, const char *, HARD_REG_SET);
  57 static void print_conflicts (FILE *, int);
  58
  59 /* Set, clear or test bit number I in `allocnos_live',
  60    a bit vector indexed by allocno number.  */
  61 #define SET_ALLOCNO_LIVE(I) SET_ALLOCNO_SET_BIT (allocnos_live, I)
  62 #define CLEAR_ALLOCNO_LIVE(I) CLEAR_ALLOCNO_SET_BIT (allocnos_live, I)
  63 #define TEST_ALLOCNO_LIVE(I) TEST_ALLOCNO_SET_BIT (allocnos_live, I)
  64
  65 /* allocnos_num by allocnos_num array of bits, recording whether two
  66    allocno's conflict (can't go in the same hardware register).
  67
  68    `conflicts' is symmetric after the call to mirror_conflicts.  */
  69 static INT_TYPE *conflicts;
  70
  71 /* Two macros to test 1 in an element of `conflicts'.  */
  72 #define CONFLICT_P(I, J)                                                \
  73  (conflicts[(I) * allocno_set_words + (unsigned) (J) / INT_BITS]        \
  74   & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
  75
  76 /* Bit mask for allocnos live at current point in the scan.  */
  77 static INT_TYPE *allocnos_live;
  78
  79 \f
  80
  81 /* The function builds allocno conflict table by processing allocno
  82    live ranges.  */
  83 static void
  84 build_conflict_bit_table (void)
  85 {
  86   int i, j, pn, pn_prod;
  87   allocno_live_range_t r;
  88
  89   allocno_set_words = (allocnos_num + INT_BITS - 1) / INT_BITS;
  90   allocnos_live = ira_allocate (sizeof (INT_TYPE) * allocno_set_words);
  91   memset (allocnos_live, 0, sizeof (INT_TYPE) * allocno_set_words);
  92   conflicts = ira_allocate (sizeof (INT_TYPE)
  93                             * allocnos_num * allocno_set_words);
  94   memset (conflicts, 0, sizeof (INT_TYPE) * allocnos_num * allocno_set_words);
  95   for (i = 0; i < max_point; i++)
  96     {
  97       for (r = start_point_ranges [i]; r != NULL; r = r->start_next)
  98         {
  99           pn = ALLOCNO_NUM (r->allocno);
 100           SET_ALLOCNO_LIVE (pn);
 101           pn_prod = pn * allocno_set_words;
 102           for (j = allocno_set_words - 1; j >= 0; j--)
 103             conflicts [pn_prod + j] |= allocnos_live [j];
 104           /* Don't set up conflict for the allocno with itself.  */
 105           CLEAR_ALLOCNO_SET_BIT (conflicts + pn_prod, pn);
 106         }
 107
 108       for (r = finish_point_ranges [i]; r != NULL; r = r->finish_next)
 109         CLEAR_ALLOCNO_LIVE (ALLOCNO_NUM (r->allocno));
 110     }
 111 }
 112
 113 /* If CONFLICT_P (i, j) is TRUE, make sure CONFLICT_P (j, i) is also TRUE.  */
 114 static void
 115 mirror_conflicts (void)
 116 {
 117   int i, j;
 118   unsigned INT_TYPE mask;
 119   int rw = allocno_set_words;
 120   int rwb = rw * INT_BITS;
 121   INT_TYPE *p = conflicts;
 122   INT_TYPE *q0 = conflicts;
 123   INT_TYPE *q1, *q2;
 124
 125   for (i = allocnos_num - 1, mask = 1; i >= 0; i--, mask <<= 1)
 126     {
 127       if (! mask)
 128         {
 129           mask = 1;
 130           q0++;
 131         }
 132       for (j = allocno_set_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
 133         {
 134           unsigned INT_TYPE word;
 135
 136           for (word = (unsigned INT_TYPE) *p++, q2 = q1;
 137                word;
 138                word >>= 1, q2 += rw)
 139             {
 140               if (word & 1)
 141                 *q2 |= mask;
 142             }
 143         }
 144     }
 145 }
 146
 147 \f
 148
 149 /* The function returns nonzero, if the operand constraint STR is
 150    commutative.  */
 151 static int
 152 commutative_constraint_p (const char *str)
 153 {
 154   int ignore_p;
 155   int c;
 156
 157   for (ignore_p = FALSE;;)
 158     {
 159       c = *str;
 160       if (c == '\0')
 161         break;
 162       str += CONSTRAINT_LEN (c, str);
 163       if (c == '#')
 164         ignore_p = TRUE;
 165       else if (c == ',')
 166         ignore_p = FALSE;
 167       else if (! ignore_p)
 168         {
 169           if (c == '%')
 170             return TRUE;
 171         }
 172     }
 173   return FALSE;
 174 }
 175
 176 /* The function returns number of the operand which should be the same
 177    in any case as operand with number OP_NUM.  If USE_COMMUT_OP_P is
 178    non-zero, the function makes temporarily commutative operand
 179    exchange before this.  The function takes only really possible
 180    alternatives into consideration.  */
 181 static int
 182 get_dup_num (int op_num, int use_commut_op_p)
 183 {
 184   int curr_alt, c, original, dup;
 185   int ignore_p, commut_op_used_p;
 186   const char *str;
 187   rtx op, equiv_const = NULL_RTX;
 188
 189   if (op_num < 0 || recog_data.n_alternatives == 0)
 190     return -1;
 191   op = recog_data.operand [op_num];
 192   ira_assert (REG_P (op));
 193   commut_op_used_p = TRUE;
 194   if (use_commut_op_p)
 195     {
 196       if (commutative_constraint_p (recog_data.constraints [op_num]))
 197         op_num++;
 198       else if (op_num > 0 && commutative_constraint_p (recog_data.constraints
 199                                                        [op_num - 1]))
 200         op_num--;
 201       else
 202         commut_op_used_p = FALSE;
 203     }
 204   str = recog_data.constraints [op_num];
 205   for (ignore_p = FALSE, original = -1, curr_alt = 0;;)
 206     {
 207       c = *str;
 208       if (c == '\0')
 209         break;
 210       if (c == '#')
 211         ignore_p = TRUE;
 212       else if (c == ',')
 213         {
 214           curr_alt++;
 215           ignore_p = FALSE;
 216         }
 217       else if (! ignore_p)
 218         switch (c)
 219           {
 220           case 'X':
 221             return -1;
 222
 223           case 'i':
 224             if (equiv_const != NULL_RTX && CONSTANT_P (equiv_const))
 225               return -1;
 226             break;
 227
 228           case 'n':
 229             if (equiv_const != NULL_RTX
 230                 && (GET_CODE (equiv_const) == CONST_INT
 231                     || (GET_CODE (equiv_const) == CONST_DOUBLE
 232                         && GET_MODE (equiv_const) == VOIDmode)))
 233               return -1;
 234             break;
 235
 236           case 's':
 237             if (equiv_const != NULL_RTX
 238                 && CONSTANT_P (equiv_const)
 239                 && GET_CODE (equiv_const) != CONST_INT
 240                 && (GET_CODE (equiv_const) != CONST_DOUBLE
 241                     || GET_MODE (equiv_const) != VOIDmode))
 242               return -1;
 243             break;
 244
 245           case 'I':
 246           case 'J':
 247           case 'K':
 248           case 'L':
 249           case 'M':
 250           case 'N':
 251           case 'O':
 252           case 'P':
 253             if ((equiv_const != NULL_RTX
 254                  && GET_CODE (equiv_const) == CONST_INT
 255                  && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
 256                                                c, str)))
 257               return -1;
 258             break;
 259
 260           case 'E':
 261           case 'F':
 262             if (equiv_const != NULL_RTX
 263                 && (GET_CODE (equiv_const) == CONST_DOUBLE
 264                     || (GET_CODE (equiv_const) == CONST_VECTOR
 265                         && (GET_MODE_CLASS (GET_MODE (equiv_const))
 266                             == MODE_VECTOR_FLOAT))))
 267               return -1;
 268             break;
 269
 270           case 'G':
 271           case 'H':
 272             if (equiv_const != NULL_RTX
 273                 && GET_CODE (equiv_const) == CONST_DOUBLE
 274                 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const, c, str))
 275               return -1;
 276             break;
 277
 278           case 'm':
 279           case 'o':
 280             /* Accept a register which might be placed in memory.  */
 281             return -1;
 282             break;
 283
 284           case 'V':
 285           case '<':
 286           case '>':
 287             break;
 288
 289           case 'p':
 290             GO_IF_LEGITIMATE_ADDRESS (VOIDmode, op, win_p);
 291             break;
 292
 293           win_p:
 294             return -1;
 295
 296           case 'g':
 297             return -1;
 298
 299           case 'r':
 300           case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
 301           case 'h': case 'j': case 'k': case 'l':
 302           case 'q': case 't': case 'u':
 303           case 'v': case 'w': case 'x': case 'y': case 'z':
 304           case 'A': case 'B': case 'C': case 'D':
 305           case 'Q': case 'R': case 'S': case 'T': case 'U':
 306           case 'W': case 'Y': case 'Z':
 307             {
 308               enum reg_class cl;
 309
 310               cl = (c == 'r'
 311                     ? GENERAL_REGS : REG_CLASS_FROM_CONSTRAINT (c, str));
 312               if (cl != NO_REGS)
 313                 return -1;
 314 #ifdef EXTRA_CONSTRAINT_STR
 315               else if (EXTRA_CONSTRAINT_STR (op, c, str))
 316                 return -1;
 317 #endif
 318               break;
 319             }
 320
 321           case '0': case '1': case '2': case '3': case '4':
 322           case '5': case '6': case '7': case '8': case '9':
 323             if (original != -1 && original != c)
 324               return -1;
 325             original = c;
 326             break;
 327           }
 328       str += CONSTRAINT_LEN (c, str);
 329     }
 330   if (original == -1)
 331     return -1;
 332   dup = original - '0';
 333   if (use_commut_op_p)
 334     {
 335       if (commutative_constraint_p (recog_data.constraints [dup]))
 336         dup++;
 337       else if (dup > 0
 338                && commutative_constraint_p (recog_data.constraints [dup -1]))
 339         dup--;
 340       else if (! commut_op_used_p)
 341         return -1;
 342     }
 343   return dup;
 344 }
 345
 346 /* The function returns operand which should be in any case the same
 347    as operand with number OP_NUM.  If USE_COMMUT_OP_P is non-zero, the
 348    function makes temporarily commutative operand exchange before
 349    this.  */
 350 static rtx
 351 get_dup (int op_num, int use_commut_op_p)
 352 {
 353   int n = get_dup_num (op_num, use_commut_op_p);
 354
 355   if (n < 0)
 356     return NULL_RTX;
 357   else
 358     return recog_data.operand [n];
 359 }
 360
 361 /* The function processes INSN and create allocno copies if
 362    necessary.  For example, it might be because INSN is a
 363    pseudo-register move or INSN is two operand insn.  */
 364 static void
 365 add_insn_allocno_copies (rtx insn)
 366 {
 367   rtx set, operand, dup;
 368   const char *str;
 369   int commut_p, bound_p;
 370   int i, j, freq, hard_regno, cost, index;
 371   copy_t cp;
 372   allocno_t a;
 373   enum reg_class class, cover_class;
 374   enum machine_mode mode;
 375
 376   freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
 377   if (freq == 0)
 378     freq = 1;
 379   if ((set = single_set (insn)) != NULL_RTX
 380       && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
 381       && ! side_effects_p (set)
 382       && find_reg_note (insn, REG_DEAD, SET_SRC (set)) != NULL_RTX
 383       && find_reg_note (insn, REG_RETVAL, NULL_RTX) == NULL_RTX)
 384     {
 385       if (HARD_REGISTER_P (SET_SRC (set)) || HARD_REGISTER_P (SET_DEST (set)))
 386         {
 387           if (HARD_REGISTER_P (SET_DEST (set)))
 388             {
 389               if (HARD_REGISTER_P (SET_SRC (set)))
 390                 return;
 391               hard_regno = REGNO (SET_DEST (set));
 392               a = ira_curr_regno_allocno_map [REGNO (SET_SRC (set))];
 393             }
 394           else
 395             {
 396               hard_regno = REGNO (SET_SRC (set));
 397               a = ira_curr_regno_allocno_map [REGNO (SET_DEST (set))];
 398             }
 399           class = REGNO_REG_CLASS (hard_regno);
 400           mode = ALLOCNO_MODE (a);
 401           cover_class = ALLOCNO_COVER_CLASS (a);
 402           if (! class_subset_p [class] [cover_class])
 403             return;
 404           if (reg_class_size [class]
 405               <= (unsigned) CLASS_MAX_NREGS (class, mode))
 406             /* It is already taken into account in ira-costs.c.  */
 407             return;
 408           index = class_hard_reg_index [cover_class] [hard_regno];
 409           if (index < 0)
 410             return;
 411           if (HARD_REGISTER_P (SET_DEST (set)))
 412             cost = register_move_cost [mode] [cover_class] [class] * freq;
 413           else
 414             cost = register_move_cost [mode] [class] [cover_class] * freq;
 415           ALLOCNO_HARD_REG_COSTS (a) [index] -= cost;
 416           ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [index] -= cost;
 417         }
 418       else
 419         {
 420           cp = add_allocno_copy
 421                (ira_curr_regno_allocno_map [REGNO (SET_DEST (set))],
 422                 ira_curr_regno_allocno_map [REGNO (SET_SRC (set))],
 423                 freq, insn, ira_curr_loop_tree_node);
 424           bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
 425         }
 426     }
 427   else
 428     {
 429       extract_insn (insn);
 430       for (i = 0; i < recog_data.n_operands; i++)
 431         {
 432           operand = recog_data.operand [i];
 433           if (REG_P (operand)
 434               && find_reg_note (insn, REG_DEAD, operand) != NULL_RTX)
 435             {
 436               str = recog_data.constraints [i];
 437               while (*str == ' ' && *str == '\t')
 438                 str++;
 439               bound_p = FALSE;
 440               for (j = 0, commut_p = FALSE; j < 2; j++, commut_p = TRUE)
 441                 if ((dup = get_dup (i, commut_p)) != NULL_RTX
 442                     && REG_P (dup) && GET_MODE (operand) == GET_MODE (dup))
 443                   {
 444                     if (HARD_REGISTER_NUM_P (REGNO (operand))
 445                         || HARD_REGISTER_NUM_P (REGNO (dup)))
 446                       {
 447                         if (HARD_REGISTER_P (operand))
 448                           {
 449                             if (HARD_REGISTER_P (dup))
 450                               continue;
 451                             hard_regno = REGNO (operand);
 452                             a = ira_curr_regno_allocno_map [REGNO (dup)];
 453                           }
 454                         else
 455                           {
 456                             hard_regno = REGNO (dup);
 457                             a = ira_curr_regno_allocno_map [REGNO (operand)];
 458                           }
 459                         class = REGNO_REG_CLASS (hard_regno);
 460                         mode = ALLOCNO_MODE (a);
 461                         cover_class = ALLOCNO_COVER_CLASS (a);
 462                         if (! class_subset_p [class] [cover_class])
 463                           continue;
 464                         index
 465                           = class_hard_reg_index [cover_class] [hard_regno];
 466                         if (index < 0)
 467                           continue;
 468                         if (HARD_REGISTER_P (operand))
 469                           cost
 470                             = register_move_cost [mode] [cover_class] [class];
 471                         else
 472                           cost
 473                             = register_move_cost [mode] [class] [cover_class];
 474                         cost *= freq;
 475                         ALLOCNO_HARD_REG_COSTS (a) [index] -= cost;
 476                         ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [index] -= cost;
 477                         bound_p = TRUE;
 478                       }
 479                     else
 480                       {
 481                         bound_p = TRUE;
 482                         cp = add_allocno_copy
 483                              (ira_curr_regno_allocno_map [REGNO (dup)],
 484                               ira_curr_regno_allocno_map [REGNO (operand)],
 485                               freq, NULL_RTX, ira_curr_loop_tree_node);
 486                         bitmap_set_bit
 487                           (ira_curr_loop_tree_node->local_copies, cp->num);
 488                       }
 489                   }
 490               if (bound_p)
 491                 continue;
 492               /* If an operand dies, prefer its hard register for the
 493                  output operands by decreasing the hard register cost
 494                  or creating the corresponding allocno copies.  */
 495               for (j = 0; j < recog_data.n_operands; j++)
 496                 {
 497                   dup = recog_data.operand [j];
 498
 499                   if (i == j || recog_data.operand_type [j] != OP_OUT
 500                       || !REG_P (dup))
 501                     continue;
 502
 503                   if (HARD_REGISTER_NUM_P (REGNO (operand))
 504                       || HARD_REGISTER_NUM_P (REGNO (dup)))
 505                     {
 506                         if (HARD_REGISTER_P (operand))
 507                           {
 508                             if (HARD_REGISTER_P (dup))
 509                               continue;
 510                             hard_regno = REGNO (operand);
 511                             a = ira_curr_regno_allocno_map [REGNO (dup)];
 512                           }
 513                         else
 514                           {
 515                             hard_regno = REGNO (dup);
 516                             a = ira_curr_regno_allocno_map [REGNO (operand)];
 517                           }
 518                         class = REGNO_REG_CLASS (hard_regno);
 519                         mode = ALLOCNO_MODE (a);
 520                         cover_class = ALLOCNO_COVER_CLASS (a);
 521                         if (! class_subset_p [class] [cover_class])
 522                           continue;
 523                         index
 524                           = class_hard_reg_index [cover_class] [hard_regno];
 525                         if (index < 0)
 526                           continue;
 527                         if (HARD_REGISTER_P (operand))
 528                           cost
 529                             = register_move_cost [mode] [cover_class] [class];
 530                         else
 531                           cost
 532                             = register_move_cost [mode] [class] [cover_class];
 533                         cost *= (freq < 8 ? 1 : freq / 8);
 534                         ALLOCNO_HARD_REG_COSTS (a) [index] -= cost;
 535                         ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [index] -= cost;
 536                       }
 537                     else
 538                       {
 539                         cp = add_allocno_copy
 540                              (ira_curr_regno_allocno_map [REGNO (dup)],
 541                               ira_curr_regno_allocno_map [REGNO (operand)],
 542                               (freq < 8 ? 1 : freq / 8), NULL_RTX,
 543                               ira_curr_loop_tree_node);
 544                         bitmap_set_bit
 545                           (ira_curr_loop_tree_node->local_copies, cp->num);
 546                       }
 547                 }
 548             }
 549         }
 550     }
 551 }
 552
 553 /* The function adds copies originated from bb given by
 554    LOOP_TREE_NODE.  */
 555 static void
 556 add_copies (loop_tree_node_t loop_tree_node)
 557 {
 558   basic_block bb;
 559   rtx insn;
 560
 561   bb = loop_tree_node->bb;
 562   if (bb == NULL)
 563     return;
 564   FOR_BB_INSNS (bb, insn)
 565     if (INSN_P (insn))
 566       add_insn_allocno_copies (insn);
 567 }
 568
 569 /* The function propagates info about allocno A to the corresponding
 570    allocno on upper loop tree level.  So allocnos on upper levels
 571    accumulate information about the corresponding allocnos in nested
 572    loops.  */
 573 static void
 574 propagate_allocno_info (allocno_t a)
 575 {
 576   int regno;
 577   allocno_t father_a, another_a, another_father_a;
 578   loop_tree_node_t father;
 579   copy_t cp, next_cp;
 580
 581   regno = ALLOCNO_REGNO (a);
 582   if ((father = ALLOCNO_LOOP_TREE_NODE (a)->father) != NULL
 583       && (father_a = father->regno_allocno_map [regno]) != NULL)
 584     {
 585       ALLOCNO_CALL_FREQ (father_a) += ALLOCNO_CALL_FREQ (a);
 586 #ifdef STACK_REGS
 587       if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
 588         ALLOCNO_TOTAL_NO_STACK_REG_P (father_a) = TRUE;
 589 #endif
 590       IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (father_a),
 591                         ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 592       if (ALLOCNO_CALLS_CROSSED_START (father_a) < 0
 593           || (ALLOCNO_CALLS_CROSSED_START (a) >= 0
 594               && (ALLOCNO_CALLS_CROSSED_START (father_a)
 595                   > ALLOCNO_CALLS_CROSSED_START (a))))
 596         ALLOCNO_CALLS_CROSSED_START (father_a)
 597           = ALLOCNO_CALLS_CROSSED_START (a);
 598       ALLOCNO_CALLS_CROSSED_NUM (father_a) += ALLOCNO_CALLS_CROSSED_NUM (a);
 599       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
 600         {
 601           if (cp->first == a)
 602             {
 603               next_cp = cp->next_first_allocno_copy;
 604               another_a = cp->second;
 605             }
 606           else if (cp->second == a)
 607             {
 608               next_cp = cp->next_second_allocno_copy;
 609               another_a = cp->first;
 610             }
 611           else
 612             gcc_unreachable ();
 613           if ((another_father_a = (father->regno_allocno_map
 614                                    [ALLOCNO_REGNO (another_a)])) != NULL)
 615             add_allocno_copy (father_a, another_father_a, cp->freq,
 616                               cp->move_insn, cp->loop_tree_node);
 617         }
 618     }
 619 }
 620
 621 /* The function propagates info about allocnos to the corresponding
 622    allocnos on upper loop tree level.  */
 623 static void
 624 propagate_info (void)
 625 {
 626   int i;
 627   allocno_t a;
 628
 629   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
 630     for (a = regno_allocno_map [i];
 631          a != NULL;
 632          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 633       propagate_allocno_info (a);
 634 }
 635
 636 /* The function returns TRUE if allocnos A1 and A2 conflict.  It
 637    checks intersection of the corresponding live ranges for this.  */
 638 int
 639 allocno_conflict_p (allocno_t a1, allocno_t a2)
 640 {
 641   allocno_live_range_t r1, r2;
 642
 643   if (a1 == a2)
 644     return FALSE;
 645   if (ALLOCNO_REG (a1) != NULL && ALLOCNO_REG (a2) != NULL
 646       && (ORIGINAL_REGNO (ALLOCNO_REG (a1))
 647           == ORIGINAL_REGNO (ALLOCNO_REG (a2))))
 648     return FALSE;
 649   for (r1 = ALLOCNO_LIVE_RANGES (a1), r2 = ALLOCNO_LIVE_RANGES (a2);
 650        r1 != NULL && r2 != NULL;)
 651     {
 652       if ((r2->start <= r1->start && r1->start <= r2->finish)
 653           || (r1->start <= r2->start && r2->start <= r1->finish))
 654         return TRUE;
 655       if (r1->start > r2->finish)
 656         r1 = r1->next;
 657       else
 658         r2 = r2->next;
 659     }
 660   return FALSE;
 661 }
 662
 663 /* The function returns TRUE if pseudo-registers REGNO1 and REGNO2
 664    conflict.  It should be used when there is only one region.  */
 665 int
 666 allocno_reg_conflict_p (int regno1, int regno2)
 667 {
 668   allocno_t a1, a2;
 669
 670   ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
 671               && regno2 >= FIRST_PSEUDO_REGISTER);
 672   /* Reg info caclulated by dataflow infrastructure can be different
 673      from one calculated by regclass.  */
 674   if ((a1 = ira_loop_tree_root->regno_allocno_map [regno1]) == NULL
 675       || (a2 = ira_loop_tree_root->regno_allocno_map [regno2]) == NULL)
 676     return FALSE;
 677   return allocno_conflict_p (a1, a2);
 678 }
 679
 680 /* Remove copies involving conflicting allocnos.  */
 681 static void
 682 remove_conflict_allocno_copies (void)
 683 {
 684   int i;
 685   allocno_t a;
 686   copy_t cp, next_cp;
 687   varray_type conflict_allocno_copy_varray;
 688
 689   VARRAY_GENERIC_PTR_NOGC_INIT (conflict_allocno_copy_varray, get_max_uid (),
 690                                 "copies of conflicting allocnos");
 691   for (i = 0; i < allocnos_num; i++)
 692     {
 693       a = allocnos [i];
 694       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
 695         if (cp->first == a)
 696           next_cp = cp->next_first_allocno_copy;
 697         else
 698           {
 699             next_cp = cp->next_second_allocno_copy;
 700             VARRAY_PUSH_GENERIC_PTR (conflict_allocno_copy_varray, cp);
 701           }
 702     }
 703   for (i = VARRAY_ACTIVE_SIZE (conflict_allocno_copy_varray) - 1; i >= 0; i--)
 704     {
 705       cp = VARRAY_GENERIC_PTR (conflict_allocno_copy_varray, i);
 706       if (CONFLICT_P (ALLOCNO_NUM (cp->first), ALLOCNO_NUM (cp->second)))
 707         remove_allocno_copy_from_list (cp);
 708     }
 709   VARRAY_FREE (conflict_allocno_copy_varray);
 710 }
 711
 712 /* The function builds conflict vectors of all allocnos from the
 713    conflict table.  */
 714 static void
 715 build_allocno_conflict_vects (void)
 716 {
 717   int i, j, level, px, another_father_pn, conflict_allocnos_num;
 718   int *level_init_p;
 719   enum reg_class cover_class;
 720   loop_tree_node_t father;
 721   allocno_t a, father_a, another_a, another_father_a, *conflict_allocnos, *vec;
 722   INT_TYPE *accumulated_conflicts, *allocno_conflicts, *propagate_conflicts;
 723
 724   conflict_allocnos = ira_allocate (sizeof (allocno_t) * allocnos_num);
 725   level_init_p = ira_allocate (ira_loop_tree_height * sizeof (int));
 726   memset (level_init_p, 0, ira_loop_tree_height * sizeof (int));
 727   accumulated_conflicts
 728     = ira_allocate (ira_loop_tree_height
 729                     * allocno_set_words * sizeof (INT_TYPE));
 730   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
 731     for (a = regno_allocno_map [i];
 732          a != NULL;
 733          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 734       {
 735         cover_class = ALLOCNO_COVER_CLASS (a);
 736         level = ALLOCNO_LOOP_TREE_NODE (a)->level;
 737         allocno_conflicts = conflicts + ALLOCNO_NUM (a) * allocno_set_words;
 738         px = 0;
 739         EXECUTE_IF_SET_IN_ALLOCNO_SET (allocno_conflicts, j,
 740           {
 741             another_a = allocnos [j];
 742             if (cover_class == ALLOCNO_COVER_CLASS (another_a))
 743               conflict_allocnos [px++] = another_a;
 744           });
 745         conflict_allocnos_num = px;
 746         if (! level_init_p [level])
 747           propagate_conflicts = allocno_conflicts;
 748         else
 749           {
 750             propagate_conflicts
 751               = accumulated_conflicts + level * allocno_set_words;
 752             EXECUTE_IF_SET_IN_ALLOCNO_SET (propagate_conflicts, j,
 753               {
 754                 another_a = allocnos [j];
 755                 ira_assert (cover_class == ALLOCNO_COVER_CLASS (another_a));
 756                 if (! TEST_ALLOCNO_SET_BIT (allocno_conflicts, j))
 757                   conflict_allocnos [px++] = another_a;
 758               });
 759             for (j = 0; j < allocno_set_words; j++)
 760               propagate_conflicts [j] |= allocno_conflicts [j];
 761           }
 762         allocate_allocno_conflicts (a, px);
 763         vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
 764         memcpy (vec, conflict_allocnos, sizeof (allocno_t) * px);
 765         vec [px] = NULL;
 766         ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = conflict_allocnos_num;
 767         ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a) = px;
 768         level_init_p [level] = FALSE;
 769         if ((father = ALLOCNO_LOOP_TREE_NODE (a)->father) == NULL
 770             || (father_a = father->regno_allocno_map [i]) == NULL)
 771           continue;
 772         level--;
 773         ira_assert (level == ALLOCNO_LOOP_TREE_NODE (father_a)->level
 774                     && cover_class == ALLOCNO_COVER_CLASS (father_a));
 775         if (! level_init_p [level])
 776           {
 777             level_init_p [level] = TRUE;
 778             memset (accumulated_conflicts + level * allocno_set_words, 0,
 779                     allocno_set_words * sizeof (INT_TYPE));
 780           }
 781         EXECUTE_IF_SET_IN_ALLOCNO_SET (propagate_conflicts, j,
 782           {
 783             another_a = allocnos [j];
 784             if ((another_father_a = (father->regno_allocno_map
 785                                      [ALLOCNO_REGNO (another_a)])) == NULL)
 786               continue;
 787             another_father_pn = ALLOCNO_NUM (another_father_a);
 788             if (another_father_pn < 0)
 789               continue;
 790             ira_assert (ALLOCNO_COVER_CLASS (another_a)
 791                         == ALLOCNO_COVER_CLASS (another_father_a));
 792             if (cover_class == ALLOCNO_COVER_CLASS (another_a))
 793               SET_ALLOCNO_SET_BIT
 794                 (accumulated_conflicts + allocno_set_words * level,
 795                  another_father_pn);
 796           });
 797       }
 798   ira_free (accumulated_conflicts);
 799   ira_free (level_init_p);
 800   ira_free (conflict_allocnos);
 801 }
 802
 803 \f
 804
 805 /* The function propagates information about allocnos modified inside
 806    the loops.  */
 807 static void
 808 propagate_modified_regnos (loop_tree_node_t loop_tree_node)
 809 {
 810   if (loop_tree_node->bb != NULL || loop_tree_node == ira_loop_tree_root)
 811     return;
 812   bitmap_ior_into (loop_tree_node->father->modified_regnos,
 813                    loop_tree_node->modified_regnos);
 814 }
 815
 816 \f
 817
 818 /* The function prints hard reg set SET with TITLE to FILE.  */
 819 static void
 820 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
 821 {
 822   int i, start;
 823
 824   fprintf (file, title);
 825   for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 826     {
 827       if (TEST_HARD_REG_BIT (set, i))
 828         {
 829           if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
 830             start = i;
 831         }
 832       if (start >= 0
 833           && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
 834         {
 835           if (start == i - 1)
 836             fprintf (file, " %d", start);
 837           else if (start == i - 2)
 838             fprintf (file, " %d %d", start, start + 1);
 839           else
 840             fprintf (file, " %d-%d", start, i - 1);
 841           start = -1;
 842         }
 843     }
 844   fprintf (file, "\n");
 845 }
 846
 847 /* The function outputs information about allocno or regno (if REG_P)
 848    conflicts to FILE.  */
 849 static void
 850 print_conflicts (FILE *file, int reg_p)
 851 {
 852   int i;
 853
 854   for (i = 0; i < allocnos_num; i++)
 855     {
 856       int j;
 857       allocno_t a, conflict_a, *allocno_vec;
 858       basic_block bb;
 859
 860       a = allocnos [i];
 861       if (reg_p)
 862         fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
 863       else
 864         {
 865           fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 866           if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 867             fprintf (file, "b%d", bb->index);
 868           else
 869             fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 870           fprintf (file, ")");
 871         }
 872       fprintf (file, " conflicts:");
 873       allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
 874       if (allocno_vec != NULL)
 875         for (j = 0; (conflict_a = allocno_vec [j]) != NULL; j++)
 876           {
 877             if (reg_p)
 878               fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
 879             else
 880               {
 881                 fprintf (file, " a%d(r%d,", ALLOCNO_NUM (conflict_a),
 882                          ALLOCNO_REGNO (conflict_a));
 883                 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
 884                   fprintf (file, "b%d)", bb->index);
 885                 else
 886                   fprintf (file, "l%d)",
 887                            ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop->num);
 888               }
 889             if (j + 1 == ALLOCNO_CONFLICT_ALLOCNOS_NUM (a))
 890               fprintf (file, "*");
 891           }
 892       print_hard_reg_set (file, "\n;;     total conflict hard regs:",
 893                           ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 894       print_hard_reg_set (file, ";;     conflict hard regs:",
 895                           ALLOCNO_CONFLICT_HARD_REGS (a));
 896     }
 897   fprintf (file, "\n");
 898 }
 899
 900 /* The function outputs information about allocno or regno (if REG_P)
 901    conflicts to stderr.  */
 902 void
 903 debug_conflicts (int reg_p)
 904 {
 905   print_conflicts (stderr, reg_p);
 906 }
 907
 908 \f
 909
 910 /* Entry function which builds allocno conflicts.  */
 911 void
 912 ira_build_conflicts (void)
 913 {
 914   int i;
 915   allocno_t a;
 916
 917   build_conflict_bit_table ();
 918   mirror_conflicts ();
 919   traverse_loop_tree (FALSE, ira_loop_tree_root, NULL, add_copies);
 920   if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
 921       || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
 922     propagate_info ();
 923   /* We need finished conflict table for the subsequent call.  */
 924   remove_conflict_allocno_copies ();
 925   build_allocno_conflict_vects ();
 926   for (i = 0; i < allocnos_num; i++)
 927     {
 928       a = allocnos [i];
 929       if (ALLOCNO_CALLS_CROSSED_NUM (a) == 0)
 930         continue;
 931       if (! flag_caller_saves)
 932         {
 933           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 934                             call_used_reg_set);
 935           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 936             IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 937                               call_used_reg_set);
 938         }
 939       else
 940         {
 941           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 942                             no_caller_save_reg_set);
 943           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
 944             IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 945                               no_caller_save_reg_set);
 946         }
 947     }
 948   traverse_loop_tree (FALSE, ira_loop_tree_root, NULL,
 949                       propagate_modified_regnos);
 950   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 951     print_conflicts (ira_dump_file, FALSE);
 952 }