gcc/ira-costs.c

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