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