gcc/ira-costs.c

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