gcc/ira.c

   1 /* Integrated Register Allocator (IRA) entry point.
   2    Copyright (C) 2006-2014 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* The integrated register allocator (IRA) is a
  22    regional register allocator performing graph coloring on a top-down
  23    traversal of nested regions.  Graph coloring in a region is based
  24    on Chaitin-Briggs algorithm.  It is called integrated because
  25    register coalescing, register live range splitting, and choosing a
  26    better hard register are done on-the-fly during coloring.  Register
  27    coalescing and choosing a cheaper hard register is done by hard
  28    register preferencing during hard register assigning.  The live
  29    range splitting is a byproduct of the regional register allocation.
  30
  31    Major IRA notions are:
  32
  33      o *Region* is a part of CFG where graph coloring based on
  34        Chaitin-Briggs algorithm is done.  IRA can work on any set of
  35        nested CFG regions forming a tree.  Currently the regions are
  36        the entire function for the root region and natural loops for
  37        the other regions.  Therefore data structure representing a
  38        region is called loop_tree_node.
  39
  40      o *Allocno class* is a register class used for allocation of
  41        given allocno.  It means that only hard register of given
  42        register class can be assigned to given allocno.  In reality,
  43        even smaller subset of (*profitable*) hard registers can be
  44        assigned.  In rare cases, the subset can be even smaller
  45        because our modification of Chaitin-Briggs algorithm requires
  46        that sets of hard registers can be assigned to allocnos forms a
  47        forest, i.e. the sets can be ordered in a way where any
  48        previous set is not intersected with given set or is a superset
  49        of given set.
  50
  51      o *Pressure class* is a register class belonging to a set of
  52        register classes containing all of the hard-registers available
  53        for register allocation.  The set of all pressure classes for a
  54        target is defined in the corresponding machine-description file
  55        according some criteria.  Register pressure is calculated only
  56        for pressure classes and it affects some IRA decisions as
  57        forming allocation regions.
  58
  59      o *Allocno* represents the live range of a pseudo-register in a
  60        region.  Besides the obvious attributes like the corresponding
  61        pseudo-register number, allocno class, conflicting allocnos and
  62        conflicting hard-registers, there are a few allocno attributes
  63        which are important for understanding the allocation algorithm:
  64
  65        - *Live ranges*.  This is a list of ranges of *program points*
  66          where the allocno lives.  Program points represent places
  67          where a pseudo can be born or become dead (there are
  68          approximately two times more program points than the insns)
  69          and they are represented by integers starting with 0.  The
  70          live ranges are used to find conflicts between allocnos.
  71          They also play very important role for the transformation of
  72          the IRA internal representation of several regions into a one
  73          region representation.  The later is used during the reload
  74          pass work because each allocno represents all of the
  75          corresponding pseudo-registers.
  76
  77        - *Hard-register costs*.  This is a vector of size equal to the
  78          number of available hard-registers of the allocno class.  The
  79          cost of a callee-clobbered hard-register for an allocno is
  80          increased by the cost of save/restore code around the calls
  81          through the given allocno's life.  If the allocno is a move
  82          instruction operand and another operand is a hard-register of
  83          the allocno class, the cost of the hard-register is decreased
  84          by the move cost.
  85
  86          When an allocno is assigned, the hard-register with minimal
  87          full cost is used.  Initially, a hard-register's full cost is
  88          the corresponding value from the hard-register's cost vector.
  89          If the allocno is connected by a *copy* (see below) to
  90          another allocno which has just received a hard-register, the
  91          cost of the hard-register is decreased.  Before choosing a
  92          hard-register for an allocno, the allocno's current costs of
  93          the hard-registers are modified by the conflict hard-register
  94          costs of all of the conflicting allocnos which are not
  95          assigned yet.
  96
  97        - *Conflict hard-register costs*.  This is a vector of the same
  98          size as the hard-register costs vector.  To permit an
  99          unassigned allocno to get a better hard-register, IRA uses
 100          this vector to calculate the final full cost of the
 101          available hard-registers.  Conflict hard-register costs of an
 102          unassigned allocno are also changed with a change of the
 103          hard-register cost of the allocno when a copy involving the
 104          allocno is processed as described above.  This is done to
 105          show other unassigned allocnos that a given allocno prefers
 106          some hard-registers in order to remove the move instruction
 107          corresponding to the copy.
 108
 109      o *Cap*.  If a pseudo-register does not live in a region but
 110        lives in a nested region, IRA creates a special allocno called
 111        a cap in the outer region.  A region cap is also created for a
 112        subregion cap.
 113
 114      o *Copy*.  Allocnos can be connected by copies.  Copies are used
 115        to modify hard-register costs for allocnos during coloring.
 116        Such modifications reflects a preference to use the same
 117        hard-register for the allocnos connected by copies.  Usually
 118        copies are created for move insns (in this case it results in
 119        register coalescing).  But IRA also creates copies for operands
 120        of an insn which should be assigned to the same hard-register
 121        due to constraints in the machine description (it usually
 122        results in removing a move generated in reload to satisfy
 123        the constraints) and copies referring to the allocno which is
 124        the output operand of an instruction and the allocno which is
 125        an input operand dying in the instruction (creation of such
 126        copies results in less register shuffling).  IRA *does not*
 127        create copies between the same register allocnos from different
 128        regions because we use another technique for propagating
 129        hard-register preference on the borders of regions.
 130
 131    Allocnos (including caps) for the upper region in the region tree
 132    *accumulate* information important for coloring from allocnos with
 133    the same pseudo-register from nested regions.  This includes
 134    hard-register and memory costs, conflicts with hard-registers,
 135    allocno conflicts, allocno copies and more.  *Thus, attributes for
 136    allocnos in a region have the same values as if the region had no
 137    subregions*.  It means that attributes for allocnos in the
 138    outermost region corresponding to the function have the same values
 139    as though the allocation used only one region which is the entire
 140    function.  It also means that we can look at IRA work as if the
 141    first IRA did allocation for all function then it improved the
 142    allocation for loops then their subloops and so on.
 143
 144    IRA major passes are:
 145
 146      o Building IRA internal representation which consists of the
 147        following subpasses:
 148
 149        * First, IRA builds regions and creates allocnos (file
 150          ira-build.c) and initializes most of their attributes.
 151
 152        * Then IRA finds an allocno class for each allocno and
 153          calculates its initial (non-accumulated) cost of memory and
 154          each hard-register of its allocno class (file ira-cost.c).
 155
 156        * IRA creates live ranges of each allocno, calculates register
 157          pressure for each pressure class in each region, sets up
 158          conflict hard registers for each allocno and info about calls
 159          the allocno lives through (file ira-lives.c).
 160
 161        * IRA removes low register pressure loops from the regions
 162          mostly to speed IRA up (file ira-build.c).
 163
 164        * IRA propagates accumulated allocno info from lower region
 165          allocnos to corresponding upper region allocnos (file
 166          ira-build.c).
 167
 168        * IRA creates all caps (file ira-build.c).
 169
 170        * Having live-ranges of allocnos and their classes, IRA creates
 171          conflicting allocnos for each allocno.  Conflicting allocnos
 172          are stored as a bit vector or array of pointers to the
 173          conflicting allocnos whatever is more profitable (file
 174          ira-conflicts.c).  At this point IRA creates allocno copies.
 175
 176      o Coloring.  Now IRA has all necessary info to start graph coloring
 177        process.  It is done in each region on top-down traverse of the
 178        region tree (file ira-color.c).  There are following subpasses:
 179
 180        * Finding profitable hard registers of corresponding allocno
 181          class for each allocno.  For example, only callee-saved hard
 182          registers are frequently profitable for allocnos living
 183          through colors.  If the profitable hard register set of
 184          allocno does not form a tree based on subset relation, we use
 185          some approximation to form the tree.  This approximation is
 186          used to figure out trivial colorability of allocnos.  The
 187          approximation is a pretty rare case.
 188
 189        * Putting allocnos onto the coloring stack.  IRA uses Briggs
 190          optimistic coloring which is a major improvement over
 191          Chaitin's coloring.  Therefore IRA does not spill allocnos at
 192          this point.  There is some freedom in the order of putting
 193          allocnos on the stack which can affect the final result of
 194          the allocation.  IRA uses some heuristics to improve the
 195          order.  The major one is to form *threads* from colorable
 196          allocnos and push them on the stack by threads.  Thread is a
 197          set of non-conflicting colorable allocnos connected by
 198          copies.  The thread contains allocnos from the colorable
 199          bucket or colorable allocnos already pushed onto the coloring
 200          stack.  Pushing thread allocnos one after another onto the
 201          stack increases chances of removing copies when the allocnos
 202          get the same hard reg.
 203
 204          We also use a modification of Chaitin-Briggs algorithm which
 205          works for intersected register classes of allocnos.  To
 206          figure out trivial colorability of allocnos, the mentioned
 207          above tree of hard register sets is used.  To get an idea how
 208          the algorithm works in i386 example, let us consider an
 209          allocno to which any general hard register can be assigned.
 210          If the allocno conflicts with eight allocnos to which only
 211          EAX register can be assigned, given allocno is still
 212          trivially colorable because all conflicting allocnos might be
 213          assigned only to EAX and all other general hard registers are
 214          still free.
 215
 216          To get an idea of the used trivial colorability criterion, it
 217          is also useful to read article "Graph-Coloring Register
 218          Allocation for Irregular Architectures" by Michael D. Smith
 219          and Glen Holloway.  Major difference between the article
 220          approach and approach used in IRA is that Smith's approach
 221          takes register classes only from machine description and IRA
 222          calculate register classes from intermediate code too
 223          (e.g. an explicit usage of hard registers in RTL code for
 224          parameter passing can result in creation of additional
 225          register classes which contain or exclude the hard
 226          registers).  That makes IRA approach useful for improving
 227          coloring even for architectures with regular register files
 228          and in fact some benchmarking shows the improvement for
 229          regular class architectures is even bigger than for irregular
 230          ones.  Another difference is that Smith's approach chooses
 231          intersection of classes of all insn operands in which a given
 232          pseudo occurs.  IRA can use bigger classes if it is still
 233          more profitable than memory usage.
 234
 235        * Popping the allocnos from the stack and assigning them hard
 236          registers.  If IRA can not assign a hard register to an
 237          allocno and the allocno is coalesced, IRA undoes the
 238          coalescing and puts the uncoalesced allocnos onto the stack in
 239          the hope that some such allocnos will get a hard register
 240          separately.  If IRA fails to assign hard register or memory
 241          is more profitable for it, IRA spills the allocno.  IRA
 242          assigns the allocno the hard-register with minimal full
 243          allocation cost which reflects the cost of usage of the
 244          hard-register for the allocno and cost of usage of the
 245          hard-register for allocnos conflicting with given allocno.
 246
 247        * Chaitin-Briggs coloring assigns as many pseudos as possible
 248          to hard registers.  After coloring we try to improve
 249          allocation with cost point of view.  We improve the
 250          allocation by spilling some allocnos and assigning the freed
 251          hard registers to other allocnos if it decreases the overall
 252          allocation cost.
 253
 254        * After allocno assigning in the region, IRA modifies the hard
 255          register and memory costs for the corresponding allocnos in
 256          the subregions to reflect the cost of possible loads, stores,
 257          or moves on the border of the region and its subregions.
 258          When default regional allocation algorithm is used
 259          (-fira-algorithm=mixed), IRA just propagates the assignment
 260          for allocnos if the register pressure in the region for the
 261          corresponding pressure class is less than number of available
 262          hard registers for given pressure class.
 263
 264      o Spill/restore code moving.  When IRA performs an allocation
 265        by traversing regions in top-down order, it does not know what
 266        happens below in the region tree.  Therefore, sometimes IRA
 267        misses opportunities to perform a better allocation.  A simple
 268        optimization tries to improve allocation in a region having
 269        subregions and containing in another region.  If the
 270        corresponding allocnos in the subregion are spilled, it spills
 271        the region allocno if it is profitable.  The optimization
 272        implements a simple iterative algorithm performing profitable
 273        transformations while they are still possible.  It is fast in
 274        practice, so there is no real need for a better time complexity
 275        algorithm.
 276
 277      o Code change.  After coloring, two allocnos representing the
 278        same pseudo-register outside and inside a region respectively
 279        may be assigned to different locations (hard-registers or
 280        memory).  In this case IRA creates and uses a new
 281        pseudo-register inside the region and adds code to move allocno
 282        values on the region's borders.  This is done during top-down
 283        traversal of the regions (file ira-emit.c).  In some
 284        complicated cases IRA can create a new allocno to move allocno
 285        values (e.g. when a swap of values stored in two hard-registers
 286        is needed).  At this stage, the new allocno is marked as
 287        spilled.  IRA still creates the pseudo-register and the moves
 288        on the region borders even when both allocnos were assigned to
 289        the same hard-register.  If the reload pass spills a
 290        pseudo-register for some reason, the effect will be smaller
 291        because another allocno will still be in the hard-register.  In
 292        most cases, this is better then spilling both allocnos.  If
 293        reload does not change the allocation for the two
 294        pseudo-registers, the trivial move will be removed by
 295        post-reload optimizations.  IRA does not generate moves for
 296        allocnos assigned to the same hard register when the default
 297        regional allocation algorithm is used and the register pressure
 298        in the region for the corresponding pressure class is less than
 299        number of available hard registers for given pressure class.
 300        IRA also does some optimizations to remove redundant stores and
 301        to reduce code duplication on the region borders.
 302
 303      o Flattening internal representation.  After changing code, IRA
 304        transforms its internal representation for several regions into
 305        one region representation (file ira-build.c).  This process is
 306        called IR flattening.  Such process is more complicated than IR
 307        rebuilding would be, but is much faster.
 308
 309      o After IR flattening, IRA tries to assign hard registers to all
 310        spilled allocnos.  This is implemented by a simple and fast
 311        priority coloring algorithm (see function
 312        ira_reassign_conflict_allocnos::ira-color.c).  Here new allocnos
 313        created during the code change pass can be assigned to hard
 314        registers.
 315
 316      o At the end IRA calls the reload pass.  The reload pass
 317        communicates with IRA through several functions in file
 318        ira-color.c to improve its decisions in
 319
 320        * sharing stack slots for the spilled pseudos based on IRA info
 321          about pseudo-register conflicts.
 322
 323        * reassigning hard-registers to all spilled pseudos at the end
 324          of each reload iteration.
 325
 326        * choosing a better hard-register to spill based on IRA info
 327          about pseudo-register live ranges and the register pressure
 328          in places where the pseudo-register lives.
 329
 330    IRA uses a lot of data representing the target processors.  These
 331    data are initialized in file ira.c.
 332
 333    If function has no loops (or the loops are ignored when
 334    -fira-algorithm=CB is used), we have classic Chaitin-Briggs
 335    coloring (only instead of separate pass of coalescing, we use hard
 336    register preferencing).  In such case, IRA works much faster
 337    because many things are not made (like IR flattening, the
 338    spill/restore optimization, and the code change).
 339
 340    Literature is worth to read for better understanding the code:
 341
 342    o Preston Briggs, Keith D. Cooper, Linda Torczon.  Improvements to
 343      Graph Coloring Register Allocation.
 344
 345    o David Callahan, Brian Koblenz.  Register allocation via
 346      hierarchical graph coloring.
 347
 348    o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
 349      Coloring Register Allocation: A Study of the Chaitin-Briggs and
 350      Callahan-Koblenz Algorithms.
 351
 352    o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
 353      Register Allocation Based on Graph Fusion.
 354
 355    o Michael D. Smith and Glenn Holloway.  Graph-Coloring Register
 356      Allocation for Irregular Architectures
 357
 358    o Vladimir Makarov. The Integrated Register Allocator for GCC.
 359
 360    o Vladimir Makarov.  The top-down register allocator for irregular
 361      register file architectures.
 362
 363 */
 364
 365
 366 #include "config.h"
 367 #include "system.h"
 368 #include "coretypes.h"
 369 #include "tm.h"
 370 #include "regs.h"
 371 #include "tree.h"
 372 #include "rtl.h"
 373 #include "tm_p.h"
 374 #include "target.h"
 375 #include "flags.h"
 376 #include "obstack.h"
 377 #include "bitmap.h"
 378 #include "hard-reg-set.h"
 379 #include "predict.h"
 380 #include "vec.h"
 381 #include "hashtab.h"
 382 #include "hash-set.h"
 383 #include "machmode.h"
 384 #include "input.h"
 385 #include "function.h"
 386 #include "dominance.h"
 387 #include "cfg.h"
 388 #include "cfgrtl.h"
 389 #include "cfgbuild.h"
 390 #include "cfgcleanup.h"
 391 #include "basic-block.h"
 392 #include "df.h"
 393 #include "expr.h"
 394 #include "recog.h"
 395 #include "params.h"
 396 #include "tree-pass.h"
 397 #include "output.h"
 398 #include "except.h"
 399 #include "reload.h"
 400 #include "diagnostic-core.h"
 401 #include "ggc.h"
 402 #include "ira-int.h"
 403 #include "lra.h"
 404 #include "dce.h"
 405 #include "dbgcnt.h"
 406 #include "rtl-iter.h"
 407 #include "shrink-wrap.h"
 408
 409 struct target_ira default_target_ira;
 410 struct target_ira_int default_target_ira_int;
 411 #if SWITCHABLE_TARGET
 412 struct target_ira *this_target_ira = &default_target_ira;
 413 struct target_ira_int *this_target_ira_int = &default_target_ira_int;
 414 #endif
 415
 416 /* A modified value of flag `-fira-verbose' used internally.  */
 417 int internal_flag_ira_verbose;
 418
 419 /* Dump file of the allocator if it is not NULL.  */
 420 FILE *ira_dump_file;
 421
 422 /* The number of elements in the following array.  */
 423 int ira_spilled_reg_stack_slots_num;
 424
 425 /* The following array contains info about spilled pseudo-registers
 426    stack slots used in current function so far.  */
 427 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
 428
 429 /* Correspondingly overall cost of the allocation, overall cost before
 430    reload, cost of the allocnos assigned to hard-registers, cost of
 431    the allocnos assigned to memory, cost of loads, stores and register
 432    move insns generated for pseudo-register live range splitting (see
 433    ira-emit.c).  */
 434 int ira_overall_cost, overall_cost_before;
 435 int ira_reg_cost, ira_mem_cost;
 436 int ira_load_cost, ira_store_cost, ira_shuffle_cost;
 437 int ira_move_loops_num, ira_additional_jumps_num;
 438
 439 /* All registers that can be eliminated.  */
 440
 441 HARD_REG_SET eliminable_regset;
 442
 443 /* Value of max_reg_num () before IRA work start.  This value helps
 444    us to recognize a situation when new pseudos were created during
 445    IRA work.  */
 446 static int max_regno_before_ira;
 447
 448 /* Temporary hard reg set used for a different calculation.  */
 449 static HARD_REG_SET temp_hard_regset;
 450
 451 #define last_mode_for_init_move_cost \
 452   (this_target_ira_int->x_last_mode_for_init_move_cost)
 453 \f
 454
 455 /* The function sets up the map IRA_REG_MODE_HARD_REGSET.  */
 456 static void
 457 setup_reg_mode_hard_regset (void)
 458 {
 459   int i, m, hard_regno;
 460
 461   for (m = 0; m < NUM_MACHINE_MODES; m++)
 462     for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
 463       {
 464         CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
 465         for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
 466           if (hard_regno + i < FIRST_PSEUDO_REGISTER)
 467             SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
 468                               hard_regno + i);
 469       }
 470 }
 471
 472 \f
 473 #define no_unit_alloc_regs \
 474   (this_target_ira_int->x_no_unit_alloc_regs)
 475
 476 /* The function sets up the three arrays declared above.  */
 477 static void
 478 setup_class_hard_regs (void)
 479 {
 480   int cl, i, hard_regno, n;
 481   HARD_REG_SET processed_hard_reg_set;
 482
 483   ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
 484   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
 485     {
 486       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 487       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 488       CLEAR_HARD_REG_SET (processed_hard_reg_set);
 489       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 490         {
 491           ira_non_ordered_class_hard_regs[cl][i] = -1;
 492           ira_class_hard_reg_index[cl][i] = -1;
 493         }
 494       for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 495         {
 496 #ifdef REG_ALLOC_ORDER
 497           hard_regno = reg_alloc_order[i];
 498 #else
 499           hard_regno = i;
 500 #endif
 501           if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
 502             continue;
 503           SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
 504           if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
 505             ira_class_hard_reg_index[cl][hard_regno] = -1;
 506           else
 507             {
 508               ira_class_hard_reg_index[cl][hard_regno] = n;
 509               ira_class_hard_regs[cl][n++] = hard_regno;
 510             }
 511         }
 512       ira_class_hard_regs_num[cl] = n;
 513       for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 514         if (TEST_HARD_REG_BIT (temp_hard_regset, i))
 515           ira_non_ordered_class_hard_regs[cl][n++] = i;
 516       ira_assert (ira_class_hard_regs_num[cl] == n);
 517     }
 518 }
 519
 520 /* Set up global variables defining info about hard registers for the
 521    allocation.  These depend on USE_HARD_FRAME_P whose TRUE value means
 522    that we can use the hard frame pointer for the allocation.  */
 523 static void
 524 setup_alloc_regs (bool use_hard_frame_p)
 525 {
 526 #ifdef ADJUST_REG_ALLOC_ORDER
 527   ADJUST_REG_ALLOC_ORDER;
 528 #endif
 529   COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
 530   if (! use_hard_frame_p)
 531     SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
 532   setup_class_hard_regs ();
 533 }
 534
 535 \f
 536
 537 #define alloc_reg_class_subclasses \
 538   (this_target_ira_int->x_alloc_reg_class_subclasses)
 539
 540 /* Initialize the table of subclasses of each reg class.  */
 541 static void
 542 setup_reg_subclasses (void)
 543 {
 544   int i, j;
 545   HARD_REG_SET temp_hard_regset2;
 546
 547   for (i = 0; i < N_REG_CLASSES; i++)
 548     for (j = 0; j < N_REG_CLASSES; j++)
 549       alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
 550
 551   for (i = 0; i < N_REG_CLASSES; i++)
 552     {
 553       if (i == (int) NO_REGS)
 554         continue;
 555
 556       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
 557       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 558       if (hard_reg_set_empty_p (temp_hard_regset))
 559         continue;
 560       for (j = 0; j < N_REG_CLASSES; j++)
 561         if (i != j)
 562           {
 563             enum reg_class *p;
 564
 565             COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
 566             AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
 567             if (! hard_reg_set_subset_p (temp_hard_regset,
 568                                          temp_hard_regset2))
 569               continue;
 570             p = &alloc_reg_class_subclasses[j][0];
 571             while (*p != LIM_REG_CLASSES) p++;
 572             *p = (enum reg_class) i;
 573           }
 574     }
 575 }
 576
 577 \f
 578
 579 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST.  */
 580 static void
 581 setup_class_subset_and_memory_move_costs (void)
 582 {
 583   int cl, cl2, mode, cost;
 584   HARD_REG_SET temp_hard_regset2;
 585
 586   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
 587     ira_memory_move_cost[mode][NO_REGS][0]
 588       = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
 589   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
 590     {
 591       if (cl != (int) NO_REGS)
 592         for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
 593           {
 594             ira_max_memory_move_cost[mode][cl][0]
 595               = ira_memory_move_cost[mode][cl][0]
 596               = memory_move_cost ((machine_mode) mode,
 597                                   (reg_class_t) cl, false);
 598             ira_max_memory_move_cost[mode][cl][1]
 599               = ira_memory_move_cost[mode][cl][1]
 600               = memory_move_cost ((machine_mode) mode,
 601                                   (reg_class_t) cl, true);
 602             /* Costs for NO_REGS are used in cost calculation on the
 603                1st pass when the preferred register classes are not
 604                known yet.  In this case we take the best scenario.  */
 605             if (ira_memory_move_cost[mode][NO_REGS][0]
 606                 > ira_memory_move_cost[mode][cl][0])
 607               ira_max_memory_move_cost[mode][NO_REGS][0]
 608                 = ira_memory_move_cost[mode][NO_REGS][0]
 609                 = ira_memory_move_cost[mode][cl][0];
 610             if (ira_memory_move_cost[mode][NO_REGS][1]
 611                 > ira_memory_move_cost[mode][cl][1])
 612               ira_max_memory_move_cost[mode][NO_REGS][1]
 613                 = ira_memory_move_cost[mode][NO_REGS][1]
 614                 = ira_memory_move_cost[mode][cl][1];
 615           }
 616     }
 617   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
 618     for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
 619       {
 620         COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 621         AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 622         COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
 623         AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
 624         ira_class_subset_p[cl][cl2]
 625           = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
 626         if (! hard_reg_set_empty_p (temp_hard_regset2)
 627             && hard_reg_set_subset_p (reg_class_contents[cl2],
 628                                       reg_class_contents[cl]))
 629           for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
 630             {
 631               cost = ira_memory_move_cost[mode][cl2][0];
 632               if (cost > ira_max_memory_move_cost[mode][cl][0])
 633                 ira_max_memory_move_cost[mode][cl][0] = cost;
 634               cost = ira_memory_move_cost[mode][cl2][1];
 635               if (cost > ira_max_memory_move_cost[mode][cl][1])
 636                 ira_max_memory_move_cost[mode][cl][1] = cost;
 637             }
 638       }
 639   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
 640     for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
 641       {
 642         ira_memory_move_cost[mode][cl][0]
 643           = ira_max_memory_move_cost[mode][cl][0];
 644         ira_memory_move_cost[mode][cl][1]
 645           = ira_max_memory_move_cost[mode][cl][1];
 646       }
 647   setup_reg_subclasses ();
 648 }
 649
 650 \f
 651
 652 /* Define the following macro if allocation through malloc if
 653    preferable.  */
 654 #define IRA_NO_OBSTACK
 655
 656 #ifndef IRA_NO_OBSTACK
 657 /* Obstack used for storing all dynamic data (except bitmaps) of the
 658    IRA.  */
 659 static struct obstack ira_obstack;
 660 #endif
 661
 662 /* Obstack used for storing all bitmaps of the IRA.  */
 663 static struct bitmap_obstack ira_bitmap_obstack;
 664
 665 /* Allocate memory of size LEN for IRA data.  */
 666 void *
 667 ira_allocate (size_t len)
 668 {
 669   void *res;
 670
 671 #ifndef IRA_NO_OBSTACK
 672   res = obstack_alloc (&ira_obstack, len);
 673 #else
 674   res = xmalloc (len);
 675 #endif
 676   return res;
 677 }
 678
 679 /* Free memory ADDR allocated for IRA data.  */
 680 void
 681 ira_free (void *addr ATTRIBUTE_UNUSED)
 682 {
 683 #ifndef IRA_NO_OBSTACK
 684   /* do nothing */
 685 #else
 686   free (addr);
 687 #endif
 688 }
 689
 690
 691 /* Allocate and returns bitmap for IRA.  */
 692 bitmap
 693 ira_allocate_bitmap (void)
 694 {
 695   return BITMAP_ALLOC (&ira_bitmap_obstack);
 696 }
 697
 698 /* Free bitmap B allocated for IRA.  */
 699 void
 700 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
 701 {
 702   /* do nothing */
 703 }
 704
 705 \f
 706
 707 /* Output information about allocation of all allocnos (except for
 708    caps) into file F.  */
 709 void
 710 ira_print_disposition (FILE *f)
 711 {
 712   int i, n, max_regno;
 713   ira_allocno_t a;
 714   basic_block bb;
 715
 716   fprintf (f, "Disposition:");
 717   max_regno = max_reg_num ();
 718   for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 719     for (a = ira_regno_allocno_map[i];
 720          a != NULL;
 721          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 722       {
 723         if (n % 4 == 0)
 724           fprintf (f, "\n");
 725         n++;
 726         fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 727         if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 728           fprintf (f, "b%-3d", bb->index);
 729         else
 730           fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
 731         if (ALLOCNO_HARD_REGNO (a) >= 0)
 732           fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
 733         else
 734           fprintf (f, " mem");
 735       }
 736   fprintf (f, "\n");
 737 }
 738
 739 /* Outputs information about allocation of all allocnos into
 740    stderr.  */
 741 void
 742 ira_debug_disposition (void)
 743 {
 744   ira_print_disposition (stderr);
 745 }
 746
 747 \f
 748
 749 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
 750    register class containing stack registers or NO_REGS if there are
 751    no stack registers.  To find this class, we iterate through all
 752    register pressure classes and choose the first register pressure
 753    class containing all the stack registers and having the biggest
 754    size.  */
 755 static void
 756 setup_stack_reg_pressure_class (void)
 757 {
 758   ira_stack_reg_pressure_class = NO_REGS;
 759 #ifdef STACK_REGS
 760   {
 761     int i, best, size;
 762     enum reg_class cl;
 763     HARD_REG_SET temp_hard_regset2;
 764
 765     CLEAR_HARD_REG_SET (temp_hard_regset);
 766     for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
 767       SET_HARD_REG_BIT (temp_hard_regset, i);
 768     best = 0;
 769     for (i = 0; i < ira_pressure_classes_num; i++)
 770       {
 771         cl = ira_pressure_classes[i];
 772         COPY_HARD_REG_SET (temp_hard_regset2, temp_hard_regset);
 773         AND_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
 774         size = hard_reg_set_size (temp_hard_regset2);
 775         if (best < size)
 776           {
 777             best = size;
 778             ira_stack_reg_pressure_class = cl;
 779           }
 780       }
 781   }
 782 #endif
 783 }
 784
 785 /* Find pressure classes which are register classes for which we
 786    calculate register pressure in IRA, register pressure sensitive
 787    insn scheduling, and register pressure sensitive loop invariant
 788    motion.
 789
 790    To make register pressure calculation easy, we always use
 791    non-intersected register pressure classes.  A move of hard
 792    registers from one register pressure class is not more expensive
 793    than load and store of the hard registers.  Most likely an allocno
 794    class will be a subset of a register pressure class and in many
 795    cases a register pressure class.  That makes usage of register
 796    pressure classes a good approximation to find a high register
 797    pressure.  */
 798 static void
 799 setup_pressure_classes (void)
 800 {
 801   int cost, i, n, curr;
 802   int cl, cl2;
 803   enum reg_class pressure_classes[N_REG_CLASSES];
 804   int m;
 805   HARD_REG_SET temp_hard_regset2;
 806   bool insert_p;
 807
 808   n = 0;
 809   for (cl = 0; cl < N_REG_CLASSES; cl++)
 810     {
 811       if (ira_class_hard_regs_num[cl] == 0)
 812         continue;
 813       if (ira_class_hard_regs_num[cl] != 1
 814           /* A register class without subclasses may contain a few
 815              hard registers and movement between them is costly
 816              (e.g. SPARC FPCC registers).  We still should consider it
 817              as a candidate for a pressure class.  */
 818           && alloc_reg_class_subclasses[cl][0] < cl)
 819         {
 820           /* Check that the moves between any hard registers of the
 821              current class are not more expensive for a legal mode
 822              than load/store of the hard registers of the current
 823              class.  Such class is a potential candidate to be a
 824              register pressure class.  */
 825           for (m = 0; m < NUM_MACHINE_MODES; m++)
 826             {
 827               COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 828               AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 829               AND_COMPL_HARD_REG_SET (temp_hard_regset,
 830                                       ira_prohibited_class_mode_regs[cl][m]);
 831               if (hard_reg_set_empty_p (temp_hard_regset))
 832                 continue;
 833               ira_init_register_move_cost_if_necessary ((machine_mode) m);
 834               cost = ira_register_move_cost[m][cl][cl];
 835               if (cost <= ira_max_memory_move_cost[m][cl][1]
 836                   || cost <= ira_max_memory_move_cost[m][cl][0])
 837                 break;
 838             }
 839           if (m >= NUM_MACHINE_MODES)
 840             continue;
 841         }
 842       curr = 0;
 843       insert_p = true;
 844       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 845       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 846       /* Remove so far added pressure classes which are subset of the
 847          current candidate class.  Prefer GENERAL_REGS as a pressure
 848          register class to another class containing the same
 849          allocatable hard registers.  We do this because machine
 850          dependent cost hooks might give wrong costs for the latter
 851          class but always give the right cost for the former class
 852          (GENERAL_REGS).  */
 853       for (i = 0; i < n; i++)
 854         {
 855           cl2 = pressure_classes[i];
 856           COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
 857           AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
 858           if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
 859               && (! hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2)
 860                   || cl2 == (int) GENERAL_REGS))
 861             {
 862               pressure_classes[curr++] = (enum reg_class) cl2;
 863               insert_p = false;
 864               continue;
 865             }
 866           if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)
 867               && (! hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset)
 868                   || cl == (int) GENERAL_REGS))
 869             continue;
 870           if (hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset))
 871             insert_p = false;
 872           pressure_classes[curr++] = (enum reg_class) cl2;
 873         }
 874       /* If the current candidate is a subset of a so far added
 875          pressure class, don't add it to the list of the pressure
 876          classes.  */
 877       if (insert_p)
 878         pressure_classes[curr++] = (enum reg_class) cl;
 879       n = curr;
 880     }
 881 #ifdef ENABLE_IRA_CHECKING
 882   {
 883     HARD_REG_SET ignore_hard_regs;
 884
 885     /* Check pressure classes correctness: here we check that hard
 886        registers from all register pressure classes contains all hard
 887        registers available for the allocation.  */
 888     CLEAR_HARD_REG_SET (temp_hard_regset);
 889     CLEAR_HARD_REG_SET (temp_hard_regset2);
 890     COPY_HARD_REG_SET (ignore_hard_regs, no_unit_alloc_regs);
 891     for (cl = 0; cl < LIM_REG_CLASSES; cl++)
 892       {
 893         /* For some targets (like MIPS with MD_REGS), there are some
 894            classes with hard registers available for allocation but
 895            not able to hold value of any mode.  */
 896         for (m = 0; m < NUM_MACHINE_MODES; m++)
 897           if (contains_reg_of_mode[cl][m])
 898             break;
 899         if (m >= NUM_MACHINE_MODES)
 900           {
 901             IOR_HARD_REG_SET (ignore_hard_regs, reg_class_contents[cl]);
 902             continue;
 903           }
 904         for (i = 0; i < n; i++)
 905           if ((int) pressure_classes[i] == cl)
 906             break;
 907         IOR_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
 908         if (i < n)
 909           IOR_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 910       }
 911     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 912       /* Some targets (like SPARC with ICC reg) have allocatable regs
 913          for which no reg class is defined.  */
 914       if (REGNO_REG_CLASS (i) == NO_REGS)
 915         SET_HARD_REG_BIT (ignore_hard_regs, i);
 916     AND_COMPL_HARD_REG_SET (temp_hard_regset, ignore_hard_regs);
 917     AND_COMPL_HARD_REG_SET (temp_hard_regset2, ignore_hard_regs);
 918     ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
 919   }
 920 #endif
 921   ira_pressure_classes_num = 0;
 922   for (i = 0; i < n; i++)
 923     {
 924       cl = (int) pressure_classes[i];
 925       ira_reg_pressure_class_p[cl] = true;
 926       ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
 927     }
 928   setup_stack_reg_pressure_class ();
 929 }
 930
 931 /* Set up IRA_UNIFORM_CLASS_P.  Uniform class is a register class
 932    whose register move cost between any registers of the class is the
 933    same as for all its subclasses.  We use the data to speed up the
 934    2nd pass of calculations of allocno costs.  */
 935 static void
 936 setup_uniform_class_p (void)
 937 {
 938   int i, cl, cl2, m;
 939
 940   for (cl = 0; cl < N_REG_CLASSES; cl++)
 941     {
 942       ira_uniform_class_p[cl] = false;
 943       if (ira_class_hard_regs_num[cl] == 0)
 944         continue;
 945       /* We can not use alloc_reg_class_subclasses here because move
 946          cost hooks does not take into account that some registers are
 947          unavailable for the subtarget.  E.g. for i686, INT_SSE_REGS
 948          is element of alloc_reg_class_subclasses for GENERAL_REGS
 949          because SSE regs are unavailable.  */
 950       for (i = 0; (cl2 = reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; i++)
 951         {
 952           if (ira_class_hard_regs_num[cl2] == 0)
 953             continue;
 954           for (m = 0; m < NUM_MACHINE_MODES; m++)
 955             if (contains_reg_of_mode[cl][m] && contains_reg_of_mode[cl2][m])
 956               {
 957                 ira_init_register_move_cost_if_necessary ((machine_mode) m);
 958                 if (ira_register_move_cost[m][cl][cl]
 959                     != ira_register_move_cost[m][cl2][cl2])
 960                   break;
 961               }
 962           if (m < NUM_MACHINE_MODES)
 963             break;
 964         }
 965       if (cl2 == LIM_REG_CLASSES)
 966         ira_uniform_class_p[cl] = true;
 967     }
 968 }
 969
 970 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
 971    IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
 972
 973    Target may have many subtargets and not all target hard registers can
 974    be used for allocation, e.g. x86 port in 32-bit mode can not use
 975    hard registers introduced in x86-64 like r8-r15).  Some classes
 976    might have the same allocatable hard registers, e.g.  INDEX_REGS
 977    and GENERAL_REGS in x86 port in 32-bit mode.  To decrease different
 978    calculations efforts we introduce allocno classes which contain
 979    unique non-empty sets of allocatable hard-registers.
 980
 981    Pseudo class cost calculation in ira-costs.c is very expensive.
 982    Therefore we are trying to decrease number of classes involved in
 983    such calculation.  Register classes used in the cost calculation
 984    are called important classes.  They are allocno classes and other
 985    non-empty classes whose allocatable hard register sets are inside
 986    of an allocno class hard register set.  From the first sight, it
 987    looks like that they are just allocno classes.  It is not true.  In
 988    example of x86-port in 32-bit mode, allocno classes will contain
 989    GENERAL_REGS but not LEGACY_REGS (because allocatable hard
 990    registers are the same for the both classes).  The important
 991    classes will contain GENERAL_REGS and LEGACY_REGS.  It is done
 992    because a machine description insn constraint may refers for
 993    LEGACY_REGS and code in ira-costs.c is mostly base on investigation
 994    of the insn constraints.  */
 995 static void
 996 setup_allocno_and_important_classes (void)
 997 {
 998   int i, j, n, cl;
 999   bool set_p;
1000   HARD_REG_SET temp_hard_regset2;
1001   static enum reg_class classes[LIM_REG_CLASSES + 1];
1002
1003   n = 0;
1004   /* Collect classes which contain unique sets of allocatable hard
1005      registers.  Prefer GENERAL_REGS to other classes containing the
1006      same set of hard registers.  */
1007   for (i = 0; i < LIM_REG_CLASSES; i++)
1008     {
1009       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
1010       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1011       for (j = 0; j < n; j++)
1012         {
1013           cl = classes[j];
1014           COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
1015           AND_COMPL_HARD_REG_SET (temp_hard_regset2,
1016                                   no_unit_alloc_regs);
1017           if (hard_reg_set_equal_p (temp_hard_regset,
1018                                     temp_hard_regset2))
1019             break;
1020         }
1021       if (j >= n)
1022         classes[n++] = (enum reg_class) i;
1023       else if (i == GENERAL_REGS)
1024         /* Prefer general regs.  For i386 example, it means that
1025            we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1026            (all of them consists of the same available hard
1027            registers).  */
1028         classes[j] = (enum reg_class) i;
1029     }
1030   classes[n] = LIM_REG_CLASSES;
1031
1032   /* Set up classes which can be used for allocnos as classes
1033      containing non-empty unique sets of allocatable hard
1034      registers.  */
1035   ira_allocno_classes_num = 0;
1036   for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
1037     if (ira_class_hard_regs_num[cl] > 0)
1038       ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
1039   ira_important_classes_num = 0;
1040   /* Add non-allocno classes containing to non-empty set of
1041      allocatable hard regs.  */
1042   for (cl = 0; cl < N_REG_CLASSES; cl++)
1043     if (ira_class_hard_regs_num[cl] > 0)
1044       {
1045         COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1046         AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1047         set_p = false;
1048         for (j = 0; j < ira_allocno_classes_num; j++)
1049           {
1050             COPY_HARD_REG_SET (temp_hard_regset2,
1051                                reg_class_contents[ira_allocno_classes[j]]);
1052             AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
1053             if ((enum reg_class) cl == ira_allocno_classes[j])
1054               break;
1055             else if (hard_reg_set_subset_p (temp_hard_regset,
1056                                             temp_hard_regset2))
1057               set_p = true;
1058           }
1059         if (set_p && j >= ira_allocno_classes_num)
1060           ira_important_classes[ira_important_classes_num++]
1061             = (enum reg_class) cl;
1062       }
1063   /* Now add allocno classes to the important classes.  */
1064   for (j = 0; j < ira_allocno_classes_num; j++)
1065     ira_important_classes[ira_important_classes_num++]
1066       = ira_allocno_classes[j];
1067   for (cl = 0; cl < N_REG_CLASSES; cl++)
1068     {
1069       ira_reg_allocno_class_p[cl] = false;
1070       ira_reg_pressure_class_p[cl] = false;
1071     }
1072   for (j = 0; j < ira_allocno_classes_num; j++)
1073     ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1074   setup_pressure_classes ();
1075   setup_uniform_class_p ();
1076 }
1077
1078 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1079    given by array CLASSES of length CLASSES_NUM.  The function is used
1080    make translation any reg class to an allocno class or to an
1081    pressure class.  This translation is necessary for some
1082    calculations when we can use only allocno or pressure classes and
1083    such translation represents an approximate representation of all
1084    classes.
1085
1086    The translation in case when allocatable hard register set of a
1087    given class is subset of allocatable hard register set of a class
1088    in CLASSES is pretty simple.  We use smallest classes from CLASSES
1089    containing a given class.  If allocatable hard register set of a
1090    given class is not a subset of any corresponding set of a class
1091    from CLASSES, we use the cheapest (with load/store point of view)
1092    class from CLASSES whose set intersects with given class set.  */
1093 static void
1094 setup_class_translate_array (enum reg_class *class_translate,
1095                              int classes_num, enum reg_class *classes)
1096 {
1097   int cl, mode;
1098   enum reg_class aclass, best_class, *cl_ptr;
1099   int i, cost, min_cost, best_cost;
1100
1101   for (cl = 0; cl < N_REG_CLASSES; cl++)
1102     class_translate[cl] = NO_REGS;
1103
1104   for (i = 0; i < classes_num; i++)
1105     {
1106       aclass = classes[i];
1107       for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1108            (cl = *cl_ptr) != LIM_REG_CLASSES;
1109            cl_ptr++)
1110         if (class_translate[cl] == NO_REGS)
1111           class_translate[cl] = aclass;
1112       class_translate[aclass] = aclass;
1113     }
1114   /* For classes which are not fully covered by one of given classes
1115      (in other words covered by more one given class), use the
1116      cheapest class.  */
1117   for (cl = 0; cl < N_REG_CLASSES; cl++)
1118     {
1119       if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1120         continue;
1121       best_class = NO_REGS;
1122       best_cost = INT_MAX;
1123       for (i = 0; i < classes_num; i++)
1124         {
1125           aclass = classes[i];
1126           COPY_HARD_REG_SET (temp_hard_regset,
1127                              reg_class_contents[aclass]);
1128           AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1129           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1130           if (! hard_reg_set_empty_p (temp_hard_regset))
1131             {
1132               min_cost = INT_MAX;
1133               for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1134                 {
1135                   cost = (ira_memory_move_cost[mode][aclass][0]
1136                           + ira_memory_move_cost[mode][aclass][1]);
1137                   if (min_cost > cost)
1138                     min_cost = cost;
1139                 }
1140               if (best_class == NO_REGS || best_cost > min_cost)
1141                 {
1142                   best_class = aclass;
1143                   best_cost = min_cost;
1144                 }
1145             }
1146         }
1147       class_translate[cl] = best_class;
1148     }
1149 }
1150
1151 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1152    IRA_PRESSURE_CLASS_TRANSLATE.  */
1153 static void
1154 setup_class_translate (void)
1155 {
1156   setup_class_translate_array (ira_allocno_class_translate,
1157                                ira_allocno_classes_num, ira_allocno_classes);
1158   setup_class_translate_array (ira_pressure_class_translate,
1159                                ira_pressure_classes_num, ira_pressure_classes);
1160 }
1161
1162 /* Order numbers of allocno classes in original target allocno class
1163    array, -1 for non-allocno classes.  */
1164 static int allocno_class_order[N_REG_CLASSES];
1165
1166 /* The function used to sort the important classes.  */
1167 static int
1168 comp_reg_classes_func (const void *v1p, const void *v2p)
1169 {
1170   enum reg_class cl1 = *(const enum reg_class *) v1p;
1171   enum reg_class cl2 = *(const enum reg_class *) v2p;
1172   enum reg_class tcl1, tcl2;
1173   int diff;
1174
1175   tcl1 = ira_allocno_class_translate[cl1];
1176   tcl2 = ira_allocno_class_translate[cl2];
1177   if (tcl1 != NO_REGS && tcl2 != NO_REGS
1178       && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1179     return diff;
1180   return (int) cl1 - (int) cl2;
1181 }
1182
1183 /* For correct work of function setup_reg_class_relation we need to
1184    reorder important classes according to the order of their allocno
1185    classes.  It places important classes containing the same
1186    allocatable hard register set adjacent to each other and allocno
1187    class with the allocatable hard register set right after the other
1188    important classes with the same set.
1189
1190    In example from comments of function
1191    setup_allocno_and_important_classes, it places LEGACY_REGS and
1192    GENERAL_REGS close to each other and GENERAL_REGS is after
1193    LEGACY_REGS.  */
1194 static void
1195 reorder_important_classes (void)
1196 {
1197   int i;
1198
1199   for (i = 0; i < N_REG_CLASSES; i++)
1200     allocno_class_order[i] = -1;
1201   for (i = 0; i < ira_allocno_classes_num; i++)
1202     allocno_class_order[ira_allocno_classes[i]] = i;
1203   qsort (ira_important_classes, ira_important_classes_num,
1204          sizeof (enum reg_class), comp_reg_classes_func);
1205   for (i = 0; i < ira_important_classes_num; i++)
1206     ira_important_class_nums[ira_important_classes[i]] = i;
1207 }
1208
1209 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1210    IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1211    IRA_REG_CLASSES_INTERSECT_P.  For the meaning of the relations,
1212    please see corresponding comments in ira-int.h.  */
1213 static void
1214 setup_reg_class_relations (void)
1215 {
1216   int i, cl1, cl2, cl3;
1217   HARD_REG_SET intersection_set, union_set, temp_set2;
1218   bool important_class_p[N_REG_CLASSES];
1219
1220   memset (important_class_p, 0, sizeof (important_class_p));
1221   for (i = 0; i < ira_important_classes_num; i++)
1222     important_class_p[ira_important_classes[i]] = true;
1223   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1224     {
1225       ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1226       for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1227         {
1228           ira_reg_classes_intersect_p[cl1][cl2] = false;
1229           ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1230           ira_reg_class_subset[cl1][cl2] = NO_REGS;
1231           COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1232           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1233           COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
1234           AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1235           if (hard_reg_set_empty_p (temp_hard_regset)
1236               && hard_reg_set_empty_p (temp_set2))
1237             {
1238               /* The both classes have no allocatable hard registers
1239                  -- take all class hard registers into account and use
1240                  reg_class_subunion and reg_class_superunion.  */
1241               for (i = 0;; i++)
1242                 {
1243                   cl3 = reg_class_subclasses[cl1][i];
1244                   if (cl3 == LIM_REG_CLASSES)
1245                     break;
1246                   if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1247                                           (enum reg_class) cl3))
1248                     ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1249                 }
1250               ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1251               ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1252               continue;
1253             }
1254           ira_reg_classes_intersect_p[cl1][cl2]
1255             = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
1256           if (important_class_p[cl1] && important_class_p[cl2]
1257               && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
1258             {
1259               /* CL1 and CL2 are important classes and CL1 allocatable
1260                  hard register set is inside of CL2 allocatable hard
1261                  registers -- make CL1 a superset of CL2.  */
1262               enum reg_class *p;
1263
1264               p = &ira_reg_class_super_classes[cl1][0];
1265               while (*p != LIM_REG_CLASSES)
1266                 p++;
1267               *p++ = (enum reg_class) cl2;
1268               *p = LIM_REG_CLASSES;
1269             }
1270           ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1271           ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1272           COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
1273           AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
1274           AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
1275           COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
1276           IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
1277           AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
1278           for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1279             {
1280               COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
1281               AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1282               if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
1283                 {
1284                   /* CL3 allocatable hard register set is inside of
1285                      intersection of allocatable hard register sets
1286                      of CL1 and CL2.  */
1287                   if (important_class_p[cl3])
1288                     {
1289                       COPY_HARD_REG_SET
1290                         (temp_set2,
1291                          reg_class_contents
1292                          [(int) ira_reg_class_intersect[cl1][cl2]]);
1293                       AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1294                       if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1295                           /* If the allocatable hard register sets are
1296                              the same, prefer GENERAL_REGS or the
1297                              smallest class for debugging
1298                              purposes.  */
1299                           || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1300                               && (cl3 == GENERAL_REGS
1301                                   || ((ira_reg_class_intersect[cl1][cl2]
1302                                        != GENERAL_REGS)
1303                                       && hard_reg_set_subset_p
1304                                          (reg_class_contents[cl3],
1305                                           reg_class_contents
1306                                           [(int)
1307                                            ira_reg_class_intersect[cl1][cl2]])))))
1308                         ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1309                     }
1310                   COPY_HARD_REG_SET
1311                     (temp_set2,
1312                      reg_class_contents[(int) ira_reg_class_subset[cl1][cl2]]);
1313                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1314                   if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1315                       /* Ignore unavailable hard registers and prefer
1316                          smallest class for debugging purposes.  */
1317                       || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1318                           && hard_reg_set_subset_p
1319                              (reg_class_contents[cl3],
1320                               reg_class_contents
1321                               [(int) ira_reg_class_subset[cl1][cl2]])))
1322                     ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3;
1323                 }
1324               if (important_class_p[cl3]
1325                   && hard_reg_set_subset_p (temp_hard_regset, union_set))
1326                 {
1327                   /* CL3 allocatable hard register set is inside of
1328                      union of allocatable hard register sets of CL1
1329                      and CL2.  */
1330                   COPY_HARD_REG_SET
1331                     (temp_set2,
1332                      reg_class_contents[(int) ira_reg_class_subunion[cl1][cl2]]);
1333                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1334                   if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1335                       || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
1336
1337                           && (! hard_reg_set_equal_p (temp_set2,
1338                                                       temp_hard_regset)
1339                               || cl3 == GENERAL_REGS
1340                               /* If the allocatable hard register sets are the
1341                                  same, prefer GENERAL_REGS or the smallest
1342                                  class for debugging purposes.  */
1343                               || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1344                                   && hard_reg_set_subset_p
1345                                      (reg_class_contents[cl3],
1346                                       reg_class_contents
1347                                       [(int) ira_reg_class_subunion[cl1][cl2]])))))
1348                     ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1349                 }
1350               if (hard_reg_set_subset_p (union_set, temp_hard_regset))
1351                 {
1352                   /* CL3 allocatable hard register set contains union
1353                      of allocatable hard register sets of CL1 and
1354                      CL2.  */
1355                   COPY_HARD_REG_SET
1356                     (temp_set2,
1357                      reg_class_contents[(int) ira_reg_class_superunion[cl1][cl2]]);
1358                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1359                   if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1360                       || (hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1361
1362                           && (! hard_reg_set_equal_p (temp_set2,
1363                                                       temp_hard_regset)
1364                               || cl3 == GENERAL_REGS
1365                               /* If the allocatable hard register sets are the
1366                                  same, prefer GENERAL_REGS or the smallest
1367                                  class for debugging purposes.  */
1368                               || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1369                                   && hard_reg_set_subset_p
1370                                      (reg_class_contents[cl3],
1371                                       reg_class_contents
1372                                       [(int) ira_reg_class_superunion[cl1][cl2]])))))
1373                     ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1374                 }
1375             }
1376         }
1377     }
1378 }
1379
1380 /* Output all uniform and important classes into file F.  */
1381 static void
1382 print_unform_and_important_classes (FILE *f)
1383 {
1384   static const char *const reg_class_names[] = REG_CLASS_NAMES;
1385   int i, cl;
1386
1387   fprintf (f, "Uniform classes:\n");
1388   for (cl = 0; cl < N_REG_CLASSES; cl++)
1389     if (ira_uniform_class_p[cl])
1390       fprintf (f, " %s", reg_class_names[cl]);
1391   fprintf (f, "\nImportant classes:\n");
1392   for (i = 0; i < ira_important_classes_num; i++)
1393     fprintf (f, " %s", reg_class_names[ira_important_classes[i]]);
1394   fprintf (f, "\n");
1395 }
1396
1397 /* Output all possible allocno or pressure classes and their
1398    translation map into file F.  */
1399 static void
1400 print_translated_classes (FILE *f, bool pressure_p)
1401 {
1402   int classes_num = (pressure_p
1403                      ? ira_pressure_classes_num : ira_allocno_classes_num);
1404   enum reg_class *classes = (pressure_p
1405                              ? ira_pressure_classes : ira_allocno_classes);
1406   enum reg_class *class_translate = (pressure_p
1407                                      ? ira_pressure_class_translate
1408                                      : ira_allocno_class_translate);
1409   static const char *const reg_class_names[] = REG_CLASS_NAMES;
1410   int i;
1411
1412   fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1413   for (i = 0; i < classes_num; i++)
1414     fprintf (f, " %s", reg_class_names[classes[i]]);
1415   fprintf (f, "\nClass translation:\n");
1416   for (i = 0; i < N_REG_CLASSES; i++)
1417     fprintf (f, " %s -> %s\n", reg_class_names[i],
1418              reg_class_names[class_translate[i]]);
1419 }
1420
1421 /* Output all possible allocno and translation classes and the
1422    translation maps into stderr.  */
1423 void
1424 ira_debug_allocno_classes (void)
1425 {
1426   print_unform_and_important_classes (stderr);
1427   print_translated_classes (stderr, false);
1428   print_translated_classes (stderr, true);
1429 }
1430
1431 /* Set up different arrays concerning class subsets, allocno and
1432    important classes.  */
1433 static void
1434 find_reg_classes (void)
1435 {
1436   setup_allocno_and_important_classes ();
1437   setup_class_translate ();
1438   reorder_important_classes ();
1439   setup_reg_class_relations ();
1440 }
1441
1442 \f
1443
1444 /* Set up the array above.  */
1445 static void
1446 setup_hard_regno_aclass (void)
1447 {
1448   int i;
1449
1450   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1451     {
1452 #if 1
1453       ira_hard_regno_allocno_class[i]
1454         = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i)
1455            ? NO_REGS
1456            : ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1457 #else
1458       int j;
1459       enum reg_class cl;
1460       ira_hard_regno_allocno_class[i] = NO_REGS;
1461       for (j = 0; j < ira_allocno_classes_num; j++)
1462         {
1463           cl = ira_allocno_classes[j];
1464           if (ira_class_hard_reg_index[cl][i] >= 0)
1465             {
1466               ira_hard_regno_allocno_class[i] = cl;
1467               break;
1468             }
1469         }
1470 #endif
1471     }
1472 }
1473
1474 \f
1475
1476 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps.  */
1477 static void
1478 setup_reg_class_nregs (void)
1479 {
1480   int i, cl, cl2, m;
1481
1482   for (m = 0; m < MAX_MACHINE_MODE; m++)
1483     {
1484       for (cl = 0; cl < N_REG_CLASSES; cl++)
1485         ira_reg_class_max_nregs[cl][m]
1486           = ira_reg_class_min_nregs[cl][m]
1487           = targetm.class_max_nregs ((reg_class_t) cl, (machine_mode) m);
1488       for (cl = 0; cl < N_REG_CLASSES; cl++)
1489         for (i = 0;
1490              (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1491              i++)
1492           if (ira_reg_class_min_nregs[cl2][m]
1493               < ira_reg_class_min_nregs[cl][m])
1494             ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1495     }
1496 }
1497
1498 \f
1499
1500 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1501    This function is called once IRA_CLASS_HARD_REGS has been initialized.  */
1502 static void
1503 setup_prohibited_class_mode_regs (void)
1504 {
1505   int j, k, hard_regno, cl, last_hard_regno, count;
1506
1507   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1508     {
1509       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1510       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1511       for (j = 0; j < NUM_MACHINE_MODES; j++)
1512         {
1513           count = 0;
1514           last_hard_regno = -1;
1515           CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1516           for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1517             {
1518               hard_regno = ira_class_hard_regs[cl][k];
1519               if (! HARD_REGNO_MODE_OK (hard_regno, (machine_mode) j))
1520                 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1521                                   hard_regno);
1522               else if (in_hard_reg_set_p (temp_hard_regset,
1523                                           (machine_mode) j, hard_regno))
1524                 {
1525                   last_hard_regno = hard_regno;
1526                   count++;
1527                 }
1528             }
1529           ira_class_singleton[cl][j] = (count == 1 ? last_hard_regno : -1);
1530         }
1531     }
1532 }
1533
1534 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1535    spanning from one register pressure class to another one.  It is
1536    called after defining the pressure classes.  */
1537 static void
1538 clarify_prohibited_class_mode_regs (void)
1539 {
1540   int j, k, hard_regno, cl, pclass, nregs;
1541
1542   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1543     for (j = 0; j < NUM_MACHINE_MODES; j++)
1544       {
1545         CLEAR_HARD_REG_SET (ira_useful_class_mode_regs[cl][j]);
1546         for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1547           {
1548             hard_regno = ira_class_hard_regs[cl][k];
1549             if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno))
1550               continue;
1551             nregs = hard_regno_nregs[hard_regno][j];
1552             if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1553               {
1554                 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1555                                   hard_regno);
1556                  continue;
1557               }
1558             pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1559             for (nregs-- ;nregs >= 0; nregs--)
1560               if (((enum reg_class) pclass
1561                    != ira_pressure_class_translate[REGNO_REG_CLASS
1562                                                    (hard_regno + nregs)]))
1563                 {
1564                   SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1565                                     hard_regno);
1566                   break;
1567                 }
1568             if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1569                                     hard_regno))
1570               add_to_hard_reg_set (&ira_useful_class_mode_regs[cl][j],
1571                                    (machine_mode) j, hard_regno);
1572           }
1573       }
1574 }
1575 \f
1576 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1577    and IRA_MAY_MOVE_OUT_COST for MODE.  */
1578 void
1579 ira_init_register_move_cost (machine_mode mode)
1580 {
1581   static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
1582   bool all_match = true;
1583   unsigned int cl1, cl2;
1584
1585   ira_assert (ira_register_move_cost[mode] == NULL
1586               && ira_may_move_in_cost[mode] == NULL
1587               && ira_may_move_out_cost[mode] == NULL);
1588   ira_assert (have_regs_of_mode[mode]);
1589   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1590     for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1591       {
1592         int cost;
1593         if (!contains_reg_of_mode[cl1][mode]
1594             || !contains_reg_of_mode[cl2][mode])
1595           {
1596             if ((ira_reg_class_max_nregs[cl1][mode]
1597                  > ira_class_hard_regs_num[cl1])
1598                 || (ira_reg_class_max_nregs[cl2][mode]
1599                     > ira_class_hard_regs_num[cl2]))
1600               cost = 65535;
1601             else
1602               cost = (ira_memory_move_cost[mode][cl1][0]
1603                       + ira_memory_move_cost[mode][cl2][1]) * 2;
1604           }
1605         else
1606           {
1607             cost = register_move_cost (mode, (enum reg_class) cl1,
1608                                        (enum reg_class) cl2);
1609             ira_assert (cost < 65535);
1610           }
1611         all_match &= (last_move_cost[cl1][cl2] == cost);
1612         last_move_cost[cl1][cl2] = cost;
1613       }
1614   if (all_match && last_mode_for_init_move_cost != -1)
1615     {
1616       ira_register_move_cost[mode]
1617         = ira_register_move_cost[last_mode_for_init_move_cost];
1618       ira_may_move_in_cost[mode]
1619         = ira_may_move_in_cost[last_mode_for_init_move_cost];
1620       ira_may_move_out_cost[mode]
1621         = ira_may_move_out_cost[last_mode_for_init_move_cost];
1622       return;
1623     }
1624   last_mode_for_init_move_cost = mode;
1625   ira_register_move_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1626   ira_may_move_in_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1627   ira_may_move_out_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1628   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1629     for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1630       {
1631         int cost;
1632         enum reg_class *p1, *p2;
1633
1634         if (last_move_cost[cl1][cl2] == 65535)
1635           {
1636             ira_register_move_cost[mode][cl1][cl2] = 65535;
1637             ira_may_move_in_cost[mode][cl1][cl2] = 65535;
1638             ira_may_move_out_cost[mode][cl1][cl2] = 65535;
1639           }
1640         else
1641           {
1642             cost = last_move_cost[cl1][cl2];
1643
1644             for (p2 = &reg_class_subclasses[cl2][0];
1645                  *p2 != LIM_REG_CLASSES; p2++)
1646               if (ira_class_hard_regs_num[*p2] > 0
1647                   && (ira_reg_class_max_nregs[*p2][mode]
1648                       <= ira_class_hard_regs_num[*p2]))
1649                 cost = MAX (cost, ira_register_move_cost[mode][cl1][*p2]);
1650
1651             for (p1 = &reg_class_subclasses[cl1][0];
1652                  *p1 != LIM_REG_CLASSES; p1++)
1653               if (ira_class_hard_regs_num[*p1] > 0
1654                   && (ira_reg_class_max_nregs[*p1][mode]
1655                       <= ira_class_hard_regs_num[*p1]))
1656                 cost = MAX (cost, ira_register_move_cost[mode][*p1][cl2]);
1657
1658             ira_assert (cost <= 65535);
1659             ira_register_move_cost[mode][cl1][cl2] = cost;
1660
1661             if (ira_class_subset_p[cl1][cl2])
1662               ira_may_move_in_cost[mode][cl1][cl2] = 0;
1663             else
1664               ira_may_move_in_cost[mode][cl1][cl2] = cost;
1665
1666             if (ira_class_subset_p[cl2][cl1])
1667               ira_may_move_out_cost[mode][cl1][cl2] = 0;
1668             else
1669               ira_may_move_out_cost[mode][cl1][cl2] = cost;
1670           }
1671       }
1672 }
1673
1674 \f
1675
1676 /* This is called once during compiler work.  It sets up
1677    different arrays whose values don't depend on the compiled
1678    function.  */
1679 void
1680 ira_init_once (void)
1681 {
1682   ira_init_costs_once ();
1683   lra_init_once ();
1684 }
1685
1686 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1687    ira_may_move_out_cost for each mode.  */
1688 void
1689 target_ira_int::free_register_move_costs (void)
1690 {
1691   int mode, i;
1692
1693   /* Reset move_cost and friends, making sure we only free shared
1694      table entries once.  */
1695   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1696     if (x_ira_register_move_cost[mode])
1697       {
1698         for (i = 0;
1699              i < mode && (x_ira_register_move_cost[i]
1700                           != x_ira_register_move_cost[mode]);
1701              i++)
1702           ;
1703         if (i == mode)
1704           {
1705             free (x_ira_register_move_cost[mode]);
1706             free (x_ira_may_move_in_cost[mode]);
1707             free (x_ira_may_move_out_cost[mode]);
1708           }
1709       }
1710   memset (x_ira_register_move_cost, 0, sizeof x_ira_register_move_cost);
1711   memset (x_ira_may_move_in_cost, 0, sizeof x_ira_may_move_in_cost);
1712   memset (x_ira_may_move_out_cost, 0, sizeof x_ira_may_move_out_cost);
1713   last_mode_for_init_move_cost = -1;
1714 }
1715
1716 target_ira_int::~target_ira_int ()
1717 {
1718   free_ira_costs ();
1719   free_register_move_costs ();
1720 }
1721
1722 /* This is called every time when register related information is
1723    changed.  */
1724 void
1725 ira_init (void)
1726 {
1727   this_target_ira_int->free_register_move_costs ();
1728   setup_reg_mode_hard_regset ();
1729   setup_alloc_regs (flag_omit_frame_pointer != 0);
1730   setup_class_subset_and_memory_move_costs ();
1731   setup_reg_class_nregs ();
1732   setup_prohibited_class_mode_regs ();
1733   find_reg_classes ();
1734   clarify_prohibited_class_mode_regs ();
1735   setup_hard_regno_aclass ();
1736   ira_init_costs ();
1737 }
1738
1739 \f
1740 #define ira_prohibited_mode_move_regs_initialized_p \
1741   (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1742
1743 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS.  */
1744 static void
1745 setup_prohibited_mode_move_regs (void)
1746 {
1747   int i, j;
1748   rtx test_reg1, test_reg2, move_pat;
1749   rtx_insn *move_insn;
1750
1751   if (ira_prohibited_mode_move_regs_initialized_p)
1752     return;
1753   ira_prohibited_mode_move_regs_initialized_p = true;
1754   test_reg1 = gen_rtx_REG (VOIDmode, 0);
1755   test_reg2 = gen_rtx_REG (VOIDmode, 0);
1756   move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2);
1757   move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, move_pat, 0, -1, 0);
1758   for (i = 0; i < NUM_MACHINE_MODES; i++)
1759     {
1760       SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1761       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1762         {
1763           if (! HARD_REGNO_MODE_OK (j, (machine_mode) i))
1764             continue;
1765           SET_REGNO_RAW (test_reg1, j);
1766           PUT_MODE (test_reg1, (machine_mode) i);
1767           SET_REGNO_RAW (test_reg2, j);
1768           PUT_MODE (test_reg2, (machine_mode) i);
1769           INSN_CODE (move_insn) = -1;
1770           recog_memoized (move_insn);
1771           if (INSN_CODE (move_insn) < 0)
1772             continue;
1773           extract_insn (move_insn);
1774           /* We don't know whether the move will be in code that is optimized
1775              for size or speed, so consider all enabled alternatives.  */
1776           if (! constrain_operands (1, get_enabled_alternatives (move_insn)))
1777             continue;
1778           CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1779         }
1780     }
1781 }
1782
1783 \f
1784
1785 /* Setup possible alternatives in ALTS for INSN.  */
1786 void
1787 ira_setup_alts (rtx_insn *insn, HARD_REG_SET &alts)
1788 {
1789   /* MAP nalt * nop -> start of constraints for given operand and
1790      alternative.  */
1791   static vec<const char *> insn_constraints;
1792   int nop, nalt;
1793   bool curr_swapped;
1794   const char *p;
1795   rtx op;
1796   int commutative = -1;
1797
1798   extract_insn (insn);
1799   alternative_mask preferred = get_preferred_alternatives (insn);
1800   CLEAR_HARD_REG_SET (alts);
1801   insn_constraints.release ();
1802   insn_constraints.safe_grow_cleared (recog_data.n_operands
1803                                       * recog_data.n_alternatives + 1);
1804   /* Check that the hard reg set is enough for holding all
1805      alternatives.  It is hard to imagine the situation when the
1806      assertion is wrong.  */
1807   ira_assert (recog_data.n_alternatives
1808               <= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
1809                             FIRST_PSEUDO_REGISTER));
1810   for (curr_swapped = false;; curr_swapped = true)
1811     {
1812       /* Calculate some data common for all alternatives to speed up the
1813          function.  */
1814       for (nop = 0; nop < recog_data.n_operands; nop++)
1815         {
1816           for (nalt = 0, p = recog_data.constraints[nop];
1817                nalt < recog_data.n_alternatives;
1818                nalt++)
1819             {
1820               insn_constraints[nop * recog_data.n_alternatives + nalt] = p;
1821               while (*p && *p != ',')
1822                 p++;
1823               if (*p)
1824                 p++;
1825             }
1826         }
1827       for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
1828         {
1829           if (!TEST_BIT (preferred, nalt)
1830               || TEST_HARD_REG_BIT (alts, nalt))
1831             continue;
1832
1833           for (nop = 0; nop < recog_data.n_operands; nop++)
1834             {
1835               int c, len;
1836
1837               op = recog_data.operand[nop];
1838               p = insn_constraints[nop * recog_data.n_alternatives + nalt];
1839               if (*p == 0 || *p == ',')
1840                 continue;
1841
1842               do
1843                 switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
1844                   {
1845                   case '#':
1846                   case ',':
1847                     c = '\0';
1848                   case '\0':
1849                     len = 0;
1850                     break;
1851
1852                   case '%':
1853                     /* We only support one commutative marker, the
1854                        first one.  We already set commutative
1855                        above.  */
1856                     if (commutative < 0)
1857                       commutative = nop;
1858                     break;
1859
1860                   case '0':  case '1':  case '2':  case '3':  case '4':
1861                   case '5':  case '6':  case '7':  case '8':  case '9':
1862                     goto op_success;
1863                     break;
1864
1865                   case 'g':
1866                     goto op_success;
1867                     break;
1868
1869                   default:
1870                     {
1871                       enum constraint_num cn = lookup_constraint (p);
1872                       switch (get_constraint_type (cn))
1873                         {
1874                         case CT_REGISTER:
1875                           if (reg_class_for_constraint (cn) != NO_REGS)
1876                             goto op_success;
1877                           break;
1878
1879                         case CT_CONST_INT:
1880                           if (CONST_INT_P (op)
1881                               && (insn_const_int_ok_for_constraint
1882                                   (INTVAL (op), cn)))
1883                             goto op_success;
1884                           break;
1885
1886                         case CT_ADDRESS:
1887                         case CT_MEMORY:
1888                           goto op_success;
1889
1890                         case CT_FIXED_FORM:
1891                           if (constraint_satisfied_p (op, cn))
1892                             goto op_success;
1893                           break;
1894                         }
1895                       break;
1896                     }
1897                   }
1898               while (p += len, c);
1899               break;
1900             op_success:
1901               ;
1902             }
1903           if (nop >= recog_data.n_operands)
1904             SET_HARD_REG_BIT (alts, nalt);
1905         }
1906       if (commutative < 0)
1907         break;
1908       if (curr_swapped)
1909         break;
1910       op = recog_data.operand[commutative];
1911       recog_data.operand[commutative] = recog_data.operand[commutative + 1];
1912       recog_data.operand[commutative + 1] = op;
1913
1914     }
1915 }
1916
1917 /* Return the number of the output non-early clobber operand which
1918    should be the same in any case as operand with number OP_NUM (or
1919    negative value if there is no such operand).  The function takes
1920    only really possible alternatives into consideration.  */
1921 int
1922 ira_get_dup_out_num (int op_num, HARD_REG_SET &alts)
1923 {
1924   int curr_alt, c, original, dup;
1925   bool ignore_p, use_commut_op_p;
1926   const char *str;
1927
1928   if (op_num < 0 || recog_data.n_alternatives == 0)
1929     return -1;
1930   /* We should find duplications only for input operands.  */
1931   if (recog_data.operand_type[op_num] != OP_IN)
1932     return -1;
1933   str = recog_data.constraints[op_num];
1934   use_commut_op_p = false;
1935   for (;;)
1936     {
1937       rtx op = recog_data.operand[op_num];
1938
1939       for (curr_alt = 0, ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt),
1940            original = -1;;)
1941         {
1942           c = *str;
1943           if (c == '\0')
1944             break;
1945           if (c == '#')
1946             ignore_p = true;
1947           else if (c == ',')
1948             {
1949               curr_alt++;
1950               ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt);
1951             }
1952           else if (! ignore_p)
1953             switch (c)
1954               {
1955               case 'g':
1956                 goto fail;
1957               default:
1958                 {
1959                   enum constraint_num cn = lookup_constraint (str);
1960                   enum reg_class cl = reg_class_for_constraint (cn);
1961                   if (cl != NO_REGS
1962                       && !targetm.class_likely_spilled_p (cl))
1963                     goto fail;
1964                   if (constraint_satisfied_p (op, cn))
1965                     goto fail;
1966                   break;
1967                 }
1968
1969               case '0': case '1': case '2': case '3': case '4':
1970               case '5': case '6': case '7': case '8': case '9':
1971                 if (original != -1 && original != c)
1972                   goto fail;
1973                 original = c;
1974                 break;
1975               }
1976           str += CONSTRAINT_LEN (c, str);
1977         }
1978       if (original == -1)
1979         goto fail;
1980       dup = -1;
1981       for (ignore_p = false, str = recog_data.constraints[original - '0'];
1982            *str != 0;
1983            str++)
1984         if (ignore_p)
1985           {
1986             if (*str == ',')
1987               ignore_p = false;
1988           }
1989         else if (*str == '#')
1990           ignore_p = true;
1991         else if (! ignore_p)
1992           {
1993             if (*str == '=')
1994               dup = original - '0';
1995             /* It is better ignore an alternative with early clobber.  */
1996             else if (*str == '&')
1997               goto fail;
1998           }
1999       if (dup >= 0)
2000         return dup;
2001     fail:
2002       if (use_commut_op_p)
2003         break;
2004       use_commut_op_p = true;
2005       if (recog_data.constraints[op_num][0] == '%')
2006         str = recog_data.constraints[op_num + 1];
2007       else if (op_num > 0 && recog_data.constraints[op_num - 1][0] == '%')
2008         str = recog_data.constraints[op_num - 1];
2009       else
2010         break;
2011     }
2012   return -1;
2013 }
2014
2015 \f
2016
2017 /* Search forward to see if the source register of a copy insn dies
2018    before either it or the destination register is modified, but don't
2019    scan past the end of the basic block.  If so, we can replace the
2020    source with the destination and let the source die in the copy
2021    insn.
2022
2023    This will reduce the number of registers live in that range and may
2024    enable the destination and the source coalescing, thus often saving
2025    one register in addition to a register-register copy.  */
2026
2027 static void
2028 decrease_live_ranges_number (void)
2029 {
2030   basic_block bb;
2031   rtx_insn *insn;
2032   rtx set, src, dest, dest_death, q, note;
2033   rtx_insn *p;
2034   int sregno, dregno;
2035
2036   if (! flag_expensive_optimizations)
2037     return;
2038
2039   if (ira_dump_file)
2040     fprintf (ira_dump_file, "Starting decreasing number of live ranges...\n");
2041
2042   FOR_EACH_BB_FN (bb, cfun)
2043     FOR_BB_INSNS (bb, insn)
2044       {
2045         set = single_set (insn);
2046         if (! set)
2047           continue;
2048         src = SET_SRC (set);
2049         dest = SET_DEST (set);
2050         if (! REG_P (src) || ! REG_P (dest)
2051             || find_reg_note (insn, REG_DEAD, src))
2052           continue;
2053         sregno = REGNO (src);
2054         dregno = REGNO (dest);
2055
2056         /* We don't want to mess with hard regs if register classes
2057            are small.  */
2058         if (sregno == dregno
2059             || (targetm.small_register_classes_for_mode_p (GET_MODE (src))
2060                 && (sregno < FIRST_PSEUDO_REGISTER
2061                     || dregno < FIRST_PSEUDO_REGISTER))
2062             /* We don't see all updates to SP if they are in an
2063                auto-inc memory reference, so we must disallow this
2064                optimization on them.  */
2065             || sregno == STACK_POINTER_REGNUM
2066             || dregno == STACK_POINTER_REGNUM)
2067           continue;
2068
2069         dest_death = NULL_RTX;
2070
2071         for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
2072           {
2073             if (! INSN_P (p))
2074               continue;
2075             if (BLOCK_FOR_INSN (p) != bb)
2076               break;
2077
2078             if (reg_set_p (src, p) || reg_set_p (dest, p)
2079                 /* If SRC is an asm-declared register, it must not be
2080                    replaced in any asm.  Unfortunately, the REG_EXPR
2081                    tree for the asm variable may be absent in the SRC
2082                    rtx, so we can't check the actual register
2083                    declaration easily (the asm operand will have it,
2084                    though).  To avoid complicating the test for a rare
2085                    case, we just don't perform register replacement
2086                    for a hard reg mentioned in an asm.  */
2087                 || (sregno < FIRST_PSEUDO_REGISTER
2088                     && asm_noperands (PATTERN (p)) >= 0
2089                     && reg_overlap_mentioned_p (src, PATTERN (p)))
2090                 /* Don't change hard registers used by a call.  */
2091                 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
2092                     && find_reg_fusage (p, USE, src))
2093                 /* Don't change a USE of a register.  */
2094                 || (GET_CODE (PATTERN (p)) == USE
2095                     && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
2096               break;
2097
2098             /* See if all of SRC dies in P.  This test is slightly
2099                more conservative than it needs to be.  */
2100             if ((note = find_regno_note (p, REG_DEAD, sregno))
2101                 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
2102               {
2103                 int failed = 0;
2104
2105                 /* We can do the optimization.  Scan forward from INSN
2106                    again, replacing regs as we go.  Set FAILED if a
2107                    replacement can't be done.  In that case, we can't
2108                    move the death note for SRC.  This should be
2109                    rare.  */
2110
2111                 /* Set to stop at next insn.  */
2112                 for (q = next_real_insn (insn);
2113                      q != next_real_insn (p);
2114                      q = next_real_insn (q))
2115                   {
2116                     if (reg_overlap_mentioned_p (src, PATTERN (q)))
2117                       {
2118                         /* If SRC is a hard register, we might miss
2119                            some overlapping registers with
2120                            validate_replace_rtx, so we would have to
2121                            undo it.  We can't if DEST is present in
2122                            the insn, so fail in that combination of
2123                            cases.  */
2124                         if (sregno < FIRST_PSEUDO_REGISTER
2125                             && reg_mentioned_p (dest, PATTERN (q)))
2126                           failed = 1;
2127
2128                         /* Attempt to replace all uses.  */
2129                         else if (!validate_replace_rtx (src, dest, q))
2130                           failed = 1;
2131
2132                         /* If this succeeded, but some part of the
2133                            register is still present, undo the
2134                            replacement.  */
2135                         else if (sregno < FIRST_PSEUDO_REGISTER
2136                                  && reg_overlap_mentioned_p (src, PATTERN (q)))
2137                           {
2138                             validate_replace_rtx (dest, src, q);
2139                             failed = 1;
2140                           }
2141                       }
2142
2143                     /* If DEST dies here, remove the death note and
2144                        save it for later.  Make sure ALL of DEST dies
2145                        here; again, this is overly conservative.  */
2146                     if (! dest_death
2147                         && (dest_death = find_regno_note (q, REG_DEAD, dregno)))
2148                       {
2149                         if (GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
2150                           remove_note (q, dest_death);
2151                         else
2152                           {
2153                             failed = 1;
2154                             dest_death = 0;
2155                           }
2156                       }
2157                   }
2158
2159                 if (! failed)
2160                   {
2161                     /* Move death note of SRC from P to INSN.  */
2162                     remove_note (p, note);
2163                     XEXP (note, 1) = REG_NOTES (insn);
2164                     REG_NOTES (insn) = note;
2165                   }
2166
2167                 /* DEST is also dead if INSN has a REG_UNUSED note for
2168                    DEST.  */
2169                 if (! dest_death
2170                     && (dest_death
2171                         = find_regno_note (insn, REG_UNUSED, dregno)))
2172                   {
2173                     PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
2174                     remove_note (insn, dest_death);
2175                   }
2176
2177                 /* Put death note of DEST on P if we saw it die.  */
2178                 if (dest_death)
2179                   {
2180                     XEXP (dest_death, 1) = REG_NOTES (p);
2181                     REG_NOTES (p) = dest_death;
2182                   }
2183                 break;
2184               }
2185
2186             /* If SRC is a hard register which is set or killed in
2187                some other way, we can't do this optimization.  */
2188             else if (sregno < FIRST_PSEUDO_REGISTER && dead_or_set_p (p, src))
2189               break;
2190           }
2191       }
2192 }
2193
2194 \f
2195
2196 /* Return nonzero if REGNO is a particularly bad choice for reloading X.  */
2197 static bool
2198 ira_bad_reload_regno_1 (int regno, rtx x)
2199 {
2200   int x_regno, n, i;
2201   ira_allocno_t a;
2202   enum reg_class pref;
2203
2204   /* We only deal with pseudo regs.  */
2205   if (! x || GET_CODE (x) != REG)
2206     return false;
2207
2208   x_regno = REGNO (x);
2209   if (x_regno < FIRST_PSEUDO_REGISTER)
2210     return false;
2211
2212   /* If the pseudo prefers REGNO explicitly, then do not consider
2213      REGNO a bad spill choice.  */
2214   pref = reg_preferred_class (x_regno);
2215   if (reg_class_size[pref] == 1)
2216     return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
2217
2218   /* If the pseudo conflicts with REGNO, then we consider REGNO a
2219      poor choice for a reload regno.  */
2220   a = ira_regno_allocno_map[x_regno];
2221   n = ALLOCNO_NUM_OBJECTS (a);
2222   for (i = 0; i < n; i++)
2223     {
2224       ira_object_t obj = ALLOCNO_OBJECT (a, i);
2225       if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
2226         return true;
2227     }
2228   return false;
2229 }
2230
2231 /* Return nonzero if REGNO is a particularly bad choice for reloading
2232    IN or OUT.  */
2233 bool
2234 ira_bad_reload_regno (int regno, rtx in, rtx out)
2235 {
2236   return (ira_bad_reload_regno_1 (regno, in)
2237           || ira_bad_reload_regno_1 (regno, out));
2238 }
2239
2240 /* Add register clobbers from asm statements.  */
2241 static void
2242 compute_regs_asm_clobbered (void)
2243 {
2244   basic_block bb;
2245
2246   FOR_EACH_BB_FN (bb, cfun)
2247     {
2248       rtx_insn *insn;
2249       FOR_BB_INSNS_REVERSE (bb, insn)
2250         {
2251           df_ref def;
2252
2253           if (NONDEBUG_INSN_P (insn) && extract_asm_operands (PATTERN (insn)))
2254             FOR_EACH_INSN_DEF (def, insn)
2255               {
2256                 unsigned int dregno = DF_REF_REGNO (def);
2257                 if (HARD_REGISTER_NUM_P (dregno))
2258                   add_to_hard_reg_set (&crtl->asm_clobbers,
2259                                        GET_MODE (DF_REF_REAL_REG (def)),
2260                                        dregno);
2261               }
2262         }
2263     }
2264 }
2265
2266
2267 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2268    REGS_EVER_LIVE.  */
2269 void
2270 ira_setup_eliminable_regset (void)
2271 {
2272 #ifdef ELIMINABLE_REGS
2273   int i;
2274   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
2275 #endif
2276   /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2277      sp for alloca.  So we can't eliminate the frame pointer in that
2278      case.  At some point, we should improve this by emitting the
2279      sp-adjusting insns for this case.  */
2280   frame_pointer_needed
2281     = (! flag_omit_frame_pointer
2282        || (cfun->calls_alloca && EXIT_IGNORE_STACK)
2283        /* We need the frame pointer to catch stack overflow exceptions
2284           if the stack pointer is moving.  */
2285        || (flag_stack_check && STACK_CHECK_MOVING_SP)
2286        || crtl->accesses_prior_frames
2287        || (SUPPORTS_STACK_ALIGNMENT && crtl->stack_realign_needed)
2288        /* We need a frame pointer for all Cilk Plus functions that use
2289           Cilk keywords.  */
2290        || (flag_cilkplus && cfun->is_cilk_function)
2291        || targetm.frame_pointer_required ());
2292
2293     /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2294        RTL is very small.  So if we use frame pointer for RA and RTL
2295        actually prevents this, we will spill pseudos assigned to the
2296        frame pointer in LRA.  */
2297
2298   if (frame_pointer_needed)
2299     df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2300
2301   COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
2302   CLEAR_HARD_REG_SET (eliminable_regset);
2303
2304   compute_regs_asm_clobbered ();
2305
2306   /* Build the regset of all eliminable registers and show we can't
2307      use those that we already know won't be eliminated.  */
2308 #ifdef ELIMINABLE_REGS
2309   for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2310     {
2311       bool cannot_elim
2312         = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
2313            || (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed));
2314
2315       if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
2316         {
2317             SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
2318
2319             if (cannot_elim)
2320               SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
2321         }
2322       else if (cannot_elim)
2323         error ("%s cannot be used in asm here",
2324                reg_names[eliminables[i].from]);
2325       else
2326         df_set_regs_ever_live (eliminables[i].from, true);
2327     }
2328 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2329   if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2330     {
2331       SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
2332       if (frame_pointer_needed)
2333         SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
2334     }
2335   else if (frame_pointer_needed)
2336     error ("%s cannot be used in asm here",
2337            reg_names[HARD_FRAME_POINTER_REGNUM]);
2338   else
2339     df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2340 #endif
2341
2342 #else
2343   if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2344     {
2345       SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
2346       if (frame_pointer_needed)
2347         SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
2348     }
2349   else if (frame_pointer_needed)
2350     error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
2351   else
2352     df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
2353 #endif
2354 }
2355
2356 \f
2357
2358 /* Vector of substitutions of register numbers,
2359    used to map pseudo regs into hardware regs.
2360    This is set up as a result of register allocation.
2361    Element N is the hard reg assigned to pseudo reg N,
2362    or is -1 if no hard reg was assigned.
2363    If N is a hard reg number, element N is N.  */
2364 short *reg_renumber;
2365
2366 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2367    the allocation found by IRA.  */
2368 static void
2369 setup_reg_renumber (void)
2370 {
2371   int regno, hard_regno;
2372   ira_allocno_t a;
2373   ira_allocno_iterator ai;
2374
2375   caller_save_needed = 0;
2376   FOR_EACH_ALLOCNO (a, ai)
2377     {
2378       if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL)
2379         continue;
2380       /* There are no caps at this point.  */
2381       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2382       if (! ALLOCNO_ASSIGNED_P (a))
2383         /* It can happen if A is not referenced but partially anticipated
2384            somewhere in a region.  */
2385         ALLOCNO_ASSIGNED_P (a) = true;
2386       ira_free_allocno_updated_costs (a);
2387       hard_regno = ALLOCNO_HARD_REGNO (a);
2388       regno = ALLOCNO_REGNO (a);
2389       reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
2390       if (hard_regno >= 0)
2391         {
2392           int i, nwords;
2393           enum reg_class pclass;
2394           ira_object_t obj;
2395
2396           pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
2397           nwords = ALLOCNO_NUM_OBJECTS (a);
2398           for (i = 0; i < nwords; i++)
2399             {
2400               obj = ALLOCNO_OBJECT (a, i);
2401               IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2402                                       reg_class_contents[pclass]);
2403             }
2404           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2405               && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
2406                                                   call_used_reg_set))
2407             {
2408               ira_assert (!optimize || flag_caller_saves
2409                           || (ALLOCNO_CALLS_CROSSED_NUM (a)
2410                               == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2411                           || regno >= ira_reg_equiv_len
2412                           || ira_equiv_no_lvalue_p (regno));
2413               caller_save_needed = 1;
2414             }
2415         }
2416     }
2417 }
2418
2419 /* Set up allocno assignment flags for further allocation
2420    improvements.  */
2421 static void
2422 setup_allocno_assignment_flags (void)
2423 {
2424   int hard_regno;
2425   ira_allocno_t a;
2426   ira_allocno_iterator ai;
2427
2428   FOR_EACH_ALLOCNO (a, ai)
2429     {
2430       if (! ALLOCNO_ASSIGNED_P (a))
2431         /* It can happen if A is not referenced but partially anticipated
2432            somewhere in a region.  */
2433         ira_free_allocno_updated_costs (a);
2434       hard_regno = ALLOCNO_HARD_REGNO (a);
2435       /* Don't assign hard registers to allocnos which are destination
2436          of removed store at the end of loop.  It has no sense to keep
2437          the same value in different hard registers.  It is also
2438          impossible to assign hard registers correctly to such
2439          allocnos because the cost info and info about intersected
2440          calls are incorrect for them.  */
2441       ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
2442                                 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
2443                                 || (ALLOCNO_MEMORY_COST (a)
2444                                     - ALLOCNO_CLASS_COST (a)) < 0);
2445       ira_assert
2446         (hard_regno < 0
2447          || ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a),
2448                                    reg_class_contents[ALLOCNO_CLASS (a)]));
2449     }
2450 }
2451
2452 /* Evaluate overall allocation cost and the costs for using hard
2453    registers and memory for allocnos.  */
2454 static void
2455 calculate_allocation_cost (void)
2456 {
2457   int hard_regno, cost;
2458   ira_allocno_t a;
2459   ira_allocno_iterator ai;
2460
2461   ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2462   FOR_EACH_ALLOCNO (a, ai)
2463     {
2464       hard_regno = ALLOCNO_HARD_REGNO (a);
2465       ira_assert (hard_regno < 0
2466                   || (ira_hard_reg_in_set_p
2467                       (hard_regno, ALLOCNO_MODE (a),
2468                        reg_class_contents[ALLOCNO_CLASS (a)])));
2469       if (hard_regno < 0)
2470         {
2471           cost = ALLOCNO_MEMORY_COST (a);
2472           ira_mem_cost += cost;
2473         }
2474       else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2475         {
2476           cost = (ALLOCNO_HARD_REG_COSTS (a)
2477                   [ira_class_hard_reg_index
2478                    [ALLOCNO_CLASS (a)][hard_regno]]);
2479           ira_reg_cost += cost;
2480         }
2481       else
2482         {
2483           cost = ALLOCNO_CLASS_COST (a);
2484           ira_reg_cost += cost;
2485         }
2486       ira_overall_cost += cost;
2487     }
2488
2489   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2490     {
2491       fprintf (ira_dump_file,
2492                "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2493                ira_overall_cost, ira_reg_cost, ira_mem_cost,
2494                ira_load_cost, ira_store_cost, ira_shuffle_cost);
2495       fprintf (ira_dump_file, "+++       move loops %d, new jumps %d\n",
2496                ira_move_loops_num, ira_additional_jumps_num);
2497     }
2498
2499 }
2500
2501 #ifdef ENABLE_IRA_CHECKING
2502 /* Check the correctness of the allocation.  We do need this because
2503    of complicated code to transform more one region internal
2504    representation into one region representation.  */
2505 static void
2506 check_allocation (void)
2507 {
2508   ira_allocno_t a;
2509   int hard_regno, nregs, conflict_nregs;
2510   ira_allocno_iterator ai;
2511
2512   FOR_EACH_ALLOCNO (a, ai)
2513     {
2514       int n = ALLOCNO_NUM_OBJECTS (a);
2515       int i;
2516
2517       if (ALLOCNO_CAP_MEMBER (a) != NULL
2518           || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2519         continue;
2520       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2521       if (nregs == 1)
2522         /* We allocated a single hard register.  */
2523         n = 1;
2524       else if (n > 1)
2525         /* We allocated multiple hard registers, and we will test
2526            conflicts in a granularity of single hard regs.  */
2527         nregs = 1;
2528
2529       for (i = 0; i < n; i++)
2530         {
2531           ira_object_t obj = ALLOCNO_OBJECT (a, i);
2532           ira_object_t conflict_obj;
2533           ira_object_conflict_iterator oci;
2534           int this_regno = hard_regno;
2535           if (n > 1)
2536             {
2537               if (REG_WORDS_BIG_ENDIAN)
2538                 this_regno += n - i - 1;
2539               else
2540                 this_regno += i;
2541             }
2542           FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2543             {
2544               ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2545               int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2546               if (conflict_hard_regno < 0)
2547                 continue;
2548
2549               conflict_nregs
2550                 = (hard_regno_nregs
2551                    [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
2552
2553               if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2554                   && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2555                 {
2556                   if (REG_WORDS_BIG_ENDIAN)
2557                     conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2558                                             - OBJECT_SUBWORD (conflict_obj) - 1);
2559                   else
2560                     conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2561                   conflict_nregs = 1;
2562                 }
2563
2564               if ((conflict_hard_regno <= this_regno
2565                  && this_regno < conflict_hard_regno + conflict_nregs)
2566                 || (this_regno <= conflict_hard_regno
2567                     && conflict_hard_regno < this_regno + nregs))
2568                 {
2569                   fprintf (stderr, "bad allocation for %d and %d\n",
2570                            ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2571                   gcc_unreachable ();
2572                 }
2573             }
2574         }
2575     }
2576 }
2577 #endif
2578
2579 /* Allocate REG_EQUIV_INIT.  Set up it from IRA_REG_EQUIV which should
2580    be already calculated.  */
2581 static void
2582 setup_reg_equiv_init (void)
2583 {
2584   int i;
2585   int max_regno = max_reg_num ();
2586
2587   for (i = 0; i < max_regno; i++)
2588     reg_equiv_init (i) = ira_reg_equiv[i].init_insns;
2589 }
2590
2591 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO.  INSNS
2592    are insns which were generated for such movement.  It is assumed
2593    that FROM_REGNO and TO_REGNO always have the same value at the
2594    point of any move containing such registers. This function is used
2595    to update equiv info for register shuffles on the region borders
2596    and for caller save/restore insns.  */
2597 void
2598 ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx_insn *insns)
2599 {
2600   rtx_insn *insn;
2601   rtx x, note;
2602
2603   if (! ira_reg_equiv[from_regno].defined_p
2604       && (! ira_reg_equiv[to_regno].defined_p
2605           || ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX
2606               && ! MEM_READONLY_P (x))))
2607     return;
2608   insn = insns;
2609   if (NEXT_INSN (insn) != NULL_RTX)
2610     {
2611       if (! ira_reg_equiv[to_regno].defined_p)
2612         {
2613           ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX);
2614           return;
2615         }
2616       ira_reg_equiv[to_regno].defined_p = false;
2617       ira_reg_equiv[to_regno].memory
2618         = ira_reg_equiv[to_regno].constant
2619         = ira_reg_equiv[to_regno].invariant
2620         = ira_reg_equiv[to_regno].init_insns = NULL;
2621       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2622         fprintf (ira_dump_file,
2623                  "      Invalidating equiv info for reg %d\n", to_regno);
2624       return;
2625     }
2626   /* It is possible that FROM_REGNO still has no equivalence because
2627      in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2628      insn was not processed yet.  */
2629   if (ira_reg_equiv[from_regno].defined_p)
2630     {
2631       ira_reg_equiv[to_regno].defined_p = true;
2632       if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX)
2633         {
2634           ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX
2635                       && ira_reg_equiv[from_regno].constant == NULL_RTX);
2636           ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX
2637                       || rtx_equal_p (ira_reg_equiv[to_regno].memory, x));
2638           ira_reg_equiv[to_regno].memory = x;
2639           if (! MEM_READONLY_P (x))
2640             /* We don't add the insn to insn init list because memory
2641                equivalence is just to say what memory is better to use
2642                when the pseudo is spilled.  */
2643             return;
2644         }
2645       else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX)
2646         {
2647           ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX);
2648           ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX
2649                       || rtx_equal_p (ira_reg_equiv[to_regno].constant, x));
2650           ira_reg_equiv[to_regno].constant = x;
2651         }
2652       else
2653         {
2654           x = ira_reg_equiv[from_regno].invariant;
2655           ira_assert (x != NULL_RTX);
2656           ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX
2657                       || rtx_equal_p (ira_reg_equiv[to_regno].invariant, x));
2658           ira_reg_equiv[to_regno].invariant = x;
2659         }
2660       if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX)
2661         {
2662           note = set_unique_reg_note (insn, REG_EQUIV, x);
2663           gcc_assert (note != NULL_RTX);
2664           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2665             {
2666               fprintf (ira_dump_file,
2667                        "      Adding equiv note to insn %u for reg %d ",
2668                        INSN_UID (insn), to_regno);
2669               dump_value_slim (ira_dump_file, x, 1);
2670               fprintf (ira_dump_file, "\n");
2671             }
2672         }
2673     }
2674   ira_reg_equiv[to_regno].init_insns
2675     = gen_rtx_INSN_LIST (VOIDmode, insn,
2676                          ira_reg_equiv[to_regno].init_insns);
2677   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2678     fprintf (ira_dump_file,
2679              "      Adding equiv init move insn %u to reg %d\n",
2680              INSN_UID (insn), to_regno);
2681 }
2682
2683 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2684    by IRA.  */
2685 static void
2686 fix_reg_equiv_init (void)
2687 {
2688   int max_regno = max_reg_num ();
2689   int i, new_regno, max;
2690   rtx x, prev, next, insn, set;
2691
2692   if (max_regno_before_ira < max_regno)
2693     {
2694       max = vec_safe_length (reg_equivs);
2695       grow_reg_equivs ();
2696       for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2697         for (prev = NULL_RTX, x = reg_equiv_init (i);
2698              x != NULL_RTX;
2699              x = next)
2700           {
2701             next = XEXP (x, 1);
2702             insn = XEXP (x, 0);
2703             set = single_set (as_a <rtx_insn *> (insn));
2704             ira_assert (set != NULL_RTX
2705                         && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2706             if (REG_P (SET_DEST (set))
2707                 && ((int) REGNO (SET_DEST (set)) == i
2708                     || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2709               new_regno = REGNO (SET_DEST (set));
2710             else if (REG_P (SET_SRC (set))
2711                      && ((int) REGNO (SET_SRC (set)) == i
2712                          || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2713               new_regno = REGNO (SET_SRC (set));
2714             else
2715               gcc_unreachable ();
2716             if (new_regno == i)
2717               prev = x;
2718             else
2719               {
2720                 /* Remove the wrong list element.  */
2721                 if (prev == NULL_RTX)
2722                   reg_equiv_init (i) = next;
2723                 else
2724                   XEXP (prev, 1) = next;
2725                 XEXP (x, 1) = reg_equiv_init (new_regno);
2726                 reg_equiv_init (new_regno) = x;
2727               }
2728           }
2729     }
2730 }
2731
2732 #ifdef ENABLE_IRA_CHECKING
2733 /* Print redundant memory-memory copies.  */
2734 static void
2735 print_redundant_copies (void)
2736 {
2737   int hard_regno;
2738   ira_allocno_t a;
2739   ira_copy_t cp, next_cp;
2740   ira_allocno_iterator ai;
2741
2742   FOR_EACH_ALLOCNO (a, ai)
2743     {
2744       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2745         /* It is a cap.  */
2746         continue;
2747       hard_regno = ALLOCNO_HARD_REGNO (a);
2748       if (hard_regno >= 0)
2749         continue;
2750       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2751         if (cp->first == a)
2752           next_cp = cp->next_first_allocno_copy;
2753         else
2754           {
2755             next_cp = cp->next_second_allocno_copy;
2756             if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2757                 && cp->insn != NULL_RTX
2758                 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2759               fprintf (ira_dump_file,
2760                        "        Redundant move from %d(freq %d):%d\n",
2761                        INSN_UID (cp->insn), cp->freq, hard_regno);
2762           }
2763     }
2764 }
2765 #endif
2766
2767 /* Setup preferred and alternative classes for new pseudo-registers
2768    created by IRA starting with START.  */
2769 static void
2770 setup_preferred_alternate_classes_for_new_pseudos (int start)
2771 {
2772   int i, old_regno;
2773   int max_regno = max_reg_num ();
2774
2775   for (i = start; i < max_regno; i++)
2776     {
2777       old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2778       ira_assert (i != old_regno);
2779       setup_reg_classes (i, reg_preferred_class (old_regno),
2780                          reg_alternate_class (old_regno),
2781                          reg_allocno_class (old_regno));
2782       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2783         fprintf (ira_dump_file,
2784                  "    New r%d: setting preferred %s, alternative %s\n",
2785                  i, reg_class_names[reg_preferred_class (old_regno)],
2786                  reg_class_names[reg_alternate_class (old_regno)]);
2787     }
2788 }
2789
2790 \f
2791 /* The number of entries allocated in reg_info.  */
2792 static int allocated_reg_info_size;
2793
2794 /* Regional allocation can create new pseudo-registers.  This function
2795    expands some arrays for pseudo-registers.  */
2796 static void
2797 expand_reg_info (void)
2798 {
2799   int i;
2800   int size = max_reg_num ();
2801
2802   resize_reg_info ();
2803   for (i = allocated_reg_info_size; i < size; i++)
2804     setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2805   setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size);
2806   allocated_reg_info_size = size;
2807 }
2808
2809 /* Return TRUE if there is too high register pressure in the function.
2810    It is used to decide when stack slot sharing is worth to do.  */
2811 static bool
2812 too_high_register_pressure_p (void)
2813 {
2814   int i;
2815   enum reg_class pclass;
2816
2817   for (i = 0; i < ira_pressure_classes_num; i++)
2818     {
2819       pclass = ira_pressure_classes[i];
2820       if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2821         return true;
2822     }
2823   return false;
2824 }
2825
2826 \f
2827
2828 /* Indicate that hard register number FROM was eliminated and replaced with
2829    an offset from hard register number TO.  The status of hard registers live
2830    at the start of a basic block is updated by replacing a use of FROM with
2831    a use of TO.  */
2832
2833 void
2834 mark_elimination (int from, int to)
2835 {
2836   basic_block bb;
2837   bitmap r;
2838
2839   FOR_EACH_BB_FN (bb, cfun)
2840     {
2841       r = DF_LR_IN (bb);
2842       if (bitmap_bit_p (r, from))
2843         {
2844           bitmap_clear_bit (r, from);
2845           bitmap_set_bit (r, to);
2846         }
2847       if (! df_live)
2848         continue;
2849       r = DF_LIVE_IN (bb);
2850       if (bitmap_bit_p (r, from))
2851         {
2852           bitmap_clear_bit (r, from);
2853           bitmap_set_bit (r, to);
2854         }
2855     }
2856 }
2857
2858 \f
2859
2860 /* The length of the following array.  */
2861 int ira_reg_equiv_len;
2862
2863 /* Info about equiv. info for each register.  */
2864 struct ira_reg_equiv_s *ira_reg_equiv;
2865
2866 /* Expand ira_reg_equiv if necessary.  */
2867 void
2868 ira_expand_reg_equiv (void)
2869 {
2870   int old = ira_reg_equiv_len;
2871
2872   if (ira_reg_equiv_len > max_reg_num ())
2873     return;
2874   ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1;
2875   ira_reg_equiv
2876     = (struct ira_reg_equiv_s *) xrealloc (ira_reg_equiv,
2877                                          ira_reg_equiv_len
2878                                          * sizeof (struct ira_reg_equiv_s));
2879   gcc_assert (old < ira_reg_equiv_len);
2880   memset (ira_reg_equiv + old, 0,
2881           sizeof (struct ira_reg_equiv_s) * (ira_reg_equiv_len - old));
2882 }
2883
2884 static void
2885 init_reg_equiv (void)
2886 {
2887   ira_reg_equiv_len = 0;
2888   ira_reg_equiv = NULL;
2889   ira_expand_reg_equiv ();
2890 }
2891
2892 static void
2893 finish_reg_equiv (void)
2894 {
2895   free (ira_reg_equiv);
2896 }
2897
2898 \f
2899
2900 struct equivalence
2901 {
2902   /* Set when a REG_EQUIV note is found or created.  Use to
2903      keep track of what memory accesses might be created later,
2904      e.g. by reload.  */
2905   rtx replacement;
2906   rtx *src_p;
2907
2908   /* The list of each instruction which initializes this register.
2909
2910      NULL indicates we know nothing about this register's equivalence
2911      properties.
2912
2913      An INSN_LIST with a NULL insn indicates this pseudo is already
2914      known to not have a valid equivalence.  */
2915   rtx_insn_list *init_insns;
2916
2917   /* Loop depth is used to recognize equivalences which appear
2918      to be present within the same loop (or in an inner loop).  */
2919   short loop_depth;
2920   /* Nonzero if this had a preexisting REG_EQUIV note.  */
2921   unsigned char is_arg_equivalence : 1;
2922   /* Set when an attempt should be made to replace a register
2923      with the associated src_p entry.  */
2924   unsigned char replace : 1;
2925   /* Set if this register has no known equivalence.  */
2926   unsigned char no_equiv : 1;
2927 };
2928
2929 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2930    structure for that register.  */
2931 static struct equivalence *reg_equiv;
2932
2933 /* Used for communication between the following two functions: contains
2934    a MEM that we wish to ensure remains unchanged.  */
2935 static rtx equiv_mem;
2936
2937 /* Set nonzero if EQUIV_MEM is modified.  */
2938 static int equiv_mem_modified;
2939
2940 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2941    Called via note_stores.  */
2942 static void
2943 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
2944                                void *data ATTRIBUTE_UNUSED)
2945 {
2946   if ((REG_P (dest)
2947        && reg_overlap_mentioned_p (dest, equiv_mem))
2948       || (MEM_P (dest)
2949           && anti_dependence (equiv_mem, dest)))
2950     equiv_mem_modified = 1;
2951 }
2952
2953 /* Verify that no store between START and the death of REG invalidates
2954    MEMREF.  MEMREF is invalidated by modifying a register used in MEMREF,
2955    by storing into an overlapping memory location, or with a non-const
2956    CALL_INSN.
2957
2958    Return 1 if MEMREF remains valid.  */
2959 static int
2960 validate_equiv_mem (rtx_insn *start, rtx reg, rtx memref)
2961 {
2962   rtx_insn *insn;
2963   rtx note;
2964
2965   equiv_mem = memref;
2966   equiv_mem_modified = 0;
2967
2968   /* If the memory reference has side effects or is volatile, it isn't a
2969      valid equivalence.  */
2970   if (side_effects_p (memref))
2971     return 0;
2972
2973   for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
2974     {
2975       if (! INSN_P (insn))
2976         continue;
2977
2978       if (find_reg_note (insn, REG_DEAD, reg))
2979         return 1;
2980
2981       /* This used to ignore readonly memory and const/pure calls.  The problem
2982          is the equivalent form may reference a pseudo which gets assigned a
2983          call clobbered hard reg.  When we later replace REG with its
2984          equivalent form, the value in the call-clobbered reg has been
2985          changed and all hell breaks loose.  */
2986       if (CALL_P (insn))
2987         return 0;
2988
2989       note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
2990
2991       /* If a register mentioned in MEMREF is modified via an
2992          auto-increment, we lose the equivalence.  Do the same if one
2993          dies; although we could extend the life, it doesn't seem worth
2994          the trouble.  */
2995
2996       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2997         if ((REG_NOTE_KIND (note) == REG_INC
2998              || REG_NOTE_KIND (note) == REG_DEAD)
2999             && REG_P (XEXP (note, 0))
3000             && reg_overlap_mentioned_p (XEXP (note, 0), memref))
3001           return 0;
3002     }
3003
3004   return 0;
3005 }
3006
3007 /* Returns zero if X is known to be invariant.  */
3008 static int
3009 equiv_init_varies_p (rtx x)
3010 {
3011   RTX_CODE code = GET_CODE (x);
3012   int i;
3013   const char *fmt;
3014
3015   switch (code)
3016     {
3017     case MEM:
3018       return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
3019
3020     case CONST:
3021     CASE_CONST_ANY:
3022     case SYMBOL_REF:
3023     case LABEL_REF:
3024       return 0;
3025
3026     case REG:
3027       return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
3028
3029     case ASM_OPERANDS:
3030       if (MEM_VOLATILE_P (x))
3031         return 1;
3032
3033       /* Fall through.  */
3034
3035     default:
3036       break;
3037     }
3038
3039   fmt = GET_RTX_FORMAT (code);
3040   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3041     if (fmt[i] == 'e')
3042       {
3043         if (equiv_init_varies_p (XEXP (x, i)))
3044           return 1;
3045       }
3046     else if (fmt[i] == 'E')
3047       {
3048         int j;
3049         for (j = 0; j < XVECLEN (x, i); j++)
3050           if (equiv_init_varies_p (XVECEXP (x, i, j)))
3051             return 1;
3052       }
3053
3054   return 0;
3055 }
3056
3057 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3058    X is only movable if the registers it uses have equivalent initializations
3059    which appear to be within the same loop (or in an inner loop) and movable
3060    or if they are not candidates for local_alloc and don't vary.  */
3061 static int
3062 equiv_init_movable_p (rtx x, int regno)
3063 {
3064   int i, j;
3065   const char *fmt;
3066   enum rtx_code code = GET_CODE (x);
3067
3068   switch (code)
3069     {
3070     case SET:
3071       return equiv_init_movable_p (SET_SRC (x), regno);
3072
3073     case CC0:
3074     case CLOBBER:
3075       return 0;
3076
3077     case PRE_INC:
3078     case PRE_DEC:
3079     case POST_INC:
3080     case POST_DEC:
3081     case PRE_MODIFY:
3082     case POST_MODIFY:
3083       return 0;
3084
3085     case REG:
3086       return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
3087                && reg_equiv[REGNO (x)].replace)
3088               || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
3089                   && ! rtx_varies_p (x, 0)));
3090
3091     case UNSPEC_VOLATILE:
3092       return 0;
3093
3094     case ASM_OPERANDS:
3095       if (MEM_VOLATILE_P (x))
3096         return 0;
3097
3098       /* Fall through.  */
3099
3100     default:
3101       break;
3102     }
3103
3104   fmt = GET_RTX_FORMAT (code);
3105   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3106     switch (fmt[i])
3107       {
3108       case 'e':
3109         if (! equiv_init_movable_p (XEXP (x, i), regno))
3110           return 0;
3111         break;
3112       case 'E':
3113         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3114           if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
3115             return 0;
3116         break;
3117       }
3118
3119   return 1;
3120 }
3121
3122 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
3123    true.  */
3124 static int
3125 contains_replace_regs (rtx x)
3126 {
3127   int i, j;
3128   const char *fmt;
3129   enum rtx_code code = GET_CODE (x);
3130
3131   switch (code)
3132     {
3133     case CONST:
3134     case LABEL_REF:
3135     case SYMBOL_REF:
3136     CASE_CONST_ANY:
3137     case PC:
3138     case CC0:
3139     case HIGH:
3140       return 0;
3141
3142     case REG:
3143       return reg_equiv[REGNO (x)].replace;
3144
3145     default:
3146       break;
3147     }
3148
3149   fmt = GET_RTX_FORMAT (code);
3150   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3151     switch (fmt[i])
3152       {
3153       case 'e':
3154         if (contains_replace_regs (XEXP (x, i)))
3155           return 1;
3156         break;
3157       case 'E':
3158         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3159           if (contains_replace_regs (XVECEXP (x, i, j)))
3160             return 1;
3161         break;
3162       }
3163
3164   return 0;
3165 }
3166
3167 /* TRUE if X references a memory location that would be affected by a store
3168    to MEMREF.  */
3169 static int
3170 memref_referenced_p (rtx memref, rtx x)
3171 {
3172   int i, j;
3173   const char *fmt;
3174   enum rtx_code code = GET_CODE (x);
3175
3176   switch (code)
3177     {
3178     case CONST:
3179     case LABEL_REF:
3180     case SYMBOL_REF:
3181     CASE_CONST_ANY:
3182     case PC:
3183     case CC0:
3184     case HIGH:
3185     case LO_SUM:
3186       return 0;
3187
3188     case REG:
3189       return (reg_equiv[REGNO (x)].replacement
3190               && memref_referenced_p (memref,
3191                                       reg_equiv[REGNO (x)].replacement));
3192
3193     case MEM:
3194       if (true_dependence (memref, VOIDmode, x))
3195         return 1;
3196       break;
3197
3198     case SET:
3199       /* If we are setting a MEM, it doesn't count (its address does), but any
3200          other SET_DEST that has a MEM in it is referencing the MEM.  */
3201       if (MEM_P (SET_DEST (x)))
3202         {
3203           if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
3204             return 1;
3205         }
3206       else if (memref_referenced_p (memref, SET_DEST (x)))
3207         return 1;
3208
3209       return memref_referenced_p (memref, SET_SRC (x));
3210
3211     default:
3212       break;
3213     }
3214
3215   fmt = GET_RTX_FORMAT (code);
3216   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3217     switch (fmt[i])
3218       {
3219       case 'e':
3220         if (memref_referenced_p (memref, XEXP (x, i)))
3221           return 1;
3222         break;
3223       case 'E':
3224         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3225           if (memref_referenced_p (memref, XVECEXP (x, i, j)))
3226             return 1;
3227         break;
3228       }
3229
3230   return 0;
3231 }
3232
3233 /* TRUE if some insn in the range (START, END] references a memory location
3234    that would be affected by a store to MEMREF.  */
3235 static int
3236 memref_used_between_p (rtx memref, rtx_insn *start, rtx_insn *end)
3237 {
3238   rtx_insn *insn;
3239
3240   for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
3241        insn = NEXT_INSN (insn))
3242     {
3243       if (!NONDEBUG_INSN_P (insn))
3244         continue;
3245
3246       if (memref_referenced_p (memref, PATTERN (insn)))
3247         return 1;
3248
3249       /* Nonconst functions may access memory.  */
3250       if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
3251         return 1;
3252     }
3253
3254   return 0;
3255 }
3256
3257 /* Mark REG as having no known equivalence.
3258    Some instructions might have been processed before and furnished
3259    with REG_EQUIV notes for this register; these notes will have to be
3260    removed.
3261    STORE is the piece of RTL that does the non-constant / conflicting
3262    assignment - a SET, CLOBBER or REG_INC note.  It is currently not used,
3263    but needs to be there because this function is called from note_stores.  */
3264 static void
3265 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
3266           void *data ATTRIBUTE_UNUSED)
3267 {
3268   int regno;
3269   rtx_insn_list *list;
3270
3271   if (!REG_P (reg))
3272     return;
3273   regno = REGNO (reg);
3274   reg_equiv[regno].no_equiv = 1;
3275   list = reg_equiv[regno].init_insns;
3276   if (list && list->insn () == NULL)
3277     return;
3278   reg_equiv[regno].init_insns = gen_rtx_INSN_LIST (VOIDmode, NULL_RTX, NULL);
3279   reg_equiv[regno].replacement = NULL_RTX;
3280   /* This doesn't matter for equivalences made for argument registers, we
3281      should keep their initialization insns.  */
3282   if (reg_equiv[regno].is_arg_equivalence)
3283     return;
3284   ira_reg_equiv[regno].defined_p = false;
3285   ira_reg_equiv[regno].init_insns = NULL;
3286   for (; list; list = list->next ())
3287     {
3288       rtx_insn *insn = list->insn ();
3289       remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
3290     }
3291 }
3292
3293 /* Check whether the SUBREG is a paradoxical subreg and set the result
3294    in PDX_SUBREGS.  */
3295
3296 static void
3297 set_paradoxical_subreg (rtx_insn *insn, bool *pdx_subregs)
3298 {
3299   subrtx_iterator::array_type array;
3300   FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3301     {
3302       const_rtx subreg = *iter;
3303       if (GET_CODE (subreg) == SUBREG)
3304         {
3305           const_rtx reg = SUBREG_REG (subreg);
3306           if (REG_P (reg) && paradoxical_subreg_p (subreg))
3307             pdx_subregs[REGNO (reg)] = true;
3308         }
3309     }
3310 }
3311
3312 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3313    equivalent replacement.  */
3314
3315 static rtx
3316 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
3317 {
3318   if (REG_P (loc))
3319     {
3320       bitmap cleared_regs = (bitmap) data;
3321       if (bitmap_bit_p (cleared_regs, REGNO (loc)))
3322         return simplify_replace_fn_rtx (copy_rtx (*reg_equiv[REGNO (loc)].src_p),
3323                                         NULL_RTX, adjust_cleared_regs, data);
3324     }
3325   return NULL_RTX;
3326 }
3327
3328 /* Nonzero if we recorded an equivalence for a LABEL_REF.  */
3329 static int recorded_label_ref;
3330
3331 /* Find registers that are equivalent to a single value throughout the
3332    compilation (either because they can be referenced in memory or are
3333    set once from a single constant).  Lower their priority for a
3334    register.
3335
3336    If such a register is only referenced once, try substituting its
3337    value into the using insn.  If it succeeds, we can eliminate the
3338    register completely.
3339
3340    Initialize init_insns in ira_reg_equiv array.
3341
3342    Return non-zero if jump label rebuilding should be done.  */
3343 static int
3344 update_equiv_regs (void)
3345 {
3346   rtx_insn *insn;
3347   basic_block bb;
3348   int loop_depth;
3349   bitmap cleared_regs;
3350   bool *pdx_subregs;
3351
3352   /* We need to keep track of whether or not we recorded a LABEL_REF so
3353      that we know if the jump optimizer needs to be rerun.  */
3354   recorded_label_ref = 0;
3355
3356   /* Use pdx_subregs to show whether a reg is used in a paradoxical
3357      subreg.  */
3358   pdx_subregs = XCNEWVEC (bool, max_regno);
3359
3360   reg_equiv = XCNEWVEC (struct equivalence, max_regno);
3361   grow_reg_equivs ();
3362
3363   init_alias_analysis ();
3364
3365   /* Scan insns and set pdx_subregs[regno] if the reg is used in a
3366      paradoxical subreg. Don't set such reg equivalent to a mem,
3367      because lra will not substitute such equiv memory in order to
3368      prevent access beyond allocated memory for paradoxical memory subreg.  */
3369   FOR_EACH_BB_FN (bb, cfun)
3370     FOR_BB_INSNS (bb, insn)
3371       if (NONDEBUG_INSN_P (insn))
3372         set_paradoxical_subreg (insn, pdx_subregs);
3373
3374   /* Scan the insns and find which registers have equivalences.  Do this
3375      in a separate scan of the insns because (due to -fcse-follow-jumps)
3376      a register can be set below its use.  */
3377   FOR_EACH_BB_FN (bb, cfun)
3378     {
3379       loop_depth = bb_loop_depth (bb);
3380
3381       for (insn = BB_HEAD (bb);
3382            insn != NEXT_INSN (BB_END (bb));
3383            insn = NEXT_INSN (insn))
3384         {
3385           rtx note;
3386           rtx set;
3387           rtx dest, src;
3388           int regno;
3389
3390           if (! INSN_P (insn))
3391             continue;
3392
3393           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3394             if (REG_NOTE_KIND (note) == REG_INC)
3395               no_equiv (XEXP (note, 0), note, NULL);
3396
3397           set = single_set (insn);
3398
3399           /* If this insn contains more (or less) than a single SET,
3400              only mark all destinations as having no known equivalence.  */
3401           if (set == NULL_RTX)
3402             {
3403               note_stores (PATTERN (insn), no_equiv, NULL);
3404               continue;
3405             }
3406           else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3407             {
3408               int i;
3409
3410               for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3411                 {
3412                   rtx part = XVECEXP (PATTERN (insn), 0, i);
3413                   if (part != set)
3414                     note_stores (part, no_equiv, NULL);
3415                 }
3416             }
3417
3418           dest = SET_DEST (set);
3419           src = SET_SRC (set);
3420
3421           /* See if this is setting up the equivalence between an argument
3422              register and its stack slot.  */
3423           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3424           if (note)
3425             {
3426               gcc_assert (REG_P (dest));
3427               regno = REGNO (dest);
3428
3429               /* Note that we don't want to clear init_insns in
3430                  ira_reg_equiv even if there are multiple sets of this
3431                  register.  */
3432               reg_equiv[regno].is_arg_equivalence = 1;
3433
3434               /* The insn result can have equivalence memory although
3435                  the equivalence is not set up by the insn.  We add
3436                  this insn to init insns as it is a flag for now that
3437                  regno has an equivalence.  We will remove the insn
3438                  from init insn list later.  */
3439               if (rtx_equal_p (src, XEXP (note, 0)) || MEM_P (XEXP (note, 0)))
3440                 ira_reg_equiv[regno].init_insns
3441                   = gen_rtx_INSN_LIST (VOIDmode, insn,
3442                                        ira_reg_equiv[regno].init_insns);
3443
3444               /* Continue normally in case this is a candidate for
3445                  replacements.  */
3446             }
3447
3448           if (!optimize)
3449             continue;
3450
3451           /* We only handle the case of a pseudo register being set
3452              once, or always to the same value.  */
3453           /* ??? The mn10200 port breaks if we add equivalences for
3454              values that need an ADDRESS_REGS register and set them equivalent
3455              to a MEM of a pseudo.  The actual problem is in the over-conservative
3456              handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3457              calculate_needs, but we traditionally work around this problem
3458              here by rejecting equivalences when the destination is in a register
3459              that's likely spilled.  This is fragile, of course, since the
3460              preferred class of a pseudo depends on all instructions that set
3461              or use it.  */
3462
3463           if (!REG_P (dest)
3464               || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
3465               || (reg_equiv[regno].init_insns
3466                   && reg_equiv[regno].init_insns->insn () == NULL)
3467               || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
3468                   && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
3469             {
3470               /* This might be setting a SUBREG of a pseudo, a pseudo that is
3471                  also set somewhere else to a constant.  */
3472               note_stores (set, no_equiv, NULL);
3473               continue;
3474             }
3475
3476           /* Don't set reg (if pdx_subregs[regno] == true) equivalent to a mem.  */
3477           if (MEM_P (src) && pdx_subregs[regno])
3478             {
3479               note_stores (set, no_equiv, NULL);
3480               continue;
3481             }
3482
3483           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3484
3485           /* cse sometimes generates function invariants, but doesn't put a
3486              REG_EQUAL note on the insn.  Since this note would be redundant,
3487              there's no point creating it earlier than here.  */
3488           if (! note && ! rtx_varies_p (src, 0))
3489             note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
3490
3491           /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3492              since it represents a function call.  */
3493           if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
3494             note = NULL_RTX;
3495
3496           if (DF_REG_DEF_COUNT (regno) != 1)
3497             {
3498               bool equal_p = true;
3499               rtx_insn_list *list;
3500
3501               /* If we have already processed this pseudo and determined it
3502                  can not have an equivalence, then honor that decision.  */
3503               if (reg_equiv[regno].no_equiv)
3504                 continue;
3505
3506               if (! note
3507                   || rtx_varies_p (XEXP (note, 0), 0)
3508                   || (reg_equiv[regno].replacement
3509                       && ! rtx_equal_p (XEXP (note, 0),
3510                                         reg_equiv[regno].replacement)))
3511                 {
3512                   no_equiv (dest, set, NULL);
3513                   continue;
3514                 }
3515
3516               list = reg_equiv[regno].init_insns;
3517               for (; list; list = list->next ())
3518                 {
3519                   rtx note_tmp;
3520                   rtx_insn *insn_tmp;
3521
3522                   insn_tmp = list->insn ();
3523                   note_tmp = find_reg_note (insn_tmp, REG_EQUAL, NULL_RTX);
3524                   gcc_assert (note_tmp);
3525                   if (! rtx_equal_p (XEXP (note, 0), XEXP (note_tmp, 0)))
3526                     {
3527                       equal_p = false;
3528                       break;
3529                     }
3530                 }
3531
3532               if (! equal_p)
3533                 {
3534                   no_equiv (dest, set, NULL);
3535                   continue;
3536                 }
3537             }
3538
3539           /* Record this insn as initializing this register.  */
3540           reg_equiv[regno].init_insns
3541             = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
3542
3543           /* If this register is known to be equal to a constant, record that
3544              it is always equivalent to the constant.  */
3545           if (DF_REG_DEF_COUNT (regno) == 1
3546               && note && ! rtx_varies_p (XEXP (note, 0), 0))
3547             {
3548               rtx note_value = XEXP (note, 0);
3549               remove_note (insn, note);
3550               set_unique_reg_note (insn, REG_EQUIV, note_value);
3551             }
3552
3553           /* If this insn introduces a "constant" register, decrease the priority
3554              of that register.  Record this insn if the register is only used once
3555              more and the equivalence value is the same as our source.
3556
3557              The latter condition is checked for two reasons:  First, it is an
3558              indication that it may be more efficient to actually emit the insn
3559              as written (if no registers are available, reload will substitute
3560              the equivalence).  Secondly, it avoids problems with any registers
3561              dying in this insn whose death notes would be missed.
3562
3563              If we don't have a REG_EQUIV note, see if this insn is loading
3564              a register used only in one basic block from a MEM.  If so, and the
3565              MEM remains unchanged for the life of the register, add a REG_EQUIV
3566              note.  */
3567           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3568
3569           if (note == NULL_RTX && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3570               && MEM_P (SET_SRC (set))
3571               && validate_equiv_mem (insn, dest, SET_SRC (set)))
3572             note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
3573
3574           if (note)
3575             {
3576               int regno = REGNO (dest);
3577               rtx x = XEXP (note, 0);
3578
3579               /* If we haven't done so, record for reload that this is an
3580                  equivalencing insn.  */
3581               if (!reg_equiv[regno].is_arg_equivalence)
3582                 ira_reg_equiv[regno].init_insns
3583                   = gen_rtx_INSN_LIST (VOIDmode, insn,
3584                                        ira_reg_equiv[regno].init_insns);
3585
3586               /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
3587                  We might end up substituting the LABEL_REF for uses of the
3588                  pseudo here or later.  That kind of transformation may turn an
3589                  indirect jump into a direct jump, in which case we must rerun the
3590                  jump optimizer to ensure that the JUMP_LABEL fields are valid.  */
3591               if (GET_CODE (x) == LABEL_REF
3592                   || (GET_CODE (x) == CONST
3593                       && GET_CODE (XEXP (x, 0)) == PLUS
3594                       && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
3595                 recorded_label_ref = 1;
3596
3597               reg_equiv[regno].replacement = x;
3598               reg_equiv[regno].src_p = &SET_SRC (set);
3599               reg_equiv[regno].loop_depth = (short) loop_depth;
3600
3601               /* Don't mess with things live during setjmp.  */
3602               if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
3603                 {
3604                   /* Note that the statement below does not affect the priority
3605                      in local-alloc!  */
3606                   REG_LIVE_LENGTH (regno) *= 2;
3607
3608                   /* If the register is referenced exactly twice, meaning it is
3609                      set once and used once, indicate that the reference may be
3610                      replaced by the equivalence we computed above.  Do this
3611                      even if the register is only used in one block so that
3612                      dependencies can be handled where the last register is
3613                      used in a different block (i.e. HIGH / LO_SUM sequences)
3614                      and to reduce the number of registers alive across
3615                      calls.  */
3616
3617                   if (REG_N_REFS (regno) == 2
3618                       && (rtx_equal_p (x, src)
3619                           || ! equiv_init_varies_p (src))
3620                       && NONJUMP_INSN_P (insn)
3621                       && equiv_init_movable_p (PATTERN (insn), regno))
3622                     reg_equiv[regno].replace = 1;
3623                 }
3624             }
3625         }
3626     }
3627
3628   if (!optimize)
3629     goto out;
3630
3631   /* A second pass, to gather additional equivalences with memory.  This needs
3632      to be done after we know which registers we are going to replace.  */
3633
3634   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3635     {
3636       rtx set, src, dest;
3637       unsigned regno;
3638
3639       if (! INSN_P (insn))
3640         continue;
3641
3642       set = single_set (insn);
3643       if (! set)
3644         continue;
3645
3646       dest = SET_DEST (set);
3647       src = SET_SRC (set);
3648
3649       /* If this sets a MEM to the contents of a REG that is only used
3650          in a single basic block, see if the register is always equivalent
3651          to that memory location and if moving the store from INSN to the
3652          insn that set REG is safe.  If so, put a REG_EQUIV note on the
3653          initializing insn.
3654
3655          Don't add a REG_EQUIV note if the insn already has one.  The existing
3656          REG_EQUIV is likely more useful than the one we are adding.
3657
3658          If one of the regs in the address has reg_equiv[REGNO].replace set,
3659          then we can't add this REG_EQUIV note.  The reg_equiv[REGNO].replace
3660          optimization may move the set of this register immediately before
3661          insn, which puts it after reg_equiv[REGNO].init_insns, and hence
3662          the mention in the REG_EQUIV note would be to an uninitialized
3663          pseudo.  */
3664
3665       if (MEM_P (dest) && REG_P (src)
3666           && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
3667           && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3668           && DF_REG_DEF_COUNT (regno) == 1
3669           && reg_equiv[regno].init_insns != NULL
3670           && reg_equiv[regno].init_insns->insn () != NULL
3671           && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
3672                               REG_EQUIV, NULL_RTX)
3673           && ! contains_replace_regs (XEXP (dest, 0))
3674           && ! pdx_subregs[regno])
3675         {
3676           rtx_insn *init_insn =
3677             as_a <rtx_insn *> (XEXP (reg_equiv[regno].init_insns, 0));
3678           if (validate_equiv_mem (init_insn, src, dest)
3679               && ! memref_used_between_p (dest, init_insn, insn)
3680               /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3681                  multiple sets.  */
3682               && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
3683             {
3684               /* This insn makes the equivalence, not the one initializing
3685                  the register.  */
3686               ira_reg_equiv[regno].init_insns
3687                 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
3688               df_notes_rescan (init_insn);
3689             }
3690         }
3691     }
3692
3693   cleared_regs = BITMAP_ALLOC (NULL);
3694   /* Now scan all regs killed in an insn to see if any of them are
3695      registers only used that once.  If so, see if we can replace the
3696      reference with the equivalent form.  If we can, delete the
3697      initializing reference and this register will go away.  If we
3698      can't replace the reference, and the initializing reference is
3699      within the same loop (or in an inner loop), then move the register
3700      initialization just before the use, so that they are in the same
3701      basic block.  */
3702   FOR_EACH_BB_REVERSE_FN (bb, cfun)
3703     {
3704       loop_depth = bb_loop_depth (bb);
3705       for (insn = BB_END (bb);
3706            insn != PREV_INSN (BB_HEAD (bb));
3707            insn = PREV_INSN (insn))
3708         {
3709           rtx link;
3710
3711           if (! INSN_P (insn))
3712             continue;
3713
3714           /* Don't substitute into a non-local goto, this confuses CFG.  */
3715           if (JUMP_P (insn)
3716               && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
3717             continue;
3718
3719           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3720             {
3721               if (REG_NOTE_KIND (link) == REG_DEAD
3722                   /* Make sure this insn still refers to the register.  */
3723                   && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
3724                 {
3725                   int regno = REGNO (XEXP (link, 0));
3726                   rtx equiv_insn;
3727
3728                   if (! reg_equiv[regno].replace
3729                       || reg_equiv[regno].loop_depth < (short) loop_depth
3730                       /* There is no sense to move insns if live range
3731                          shrinkage or register pressure-sensitive
3732                          scheduling were done because it will not
3733                          improve allocation but worsen insn schedule
3734                          with a big probability.  */
3735                       || flag_live_range_shrinkage
3736                       || (flag_sched_pressure && flag_schedule_insns))
3737                     continue;
3738
3739                   /* reg_equiv[REGNO].replace gets set only when
3740                      REG_N_REFS[REGNO] is 2, i.e. the register is set
3741                      once and used once.  (If it were only set, but
3742                      not used, flow would have deleted the setting
3743                      insns.)  Hence there can only be one insn in
3744                      reg_equiv[REGNO].init_insns.  */
3745                   gcc_assert (reg_equiv[regno].init_insns
3746                               && !XEXP (reg_equiv[regno].init_insns, 1));
3747                   equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
3748
3749                   /* We may not move instructions that can throw, since
3750                      that changes basic block boundaries and we are not
3751                      prepared to adjust the CFG to match.  */
3752                   if (can_throw_internal (equiv_insn))
3753                     continue;
3754
3755                   if (asm_noperands (PATTERN (equiv_insn)) < 0
3756                       && validate_replace_rtx (regno_reg_rtx[regno],
3757                                                *(reg_equiv[regno].src_p), insn))
3758                     {
3759                       rtx equiv_link;
3760                       rtx last_link;
3761                       rtx note;
3762
3763                       /* Find the last note.  */
3764                       for (last_link = link; XEXP (last_link, 1);
3765                            last_link = XEXP (last_link, 1))
3766                         ;
3767
3768                       /* Append the REG_DEAD notes from equiv_insn.  */
3769                       equiv_link = REG_NOTES (equiv_insn);
3770                       while (equiv_link)
3771                         {
3772                           note = equiv_link;
3773                           equiv_link = XEXP (equiv_link, 1);
3774                           if (REG_NOTE_KIND (note) == REG_DEAD)
3775                             {
3776                               remove_note (equiv_insn, note);
3777                               XEXP (last_link, 1) = note;
3778                               XEXP (note, 1) = NULL_RTX;
3779                               last_link = note;
3780                             }
3781                         }
3782
3783                       remove_death (regno, insn);
3784                       SET_REG_N_REFS (regno, 0);
3785                       REG_FREQ (regno) = 0;
3786                       delete_insn (equiv_insn);
3787
3788                       reg_equiv[regno].init_insns
3789                         = reg_equiv[regno].init_insns->next ();
3790
3791                       ira_reg_equiv[regno].init_insns = NULL;
3792                       bitmap_set_bit (cleared_regs, regno);
3793                     }
3794                   /* Move the initialization of the register to just before
3795                      INSN.  Update the flow information.  */
3796                   else if (prev_nondebug_insn (insn) != equiv_insn)
3797                     {
3798                       rtx_insn *new_insn;
3799
3800                       new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
3801                       REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
3802                       REG_NOTES (equiv_insn) = 0;
3803                       /* Rescan it to process the notes.  */
3804                       df_insn_rescan (new_insn);
3805
3806                       /* Make sure this insn is recognized before
3807                          reload begins, otherwise
3808                          eliminate_regs_in_insn will die.  */
3809                       INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
3810
3811                       delete_insn (equiv_insn);
3812
3813                       XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
3814
3815                       REG_BASIC_BLOCK (regno) = bb->index;
3816                       REG_N_CALLS_CROSSED (regno) = 0;
3817                       REG_FREQ_CALLS_CROSSED (regno) = 0;
3818                       REG_N_THROWING_CALLS_CROSSED (regno) = 0;
3819                       REG_LIVE_LENGTH (regno) = 2;
3820
3821                       if (insn == BB_HEAD (bb))
3822                         BB_HEAD (bb) = PREV_INSN (insn);
3823
3824                       ira_reg_equiv[regno].init_insns
3825                         = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
3826                       bitmap_set_bit (cleared_regs, regno);
3827                     }
3828                 }
3829             }
3830         }
3831     }
3832
3833   if (!bitmap_empty_p (cleared_regs))
3834     {
3835       FOR_EACH_BB_FN (bb, cfun)
3836         {
3837           bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
3838           bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
3839           if (! df_live)
3840             continue;
3841           bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
3842           bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
3843         }
3844
3845       /* Last pass - adjust debug insns referencing cleared regs.  */
3846       if (MAY_HAVE_DEBUG_INSNS)
3847         for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3848           if (DEBUG_INSN_P (insn))
3849             {
3850               rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
3851               INSN_VAR_LOCATION_LOC (insn)
3852                 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
3853                                            adjust_cleared_regs,
3854                                            (void *) cleared_regs);
3855               if (old_loc != INSN_VAR_LOCATION_LOC (insn))
3856                 df_insn_rescan (insn);
3857             }
3858     }
3859
3860   BITMAP_FREE (cleared_regs);
3861
3862   out:
3863   /* Clean up.  */
3864
3865   end_alias_analysis ();
3866   free (reg_equiv);
3867   free (pdx_subregs);
3868   return recorded_label_ref;
3869 }
3870
3871 \f
3872
3873 /* Set up fields memory, constant, and invariant from init_insns in
3874    the structures of array ira_reg_equiv.  */
3875 static void
3876 setup_reg_equiv (void)
3877 {
3878   int i;
3879   rtx_insn_list *elem, *prev_elem, *next_elem;
3880   rtx_insn *insn;
3881   rtx set, x;
3882
3883   for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++)
3884     for (prev_elem = NULL, elem = ira_reg_equiv[i].init_insns;
3885          elem;
3886          prev_elem = elem, elem = next_elem)
3887       {
3888         next_elem = elem->next ();
3889         insn = elem->insn ();
3890         set = single_set (insn);
3891
3892         /* Init insns can set up equivalence when the reg is a destination or
3893            a source (in this case the destination is memory).  */
3894         if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))))
3895           {
3896             if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL)
3897               {
3898                 x = XEXP (x, 0);
3899                 if (REG_P (SET_DEST (set))
3900                     && REGNO (SET_DEST (set)) == (unsigned int) i
3901                     && ! rtx_equal_p (SET_SRC (set), x) && MEM_P (x))
3902                   {
3903                     /* This insn reporting the equivalence but
3904                        actually not setting it.  Remove it from the
3905                        list.  */
3906                     if (prev_elem == NULL)
3907                       ira_reg_equiv[i].init_insns = next_elem;
3908                     else
3909                       XEXP (prev_elem, 1) = next_elem;
3910                     elem = prev_elem;
3911                   }
3912               }
3913             else if (REG_P (SET_DEST (set))
3914                      && REGNO (SET_DEST (set)) == (unsigned int) i)
3915               x = SET_SRC (set);
3916             else
3917               {
3918                 gcc_assert (REG_P (SET_SRC (set))
3919                             && REGNO (SET_SRC (set)) == (unsigned int) i);
3920                 x = SET_DEST (set);
3921               }
3922             if (! function_invariant_p (x)
3923                 || ! flag_pic
3924                 /* A function invariant is often CONSTANT_P but may
3925                    include a register.  We promise to only pass
3926                    CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P.  */
3927                 || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
3928               {
3929                 /* It can happen that a REG_EQUIV note contains a MEM
3930                    that is not a legitimate memory operand.  As later
3931                    stages of reload assume that all addresses found in
3932                    the lra_regno_equiv_* arrays were originally
3933                    legitimate, we ignore such REG_EQUIV notes.  */
3934                 if (memory_operand (x, VOIDmode))
3935                   {
3936                     ira_reg_equiv[i].defined_p = true;
3937                     ira_reg_equiv[i].memory = x;
3938                     continue;
3939                   }
3940                 else if (function_invariant_p (x))
3941                   {
3942                     machine_mode mode;
3943
3944                     mode = GET_MODE (SET_DEST (set));
3945                     if (GET_CODE (x) == PLUS
3946                         || x == frame_pointer_rtx || x == arg_pointer_rtx)
3947                       /* This is PLUS of frame pointer and a constant,
3948                          or fp, or argp.  */
3949                       ira_reg_equiv[i].invariant = x;
3950                     else if (targetm.legitimate_constant_p (mode, x))
3951                       ira_reg_equiv[i].constant = x;
3952                     else
3953                       {
3954                         ira_reg_equiv[i].memory = force_const_mem (mode, x);
3955                         if (ira_reg_equiv[i].memory == NULL_RTX)
3956                           {
3957                             ira_reg_equiv[i].defined_p = false;
3958                             ira_reg_equiv[i].init_insns = NULL;
3959                             break;
3960                           }
3961                       }
3962                     ira_reg_equiv[i].defined_p = true;
3963                     continue;
3964                   }
3965               }
3966           }
3967         ira_reg_equiv[i].defined_p = false;
3968         ira_reg_equiv[i].init_insns = NULL;
3969         break;
3970       }
3971 }
3972
3973 \f
3974
3975 /* Print chain C to FILE.  */
3976 static void
3977 print_insn_chain (FILE *file, struct insn_chain *c)
3978 {
3979   fprintf (file, "insn=%d, ", INSN_UID (c->insn));
3980   bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
3981   bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
3982 }
3983
3984
3985 /* Print all reload_insn_chains to FILE.  */
3986 static void
3987 print_insn_chains (FILE *file)
3988 {
3989   struct insn_chain *c;
3990   for (c = reload_insn_chain; c ; c = c->next)
3991     print_insn_chain (file, c);
3992 }
3993
3994 /* Return true if pseudo REGNO should be added to set live_throughout
3995    or dead_or_set of the insn chains for reload consideration.  */
3996 static bool
3997 pseudo_for_reload_consideration_p (int regno)
3998 {
3999   /* Consider spilled pseudos too for IRA because they still have a
4000      chance to get hard-registers in the reload when IRA is used.  */
4001   return (reg_renumber[regno] >= 0 || ira_conflicts_p);
4002 }
4003
4004 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
4005    REG to the number of nregs, and INIT_VALUE to get the
4006    initialization.  ALLOCNUM need not be the regno of REG.  */
4007 static void
4008 init_live_subregs (bool init_value, sbitmap *live_subregs,
4009                    bitmap live_subregs_used, int allocnum, rtx reg)
4010 {
4011   unsigned int regno = REGNO (SUBREG_REG (reg));
4012   int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
4013
4014   gcc_assert (size > 0);
4015
4016   /* Been there, done that.  */
4017   if (bitmap_bit_p (live_subregs_used, allocnum))
4018     return;
4019
4020   /* Create a new one.  */
4021   if (live_subregs[allocnum] == NULL)
4022     live_subregs[allocnum] = sbitmap_alloc (size);
4023
4024   /* If the entire reg was live before blasting into subregs, we need
4025      to init all of the subregs to ones else init to 0.  */
4026   if (init_value)
4027     bitmap_ones (live_subregs[allocnum]);
4028   else
4029     bitmap_clear (live_subregs[allocnum]);
4030
4031   bitmap_set_bit (live_subregs_used, allocnum);
4032 }
4033
4034 /* Walk the insns of the current function and build reload_insn_chain,
4035    and record register life information.  */
4036 static void
4037 build_insn_chain (void)
4038 {
4039   unsigned int i;
4040   struct insn_chain **p = &reload_insn_chain;
4041   basic_block bb;
4042   struct insn_chain *c = NULL;
4043   struct insn_chain *next = NULL;
4044   bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
4045   bitmap elim_regset = BITMAP_ALLOC (NULL);
4046   /* live_subregs is a vector used to keep accurate information about
4047      which hardregs are live in multiword pseudos.  live_subregs and
4048      live_subregs_used are indexed by pseudo number.  The live_subreg
4049      entry for a particular pseudo is only used if the corresponding
4050      element is non zero in live_subregs_used.  The sbitmap size of
4051      live_subreg[allocno] is number of bytes that the pseudo can
4052      occupy.  */
4053   sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
4054   bitmap live_subregs_used = BITMAP_ALLOC (NULL);
4055
4056   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4057     if (TEST_HARD_REG_BIT (eliminable_regset, i))
4058       bitmap_set_bit (elim_regset, i);
4059   FOR_EACH_BB_REVERSE_FN (bb, cfun)
4060     {
4061       bitmap_iterator bi;
4062       rtx_insn *insn;
4063
4064       CLEAR_REG_SET (live_relevant_regs);
4065       bitmap_clear (live_subregs_used);
4066
4067       EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
4068         {
4069           if (i >= FIRST_PSEUDO_REGISTER)
4070             break;
4071           bitmap_set_bit (live_relevant_regs, i);
4072         }
4073
4074       EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb),
4075                                 FIRST_PSEUDO_REGISTER, i, bi)
4076         {
4077           if (pseudo_for_reload_consideration_p (i))
4078             bitmap_set_bit (live_relevant_regs, i);
4079         }
4080
4081       FOR_BB_INSNS_REVERSE (bb, insn)
4082         {
4083           if (!NOTE_P (insn) && !BARRIER_P (insn))
4084             {
4085               struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4086               df_ref def, use;
4087
4088               c = new_insn_chain ();
4089               c->next = next;
4090               next = c;
4091               *p = c;
4092               p = &c->prev;
4093
4094               c->insn = insn;
4095               c->block = bb->index;
4096
4097               if (NONDEBUG_INSN_P (insn))
4098                 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4099                   {
4100                     unsigned int regno = DF_REF_REGNO (def);
4101
4102                     /* Ignore may clobbers because these are generated
4103                        from calls. However, every other kind of def is
4104                        added to dead_or_set.  */
4105                     if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
4106                       {
4107                         if (regno < FIRST_PSEUDO_REGISTER)
4108                           {
4109                             if (!fixed_regs[regno])
4110                               bitmap_set_bit (&c->dead_or_set, regno);
4111                           }
4112                         else if (pseudo_for_reload_consideration_p (regno))
4113                           bitmap_set_bit (&c->dead_or_set, regno);
4114                       }
4115
4116                     if ((regno < FIRST_PSEUDO_REGISTER
4117                          || reg_renumber[regno] >= 0
4118                          || ira_conflicts_p)
4119                         && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
4120                       {
4121                         rtx reg = DF_REF_REG (def);
4122
4123                         /* We can model subregs, but not if they are
4124                            wrapped in ZERO_EXTRACTS.  */
4125                         if (GET_CODE (reg) == SUBREG
4126                             && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
4127                           {
4128                             unsigned int start = SUBREG_BYTE (reg);
4129                             unsigned int last = start
4130                               + GET_MODE_SIZE (GET_MODE (reg));
4131
4132                             init_live_subregs
4133                               (bitmap_bit_p (live_relevant_regs, regno),
4134                                live_subregs, live_subregs_used, regno, reg);
4135
4136                             if (!DF_REF_FLAGS_IS_SET
4137                                 (def, DF_REF_STRICT_LOW_PART))
4138                               {
4139                                 /* Expand the range to cover entire words.
4140                                    Bytes added here are "don't care".  */
4141                                 start
4142                                   = start / UNITS_PER_WORD * UNITS_PER_WORD;
4143                                 last = ((last + UNITS_PER_WORD - 1)
4144                                         / UNITS_PER_WORD * UNITS_PER_WORD);
4145                               }
4146
4147                             /* Ignore the paradoxical bits.  */
4148                             if (last > SBITMAP_SIZE (live_subregs[regno]))
4149                               last = SBITMAP_SIZE (live_subregs[regno]);
4150
4151                             while (start < last)
4152                               {
4153                                 bitmap_clear_bit (live_subregs[regno], start);
4154                                 start++;
4155                               }
4156
4157                             if (bitmap_empty_p (live_subregs[regno]))
4158                               {
4159                                 bitmap_clear_bit (live_subregs_used, regno);
4160                                 bitmap_clear_bit (live_relevant_regs, regno);
4161                               }
4162                             else
4163                               /* Set live_relevant_regs here because
4164                                  that bit has to be true to get us to
4165                                  look at the live_subregs fields.  */
4166                               bitmap_set_bit (live_relevant_regs, regno);
4167                           }
4168                         else
4169                           {
4170                             /* DF_REF_PARTIAL is generated for
4171                                subregs, STRICT_LOW_PART, and
4172                                ZERO_EXTRACT.  We handle the subreg
4173                                case above so here we have to keep from
4174                                modeling the def as a killing def.  */
4175                             if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
4176                               {
4177                                 bitmap_clear_bit (live_subregs_used, regno);
4178                                 bitmap_clear_bit (live_relevant_regs, regno);
4179                               }
4180                           }
4181                       }
4182                   }
4183
4184               bitmap_and_compl_into (live_relevant_regs, elim_regset);
4185               bitmap_copy (&c->live_throughout, live_relevant_regs);
4186
4187               if (NONDEBUG_INSN_P (insn))
4188                 FOR_EACH_INSN_INFO_USE (use, insn_info)
4189                   {
4190                     unsigned int regno = DF_REF_REGNO (use);
4191                     rtx reg = DF_REF_REG (use);
4192
4193                     /* DF_REF_READ_WRITE on a use means that this use
4194                        is fabricated from a def that is a partial set
4195                        to a multiword reg.  Here, we only model the
4196                        subreg case that is not wrapped in ZERO_EXTRACT
4197                        precisely so we do not need to look at the
4198                        fabricated use.  */
4199                     if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
4200                         && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
4201                         && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
4202                       continue;
4203
4204                     /* Add the last use of each var to dead_or_set.  */
4205                     if (!bitmap_bit_p (live_relevant_regs, regno))
4206                       {
4207                         if (regno < FIRST_PSEUDO_REGISTER)
4208                           {
4209                             if (!fixed_regs[regno])
4210                               bitmap_set_bit (&c->dead_or_set, regno);
4211                           }
4212                         else if (pseudo_for_reload_consideration_p (regno))
4213                           bitmap_set_bit (&c->dead_or_set, regno);
4214                       }
4215
4216                     if (regno < FIRST_PSEUDO_REGISTER
4217                         || pseudo_for_reload_consideration_p (regno))
4218                       {
4219                         if (GET_CODE (reg) == SUBREG
4220                             && !DF_REF_FLAGS_IS_SET (use,
4221                                                      DF_REF_SIGN_EXTRACT
4222                                                      | DF_REF_ZERO_EXTRACT))
4223                           {
4224                             unsigned int start = SUBREG_BYTE (reg);
4225                             unsigned int last = start
4226                               + GET_MODE_SIZE (GET_MODE (reg));
4227
4228                             init_live_subregs
4229                               (bitmap_bit_p (live_relevant_regs, regno),
4230                                live_subregs, live_subregs_used, regno, reg);
4231
4232                             /* Ignore the paradoxical bits.  */
4233                             if (last > SBITMAP_SIZE (live_subregs[regno]))
4234                               last = SBITMAP_SIZE (live_subregs[regno]);
4235
4236                             while (start < last)
4237                               {
4238                                 bitmap_set_bit (live_subregs[regno], start);
4239                                 start++;
4240                               }
4241                           }
4242                         else
4243                           /* Resetting the live_subregs_used is
4244                              effectively saying do not use the subregs
4245                              because we are reading the whole
4246                              pseudo.  */
4247                           bitmap_clear_bit (live_subregs_used, regno);
4248                         bitmap_set_bit (live_relevant_regs, regno);
4249                       }
4250                   }
4251             }
4252         }
4253
4254       /* FIXME!! The following code is a disaster.  Reload needs to see the
4255          labels and jump tables that are just hanging out in between
4256          the basic blocks.  See pr33676.  */
4257       insn = BB_HEAD (bb);
4258
4259       /* Skip over the barriers and cruft.  */
4260       while (insn && (BARRIER_P (insn) || NOTE_P (insn)
4261                       || BLOCK_FOR_INSN (insn) == bb))
4262         insn = PREV_INSN (insn);
4263
4264       /* While we add anything except barriers and notes, the focus is
4265          to get the labels and jump tables into the
4266          reload_insn_chain.  */
4267       while (insn)
4268         {
4269           if (!NOTE_P (insn) && !BARRIER_P (insn))
4270             {
4271               if (BLOCK_FOR_INSN (insn))
4272                 break;
4273
4274               c = new_insn_chain ();
4275               c->next = next;
4276               next = c;
4277               *p = c;
4278               p = &c->prev;
4279
4280               /* The block makes no sense here, but it is what the old
4281                  code did.  */
4282               c->block = bb->index;
4283               c->insn = insn;
4284               bitmap_copy (&c->live_throughout, live_relevant_regs);
4285             }
4286           insn = PREV_INSN (insn);
4287         }
4288     }
4289
4290   reload_insn_chain = c;
4291   *p = NULL;
4292
4293   for (i = 0; i < (unsigned int) max_regno; i++)
4294     if (live_subregs[i] != NULL)
4295       sbitmap_free (live_subregs[i]);
4296   free (live_subregs);
4297   BITMAP_FREE (live_subregs_used);
4298   BITMAP_FREE (live_relevant_regs);
4299   BITMAP_FREE (elim_regset);
4300
4301   if (dump_file)
4302     print_insn_chains (dump_file);
4303 }
4304  \f
4305 /* Examine the rtx found in *LOC, which is read or written to as determined
4306    by TYPE.  Return false if we find a reason why an insn containing this
4307    rtx should not be moved (such as accesses to non-constant memory), true
4308    otherwise.  */
4309 static bool
4310 rtx_moveable_p (rtx *loc, enum op_type type)
4311 {
4312   const char *fmt;
4313   rtx x = *loc;
4314   enum rtx_code code = GET_CODE (x);
4315   int i, j;
4316
4317   code = GET_CODE (x);
4318   switch (code)
4319     {
4320     case CONST:
4321     CASE_CONST_ANY:
4322     case SYMBOL_REF:
4323     case LABEL_REF:
4324       return true;
4325
4326     case PC:
4327       return type == OP_IN;
4328
4329     case CC0:
4330       return false;
4331
4332     case REG:
4333       if (x == frame_pointer_rtx)
4334         return true;
4335       if (HARD_REGISTER_P (x))
4336         return false;
4337
4338       return true;
4339
4340     case MEM:
4341       if (type == OP_IN && MEM_READONLY_P (x))
4342         return rtx_moveable_p (&XEXP (x, 0), OP_IN);
4343       return false;
4344
4345     case SET:
4346       return (rtx_moveable_p (&SET_SRC (x), OP_IN)
4347               && rtx_moveable_p (&SET_DEST (x), OP_OUT));
4348
4349     case STRICT_LOW_PART:
4350       return rtx_moveable_p (&XEXP (x, 0), OP_OUT);
4351
4352     case ZERO_EXTRACT:
4353     case SIGN_EXTRACT:
4354       return (rtx_moveable_p (&XEXP (x, 0), type)
4355               && rtx_moveable_p (&XEXP (x, 1), OP_IN)
4356               && rtx_moveable_p (&XEXP (x, 2), OP_IN));
4357
4358     case CLOBBER:
4359       return rtx_moveable_p (&SET_DEST (x), OP_OUT);
4360
4361     default:
4362       break;
4363     }
4364
4365   fmt = GET_RTX_FORMAT (code);
4366   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4367     {
4368       if (fmt[i] == 'e')
4369         {
4370           if (!rtx_moveable_p (&XEXP (x, i), type))
4371             return false;
4372         }
4373       else if (fmt[i] == 'E')
4374         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4375           {
4376             if (!rtx_moveable_p (&XVECEXP (x, i, j), type))
4377               return false;
4378           }
4379     }
4380   return true;
4381 }
4382
4383 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4384    to give dominance relationships between two insns I1 and I2.  */
4385 static bool
4386 insn_dominated_by_p (rtx i1, rtx i2, int *uid_luid)
4387 {
4388   basic_block bb1 = BLOCK_FOR_INSN (i1);
4389   basic_block bb2 = BLOCK_FOR_INSN (i2);
4390
4391   if (bb1 == bb2)
4392     return uid_luid[INSN_UID (i2)] < uid_luid[INSN_UID (i1)];
4393   return dominated_by_p (CDI_DOMINATORS, bb1, bb2);
4394 }
4395
4396 /* Record the range of register numbers added by find_moveable_pseudos.  */
4397 int first_moveable_pseudo, last_moveable_pseudo;
4398
4399 /* These two vectors hold data for every register added by
4400    find_movable_pseudos, with index 0 holding data for the
4401    first_moveable_pseudo.  */
4402 /* The original home register.  */
4403 static vec<rtx> pseudo_replaced_reg;
4404
4405 /* Look for instances where we have an instruction that is known to increase
4406    register pressure, and whose result is not used immediately.  If it is
4407    possible to move the instruction downwards to just before its first use,
4408    split its lifetime into two ranges.  We create a new pseudo to compute the
4409    value, and emit a move instruction just before the first use.  If, after
4410    register allocation, the new pseudo remains unallocated, the function
4411    move_unallocated_pseudos then deletes the move instruction and places
4412    the computation just before the first use.
4413
4414    Such a move is safe and profitable if all the input registers remain live
4415    and unchanged between the original computation and its first use.  In such
4416    a situation, the computation is known to increase register pressure, and
4417    moving it is known to at least not worsen it.
4418
4419    We restrict moves to only those cases where a register remains unallocated,
4420    in order to avoid interfering too much with the instruction schedule.  As
4421    an exception, we may move insns which only modify their input register
4422    (typically induction variables), as this increases the freedom for our
4423    intended transformation, and does not limit the second instruction
4424    scheduler pass.  */
4425
4426 static void
4427 find_moveable_pseudos (void)
4428 {
4429   unsigned i;
4430   int max_regs = max_reg_num ();
4431   int max_uid = get_max_uid ();
4432   basic_block bb;
4433   int *uid_luid = XNEWVEC (int, max_uid);
4434   rtx_insn **closest_uses = XNEWVEC (rtx_insn *, max_regs);
4435   /* A set of registers which are live but not modified throughout a block.  */
4436   bitmap_head *bb_transp_live = XNEWVEC (bitmap_head,
4437                                          last_basic_block_for_fn (cfun));
4438   /* A set of registers which only exist in a given basic block.  */
4439   bitmap_head *bb_local = XNEWVEC (bitmap_head,
4440                                    last_basic_block_for_fn (cfun));
4441   /* A set of registers which are set once, in an instruction that can be
4442      moved freely downwards, but are otherwise transparent to a block.  */
4443   bitmap_head *bb_moveable_reg_sets = XNEWVEC (bitmap_head,
4444                                                last_basic_block_for_fn (cfun));
4445   bitmap_head live, used, set, interesting, unusable_as_input;
4446   bitmap_iterator bi;
4447   bitmap_initialize (&interesting, 0);
4448
4449   first_moveable_pseudo = max_regs;
4450   pseudo_replaced_reg.release ();
4451   pseudo_replaced_reg.safe_grow_cleared (max_regs);
4452
4453   df_analyze ();
4454   calculate_dominance_info (CDI_DOMINATORS);
4455
4456   i = 0;
4457   bitmap_initialize (&live, 0);
4458   bitmap_initialize (&used, 0);
4459   bitmap_initialize (&set, 0);
4460   bitmap_initialize (&unusable_as_input, 0);
4461   FOR_EACH_BB_FN (bb, cfun)
4462     {
4463       rtx_insn *insn;
4464       bitmap transp = bb_transp_live + bb->index;
4465       bitmap moveable = bb_moveable_reg_sets + bb->index;
4466       bitmap local = bb_local + bb->index;
4467
4468       bitmap_initialize (local, 0);
4469       bitmap_initialize (transp, 0);
4470       bitmap_initialize (moveable, 0);
4471       bitmap_copy (&live, df_get_live_out (bb));
4472       bitmap_and_into (&live, df_get_live_in (bb));
4473       bitmap_copy (transp, &live);
4474       bitmap_clear (moveable);
4475       bitmap_clear (&live);
4476       bitmap_clear (&used);
4477       bitmap_clear (&set);
4478       FOR_BB_INSNS (bb, insn)
4479         if (NONDEBUG_INSN_P (insn))
4480           {
4481             df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4482             df_ref def, use;
4483
4484             uid_luid[INSN_UID (insn)] = i++;
4485
4486             def = df_single_def (insn_info);
4487             use = df_single_use (insn_info);
4488             if (use
4489                 && def
4490                 && DF_REF_REGNO (use) == DF_REF_REGNO (def)
4491                 && !bitmap_bit_p (&set, DF_REF_REGNO (use))
4492                 && rtx_moveable_p (&PATTERN (insn), OP_IN))
4493               {
4494                 unsigned regno = DF_REF_REGNO (use);
4495                 bitmap_set_bit (moveable, regno);
4496                 bitmap_set_bit (&set, regno);
4497                 bitmap_set_bit (&used, regno);
4498                 bitmap_clear_bit (transp, regno);
4499                 continue;
4500               }
4501             FOR_EACH_INSN_INFO_USE (use, insn_info)
4502               {
4503                 unsigned regno = DF_REF_REGNO (use);
4504                 bitmap_set_bit (&used, regno);
4505                 if (bitmap_clear_bit (moveable, regno))
4506                   bitmap_clear_bit (transp, regno);
4507               }
4508
4509             FOR_EACH_INSN_INFO_DEF (def, insn_info)
4510               {
4511                 unsigned regno = DF_REF_REGNO (def);
4512                 bitmap_set_bit (&set, regno);
4513                 bitmap_clear_bit (transp, regno);
4514                 bitmap_clear_bit (moveable, regno);
4515               }
4516           }
4517     }
4518
4519   bitmap_clear (&live);
4520   bitmap_clear (&used);
4521   bitmap_clear (&set);
4522
4523   FOR_EACH_BB_FN (bb, cfun)
4524     {
4525       bitmap local = bb_local + bb->index;
4526       rtx_insn *insn;
4527
4528       FOR_BB_INSNS (bb, insn)
4529         if (NONDEBUG_INSN_P (insn))
4530           {
4531             df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4532             rtx_insn *def_insn;
4533             rtx closest_use, note;
4534             df_ref def, use;
4535             unsigned regno;
4536             bool all_dominated, all_local;
4537             machine_mode mode;
4538
4539             def = df_single_def (insn_info);
4540             /* There must be exactly one def in this insn.  */
4541             if (!def || !single_set (insn))
4542               continue;
4543             /* This must be the only definition of the reg.  We also limit
4544                which modes we deal with so that we can assume we can generate
4545                move instructions.  */
4546             regno = DF_REF_REGNO (def);
4547             mode = GET_MODE (DF_REF_REG (def));
4548             if (DF_REG_DEF_COUNT (regno) != 1
4549                 || !DF_REF_INSN_INFO (def)
4550                 || HARD_REGISTER_NUM_P (regno)
4551                 || DF_REG_EQ_USE_COUNT (regno) > 0
4552                 || (!INTEGRAL_MODE_P (mode) && !FLOAT_MODE_P (mode)))
4553               continue;
4554             def_insn = DF_REF_INSN (def);
4555
4556             for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
4557               if (REG_NOTE_KIND (note) == REG_EQUIV && MEM_P (XEXP (note, 0)))
4558                 break;
4559
4560             if (note)
4561               {
4562                 if (dump_file)
4563                   fprintf (dump_file, "Ignoring reg %d, has equiv memory\n",
4564                            regno);
4565                 bitmap_set_bit (&unusable_as_input, regno);
4566                 continue;
4567               }
4568
4569             use = DF_REG_USE_CHAIN (regno);
4570             all_dominated = true;
4571             all_local = true;
4572             closest_use = NULL_RTX;
4573             for (; use; use = DF_REF_NEXT_REG (use))
4574               {
4575                 rtx_insn *insn;
4576                 if (!DF_REF_INSN_INFO (use))
4577                   {
4578                     all_dominated = false;
4579                     all_local = false;
4580                     break;
4581                   }
4582                 insn = DF_REF_INSN (use);
4583                 if (DEBUG_INSN_P (insn))
4584                   continue;
4585                 if (BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (def_insn))
4586                   all_local = false;
4587                 if (!insn_dominated_by_p (insn, def_insn, uid_luid))
4588                   all_dominated = false;
4589                 if (closest_use != insn && closest_use != const0_rtx)
4590                   {
4591                     if (closest_use == NULL_RTX)
4592                       closest_use = insn;
4593                     else if (insn_dominated_by_p (closest_use, insn, uid_luid))
4594                       closest_use = insn;
4595                     else if (!insn_dominated_by_p (insn, closest_use, uid_luid))
4596                       closest_use = const0_rtx;
4597                   }
4598               }
4599             if (!all_dominated)
4600               {
4601                 if (dump_file)
4602                   fprintf (dump_file, "Reg %d not all uses dominated by set\n",
4603                            regno);
4604                 continue;
4605               }
4606             if (all_local)
4607               bitmap_set_bit (local, regno);
4608             if (closest_use == const0_rtx || closest_use == NULL
4609                 || next_nonnote_nondebug_insn (def_insn) == closest_use)
4610               {
4611                 if (dump_file)
4612                   fprintf (dump_file, "Reg %d uninteresting%s\n", regno,
4613                            closest_use == const0_rtx || closest_use == NULL
4614                            ? " (no unique first use)" : "");
4615                 continue;
4616               }
4617 #ifdef HAVE_cc0
4618             if (reg_referenced_p (cc0_rtx, PATTERN (closest_use)))
4619               {
4620                 if (dump_file)
4621                   fprintf (dump_file, "Reg %d: closest user uses cc0\n",
4622                            regno);
4623                 continue;
4624               }
4625 #endif
4626             bitmap_set_bit (&interesting, regno);
4627             /* If we get here, we know closest_use is a non-NULL insn
4628                (as opposed to const_0_rtx).  */
4629             closest_uses[regno] = as_a <rtx_insn *> (closest_use);
4630
4631             if (dump_file && (all_local || all_dominated))
4632               {
4633                 fprintf (dump_file, "Reg %u:", regno);
4634                 if (all_local)
4635                   fprintf (dump_file, " local to bb %d", bb->index);
4636                 if (all_dominated)
4637                   fprintf (dump_file, " def dominates all uses");
4638                 if (closest_use != const0_rtx)
4639                   fprintf (dump_file, " has unique first use");
4640                 fputs ("\n", dump_file);
4641               }
4642           }
4643     }
4644
4645   EXECUTE_IF_SET_IN_BITMAP (&interesting, 0, i, bi)
4646     {
4647       df_ref def = DF_REG_DEF_CHAIN (i);
4648       rtx_insn *def_insn = DF_REF_INSN (def);
4649       basic_block def_block = BLOCK_FOR_INSN (def_insn);
4650       bitmap def_bb_local = bb_local + def_block->index;
4651       bitmap def_bb_moveable = bb_moveable_reg_sets + def_block->index;
4652       bitmap def_bb_transp = bb_transp_live + def_block->index;
4653       bool local_to_bb_p = bitmap_bit_p (def_bb_local, i);
4654       rtx_insn *use_insn = closest_uses[i];
4655       df_ref use;
4656       bool all_ok = true;
4657       bool all_transp = true;
4658
4659       if (!REG_P (DF_REF_REG (def)))
4660         continue;
4661
4662       if (!local_to_bb_p)
4663         {
4664           if (dump_file)
4665             fprintf (dump_file, "Reg %u not local to one basic block\n",
4666                      i);
4667           continue;
4668         }
4669       if (reg_equiv_init (i) != NULL_RTX)
4670         {
4671           if (dump_file)
4672             fprintf (dump_file, "Ignoring reg %u with equiv init insn\n",
4673                      i);
4674           continue;
4675         }
4676       if (!rtx_moveable_p (&PATTERN (def_insn), OP_IN))
4677         {
4678           if (dump_file)
4679             fprintf (dump_file, "Found def insn %d for %d to be not moveable\n",
4680                      INSN_UID (def_insn), i);
4681           continue;
4682         }
4683       if (dump_file)
4684         fprintf (dump_file, "Examining insn %d, def for %d\n",
4685                  INSN_UID (def_insn), i);
4686       FOR_EACH_INSN_USE (use, def_insn)
4687         {
4688           unsigned regno = DF_REF_REGNO (use);
4689           if (bitmap_bit_p (&unusable_as_input, regno))
4690             {
4691               all_ok = false;
4692               if (dump_file)
4693                 fprintf (dump_file, "  found unusable input reg %u.\n", regno);
4694               break;
4695             }
4696           if (!bitmap_bit_p (def_bb_transp, regno))
4697             {
4698               if (bitmap_bit_p (def_bb_moveable, regno)
4699                   && !control_flow_insn_p (use_insn)
4700 #ifdef HAVE_cc0
4701                   && !sets_cc0_p (use_insn)
4702 #endif
4703                   )
4704                 {
4705                   if (modified_between_p (DF_REF_REG (use), def_insn, use_insn))
4706                     {
4707                       rtx_insn *x = NEXT_INSN (def_insn);
4708                       while (!modified_in_p (DF_REF_REG (use), x))
4709                         {
4710                           gcc_assert (x != use_insn);
4711                           x = NEXT_INSN (x);
4712                         }
4713                       if (dump_file)
4714                         fprintf (dump_file, "  input reg %u modified but insn %d moveable\n",
4715                                  regno, INSN_UID (x));
4716                       emit_insn_after (PATTERN (x), use_insn);
4717                       set_insn_deleted (x);
4718                     }
4719                   else
4720                     {
4721                       if (dump_file)
4722                         fprintf (dump_file, "  input reg %u modified between def and use\n",
4723                                  regno);
4724                       all_transp = false;
4725                     }
4726                 }
4727               else
4728                 all_transp = false;
4729             }
4730         }
4731       if (!all_ok)
4732         continue;
4733       if (!dbg_cnt (ira_move))
4734         break;
4735       if (dump_file)
4736         fprintf (dump_file, "  all ok%s\n", all_transp ? " and transp" : "");
4737
4738       if (all_transp)
4739         {
4740           rtx def_reg = DF_REF_REG (def);
4741           rtx newreg = ira_create_new_reg (def_reg);
4742           if (validate_change (def_insn, DF_REF_REAL_LOC (def), newreg, 0))
4743             {
4744               unsigned nregno = REGNO (newreg);
4745               emit_insn_before (gen_move_insn (def_reg, newreg), use_insn);
4746               nregno -= max_regs;
4747               pseudo_replaced_reg[nregno] = def_reg;
4748             }
4749         }
4750     }
4751
4752   FOR_EACH_BB_FN (bb, cfun)
4753     {
4754       bitmap_clear (bb_local + bb->index);
4755       bitmap_clear (bb_transp_live + bb->index);
4756       bitmap_clear (bb_moveable_reg_sets + bb->index);
4757     }
4758   bitmap_clear (&interesting);
4759   bitmap_clear (&unusable_as_input);
4760   free (uid_luid);
4761   free (closest_uses);
4762   free (bb_local);
4763   free (bb_transp_live);
4764   free (bb_moveable_reg_sets);
4765
4766   last_moveable_pseudo = max_reg_num ();
4767
4768   fix_reg_equiv_init ();
4769   expand_reg_info ();
4770   regstat_free_n_sets_and_refs ();
4771   regstat_free_ri ();
4772   regstat_init_n_sets_and_refs ();
4773   regstat_compute_ri ();
4774   free_dominance_info (CDI_DOMINATORS);
4775 }
4776
4777 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4778    is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4779    the destination.  Otherwise return NULL.  */
4780
4781 static rtx
4782 interesting_dest_for_shprep_1 (rtx set, basic_block call_dom)
4783 {
4784   rtx src = SET_SRC (set);
4785   rtx dest = SET_DEST (set);
4786   if (!REG_P (src) || !HARD_REGISTER_P (src)
4787       || !REG_P (dest) || HARD_REGISTER_P (dest)
4788       || (call_dom && !bitmap_bit_p (df_get_live_in (call_dom), REGNO (dest))))
4789     return NULL;
4790   return dest;
4791 }
4792
4793 /* If insn is interesting for parameter range-splitting shrink-wrapping
4794    preparation, i.e. it is a single set from a hard register to a pseudo, which
4795    is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4796    parallel statement with only one such statement, return the destination.
4797    Otherwise return NULL.  */
4798
4799 static rtx
4800 interesting_dest_for_shprep (rtx_insn *insn, basic_block call_dom)
4801 {
4802   if (!INSN_P (insn))
4803     return NULL;
4804   rtx pat = PATTERN (insn);
4805   if (GET_CODE (pat) == SET)
4806     return interesting_dest_for_shprep_1 (pat, call_dom);
4807
4808   if (GET_CODE (pat) != PARALLEL)
4809     return NULL;
4810   rtx ret = NULL;
4811   for (int i = 0; i < XVECLEN (pat, 0); i++)
4812     {
4813       rtx sub = XVECEXP (pat, 0, i);
4814       if (GET_CODE (sub) == USE || GET_CODE (sub) == CLOBBER)
4815         continue;
4816       if (GET_CODE (sub) != SET
4817           || side_effects_p (sub))
4818         return NULL;
4819       rtx dest = interesting_dest_for_shprep_1 (sub, call_dom);
4820       if (dest && ret)
4821         return NULL;
4822       if (dest)
4823         ret = dest;
4824     }
4825   return ret;
4826 }
4827
4828 /* Split live ranges of pseudos that are loaded from hard registers in the
4829    first BB in a BB that dominates all non-sibling call if such a BB can be
4830    found and is not in a loop.  Return true if the function has made any
4831    changes.  */
4832
4833 static bool
4834 split_live_ranges_for_shrink_wrap (void)
4835 {
4836   basic_block bb, call_dom = NULL;
4837   basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
4838   rtx_insn *insn, *last_interesting_insn = NULL;
4839   bitmap_head need_new, reachable;
4840   vec<basic_block> queue;
4841
4842   if (!SHRINK_WRAPPING_ENABLED)
4843     return false;
4844
4845   bitmap_initialize (&need_new, 0);
4846   bitmap_initialize (&reachable, 0);
4847   queue.create (n_basic_blocks_for_fn (cfun));
4848
4849   FOR_EACH_BB_FN (bb, cfun)
4850     FOR_BB_INSNS (bb, insn)
4851       if (CALL_P (insn) && !SIBLING_CALL_P (insn))
4852         {
4853           if (bb == first)
4854             {
4855               bitmap_clear (&need_new);
4856               bitmap_clear (&reachable);
4857               queue.release ();
4858               return false;
4859             }
4860
4861           bitmap_set_bit (&need_new, bb->index);
4862           bitmap_set_bit (&reachable, bb->index);
4863           queue.quick_push (bb);
4864           break;
4865         }
4866
4867   if (queue.is_empty ())
4868     {
4869       bitmap_clear (&need_new);
4870       bitmap_clear (&reachable);
4871       queue.release ();
4872       return false;
4873     }
4874
4875   while (!queue.is_empty ())
4876     {
4877       edge e;
4878       edge_iterator ei;
4879
4880       bb = queue.pop ();
4881       FOR_EACH_EDGE (e, ei, bb->succs)
4882         if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
4883             && bitmap_set_bit (&reachable, e->dest->index))
4884           queue.quick_push (e->dest);
4885     }
4886   queue.release ();
4887
4888   FOR_BB_INSNS (first, insn)
4889     {
4890       rtx dest = interesting_dest_for_shprep (insn, NULL);
4891       if (!dest)
4892         continue;
4893
4894       if (DF_REG_DEF_COUNT (REGNO (dest)) > 1)
4895         {
4896           bitmap_clear (&need_new);
4897           bitmap_clear (&reachable);
4898           return false;
4899         }
4900
4901       for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
4902            use;
4903            use = DF_REF_NEXT_REG (use))
4904         {
4905           int ubbi = DF_REF_BB (use)->index;
4906           if (bitmap_bit_p (&reachable, ubbi))
4907             bitmap_set_bit (&need_new, ubbi);
4908         }
4909       last_interesting_insn = insn;
4910     }
4911
4912   bitmap_clear (&reachable);
4913   if (!last_interesting_insn)
4914     {
4915       bitmap_clear (&need_new);
4916       return false;
4917     }
4918
4919   call_dom = nearest_common_dominator_for_set (CDI_DOMINATORS, &need_new);
4920   bitmap_clear (&need_new);
4921   if (call_dom == first)
4922     return false;
4923
4924   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4925   while (bb_loop_depth (call_dom) > 0)
4926     call_dom = get_immediate_dominator (CDI_DOMINATORS, call_dom);
4927   loop_optimizer_finalize ();
4928
4929   if (call_dom == first)
4930     return false;
4931
4932   calculate_dominance_info (CDI_POST_DOMINATORS);
4933   if (dominated_by_p (CDI_POST_DOMINATORS, first, call_dom))
4934     {
4935       free_dominance_info (CDI_POST_DOMINATORS);
4936       return false;
4937     }
4938   free_dominance_info (CDI_POST_DOMINATORS);
4939
4940   if (dump_file)
4941     fprintf (dump_file, "Will split live ranges of parameters at BB %i\n",
4942              call_dom->index);
4943
4944   bool ret = false;
4945   FOR_BB_INSNS (first, insn)
4946     {
4947       rtx dest = interesting_dest_for_shprep (insn, call_dom);
4948       if (!dest || dest == pic_offset_table_rtx)
4949         continue;
4950
4951       rtx newreg = NULL_RTX;
4952       df_ref use, next;
4953       for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
4954         {
4955           rtx_insn *uin = DF_REF_INSN (use);
4956           next = DF_REF_NEXT_REG (use);
4957
4958           basic_block ubb = BLOCK_FOR_INSN (uin);
4959           if (ubb == call_dom
4960               || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
4961             {
4962               if (!newreg)
4963                 newreg = ira_create_new_reg (dest);
4964               validate_change (uin, DF_REF_REAL_LOC (use), newreg, true);
4965             }
4966         }
4967
4968       if (newreg)
4969         {
4970           rtx new_move = gen_move_insn (newreg, dest);
4971           emit_insn_after (new_move, bb_note (call_dom));
4972           if (dump_file)
4973             {
4974               fprintf (dump_file, "Split live-range of register ");
4975               print_rtl_single (dump_file, dest);
4976             }
4977           ret = true;
4978         }
4979
4980       if (insn == last_interesting_insn)
4981         break;
4982     }
4983   apply_change_group ();
4984   return ret;
4985 }
4986
4987 /* Perform the second half of the transformation started in
4988    find_moveable_pseudos.  We look for instances where the newly introduced
4989    pseudo remains unallocated, and remove it by moving the definition to
4990    just before its use, replacing the move instruction generated by
4991    find_moveable_pseudos.  */
4992 static void
4993 move_unallocated_pseudos (void)
4994 {
4995   int i;
4996   for (i = first_moveable_pseudo; i < last_moveable_pseudo; i++)
4997     if (reg_renumber[i] < 0)
4998       {
4999         int idx = i - first_moveable_pseudo;
5000         rtx other_reg = pseudo_replaced_reg[idx];
5001         rtx_insn *def_insn = DF_REF_INSN (DF_REG_DEF_CHAIN (i));
5002         /* The use must follow all definitions of OTHER_REG, so we can
5003            insert the new definition immediately after any of them.  */
5004         df_ref other_def = DF_REG_DEF_CHAIN (REGNO (other_reg));
5005         rtx_insn *move_insn = DF_REF_INSN (other_def);
5006         rtx_insn *newinsn = emit_insn_after (PATTERN (def_insn), move_insn);
5007         rtx set;
5008         int success;
5009
5010         if (dump_file)
5011           fprintf (dump_file, "moving def of %d (insn %d now) ",
5012                    REGNO (other_reg), INSN_UID (def_insn));
5013
5014         delete_insn (move_insn);
5015         while ((other_def = DF_REG_DEF_CHAIN (REGNO (other_reg))))
5016           delete_insn (DF_REF_INSN (other_def));
5017         delete_insn (def_insn);
5018
5019         set = single_set (newinsn);
5020         success = validate_change (newinsn, &SET_DEST (set), other_reg, 0);
5021         gcc_assert (success);
5022         if (dump_file)
5023           fprintf (dump_file, " %d) rather than keep unallocated replacement %d\n",
5024                    INSN_UID (newinsn), i);
5025         SET_REG_N_REFS (i, 0);
5026       }
5027 }
5028 \f
5029 /* If the backend knows where to allocate pseudos for hard
5030    register initial values, register these allocations now.  */
5031 static void
5032 allocate_initial_values (void)
5033 {
5034   if (targetm.allocate_initial_value)
5035     {
5036       rtx hreg, preg, x;
5037       int i, regno;
5038
5039       for (i = 0; HARD_REGISTER_NUM_P (i); i++)
5040         {
5041           if (! initial_value_entry (i, &hreg, &preg))
5042             break;
5043
5044           x = targetm.allocate_initial_value (hreg);
5045           regno = REGNO (preg);
5046           if (x && REG_N_SETS (regno) <= 1)
5047             {
5048               if (MEM_P (x))
5049                 reg_equiv_memory_loc (regno) = x;
5050               else
5051                 {
5052                   basic_block bb;
5053                   int new_regno;
5054
5055                   gcc_assert (REG_P (x));
5056                   new_regno = REGNO (x);
5057                   reg_renumber[regno] = new_regno;
5058                   /* Poke the regno right into regno_reg_rtx so that even
5059                      fixed regs are accepted.  */
5060                   SET_REGNO (preg, new_regno);
5061                   /* Update global register liveness information.  */
5062                   FOR_EACH_BB_FN (bb, cfun)
5063                     {
5064                       if (REGNO_REG_SET_P (df_get_live_in (bb), regno))
5065                         SET_REGNO_REG_SET (df_get_live_in (bb), new_regno);
5066                       if (REGNO_REG_SET_P (df_get_live_out (bb), regno))
5067                         SET_REGNO_REG_SET (df_get_live_out (bb), new_regno);
5068                     }
5069                 }
5070             }
5071         }
5072
5073       gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER,
5074                                                   &hreg, &preg));
5075     }
5076 }
5077 \f
5078
5079 /* True when we use LRA instead of reload pass for the current
5080    function.  */
5081 bool ira_use_lra_p;
5082
5083 /* True if we have allocno conflicts.  It is false for non-optimized
5084    mode or when the conflict table is too big.  */
5085 bool ira_conflicts_p;
5086
5087 /* Saved between IRA and reload.  */
5088 static int saved_flag_ira_share_spill_slots;
5089
5090 /* This is the main entry of IRA.  */
5091 static void
5092 ira (FILE *f)
5093 {
5094   bool loops_p;
5095   int ira_max_point_before_emit;
5096   int rebuild_p;
5097   bool saved_flag_caller_saves = flag_caller_saves;
5098   enum ira_region saved_flag_ira_region = flag_ira_region;
5099
5100   /* Perform target specific PIC register initialization.  */
5101   targetm.init_pic_reg ();
5102
5103   ira_conflicts_p = optimize > 0;
5104
5105   ira_use_lra_p = targetm.lra_p ();
5106   /* If there are too many pseudos and/or basic blocks (e.g. 10K
5107      pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5108      use simplified and faster algorithms in LRA.  */
5109   lra_simple_p
5110     = (ira_use_lra_p
5111        && max_reg_num () >= (1 << 26) / last_basic_block_for_fn (cfun));
5112   if (lra_simple_p)
5113     {
5114       /* It permits to skip live range splitting in LRA.  */
5115       flag_caller_saves = false;
5116       /* There is no sense to do regional allocation when we use
5117          simplified LRA.  */
5118       flag_ira_region = IRA_REGION_ONE;
5119       ira_conflicts_p = false;
5120     }
5121
5122 #ifndef IRA_NO_OBSTACK
5123   gcc_obstack_init (&ira_obstack);
5124 #endif
5125   bitmap_obstack_initialize (&ira_bitmap_obstack);
5126
5127   /* LRA uses its own infrastructure to handle caller save registers.  */
5128   if (flag_caller_saves && !ira_use_lra_p)
5129     init_caller_save ();
5130
5131   if (flag_ira_verbose < 10)
5132     {
5133       internal_flag_ira_verbose = flag_ira_verbose;
5134       ira_dump_file = f;
5135     }
5136   else
5137     {
5138       internal_flag_ira_verbose = flag_ira_verbose - 10;
5139       ira_dump_file = stderr;
5140     }
5141
5142   setup_prohibited_mode_move_regs ();
5143   decrease_live_ranges_number ();
5144   df_note_add_problem ();
5145
5146   /* DF_LIVE can't be used in the register allocator, too many other
5147      parts of the compiler depend on using the "classic" liveness
5148      interpretation of the DF_LR problem.  See PR38711.
5149      Remove the problem, so that we don't spend time updating it in
5150      any of the df_analyze() calls during IRA/LRA.  */
5151   if (optimize > 1)
5152     df_remove_problem (df_live);
5153   gcc_checking_assert (df_live == NULL);
5154
5155 #ifdef ENABLE_CHECKING
5156   df->changeable_flags |= DF_VERIFY_SCHEDULED;
5157 #endif
5158   df_analyze ();
5159
5160   init_reg_equiv ();
5161   if (ira_conflicts_p)
5162     {
5163       calculate_dominance_info (CDI_DOMINATORS);
5164
5165       if (split_live_ranges_for_shrink_wrap ())
5166         df_analyze ();
5167
5168       free_dominance_info (CDI_DOMINATORS);
5169     }
5170
5171   df_clear_flags (DF_NO_INSN_RESCAN);
5172
5173   regstat_init_n_sets_and_refs ();
5174   regstat_compute_ri ();
5175
5176   /* If we are not optimizing, then this is the only place before
5177      register allocation where dataflow is done.  And that is needed
5178      to generate these warnings.  */
5179   if (warn_clobbered)
5180     generate_setjmp_warnings ();
5181
5182   /* Determine if the current function is a leaf before running IRA
5183      since this can impact optimizations done by the prologue and
5184      epilogue thus changing register elimination offsets.  */
5185   crtl->is_leaf = leaf_function_p ();
5186
5187   if (resize_reg_info () && flag_ira_loop_pressure)
5188     ira_set_pseudo_classes (true, ira_dump_file);
5189
5190   rebuild_p = update_equiv_regs ();
5191   setup_reg_equiv ();
5192   setup_reg_equiv_init ();
5193
5194   if (optimize && rebuild_p)
5195     {
5196       timevar_push (TV_JUMP);
5197       rebuild_jump_labels (get_insns ());
5198       if (purge_all_dead_edges ())
5199         delete_unreachable_blocks ();
5200       timevar_pop (TV_JUMP);
5201     }
5202
5203   allocated_reg_info_size = max_reg_num ();
5204
5205   if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5206     df_analyze ();
5207
5208   /* It is not worth to do such improvement when we use a simple
5209      allocation because of -O0 usage or because the function is too
5210      big.  */
5211   if (ira_conflicts_p)
5212     find_moveable_pseudos ();
5213
5214   max_regno_before_ira = max_reg_num ();
5215   ira_setup_eliminable_regset ();
5216
5217   ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
5218   ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
5219   ira_move_loops_num = ira_additional_jumps_num = 0;
5220
5221   ira_assert (current_loops == NULL);
5222   if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
5223     loop_optimizer_init (AVOID_CFG_MODIFICATIONS | LOOPS_HAVE_RECORDED_EXITS);
5224
5225   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5226     fprintf (ira_dump_file, "Building IRA IR\n");
5227   loops_p = ira_build ();
5228
5229   ira_assert (ira_conflicts_p || !loops_p);
5230
5231   saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
5232   if (too_high_register_pressure_p () || cfun->calls_setjmp)
5233     /* It is just wasting compiler's time to pack spilled pseudos into
5234        stack slots in this case -- prohibit it.  We also do this if
5235        there is setjmp call because a variable not modified between
5236        setjmp and longjmp the compiler is required to preserve its
5237        value and sharing slots does not guarantee it.  */
5238     flag_ira_share_spill_slots = FALSE;
5239
5240   ira_color ();
5241
5242   ira_max_point_before_emit = ira_max_point;
5243
5244   ira_initiate_emit_data ();
5245
5246   ira_emit (loops_p);
5247
5248   max_regno = max_reg_num ();
5249   if (ira_conflicts_p)
5250     {
5251       if (! loops_p)
5252         {
5253           if (! ira_use_lra_p)
5254             ira_initiate_assign ();
5255         }
5256       else
5257         {
5258           expand_reg_info ();
5259
5260           if (ira_use_lra_p)
5261             {
5262               ira_allocno_t a;
5263               ira_allocno_iterator ai;
5264
5265               FOR_EACH_ALLOCNO (a, ai)
5266                 {
5267                   int old_regno = ALLOCNO_REGNO (a);
5268                   int new_regno = REGNO (ALLOCNO_EMIT_DATA (a)->reg);
5269
5270                   ALLOCNO_REGNO (a) = new_regno;
5271
5272                   if (old_regno != new_regno)
5273                     setup_reg_classes (new_regno, reg_preferred_class (old_regno),
5274                                        reg_alternate_class (old_regno),
5275                                        reg_allocno_class (old_regno));
5276                 }
5277
5278             }
5279           else
5280             {
5281               if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5282                 fprintf (ira_dump_file, "Flattening IR\n");
5283               ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
5284             }
5285           /* New insns were generated: add notes and recalculate live
5286              info.  */
5287           df_analyze ();
5288
5289           /* ??? Rebuild the loop tree, but why?  Does the loop tree
5290              change if new insns were generated?  Can that be handled
5291              by updating the loop tree incrementally?  */
5292           loop_optimizer_finalize ();
5293           free_dominance_info (CDI_DOMINATORS);
5294           loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5295                                | LOOPS_HAVE_RECORDED_EXITS);
5296
5297           if (! ira_use_lra_p)
5298             {
5299               setup_allocno_assignment_flags ();
5300               ira_initiate_assign ();
5301               ira_reassign_conflict_allocnos (max_regno);
5302             }
5303         }
5304     }
5305
5306   ira_finish_emit_data ();
5307
5308   setup_reg_renumber ();
5309
5310   calculate_allocation_cost ();
5311
5312 #ifdef ENABLE_IRA_CHECKING
5313   if (ira_conflicts_p)
5314     check_allocation ();
5315 #endif
5316
5317   if (max_regno != max_regno_before_ira)
5318     {
5319       regstat_free_n_sets_and_refs ();
5320       regstat_free_ri ();
5321       regstat_init_n_sets_and_refs ();
5322       regstat_compute_ri ();
5323     }
5324
5325   overall_cost_before = ira_overall_cost;
5326   if (! ira_conflicts_p)
5327     grow_reg_equivs ();
5328   else
5329     {
5330       fix_reg_equiv_init ();
5331
5332 #ifdef ENABLE_IRA_CHECKING
5333       print_redundant_copies ();
5334 #endif
5335       if (! ira_use_lra_p)
5336         {
5337           ira_spilled_reg_stack_slots_num = 0;
5338           ira_spilled_reg_stack_slots
5339             = ((struct ira_spilled_reg_stack_slot *)
5340                ira_allocate (max_regno
5341                              * sizeof (struct ira_spilled_reg_stack_slot)));
5342           memset (ira_spilled_reg_stack_slots, 0,
5343                   max_regno * sizeof (struct ira_spilled_reg_stack_slot));
5344         }
5345     }
5346   allocate_initial_values ();
5347
5348   /* See comment for find_moveable_pseudos call.  */
5349   if (ira_conflicts_p)
5350     move_unallocated_pseudos ();
5351
5352   /* Restore original values.  */
5353   if (lra_simple_p)
5354     {
5355       flag_caller_saves = saved_flag_caller_saves;
5356       flag_ira_region = saved_flag_ira_region;
5357     }
5358 }
5359
5360 static void
5361 do_reload (void)
5362 {
5363   basic_block bb;
5364   bool need_dce;
5365   unsigned pic_offset_table_regno = INVALID_REGNUM;
5366
5367   if (flag_ira_verbose < 10)
5368     ira_dump_file = dump_file;
5369
5370   /* If pic_offset_table_rtx is a pseudo register, then keep it so
5371      after reload to avoid possible wrong usages of hard reg assigned
5372      to it.  */
5373   if (pic_offset_table_rtx
5374       && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
5375     pic_offset_table_regno = REGNO (pic_offset_table_rtx);
5376
5377   timevar_push (TV_RELOAD);
5378   if (ira_use_lra_p)
5379     {
5380       if (current_loops != NULL)
5381         {
5382           loop_optimizer_finalize ();
5383           free_dominance_info (CDI_DOMINATORS);
5384         }
5385       FOR_ALL_BB_FN (bb, cfun)
5386         bb->loop_father = NULL;
5387       current_loops = NULL;
5388
5389       ira_destroy ();
5390
5391       lra (ira_dump_file);
5392       /* ???!!! Move it before lra () when we use ira_reg_equiv in
5393          LRA.  */
5394       vec_free (reg_equivs);
5395       reg_equivs = NULL;
5396       need_dce = false;
5397     }
5398   else
5399     {
5400       df_set_flags (DF_NO_INSN_RESCAN);
5401       build_insn_chain ();
5402
5403       need_dce = reload (get_insns (), ira_conflicts_p);
5404
5405     }
5406
5407   timevar_pop (TV_RELOAD);
5408
5409   timevar_push (TV_IRA);
5410
5411   if (ira_conflicts_p && ! ira_use_lra_p)
5412     {
5413       ira_free (ira_spilled_reg_stack_slots);
5414       ira_finish_assign ();
5415     }
5416
5417   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
5418       && overall_cost_before != ira_overall_cost)
5419     fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
5420
5421   flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
5422
5423   if (! ira_use_lra_p)
5424     {
5425       ira_destroy ();
5426       if (current_loops != NULL)
5427         {
5428           loop_optimizer_finalize ();
5429           free_dominance_info (CDI_DOMINATORS);
5430         }
5431       FOR_ALL_BB_FN (bb, cfun)
5432         bb->loop_father = NULL;
5433       current_loops = NULL;
5434
5435       regstat_free_ri ();
5436       regstat_free_n_sets_and_refs ();
5437     }
5438
5439   if (optimize)
5440     cleanup_cfg (CLEANUP_EXPENSIVE);
5441
5442   finish_reg_equiv ();
5443
5444   bitmap_obstack_release (&ira_bitmap_obstack);
5445 #ifndef IRA_NO_OBSTACK
5446   obstack_free (&ira_obstack, NULL);
5447 #endif
5448
5449   /* The code after the reload has changed so much that at this point
5450      we might as well just rescan everything.  Note that
5451      df_rescan_all_insns is not going to help here because it does not
5452      touch the artificial uses and defs.  */
5453   df_finish_pass (true);
5454   df_scan_alloc (NULL);
5455   df_scan_blocks ();
5456
5457   if (optimize > 1)
5458     {
5459       df_live_add_problem ();
5460       df_live_set_all_dirty ();
5461     }
5462
5463   if (optimize)
5464     df_analyze ();
5465
5466   if (need_dce && optimize)
5467     run_fast_dce ();
5468
5469   /* Diagnose uses of the hard frame pointer when it is used as a global
5470      register.  Often we can get away with letting the user appropriate
5471      the frame pointer, but we should let them know when code generation
5472      makes that impossible.  */
5473   if (global_regs[HARD_FRAME_POINTER_REGNUM] && frame_pointer_needed)
5474     {
5475       tree decl = global_regs_decl[HARD_FRAME_POINTER_REGNUM];
5476       error_at (DECL_SOURCE_LOCATION (current_function_decl),
5477                 "frame pointer required, but reserved");
5478       inform (DECL_SOURCE_LOCATION (decl), "for %qD", decl);
5479     }
5480
5481   if (pic_offset_table_regno != INVALID_REGNUM)
5482     pic_offset_table_rtx = gen_rtx_REG (Pmode, pic_offset_table_regno);
5483
5484   timevar_pop (TV_IRA);
5485 }
5486 \f
5487 /* Run the integrated register allocator.  */
5488
5489 namespace {
5490
5491 const pass_data pass_data_ira =
5492 {
5493   RTL_PASS, /* type */
5494   "ira", /* name */
5495   OPTGROUP_NONE, /* optinfo_flags */
5496   TV_IRA, /* tv_id */
5497   0, /* properties_required */
5498   0, /* properties_provided */
5499   0, /* properties_destroyed */
5500   0, /* todo_flags_start */
5501   TODO_do_not_ggc_collect, /* todo_flags_finish */
5502 };
5503
5504 class pass_ira : public rtl_opt_pass
5505 {
5506 public:
5507   pass_ira (gcc::context *ctxt)
5508     : rtl_opt_pass (pass_data_ira, ctxt)
5509   {}
5510
5511   /* opt_pass methods: */
5512   virtual bool gate (function *)
5513     {
5514       return !targetm.no_register_allocation;
5515     }
5516   virtual unsigned int execute (function *)
5517     {
5518       ira (dump_file);
5519       return 0;
5520     }
5521
5522 }; // class pass_ira
5523
5524 } // anon namespace
5525
5526 rtl_opt_pass *
5527 make_pass_ira (gcc::context *ctxt)
5528 {
5529   return new pass_ira (ctxt);
5530 }
5531
5532 namespace {
5533
5534 const pass_data pass_data_reload =
5535 {
5536   RTL_PASS, /* type */
5537   "reload", /* name */
5538   OPTGROUP_NONE, /* optinfo_flags */
5539   TV_RELOAD, /* tv_id */
5540   0, /* properties_required */
5541   0, /* properties_provided */
5542   0, /* properties_destroyed */
5543   0, /* todo_flags_start */
5544   0, /* todo_flags_finish */
5545 };
5546
5547 class pass_reload : public rtl_opt_pass
5548 {
5549 public:
5550   pass_reload (gcc::context *ctxt)
5551     : rtl_opt_pass (pass_data_reload, ctxt)
5552   {}
5553
5554   /* opt_pass methods: */
5555   virtual bool gate (function *)
5556     {
5557       return !targetm.no_register_allocation;
5558     }
5559   virtual unsigned int execute (function *)
5560     {
5561       do_reload ();
5562       return 0;
5563     }
5564
5565 }; // class pass_reload
5566
5567 } // anon namespace
5568
5569 rtl_opt_pass *
5570 make_pass_reload (gcc::context *ctxt)
5571 {
5572   return new pass_reload (ctxt);
5573 }