gcc/ira-costs.c

   1 /* IRA hard register and memory cost calculation for allocnos or pseudos.
   2    Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
   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 "hard-reg-set.h"
  27 #include "rtl.h"
  28 #include "expr.h"
  29 #include "tm_p.h"
  30 #include "flags.h"
  31 #include "basic-block.h"
  32 #include "regs.h"
  33 #include "addresses.h"
  34 #include "insn-config.h"
  35 #include "recog.h"
  36 #include "reload.h"
  37 #include "diagnostic-core.h"
  38 #include "target.h"
  39 #include "params.h"
  40 #include "ira-int.h"
  41
  42 /* The flags is set up every time when we calculate pseudo register
  43    classes through function ira_set_pseudo_classes.  */
  44 static bool pseudo_classes_defined_p = false;
  45
  46 /* TRUE if we work with allocnos.  Otherwise we work with pseudos.  */
  47 static bool allocno_p;
  48
  49 /* Number of elements in arrays `in_inc_dec' and `costs'.  */
  50 static int cost_elements_num;
  51
  52 #ifdef FORBIDDEN_INC_DEC_CLASSES
  53 /* Indexed by n, is TRUE if allocno or pseudo with number N is used in
  54    an auto-inc or auto-dec context.  */
  55 static bool *in_inc_dec;
  56 #endif
  57
  58 /* The `costs' struct records the cost of using hard registers of each
  59    class considered for the calculation and of using memory for each
  60    allocno or pseudo.  */
  61 struct costs
  62 {
  63   int mem_cost;
  64   /* Costs for register classes start here.  We process only some
  65      allocno classes.  */
  66   int cost[1];
  67 };
  68
  69 #define max_struct_costs_size \
  70   (this_target_ira_int->x_max_struct_costs_size)
  71 #define init_cost \
  72   (this_target_ira_int->x_init_cost)
  73 #define temp_costs \
  74   (this_target_ira_int->x_temp_costs)
  75 #define op_costs \
  76   (this_target_ira_int->x_op_costs)
  77 #define this_op_costs \
  78   (this_target_ira_int->x_this_op_costs)
  79
  80 /* Costs of each class for each allocno or pseudo.  */
  81 static struct costs *costs;
  82
  83 /* Accumulated costs of each class for each allocno.  */
  84 static struct costs *total_allocno_costs;
  85
  86 /* It is the current size of struct costs.  */
  87 static int struct_costs_size;
  88
  89 /* Return pointer to structure containing costs of allocno or pseudo
  90    with given NUM in array ARR.  */
  91 #define COSTS(arr, num) \
  92   ((struct costs *) ((char *) (arr) + (num) * struct_costs_size))
  93
  94 /* Return index in COSTS when processing reg with REGNO.  */
  95 #define COST_INDEX(regno) (allocno_p                                         \
  96                            ? ALLOCNO_NUM (ira_curr_regno_allocno_map[regno]) \
  97                            : (int) regno)
  98
  99 /* Record register class preferences of each allocno or pseudo.  Null
 100    value means no preferences.  It happens on the 1st iteration of the
 101    cost calculation.  */
 102 static enum reg_class *pref;
 103
 104 /* Allocated buffers for pref.  */
 105 static enum reg_class *pref_buffer;
 106
 107 /* Record allocno class of each allocno with the same regno.  */
 108 static enum reg_class *regno_aclass;
 109
 110 /* Record cost gains for not allocating a register with an invariant
 111    equivalence.  */
 112 static int *regno_equiv_gains;
 113
 114 /* Execution frequency of the current insn.  */
 115 static int frequency;
 116
 117 \f
 118
 119 /* Info about reg classes whose costs are calculated for a pseudo.  */
 120 struct cost_classes
 121 {
 122   /* Number of the cost classes in the subsequent array.  */
 123   int num;
 124   /* Container of the cost classes.  */
 125   enum reg_class classes[N_REG_CLASSES];
 126   /* Map reg class -> index of the reg class in the previous array.
 127      -1 if it is not a cost classe.  */
 128   int index[N_REG_CLASSES];
 129   /* Map hard regno index of first class in array CLASSES containing
 130      the hard regno, -1 otherwise.  */
 131   int hard_regno_index[FIRST_PSEUDO_REGISTER];
 132 };
 133
 134 /* Types of pointers to the structure above.  */
 135 typedef struct cost_classes *cost_classes_t;
 136 typedef const struct cost_classes *const_cost_classes_t;
 137
 138 /* Info about cost classes for each pseudo.  */
 139 static cost_classes_t *regno_cost_classes;
 140
 141 /* Returns hash value for cost classes info V.  */
 142 static hashval_t
 143 cost_classes_hash (const void *v)
 144 {
 145   const_cost_classes_t hv = (const_cost_classes_t) v;
 146
 147   return iterative_hash (&hv->classes, sizeof (enum reg_class) * hv->num, 0);
 148 }
 149
 150 /* Compares cost classes info V1 and V2.  */
 151 static int
 152 cost_classes_eq (const void *v1, const void *v2)
 153 {
 154   const_cost_classes_t hv1 = (const_cost_classes_t) v1;
 155   const_cost_classes_t hv2 = (const_cost_classes_t) v2;
 156
 157   return hv1->num == hv2->num && memcmp (hv1->classes, hv2->classes,
 158                                          sizeof (enum reg_class) * hv1->num);
 159 }
 160
 161 /* Delete cost classes info V from the hash table.  */
 162 static void
 163 cost_classes_del (void *v)
 164 {
 165   ira_free (v);
 166 }
 167
 168 /* Hash table of unique cost classes.  */
 169 static htab_t cost_classes_htab;
 170
 171 /* Map allocno class -> cost classes for pseudo of given allocno
 172    class.  */
 173 static cost_classes_t cost_classes_aclass_cache[N_REG_CLASSES];
 174
 175 /* Map mode -> cost classes for pseudo of give mode.  */
 176 static cost_classes_t cost_classes_mode_cache[MAX_MACHINE_MODE];
 177
 178 /* Initialize info about the cost classes for each pseudo.  */
 179 static void
 180 initiate_regno_cost_classes (void)
 181 {
 182   int size = sizeof (cost_classes_t) * max_reg_num ();
 183
 184   regno_cost_classes = (cost_classes_t *) ira_allocate (size);
 185   memset (regno_cost_classes, 0, size);
 186   memset (cost_classes_aclass_cache, 0,
 187           sizeof (cost_classes_t) * N_REG_CLASSES);
 188   memset (cost_classes_mode_cache, 0,
 189           sizeof (cost_classes_t) * MAX_MACHINE_MODE);
 190   cost_classes_htab
 191     = htab_create (200, cost_classes_hash, cost_classes_eq, cost_classes_del);
 192 }
 193
 194 /* Create new cost classes from cost classes FROM and set up members
 195    index and hard_regno_index.  Return the new classes.  The function
 196    implements some common code of two functions
 197    setup_regno_cost_classes_by_aclass and
 198    setup_regno_cost_classes_by_mode.  */
 199 static cost_classes_t
 200 setup_cost_classes (cost_classes_t from)
 201 {
 202   cost_classes_t classes_ptr;
 203   enum reg_class cl;
 204   int i, j, hard_regno;
 205
 206   classes_ptr = (cost_classes_t) ira_allocate (sizeof (struct cost_classes));
 207   classes_ptr->num = from->num;
 208   for (i = 0; i < N_REG_CLASSES; i++)
 209     classes_ptr->index[i] = -1;
 210   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 211     classes_ptr->hard_regno_index[i] = -1;
 212   for (i = 0; i < from->num; i++)
 213     {
 214       cl = classes_ptr->classes[i] = from->classes[i];
 215       classes_ptr->index[cl] = i;
 216       for (j = ira_class_hard_regs_num[cl] - 1; j >= 0; j--)
 217         {
 218           hard_regno = ira_class_hard_regs[cl][j];
 219           if (classes_ptr->hard_regno_index[hard_regno] < 0)
 220             classes_ptr->hard_regno_index[hard_regno] = i;
 221         }
 222     }
 223   return classes_ptr;
 224 }
 225
 226 /* Setup cost classes for pseudo REGNO whose allocno class is ACLASS.
 227    This function is used when we know an initial approximation of
 228    allocno class of the pseudo already, e.g. on the second iteration
 229    of class cost calculation or after class cost calculation in
 230    register-pressure sensitive insn scheduling or register-pressure
 231    sensitive loop-invariant motion.  */
 232 static void
 233 setup_regno_cost_classes_by_aclass (int regno, enum reg_class aclass)
 234 {
 235   static struct cost_classes classes;
 236   cost_classes_t classes_ptr;
 237   enum reg_class cl;
 238   int i;
 239   PTR *slot;
 240   HARD_REG_SET temp, temp2;
 241
 242   if ((classes_ptr = cost_classes_aclass_cache[aclass]) == NULL)
 243     {
 244       COPY_HARD_REG_SET (temp, reg_class_contents[aclass]);
 245       AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
 246       classes.num = 0;
 247       for (i = 0; i < ira_important_classes_num; i++)
 248         {
 249           cl = ira_important_classes[i];
 250           COPY_HARD_REG_SET (temp2, reg_class_contents[cl]);
 251           AND_COMPL_HARD_REG_SET (temp2, ira_no_alloc_regs);
 252           if (! ira_reg_pressure_class_p[cl]
 253               && hard_reg_set_subset_p (temp2, temp) && cl != aclass)
 254             continue;
 255           classes.classes[classes.num++] = cl;
 256         }
 257       slot = htab_find_slot (cost_classes_htab, &classes, INSERT);
 258       if (*slot == NULL)
 259         {
 260           classes_ptr = setup_cost_classes (&classes);
 261           *slot = classes_ptr;
 262         }
 263       classes_ptr = cost_classes_aclass_cache[aclass] = (cost_classes_t) *slot;
 264     }
 265   regno_cost_classes[regno] = classes_ptr;
 266 }
 267
 268 /* Setup cost classes for pseudo REGNO with MODE.  Usage of MODE can
 269    decrease number of cost classes for the pseudo, if hard registers
 270    of some important classes can not hold a value of MODE.  So the
 271    pseudo can not get hard register of some important classes and cost
 272    calculation for such important classes is only waisting CPU
 273    time.  */
 274 static void
 275 setup_regno_cost_classes_by_mode (int regno, enum machine_mode mode)
 276 {
 277   static struct cost_classes classes;
 278   cost_classes_t classes_ptr;
 279   enum reg_class cl;
 280   int i;
 281   PTR *slot;
 282   HARD_REG_SET temp;
 283
 284   if ((classes_ptr = cost_classes_mode_cache[mode]) == NULL)
 285     {
 286       classes.num = 0;
 287       for (i = 0; i < ira_important_classes_num; i++)
 288         {
 289           cl = ira_important_classes[i];
 290           COPY_HARD_REG_SET (temp, ira_prohibited_class_mode_regs[cl][mode]);
 291           IOR_HARD_REG_SET (temp, ira_no_alloc_regs);
 292           if (hard_reg_set_subset_p (reg_class_contents[cl], temp))
 293             continue;
 294           classes.classes[classes.num++] = cl;
 295         }
 296       slot = htab_find_slot (cost_classes_htab, &classes, INSERT);
 297       if (*slot == NULL)
 298         {
 299           classes_ptr = setup_cost_classes (&classes);
 300           *slot = classes_ptr;
 301         }
 302       cost_classes_mode_cache[mode] = (cost_classes_t) *slot;
 303     }
 304   regno_cost_classes[regno] = classes_ptr;
 305 }
 306
 307 /* Finilize info about the cost classes for each pseudo.  */
 308 static void
 309 finish_regno_cost_classes (void)
 310 {
 311   ira_free (regno_cost_classes);
 312   htab_delete (cost_classes_htab);
 313 }
 314
 315 \f
 316
 317 /* Compute the cost of loading X into (if TO_P is TRUE) or from (if
 318    TO_P is FALSE) a register of class RCLASS in mode MODE.  X must not
 319    be a pseudo register.  */
 320 static int
 321 copy_cost (rtx x, enum machine_mode mode, reg_class_t rclass, bool to_p,
 322            secondary_reload_info *prev_sri)
 323 {
 324   secondary_reload_info sri;
 325   reg_class_t secondary_class = NO_REGS;
 326
 327   /* If X is a SCRATCH, there is actually nothing to move since we are
 328      assuming optimal allocation.  */
 329   if (GET_CODE (x) == SCRATCH)
 330     return 0;
 331
 332   /* Get the class we will actually use for a reload.  */
 333   rclass = targetm.preferred_reload_class (x, rclass);
 334
 335   /* If we need a secondary reload for an intermediate, the cost is
 336      that to load the input into the intermediate register, then to
 337      copy it.  */
 338   sri.prev_sri = prev_sri;
 339   sri.extra_cost = 0;
 340   secondary_class = targetm.secondary_reload (to_p, x, rclass, mode, &sri);
 341
 342   if (secondary_class != NO_REGS)
 343     {
 344       if (!move_cost[mode])
 345         init_move_cost (mode);
 346       return (move_cost[mode][(int) secondary_class][(int) rclass]
 347               + sri.extra_cost
 348               + copy_cost (x, mode, secondary_class, to_p, &sri));
 349     }
 350
 351   /* For memory, use the memory move cost, for (hard) registers, use
 352      the cost to move between the register classes, and use 2 for
 353      everything else (constants).  */
 354   if (MEM_P (x) || rclass == NO_REGS)
 355     return sri.extra_cost
 356            + ira_memory_move_cost[mode][(int) rclass][to_p != 0];
 357   else if (REG_P (x))
 358     {
 359       if (!move_cost[mode])
 360         init_move_cost (mode);
 361       return (sri.extra_cost
 362               + move_cost[mode][REGNO_REG_CLASS (REGNO (x))][(int) rclass]);
 363     }
 364   else
 365     /* If this is a constant, we may eventually want to call rtx_cost
 366        here.  */
 367     return sri.extra_cost + COSTS_N_INSNS (1);
 368 }
 369
 370 \f
 371
 372 /* Record the cost of using memory or hard registers of various
 373    classes for the operands in INSN.
 374
 375    N_ALTS is the number of alternatives.
 376    N_OPS is the number of operands.
 377    OPS is an array of the operands.
 378    MODES are the modes of the operands, in case any are VOIDmode.
 379    CONSTRAINTS are the constraints to use for the operands.  This array
 380    is modified by this procedure.
 381
 382    This procedure works alternative by alternative.  For each
 383    alternative we assume that we will be able to allocate all allocnos
 384    to their ideal register class and calculate the cost of using that
 385    alternative.  Then we compute, for each operand that is a
 386    pseudo-register, the cost of having the allocno allocated to each
 387    register class and using it in that alternative.  To this cost is
 388    added the cost of the alternative.
 389
 390    The cost of each class for this insn is its lowest cost among all
 391    the alternatives.  */
 392 static void
 393 record_reg_classes (int n_alts, int n_ops, rtx *ops,
 394                     enum machine_mode *modes, const char **constraints,
 395                     rtx insn, enum reg_class *pref)
 396 {
 397   int alt;
 398   int i, j, k;
 399   rtx set;
 400   int insn_allows_mem[MAX_RECOG_OPERANDS];
 401
 402   for (i = 0; i < n_ops; i++)
 403     insn_allows_mem[i] = 0;
 404
 405   /* Process each alternative, each time minimizing an operand's cost
 406      with the cost for each operand in that alternative.  */
 407   for (alt = 0; alt < n_alts; alt++)
 408     {
 409       enum reg_class classes[MAX_RECOG_OPERANDS];
 410       int allows_mem[MAX_RECOG_OPERANDS];
 411       enum reg_class rclass;
 412       int alt_fail = 0;
 413       int alt_cost = 0, op_cost_add;
 414
 415       if (!recog_data.alternative_enabled_p[alt])
 416         {
 417           for (i = 0; i < recog_data.n_operands; i++)
 418             constraints[i] = skip_alternative (constraints[i]);
 419
 420           continue;
 421         }
 422
 423       for (i = 0; i < n_ops; i++)
 424         {
 425           unsigned char c;
 426           const char *p = constraints[i];
 427           rtx op = ops[i];
 428           enum machine_mode mode = modes[i];
 429           int allows_addr = 0;
 430           int win = 0;
 431
 432           /* Initially show we know nothing about the register class.  */
 433           classes[i] = NO_REGS;
 434           allows_mem[i] = 0;
 435
 436           /* If this operand has no constraints at all, we can
 437              conclude nothing about it since anything is valid.  */
 438           if (*p == 0)
 439             {
 440               if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
 441                 memset (this_op_costs[i], 0, struct_costs_size);
 442               continue;
 443             }
 444
 445           /* If this alternative is only relevant when this operand
 446              matches a previous operand, we do different things
 447              depending on whether this operand is a allocno-reg or not.
 448              We must process any modifiers for the operand before we
 449              can make this test.  */
 450           while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
 451             p++;
 452
 453           if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
 454             {
 455               /* Copy class and whether memory is allowed from the
 456                  matching alternative.  Then perform any needed cost
 457                  computations and/or adjustments.  */
 458               j = p[0] - '0';
 459               classes[i] = classes[j];
 460               allows_mem[i] = allows_mem[j];
 461               if (allows_mem[i])
 462                 insn_allows_mem[i] = 1;
 463
 464               if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
 465                 {
 466                   /* If this matches the other operand, we have no
 467                      added cost and we win.  */
 468                   if (rtx_equal_p (ops[j], op))
 469                     win = 1;
 470                   /* If we can put the other operand into a register,
 471                      add to the cost of this alternative the cost to
 472                      copy this operand to the register used for the
 473                      other operand.  */
 474                   else if (classes[j] != NO_REGS)
 475                     {
 476                       alt_cost += copy_cost (op, mode, classes[j], 1, NULL);
 477                       win = 1;
 478                     }
 479                 }
 480               else if (! REG_P (ops[j])
 481                        || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
 482                 {
 483                   /* This op is an allocno but the one it matches is
 484                      not.  */
 485
 486                   /* If we can't put the other operand into a
 487                      register, this alternative can't be used.  */
 488
 489                   if (classes[j] == NO_REGS)
 490                     alt_fail = 1;
 491                   /* Otherwise, add to the cost of this alternative
 492                      the cost to copy the other operand to the hard
 493                      register used for this operand.  */
 494                   else
 495                     alt_cost += copy_cost (ops[j], mode, classes[j], 1, NULL);
 496                 }
 497               else
 498                 {
 499                   /* The costs of this operand are not the same as the
 500                      other operand since move costs are not symmetric.
 501                      Moreover, if we cannot tie them, this alternative
 502                      needs to do a copy, which is one insn.  */
 503                   struct costs *pp = this_op_costs[i];
 504                   int *pp_costs = pp->cost;
 505                   cost_classes_t cost_classes_ptr
 506                     = regno_cost_classes[REGNO (op)];
 507                   enum reg_class *cost_classes = cost_classes_ptr->classes;
 508                   bool in_p = recog_data.operand_type[i] != OP_OUT;
 509                   bool out_p = recog_data.operand_type[i] != OP_IN;
 510                   enum reg_class op_class = classes[i];
 511                   move_table *move_in_cost, *move_out_cost;
 512
 513                   ira_init_register_move_cost_if_necessary (mode);
 514                   if (! in_p)
 515                     {
 516                       ira_assert (out_p);
 517                       move_out_cost = ira_may_move_out_cost[mode];
 518                       for (k = cost_classes_ptr->num - 1; k >= 0; k--)
 519                         {
 520                           rclass = cost_classes[k];
 521                           pp_costs[k]
 522                             = move_out_cost[op_class][rclass] * frequency;
 523                         }
 524                     }
 525                   else if (! out_p)
 526                     {
 527                       ira_assert (in_p);
 528                       move_in_cost = ira_may_move_in_cost[mode];
 529                       for (k = cost_classes_ptr->num - 1; k >= 0; k--)
 530                         {
 531                           rclass = cost_classes[k];
 532                           pp_costs[k]
 533                             = move_in_cost[rclass][op_class] * frequency;
 534                         }
 535                     }
 536                   else
 537                     {
 538                       move_in_cost = ira_may_move_in_cost[mode];
 539                       move_out_cost = ira_may_move_out_cost[mode];
 540                       for (k = cost_classes_ptr->num - 1; k >= 0; k--)
 541                         {
 542                           rclass = cost_classes[k];
 543                           pp_costs[k] = ((move_in_cost[rclass][op_class]
 544                                           + move_out_cost[op_class][rclass])
 545                                          * frequency);
 546                         }
 547                     }
 548
 549                   /* If the alternative actually allows memory, make
 550                      things a bit cheaper since we won't need an extra
 551                      insn to load it.  */
 552                   pp->mem_cost
 553                     = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
 554                        + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
 555                        - allows_mem[i]) * frequency;
 556
 557                   /* If we have assigned a class to this allocno in
 558                      our first pass, add a cost to this alternative
 559                      corresponding to what we would add if this
 560                      allocno were not in the appropriate class.  */
 561                   if (pref)
 562                     {
 563                       enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
 564
 565                       if (pref_class == NO_REGS)
 566                         alt_cost
 567                           += ((out_p
 568                                ? ira_memory_move_cost[mode][op_class][0] : 0)
 569                               + (in_p
 570                                  ? ira_memory_move_cost[mode][op_class][1]
 571                                  : 0));
 572                       else if (ira_reg_class_intersect
 573                                [pref_class][op_class] == NO_REGS)
 574                         alt_cost
 575                           += ira_register_move_cost[mode][pref_class][op_class];
 576                     }
 577                   if (REGNO (ops[i]) != REGNO (ops[j])
 578                       && ! find_reg_note (insn, REG_DEAD, op))
 579                     alt_cost += 2;
 580
 581                   /* This is in place of ordinary cost computation for
 582                      this operand, so skip to the end of the
 583                      alternative (should be just one character).  */
 584                   while (*p && *p++ != ',')
 585                     ;
 586
 587                   constraints[i] = p;
 588                   continue;
 589                 }
 590             }
 591
 592           /* Scan all the constraint letters.  See if the operand
 593              matches any of the constraints.  Collect the valid
 594              register classes and see if this operand accepts
 595              memory.  */
 596           while ((c = *p))
 597             {
 598               switch (c)
 599                 {
 600                 case ',':
 601                   break;
 602                 case '*':
 603                   /* Ignore the next letter for this pass.  */
 604                   c = *++p;
 605                   break;
 606
 607                 case '?':
 608                   alt_cost += 2;
 609                 case '!':  case '#':  case '&':
 610                 case '0':  case '1':  case '2':  case '3':  case '4':
 611                 case '5':  case '6':  case '7':  case '8':  case '9':
 612                   break;
 613
 614                 case 'p':
 615                   allows_addr = 1;
 616                   win = address_operand (op, GET_MODE (op));
 617                   /* We know this operand is an address, so we want it
 618                      to be allocated to a register that can be the
 619                      base of an address, i.e. BASE_REG_CLASS.  */
 620                   classes[i]
 621                     = ira_reg_class_subunion[classes[i]]
 622                       [base_reg_class (VOIDmode, ADDRESS, SCRATCH)];
 623                   break;
 624
 625                 case 'm':  case 'o':  case 'V':
 626                   /* It doesn't seem worth distinguishing between
 627                      offsettable and non-offsettable addresses
 628                      here.  */
 629                   insn_allows_mem[i] = allows_mem[i] = 1;
 630                   if (MEM_P (op))
 631                     win = 1;
 632                   break;
 633
 634                 case '<':
 635                   if (MEM_P (op)
 636                       && (GET_CODE (XEXP (op, 0)) == PRE_DEC
 637                           || GET_CODE (XEXP (op, 0)) == POST_DEC))
 638                     win = 1;
 639                   break;
 640
 641                 case '>':
 642                   if (MEM_P (op)
 643                       && (GET_CODE (XEXP (op, 0)) == PRE_INC
 644                           || GET_CODE (XEXP (op, 0)) == POST_INC))
 645                     win = 1;
 646                   break;
 647
 648                 case 'E':
 649                 case 'F':
 650                   if (GET_CODE (op) == CONST_DOUBLE
 651                       || (GET_CODE (op) == CONST_VECTOR
 652                           && (GET_MODE_CLASS (GET_MODE (op))
 653                               == MODE_VECTOR_FLOAT)))
 654                     win = 1;
 655                   break;
 656
 657                 case 'G':
 658                 case 'H':
 659                   if (GET_CODE (op) == CONST_DOUBLE
 660                       && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, p))
 661                     win = 1;
 662                   break;
 663
 664                 case 's':
 665                   if (CONST_INT_P (op)
 666                       || (GET_CODE (op) == CONST_DOUBLE
 667                           && GET_MODE (op) == VOIDmode))
 668                     break;
 669
 670                 case 'i':
 671                   if (CONSTANT_P (op)
 672                       && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op)))
 673                     win = 1;
 674                   break;
 675
 676                 case 'n':
 677                   if (CONST_INT_P (op)
 678                       || (GET_CODE (op) == CONST_DOUBLE
 679                           && GET_MODE (op) == VOIDmode))
 680                     win = 1;
 681                   break;
 682
 683                 case 'I':
 684                 case 'J':
 685                 case 'K':
 686                 case 'L':
 687                 case 'M':
 688                 case 'N':
 689                 case 'O':
 690                 case 'P':
 691                   if (CONST_INT_P (op)
 692                       && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, p))
 693                     win = 1;
 694                   break;
 695
 696                 case 'X':
 697                   win = 1;
 698                   break;
 699
 700                 case 'g':
 701                   if (MEM_P (op)
 702                       || (CONSTANT_P (op)
 703                           && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))))
 704                     win = 1;
 705                   insn_allows_mem[i] = allows_mem[i] = 1;
 706                 case 'r':
 707                   classes[i] = ira_reg_class_subunion[classes[i]][GENERAL_REGS];
 708                   break;
 709
 710                 default:
 711                   if (REG_CLASS_FROM_CONSTRAINT (c, p) != NO_REGS)
 712                     classes[i] = ira_reg_class_subunion[classes[i]]
 713                                  [REG_CLASS_FROM_CONSTRAINT (c, p)];
 714 #ifdef EXTRA_CONSTRAINT_STR
 715                   else if (EXTRA_CONSTRAINT_STR (op, c, p))
 716                     win = 1;
 717
 718                   if (EXTRA_MEMORY_CONSTRAINT (c, p))
 719                     {
 720                       /* Every MEM can be reloaded to fit.  */
 721                       insn_allows_mem[i] = allows_mem[i] = 1;
 722                       if (MEM_P (op))
 723                         win = 1;
 724                     }
 725                   if (EXTRA_ADDRESS_CONSTRAINT (c, p))
 726                     {
 727                       /* Every address can be reloaded to fit.  */
 728                       allows_addr = 1;
 729                       if (address_operand (op, GET_MODE (op)))
 730                         win = 1;
 731                       /* We know this operand is an address, so we
 732                          want it to be allocated to a hard register
 733                          that can be the base of an address,
 734                          i.e. BASE_REG_CLASS.  */
 735                       classes[i]
 736                         = ira_reg_class_subunion[classes[i]]
 737                           [base_reg_class (VOIDmode, ADDRESS, SCRATCH)];
 738                     }
 739 #endif
 740                   break;
 741                 }
 742               p += CONSTRAINT_LEN (c, p);
 743               if (c == ',')
 744                 break;
 745             }
 746
 747           constraints[i] = p;
 748
 749           /* How we account for this operand now depends on whether it
 750              is a pseudo register or not.  If it is, we first check if
 751              any register classes are valid.  If not, we ignore this
 752              alternative, since we want to assume that all allocnos get
 753              allocated for register preferencing.  If some register
 754              class is valid, compute the costs of moving the allocno
 755              into that class.  */
 756           if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
 757             {
 758               if (classes[i] == NO_REGS)
 759                 {
 760                   /* We must always fail if the operand is a REG, but
 761                      we did not find a suitable class.
 762
 763                      Otherwise we may perform an uninitialized read
 764                      from this_op_costs after the `continue' statement
 765                      below.  */
 766                   alt_fail = 1;
 767                 }
 768               else
 769                 {
 770                   unsigned int regno = REGNO (op);
 771                   struct costs *pp = this_op_costs[i];
 772                   int *pp_costs = pp->cost;
 773                   cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
 774                   enum reg_class *cost_classes = cost_classes_ptr->classes;
 775                   bool in_p = recog_data.operand_type[i] != OP_OUT;
 776                   bool out_p = recog_data.operand_type[i] != OP_IN;
 777                   enum reg_class op_class = classes[i];
 778                   move_table *move_in_cost, *move_out_cost;
 779
 780                   ira_init_register_move_cost_if_necessary (mode);
 781                   if (! in_p)
 782                     {
 783                       ira_assert (out_p);
 784                       move_out_cost = ira_may_move_out_cost[mode];
 785                       for (k = cost_classes_ptr->num - 1; k >= 0; k--)
 786                         {
 787                           rclass = cost_classes[k];
 788                           pp_costs[k]
 789                             = move_out_cost[op_class][rclass] * frequency;
 790                         }
 791                     }
 792                   else if (! out_p)
 793                     {
 794                       ira_assert (in_p);
 795                       move_in_cost = ira_may_move_in_cost[mode];
 796                       for (k = cost_classes_ptr->num - 1; k >= 0; k--)
 797                         {
 798                           rclass = cost_classes[k];
 799                           pp_costs[k]
 800                             = move_in_cost[rclass][op_class] * frequency;
 801                         }
 802                     }
 803                   else
 804                     {
 805                       move_in_cost = ira_may_move_in_cost[mode];
 806                       move_out_cost = ira_may_move_out_cost[mode];
 807                       for (k = cost_classes_ptr->num - 1; k >= 0; k--)
 808                         {
 809                           rclass = cost_classes[k];
 810                           pp_costs[k] = ((move_in_cost[rclass][op_class]
 811                                           + move_out_cost[op_class][rclass])
 812                                          * frequency);
 813                         }
 814                     }
 815
 816                   /* If the alternative actually allows memory, make
 817                      things a bit cheaper since we won't need an extra
 818                      insn to load it.  */
 819                   pp->mem_cost
 820                     = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
 821                        + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
 822                        - allows_mem[i]) * frequency;
 823                   /* If we have assigned a class to this allocno in
 824                      our first pass, add a cost to this alternative
 825                      corresponding to what we would add if this
 826                      allocno were not in the appropriate class.  */
 827                   if (pref)
 828                     {
 829                       enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
 830
 831                       if (pref_class == NO_REGS)
 832                         alt_cost
 833                           += ((out_p
 834                                ? ira_memory_move_cost[mode][op_class][0] : 0)
 835                               + (in_p
 836                                  ? ira_memory_move_cost[mode][op_class][1]
 837                                  : 0));
 838                       else if (ira_reg_class_intersect[pref_class][op_class]
 839                                == NO_REGS)
 840                         alt_cost += ira_register_move_cost[mode][pref_class][op_class];
 841                     }
 842                 }
 843             }
 844
 845           /* Otherwise, if this alternative wins, either because we
 846              have already determined that or if we have a hard
 847              register of the proper class, there is no cost for this
 848              alternative.  */
 849           else if (win || (REG_P (op)
 850                            && reg_fits_class_p (op, classes[i],
 851                                                 0, GET_MODE (op))))
 852             ;
 853
 854           /* If registers are valid, the cost of this alternative
 855              includes copying the object to and/or from a
 856              register.  */
 857           else if (classes[i] != NO_REGS)
 858             {
 859               if (recog_data.operand_type[i] != OP_OUT)
 860                 alt_cost += copy_cost (op, mode, classes[i], 1, NULL);
 861
 862               if (recog_data.operand_type[i] != OP_IN)
 863                 alt_cost += copy_cost (op, mode, classes[i], 0, NULL);
 864             }
 865           /* The only other way this alternative can be used is if
 866              this is a constant that could be placed into memory.  */
 867           else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
 868             alt_cost += ira_memory_move_cost[mode][classes[i]][1];
 869           else
 870             alt_fail = 1;
 871         }
 872
 873       if (alt_fail)
 874         continue;
 875
 876       op_cost_add = alt_cost * frequency;
 877       /* Finally, update the costs with the information we've
 878          calculated about this alternative.  */
 879       for (i = 0; i < n_ops; i++)
 880         if (REG_P (ops[i]) && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
 881           {
 882             struct costs *pp = op_costs[i], *qq = this_op_costs[i];
 883             int *pp_costs = pp->cost, *qq_costs = qq->cost;
 884             int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
 885             cost_classes_t cost_classes_ptr
 886               = regno_cost_classes[REGNO (ops[i])];
 887
 888             pp->mem_cost = MIN (pp->mem_cost,
 889                                 (qq->mem_cost + op_cost_add) * scale);
 890
 891             for (k = cost_classes_ptr->num - 1; k >= 0; k--)
 892               pp_costs[k]
 893                 = MIN (pp_costs[k], (qq_costs[k] + op_cost_add) * scale);
 894           }
 895     }
 896
 897   if (allocno_p)
 898     for (i = 0; i < n_ops; i++)
 899       {
 900         ira_allocno_t a;
 901         rtx op = ops[i];
 902
 903         if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
 904           continue;
 905         a = ira_curr_regno_allocno_map [REGNO (op)];
 906         if (! ALLOCNO_BAD_SPILL_P (a) && insn_allows_mem[i] == 0)
 907           ALLOCNO_BAD_SPILL_P (a) = true;
 908       }
 909
 910   /* If this insn is a single set copying operand 1 to operand 0 and
 911      one operand is an allocno with the other a hard reg or an allocno
 912      that prefers a hard register that is in its own register class
 913      then we may want to adjust the cost of that register class to -1.
 914
 915      Avoid the adjustment if the source does not die to avoid
 916      stressing of register allocator by preferrencing two colliding
 917      registers into single class.
 918
 919      Also avoid the adjustment if a copy between hard registers of the
 920      class is expensive (ten times the cost of a default copy is
 921      considered arbitrarily expensive).  This avoids losing when the
 922      preferred class is very expensive as the source of a copy
 923      instruction.  */
 924   if ((set = single_set (insn)) != 0
 925       && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set)
 926       && REG_P (ops[0]) && REG_P (ops[1])
 927       && find_regno_note (insn, REG_DEAD, REGNO (ops[1])))
 928     for (i = 0; i <= 1; i++)
 929       if (REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER
 930           && REGNO (ops[!i]) < FIRST_PSEUDO_REGISTER)
 931         {
 932           unsigned int regno = REGNO (ops[i]);
 933           unsigned int other_regno = REGNO (ops[!i]);
 934           enum machine_mode mode = GET_MODE (ops[!i]);
 935           cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
 936           enum reg_class *cost_classes = cost_classes_ptr->classes;
 937           enum reg_class rclass;
 938           int nr;
 939
 940           for (k = cost_classes_ptr->num - 1; k >= 0; k--)
 941             {
 942               rclass = cost_classes[k];
 943               if (TEST_HARD_REG_BIT (reg_class_contents[rclass], other_regno)
 944                   && (reg_class_size[rclass]
 945                       == (unsigned) CLASS_MAX_NREGS (rclass, mode)))
 946                 {
 947                   if (reg_class_size[rclass] == 1)
 948                     op_costs[i]->cost[k] = -frequency;
 949                   else
 950                     {
 951                       for (nr = 0;
 952                            nr < hard_regno_nregs[other_regno][mode];
 953                            nr++)
 954                         if (! TEST_HARD_REG_BIT (reg_class_contents[rclass],
 955                                                  other_regno + nr))
 956                           break;
 957
 958                       if (nr == hard_regno_nregs[other_regno][mode])
 959                         op_costs[i]->cost[k] = -frequency;
 960                     }
 961                 }
 962             }
 963         }
 964 }
 965
 966 \f
 967
 968 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers.  */
 969 static inline bool
 970 ok_for_index_p_nonstrict (rtx reg)
 971 {
 972   unsigned regno = REGNO (reg);
 973
 974   return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
 975 }
 976
 977 /* A version of regno_ok_for_base_p for use here, when all
 978    pseudo-registers should count as OK.  Arguments as for
 979    regno_ok_for_base_p.  */
 980 static inline bool
 981 ok_for_base_p_nonstrict (rtx reg, enum machine_mode mode,
 982                          enum rtx_code outer_code, enum rtx_code index_code)
 983 {
 984   unsigned regno = REGNO (reg);
 985
 986   if (regno >= FIRST_PSEUDO_REGISTER)
 987     return true;
 988   return ok_for_base_p_1 (regno, mode, outer_code, index_code);
 989 }
 990
 991 /* Record the pseudo registers we must reload into hard registers in a
 992    subexpression of a memory address, X.
 993
 994    If CONTEXT is 0, we are looking at the base part of an address,
 995    otherwise we are looking at the index part.
 996
 997    MODE is the mode of the memory reference; OUTER_CODE and INDEX_CODE
 998    give the context that the rtx appears in.  These three arguments
 999    are passed down to base_reg_class.
1000
1001    SCALE is twice the amount to multiply the cost by (it is twice so
1002    we can represent half-cost adjustments).  */
1003 static void
1004 record_address_regs (enum machine_mode mode, rtx x, int context,
1005                      enum rtx_code outer_code, enum rtx_code index_code,
1006                      int scale)
1007 {
1008   enum rtx_code code = GET_CODE (x);
1009   enum reg_class rclass;
1010
1011   if (context == 1)
1012     rclass = INDEX_REG_CLASS;
1013   else
1014     rclass = base_reg_class (mode, outer_code, index_code);
1015
1016   switch (code)
1017     {
1018     case CONST_INT:
1019     case CONST:
1020     case CC0:
1021     case PC:
1022     case SYMBOL_REF:
1023     case LABEL_REF:
1024       return;
1025
1026     case PLUS:
1027       /* When we have an address that is a sum, we must determine
1028          whether registers are "base" or "index" regs.  If there is a
1029          sum of two registers, we must choose one to be the "base".
1030          Luckily, we can use the REG_POINTER to make a good choice
1031          most of the time.  We only need to do this on machines that
1032          can have two registers in an address and where the base and
1033          index register classes are different.
1034
1035          ??? This code used to set REGNO_POINTER_FLAG in some cases,
1036          but that seems bogus since it should only be set when we are
1037          sure the register is being used as a pointer.  */
1038       {
1039         rtx arg0 = XEXP (x, 0);
1040         rtx arg1 = XEXP (x, 1);
1041         enum rtx_code code0 = GET_CODE (arg0);
1042         enum rtx_code code1 = GET_CODE (arg1);
1043
1044         /* Look inside subregs.  */
1045         if (code0 == SUBREG)
1046           arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1047         if (code1 == SUBREG)
1048           arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1049
1050         /* If this machine only allows one register per address, it
1051            must be in the first operand.  */
1052         if (MAX_REGS_PER_ADDRESS == 1)
1053           record_address_regs (mode, arg0, 0, PLUS, code1, scale);
1054
1055         /* If index and base registers are the same on this machine,
1056            just record registers in any non-constant operands.  We
1057            assume here, as well as in the tests below, that all
1058            addresses are in canonical form.  */
1059         else if (INDEX_REG_CLASS == base_reg_class (VOIDmode, PLUS, SCRATCH))
1060           {
1061             record_address_regs (mode, arg0, context, PLUS, code1, scale);
1062             if (! CONSTANT_P (arg1))
1063               record_address_regs (mode, arg1, context, PLUS, code0, scale);
1064           }
1065
1066         /* If the second operand is a constant integer, it doesn't
1067            change what class the first operand must be.  */
1068         else if (code1 == CONST_INT || code1 == CONST_DOUBLE)
1069           record_address_regs (mode, arg0, context, PLUS, code1, scale);
1070         /* If the second operand is a symbolic constant, the first
1071            operand must be an index register.  */
1072         else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1073           record_address_regs (mode, arg0, 1, PLUS, code1, scale);
1074         /* If both operands are registers but one is already a hard
1075            register of index or reg-base class, give the other the
1076            class that the hard register is not.  */
1077         else if (code0 == REG && code1 == REG
1078                  && REGNO (arg0) < FIRST_PSEUDO_REGISTER
1079                  && (ok_for_base_p_nonstrict (arg0, mode, PLUS, REG)
1080                      || ok_for_index_p_nonstrict (arg0)))
1081           record_address_regs (mode, arg1,
1082                                ok_for_base_p_nonstrict (arg0, mode, PLUS, REG)
1083                                ? 1 : 0,
1084                                PLUS, REG, scale);
1085         else if (code0 == REG && code1 == REG
1086                  && REGNO (arg1) < FIRST_PSEUDO_REGISTER
1087                  && (ok_for_base_p_nonstrict (arg1, mode, PLUS, REG)
1088                      || ok_for_index_p_nonstrict (arg1)))
1089           record_address_regs (mode, arg0,
1090                                ok_for_base_p_nonstrict (arg1, mode, PLUS, REG)
1091                                ? 1 : 0,
1092                                PLUS, REG, scale);
1093         /* If one operand is known to be a pointer, it must be the
1094            base with the other operand the index.  Likewise if the
1095            other operand is a MULT.  */
1096         else if ((code0 == REG && REG_POINTER (arg0)) || code1 == MULT)
1097           {
1098             record_address_regs (mode, arg0, 0, PLUS, code1, scale);
1099             record_address_regs (mode, arg1, 1, PLUS, code0, scale);
1100           }
1101         else if ((code1 == REG && REG_POINTER (arg1)) || code0 == MULT)
1102           {
1103             record_address_regs (mode, arg0, 1, PLUS, code1, scale);
1104             record_address_regs (mode, arg1, 0, PLUS, code0, scale);
1105           }
1106         /* Otherwise, count equal chances that each might be a base or
1107            index register.  This case should be rare.  */
1108         else
1109           {
1110             record_address_regs (mode, arg0, 0, PLUS, code1, scale / 2);
1111             record_address_regs (mode, arg0, 1, PLUS, code1, scale / 2);
1112             record_address_regs (mode, arg1, 0, PLUS, code0, scale / 2);
1113             record_address_regs (mode, arg1, 1, PLUS, code0, scale / 2);
1114           }
1115       }
1116       break;
1117
1118       /* Double the importance of an allocno that is incremented or
1119          decremented, since it would take two extra insns if it ends
1120          up in the wrong place.  */
1121     case POST_MODIFY:
1122     case PRE_MODIFY:
1123       record_address_regs (mode, XEXP (x, 0), 0, code,
1124                            GET_CODE (XEXP (XEXP (x, 1), 1)), 2 * scale);
1125       if (REG_P (XEXP (XEXP (x, 1), 1)))
1126         record_address_regs (mode, XEXP (XEXP (x, 1), 1), 1, code, REG,
1127                              2 * scale);
1128       break;
1129
1130     case POST_INC:
1131     case PRE_INC:
1132     case POST_DEC:
1133     case PRE_DEC:
1134       /* Double the importance of an allocno that is incremented or
1135          decremented, since it would take two extra insns if it ends
1136          up in the wrong place.  If the operand is a pseudo-register,
1137          show it is being used in an INC_DEC context.  */
1138 #ifdef FORBIDDEN_INC_DEC_CLASSES
1139       if (REG_P (XEXP (x, 0))
1140           && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER)
1141         in_inc_dec[COST_INDEX (REGNO (XEXP (x, 0)))] = true;
1142 #endif
1143       record_address_regs (mode, XEXP (x, 0), 0, code, SCRATCH, 2 * scale);
1144       break;
1145
1146     case REG:
1147       {
1148         struct costs *pp;
1149         int *pp_costs;
1150         enum reg_class i;
1151         int k, regno, add_cost;
1152         cost_classes_t cost_classes_ptr;
1153         enum reg_class *cost_classes;
1154         move_table *move_in_cost;
1155
1156         if (REGNO (x) < FIRST_PSEUDO_REGISTER)
1157           break;
1158
1159         regno = REGNO (x);
1160         if (allocno_p)
1161           ALLOCNO_BAD_SPILL_P (ira_curr_regno_allocno_map[regno]) = true;
1162         pp = COSTS (costs, COST_INDEX (regno));
1163         add_cost = (ira_memory_move_cost[Pmode][rclass][1] * scale) / 2;
1164         if (INT_MAX - add_cost < pp->mem_cost)
1165           pp->mem_cost = INT_MAX;
1166         else
1167           pp->mem_cost += add_cost;
1168         cost_classes_ptr = regno_cost_classes[regno];
1169         cost_classes = cost_classes_ptr->classes;
1170         pp_costs = pp->cost;
1171         ira_init_register_move_cost_if_necessary (Pmode);
1172         move_in_cost = ira_may_move_in_cost[Pmode];
1173         for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1174           {
1175             i = cost_classes[k];
1176             add_cost = (move_in_cost[i][rclass] * scale) / 2;
1177             if (INT_MAX - add_cost < pp_costs[k])
1178               pp_costs[k] = INT_MAX;
1179             else
1180               pp_costs[k] += add_cost;
1181           }
1182       }
1183       break;
1184
1185     default:
1186       {
1187         const char *fmt = GET_RTX_FORMAT (code);
1188         int i;
1189         for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1190           if (fmt[i] == 'e')
1191             record_address_regs (mode, XEXP (x, i), context, code, SCRATCH,
1192                                  scale);
1193       }
1194     }
1195 }
1196
1197 \f
1198
1199 /* Calculate the costs of insn operands.  */
1200 static void
1201 record_operand_costs (rtx insn, enum reg_class *pref)
1202 {
1203   const char *constraints[MAX_RECOG_OPERANDS];
1204   enum machine_mode modes[MAX_RECOG_OPERANDS];
1205   int i;
1206
1207   for (i = 0; i < recog_data.n_operands; i++)
1208     {
1209       constraints[i] = recog_data.constraints[i];
1210       modes[i] = recog_data.operand_mode[i];
1211     }
1212
1213   /* If we get here, we are set up to record the costs of all the
1214      operands for this insn.  Start by initializing the costs.  Then
1215      handle any address registers.  Finally record the desired classes
1216      for any allocnos, doing it twice if some pair of operands are
1217      commutative.  */
1218   for (i = 0; i < recog_data.n_operands; i++)
1219     {
1220       memcpy (op_costs[i], init_cost, struct_costs_size);
1221
1222       if (GET_CODE (recog_data.operand[i]) == SUBREG)
1223         recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
1224
1225       if (MEM_P (recog_data.operand[i]))
1226         record_address_regs (GET_MODE (recog_data.operand[i]),
1227                              XEXP (recog_data.operand[i], 0),
1228                              0, MEM, SCRATCH, frequency * 2);
1229       else if (constraints[i][0] == 'p'
1230                || EXTRA_ADDRESS_CONSTRAINT (constraints[i][0],
1231                                             constraints[i]))
1232         record_address_regs (VOIDmode, recog_data.operand[i], 0, ADDRESS,
1233                              SCRATCH, frequency * 2);
1234     }
1235
1236   /* Check for commutative in a separate loop so everything will have
1237      been initialized.  We must do this even if one operand is a
1238      constant--see addsi3 in m68k.md.  */
1239   for (i = 0; i < (int) recog_data.n_operands - 1; i++)
1240     if (constraints[i][0] == '%')
1241       {
1242         const char *xconstraints[MAX_RECOG_OPERANDS];
1243         int j;
1244
1245         /* Handle commutative operands by swapping the constraints.
1246            We assume the modes are the same.  */
1247         for (j = 0; j < recog_data.n_operands; j++)
1248           xconstraints[j] = constraints[j];
1249
1250         xconstraints[i] = constraints[i+1];
1251         xconstraints[i+1] = constraints[i];
1252         record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1253                             recog_data.operand, modes,
1254                             xconstraints, insn, pref);
1255       }
1256   record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1257                       recog_data.operand, modes,
1258                       constraints, insn, pref);
1259 }
1260
1261 \f
1262
1263 /* Process one insn INSN.  Scan it and record each time it would save
1264    code to put a certain allocnos in a certain class.  Return the last
1265    insn processed, so that the scan can be continued from there.  */
1266 static rtx
1267 scan_one_insn (rtx insn)
1268 {
1269   enum rtx_code pat_code;
1270   rtx set, note;
1271   int i, k;
1272   bool counted_mem;
1273
1274   if (!NONDEBUG_INSN_P (insn))
1275     return insn;
1276
1277   pat_code = GET_CODE (PATTERN (insn));
1278   if (pat_code == USE || pat_code == CLOBBER || pat_code == ASM_INPUT
1279       || pat_code == ADDR_VEC || pat_code == ADDR_DIFF_VEC)
1280     return insn;
1281
1282   counted_mem = false;
1283   set = single_set (insn);
1284   extract_insn (insn);
1285
1286   /* If this insn loads a parameter from its stack slot, then it
1287      represents a savings, rather than a cost, if the parameter is
1288      stored in memory.  Record this fact.
1289
1290      Similarly if we're loading other constants from memory (constant
1291      pool, TOC references, small data areas, etc) and this is the only
1292      assignment to the destination pseudo.  */
1293   if (set != 0 && REG_P (SET_DEST (set)) && MEM_P (SET_SRC (set))
1294       && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX
1295       && ((MEM_P (XEXP (note, 0)))
1296           || (CONSTANT_P (XEXP (note, 0))
1297               && targetm.legitimate_constant_p (GET_MODE (SET_DEST (set)),
1298                                                 XEXP (note, 0))
1299               && REG_N_SETS (REGNO (SET_DEST (set))) == 1)))
1300     {
1301       enum reg_class cl = GENERAL_REGS;
1302       rtx reg = SET_DEST (set);
1303       int num = COST_INDEX (REGNO (reg));
1304
1305       COSTS (costs, num)->mem_cost
1306         -= ira_memory_move_cost[GET_MODE (reg)][cl][1] * frequency;
1307       record_address_regs (GET_MODE (SET_SRC (set)), XEXP (SET_SRC (set), 0),
1308                            0, MEM, SCRATCH, frequency * 2);
1309       counted_mem = true;
1310     }
1311
1312   record_operand_costs (insn, pref);
1313
1314   /* Now add the cost for each operand to the total costs for its
1315      allocno.  */
1316   for (i = 0; i < recog_data.n_operands; i++)
1317     if (REG_P (recog_data.operand[i])
1318         && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
1319       {
1320         int regno = REGNO (recog_data.operand[i]);
1321         struct costs *p = COSTS (costs, COST_INDEX (regno));
1322         struct costs *q = op_costs[i];
1323         int *p_costs = p->cost, *q_costs = q->cost;
1324         cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1325         int add_cost;
1326
1327         /* If the already accounted for the memory "cost" above, don't
1328            do so again.  */
1329         if (!counted_mem)
1330           {
1331             add_cost = q->mem_cost;
1332             if (add_cost > 0 && INT_MAX - add_cost < p->mem_cost)
1333               p->mem_cost = INT_MAX;
1334             else
1335               p->mem_cost += add_cost;
1336           }
1337         for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1338           {
1339             add_cost = q_costs[k];
1340             if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1341               p_costs[k] = INT_MAX;
1342             else
1343               p_costs[k] += add_cost;
1344           }
1345       }
1346
1347   return insn;
1348 }
1349
1350 \f
1351
1352 /* Print allocnos costs to file F.  */
1353 static void
1354 print_allocno_costs (FILE *f)
1355 {
1356   int k;
1357   ira_allocno_t a;
1358   ira_allocno_iterator ai;
1359
1360   ira_assert (allocno_p);
1361   fprintf (f, "\n");
1362   FOR_EACH_ALLOCNO (a, ai)
1363     {
1364       int i, rclass;
1365       basic_block bb;
1366       int regno = ALLOCNO_REGNO (a);
1367       cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1368       enum reg_class *cost_classes = cost_classes_ptr->classes;
1369
1370       i = ALLOCNO_NUM (a);
1371       fprintf (f, "  a%d(r%d,", i, regno);
1372       if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1373         fprintf (f, "b%d", bb->index);
1374       else
1375         fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
1376       fprintf (f, ") costs:");
1377       for (k = 0; k < cost_classes_ptr->num; k++)
1378         {
1379           rclass = cost_classes[k];
1380           if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1381 #ifdef FORBIDDEN_INC_DEC_CLASSES
1382               && (! in_inc_dec[i] || ! forbidden_inc_dec_class[rclass])
1383 #endif
1384 #ifdef CANNOT_CHANGE_MODE_CLASS
1385               && ! invalid_mode_change_p (regno, (enum reg_class) rclass)
1386 #endif
1387               )
1388             {
1389               fprintf (f, " %s:%d", reg_class_names[rclass],
1390                        COSTS (costs, i)->cost[k]);
1391               if (flag_ira_region == IRA_REGION_ALL
1392                   || flag_ira_region == IRA_REGION_MIXED)
1393                 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->cost[k]);
1394             }
1395         }
1396       fprintf (f, " MEM:%i", COSTS (costs, i)->mem_cost);
1397       if (flag_ira_region == IRA_REGION_ALL
1398           || flag_ira_region == IRA_REGION_MIXED)
1399         fprintf (f, ",%d", COSTS (total_allocno_costs, i)->mem_cost);
1400       fprintf (f, "\n");
1401     }
1402 }
1403
1404 /* Print pseudo costs to file F.  */
1405 static void
1406 print_pseudo_costs (FILE *f)
1407 {
1408   int regno, k;
1409   int rclass;
1410   cost_classes_t cost_classes_ptr;
1411   enum reg_class *cost_classes;
1412
1413   ira_assert (! allocno_p);
1414   fprintf (f, "\n");
1415   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1416     {
1417       if (REG_N_REFS (regno) <= 0)
1418         continue;
1419       cost_classes_ptr = regno_cost_classes[regno];
1420       cost_classes = cost_classes_ptr->classes;
1421       fprintf (f, "  r%d costs:", regno);
1422       for (k = 0; k < cost_classes_ptr->num; k++)
1423         {
1424           rclass = cost_classes[k];
1425           if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1426 #ifdef FORBIDDEN_INC_DEC_CLASSES
1427               && (! in_inc_dec[regno] || ! forbidden_inc_dec_class[rclass])
1428 #endif
1429 #ifdef CANNOT_CHANGE_MODE_CLASS
1430               && ! invalid_mode_change_p (regno, (enum reg_class) rclass)
1431 #endif
1432               )
1433             fprintf (f, " %s:%d", reg_class_names[rclass],
1434                      COSTS (costs, regno)->cost[k]);
1435         }
1436       fprintf (f, " MEM:%i\n", COSTS (costs, regno)->mem_cost);
1437     }
1438 }
1439
1440 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1441    costs.  */
1442 static void
1443 process_bb_for_costs (basic_block bb)
1444 {
1445   rtx insn;
1446
1447   frequency = REG_FREQ_FROM_BB (bb);
1448   if (frequency == 0)
1449     frequency = 1;
1450   FOR_BB_INSNS (bb, insn)
1451     insn = scan_one_insn (insn);
1452 }
1453
1454 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1455    costs.  */
1456 static void
1457 process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node)
1458 {
1459   basic_block bb;
1460
1461   bb = loop_tree_node->bb;
1462   if (bb != NULL)
1463     process_bb_for_costs (bb);
1464 }
1465
1466 /* Find costs of register classes and memory for allocnos or pseudos
1467    and their best costs.  Set up preferred, alternative and allocno
1468    classes for pseudos.  */
1469 static void
1470 find_costs_and_classes (FILE *dump_file)
1471 {
1472   int i, k, start, max_cost_classes_num;
1473   int pass;
1474   basic_block bb;
1475   enum reg_class *regno_best_class;
1476
1477   init_recog ();
1478 #ifdef FORBIDDEN_INC_DEC_CLASSES
1479   in_inc_dec = ira_allocate (sizeof (bool) * cost_elements_num);
1480 #endif /* FORBIDDEN_INC_DEC_CLASSES */
1481   regno_best_class
1482     = (enum reg_class *) ira_allocate (max_reg_num ()
1483                                        * sizeof (enum reg_class));
1484   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1485     regno_best_class[i] = NO_REGS;
1486   if (!resize_reg_info () && allocno_p
1487       && pseudo_classes_defined_p && flag_expensive_optimizations)
1488     {
1489       ira_allocno_t a;
1490       ira_allocno_iterator ai;
1491
1492       pref = pref_buffer;
1493       max_cost_classes_num = 1;
1494       FOR_EACH_ALLOCNO (a, ai)
1495         {
1496           pref[ALLOCNO_NUM (a)] = reg_preferred_class (ALLOCNO_REGNO (a));
1497           setup_regno_cost_classes_by_aclass
1498             (ALLOCNO_REGNO (a), pref[ALLOCNO_NUM (a)]);
1499           max_cost_classes_num
1500             = MAX (max_cost_classes_num,
1501                    regno_cost_classes[ALLOCNO_REGNO (a)]->num);
1502         }
1503       start = 1;
1504     }
1505   else
1506     {
1507       pref = NULL;
1508       max_cost_classes_num = ira_important_classes_num;
1509       for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1510         if (regno_reg_rtx[i] != NULL_RTX)
1511           setup_regno_cost_classes_by_mode (i, PSEUDO_REGNO_MODE (i));
1512         else
1513           setup_regno_cost_classes_by_aclass (i, ALL_REGS);
1514       start = 0;
1515     }
1516   if (allocno_p)
1517     /* Clear the flag for the next compiled function.  */
1518     pseudo_classes_defined_p = false;
1519   /* Normally we scan the insns once and determine the best class to
1520      use for each allocno.  However, if -fexpensive-optimizations are
1521      on, we do so twice, the second time using the tentative best
1522      classes to guide the selection.  */
1523   for (pass = start; pass <= flag_expensive_optimizations; pass++)
1524     {
1525       if ((!allocno_p || internal_flag_ira_verbose > 0) && dump_file)
1526         fprintf (dump_file,
1527                  "\nPass %i for finding pseudo/allocno costs\n\n", pass);
1528
1529       if (pass != start)
1530         {
1531           max_cost_classes_num = 1;
1532           for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1533             {
1534               setup_regno_cost_classes_by_aclass (i, regno_best_class[i]);
1535               max_cost_classes_num
1536                 = MAX (max_cost_classes_num, regno_cost_classes[i]->num);
1537             }
1538         }
1539
1540       struct_costs_size
1541         = sizeof (struct costs) + sizeof (int) * (max_cost_classes_num - 1);
1542       /* Zero out our accumulation of the cost of each class for each
1543          allocno.  */
1544       memset (costs, 0, cost_elements_num * struct_costs_size);
1545 #ifdef FORBIDDEN_INC_DEC_CLASSES
1546       memset (in_inc_dec, 0, cost_elements_num * sizeof (bool));
1547 #endif
1548
1549       if (allocno_p)
1550         {
1551           /* Scan the instructions and record each time it would save code
1552              to put a certain allocno in a certain class.  */
1553           ira_traverse_loop_tree (true, ira_loop_tree_root,
1554                                   process_bb_node_for_costs, NULL);
1555
1556           memcpy (total_allocno_costs, costs,
1557                   max_struct_costs_size * ira_allocnos_num);
1558         }
1559       else
1560         {
1561           basic_block bb;
1562
1563           FOR_EACH_BB (bb)
1564             process_bb_for_costs (bb);
1565         }
1566
1567       if (pass == 0)
1568         pref = pref_buffer;
1569
1570       /* Now for each allocno look at how desirable each class is and
1571          find which class is preferred.  */
1572       for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1573         {
1574           ira_allocno_t a, parent_a;
1575           int rclass, a_num, parent_a_num, add_cost;
1576           ira_loop_tree_node_t parent;
1577           int best_cost, allocno_cost;
1578           enum reg_class best, alt_class;
1579 #ifdef FORBIDDEN_INC_DEC_CLASSES
1580           int inc_dec_p = false;
1581 #endif
1582           cost_classes_t cost_classes_ptr = regno_cost_classes[i];
1583           enum reg_class *cost_classes = cost_classes_ptr->classes;
1584           int *i_costs = temp_costs->cost;
1585           int i_mem_cost;
1586           int equiv_savings = regno_equiv_gains[i];
1587
1588           if (! allocno_p)
1589             {
1590               if (regno_reg_rtx[i] == NULL_RTX)
1591                 continue;
1592 #ifdef FORBIDDEN_INC_DEC_CLASSES
1593               inc_dec_p = in_inc_dec[i];
1594 #endif
1595               memcpy (temp_costs, COSTS (costs, i), struct_costs_size);
1596               i_mem_cost = temp_costs->mem_cost;
1597             }
1598           else
1599             {
1600               if (ira_regno_allocno_map[i] == NULL)
1601                 continue;
1602               memset (temp_costs, 0, struct_costs_size);
1603               i_mem_cost = 0;
1604               /* Find cost of all allocnos with the same regno.  */
1605               for (a = ira_regno_allocno_map[i];
1606                    a != NULL;
1607                    a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1608                 {
1609                   int *a_costs, *p_costs;
1610
1611                   a_num = ALLOCNO_NUM (a);
1612                   if ((flag_ira_region == IRA_REGION_ALL
1613                        || flag_ira_region == IRA_REGION_MIXED)
1614                       && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1615                       && (parent_a = parent->regno_allocno_map[i]) != NULL
1616                       /* There are no caps yet.  */
1617                       && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE
1618                                        (a)->border_allocnos,
1619                                        ALLOCNO_NUM (a)))
1620                     {
1621                       /* Propagate costs to upper levels in the region
1622                          tree.  */
1623                       parent_a_num = ALLOCNO_NUM (parent_a);
1624                       a_costs = COSTS (total_allocno_costs, a_num)->cost;
1625                       p_costs = COSTS (total_allocno_costs, parent_a_num)->cost;
1626                       for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1627                         {
1628                           add_cost = a_costs[k];
1629                           if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1630                             p_costs[k] = INT_MAX;
1631                           else
1632                             p_costs[k] += add_cost;
1633                         }
1634                       add_cost = COSTS (total_allocno_costs, a_num)->mem_cost;
1635                       if (add_cost > 0
1636                           && (INT_MAX - add_cost
1637                               < COSTS (total_allocno_costs,
1638                                        parent_a_num)->mem_cost))
1639                         COSTS (total_allocno_costs, parent_a_num)->mem_cost
1640                           = INT_MAX;
1641                       else
1642                         COSTS (total_allocno_costs, parent_a_num)->mem_cost
1643                           += add_cost;
1644
1645                     }
1646                   a_costs = COSTS (costs, a_num)->cost;
1647                   for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1648                     {
1649                       add_cost = a_costs[k];
1650                       if (add_cost > 0 && INT_MAX - add_cost < i_costs[k])
1651                         i_costs[k] = INT_MAX;
1652                       else
1653                         i_costs[k] += add_cost;
1654                     }
1655                   add_cost = COSTS (costs, a_num)->mem_cost;
1656                   if (add_cost > 0 && INT_MAX - add_cost < i_mem_cost)
1657                     i_mem_cost = INT_MAX;
1658                   else
1659                     i_mem_cost += add_cost;
1660 #ifdef FORBIDDEN_INC_DEC_CLASSES
1661                   if (in_inc_dec[a_num])
1662                     inc_dec_p = true;
1663 #endif
1664                 }
1665             }
1666           if (equiv_savings < 0)
1667             i_mem_cost = -equiv_savings;
1668           else if (equiv_savings > 0)
1669             {
1670               i_mem_cost = 0;
1671               for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1672                 i_costs[k] += equiv_savings;
1673             }
1674
1675           best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1676           best = ALL_REGS;
1677           alt_class = NO_REGS;
1678           /* Find best common class for all allocnos with the same
1679              regno.  */
1680           for (k = 0; k < cost_classes_ptr->num; k++)
1681             {
1682               rclass = cost_classes[k];
1683               /* Ignore classes that are too small for this operand or
1684                  invalid for an operand that was auto-incremented.  */
1685               if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1686 #ifdef FORBIDDEN_INC_DEC_CLASSES
1687                   || (inc_dec_p && forbidden_inc_dec_class[rclass])
1688 #endif
1689 #ifdef CANNOT_CHANGE_MODE_CLASS
1690                   || invalid_mode_change_p (i, (enum reg_class) rclass)
1691 #endif
1692                   )
1693                 continue;
1694               if (i_costs[k] < best_cost)
1695                 {
1696                   best_cost = i_costs[k];
1697                   best = (enum reg_class) rclass;
1698                 }
1699               else if (i_costs[k] == best_cost)
1700                 best = ira_reg_class_subunion[best][rclass];
1701               if (pass == flag_expensive_optimizations
1702                   && i_costs[k] < i_mem_cost
1703                   && (reg_class_size[reg_class_subunion[alt_class][rclass]]
1704                       > reg_class_size[alt_class]))
1705                 alt_class = reg_class_subunion[alt_class][rclass];
1706             }
1707           alt_class = ira_allocno_class_translate[alt_class];
1708           if (best_cost > i_mem_cost)
1709             regno_aclass[i] = NO_REGS;
1710           else
1711             {
1712               /* Make the common class the biggest class of best and
1713                  alt_class.  */
1714               regno_aclass[i]
1715                 = ira_reg_class_superunion[best][alt_class];
1716               ira_assert (regno_aclass[i] != NO_REGS
1717                           && ira_reg_allocno_class_p[regno_aclass[i]]);
1718             }
1719           if (pass == flag_expensive_optimizations)
1720             {
1721               if (best_cost > i_mem_cost)
1722                 best = alt_class = NO_REGS;
1723               else if (best == alt_class)
1724                 alt_class = NO_REGS;
1725               setup_reg_classes (i, best, alt_class, regno_aclass[i]);
1726               if ((!allocno_p || internal_flag_ira_verbose > 2)
1727                   && dump_file != NULL)
1728                 fprintf (dump_file,
1729                          "    r%d: preferred %s, alternative %s, allocno %s\n",
1730                          i, reg_class_names[best], reg_class_names[alt_class],
1731                          reg_class_names[regno_aclass[i]]);
1732             }
1733           regno_best_class[i] = best;
1734           if (! allocno_p)
1735             {
1736               pref[i] = best_cost > i_mem_cost ? NO_REGS : best;
1737               continue;
1738             }
1739           for (a = ira_regno_allocno_map[i];
1740                a != NULL;
1741                a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1742             {
1743               a_num = ALLOCNO_NUM (a);
1744               if (regno_aclass[i] == NO_REGS)
1745                 best = NO_REGS;
1746               else
1747                 {
1748                   int *total_a_costs = COSTS (total_allocno_costs, a_num)->cost;
1749                   int *a_costs = COSTS (costs, a_num)->cost;
1750
1751                   /* Finding best class which is subset of the common
1752                      class.  */
1753                   best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1754                   allocno_cost = best_cost;
1755                   best = ALL_REGS;
1756                   for (k = 0; k < cost_classes_ptr->num; k++)
1757                     {
1758                       rclass = cost_classes[k];
1759                       if (! ira_class_subset_p[rclass][regno_aclass[i]])
1760                         continue;
1761                       /* Ignore classes that are too small for this
1762                          operand or invalid for an operand that was
1763                          auto-incremented.  */
1764                       if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1765 #ifdef FORBIDDEN_INC_DEC_CLASSES
1766                           || (inc_dec_p && forbidden_inc_dec_class[rclass])
1767 #endif
1768 #ifdef CANNOT_CHANGE_MODE_CLASS
1769                           || invalid_mode_change_p (i, (enum reg_class) rclass)
1770 #endif
1771                           )
1772                         ;
1773                       else if (total_a_costs[k] < best_cost)
1774                         {
1775                           best_cost = total_a_costs[k];
1776                           allocno_cost = a_costs[k];
1777                           best = (enum reg_class) rclass;
1778                         }
1779                       else if (total_a_costs[k] == best_cost)
1780                         {
1781                           best = ira_reg_class_subunion[best][rclass];
1782                           allocno_cost = MAX (allocno_cost, a_costs[k]);
1783                         }
1784                     }
1785                   ALLOCNO_CLASS_COST (a) = allocno_cost;
1786                 }
1787               if (internal_flag_ira_verbose > 2 && dump_file != NULL
1788                   && (pass == 0 || pref[a_num] != best))
1789                 {
1790                   fprintf (dump_file, "    a%d (r%d,", a_num, i);
1791                   if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1792                     fprintf (dump_file, "b%d", bb->index);
1793                   else
1794                     fprintf (dump_file, "l%d",
1795                              ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
1796                   fprintf (dump_file, ") best %s, allocno %s\n",
1797                            reg_class_names[best],
1798                            reg_class_names[regno_aclass[i]]);
1799                 }
1800               pref[a_num] = best;
1801             }
1802         }
1803
1804       if (internal_flag_ira_verbose > 4 && dump_file)
1805         {
1806           if (allocno_p)
1807             print_allocno_costs (dump_file);
1808           else
1809             print_pseudo_costs (dump_file);
1810           fprintf (dump_file,"\n");
1811         }
1812     }
1813   ira_free (regno_best_class);
1814 #ifdef FORBIDDEN_INC_DEC_CLASSES
1815   ira_free (in_inc_dec);
1816 #endif
1817 }
1818
1819 \f
1820
1821 /* Process moves involving hard regs to modify allocno hard register
1822    costs.  We can do this only after determining allocno class.  If a
1823    hard register forms a register class, than moves with the hard
1824    register are already taken into account in class costs for the
1825    allocno.  */
1826 static void
1827 process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
1828 {
1829   int i, freq, cost, src_regno, dst_regno, hard_regno;
1830   bool to_p;
1831   ira_allocno_t a;
1832   enum reg_class rclass, hard_reg_class;
1833   enum machine_mode mode;
1834   basic_block bb;
1835   rtx insn, set, src, dst;
1836
1837   bb = loop_tree_node->bb;
1838   if (bb == NULL)
1839     return;
1840   freq = REG_FREQ_FROM_BB (bb);
1841   if (freq == 0)
1842     freq = 1;
1843   FOR_BB_INSNS (bb, insn)
1844     {
1845       if (!NONDEBUG_INSN_P (insn))
1846         continue;
1847       set = single_set (insn);
1848       if (set == NULL_RTX)
1849         continue;
1850       dst = SET_DEST (set);
1851       src = SET_SRC (set);
1852       if (! REG_P (dst) || ! REG_P (src))
1853         continue;
1854       dst_regno = REGNO (dst);
1855       src_regno = REGNO (src);
1856       if (dst_regno >= FIRST_PSEUDO_REGISTER
1857           && src_regno < FIRST_PSEUDO_REGISTER)
1858         {
1859           hard_regno = src_regno;
1860           to_p = true;
1861           a = ira_curr_regno_allocno_map[dst_regno];
1862         }
1863       else if (src_regno >= FIRST_PSEUDO_REGISTER
1864                && dst_regno < FIRST_PSEUDO_REGISTER)
1865         {
1866           hard_regno = dst_regno;
1867           to_p = false;
1868           a = ira_curr_regno_allocno_map[src_regno];
1869         }
1870       else
1871         continue;
1872       rclass = ALLOCNO_CLASS (a);
1873       if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno))
1874         continue;
1875       i = ira_class_hard_reg_index[rclass][hard_regno];
1876       if (i < 0)
1877         continue;
1878       mode = ALLOCNO_MODE (a);
1879       hard_reg_class = REGNO_REG_CLASS (hard_regno);
1880       ira_init_register_move_cost_if_necessary (mode);
1881       cost
1882         = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass]
1883            : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq;
1884       ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass,
1885                                   ALLOCNO_CLASS_COST (a));
1886       ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1887                                   rclass, 0);
1888       ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
1889       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
1890       ALLOCNO_CLASS_COST (a) = MIN (ALLOCNO_CLASS_COST (a),
1891                                     ALLOCNO_HARD_REG_COSTS (a)[i]);
1892     }
1893 }
1894
1895 /* After we find hard register and memory costs for allocnos, define
1896    its class and modify hard register cost because insns moving
1897    allocno to/from hard registers.  */
1898 static void
1899 setup_allocno_class_and_costs (void)
1900 {
1901   int i, j, n, regno, hard_regno, num;
1902   int *reg_costs;
1903   enum reg_class aclass, rclass;
1904   ira_allocno_t a;
1905   ira_allocno_iterator ai;
1906   cost_classes_t cost_classes_ptr;
1907
1908   ira_assert (allocno_p);
1909   FOR_EACH_ALLOCNO (a, ai)
1910     {
1911       i = ALLOCNO_NUM (a);
1912       regno = ALLOCNO_REGNO (a);
1913       aclass = regno_aclass[regno];
1914       cost_classes_ptr = regno_cost_classes[regno];
1915       ira_assert (pref[i] == NO_REGS || aclass != NO_REGS);
1916       ALLOCNO_MEMORY_COST (a) = COSTS (costs, i)->mem_cost;
1917       ira_set_allocno_class (a, aclass);
1918       if (aclass == NO_REGS)
1919         continue;
1920       if (optimize && ALLOCNO_CLASS (a) != pref[i])
1921         {
1922           n = ira_class_hard_regs_num[aclass];
1923           ALLOCNO_HARD_REG_COSTS (a)
1924             = reg_costs = ira_allocate_cost_vector (aclass);
1925           for (j = n - 1; j >= 0; j--)
1926             {
1927               hard_regno = ira_class_hard_regs[aclass][j];
1928               if (TEST_HARD_REG_BIT (reg_class_contents[pref[i]], hard_regno))
1929                 reg_costs[j] = ALLOCNO_CLASS_COST (a);
1930               else
1931                 {
1932                   rclass = REGNO_REG_CLASS (hard_regno);
1933                   num = cost_classes_ptr->index[rclass];
1934                   if (num < 0)
1935                     {
1936                       num = cost_classes_ptr->hard_regno_index[hard_regno];
1937                       ira_assert (num >= 0);
1938                     }
1939                   reg_costs[j] = COSTS (costs, i)->cost[num];
1940                 }
1941             }
1942         }
1943     }
1944   if (optimize)
1945     ira_traverse_loop_tree (true, ira_loop_tree_root,
1946                             process_bb_node_for_hard_reg_moves, NULL);
1947 }
1948
1949 \f
1950
1951 /* Function called once during compiler work.  */
1952 void
1953 ira_init_costs_once (void)
1954 {
1955   int i;
1956
1957   init_cost = NULL;
1958   for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1959     {
1960       op_costs[i] = NULL;
1961       this_op_costs[i] = NULL;
1962     }
1963   temp_costs = NULL;
1964 }
1965
1966 /* Free allocated temporary cost vectors.  */
1967 static void
1968 free_ira_costs (void)
1969 {
1970   int i;
1971
1972   free (init_cost);
1973   init_cost = NULL;
1974   for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1975     {
1976       free (op_costs[i]);
1977       free (this_op_costs[i]);
1978       op_costs[i] = this_op_costs[i] = NULL;
1979     }
1980   free (temp_costs);
1981   temp_costs = NULL;
1982 }
1983
1984 /* This is called each time register related information is
1985    changed.  */
1986 void
1987 ira_init_costs (void)
1988 {
1989   int i;
1990
1991   free_ira_costs ();
1992   max_struct_costs_size
1993     = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1);
1994   /* Don't use ira_allocate because vectors live through several IRA
1995      calls.  */
1996   init_cost = (struct costs *) xmalloc (max_struct_costs_size);
1997   init_cost->mem_cost = 1000000;
1998   for (i = 0; i < ira_important_classes_num; i++)
1999     init_cost->cost[i] = 1000000;
2000   for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2001     {
2002       op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2003       this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2004     }
2005   temp_costs = (struct costs *) xmalloc (max_struct_costs_size);
2006 }
2007
2008 /* Function called once at the end of compiler work.  */
2009 void
2010 ira_finish_costs_once (void)
2011 {
2012   free_ira_costs ();
2013 }
2014
2015 \f
2016
2017 /* Common initialization function for ira_costs and
2018    ira_set_pseudo_classes.  */
2019 static void
2020 init_costs (void)
2021 {
2022   init_subregs_of_mode ();
2023   costs = (struct costs *) ira_allocate (max_struct_costs_size
2024                                          * cost_elements_num);
2025   pref_buffer = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2026                                                  * cost_elements_num);
2027   regno_aclass = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2028                                                  * max_reg_num ());
2029   regno_equiv_gains = (int *) ira_allocate (sizeof (int) * max_reg_num ());
2030   memset (regno_equiv_gains, 0, sizeof (int) * max_reg_num ());
2031 }
2032
2033 /* Common finalization function for ira_costs and
2034    ira_set_pseudo_classes.  */
2035 static void
2036 finish_costs (void)
2037 {
2038   finish_subregs_of_mode ();
2039   ira_free (regno_equiv_gains);
2040   ira_free (regno_aclass);
2041   ira_free (pref_buffer);
2042   ira_free (costs);
2043 }
2044
2045 /* Entry function which defines register class, memory and hard
2046    register costs for each allocno.  */
2047 void
2048 ira_costs (void)
2049 {
2050   allocno_p = true;
2051   cost_elements_num = ira_allocnos_num;
2052   init_costs ();
2053   total_allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
2054                                                        * ira_allocnos_num);
2055   initiate_regno_cost_classes ();
2056   calculate_elim_costs_all_insns ();
2057   find_costs_and_classes (ira_dump_file);
2058   setup_allocno_class_and_costs ();
2059   finish_regno_cost_classes ();
2060   finish_costs ();
2061   ira_free (total_allocno_costs);
2062 }
2063
2064 /* Entry function which defines classes for pseudos.  */
2065 void
2066 ira_set_pseudo_classes (FILE *dump_file)
2067 {
2068   allocno_p = false;
2069   internal_flag_ira_verbose = flag_ira_verbose;
2070   cost_elements_num = max_reg_num ();
2071   init_costs ();
2072   initiate_regno_cost_classes ();
2073   find_costs_and_classes (dump_file);
2074   finish_regno_cost_classes ();
2075   pseudo_classes_defined_p = true;
2076   finish_costs ();
2077 }
2078
2079 \f
2080
2081 /* Change hard register costs for allocnos which lives through
2082    function calls.  This is called only when we found all intersected
2083    calls during building allocno live ranges.  */
2084 void
2085 ira_tune_allocno_costs (void)
2086 {
2087   int j, n, regno;
2088   int cost, min_cost, *reg_costs;
2089   enum reg_class aclass, rclass;
2090   enum machine_mode mode;
2091   ira_allocno_t a;
2092   ira_allocno_iterator ai;
2093   ira_allocno_object_iterator oi;
2094   ira_object_t obj;
2095   bool skip_p;
2096
2097   FOR_EACH_ALLOCNO (a, ai)
2098     {
2099       aclass = ALLOCNO_CLASS (a);
2100       if (aclass == NO_REGS)
2101         continue;
2102       mode = ALLOCNO_MODE (a);
2103       n = ira_class_hard_regs_num[aclass];
2104       min_cost = INT_MAX;
2105       if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2106         {
2107           ira_allocate_and_set_costs
2108             (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2109              ALLOCNO_CLASS_COST (a));
2110           reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2111           for (j = n - 1; j >= 0; j--)
2112             {
2113               regno = ira_class_hard_regs[aclass][j];
2114               skip_p = false;
2115               FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2116                 {
2117                   if (! ira_hard_reg_not_in_set_p (regno, mode,
2118                                                    OBJECT_CONFLICT_HARD_REGS
2119                                                    (obj)))
2120                     {
2121                       skip_p = true;
2122                       break;
2123                     }
2124                 }
2125               if (skip_p)
2126                 continue;
2127               rclass = REGNO_REG_CLASS (regno);
2128               cost = 0;
2129               if (! ira_hard_reg_not_in_set_p (regno, mode, call_used_reg_set)
2130                   || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
2131                 cost += (ALLOCNO_CALL_FREQ (a)
2132                          * (ira_memory_move_cost[mode][rclass][0]
2133                             + ira_memory_move_cost[mode][rclass][1]));
2134 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
2135               cost += ((ira_memory_move_cost[mode][rclass][0]
2136                         + ira_memory_move_cost[mode][rclass][1])
2137                        * ALLOCNO_FREQ (a)
2138                        * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2);
2139 #endif
2140               if (INT_MAX - cost < reg_costs[j])
2141                 reg_costs[j] = INT_MAX;
2142               else
2143                 reg_costs[j] += cost;
2144               if (min_cost > reg_costs[j])
2145                 min_cost = reg_costs[j];
2146             }
2147         }
2148       if (min_cost != INT_MAX)
2149         ALLOCNO_CLASS_COST (a) = min_cost;
2150
2151       /* Some targets allow pseudos to be allocated to unaligned sequences
2152          of hard registers.  However, selecting an unaligned sequence can
2153          unnecessarily restrict later allocations.  So increase the cost of
2154          unaligned hard regs to encourage the use of aligned hard regs.  */
2155       {
2156         const int nregs = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2157
2158         if (nregs > 1)
2159           {
2160             ira_allocate_and_set_costs
2161               (&ALLOCNO_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a));
2162             reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2163             for (j = n - 1; j >= 0; j--)
2164               {
2165                 regno = ira_non_ordered_class_hard_regs[aclass][j];
2166                 if ((regno % nregs) != 0)
2167                   {
2168                     int index = ira_class_hard_reg_index[aclass][regno];
2169                     ira_assert (index != -1);
2170                     reg_costs[index] += ALLOCNO_FREQ (a);
2171                   }
2172               }
2173           }
2174       }
2175     }
2176 }
2177
2178 /* Add COST to the estimated gain for eliminating REGNO with its
2179    equivalence.  If COST is zero, record that no such elimination is
2180    possible.  */
2181
2182 void
2183 ira_adjust_equiv_reg_cost (unsigned regno, int cost)
2184 {
2185   if (cost == 0)
2186     regno_equiv_gains[regno] = 0;
2187   else
2188     regno_equiv_gains[regno] += cost;
2189 }