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