gcc/ira-costs.c

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