gcc/ira.c

   1 /* Integrated Register Allocator (IRA) entry point.
   2    Copyright (C) 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* The integrated register allocator (IRA) is a
  23    regional register allocator performing graph coloring on a top-down
  24    traversal of nested regions.  Graph coloring in a region is based
  25    on Chaitin-Briggs algorithm.  It is called integrated because
  26    register coalescing, register live range splitting, and choosing a
  27    better hard register are done on-the-fly during coloring.  Register
  28    coalescing and choosing a cheaper hard register is done by hard
  29    register preferencing during hard register assigning.  The live
  30    range splitting is a byproduct of the regional register allocation.
  31
  32    Major IRA notions are:
  33
  34      o *Region* is a part of CFG where graph coloring based on
  35        Chaitin-Briggs algorithm is done.  IRA can work on any set of
  36        nested CFG regions forming a tree.  Currently the regions are
  37        the entire function for the root region and natural loops for
  38        the other regions.  Therefore data structure representing a
  39        region is called loop_tree_node.
  40
  41      o *Cover class* is a register class belonging to a set of
  42        non-intersecting register classes containing all of the
  43        hard-registers available for register allocation.  The set of
  44        all cover classes for a target is defined in the corresponding
  45        machine-description file according some criteria.  Such notion
  46        is needed because Chaitin-Briggs algorithm works on
  47        non-intersected register classes.
  48
  49      o *Allocno* represents the live range of a pseudo-register in a
  50        region.  Besides the obvious attributes like the corresponding
  51        pseudo-register number, cover class, conflicting allocnos and
  52        conflicting hard-registers, there are a few allocno attributes
  53        which are important for understanding the allocation algorithm:
  54
  55        - *Live ranges*.  This is a list of ranges of *program
  56          points* where the allocno lives.  Program points represent
  57          places where a pseudo can be born or become dead (there are
  58          approximately two times more program points than the insns)
  59          and they are represented by integers starting with 0.  The
  60          live ranges are used to find conflicts between allocnos of
  61          different cover classes.  They also play very important role
  62          for the transformation of the IRA internal representation of
  63          several regions into a one region representation.  The later is
  64          used during the reload pass work because each allocno
  65          represents all of the corresponding pseudo-registers.
  66
  67        - *Hard-register costs*.  This is a vector of size equal to the
  68          number of available hard-registers of the allocno's cover
  69          class.  The cost of a callee-clobbered hard-register for an
  70          allocno is increased by the cost of save/restore code around
  71          the calls through the given allocno's life.  If the allocno
  72          is a move instruction operand and another operand is a
  73          hard-register of the allocno's cover class, the cost of the
  74          hard-register is decreased by the move cost.
  75
  76          When an allocno is assigned, the hard-register with minimal
  77          full cost is used.  Initially, a hard-register's full cost is
  78          the corresponding value from the hard-register's cost vector.
  79          If the allocno is connected by a *copy* (see below) to
  80          another allocno which has just received a hard-register, the
  81          cost of the hard-register is decreased.  Before choosing a
  82          hard-register for an allocno, the allocno's current costs of
  83          the hard-registers are modified by the conflict hard-register
  84          costs of all of the conflicting allocnos which are not
  85          assigned yet.
  86
  87        - *Conflict hard-register costs*.  This is a vector of the same
  88          size as the hard-register costs vector.  To permit an
  89          unassigned allocno to get a better hard-register, IRA uses
  90          this vector to calculate the final full cost of the
  91          available hard-registers.  Conflict hard-register costs of an
  92          unassigned allocno are also changed with a change of the
  93          hard-register cost of the allocno when a copy involving the
  94          allocno is processed as described above.  This is done to
  95          show other unassigned allocnos that a given allocno prefers
  96          some hard-registers in order to remove the move instruction
  97          corresponding to the copy.
  98
  99      o *Cap*.  If a pseudo-register does not live in a region but
 100        lives in a nested region, IRA creates a special allocno called
 101        a cap in the outer region.  A region cap is also created for a
 102        subregion cap.
 103
 104      o *Copy*.  Allocnos can be connected by copies.  Copies are used
 105        to modify hard-register costs for allocnos during coloring.
 106        Such modifications reflects a preference to use the same
 107        hard-register for the allocnos connected by copies.  Usually
 108        copies are created for move insns (in this case it results in
 109        register coalescing).  But IRA also creates copies for operands
 110        of an insn which should be assigned to the same hard-register
 111        due to constraints in the machine description (it usually
 112        results in removing a move generated in reload to satisfy
 113        the constraints) and copies referring to the allocno which is
 114        the output operand of an instruction and the allocno which is
 115        an input operand dying in the instruction (creation of such
 116        copies results in less register shuffling).  IRA *does not*
 117        create copies between the same register allocnos from different
 118        regions because we use another technique for propagating
 119        hard-register preference on the borders of regions.
 120
 121    Allocnos (including caps) for the upper region in the region tree
 122    *accumulate* information important for coloring from allocnos with
 123    the same pseudo-register from nested regions.  This includes
 124    hard-register and memory costs, conflicts with hard-registers,
 125    allocno conflicts, allocno copies and more.  *Thus, attributes for
 126    allocnos in a region have the same values as if the region had no
 127    subregions*.  It means that attributes for allocnos in the
 128    outermost region corresponding to the function have the same values
 129    as though the allocation used only one region which is the entire
 130    function.  It also means that we can look at IRA work as if the
 131    first IRA did allocation for all function then it improved the
 132    allocation for loops then their subloops and so on.
 133
 134    IRA major passes are:
 135
 136      o Building IRA internal representation which consists of the
 137        following subpasses:
 138
 139        * First, IRA builds regions and creates allocnos (file
 140          ira-build.c) and initializes most of their attributes.
 141
 142        * Then IRA finds a cover class for each allocno and calculates
 143          its initial (non-accumulated) cost of memory and each
 144          hard-register of its cover class (file ira-cost.c).
 145
 146        * IRA creates live ranges of each allocno, calulates register
 147          pressure for each cover class in each region, sets up
 148          conflict hard registers for each allocno and info about calls
 149          the allocno lives through (file ira-lives.c).
 150
 151        * IRA removes low register pressure loops from the regions
 152          mostly to speed IRA up (file ira-build.c).
 153
 154        * IRA propagates accumulated allocno info from lower region
 155          allocnos to corresponding upper region allocnos (file
 156          ira-build.c).
 157
 158        * IRA creates all caps (file ira-build.c).
 159
 160        * Having live-ranges of allocnos and their cover classes, IRA
 161          creates conflicting allocnos of the same cover class for each
 162          allocno.  Conflicting allocnos are stored as a bit vector or
 163          array of pointers to the conflicting allocnos whatever is
 164          more profitable (file ira-conflicts.c).  At this point IRA
 165          creates allocno copies.
 166
 167      o Coloring.  Now IRA has all necessary info to start graph coloring
 168        process.  It is done in each region on top-down traverse of the
 169        region tree (file ira-color.c).  There are following subpasses:
 170
 171        * Putting allocnos onto the coloring stack.  IRA uses Briggs
 172          optimistic coloring which is a major improvement over
 173          Chaitin's coloring.  Therefore IRA does not spill allocnos at
 174          this point.  There is some freedom in the order of putting
 175          allocnos on the stack which can affect the final result of
 176          the allocation.  IRA uses some heuristics to improve the order.
 177
 178        * Popping the allocnos from the stack and assigning them hard
 179          registers.  If IRA can not assign a hard register to an
 180          allocno and the allocno is coalesced, IRA undoes the
 181          coalescing and puts the uncoalesced allocnos onto the stack in
 182          the hope that some such allocnos will get a hard register
 183          separately.  If IRA fails to assign hard register or memory
 184          is more profitable for it, IRA spills the allocno.  IRA
 185          assigns the allocno the hard-register with minimal full
 186          allocation cost which reflects the cost of usage of the
 187          hard-register for the allocno and cost of usage of the
 188          hard-register for allocnos conflicting with given allocno.
 189
 190        * After allono assigning in the region, IRA modifies the hard
 191          register and memory costs for the corresponding allocnos in
 192          the subregions to reflect the cost of possible loads, stores,
 193          or moves on the border of the region and its subregions.
 194          When default regional allocation algorithm is used
 195          (-fira-algorithm=mixed), IRA just propagates the assignment
 196          for allocnos if the register pressure in the region for the
 197          corresponding cover class is less than number of available
 198          hard registers for given cover class.
 199
 200      o Spill/restore code moving.  When IRA performs an allocation
 201        by traversing regions in top-down order, it does not know what
 202        happens below in the region tree.  Therefore, sometimes IRA
 203        misses opportunities to perform a better allocation.  A simple
 204        optimization tries to improve allocation in a region having
 205        subregions and containing in another region.  If the
 206        corresponding allocnos in the subregion are spilled, it spills
 207        the region allocno if it is profitable.  The optimization
 208        implements a simple iterative algorithm performing profitable
 209        transformations while they are still possible.  It is fast in
 210        practice, so there is no real need for a better time complexity
 211        algorithm.
 212
 213      o Code change.  After coloring, two allocnos representing the same
 214        pseudo-register outside and inside a region respectively may be
 215        assigned to different locations (hard-registers or memory).  In
 216        this case IRA creates and uses a new pseudo-register inside the
 217        region and adds code to move allocno values on the region's
 218        borders.  This is done during top-down traversal of the regions
 219        (file ira-emit.c).  In some complicated cases IRA can create a
 220        new allocno to move allocno values (e.g. when a swap of values
 221        stored in two hard-registers is needed).  At this stage, the
 222        new allocno is marked as spilled.  IRA still creates the
 223        pseudo-register and the moves on the region borders even when
 224        both allocnos were assigned to the same hard-register.  If the
 225        reload pass spills a pseudo-register for some reason, the
 226        effect will be smaller because another allocno will still be in
 227        the hard-register.  In most cases, this is better then spilling
 228        both allocnos.  If reload does not change the allocation
 229        for the two pseudo-registers, the trivial move will be removed
 230        by post-reload optimizations.  IRA does not generate moves for
 231        allocnos assigned to the same hard register when the default
 232        regional allocation algorithm is used and the register pressure
 233        in the region for the corresponding allocno cover class is less
 234        than number of available hard registers for given cover class.
 235        IRA also does some optimizations to remove redundant stores and
 236        to reduce code duplication on the region borders.
 237
 238      o Flattening internal representation.  After changing code, IRA
 239        transforms its internal representation for several regions into
 240        one region representation (file ira-build.c).  This process is
 241        called IR flattening.  Such process is more complicated than IR
 242        rebuilding would be, but is much faster.
 243
 244      o After IR flattening, IRA tries to assign hard registers to all
 245        spilled allocnos.  This is impelemented by a simple and fast
 246        priority coloring algorithm (see function
 247        ira_reassign_conflict_allocnos::ira-color.c).  Here new allocnos
 248        created during the code change pass can be assigned to hard
 249        registers.
 250
 251      o At the end IRA calls the reload pass.  The reload pass
 252        communicates with IRA through several functions in file
 253        ira-color.c to improve its decisions in
 254
 255        * sharing stack slots for the spilled pseudos based on IRA info
 256          about pseudo-register conflicts.
 257
 258        * reassigning hard-registers to all spilled pseudos at the end
 259          of each reload iteration.
 260
 261        * choosing a better hard-register to spill based on IRA info
 262          about pseudo-register live ranges and the register pressure
 263          in places where the pseudo-register lives.
 264
 265    IRA uses a lot of data representing the target processors.  These
 266    data are initilized in file ira.c.
 267
 268    If function has no loops (or the loops are ignored when
 269    -fira-algorithm=CB is used), we have classic Chaitin-Briggs
 270    coloring (only instead of separate pass of coalescing, we use hard
 271    register preferencing).  In such case, IRA works much faster
 272    because many things are not made (like IR flattening, the
 273    spill/restore optimization, and the code change).
 274
 275    Literature is worth to read for better understanding the code:
 276
 277    o Preston Briggs, Keith D. Cooper, Linda Torczon.  Improvements to
 278      Graph Coloring Register Allocation.
 279
 280    o David Callahan, Brian Koblenz.  Register allocation via
 281      hierarchical graph coloring.
 282
 283    o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
 284      Coloring Register Allocation: A Study of the Chaitin-Briggs and
 285      Callahan-Koblenz Algorithms.
 286
 287    o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
 288      Register Allocation Based on Graph Fusion.
 289
 290    o Vladimir Makarov. The Integrated Register Allocator for GCC.
 291
 292    o Vladimir Makarov.  The top-down register allocator for irregular
 293      register file architectures.
 294
 295 */
 296
 297
 298 #include "config.h"
 299 #include "system.h"
 300 #include "coretypes.h"
 301 #include "tm.h"
 302 #include "regs.h"
 303 #include "rtl.h"
 304 #include "tm_p.h"
 305 #include "target.h"
 306 #include "flags.h"
 307 #include "obstack.h"
 308 #include "bitmap.h"
 309 #include "hard-reg-set.h"
 310 #include "basic-block.h"
 311 #include "df.h"
 312 #include "expr.h"
 313 #include "recog.h"
 314 #include "params.h"
 315 #include "timevar.h"
 316 #include "tree-pass.h"
 317 #include "output.h"
 318 #include "except.h"
 319 #include "reload.h"
 320 #include "diagnostic-core.h"
 321 #include "integrate.h"
 322 #include "ggc.h"
 323 #include "ira-int.h"
 324
 325
 326 struct target_ira default_target_ira;
 327 struct target_ira_int default_target_ira_int;
 328 #if SWITCHABLE_TARGET
 329 struct target_ira *this_target_ira = &default_target_ira;
 330 struct target_ira_int *this_target_ira_int = &default_target_ira_int;
 331 #endif
 332
 333 /* A modified value of flag `-fira-verbose' used internally.  */
 334 int internal_flag_ira_verbose;
 335
 336 /* Dump file of the allocator if it is not NULL.  */
 337 FILE *ira_dump_file;
 338
 339 /* The number of elements in the following array.  */
 340 int ira_spilled_reg_stack_slots_num;
 341
 342 /* The following array contains info about spilled pseudo-registers
 343    stack slots used in current function so far.  */
 344 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
 345
 346 /* Correspondingly overall cost of the allocation, cost of the
 347    allocnos assigned to hard-registers, cost of the allocnos assigned
 348    to memory, cost of loads, stores and register move insns generated
 349    for pseudo-register live range splitting (see ira-emit.c).  */
 350 int ira_overall_cost;
 351 int ira_reg_cost, ira_mem_cost;
 352 int ira_load_cost, ira_store_cost, ira_shuffle_cost;
 353 int ira_move_loops_num, ira_additional_jumps_num;
 354
 355 /* All registers that can be eliminated.  */
 356
 357 HARD_REG_SET eliminable_regset;
 358
 359 /* Temporary hard reg set used for a different calculation.  */
 360 static HARD_REG_SET temp_hard_regset;
 361
 362 \f
 363
 364 /* The function sets up the map IRA_REG_MODE_HARD_REGSET.  */
 365 static void
 366 setup_reg_mode_hard_regset (void)
 367 {
 368   int i, m, hard_regno;
 369
 370   for (m = 0; m < NUM_MACHINE_MODES; m++)
 371     for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
 372       {
 373         CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
 374         for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
 375           if (hard_regno + i < FIRST_PSEUDO_REGISTER)
 376             SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
 377                               hard_regno + i);
 378       }
 379 }
 380
 381 \f
 382 #define no_unit_alloc_regs \
 383   (this_target_ira_int->x_no_unit_alloc_regs)
 384
 385 /* The function sets up the three arrays declared above.  */
 386 static void
 387 setup_class_hard_regs (void)
 388 {
 389   int cl, i, hard_regno, n;
 390   HARD_REG_SET processed_hard_reg_set;
 391
 392   ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
 393   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
 394     {
 395       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 396       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 397       CLEAR_HARD_REG_SET (processed_hard_reg_set);
 398       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 399         {
 400           ira_non_ordered_class_hard_regs[cl][i] = -1;
 401           ira_class_hard_reg_index[cl][i] = -1;
 402         }
 403       for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 404         {
 405 #ifdef REG_ALLOC_ORDER
 406           hard_regno = reg_alloc_order[i];
 407 #else
 408           hard_regno = i;
 409 #endif
 410           if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
 411             continue;
 412           SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
 413           if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
 414             ira_class_hard_reg_index[cl][hard_regno] = -1;
 415           else
 416             {
 417               ira_class_hard_reg_index[cl][hard_regno] = n;
 418               ira_class_hard_regs[cl][n++] = hard_regno;
 419             }
 420         }
 421       ira_class_hard_regs_num[cl] = n;
 422       for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 423         if (TEST_HARD_REG_BIT (temp_hard_regset, i))
 424           ira_non_ordered_class_hard_regs[cl][n++] = i;
 425       ira_assert (ira_class_hard_regs_num[cl] == n);
 426     }
 427 }
 428
 429 /* Set up IRA_AVAILABLE_CLASS_REGS.  */
 430 static void
 431 setup_available_class_regs (void)
 432 {
 433   int i, j;
 434
 435   memset (ira_available_class_regs, 0, sizeof (ira_available_class_regs));
 436   for (i = 0; i < N_REG_CLASSES; i++)
 437     {
 438       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
 439       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 440       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
 441         if (TEST_HARD_REG_BIT (temp_hard_regset, j))
 442           ira_available_class_regs[i]++;
 443     }
 444 }
 445
 446 /* Set up global variables defining info about hard registers for the
 447    allocation.  These depend on USE_HARD_FRAME_P whose TRUE value means
 448    that we can use the hard frame pointer for the allocation.  */
 449 static void
 450 setup_alloc_regs (bool use_hard_frame_p)
 451 {
 452 #ifdef ADJUST_REG_ALLOC_ORDER
 453   ADJUST_REG_ALLOC_ORDER;
 454 #endif
 455   COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
 456   if (! use_hard_frame_p)
 457     SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
 458   setup_class_hard_regs ();
 459   setup_available_class_regs ();
 460 }
 461
 462 \f
 463
 464 /* Set up IRA_MEMORY_MOVE_COST, IRA_REGISTER_MOVE_COST.  */
 465 static void
 466 setup_class_subset_and_memory_move_costs (void)
 467 {
 468   int cl, cl2, mode;
 469   HARD_REG_SET temp_hard_regset2;
 470
 471   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
 472     ira_memory_move_cost[mode][NO_REGS][0]
 473       = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
 474   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
 475     {
 476       if (cl != (int) NO_REGS)
 477         for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
 478           {
 479             ira_memory_move_cost[mode][cl][0] =
 480               memory_move_cost ((enum machine_mode) mode,
 481                                 (enum reg_class) cl, false);
 482             ira_memory_move_cost[mode][cl][1] =
 483               memory_move_cost ((enum machine_mode) mode,
 484                                 (enum reg_class) cl, true);
 485             /* Costs for NO_REGS are used in cost calculation on the
 486                1st pass when the preferred register classes are not
 487                known yet.  In this case we take the best scenario.  */
 488             if (ira_memory_move_cost[mode][NO_REGS][0]
 489                 > ira_memory_move_cost[mode][cl][0])
 490               ira_memory_move_cost[mode][NO_REGS][0]
 491                 = ira_memory_move_cost[mode][cl][0];
 492             if (ira_memory_move_cost[mode][NO_REGS][1]
 493                 > ira_memory_move_cost[mode][cl][1])
 494               ira_memory_move_cost[mode][NO_REGS][1]
 495                 = ira_memory_move_cost[mode][cl][1];
 496           }
 497       for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
 498         {
 499           COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 500           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 501           COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
 502           AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
 503           ira_class_subset_p[cl][cl2]
 504             = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
 505         }
 506     }
 507 }
 508
 509 \f
 510
 511 /* Define the following macro if allocation through malloc if
 512    preferable.  */
 513 #define IRA_NO_OBSTACK
 514
 515 #ifndef IRA_NO_OBSTACK
 516 /* Obstack used for storing all dynamic data (except bitmaps) of the
 517    IRA.  */
 518 static struct obstack ira_obstack;
 519 #endif
 520
 521 /* Obstack used for storing all bitmaps of the IRA.  */
 522 static struct bitmap_obstack ira_bitmap_obstack;
 523
 524 /* Allocate memory of size LEN for IRA data.  */
 525 void *
 526 ira_allocate (size_t len)
 527 {
 528   void *res;
 529
 530 #ifndef IRA_NO_OBSTACK
 531   res = obstack_alloc (&ira_obstack, len);
 532 #else
 533   res = xmalloc (len);
 534 #endif
 535   return res;
 536 }
 537
 538 /* Reallocate memory PTR of size LEN for IRA data.  */
 539 void *
 540 ira_reallocate (void *ptr, size_t len)
 541 {
 542   void *res;
 543
 544 #ifndef IRA_NO_OBSTACK
 545   res = obstack_alloc (&ira_obstack, len);
 546 #else
 547   res = xrealloc (ptr, len);
 548 #endif
 549   return res;
 550 }
 551
 552 /* Free memory ADDR allocated for IRA data.  */
 553 void
 554 ira_free (void *addr ATTRIBUTE_UNUSED)
 555 {
 556 #ifndef IRA_NO_OBSTACK
 557   /* do nothing */
 558 #else
 559   free (addr);
 560 #endif
 561 }
 562
 563
 564 /* Allocate and returns bitmap for IRA.  */
 565 bitmap
 566 ira_allocate_bitmap (void)
 567 {
 568   return BITMAP_ALLOC (&ira_bitmap_obstack);
 569 }
 570
 571 /* Free bitmap B allocated for IRA.  */
 572 void
 573 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
 574 {
 575   /* do nothing */
 576 }
 577
 578 \f
 579
 580 /* Output information about allocation of all allocnos (except for
 581    caps) into file F.  */
 582 void
 583 ira_print_disposition (FILE *f)
 584 {
 585   int i, n, max_regno;
 586   ira_allocno_t a;
 587   basic_block bb;
 588
 589   fprintf (f, "Disposition:");
 590   max_regno = max_reg_num ();
 591   for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 592     for (a = ira_regno_allocno_map[i];
 593          a != NULL;
 594          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 595       {
 596         if (n % 4 == 0)
 597           fprintf (f, "\n");
 598         n++;
 599         fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 600         if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 601           fprintf (f, "b%-3d", bb->index);
 602         else
 603           fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 604         if (ALLOCNO_HARD_REGNO (a) >= 0)
 605           fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
 606         else
 607           fprintf (f, " mem");
 608       }
 609   fprintf (f, "\n");
 610 }
 611
 612 /* Outputs information about allocation of all allocnos into
 613    stderr.  */
 614 void
 615 ira_debug_disposition (void)
 616 {
 617   ira_print_disposition (stderr);
 618 }
 619
 620 \f
 621 #define alloc_reg_class_subclasses \
 622   (this_target_ira_int->x_alloc_reg_class_subclasses)
 623
 624 /* Initialize the table of subclasses of each reg class.  */
 625 static void
 626 setup_reg_subclasses (void)
 627 {
 628   int i, j;
 629   HARD_REG_SET temp_hard_regset2;
 630
 631   for (i = 0; i < N_REG_CLASSES; i++)
 632     for (j = 0; j < N_REG_CLASSES; j++)
 633       alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
 634
 635   for (i = 0; i < N_REG_CLASSES; i++)
 636     {
 637       if (i == (int) NO_REGS)
 638         continue;
 639
 640       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
 641       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 642       if (hard_reg_set_empty_p (temp_hard_regset))
 643         continue;
 644       for (j = 0; j < N_REG_CLASSES; j++)
 645         if (i != j)
 646           {
 647             enum reg_class *p;
 648
 649             COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
 650             AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
 651             if (! hard_reg_set_subset_p (temp_hard_regset,
 652                                          temp_hard_regset2))
 653               continue;
 654             p = &alloc_reg_class_subclasses[j][0];
 655             while (*p != LIM_REG_CLASSES) p++;
 656             *p = (enum reg_class) i;
 657           }
 658     }
 659 }
 660
 661 \f
 662
 663 /* Set the four global variables defined above.  */
 664 static void
 665 setup_cover_and_important_classes (void)
 666 {
 667   int i, j, n, cl;
 668   bool set_p;
 669   const reg_class_t *cover_classes;
 670   HARD_REG_SET temp_hard_regset2;
 671   static enum reg_class classes[LIM_REG_CLASSES + 1];
 672
 673   if (targetm.ira_cover_classes == NULL)
 674     cover_classes = NULL;
 675   else
 676     cover_classes = targetm.ira_cover_classes ();
 677   if (cover_classes == NULL)
 678     ira_assert (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY);
 679   else
 680     {
 681       for (i = 0; (cl = cover_classes[i]) != LIM_REG_CLASSES; i++)
 682         classes[i] = (enum reg_class) cl;
 683       classes[i] = LIM_REG_CLASSES;
 684     }
 685
 686   if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
 687     {
 688       n = 0;
 689       for (i = 0; i <= LIM_REG_CLASSES; i++)
 690         {
 691           if (i == NO_REGS)
 692             continue;
 693 #ifdef CONSTRAINT_NUM_DEFINED_P
 694           for (j = 0; j < CONSTRAINT__LIMIT; j++)
 695             if ((int) REG_CLASS_FOR_CONSTRAINT ((enum constraint_num) j) == i)
 696               break;
 697           if (j < CONSTRAINT__LIMIT)
 698             {
 699               classes[n++] = (enum reg_class) i;
 700               continue;
 701             }
 702 #endif
 703           COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
 704           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 705           for (j = 0; j < LIM_REG_CLASSES; j++)
 706             {
 707               if (i == j)
 708                 continue;
 709               COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
 710               AND_COMPL_HARD_REG_SET (temp_hard_regset2,
 711                                       no_unit_alloc_regs);
 712               if (hard_reg_set_equal_p (temp_hard_regset,
 713                                         temp_hard_regset2))
 714                     break;
 715             }
 716           if (j >= i)
 717             classes[n++] = (enum reg_class) i;
 718         }
 719       classes[n] = LIM_REG_CLASSES;
 720     }
 721
 722   ira_reg_class_cover_size = 0;
 723   for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
 724     {
 725       for (j = 0; j < i; j++)
 726         if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
 727             && reg_classes_intersect_p ((enum reg_class) cl, classes[j]))
 728           gcc_unreachable ();
 729       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 730       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 731       if (! hard_reg_set_empty_p (temp_hard_regset))
 732         ira_reg_class_cover[ira_reg_class_cover_size++] = (enum reg_class) cl;
 733     }
 734   ira_important_classes_num = 0;
 735   for (cl = 0; cl < N_REG_CLASSES; cl++)
 736     {
 737       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 738       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 739       if (! hard_reg_set_empty_p (temp_hard_regset))
 740         {
 741           set_p = false;
 742           for (j = 0; j < ira_reg_class_cover_size; j++)
 743             {
 744               COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 745               AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 746               COPY_HARD_REG_SET (temp_hard_regset2,
 747                                  reg_class_contents[ira_reg_class_cover[j]]);
 748               AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
 749               if ((enum reg_class) cl == ira_reg_class_cover[j]
 750                   || hard_reg_set_equal_p (temp_hard_regset,
 751                                            temp_hard_regset2))
 752                 break;
 753               else if (hard_reg_set_subset_p (temp_hard_regset,
 754                                               temp_hard_regset2))
 755                 set_p = true;
 756             }
 757           if (set_p && j >= ira_reg_class_cover_size)
 758             ira_important_classes[ira_important_classes_num++]
 759               = (enum reg_class) cl;
 760         }
 761     }
 762   for (j = 0; j < ira_reg_class_cover_size; j++)
 763     ira_important_classes[ira_important_classes_num++]
 764       = ira_reg_class_cover[j];
 765 }
 766
 767 /* Set up array IRA_CLASS_TRANSLATE.  */
 768 static void
 769 setup_class_translate (void)
 770 {
 771   int cl, mode;
 772   enum reg_class cover_class, best_class, *cl_ptr;
 773   int i, cost, min_cost, best_cost;
 774
 775   for (cl = 0; cl < N_REG_CLASSES; cl++)
 776     ira_class_translate[cl] = NO_REGS;
 777
 778   if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
 779     for (cl = 0; cl < LIM_REG_CLASSES; cl++)
 780       {
 781         COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 782         AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 783         for (i = 0; i < ira_reg_class_cover_size; i++)
 784           {
 785             HARD_REG_SET temp_hard_regset2;
 786
 787             cover_class = ira_reg_class_cover[i];
 788             COPY_HARD_REG_SET (temp_hard_regset2,
 789                                reg_class_contents[cover_class]);
 790             AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
 791             if (hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2))
 792               ira_class_translate[cl] = cover_class;
 793           }
 794       }
 795   for (i = 0; i < ira_reg_class_cover_size; i++)
 796     {
 797       cover_class = ira_reg_class_cover[i];
 798       if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY)
 799         for (cl_ptr = &alloc_reg_class_subclasses[cover_class][0];
 800              (cl = *cl_ptr) != LIM_REG_CLASSES;
 801              cl_ptr++)
 802           {
 803             if (ira_class_translate[cl] == NO_REGS)
 804               ira_class_translate[cl] = cover_class;
 805 #ifdef ENABLE_IRA_CHECKING
 806             else
 807               {
 808                 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 809                 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 810                 if (! hard_reg_set_empty_p (temp_hard_regset))
 811                   gcc_unreachable ();
 812               }
 813 #endif
 814           }
 815       ira_class_translate[cover_class] = cover_class;
 816     }
 817   /* For classes which are not fully covered by a cover class (in
 818      other words covered by more one cover class), use the cheapest
 819      cover class.  */
 820   for (cl = 0; cl < N_REG_CLASSES; cl++)
 821     {
 822       if (cl == NO_REGS || ira_class_translate[cl] != NO_REGS)
 823         continue;
 824       best_class = NO_REGS;
 825       best_cost = INT_MAX;
 826       for (i = 0; i < ira_reg_class_cover_size; i++)
 827         {
 828           cover_class = ira_reg_class_cover[i];
 829           COPY_HARD_REG_SET (temp_hard_regset,
 830                              reg_class_contents[cover_class]);
 831           AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
 832           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 833           if (! hard_reg_set_empty_p (temp_hard_regset))
 834             {
 835               min_cost = INT_MAX;
 836               for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
 837                 {
 838                   cost = (ira_memory_move_cost[mode][cl][0]
 839                           + ira_memory_move_cost[mode][cl][1]);
 840                   if (min_cost > cost)
 841                     min_cost = cost;
 842                 }
 843               if (best_class == NO_REGS || best_cost > min_cost)
 844                 {
 845                   best_class = cover_class;
 846                   best_cost = min_cost;
 847                 }
 848             }
 849         }
 850       ira_class_translate[cl] = best_class;
 851     }
 852 }
 853
 854 /* Order numbers of cover classes in original target cover class
 855    array, -1 for non-cover classes.  This is only live during
 856    reorder_important_classes.  */
 857 static int cover_class_order[N_REG_CLASSES];
 858
 859 /* The function used to sort the important classes.  */
 860 static int
 861 comp_reg_classes_func (const void *v1p, const void *v2p)
 862 {
 863   enum reg_class cl1 = *(const enum reg_class *) v1p;
 864   enum reg_class cl2 = *(const enum reg_class *) v2p;
 865   int diff;
 866
 867   cl1 = ira_class_translate[cl1];
 868   cl2 = ira_class_translate[cl2];
 869   if (cl1 != NO_REGS && cl2 != NO_REGS
 870       && (diff = cover_class_order[cl1] - cover_class_order[cl2]) != 0)
 871     return diff;
 872   return (int) cl1 - (int) cl2;
 873 }
 874
 875 /* Reorder important classes according to the order of their cover
 876    classes.  */
 877 static void
 878 reorder_important_classes (void)
 879 {
 880   int i;
 881
 882   for (i = 0; i < N_REG_CLASSES; i++)
 883     cover_class_order[i] = -1;
 884   for (i = 0; i < ira_reg_class_cover_size; i++)
 885     cover_class_order[ira_reg_class_cover[i]] = i;
 886   qsort (ira_important_classes, ira_important_classes_num,
 887          sizeof (enum reg_class), comp_reg_classes_func);
 888 }
 889
 890 /* Set up the above reg class relations.  */
 891 static void
 892 setup_reg_class_relations (void)
 893 {
 894   int i, cl1, cl2, cl3;
 895   HARD_REG_SET intersection_set, union_set, temp_set2;
 896   bool important_class_p[N_REG_CLASSES];
 897
 898   memset (important_class_p, 0, sizeof (important_class_p));
 899   for (i = 0; i < ira_important_classes_num; i++)
 900     important_class_p[ira_important_classes[i]] = true;
 901   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
 902     {
 903       ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
 904       for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
 905         {
 906           ira_reg_classes_intersect_p[cl1][cl2] = false;
 907           ira_reg_class_intersect[cl1][cl2] = NO_REGS;
 908           COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
 909           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 910           COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
 911           AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
 912           if (hard_reg_set_empty_p (temp_hard_regset)
 913               && hard_reg_set_empty_p (temp_set2))
 914             {
 915               for (i = 0;; i++)
 916                 {
 917                   cl3 = reg_class_subclasses[cl1][i];
 918                   if (cl3 == LIM_REG_CLASSES)
 919                     break;
 920                   if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
 921                                           (enum reg_class) cl3))
 922                     ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
 923                 }
 924               ira_reg_class_union[cl1][cl2] = reg_class_subunion[cl1][cl2];
 925               continue;
 926             }
 927           ira_reg_classes_intersect_p[cl1][cl2]
 928             = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
 929           if (important_class_p[cl1] && important_class_p[cl2]
 930               && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
 931             {
 932               enum reg_class *p;
 933
 934               p = &ira_reg_class_super_classes[cl1][0];
 935               while (*p != LIM_REG_CLASSES)
 936                 p++;
 937               *p++ = (enum reg_class) cl2;
 938               *p = LIM_REG_CLASSES;
 939             }
 940           ira_reg_class_union[cl1][cl2] = NO_REGS;
 941           COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
 942           AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
 943           AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
 944           COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
 945           IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
 946           AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
 947           for (i = 0; i < ira_important_classes_num; i++)
 948             {
 949               cl3 = ira_important_classes[i];
 950               COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
 951               AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 952               if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
 953                 {
 954                   COPY_HARD_REG_SET
 955                     (temp_set2,
 956                      reg_class_contents[(int)
 957                                         ira_reg_class_intersect[cl1][cl2]]);
 958                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
 959                   if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
 960                       /* Ignore unavailable hard registers and prefer
 961                          smallest class for debugging purposes.  */
 962                       || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
 963                           && hard_reg_set_subset_p
 964                              (reg_class_contents[cl3],
 965                               reg_class_contents
 966                               [(int) ira_reg_class_intersect[cl1][cl2]])))
 967                     ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
 968                 }
 969               if (hard_reg_set_subset_p (temp_hard_regset, union_set))
 970                 {
 971                   COPY_HARD_REG_SET
 972                     (temp_set2,
 973                      reg_class_contents[(int) ira_reg_class_union[cl1][cl2]]);
 974                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
 975                   if (ira_reg_class_union[cl1][cl2] == NO_REGS
 976                       || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
 977
 978                           && (! hard_reg_set_equal_p (temp_set2,
 979                                                       temp_hard_regset)
 980                               /* Ignore unavailable hard registers and
 981                                  prefer smallest class for debugging
 982                                  purposes.  */
 983                               || hard_reg_set_subset_p
 984                                  (reg_class_contents[cl3],
 985                                   reg_class_contents
 986                                   [(int) ira_reg_class_union[cl1][cl2]]))))
 987                     ira_reg_class_union[cl1][cl2] = (enum reg_class) cl3;
 988                 }
 989             }
 990         }
 991     }
 992 }
 993
 994 /* Output all cover classes and the translation map into file F.  */
 995 static void
 996 print_class_cover (FILE *f)
 997 {
 998   static const char *const reg_class_names[] = REG_CLASS_NAMES;
 999   int i;
1000
1001   fprintf (f, "Class cover:\n");
1002   for (i = 0; i < ira_reg_class_cover_size; i++)
1003     fprintf (f, " %s", reg_class_names[ira_reg_class_cover[i]]);
1004   fprintf (f, "\nClass translation:\n");
1005   for (i = 0; i < N_REG_CLASSES; i++)
1006     fprintf (f, " %s -> %s\n", reg_class_names[i],
1007              reg_class_names[ira_class_translate[i]]);
1008 }
1009
1010 /* Output all cover classes and the translation map into
1011    stderr.  */
1012 void
1013 ira_debug_class_cover (void)
1014 {
1015   print_class_cover (stderr);
1016 }
1017
1018 /* Set up different arrays concerning class subsets, cover and
1019    important classes.  */
1020 static void
1021 find_reg_class_closure (void)
1022 {
1023   setup_reg_subclasses ();
1024   setup_cover_and_important_classes ();
1025   setup_class_translate ();
1026   reorder_important_classes ();
1027   setup_reg_class_relations ();
1028 }
1029
1030 \f
1031
1032 /* Set up the array above.  */
1033 static void
1034 setup_hard_regno_cover_class (void)
1035 {
1036   int i, j;
1037   enum reg_class cl;
1038
1039   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1040     {
1041       ira_hard_regno_cover_class[i] = NO_REGS;
1042       for (j = 0; j < ira_reg_class_cover_size; j++)
1043         {
1044           cl = ira_reg_class_cover[j];
1045           if (ira_class_hard_reg_index[cl][i] >= 0)
1046             {
1047               ira_hard_regno_cover_class[i] = cl;
1048               break;
1049             }
1050         }
1051
1052     }
1053 }
1054
1055 \f
1056
1057 /* Form IRA_REG_CLASS_NREGS map.  */
1058 static void
1059 setup_reg_class_nregs (void)
1060 {
1061   int cl, m;
1062
1063   for (cl = 0; cl < N_REG_CLASSES; cl++)
1064     for (m = 0; m < MAX_MACHINE_MODE; m++)
1065       ira_reg_class_nregs[cl][m] = CLASS_MAX_NREGS ((enum reg_class) cl,
1066                                                     (enum machine_mode) m);
1067 }
1068
1069 \f
1070
1071 /* Set up PROHIBITED_CLASS_MODE_REGS.  */
1072 static void
1073 setup_prohibited_class_mode_regs (void)
1074 {
1075   int i, j, k, hard_regno;
1076   enum reg_class cl;
1077
1078   for (i = 0; i < ira_reg_class_cover_size; i++)
1079     {
1080       cl = ira_reg_class_cover[i];
1081       for (j = 0; j < NUM_MACHINE_MODES; j++)
1082         {
1083           CLEAR_HARD_REG_SET (prohibited_class_mode_regs[cl][j]);
1084           for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1085             {
1086               hard_regno = ira_class_hard_regs[cl][k];
1087               if (! HARD_REGNO_MODE_OK (hard_regno, (enum machine_mode) j))
1088                 SET_HARD_REG_BIT (prohibited_class_mode_regs[cl][j],
1089                                   hard_regno);
1090             }
1091         }
1092     }
1093 }
1094
1095 \f
1096
1097 /* Allocate and initialize IRA_REGISTER_MOVE_COST,
1098    IRA_MAY_MOVE_IN_COST, and IRA_MAY_MOVE_OUT_COST for MODE if it is
1099    not done yet.  */
1100 void
1101 ira_init_register_move_cost (enum machine_mode mode)
1102 {
1103   int cl1, cl2;
1104
1105   ira_assert (ira_register_move_cost[mode] == NULL
1106               && ira_may_move_in_cost[mode] == NULL
1107               && ira_may_move_out_cost[mode] == NULL);
1108   if (move_cost[mode] == NULL)
1109     init_move_cost (mode);
1110   ira_register_move_cost[mode] = move_cost[mode];
1111   /* Don't use ira_allocate because the tables exist out of scope of a
1112      IRA call.  */
1113   ira_may_move_in_cost[mode]
1114     = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1115   memcpy (ira_may_move_in_cost[mode], may_move_in_cost[mode],
1116           sizeof (move_table) * N_REG_CLASSES);
1117   ira_may_move_out_cost[mode]
1118     = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1119   memcpy (ira_may_move_out_cost[mode], may_move_out_cost[mode],
1120           sizeof (move_table) * N_REG_CLASSES);
1121   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1122     {
1123       for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1124         {
1125           if (ira_class_subset_p[cl1][cl2])
1126             ira_may_move_in_cost[mode][cl1][cl2] = 0;
1127           if (ira_class_subset_p[cl2][cl1])
1128             ira_may_move_out_cost[mode][cl1][cl2] = 0;
1129         }
1130     }
1131 }
1132
1133 \f
1134
1135 /* This is called once during compiler work.  It sets up
1136    different arrays whose values don't depend on the compiled
1137    function.  */
1138 void
1139 ira_init_once (void)
1140 {
1141   int mode;
1142
1143   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1144     {
1145       ira_register_move_cost[mode] = NULL;
1146       ira_may_move_in_cost[mode] = NULL;
1147       ira_may_move_out_cost[mode] = NULL;
1148     }
1149   ira_init_costs_once ();
1150 }
1151
1152 /* Free ira_register_move_cost, ira_may_move_in_cost, and
1153    ira_may_move_out_cost for each mode.  */
1154 static void
1155 free_register_move_costs (void)
1156 {
1157   int mode;
1158
1159   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1160     {
1161       if (ira_may_move_in_cost[mode] != NULL)
1162         free (ira_may_move_in_cost[mode]);
1163       if (ira_may_move_out_cost[mode] != NULL)
1164         free (ira_may_move_out_cost[mode]);
1165       ira_register_move_cost[mode] = NULL;
1166       ira_may_move_in_cost[mode] = NULL;
1167       ira_may_move_out_cost[mode] = NULL;
1168     }
1169 }
1170
1171 /* This is called every time when register related information is
1172    changed.  */
1173 void
1174 ira_init (void)
1175 {
1176   free_register_move_costs ();
1177   setup_reg_mode_hard_regset ();
1178   setup_alloc_regs (flag_omit_frame_pointer != 0);
1179   setup_class_subset_and_memory_move_costs ();
1180   find_reg_class_closure ();
1181   setup_hard_regno_cover_class ();
1182   setup_reg_class_nregs ();
1183   setup_prohibited_class_mode_regs ();
1184   ira_init_costs ();
1185 }
1186
1187 /* Function called once at the end of compiler work.  */
1188 void
1189 ira_finish_once (void)
1190 {
1191   ira_finish_costs_once ();
1192   free_register_move_costs ();
1193 }
1194
1195 \f
1196 #define ira_prohibited_mode_move_regs_initialized_p \
1197   (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1198
1199 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS.  */
1200 static void
1201 setup_prohibited_mode_move_regs (void)
1202 {
1203   int i, j;
1204   rtx test_reg1, test_reg2, move_pat, move_insn;
1205
1206   if (ira_prohibited_mode_move_regs_initialized_p)
1207     return;
1208   ira_prohibited_mode_move_regs_initialized_p = true;
1209   test_reg1 = gen_rtx_REG (VOIDmode, 0);
1210   test_reg2 = gen_rtx_REG (VOIDmode, 0);
1211   move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2);
1212   move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, 0, move_pat, 0, -1, 0);
1213   for (i = 0; i < NUM_MACHINE_MODES; i++)
1214     {
1215       SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1216       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1217         {
1218           if (! HARD_REGNO_MODE_OK (j, (enum machine_mode) i))
1219             continue;
1220           SET_REGNO_RAW (test_reg1, j);
1221           PUT_MODE (test_reg1, (enum machine_mode) i);
1222           SET_REGNO_RAW (test_reg2, j);
1223           PUT_MODE (test_reg2, (enum machine_mode) i);
1224           INSN_CODE (move_insn) = -1;
1225           recog_memoized (move_insn);
1226           if (INSN_CODE (move_insn) < 0)
1227             continue;
1228           extract_insn (move_insn);
1229           if (! constrain_operands (1))
1230             continue;
1231           CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1232         }
1233     }
1234 }
1235
1236 \f
1237
1238 /* Return nonzero if REGNO is a particularly bad choice for reloading X.  */
1239 static bool
1240 ira_bad_reload_regno_1 (int regno, rtx x)
1241 {
1242   int x_regno, n, i;
1243   ira_allocno_t a;
1244   enum reg_class pref;
1245
1246   /* We only deal with pseudo regs.  */
1247   if (! x || GET_CODE (x) != REG)
1248     return false;
1249
1250   x_regno = REGNO (x);
1251   if (x_regno < FIRST_PSEUDO_REGISTER)
1252     return false;
1253
1254   /* If the pseudo prefers REGNO explicitly, then do not consider
1255      REGNO a bad spill choice.  */
1256   pref = reg_preferred_class (x_regno);
1257   if (reg_class_size[pref] == 1)
1258     return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
1259
1260   /* If the pseudo conflicts with REGNO, then we consider REGNO a
1261      poor choice for a reload regno.  */
1262   a = ira_regno_allocno_map[x_regno];
1263   n = ALLOCNO_NUM_OBJECTS (a);
1264   for (i = 0; i < n; i++)
1265     {
1266       ira_object_t obj = ALLOCNO_OBJECT (a, i);
1267       if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
1268         return true;
1269     }
1270   return false;
1271 }
1272
1273 /* Return nonzero if REGNO is a particularly bad choice for reloading
1274    IN or OUT.  */
1275 bool
1276 ira_bad_reload_regno (int regno, rtx in, rtx out)
1277 {
1278   return (ira_bad_reload_regno_1 (regno, in)
1279           || ira_bad_reload_regno_1 (regno, out));
1280 }
1281
1282 /* Function specific hard registers that can not be used for the
1283    register allocation.  */
1284 HARD_REG_SET ira_no_alloc_regs;
1285
1286 /* Return TRUE if *LOC contains an asm.  */
1287 static int
1288 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
1289 {
1290   if ( !*loc)
1291     return FALSE;
1292   if (GET_CODE (*loc) == ASM_OPERANDS)
1293     return TRUE;
1294   return FALSE;
1295 }
1296
1297
1298 /* Return TRUE if INSN contains an ASM.  */
1299 static bool
1300 insn_contains_asm (rtx insn)
1301 {
1302   return for_each_rtx (&insn, insn_contains_asm_1, NULL);
1303 }
1304
1305 /* Add register clobbers from asm statements.  */
1306 static void
1307 compute_regs_asm_clobbered (void)
1308 {
1309   basic_block bb;
1310
1311   FOR_EACH_BB (bb)
1312     {
1313       rtx insn;
1314       FOR_BB_INSNS_REVERSE (bb, insn)
1315         {
1316           df_ref *def_rec;
1317
1318           if (insn_contains_asm (insn))
1319             for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1320               {
1321                 df_ref def = *def_rec;
1322                 unsigned int dregno = DF_REF_REGNO (def);
1323                 if (dregno < FIRST_PSEUDO_REGISTER)
1324                   {
1325                     unsigned int i;
1326                     enum machine_mode mode = GET_MODE (DF_REF_REAL_REG (def));
1327                     unsigned int end = dregno
1328                       + hard_regno_nregs[dregno][mode] - 1;
1329
1330                     for (i = dregno; i <= end; ++i)
1331                       SET_HARD_REG_BIT(crtl->asm_clobbers, i);
1332                   }
1333               }
1334         }
1335     }
1336 }
1337
1338
1339 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE.  */
1340 void
1341 ira_setup_eliminable_regset (void)
1342 {
1343 #ifdef ELIMINABLE_REGS
1344   int i;
1345   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
1346 #endif
1347   /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
1348      sp for alloca.  So we can't eliminate the frame pointer in that
1349      case.  At some point, we should improve this by emitting the
1350      sp-adjusting insns for this case.  */
1351   int need_fp
1352     = (! flag_omit_frame_pointer
1353        || (cfun->calls_alloca && EXIT_IGNORE_STACK)
1354        /* We need the frame pointer to catch stack overflow exceptions
1355           if the stack pointer is moving.  */
1356        || (flag_stack_check && STACK_CHECK_MOVING_SP)
1357        || crtl->accesses_prior_frames
1358        || crtl->stack_realign_needed
1359        || targetm.frame_pointer_required ());
1360
1361   frame_pointer_needed = need_fp;
1362
1363   COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
1364   CLEAR_HARD_REG_SET (eliminable_regset);
1365
1366   compute_regs_asm_clobbered ();
1367
1368   /* Build the regset of all eliminable registers and show we can't
1369      use those that we already know won't be eliminated.  */
1370 #ifdef ELIMINABLE_REGS
1371   for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
1372     {
1373       bool cannot_elim
1374         = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
1375            || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
1376
1377       if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
1378         {
1379             SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
1380
1381             if (cannot_elim)
1382               SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
1383         }
1384       else if (cannot_elim)
1385         error ("%s cannot be used in asm here",
1386                reg_names[eliminables[i].from]);
1387       else
1388         df_set_regs_ever_live (eliminables[i].from, true);
1389     }
1390 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1391   if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
1392     {
1393       SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
1394       if (need_fp)
1395         SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
1396     }
1397   else if (need_fp)
1398     error ("%s cannot be used in asm here",
1399            reg_names[HARD_FRAME_POINTER_REGNUM]);
1400   else
1401     df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
1402 #endif
1403
1404 #else
1405   if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
1406     {
1407       SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
1408       if (need_fp)
1409         SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
1410     }
1411   else if (need_fp)
1412     error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
1413   else
1414     df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
1415 #endif
1416 }
1417
1418 \f
1419
1420 /* The length of the following two arrays.  */
1421 int ira_reg_equiv_len;
1422
1423 /* The element value is TRUE if the corresponding regno value is
1424    invariant.  */
1425 bool *ira_reg_equiv_invariant_p;
1426
1427 /* The element value is equiv constant of given pseudo-register or
1428    NULL_RTX.  */
1429 rtx *ira_reg_equiv_const;
1430
1431 /* Set up the two arrays declared above.  */
1432 static void
1433 find_reg_equiv_invariant_const (void)
1434 {
1435   int i;
1436   bool invariant_p;
1437   rtx list, insn, note, constant, x;
1438
1439   for (i = FIRST_PSEUDO_REGISTER; i < reg_equiv_init_size; i++)
1440     {
1441       constant = NULL_RTX;
1442       invariant_p = false;
1443       for (list = reg_equiv_init[i]; list != NULL_RTX; list = XEXP (list, 1))
1444         {
1445           insn = XEXP (list, 0);
1446           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
1447
1448           if (note == NULL_RTX)
1449             continue;
1450
1451           x = XEXP (note, 0);
1452
1453           if (! CONSTANT_P (x)
1454               || ! flag_pic || LEGITIMATE_PIC_OPERAND_P (x))
1455             {
1456               /* It can happen that a REG_EQUIV note contains a MEM
1457                  that is not a legitimate memory operand.  As later
1458                  stages of the reload assume that all addresses found
1459                  in the reg_equiv_* arrays were originally legitimate,
1460                  we ignore such REG_EQUIV notes.  */
1461               if (memory_operand (x, VOIDmode))
1462                 invariant_p = MEM_READONLY_P (x);
1463               else if (function_invariant_p (x))
1464                 {
1465                   if (GET_CODE (x) == PLUS
1466                       || x == frame_pointer_rtx || x == arg_pointer_rtx)
1467                     invariant_p = true;
1468                   else
1469                     constant = x;
1470                 }
1471             }
1472         }
1473       ira_reg_equiv_invariant_p[i] = invariant_p;
1474       ira_reg_equiv_const[i] = constant;
1475     }
1476 }
1477
1478 \f
1479
1480 /* Vector of substitutions of register numbers,
1481    used to map pseudo regs into hardware regs.
1482    This is set up as a result of register allocation.
1483    Element N is the hard reg assigned to pseudo reg N,
1484    or is -1 if no hard reg was assigned.
1485    If N is a hard reg number, element N is N.  */
1486 short *reg_renumber;
1487
1488 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
1489    the allocation found by IRA.  */
1490 static void
1491 setup_reg_renumber (void)
1492 {
1493   int regno, hard_regno;
1494   ira_allocno_t a;
1495   ira_allocno_iterator ai;
1496
1497   caller_save_needed = 0;
1498   FOR_EACH_ALLOCNO (a, ai)
1499     {
1500       /* There are no caps at this point.  */
1501       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1502       if (! ALLOCNO_ASSIGNED_P (a))
1503         /* It can happen if A is not referenced but partially anticipated
1504            somewhere in a region.  */
1505         ALLOCNO_ASSIGNED_P (a) = true;
1506       ira_free_allocno_updated_costs (a);
1507       hard_regno = ALLOCNO_HARD_REGNO (a);
1508       regno = (int) REGNO (ALLOCNO_REG (a));
1509       reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
1510       if (hard_regno >= 0 && ALLOCNO_CALLS_CROSSED_NUM (a) != 0
1511           && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
1512                                           call_used_reg_set))
1513         {
1514           ira_assert (!optimize || flag_caller_saves
1515                       || regno >= ira_reg_equiv_len
1516                       || ira_reg_equiv_const[regno]
1517                       || ira_reg_equiv_invariant_p[regno]);
1518           caller_save_needed = 1;
1519         }
1520     }
1521 }
1522
1523 /* Set up allocno assignment flags for further allocation
1524    improvements.  */
1525 static void
1526 setup_allocno_assignment_flags (void)
1527 {
1528   int hard_regno;
1529   ira_allocno_t a;
1530   ira_allocno_iterator ai;
1531
1532   FOR_EACH_ALLOCNO (a, ai)
1533     {
1534       if (! ALLOCNO_ASSIGNED_P (a))
1535         /* It can happen if A is not referenced but partially anticipated
1536            somewhere in a region.  */
1537         ira_free_allocno_updated_costs (a);
1538       hard_regno = ALLOCNO_HARD_REGNO (a);
1539       /* Don't assign hard registers to allocnos which are destination
1540          of removed store at the end of loop.  It has no sense to keep
1541          the same value in different hard registers.  It is also
1542          impossible to assign hard registers correctly to such
1543          allocnos because the cost info and info about intersected
1544          calls are incorrect for them.  */
1545       ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
1546                                 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a)
1547                                 || (ALLOCNO_MEMORY_COST (a)
1548                                     - ALLOCNO_COVER_CLASS_COST (a)) < 0);
1549       ira_assert (hard_regno < 0
1550                   || ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
1551                                                   reg_class_contents
1552                                                   [ALLOCNO_COVER_CLASS (a)]));
1553     }
1554 }
1555
1556 /* Evaluate overall allocation cost and the costs for using hard
1557    registers and memory for allocnos.  */
1558 static void
1559 calculate_allocation_cost (void)
1560 {
1561   int hard_regno, cost;
1562   ira_allocno_t a;
1563   ira_allocno_iterator ai;
1564
1565   ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
1566   FOR_EACH_ALLOCNO (a, ai)
1567     {
1568       hard_regno = ALLOCNO_HARD_REGNO (a);
1569       ira_assert (hard_regno < 0
1570                   || ! ira_hard_reg_not_in_set_p
1571                        (hard_regno, ALLOCNO_MODE (a),
1572                         reg_class_contents[ALLOCNO_COVER_CLASS (a)]));
1573       if (hard_regno < 0)
1574         {
1575           cost = ALLOCNO_MEMORY_COST (a);
1576           ira_mem_cost += cost;
1577         }
1578       else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1579         {
1580           cost = (ALLOCNO_HARD_REG_COSTS (a)
1581                   [ira_class_hard_reg_index
1582                    [ALLOCNO_COVER_CLASS (a)][hard_regno]]);
1583           ira_reg_cost += cost;
1584         }
1585       else
1586         {
1587           cost = ALLOCNO_COVER_CLASS_COST (a);
1588           ira_reg_cost += cost;
1589         }
1590       ira_overall_cost += cost;
1591     }
1592
1593   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1594     {
1595       fprintf (ira_dump_file,
1596                "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
1597                ira_overall_cost, ira_reg_cost, ira_mem_cost,
1598                ira_load_cost, ira_store_cost, ira_shuffle_cost);
1599       fprintf (ira_dump_file, "+++       move loops %d, new jumps %d\n",
1600                ira_move_loops_num, ira_additional_jumps_num);
1601     }
1602
1603 }
1604
1605 #ifdef ENABLE_IRA_CHECKING
1606 /* Check the correctness of the allocation.  We do need this because
1607    of complicated code to transform more one region internal
1608    representation into one region representation.  */
1609 static void
1610 check_allocation (void)
1611 {
1612   ira_allocno_t a;
1613   int hard_regno, nregs, conflict_nregs;
1614   ira_allocno_iterator ai;
1615
1616   FOR_EACH_ALLOCNO (a, ai)
1617     {
1618       int n = ALLOCNO_NUM_OBJECTS (a);
1619       int i;
1620
1621       if (ALLOCNO_CAP_MEMBER (a) != NULL
1622           || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1623         continue;
1624       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
1625       if (nregs == 1)
1626         /* We allocated a single hard register.  */
1627         n = 1;
1628       else if (n > 1)
1629         /* We allocated multiple hard registers, and we will test
1630            conflicts in a granularity of single hard regs.  */
1631         nregs = 1;
1632
1633       for (i = 0; i < n; i++)
1634         {
1635           ira_object_t obj = ALLOCNO_OBJECT (a, i);
1636           ira_object_t conflict_obj;
1637           ira_object_conflict_iterator oci;
1638           int this_regno = hard_regno;
1639           if (n > 1)
1640             {
1641               if (WORDS_BIG_ENDIAN)
1642                 this_regno += n - i - 1;
1643               else
1644                 this_regno += i;
1645             }
1646           FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1647             {
1648               ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1649               int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1650               if (conflict_hard_regno < 0)
1651                 continue;
1652
1653               conflict_nregs
1654                 = (hard_regno_nregs
1655                    [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
1656
1657               if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
1658                   && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
1659                 {
1660                   if (WORDS_BIG_ENDIAN)
1661                     conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
1662                                             - OBJECT_SUBWORD (conflict_obj) - 1);
1663                   else
1664                     conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
1665                   conflict_nregs = 1;
1666                 }
1667
1668               if ((conflict_hard_regno <= this_regno
1669                  && this_regno < conflict_hard_regno + conflict_nregs)
1670                 || (this_regno <= conflict_hard_regno
1671                     && conflict_hard_regno < this_regno + nregs))
1672                 {
1673                   fprintf (stderr, "bad allocation for %d and %d\n",
1674                            ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
1675                   gcc_unreachable ();
1676                 }
1677             }
1678         }
1679     }
1680 }
1681 #endif
1682
1683 /* Fix values of array REG_EQUIV_INIT after live range splitting done
1684    by IRA.  */
1685 static void
1686 fix_reg_equiv_init (void)
1687 {
1688   int max_regno = max_reg_num ();
1689   int i, new_regno;
1690   rtx x, prev, next, insn, set;
1691
1692   if (reg_equiv_init_size < max_regno)
1693     {
1694       reg_equiv_init = GGC_RESIZEVEC (rtx, reg_equiv_init, max_regno);
1695       while (reg_equiv_init_size < max_regno)
1696         reg_equiv_init[reg_equiv_init_size++] = NULL_RTX;
1697       for (i = FIRST_PSEUDO_REGISTER; i < reg_equiv_init_size; i++)
1698         for (prev = NULL_RTX, x = reg_equiv_init[i]; x != NULL_RTX; x = next)
1699           {
1700             next = XEXP (x, 1);
1701             insn = XEXP (x, 0);
1702             set = single_set (insn);
1703             ira_assert (set != NULL_RTX
1704                         && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
1705             if (REG_P (SET_DEST (set))
1706                 && ((int) REGNO (SET_DEST (set)) == i
1707                     || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
1708               new_regno = REGNO (SET_DEST (set));
1709             else if (REG_P (SET_SRC (set))
1710                      && ((int) REGNO (SET_SRC (set)) == i
1711                          || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
1712               new_regno = REGNO (SET_SRC (set));
1713             else
1714               gcc_unreachable ();
1715             if (new_regno == i)
1716               prev = x;
1717             else
1718               {
1719                 if (prev == NULL_RTX)
1720                   reg_equiv_init[i] = next;
1721                 else
1722                   XEXP (prev, 1) = next;
1723                 XEXP (x, 1) = reg_equiv_init[new_regno];
1724                 reg_equiv_init[new_regno] = x;
1725               }
1726           }
1727     }
1728 }
1729
1730 #ifdef ENABLE_IRA_CHECKING
1731 /* Print redundant memory-memory copies.  */
1732 static void
1733 print_redundant_copies (void)
1734 {
1735   int hard_regno;
1736   ira_allocno_t a;
1737   ira_copy_t cp, next_cp;
1738   ira_allocno_iterator ai;
1739
1740   FOR_EACH_ALLOCNO (a, ai)
1741     {
1742       if (ALLOCNO_CAP_MEMBER (a) != NULL)
1743         /* It is a cap. */
1744         continue;
1745       hard_regno = ALLOCNO_HARD_REGNO (a);
1746       if (hard_regno >= 0)
1747         continue;
1748       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1749         if (cp->first == a)
1750           next_cp = cp->next_first_allocno_copy;
1751         else
1752           {
1753             next_cp = cp->next_second_allocno_copy;
1754             if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
1755                 && cp->insn != NULL_RTX
1756                 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
1757               fprintf (ira_dump_file,
1758                        "        Redundant move from %d(freq %d):%d\n",
1759                        INSN_UID (cp->insn), cp->freq, hard_regno);
1760           }
1761     }
1762 }
1763 #endif
1764
1765 /* Setup preferred and alternative classes for new pseudo-registers
1766    created by IRA starting with START.  */
1767 static void
1768 setup_preferred_alternate_classes_for_new_pseudos (int start)
1769 {
1770   int i, old_regno;
1771   int max_regno = max_reg_num ();
1772
1773   for (i = start; i < max_regno; i++)
1774     {
1775       old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
1776       ira_assert (i != old_regno);
1777       setup_reg_classes (i, reg_preferred_class (old_regno),
1778                          reg_alternate_class (old_regno),
1779                          reg_cover_class (old_regno));
1780       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1781         fprintf (ira_dump_file,
1782                  "    New r%d: setting preferred %s, alternative %s\n",
1783                  i, reg_class_names[reg_preferred_class (old_regno)],
1784                  reg_class_names[reg_alternate_class (old_regno)]);
1785     }
1786 }
1787
1788 \f
1789
1790 /* Regional allocation can create new pseudo-registers.  This function
1791    expands some arrays for pseudo-registers.  */
1792 static void
1793 expand_reg_info (int old_size)
1794 {
1795   int i;
1796   int size = max_reg_num ();
1797
1798   resize_reg_info ();
1799   for (i = old_size; i < size; i++)
1800     setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
1801 }
1802
1803 /* Return TRUE if there is too high register pressure in the function.
1804    It is used to decide when stack slot sharing is worth to do.  */
1805 static bool
1806 too_high_register_pressure_p (void)
1807 {
1808   int i;
1809   enum reg_class cover_class;
1810
1811   for (i = 0; i < ira_reg_class_cover_size; i++)
1812     {
1813       cover_class = ira_reg_class_cover[i];
1814       if (ira_loop_tree_root->reg_pressure[cover_class] > 10000)
1815         return true;
1816     }
1817   return false;
1818 }
1819
1820 \f
1821
1822 /* Indicate that hard register number FROM was eliminated and replaced with
1823    an offset from hard register number TO.  The status of hard registers live
1824    at the start of a basic block is updated by replacing a use of FROM with
1825    a use of TO.  */
1826
1827 void
1828 mark_elimination (int from, int to)
1829 {
1830   basic_block bb;
1831
1832   FOR_EACH_BB (bb)
1833     {
1834       /* We don't use LIVE info in IRA.  */
1835       bitmap r = DF_LR_IN (bb);
1836
1837       if (REGNO_REG_SET_P (r, from))
1838         {
1839           CLEAR_REGNO_REG_SET (r, from);
1840           SET_REGNO_REG_SET (r, to);
1841         }
1842     }
1843 }
1844
1845 \f
1846
1847 struct equivalence
1848 {
1849   /* Set when a REG_EQUIV note is found or created.  Use to
1850      keep track of what memory accesses might be created later,
1851      e.g. by reload.  */
1852   rtx replacement;
1853   rtx *src_p;
1854   /* The list of each instruction which initializes this register.  */
1855   rtx init_insns;
1856   /* Loop depth is used to recognize equivalences which appear
1857      to be present within the same loop (or in an inner loop).  */
1858   int loop_depth;
1859   /* Nonzero if this had a preexisting REG_EQUIV note.  */
1860   int is_arg_equivalence;
1861   /* Set when an attempt should be made to replace a register
1862      with the associated src_p entry.  */
1863   char replace;
1864 };
1865
1866 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
1867    structure for that register.  */
1868 static struct equivalence *reg_equiv;
1869
1870 /* Used for communication between the following two functions: contains
1871    a MEM that we wish to ensure remains unchanged.  */
1872 static rtx equiv_mem;
1873
1874 /* Set nonzero if EQUIV_MEM is modified.  */
1875 static int equiv_mem_modified;
1876
1877 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
1878    Called via note_stores.  */
1879 static void
1880 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
1881                                void *data ATTRIBUTE_UNUSED)
1882 {
1883   if ((REG_P (dest)
1884        && reg_overlap_mentioned_p (dest, equiv_mem))
1885       || (MEM_P (dest)
1886           && true_dependence (dest, VOIDmode, equiv_mem, rtx_varies_p)))
1887     equiv_mem_modified = 1;
1888 }
1889
1890 /* Verify that no store between START and the death of REG invalidates
1891    MEMREF.  MEMREF is invalidated by modifying a register used in MEMREF,
1892    by storing into an overlapping memory location, or with a non-const
1893    CALL_INSN.
1894
1895    Return 1 if MEMREF remains valid.  */
1896 static int
1897 validate_equiv_mem (rtx start, rtx reg, rtx memref)
1898 {
1899   rtx insn;
1900   rtx note;
1901
1902   equiv_mem = memref;
1903   equiv_mem_modified = 0;
1904
1905   /* If the memory reference has side effects or is volatile, it isn't a
1906      valid equivalence.  */
1907   if (side_effects_p (memref))
1908     return 0;
1909
1910   for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
1911     {
1912       if (! INSN_P (insn))
1913         continue;
1914
1915       if (find_reg_note (insn, REG_DEAD, reg))
1916         return 1;
1917
1918       /* This used to ignore readonly memory and const/pure calls.  The problem
1919          is the equivalent form may reference a pseudo which gets assigned a
1920          call clobbered hard reg.  When we later replace REG with its
1921          equivalent form, the value in the call-clobbered reg has been
1922          changed and all hell breaks loose.  */
1923       if (CALL_P (insn))
1924         return 0;
1925
1926       note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
1927
1928       /* If a register mentioned in MEMREF is modified via an
1929          auto-increment, we lose the equivalence.  Do the same if one
1930          dies; although we could extend the life, it doesn't seem worth
1931          the trouble.  */
1932
1933       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1934         if ((REG_NOTE_KIND (note) == REG_INC
1935              || REG_NOTE_KIND (note) == REG_DEAD)
1936             && REG_P (XEXP (note, 0))
1937             && reg_overlap_mentioned_p (XEXP (note, 0), memref))
1938           return 0;
1939     }
1940
1941   return 0;
1942 }
1943
1944 /* Returns zero if X is known to be invariant.  */
1945 static int
1946 equiv_init_varies_p (rtx x)
1947 {
1948   RTX_CODE code = GET_CODE (x);
1949   int i;
1950   const char *fmt;
1951
1952   switch (code)
1953     {
1954     case MEM:
1955       return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
1956
1957     case CONST:
1958     case CONST_INT:
1959     case CONST_DOUBLE:
1960     case CONST_FIXED:
1961     case CONST_VECTOR:
1962     case SYMBOL_REF:
1963     case LABEL_REF:
1964       return 0;
1965
1966     case REG:
1967       return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
1968
1969     case ASM_OPERANDS:
1970       if (MEM_VOLATILE_P (x))
1971         return 1;
1972
1973       /* Fall through.  */
1974
1975     default:
1976       break;
1977     }
1978
1979   fmt = GET_RTX_FORMAT (code);
1980   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1981     if (fmt[i] == 'e')
1982       {
1983         if (equiv_init_varies_p (XEXP (x, i)))
1984           return 1;
1985       }
1986     else if (fmt[i] == 'E')
1987       {
1988         int j;
1989         for (j = 0; j < XVECLEN (x, i); j++)
1990           if (equiv_init_varies_p (XVECEXP (x, i, j)))
1991             return 1;
1992       }
1993
1994   return 0;
1995 }
1996
1997 /* Returns nonzero if X (used to initialize register REGNO) is movable.
1998    X is only movable if the registers it uses have equivalent initializations
1999    which appear to be within the same loop (or in an inner loop) and movable
2000    or if they are not candidates for local_alloc and don't vary.  */
2001 static int
2002 equiv_init_movable_p (rtx x, int regno)
2003 {
2004   int i, j;
2005   const char *fmt;
2006   enum rtx_code code = GET_CODE (x);
2007
2008   switch (code)
2009     {
2010     case SET:
2011       return equiv_init_movable_p (SET_SRC (x), regno);
2012
2013     case CC0:
2014     case CLOBBER:
2015       return 0;
2016
2017     case PRE_INC:
2018     case PRE_DEC:
2019     case POST_INC:
2020     case POST_DEC:
2021     case PRE_MODIFY:
2022     case POST_MODIFY:
2023       return 0;
2024
2025     case REG:
2026       return (reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
2027               && reg_equiv[REGNO (x)].replace)
2028              || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS && ! rtx_varies_p (x, 0));
2029
2030     case UNSPEC_VOLATILE:
2031       return 0;
2032
2033     case ASM_OPERANDS:
2034       if (MEM_VOLATILE_P (x))
2035         return 0;
2036
2037       /* Fall through.  */
2038
2039     default:
2040       break;
2041     }
2042
2043   fmt = GET_RTX_FORMAT (code);
2044   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2045     switch (fmt[i])
2046       {
2047       case 'e':
2048         if (! equiv_init_movable_p (XEXP (x, i), regno))
2049           return 0;
2050         break;
2051       case 'E':
2052         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2053           if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
2054             return 0;
2055         break;
2056       }
2057
2058   return 1;
2059 }
2060
2061 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true.  */
2062 static int
2063 contains_replace_regs (rtx x)
2064 {
2065   int i, j;
2066   const char *fmt;
2067   enum rtx_code code = GET_CODE (x);
2068
2069   switch (code)
2070     {
2071     case CONST_INT:
2072     case CONST:
2073     case LABEL_REF:
2074     case SYMBOL_REF:
2075     case CONST_DOUBLE:
2076     case CONST_FIXED:
2077     case CONST_VECTOR:
2078     case PC:
2079     case CC0:
2080     case HIGH:
2081       return 0;
2082
2083     case REG:
2084       return reg_equiv[REGNO (x)].replace;
2085
2086     default:
2087       break;
2088     }
2089
2090   fmt = GET_RTX_FORMAT (code);
2091   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2092     switch (fmt[i])
2093       {
2094       case 'e':
2095         if (contains_replace_regs (XEXP (x, i)))
2096           return 1;
2097         break;
2098       case 'E':
2099         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2100           if (contains_replace_regs (XVECEXP (x, i, j)))
2101             return 1;
2102         break;
2103       }
2104
2105   return 0;
2106 }
2107
2108 /* TRUE if X references a memory location that would be affected by a store
2109    to MEMREF.  */
2110 static int
2111 memref_referenced_p (rtx memref, rtx x)
2112 {
2113   int i, j;
2114   const char *fmt;
2115   enum rtx_code code = GET_CODE (x);
2116
2117   switch (code)
2118     {
2119     case CONST_INT:
2120     case CONST:
2121     case LABEL_REF:
2122     case SYMBOL_REF:
2123     case CONST_DOUBLE:
2124     case CONST_FIXED:
2125     case CONST_VECTOR:
2126     case PC:
2127     case CC0:
2128     case HIGH:
2129     case LO_SUM:
2130       return 0;
2131
2132     case REG:
2133       return (reg_equiv[REGNO (x)].replacement
2134               && memref_referenced_p (memref,
2135                                       reg_equiv[REGNO (x)].replacement));
2136
2137     case MEM:
2138       if (true_dependence (memref, VOIDmode, x, rtx_varies_p))
2139         return 1;
2140       break;
2141
2142     case SET:
2143       /* If we are setting a MEM, it doesn't count (its address does), but any
2144          other SET_DEST that has a MEM in it is referencing the MEM.  */
2145       if (MEM_P (SET_DEST (x)))
2146         {
2147           if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
2148             return 1;
2149         }
2150       else if (memref_referenced_p (memref, SET_DEST (x)))
2151         return 1;
2152
2153       return memref_referenced_p (memref, SET_SRC (x));
2154
2155     default:
2156       break;
2157     }
2158
2159   fmt = GET_RTX_FORMAT (code);
2160   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2161     switch (fmt[i])
2162       {
2163       case 'e':
2164         if (memref_referenced_p (memref, XEXP (x, i)))
2165           return 1;
2166         break;
2167       case 'E':
2168         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2169           if (memref_referenced_p (memref, XVECEXP (x, i, j)))
2170             return 1;
2171         break;
2172       }
2173
2174   return 0;
2175 }
2176
2177 /* TRUE if some insn in the range (START, END] references a memory location
2178    that would be affected by a store to MEMREF.  */
2179 static int
2180 memref_used_between_p (rtx memref, rtx start, rtx end)
2181 {
2182   rtx insn;
2183
2184   for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2185        insn = NEXT_INSN (insn))
2186     {
2187       if (!NONDEBUG_INSN_P (insn))
2188         continue;
2189
2190       if (memref_referenced_p (memref, PATTERN (insn)))
2191         return 1;
2192
2193       /* Nonconst functions may access memory.  */
2194       if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
2195         return 1;
2196     }
2197
2198   return 0;
2199 }
2200
2201 /* Mark REG as having no known equivalence.
2202    Some instructions might have been processed before and furnished
2203    with REG_EQUIV notes for this register; these notes will have to be
2204    removed.
2205    STORE is the piece of RTL that does the non-constant / conflicting
2206    assignment - a SET, CLOBBER or REG_INC note.  It is currently not used,
2207    but needs to be there because this function is called from note_stores.  */
2208 static void
2209 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
2210 {
2211   int regno;
2212   rtx list;
2213
2214   if (!REG_P (reg))
2215     return;
2216   regno = REGNO (reg);
2217   list = reg_equiv[regno].init_insns;
2218   if (list == const0_rtx)
2219     return;
2220   reg_equiv[regno].init_insns = const0_rtx;
2221   reg_equiv[regno].replacement = NULL_RTX;
2222   /* This doesn't matter for equivalences made for argument registers, we
2223      should keep their initialization insns.  */
2224   if (reg_equiv[regno].is_arg_equivalence)
2225     return;
2226   reg_equiv_init[regno] = NULL_RTX;
2227   for (; list; list =  XEXP (list, 1))
2228     {
2229       rtx insn = XEXP (list, 0);
2230       remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
2231     }
2232 }
2233
2234 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
2235    equivalent replacement.  */
2236
2237 static rtx
2238 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
2239 {
2240   if (REG_P (loc))
2241     {
2242       bitmap cleared_regs = (bitmap) data;
2243       if (bitmap_bit_p (cleared_regs, REGNO (loc)))
2244         return simplify_replace_fn_rtx (*reg_equiv[REGNO (loc)].src_p,
2245                                         NULL_RTX, adjust_cleared_regs, data);
2246     }
2247   return NULL_RTX;
2248 }
2249
2250 /* Nonzero if we recorded an equivalence for a LABEL_REF.  */
2251 static int recorded_label_ref;
2252
2253 /* Find registers that are equivalent to a single value throughout the
2254    compilation (either because they can be referenced in memory or are set once
2255    from a single constant).  Lower their priority for a register.
2256
2257    If such a register is only referenced once, try substituting its value
2258    into the using insn.  If it succeeds, we can eliminate the register
2259    completely.
2260
2261    Initialize the REG_EQUIV_INIT array of initializing insns.
2262
2263    Return non-zero if jump label rebuilding should be done.  */
2264 static int
2265 update_equiv_regs (void)
2266 {
2267   rtx insn;
2268   basic_block bb;
2269   int loop_depth;
2270   bitmap cleared_regs;
2271
2272   /* We need to keep track of whether or not we recorded a LABEL_REF so
2273      that we know if the jump optimizer needs to be rerun.  */
2274   recorded_label_ref = 0;
2275
2276   reg_equiv = XCNEWVEC (struct equivalence, max_regno);
2277   reg_equiv_init = ggc_alloc_cleared_vec_rtx (max_regno);
2278   reg_equiv_init_size = max_regno;
2279
2280   init_alias_analysis ();
2281
2282   /* Scan the insns and find which registers have equivalences.  Do this
2283      in a separate scan of the insns because (due to -fcse-follow-jumps)
2284      a register can be set below its use.  */
2285   FOR_EACH_BB (bb)
2286     {
2287       loop_depth = bb->loop_depth;
2288
2289       for (insn = BB_HEAD (bb);
2290            insn != NEXT_INSN (BB_END (bb));
2291            insn = NEXT_INSN (insn))
2292         {
2293           rtx note;
2294           rtx set;
2295           rtx dest, src;
2296           int regno;
2297
2298           if (! INSN_P (insn))
2299             continue;
2300
2301           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2302             if (REG_NOTE_KIND (note) == REG_INC)
2303               no_equiv (XEXP (note, 0), note, NULL);
2304
2305           set = single_set (insn);
2306
2307           /* If this insn contains more (or less) than a single SET,
2308              only mark all destinations as having no known equivalence.  */
2309           if (set == 0)
2310             {
2311               note_stores (PATTERN (insn), no_equiv, NULL);
2312               continue;
2313             }
2314           else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2315             {
2316               int i;
2317
2318               for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2319                 {
2320                   rtx part = XVECEXP (PATTERN (insn), 0, i);
2321                   if (part != set)
2322                     note_stores (part, no_equiv, NULL);
2323                 }
2324             }
2325
2326           dest = SET_DEST (set);
2327           src = SET_SRC (set);
2328
2329           /* See if this is setting up the equivalence between an argument
2330              register and its stack slot.  */
2331           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2332           if (note)
2333             {
2334               gcc_assert (REG_P (dest));
2335               regno = REGNO (dest);
2336
2337               /* Note that we don't want to clear reg_equiv_init even if there
2338                  are multiple sets of this register.  */
2339               reg_equiv[regno].is_arg_equivalence = 1;
2340
2341               /* Record for reload that this is an equivalencing insn.  */
2342               if (rtx_equal_p (src, XEXP (note, 0)))
2343                 reg_equiv_init[regno]
2344                   = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
2345
2346               /* Continue normally in case this is a candidate for
2347                  replacements.  */
2348             }
2349
2350           if (!optimize)
2351             continue;
2352
2353           /* We only handle the case of a pseudo register being set
2354              once, or always to the same value.  */
2355           /* ??? The mn10200 port breaks if we add equivalences for
2356              values that need an ADDRESS_REGS register and set them equivalent
2357              to a MEM of a pseudo.  The actual problem is in the over-conservative
2358              handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
2359              calculate_needs, but we traditionally work around this problem
2360              here by rejecting equivalences when the destination is in a register
2361              that's likely spilled.  This is fragile, of course, since the
2362              preferred class of a pseudo depends on all instructions that set
2363              or use it.  */
2364
2365           if (!REG_P (dest)
2366               || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
2367               || reg_equiv[regno].init_insns == const0_rtx
2368               || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
2369                   && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
2370             {
2371               /* This might be setting a SUBREG of a pseudo, a pseudo that is
2372                  also set somewhere else to a constant.  */
2373               note_stores (set, no_equiv, NULL);
2374               continue;
2375             }
2376
2377           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
2378
2379           /* cse sometimes generates function invariants, but doesn't put a
2380              REG_EQUAL note on the insn.  Since this note would be redundant,
2381              there's no point creating it earlier than here.  */
2382           if (! note && ! rtx_varies_p (src, 0))
2383             note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
2384
2385           /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
2386              since it represents a function call */
2387           if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
2388             note = NULL_RTX;
2389
2390           if (DF_REG_DEF_COUNT (regno) != 1
2391               && (! note
2392                   || rtx_varies_p (XEXP (note, 0), 0)
2393                   || (reg_equiv[regno].replacement
2394                       && ! rtx_equal_p (XEXP (note, 0),
2395                                         reg_equiv[regno].replacement))))
2396             {
2397               no_equiv (dest, set, NULL);
2398               continue;
2399             }
2400           /* Record this insn as initializing this register.  */
2401           reg_equiv[regno].init_insns
2402             = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
2403
2404           /* If this register is known to be equal to a constant, record that
2405              it is always equivalent to the constant.  */
2406           if (DF_REG_DEF_COUNT (regno) == 1
2407               && note && ! rtx_varies_p (XEXP (note, 0), 0))
2408             {
2409               rtx note_value = XEXP (note, 0);
2410               remove_note (insn, note);
2411               set_unique_reg_note (insn, REG_EQUIV, note_value);
2412             }
2413
2414           /* If this insn introduces a "constant" register, decrease the priority
2415              of that register.  Record this insn if the register is only used once
2416              more and the equivalence value is the same as our source.
2417
2418              The latter condition is checked for two reasons:  First, it is an
2419              indication that it may be more efficient to actually emit the insn
2420              as written (if no registers are available, reload will substitute
2421              the equivalence).  Secondly, it avoids problems with any registers
2422              dying in this insn whose death notes would be missed.
2423
2424              If we don't have a REG_EQUIV note, see if this insn is loading
2425              a register used only in one basic block from a MEM.  If so, and the
2426              MEM remains unchanged for the life of the register, add a REG_EQUIV
2427              note.  */
2428
2429           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2430
2431           if (note == 0 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2432               && MEM_P (SET_SRC (set))
2433               && validate_equiv_mem (insn, dest, SET_SRC (set)))
2434             note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
2435
2436           if (note)
2437             {
2438               int regno = REGNO (dest);
2439               rtx x = XEXP (note, 0);
2440
2441               /* If we haven't done so, record for reload that this is an
2442                  equivalencing insn.  */
2443               if (!reg_equiv[regno].is_arg_equivalence)
2444                 reg_equiv_init[regno]
2445                   = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
2446
2447               /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
2448                  We might end up substituting the LABEL_REF for uses of the
2449                  pseudo here or later.  That kind of transformation may turn an
2450                  indirect jump into a direct jump, in which case we must rerun the
2451                  jump optimizer to ensure that the JUMP_LABEL fields are valid.  */
2452               if (GET_CODE (x) == LABEL_REF
2453                   || (GET_CODE (x) == CONST
2454                       && GET_CODE (XEXP (x, 0)) == PLUS
2455                       && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
2456                 recorded_label_ref = 1;
2457
2458               reg_equiv[regno].replacement = x;
2459               reg_equiv[regno].src_p = &SET_SRC (set);
2460               reg_equiv[regno].loop_depth = loop_depth;
2461
2462               /* Don't mess with things live during setjmp.  */
2463               if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
2464                 {
2465                   /* Note that the statement below does not affect the priority
2466                      in local-alloc!  */
2467                   REG_LIVE_LENGTH (regno) *= 2;
2468
2469                   /* If the register is referenced exactly twice, meaning it is
2470                      set once and used once, indicate that the reference may be
2471                      replaced by the equivalence we computed above.  Do this
2472                      even if the register is only used in one block so that
2473                      dependencies can be handled where the last register is
2474                      used in a different block (i.e. HIGH / LO_SUM sequences)
2475                      and to reduce the number of registers alive across
2476                      calls.  */
2477
2478                   if (REG_N_REFS (regno) == 2
2479                       && (rtx_equal_p (x, src)
2480                           || ! equiv_init_varies_p (src))
2481                       && NONJUMP_INSN_P (insn)
2482                       && equiv_init_movable_p (PATTERN (insn), regno))
2483                     reg_equiv[regno].replace = 1;
2484                 }
2485             }
2486         }
2487     }
2488
2489   if (!optimize)
2490     goto out;
2491
2492   /* A second pass, to gather additional equivalences with memory.  This needs
2493      to be done after we know which registers we are going to replace.  */
2494
2495   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2496     {
2497       rtx set, src, dest;
2498       unsigned regno;
2499
2500       if (! INSN_P (insn))
2501         continue;
2502
2503       set = single_set (insn);
2504       if (! set)
2505         continue;
2506
2507       dest = SET_DEST (set);
2508       src = SET_SRC (set);
2509
2510       /* If this sets a MEM to the contents of a REG that is only used
2511          in a single basic block, see if the register is always equivalent
2512          to that memory location and if moving the store from INSN to the
2513          insn that set REG is safe.  If so, put a REG_EQUIV note on the
2514          initializing insn.
2515
2516          Don't add a REG_EQUIV note if the insn already has one.  The existing
2517          REG_EQUIV is likely more useful than the one we are adding.
2518
2519          If one of the regs in the address has reg_equiv[REGNO].replace set,
2520          then we can't add this REG_EQUIV note.  The reg_equiv[REGNO].replace
2521          optimization may move the set of this register immediately before
2522          insn, which puts it after reg_equiv[REGNO].init_insns, and hence
2523          the mention in the REG_EQUIV note would be to an uninitialized
2524          pseudo.  */
2525
2526       if (MEM_P (dest) && REG_P (src)
2527           && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
2528           && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2529           && DF_REG_DEF_COUNT (regno) == 1
2530           && reg_equiv[regno].init_insns != 0
2531           && reg_equiv[regno].init_insns != const0_rtx
2532           && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
2533                               REG_EQUIV, NULL_RTX)
2534           && ! contains_replace_regs (XEXP (dest, 0)))
2535         {
2536           rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
2537           if (validate_equiv_mem (init_insn, src, dest)
2538               && ! memref_used_between_p (dest, init_insn, insn)
2539               /* Attaching a REG_EQUIV note will fail if INIT_INSN has
2540                  multiple sets.  */
2541               && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
2542             {
2543               /* This insn makes the equivalence, not the one initializing
2544                  the register.  */
2545               reg_equiv_init[regno]
2546                 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
2547               df_notes_rescan (init_insn);
2548             }
2549         }
2550     }
2551
2552   cleared_regs = BITMAP_ALLOC (NULL);
2553   /* Now scan all regs killed in an insn to see if any of them are
2554      registers only used that once.  If so, see if we can replace the
2555      reference with the equivalent form.  If we can, delete the
2556      initializing reference and this register will go away.  If we
2557      can't replace the reference, and the initializing reference is
2558      within the same loop (or in an inner loop), then move the register
2559      initialization just before the use, so that they are in the same
2560      basic block.  */
2561   FOR_EACH_BB_REVERSE (bb)
2562     {
2563       loop_depth = bb->loop_depth;
2564       for (insn = BB_END (bb);
2565            insn != PREV_INSN (BB_HEAD (bb));
2566            insn = PREV_INSN (insn))
2567         {
2568           rtx link;
2569
2570           if (! INSN_P (insn))
2571             continue;
2572
2573           /* Don't substitute into a non-local goto, this confuses CFG.  */
2574           if (JUMP_P (insn)
2575               && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
2576             continue;
2577
2578           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2579             {
2580               if (REG_NOTE_KIND (link) == REG_DEAD
2581                   /* Make sure this insn still refers to the register.  */
2582                   && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
2583                 {
2584                   int regno = REGNO (XEXP (link, 0));
2585                   rtx equiv_insn;
2586
2587                   if (! reg_equiv[regno].replace
2588                       || reg_equiv[regno].loop_depth < loop_depth)
2589                     continue;
2590
2591                   /* reg_equiv[REGNO].replace gets set only when
2592                      REG_N_REFS[REGNO] is 2, i.e. the register is set
2593                      once and used once.  (If it were only set, but not used,
2594                      flow would have deleted the setting insns.)  Hence
2595                      there can only be one insn in reg_equiv[REGNO].init_insns.  */
2596                   gcc_assert (reg_equiv[regno].init_insns
2597                               && !XEXP (reg_equiv[regno].init_insns, 1));
2598                   equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
2599
2600                   /* We may not move instructions that can throw, since
2601                      that changes basic block boundaries and we are not
2602                      prepared to adjust the CFG to match.  */
2603                   if (can_throw_internal (equiv_insn))
2604                     continue;
2605
2606                   if (asm_noperands (PATTERN (equiv_insn)) < 0
2607                       && validate_replace_rtx (regno_reg_rtx[regno],
2608                                                *(reg_equiv[regno].src_p), insn))
2609                     {
2610                       rtx equiv_link;
2611                       rtx last_link;
2612                       rtx note;
2613
2614                       /* Find the last note.  */
2615                       for (last_link = link; XEXP (last_link, 1);
2616                            last_link = XEXP (last_link, 1))
2617                         ;
2618
2619                       /* Append the REG_DEAD notes from equiv_insn.  */
2620                       equiv_link = REG_NOTES (equiv_insn);
2621                       while (equiv_link)
2622                         {
2623                           note = equiv_link;
2624                           equiv_link = XEXP (equiv_link, 1);
2625                           if (REG_NOTE_KIND (note) == REG_DEAD)
2626                             {
2627                               remove_note (equiv_insn, note);
2628                               XEXP (last_link, 1) = note;
2629                               XEXP (note, 1) = NULL_RTX;
2630                               last_link = note;
2631                             }
2632                         }
2633
2634                       remove_death (regno, insn);
2635                       SET_REG_N_REFS (regno, 0);
2636                       REG_FREQ (regno) = 0;
2637                       delete_insn (equiv_insn);
2638
2639                       reg_equiv[regno].init_insns
2640                         = XEXP (reg_equiv[regno].init_insns, 1);
2641
2642                       reg_equiv_init[regno] = NULL_RTX;
2643                       bitmap_set_bit (cleared_regs, regno);
2644                     }
2645                   /* Move the initialization of the register to just before
2646                      INSN.  Update the flow information.  */
2647                   else if (prev_nondebug_insn (insn) != equiv_insn)
2648                     {
2649                       rtx new_insn;
2650
2651                       new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
2652                       REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
2653                       REG_NOTES (equiv_insn) = 0;
2654                       /* Rescan it to process the notes.  */
2655                       df_insn_rescan (new_insn);
2656
2657                       /* Make sure this insn is recognized before
2658                          reload begins, otherwise
2659                          eliminate_regs_in_insn will die.  */
2660                       INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
2661
2662                       delete_insn (equiv_insn);
2663
2664                       XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
2665
2666                       REG_BASIC_BLOCK (regno) = bb->index;
2667                       REG_N_CALLS_CROSSED (regno) = 0;
2668                       REG_FREQ_CALLS_CROSSED (regno) = 0;
2669                       REG_N_THROWING_CALLS_CROSSED (regno) = 0;
2670                       REG_LIVE_LENGTH (regno) = 2;
2671
2672                       if (insn == BB_HEAD (bb))
2673                         BB_HEAD (bb) = PREV_INSN (insn);
2674
2675                       reg_equiv_init[regno]
2676                         = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
2677                       bitmap_set_bit (cleared_regs, regno);
2678                     }
2679                 }
2680             }
2681         }
2682     }
2683
2684   if (!bitmap_empty_p (cleared_regs))
2685     {
2686       FOR_EACH_BB (bb)
2687         {
2688           bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
2689           bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
2690           bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
2691           bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
2692         }
2693
2694       /* Last pass - adjust debug insns referencing cleared regs.  */
2695       if (MAY_HAVE_DEBUG_INSNS)
2696         for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2697           if (DEBUG_INSN_P (insn))
2698             {
2699               rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
2700               INSN_VAR_LOCATION_LOC (insn)
2701                 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
2702                                            adjust_cleared_regs,
2703                                            (void *) cleared_regs);
2704               if (old_loc != INSN_VAR_LOCATION_LOC (insn))
2705                 df_insn_rescan (insn);
2706             }
2707     }
2708
2709   BITMAP_FREE (cleared_regs);
2710
2711   out:
2712   /* Clean up.  */
2713
2714   end_alias_analysis ();
2715   free (reg_equiv);
2716   return recorded_label_ref;
2717 }
2718
2719 \f
2720
2721 /* Print chain C to FILE.  */
2722 static void
2723 print_insn_chain (FILE *file, struct insn_chain *c)
2724 {
2725   fprintf (file, "insn=%d, ", INSN_UID(c->insn));
2726   bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
2727   bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
2728 }
2729
2730
2731 /* Print all reload_insn_chains to FILE.  */
2732 static void
2733 print_insn_chains (FILE *file)
2734 {
2735   struct insn_chain *c;
2736   for (c = reload_insn_chain; c ; c = c->next)
2737     print_insn_chain (file, c);
2738 }
2739
2740 /* Return true if pseudo REGNO should be added to set live_throughout
2741    or dead_or_set of the insn chains for reload consideration.  */
2742 static bool
2743 pseudo_for_reload_consideration_p (int regno)
2744 {
2745   /* Consider spilled pseudos too for IRA because they still have a
2746      chance to get hard-registers in the reload when IRA is used.  */
2747   return (reg_renumber[regno] >= 0 || ira_conflicts_p);
2748 }
2749
2750 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
2751    REG to the number of nregs, and INIT_VALUE to get the
2752    initialization.  ALLOCNUM need not be the regno of REG.  */
2753 static void
2754 init_live_subregs (bool init_value, sbitmap *live_subregs,
2755                    int *live_subregs_used, int allocnum, rtx reg)
2756 {
2757   unsigned int regno = REGNO (SUBREG_REG (reg));
2758   int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2759
2760   gcc_assert (size > 0);
2761
2762   /* Been there, done that.  */
2763   if (live_subregs_used[allocnum])
2764     return;
2765
2766   /* Create a new one with zeros.  */
2767   if (live_subregs[allocnum] == NULL)
2768     live_subregs[allocnum] = sbitmap_alloc (size);
2769
2770   /* If the entire reg was live before blasting into subregs, we need
2771      to init all of the subregs to ones else init to 0.  */
2772   if (init_value)
2773     sbitmap_ones (live_subregs[allocnum]);
2774   else
2775     sbitmap_zero (live_subregs[allocnum]);
2776
2777   /* Set the number of bits that we really want.  */
2778   live_subregs_used[allocnum] = size;
2779 }
2780
2781 /* Walk the insns of the current function and build reload_insn_chain,
2782    and record register life information.  */
2783 static void
2784 build_insn_chain (void)
2785 {
2786   unsigned int i;
2787   struct insn_chain **p = &reload_insn_chain;
2788   basic_block bb;
2789   struct insn_chain *c = NULL;
2790   struct insn_chain *next = NULL;
2791   bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
2792   bitmap elim_regset = BITMAP_ALLOC (NULL);
2793   /* live_subregs is a vector used to keep accurate information about
2794      which hardregs are live in multiword pseudos.  live_subregs and
2795      live_subregs_used are indexed by pseudo number.  The live_subreg
2796      entry for a particular pseudo is only used if the corresponding
2797      element is non zero in live_subregs_used.  The value in
2798      live_subregs_used is number of bytes that the pseudo can
2799      occupy.  */
2800   sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
2801   int *live_subregs_used = XNEWVEC (int, max_regno);
2802
2803   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2804     if (TEST_HARD_REG_BIT (eliminable_regset, i))
2805       bitmap_set_bit (elim_regset, i);
2806   FOR_EACH_BB_REVERSE (bb)
2807     {
2808       bitmap_iterator bi;
2809       rtx insn;
2810
2811       CLEAR_REG_SET (live_relevant_regs);
2812       memset (live_subregs_used, 0, max_regno * sizeof (int));
2813
2814       EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb), 0, i, bi)
2815         {
2816           if (i >= FIRST_PSEUDO_REGISTER)
2817             break;
2818           bitmap_set_bit (live_relevant_regs, i);
2819         }
2820
2821       EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb),
2822                                 FIRST_PSEUDO_REGISTER, i, bi)
2823         {
2824           if (pseudo_for_reload_consideration_p (i))
2825             bitmap_set_bit (live_relevant_regs, i);
2826         }
2827
2828       FOR_BB_INSNS_REVERSE (bb, insn)
2829         {
2830           if (!NOTE_P (insn) && !BARRIER_P (insn))
2831             {
2832               unsigned int uid = INSN_UID (insn);
2833               df_ref *def_rec;
2834               df_ref *use_rec;
2835
2836               c = new_insn_chain ();
2837               c->next = next;
2838               next = c;
2839               *p = c;
2840               p = &c->prev;
2841
2842               c->insn = insn;
2843               c->block = bb->index;
2844
2845               if (INSN_P (insn))
2846                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2847                   {
2848                     df_ref def = *def_rec;
2849                     unsigned int regno = DF_REF_REGNO (def);
2850
2851                     /* Ignore may clobbers because these are generated
2852                        from calls. However, every other kind of def is
2853                        added to dead_or_set.  */
2854                     if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2855                       {
2856                         if (regno < FIRST_PSEUDO_REGISTER)
2857                           {
2858                             if (!fixed_regs[regno])
2859                               bitmap_set_bit (&c->dead_or_set, regno);
2860                           }
2861                         else if (pseudo_for_reload_consideration_p (regno))
2862                           bitmap_set_bit (&c->dead_or_set, regno);
2863                       }
2864
2865                     if ((regno < FIRST_PSEUDO_REGISTER
2866                          || reg_renumber[regno] >= 0
2867                          || ira_conflicts_p)
2868                         && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
2869                       {
2870                         rtx reg = DF_REF_REG (def);
2871
2872                         /* We can model subregs, but not if they are
2873                            wrapped in ZERO_EXTRACTS.  */
2874                         if (GET_CODE (reg) == SUBREG
2875                             && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
2876                           {
2877                             unsigned int start = SUBREG_BYTE (reg);
2878                             unsigned int last = start
2879                               + GET_MODE_SIZE (GET_MODE (reg));
2880
2881                             init_live_subregs
2882                               (bitmap_bit_p (live_relevant_regs, regno),
2883                                live_subregs, live_subregs_used, regno, reg);
2884
2885                             if (!DF_REF_FLAGS_IS_SET
2886                                 (def, DF_REF_STRICT_LOW_PART))
2887                               {
2888                                 /* Expand the range to cover entire words.
2889                                    Bytes added here are "don't care".  */
2890                                 start
2891                                   = start / UNITS_PER_WORD * UNITS_PER_WORD;
2892                                 last = ((last + UNITS_PER_WORD - 1)
2893                                         / UNITS_PER_WORD * UNITS_PER_WORD);
2894                               }
2895
2896                             /* Ignore the paradoxical bits.  */
2897                             if ((int)last > live_subregs_used[regno])
2898                               last = live_subregs_used[regno];
2899
2900                             while (start < last)
2901                               {
2902                                 RESET_BIT (live_subregs[regno], start);
2903                                 start++;
2904                               }
2905
2906                             if (sbitmap_empty_p (live_subregs[regno]))
2907                               {
2908                                 live_subregs_used[regno] = 0;
2909                                 bitmap_clear_bit (live_relevant_regs, regno);
2910                               }
2911                             else
2912                               /* Set live_relevant_regs here because
2913                                  that bit has to be true to get us to
2914                                  look at the live_subregs fields.  */
2915                               bitmap_set_bit (live_relevant_regs, regno);
2916                           }
2917                         else
2918                           {
2919                             /* DF_REF_PARTIAL is generated for
2920                                subregs, STRICT_LOW_PART, and
2921                                ZERO_EXTRACT.  We handle the subreg
2922                                case above so here we have to keep from
2923                                modeling the def as a killing def.  */
2924                             if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
2925                               {
2926                                 bitmap_clear_bit (live_relevant_regs, regno);
2927                                 live_subregs_used[regno] = 0;
2928                               }
2929                           }
2930                       }
2931                   }
2932
2933               bitmap_and_compl_into (live_relevant_regs, elim_regset);
2934               bitmap_copy (&c->live_throughout, live_relevant_regs);
2935
2936               if (INSN_P (insn))
2937                 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2938                   {
2939                     df_ref use = *use_rec;
2940                     unsigned int regno = DF_REF_REGNO (use);
2941                     rtx reg = DF_REF_REG (use);
2942
2943                     /* DF_REF_READ_WRITE on a use means that this use
2944                        is fabricated from a def that is a partial set
2945                        to a multiword reg.  Here, we only model the
2946                        subreg case that is not wrapped in ZERO_EXTRACT
2947                        precisely so we do not need to look at the
2948                        fabricated use. */
2949                     if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
2950                         && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
2951                         && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
2952                       continue;
2953
2954                     /* Add the last use of each var to dead_or_set.  */
2955                     if (!bitmap_bit_p (live_relevant_regs, regno))
2956                       {
2957                         if (regno < FIRST_PSEUDO_REGISTER)
2958                           {
2959                             if (!fixed_regs[regno])
2960                               bitmap_set_bit (&c->dead_or_set, regno);
2961                           }
2962                         else if (pseudo_for_reload_consideration_p (regno))
2963                           bitmap_set_bit (&c->dead_or_set, regno);
2964                       }
2965
2966                     if (regno < FIRST_PSEUDO_REGISTER
2967                         || pseudo_for_reload_consideration_p (regno))
2968                       {
2969                         if (GET_CODE (reg) == SUBREG
2970                             && !DF_REF_FLAGS_IS_SET (use,
2971                                                      DF_REF_SIGN_EXTRACT
2972                                                      | DF_REF_ZERO_EXTRACT))
2973                           {
2974                             unsigned int start = SUBREG_BYTE (reg);
2975                             unsigned int last = start
2976                               + GET_MODE_SIZE (GET_MODE (reg));
2977
2978                             init_live_subregs
2979                               (bitmap_bit_p (live_relevant_regs, regno),
2980                                live_subregs, live_subregs_used, regno, reg);
2981
2982                             /* Ignore the paradoxical bits.  */
2983                             if ((int)last > live_subregs_used[regno])
2984                               last = live_subregs_used[regno];
2985
2986                             while (start < last)
2987                               {
2988                                 SET_BIT (live_subregs[regno], start);
2989                                 start++;
2990                               }
2991                           }
2992                         else
2993                           /* Resetting the live_subregs_used is
2994                              effectively saying do not use the subregs
2995                              because we are reading the whole
2996                              pseudo.  */
2997                           live_subregs_used[regno] = 0;
2998                         bitmap_set_bit (live_relevant_regs, regno);
2999                       }
3000                   }
3001             }
3002         }
3003
3004       /* FIXME!! The following code is a disaster.  Reload needs to see the
3005          labels and jump tables that are just hanging out in between
3006          the basic blocks.  See pr33676.  */
3007       insn = BB_HEAD (bb);
3008
3009       /* Skip over the barriers and cruft.  */
3010       while (insn && (BARRIER_P (insn) || NOTE_P (insn)
3011                       || BLOCK_FOR_INSN (insn) == bb))
3012         insn = PREV_INSN (insn);
3013
3014       /* While we add anything except barriers and notes, the focus is
3015          to get the labels and jump tables into the
3016          reload_insn_chain.  */
3017       while (insn)
3018         {
3019           if (!NOTE_P (insn) && !BARRIER_P (insn))
3020             {
3021               if (BLOCK_FOR_INSN (insn))
3022                 break;
3023
3024               c = new_insn_chain ();
3025               c->next = next;
3026               next = c;
3027               *p = c;
3028               p = &c->prev;
3029
3030               /* The block makes no sense here, but it is what the old
3031                  code did.  */
3032               c->block = bb->index;
3033               c->insn = insn;
3034               bitmap_copy (&c->live_throughout, live_relevant_regs);
3035             }
3036           insn = PREV_INSN (insn);
3037         }
3038     }
3039
3040   for (i = 0; i < (unsigned int) max_regno; i++)
3041     if (live_subregs[i])
3042       free (live_subregs[i]);
3043
3044   reload_insn_chain = c;
3045   *p = NULL;
3046
3047   free (live_subregs);
3048   free (live_subregs_used);
3049   BITMAP_FREE (live_relevant_regs);
3050   BITMAP_FREE (elim_regset);
3051
3052   if (dump_file)
3053     print_insn_chains (dump_file);
3054 }
3055 \f
3056 /* Allocate memory for reg_equiv_memory_loc.  */
3057 static void
3058 init_reg_equiv_memory_loc (void)
3059 {
3060   max_regno = max_reg_num ();
3061
3062   /* And the reg_equiv_memory_loc array.  */
3063   VEC_safe_grow (rtx, gc, reg_equiv_memory_loc_vec, max_regno);
3064   memset (VEC_address (rtx, reg_equiv_memory_loc_vec), 0,
3065           sizeof (rtx) * max_regno);
3066   reg_equiv_memory_loc = VEC_address (rtx, reg_equiv_memory_loc_vec);
3067 }
3068
3069 /* All natural loops.  */
3070 struct loops ira_loops;
3071
3072 /* True if we have allocno conflicts.  It is false for non-optimized
3073    mode or when the conflict table is too big.  */
3074 bool ira_conflicts_p;
3075
3076 /* This is the main entry of IRA.  */
3077 static void
3078 ira (FILE *f)
3079 {
3080   int overall_cost_before, allocated_reg_info_size;
3081   bool loops_p;
3082   int max_regno_before_ira, ira_max_point_before_emit;
3083   int rebuild_p;
3084   int saved_flag_ira_share_spill_slots;
3085   basic_block bb;
3086
3087   timevar_push (TV_IRA);
3088
3089   if (flag_caller_saves)
3090     init_caller_save ();
3091
3092   if (flag_ira_verbose < 10)
3093     {
3094       internal_flag_ira_verbose = flag_ira_verbose;
3095       ira_dump_file = f;
3096     }
3097   else
3098     {
3099       internal_flag_ira_verbose = flag_ira_verbose - 10;
3100       ira_dump_file = stderr;
3101     }
3102
3103   ira_conflicts_p = optimize > 0;
3104   setup_prohibited_mode_move_regs ();
3105
3106   df_note_add_problem ();
3107
3108   if (optimize == 1)
3109     {
3110       df_live_add_problem ();
3111       df_live_set_all_dirty ();
3112     }
3113 #ifdef ENABLE_CHECKING
3114   df->changeable_flags |= DF_VERIFY_SCHEDULED;
3115 #endif
3116   df_analyze ();
3117   df_clear_flags (DF_NO_INSN_RESCAN);
3118   regstat_init_n_sets_and_refs ();
3119   regstat_compute_ri ();
3120
3121   /* If we are not optimizing, then this is the only place before
3122      register allocation where dataflow is done.  And that is needed
3123      to generate these warnings.  */
3124   if (warn_clobbered)
3125     generate_setjmp_warnings ();
3126
3127   /* Determine if the current function is a leaf before running IRA
3128      since this can impact optimizations done by the prologue and
3129      epilogue thus changing register elimination offsets.  */
3130   current_function_is_leaf = leaf_function_p ();
3131
3132   if (resize_reg_info () && flag_ira_loop_pressure)
3133     ira_set_pseudo_classes (ira_dump_file);
3134
3135   rebuild_p = update_equiv_regs ();
3136
3137 #ifndef IRA_NO_OBSTACK
3138   gcc_obstack_init (&ira_obstack);
3139 #endif
3140   bitmap_obstack_initialize (&ira_bitmap_obstack);
3141   if (optimize)
3142     {
3143       max_regno = max_reg_num ();
3144       ira_reg_equiv_len = max_regno;
3145       ira_reg_equiv_invariant_p
3146         = (bool *) ira_allocate (max_regno * sizeof (bool));
3147       memset (ira_reg_equiv_invariant_p, 0, max_regno * sizeof (bool));
3148       ira_reg_equiv_const = (rtx *) ira_allocate (max_regno * sizeof (rtx));
3149       memset (ira_reg_equiv_const, 0, max_regno * sizeof (rtx));
3150       find_reg_equiv_invariant_const ();
3151       if (rebuild_p)
3152         {
3153           timevar_push (TV_JUMP);
3154           rebuild_jump_labels (get_insns ());
3155           purge_all_dead_edges ();
3156           timevar_pop (TV_JUMP);
3157         }
3158     }
3159
3160   max_regno_before_ira = allocated_reg_info_size = max_reg_num ();
3161   ira_setup_eliminable_regset ();
3162
3163   ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
3164   ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
3165   ira_move_loops_num = ira_additional_jumps_num = 0;
3166
3167   ira_assert (current_loops == NULL);
3168   flow_loops_find (&ira_loops);
3169   record_loop_exits ();
3170   current_loops = &ira_loops;
3171
3172   init_reg_equiv_memory_loc ();
3173
3174   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3175     fprintf (ira_dump_file, "Building IRA IR\n");
3176   loops_p = ira_build (optimize
3177                        && (flag_ira_region == IRA_REGION_ALL
3178                            || flag_ira_region == IRA_REGION_MIXED));
3179
3180   ira_assert (ira_conflicts_p || !loops_p);
3181
3182   saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
3183   if (too_high_register_pressure_p () || cfun->calls_setjmp)
3184     /* It is just wasting compiler's time to pack spilled pseudos into
3185        stack slots in this case -- prohibit it.  We also do this if
3186        there is setjmp call because a variable not modified between
3187        setjmp and longjmp the compiler is required to preserve its
3188        value and sharing slots does not guarantee it.  */
3189     flag_ira_share_spill_slots = FALSE;
3190
3191   ira_color ();
3192
3193   ira_max_point_before_emit = ira_max_point;
3194
3195   ira_emit (loops_p);
3196
3197   if (ira_conflicts_p)
3198     {
3199       max_regno = max_reg_num ();
3200
3201       if (! loops_p)
3202         ira_initiate_assign ();
3203       else
3204         {
3205           expand_reg_info (allocated_reg_info_size);
3206           setup_preferred_alternate_classes_for_new_pseudos
3207             (allocated_reg_info_size);
3208           allocated_reg_info_size = max_regno;
3209
3210           if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3211             fprintf (ira_dump_file, "Flattening IR\n");
3212           ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
3213           /* New insns were generated: add notes and recalculate live
3214              info.  */
3215           df_analyze ();
3216
3217           flow_loops_find (&ira_loops);
3218           record_loop_exits ();
3219           current_loops = &ira_loops;
3220
3221           setup_allocno_assignment_flags ();
3222           ira_initiate_assign ();
3223           ira_reassign_conflict_allocnos (max_regno);
3224         }
3225     }
3226
3227   setup_reg_renumber ();
3228
3229   calculate_allocation_cost ();
3230
3231 #ifdef ENABLE_IRA_CHECKING
3232   if (ira_conflicts_p)
3233     check_allocation ();
3234 #endif
3235
3236   delete_trivially_dead_insns (get_insns (), max_reg_num ());
3237
3238   init_reg_equiv_memory_loc ();
3239
3240   if (max_regno != max_regno_before_ira)
3241     {
3242       regstat_free_n_sets_and_refs ();
3243       regstat_free_ri ();
3244       regstat_init_n_sets_and_refs ();
3245       regstat_compute_ri ();
3246     }
3247
3248   allocate_initial_values (reg_equiv_memory_loc);
3249
3250   overall_cost_before = ira_overall_cost;
3251   if (ira_conflicts_p)
3252     {
3253       fix_reg_equiv_init ();
3254
3255 #ifdef ENABLE_IRA_CHECKING
3256       print_redundant_copies ();
3257 #endif
3258
3259       ira_spilled_reg_stack_slots_num = 0;
3260       ira_spilled_reg_stack_slots
3261         = ((struct ira_spilled_reg_stack_slot *)
3262            ira_allocate (max_regno
3263                          * sizeof (struct ira_spilled_reg_stack_slot)));
3264       memset (ira_spilled_reg_stack_slots, 0,
3265               max_regno * sizeof (struct ira_spilled_reg_stack_slot));
3266     }
3267
3268   timevar_pop (TV_IRA);
3269
3270   timevar_push (TV_RELOAD);
3271   df_set_flags (DF_NO_INSN_RESCAN);
3272   build_insn_chain ();
3273
3274   reload_completed = !reload (get_insns (), ira_conflicts_p);
3275
3276   finish_subregs_of_mode ();
3277
3278   timevar_pop (TV_RELOAD);
3279
3280   timevar_push (TV_IRA);
3281
3282   if (ira_conflicts_p)
3283     {
3284       ira_free (ira_spilled_reg_stack_slots);
3285
3286       ira_finish_assign ();
3287
3288     }
3289   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
3290       && overall_cost_before != ira_overall_cost)
3291     fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
3292   ira_destroy ();
3293
3294   flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
3295
3296   flow_loops_free (&ira_loops);
3297   free_dominance_info (CDI_DOMINATORS);
3298   FOR_ALL_BB (bb)
3299     bb->loop_father = NULL;
3300   current_loops = NULL;
3301
3302   regstat_free_ri ();
3303   regstat_free_n_sets_and_refs ();
3304
3305   if (optimize)
3306     {
3307       cleanup_cfg (CLEANUP_EXPENSIVE);
3308
3309       ira_free (ira_reg_equiv_invariant_p);
3310       ira_free (ira_reg_equiv_const);
3311     }
3312
3313   bitmap_obstack_release (&ira_bitmap_obstack);
3314 #ifndef IRA_NO_OBSTACK
3315   obstack_free (&ira_obstack, NULL);
3316 #endif
3317
3318   /* The code after the reload has changed so much that at this point
3319      we might as well just rescan everything.  Not that
3320      df_rescan_all_insns is not going to help here because it does not
3321      touch the artificial uses and defs.  */
3322   df_finish_pass (true);
3323   if (optimize > 1)
3324     df_live_add_problem ();
3325   df_scan_alloc (NULL);
3326   df_scan_blocks ();
3327
3328   if (optimize)
3329     df_analyze ();
3330
3331   timevar_pop (TV_IRA);
3332 }
3333
3334 \f
3335
3336 static bool
3337 gate_ira (void)
3338 {
3339   return true;
3340 }
3341
3342 /* Run the integrated register allocator.  */
3343 static unsigned int
3344 rest_of_handle_ira (void)
3345 {
3346   ira (dump_file);
3347   return 0;
3348 }
3349
3350 struct rtl_opt_pass pass_ira =
3351 {
3352  {
3353   RTL_PASS,
3354   "ira",                                /* name */
3355   gate_ira,                             /* gate */
3356   rest_of_handle_ira,                   /* execute */
3357   NULL,                                 /* sub */
3358   NULL,                                 /* next */
3359   0,                                    /* static_pass_number */
3360   TV_NONE,                              /* tv_id */
3361   0,                                    /* properties_required */
3362   0,                                    /* properties_provided */
3363   0,                                    /* properties_destroyed */
3364   0,                                    /* todo_flags_start */
3365   TODO_dump_func |
3366   TODO_ggc_collect                      /* todo_flags_finish */
3367  }
3368 };