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