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][0] = -1;
 401           ira_class_hard_reg_index[cl][0] = -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       if (CALL_P (insn) && ! MEM_READONLY_P (memref)
1919           && ! RTL_CONST_OR_PURE_CALL_P (insn))
1920         return 0;
1921
1922       note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
1923
1924       /* If a register mentioned in MEMREF is modified via an
1925          auto-increment, we lose the equivalence.  Do the same if one
1926          dies; although we could extend the life, it doesn't seem worth
1927          the trouble.  */
1928
1929       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1930         if ((REG_NOTE_KIND (note) == REG_INC
1931              || REG_NOTE_KIND (note) == REG_DEAD)
1932             && REG_P (XEXP (note, 0))
1933             && reg_overlap_mentioned_p (XEXP (note, 0), memref))
1934           return 0;
1935     }
1936
1937   return 0;
1938 }
1939
1940 /* Returns zero if X is known to be invariant.  */
1941 static int
1942 equiv_init_varies_p (rtx x)
1943 {
1944   RTX_CODE code = GET_CODE (x);
1945   int i;
1946   const char *fmt;
1947
1948   switch (code)
1949     {
1950     case MEM:
1951       return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
1952
1953     case CONST:
1954     case CONST_INT:
1955     case CONST_DOUBLE:
1956     case CONST_FIXED:
1957     case CONST_VECTOR:
1958     case SYMBOL_REF:
1959     case LABEL_REF:
1960       return 0;
1961
1962     case REG:
1963       return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
1964
1965     case ASM_OPERANDS:
1966       if (MEM_VOLATILE_P (x))
1967         return 1;
1968
1969       /* Fall through.  */
1970
1971     default:
1972       break;
1973     }
1974
1975   fmt = GET_RTX_FORMAT (code);
1976   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1977     if (fmt[i] == 'e')
1978       {
1979         if (equiv_init_varies_p (XEXP (x, i)))
1980           return 1;
1981       }
1982     else if (fmt[i] == 'E')
1983       {
1984         int j;
1985         for (j = 0; j < XVECLEN (x, i); j++)
1986           if (equiv_init_varies_p (XVECEXP (x, i, j)))
1987             return 1;
1988       }
1989
1990   return 0;
1991 }
1992
1993 /* Returns nonzero if X (used to initialize register REGNO) is movable.
1994    X is only movable if the registers it uses have equivalent initializations
1995    which appear to be within the same loop (or in an inner loop) and movable
1996    or if they are not candidates for local_alloc and don't vary.  */
1997 static int
1998 equiv_init_movable_p (rtx x, int regno)
1999 {
2000   int i, j;
2001   const char *fmt;
2002   enum rtx_code code = GET_CODE (x);
2003
2004   switch (code)
2005     {
2006     case SET:
2007       return equiv_init_movable_p (SET_SRC (x), regno);
2008
2009     case CC0:
2010     case CLOBBER:
2011       return 0;
2012
2013     case PRE_INC:
2014     case PRE_DEC:
2015     case POST_INC:
2016     case POST_DEC:
2017     case PRE_MODIFY:
2018     case POST_MODIFY:
2019       return 0;
2020
2021     case REG:
2022       return (reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
2023               && reg_equiv[REGNO (x)].replace)
2024              || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS && ! rtx_varies_p (x, 0));
2025
2026     case UNSPEC_VOLATILE:
2027       return 0;
2028
2029     case ASM_OPERANDS:
2030       if (MEM_VOLATILE_P (x))
2031         return 0;
2032
2033       /* Fall through.  */
2034
2035     default:
2036       break;
2037     }
2038
2039   fmt = GET_RTX_FORMAT (code);
2040   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2041     switch (fmt[i])
2042       {
2043       case 'e':
2044         if (! equiv_init_movable_p (XEXP (x, i), regno))
2045           return 0;
2046         break;
2047       case 'E':
2048         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2049           if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
2050             return 0;
2051         break;
2052       }
2053
2054   return 1;
2055 }
2056
2057 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true.  */
2058 static int
2059 contains_replace_regs (rtx x)
2060 {
2061   int i, j;
2062   const char *fmt;
2063   enum rtx_code code = GET_CODE (x);
2064
2065   switch (code)
2066     {
2067     case CONST_INT:
2068     case CONST:
2069     case LABEL_REF:
2070     case SYMBOL_REF:
2071     case CONST_DOUBLE:
2072     case CONST_FIXED:
2073     case CONST_VECTOR:
2074     case PC:
2075     case CC0:
2076     case HIGH:
2077       return 0;
2078
2079     case REG:
2080       return reg_equiv[REGNO (x)].replace;
2081
2082     default:
2083       break;
2084     }
2085
2086   fmt = GET_RTX_FORMAT (code);
2087   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2088     switch (fmt[i])
2089       {
2090       case 'e':
2091         if (contains_replace_regs (XEXP (x, i)))
2092           return 1;
2093         break;
2094       case 'E':
2095         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2096           if (contains_replace_regs (XVECEXP (x, i, j)))
2097             return 1;
2098         break;
2099       }
2100
2101   return 0;
2102 }
2103
2104 /* TRUE if X references a memory location that would be affected by a store
2105    to MEMREF.  */
2106 static int
2107 memref_referenced_p (rtx memref, rtx x)
2108 {
2109   int i, j;
2110   const char *fmt;
2111   enum rtx_code code = GET_CODE (x);
2112
2113   switch (code)
2114     {
2115     case CONST_INT:
2116     case CONST:
2117     case LABEL_REF:
2118     case SYMBOL_REF:
2119     case CONST_DOUBLE:
2120     case CONST_FIXED:
2121     case CONST_VECTOR:
2122     case PC:
2123     case CC0:
2124     case HIGH:
2125     case LO_SUM:
2126       return 0;
2127
2128     case REG:
2129       return (reg_equiv[REGNO (x)].replacement
2130               && memref_referenced_p (memref,
2131                                       reg_equiv[REGNO (x)].replacement));
2132
2133     case MEM:
2134       if (true_dependence (memref, VOIDmode, x, rtx_varies_p))
2135         return 1;
2136       break;
2137
2138     case SET:
2139       /* If we are setting a MEM, it doesn't count (its address does), but any
2140          other SET_DEST that has a MEM in it is referencing the MEM.  */
2141       if (MEM_P (SET_DEST (x)))
2142         {
2143           if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
2144             return 1;
2145         }
2146       else if (memref_referenced_p (memref, SET_DEST (x)))
2147         return 1;
2148
2149       return memref_referenced_p (memref, SET_SRC (x));
2150
2151     default:
2152       break;
2153     }
2154
2155   fmt = GET_RTX_FORMAT (code);
2156   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2157     switch (fmt[i])
2158       {
2159       case 'e':
2160         if (memref_referenced_p (memref, XEXP (x, i)))
2161           return 1;
2162         break;
2163       case 'E':
2164         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2165           if (memref_referenced_p (memref, XVECEXP (x, i, j)))
2166             return 1;
2167         break;
2168       }
2169
2170   return 0;
2171 }
2172
2173 /* TRUE if some insn in the range (START, END] references a memory location
2174    that would be affected by a store to MEMREF.  */
2175 static int
2176 memref_used_between_p (rtx memref, rtx start, rtx end)
2177 {
2178   rtx insn;
2179
2180   for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2181        insn = NEXT_INSN (insn))
2182     {
2183       if (!NONDEBUG_INSN_P (insn))
2184         continue;
2185
2186       if (memref_referenced_p (memref, PATTERN (insn)))
2187         return 1;
2188
2189       /* Nonconst functions may access memory.  */
2190       if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
2191         return 1;
2192     }
2193
2194   return 0;
2195 }
2196
2197 /* Mark REG as having no known equivalence.
2198    Some instructions might have been processed before and furnished
2199    with REG_EQUIV notes for this register; these notes will have to be
2200    removed.
2201    STORE is the piece of RTL that does the non-constant / conflicting
2202    assignment - a SET, CLOBBER or REG_INC note.  It is currently not used,
2203    but needs to be there because this function is called from note_stores.  */
2204 static void
2205 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
2206 {
2207   int regno;
2208   rtx list;
2209
2210   if (!REG_P (reg))
2211     return;
2212   regno = REGNO (reg);
2213   list = reg_equiv[regno].init_insns;
2214   if (list == const0_rtx)
2215     return;
2216   reg_equiv[regno].init_insns = const0_rtx;
2217   reg_equiv[regno].replacement = NULL_RTX;
2218   /* This doesn't matter for equivalences made for argument registers, we
2219      should keep their initialization insns.  */
2220   if (reg_equiv[regno].is_arg_equivalence)
2221     return;
2222   reg_equiv_init[regno] = NULL_RTX;
2223   for (; list; list =  XEXP (list, 1))
2224     {
2225       rtx insn = XEXP (list, 0);
2226       remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
2227     }
2228 }
2229
2230 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
2231    equivalent replacement.  */
2232
2233 static rtx
2234 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
2235 {
2236   if (REG_P (loc))
2237     {
2238       bitmap cleared_regs = (bitmap) data;
2239       if (bitmap_bit_p (cleared_regs, REGNO (loc)))
2240         return simplify_replace_fn_rtx (*reg_equiv[REGNO (loc)].src_p,
2241                                         NULL_RTX, adjust_cleared_regs, data);
2242     }
2243   return NULL_RTX;
2244 }
2245
2246 /* Nonzero if we recorded an equivalence for a LABEL_REF.  */
2247 static int recorded_label_ref;
2248
2249 /* Find registers that are equivalent to a single value throughout the
2250    compilation (either because they can be referenced in memory or are set once
2251    from a single constant).  Lower their priority for a register.
2252
2253    If such a register is only referenced once, try substituting its value
2254    into the using insn.  If it succeeds, we can eliminate the register
2255    completely.
2256
2257    Initialize the REG_EQUIV_INIT array of initializing insns.
2258
2259    Return non-zero if jump label rebuilding should be done.  */
2260 static int
2261 update_equiv_regs (void)
2262 {
2263   rtx insn;
2264   basic_block bb;
2265   int loop_depth;
2266   bitmap cleared_regs;
2267
2268   /* We need to keep track of whether or not we recorded a LABEL_REF so
2269      that we know if the jump optimizer needs to be rerun.  */
2270   recorded_label_ref = 0;
2271
2272   reg_equiv = XCNEWVEC (struct equivalence, max_regno);
2273   reg_equiv_init = ggc_alloc_cleared_vec_rtx (max_regno);
2274   reg_equiv_init_size = max_regno;
2275
2276   init_alias_analysis ();
2277
2278   /* Scan the insns and find which registers have equivalences.  Do this
2279      in a separate scan of the insns because (due to -fcse-follow-jumps)
2280      a register can be set below its use.  */
2281   FOR_EACH_BB (bb)
2282     {
2283       loop_depth = bb->loop_depth;
2284
2285       for (insn = BB_HEAD (bb);
2286            insn != NEXT_INSN (BB_END (bb));
2287            insn = NEXT_INSN (insn))
2288         {
2289           rtx note;
2290           rtx set;
2291           rtx dest, src;
2292           int regno;
2293
2294           if (! INSN_P (insn))
2295             continue;
2296
2297           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2298             if (REG_NOTE_KIND (note) == REG_INC)
2299               no_equiv (XEXP (note, 0), note, NULL);
2300
2301           set = single_set (insn);
2302
2303           /* If this insn contains more (or less) than a single SET,
2304              only mark all destinations as having no known equivalence.  */
2305           if (set == 0)
2306             {
2307               note_stores (PATTERN (insn), no_equiv, NULL);
2308               continue;
2309             }
2310           else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2311             {
2312               int i;
2313
2314               for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2315                 {
2316                   rtx part = XVECEXP (PATTERN (insn), 0, i);
2317                   if (part != set)
2318                     note_stores (part, no_equiv, NULL);
2319                 }
2320             }
2321
2322           dest = SET_DEST (set);
2323           src = SET_SRC (set);
2324
2325           /* See if this is setting up the equivalence between an argument
2326              register and its stack slot.  */
2327           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2328           if (note)
2329             {
2330               gcc_assert (REG_P (dest));
2331               regno = REGNO (dest);
2332
2333               /* Note that we don't want to clear reg_equiv_init even if there
2334                  are multiple sets of this register.  */
2335               reg_equiv[regno].is_arg_equivalence = 1;
2336
2337               /* Record for reload that this is an equivalencing insn.  */
2338               if (rtx_equal_p (src, XEXP (note, 0)))
2339                 reg_equiv_init[regno]
2340                   = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
2341
2342               /* Continue normally in case this is a candidate for
2343                  replacements.  */
2344             }
2345
2346           if (!optimize)
2347             continue;
2348
2349           /* We only handle the case of a pseudo register being set
2350              once, or always to the same value.  */
2351           /* ??? The mn10200 port breaks if we add equivalences for
2352              values that need an ADDRESS_REGS register and set them equivalent
2353              to a MEM of a pseudo.  The actual problem is in the over-conservative
2354              handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
2355              calculate_needs, but we traditionally work around this problem
2356              here by rejecting equivalences when the destination is in a register
2357              that's likely spilled.  This is fragile, of course, since the
2358              preferred class of a pseudo depends on all instructions that set
2359              or use it.  */
2360
2361           if (!REG_P (dest)
2362               || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
2363               || reg_equiv[regno].init_insns == const0_rtx
2364               || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
2365                   && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
2366             {
2367               /* This might be setting a SUBREG of a pseudo, a pseudo that is
2368                  also set somewhere else to a constant.  */
2369               note_stores (set, no_equiv, NULL);
2370               continue;
2371             }
2372
2373           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
2374
2375           /* cse sometimes generates function invariants, but doesn't put a
2376              REG_EQUAL note on the insn.  Since this note would be redundant,
2377              there's no point creating it earlier than here.  */
2378           if (! note && ! rtx_varies_p (src, 0))
2379             note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
2380
2381           /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
2382              since it represents a function call */
2383           if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
2384             note = NULL_RTX;
2385
2386           if (DF_REG_DEF_COUNT (regno) != 1
2387               && (! note
2388                   || rtx_varies_p (XEXP (note, 0), 0)
2389                   || (reg_equiv[regno].replacement
2390                       && ! rtx_equal_p (XEXP (note, 0),
2391                                         reg_equiv[regno].replacement))))
2392             {
2393               no_equiv (dest, set, NULL);
2394               continue;
2395             }
2396           /* Record this insn as initializing this register.  */
2397           reg_equiv[regno].init_insns
2398             = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
2399
2400           /* If this register is known to be equal to a constant, record that
2401              it is always equivalent to the constant.  */
2402           if (DF_REG_DEF_COUNT (regno) == 1
2403               && note && ! rtx_varies_p (XEXP (note, 0), 0))
2404             {
2405               rtx note_value = XEXP (note, 0);
2406               remove_note (insn, note);
2407               set_unique_reg_note (insn, REG_EQUIV, note_value);
2408             }
2409
2410           /* If this insn introduces a "constant" register, decrease the priority
2411              of that register.  Record this insn if the register is only used once
2412              more and the equivalence value is the same as our source.
2413
2414              The latter condition is checked for two reasons:  First, it is an
2415              indication that it may be more efficient to actually emit the insn
2416              as written (if no registers are available, reload will substitute
2417              the equivalence).  Secondly, it avoids problems with any registers
2418              dying in this insn whose death notes would be missed.
2419
2420              If we don't have a REG_EQUIV note, see if this insn is loading
2421              a register used only in one basic block from a MEM.  If so, and the
2422              MEM remains unchanged for the life of the register, add a REG_EQUIV
2423              note.  */
2424
2425           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2426
2427           if (note == 0 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2428               && MEM_P (SET_SRC (set))
2429               && validate_equiv_mem (insn, dest, SET_SRC (set)))
2430             note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
2431
2432           if (note)
2433             {
2434               int regno = REGNO (dest);
2435               rtx x = XEXP (note, 0);
2436
2437               /* If we haven't done so, record for reload that this is an
2438                  equivalencing insn.  */
2439               if (!reg_equiv[regno].is_arg_equivalence)
2440                 reg_equiv_init[regno]
2441                   = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
2442
2443               /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
2444                  We might end up substituting the LABEL_REF for uses of the
2445                  pseudo here or later.  That kind of transformation may turn an
2446                  indirect jump into a direct jump, in which case we must rerun the
2447                  jump optimizer to ensure that the JUMP_LABEL fields are valid.  */
2448               if (GET_CODE (x) == LABEL_REF
2449                   || (GET_CODE (x) == CONST
2450                       && GET_CODE (XEXP (x, 0)) == PLUS
2451                       && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
2452                 recorded_label_ref = 1;
2453
2454               reg_equiv[regno].replacement = x;
2455               reg_equiv[regno].src_p = &SET_SRC (set);
2456               reg_equiv[regno].loop_depth = loop_depth;
2457
2458               /* Don't mess with things live during setjmp.  */
2459               if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
2460                 {
2461                   /* Note that the statement below does not affect the priority
2462                      in local-alloc!  */
2463                   REG_LIVE_LENGTH (regno) *= 2;
2464
2465                   /* If the register is referenced exactly twice, meaning it is
2466                      set once and used once, indicate that the reference may be
2467                      replaced by the equivalence we computed above.  Do this
2468                      even if the register is only used in one block so that
2469                      dependencies can be handled where the last register is
2470                      used in a different block (i.e. HIGH / LO_SUM sequences)
2471                      and to reduce the number of registers alive across
2472                      calls.  */
2473
2474                   if (REG_N_REFS (regno) == 2
2475                       && (rtx_equal_p (x, src)
2476                           || ! equiv_init_varies_p (src))
2477                       && NONJUMP_INSN_P (insn)
2478                       && equiv_init_movable_p (PATTERN (insn), regno))
2479                     reg_equiv[regno].replace = 1;
2480                 }
2481             }
2482         }
2483     }
2484
2485   if (!optimize)
2486     goto out;
2487
2488   /* A second pass, to gather additional equivalences with memory.  This needs
2489      to be done after we know which registers we are going to replace.  */
2490
2491   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2492     {
2493       rtx set, src, dest;
2494       unsigned regno;
2495
2496       if (! INSN_P (insn))
2497         continue;
2498
2499       set = single_set (insn);
2500       if (! set)
2501         continue;
2502
2503       dest = SET_DEST (set);
2504       src = SET_SRC (set);
2505
2506       /* If this sets a MEM to the contents of a REG that is only used
2507          in a single basic block, see if the register is always equivalent
2508          to that memory location and if moving the store from INSN to the
2509          insn that set REG is safe.  If so, put a REG_EQUIV note on the
2510          initializing insn.
2511
2512          Don't add a REG_EQUIV note if the insn already has one.  The existing
2513          REG_EQUIV is likely more useful than the one we are adding.
2514
2515          If one of the regs in the address has reg_equiv[REGNO].replace set,
2516          then we can't add this REG_EQUIV note.  The reg_equiv[REGNO].replace
2517          optimization may move the set of this register immediately before
2518          insn, which puts it after reg_equiv[REGNO].init_insns, and hence
2519          the mention in the REG_EQUIV note would be to an uninitialized
2520          pseudo.  */
2521
2522       if (MEM_P (dest) && REG_P (src)
2523           && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
2524           && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2525           && DF_REG_DEF_COUNT (regno) == 1
2526           && reg_equiv[regno].init_insns != 0
2527           && reg_equiv[regno].init_insns != const0_rtx
2528           && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
2529                               REG_EQUIV, NULL_RTX)
2530           && ! contains_replace_regs (XEXP (dest, 0)))
2531         {
2532           rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
2533           if (validate_equiv_mem (init_insn, src, dest)
2534               && ! memref_used_between_p (dest, init_insn, insn)
2535               /* Attaching a REG_EQUIV note will fail if INIT_INSN has
2536                  multiple sets.  */
2537               && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
2538             {
2539               /* This insn makes the equivalence, not the one initializing
2540                  the register.  */
2541               reg_equiv_init[regno]
2542                 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
2543               df_notes_rescan (init_insn);
2544             }
2545         }
2546     }
2547
2548   cleared_regs = BITMAP_ALLOC (NULL);
2549   /* Now scan all regs killed in an insn to see if any of them are
2550      registers only used that once.  If so, see if we can replace the
2551      reference with the equivalent form.  If we can, delete the
2552      initializing reference and this register will go away.  If we
2553      can't replace the reference, and the initializing reference is
2554      within the same loop (or in an inner loop), then move the register
2555      initialization just before the use, so that they are in the same
2556      basic block.  */
2557   FOR_EACH_BB_REVERSE (bb)
2558     {
2559       loop_depth = bb->loop_depth;
2560       for (insn = BB_END (bb);
2561            insn != PREV_INSN (BB_HEAD (bb));
2562            insn = PREV_INSN (insn))
2563         {
2564           rtx link;
2565
2566           if (! INSN_P (insn))
2567             continue;
2568
2569           /* Don't substitute into a non-local goto, this confuses CFG.  */
2570           if (JUMP_P (insn)
2571               && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
2572             continue;
2573
2574           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2575             {
2576               if (REG_NOTE_KIND (link) == REG_DEAD
2577                   /* Make sure this insn still refers to the register.  */
2578                   && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
2579                 {
2580                   int regno = REGNO (XEXP (link, 0));
2581                   rtx equiv_insn;
2582
2583                   if (! reg_equiv[regno].replace
2584                       || reg_equiv[regno].loop_depth < loop_depth)
2585                     continue;
2586
2587                   /* reg_equiv[REGNO].replace gets set only when
2588                      REG_N_REFS[REGNO] is 2, i.e. the register is set
2589                      once and used once.  (If it were only set, but not used,
2590                      flow would have deleted the setting insns.)  Hence
2591                      there can only be one insn in reg_equiv[REGNO].init_insns.  */
2592                   gcc_assert (reg_equiv[regno].init_insns
2593                               && !XEXP (reg_equiv[regno].init_insns, 1));
2594                   equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
2595
2596                   /* We may not move instructions that can throw, since
2597                      that changes basic block boundaries and we are not
2598                      prepared to adjust the CFG to match.  */
2599                   if (can_throw_internal (equiv_insn))
2600                     continue;
2601
2602                   if (asm_noperands (PATTERN (equiv_insn)) < 0
2603                       && validate_replace_rtx (regno_reg_rtx[regno],
2604                                                *(reg_equiv[regno].src_p), insn))
2605                     {
2606                       rtx equiv_link;
2607                       rtx last_link;
2608                       rtx note;
2609
2610                       /* Find the last note.  */
2611                       for (last_link = link; XEXP (last_link, 1);
2612                            last_link = XEXP (last_link, 1))
2613                         ;
2614
2615                       /* Append the REG_DEAD notes from equiv_insn.  */
2616                       equiv_link = REG_NOTES (equiv_insn);
2617                       while (equiv_link)
2618                         {
2619                           note = equiv_link;
2620                           equiv_link = XEXP (equiv_link, 1);
2621                           if (REG_NOTE_KIND (note) == REG_DEAD)
2622                             {
2623                               remove_note (equiv_insn, note);
2624                               XEXP (last_link, 1) = note;
2625                               XEXP (note, 1) = NULL_RTX;
2626                               last_link = note;
2627                             }
2628                         }
2629
2630                       remove_death (regno, insn);
2631                       SET_REG_N_REFS (regno, 0);
2632                       REG_FREQ (regno) = 0;
2633                       delete_insn (equiv_insn);
2634
2635                       reg_equiv[regno].init_insns
2636                         = XEXP (reg_equiv[regno].init_insns, 1);
2637
2638                       reg_equiv_init[regno] = NULL_RTX;
2639                       bitmap_set_bit (cleared_regs, regno);
2640                     }
2641                   /* Move the initialization of the register to just before
2642                      INSN.  Update the flow information.  */
2643                   else if (prev_nondebug_insn (insn) != equiv_insn)
2644                     {
2645                       rtx new_insn;
2646
2647                       new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
2648                       REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
2649                       REG_NOTES (equiv_insn) = 0;
2650                       /* Rescan it to process the notes.  */
2651                       df_insn_rescan (new_insn);
2652
2653                       /* Make sure this insn is recognized before
2654                          reload begins, otherwise
2655                          eliminate_regs_in_insn will die.  */
2656                       INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
2657
2658                       delete_insn (equiv_insn);
2659
2660                       XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
2661
2662                       REG_BASIC_BLOCK (regno) = bb->index;
2663                       REG_N_CALLS_CROSSED (regno) = 0;
2664                       REG_FREQ_CALLS_CROSSED (regno) = 0;
2665                       REG_N_THROWING_CALLS_CROSSED (regno) = 0;
2666                       REG_LIVE_LENGTH (regno) = 2;
2667
2668                       if (insn == BB_HEAD (bb))
2669                         BB_HEAD (bb) = PREV_INSN (insn);
2670
2671                       reg_equiv_init[regno]
2672                         = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
2673                       bitmap_set_bit (cleared_regs, regno);
2674                     }
2675                 }
2676             }
2677         }
2678     }
2679
2680   if (!bitmap_empty_p (cleared_regs))
2681     {
2682       FOR_EACH_BB (bb)
2683         {
2684           bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
2685           bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
2686           bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
2687           bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
2688         }
2689
2690       /* Last pass - adjust debug insns referencing cleared regs.  */
2691       if (MAY_HAVE_DEBUG_INSNS)
2692         for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2693           if (DEBUG_INSN_P (insn))
2694             {
2695               rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
2696               INSN_VAR_LOCATION_LOC (insn)
2697                 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
2698                                            adjust_cleared_regs,
2699                                            (void *) cleared_regs);
2700               if (old_loc != INSN_VAR_LOCATION_LOC (insn))
2701                 df_insn_rescan (insn);
2702             }
2703     }
2704
2705   BITMAP_FREE (cleared_regs);
2706
2707   out:
2708   /* Clean up.  */
2709
2710   end_alias_analysis ();
2711   free (reg_equiv);
2712   return recorded_label_ref;
2713 }
2714
2715 \f
2716
2717 /* Print chain C to FILE.  */
2718 static void
2719 print_insn_chain (FILE *file, struct insn_chain *c)
2720 {
2721   fprintf (file, "insn=%d, ", INSN_UID(c->insn));
2722   bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
2723   bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
2724 }
2725
2726
2727 /* Print all reload_insn_chains to FILE.  */
2728 static void
2729 print_insn_chains (FILE *file)
2730 {
2731   struct insn_chain *c;
2732   for (c = reload_insn_chain; c ; c = c->next)
2733     print_insn_chain (file, c);
2734 }
2735
2736 /* Return true if pseudo REGNO should be added to set live_throughout
2737    or dead_or_set of the insn chains for reload consideration.  */
2738 static bool
2739 pseudo_for_reload_consideration_p (int regno)
2740 {
2741   /* Consider spilled pseudos too for IRA because they still have a
2742      chance to get hard-registers in the reload when IRA is used.  */
2743   return (reg_renumber[regno] >= 0 || ira_conflicts_p);
2744 }
2745
2746 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
2747    REG to the number of nregs, and INIT_VALUE to get the
2748    initialization.  ALLOCNUM need not be the regno of REG.  */
2749 static void
2750 init_live_subregs (bool init_value, sbitmap *live_subregs,
2751                    int *live_subregs_used, int allocnum, rtx reg)
2752 {
2753   unsigned int regno = REGNO (SUBREG_REG (reg));
2754   int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2755
2756   gcc_assert (size > 0);
2757
2758   /* Been there, done that.  */
2759   if (live_subregs_used[allocnum])
2760     return;
2761
2762   /* Create a new one with zeros.  */
2763   if (live_subregs[allocnum] == NULL)
2764     live_subregs[allocnum] = sbitmap_alloc (size);
2765
2766   /* If the entire reg was live before blasting into subregs, we need
2767      to init all of the subregs to ones else init to 0.  */
2768   if (init_value)
2769     sbitmap_ones (live_subregs[allocnum]);
2770   else
2771     sbitmap_zero (live_subregs[allocnum]);
2772
2773   /* Set the number of bits that we really want.  */
2774   live_subregs_used[allocnum] = size;
2775 }
2776
2777 /* Walk the insns of the current function and build reload_insn_chain,
2778    and record register life information.  */
2779 static void
2780 build_insn_chain (void)
2781 {
2782   unsigned int i;
2783   struct insn_chain **p = &reload_insn_chain;
2784   basic_block bb;
2785   struct insn_chain *c = NULL;
2786   struct insn_chain *next = NULL;
2787   bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
2788   bitmap elim_regset = BITMAP_ALLOC (NULL);
2789   /* live_subregs is a vector used to keep accurate information about
2790      which hardregs are live in multiword pseudos.  live_subregs and
2791      live_subregs_used are indexed by pseudo number.  The live_subreg
2792      entry for a particular pseudo is only used if the corresponding
2793      element is non zero in live_subregs_used.  The value in
2794      live_subregs_used is number of bytes that the pseudo can
2795      occupy.  */
2796   sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
2797   int *live_subregs_used = XNEWVEC (int, max_regno);
2798
2799   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2800     if (TEST_HARD_REG_BIT (eliminable_regset, i))
2801       bitmap_set_bit (elim_regset, i);
2802   FOR_EACH_BB_REVERSE (bb)
2803     {
2804       bitmap_iterator bi;
2805       rtx insn;
2806
2807       CLEAR_REG_SET (live_relevant_regs);
2808       memset (live_subregs_used, 0, max_regno * sizeof (int));
2809
2810       EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb), 0, i, bi)
2811         {
2812           if (i >= FIRST_PSEUDO_REGISTER)
2813             break;
2814           bitmap_set_bit (live_relevant_regs, i);
2815         }
2816
2817       EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb),
2818                                 FIRST_PSEUDO_REGISTER, i, bi)
2819         {
2820           if (pseudo_for_reload_consideration_p (i))
2821             bitmap_set_bit (live_relevant_regs, i);
2822         }
2823
2824       FOR_BB_INSNS_REVERSE (bb, insn)
2825         {
2826           if (!NOTE_P (insn) && !BARRIER_P (insn))
2827             {
2828               unsigned int uid = INSN_UID (insn);
2829               df_ref *def_rec;
2830               df_ref *use_rec;
2831
2832               c = new_insn_chain ();
2833               c->next = next;
2834               next = c;
2835               *p = c;
2836               p = &c->prev;
2837
2838               c->insn = insn;
2839               c->block = bb->index;
2840
2841               if (INSN_P (insn))
2842                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2843                   {
2844                     df_ref def = *def_rec;
2845                     unsigned int regno = DF_REF_REGNO (def);
2846
2847                     /* Ignore may clobbers because these are generated
2848                        from calls. However, every other kind of def is
2849                        added to dead_or_set.  */
2850                     if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2851                       {
2852                         if (regno < FIRST_PSEUDO_REGISTER)
2853                           {
2854                             if (!fixed_regs[regno])
2855                               bitmap_set_bit (&c->dead_or_set, regno);
2856                           }
2857                         else if (pseudo_for_reload_consideration_p (regno))
2858                           bitmap_set_bit (&c->dead_or_set, regno);
2859                       }
2860
2861                     if ((regno < FIRST_PSEUDO_REGISTER
2862                          || reg_renumber[regno] >= 0
2863                          || ira_conflicts_p)
2864                         && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
2865                       {
2866                         rtx reg = DF_REF_REG (def);
2867
2868                         /* We can model subregs, but not if they are
2869                            wrapped in ZERO_EXTRACTS.  */
2870                         if (GET_CODE (reg) == SUBREG
2871                             && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
2872                           {
2873                             unsigned int start = SUBREG_BYTE (reg);
2874                             unsigned int last = start
2875                               + GET_MODE_SIZE (GET_MODE (reg));
2876
2877                             init_live_subregs
2878                               (bitmap_bit_p (live_relevant_regs, regno),
2879                                live_subregs, live_subregs_used, regno, reg);
2880
2881                             if (!DF_REF_FLAGS_IS_SET
2882                                 (def, DF_REF_STRICT_LOW_PART))
2883                               {
2884                                 /* Expand the range to cover entire words.
2885                                    Bytes added here are "don't care".  */
2886                                 start
2887                                   = start / UNITS_PER_WORD * UNITS_PER_WORD;
2888                                 last = ((last + UNITS_PER_WORD - 1)
2889                                         / UNITS_PER_WORD * UNITS_PER_WORD);
2890                               }
2891
2892                             /* Ignore the paradoxical bits.  */
2893                             if ((int)last > live_subregs_used[regno])
2894                               last = live_subregs_used[regno];
2895
2896                             while (start < last)
2897                               {
2898                                 RESET_BIT (live_subregs[regno], start);
2899                                 start++;
2900                               }
2901
2902                             if (sbitmap_empty_p (live_subregs[regno]))
2903                               {
2904                                 live_subregs_used[regno] = 0;
2905                                 bitmap_clear_bit (live_relevant_regs, regno);
2906                               }
2907                             else
2908                               /* Set live_relevant_regs here because
2909                                  that bit has to be true to get us to
2910                                  look at the live_subregs fields.  */
2911                               bitmap_set_bit (live_relevant_regs, regno);
2912                           }
2913                         else
2914                           {
2915                             /* DF_REF_PARTIAL is generated for
2916                                subregs, STRICT_LOW_PART, and
2917                                ZERO_EXTRACT.  We handle the subreg
2918                                case above so here we have to keep from
2919                                modeling the def as a killing def.  */
2920                             if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
2921                               {
2922                                 bitmap_clear_bit (live_relevant_regs, regno);
2923                                 live_subregs_used[regno] = 0;
2924                               }
2925                           }
2926                       }
2927                   }
2928
2929               bitmap_and_compl_into (live_relevant_regs, elim_regset);
2930               bitmap_copy (&c->live_throughout, live_relevant_regs);
2931
2932               if (INSN_P (insn))
2933                 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2934                   {
2935                     df_ref use = *use_rec;
2936                     unsigned int regno = DF_REF_REGNO (use);
2937                     rtx reg = DF_REF_REG (use);
2938
2939                     /* DF_REF_READ_WRITE on a use means that this use
2940                        is fabricated from a def that is a partial set
2941                        to a multiword reg.  Here, we only model the
2942                        subreg case that is not wrapped in ZERO_EXTRACT
2943                        precisely so we do not need to look at the
2944                        fabricated use. */
2945                     if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
2946                         && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
2947                         && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
2948                       continue;
2949
2950                     /* Add the last use of each var to dead_or_set.  */
2951                     if (!bitmap_bit_p (live_relevant_regs, regno))
2952                       {
2953                         if (regno < FIRST_PSEUDO_REGISTER)
2954                           {
2955                             if (!fixed_regs[regno])
2956                               bitmap_set_bit (&c->dead_or_set, regno);
2957                           }
2958                         else if (pseudo_for_reload_consideration_p (regno))
2959                           bitmap_set_bit (&c->dead_or_set, regno);
2960                       }
2961
2962                     if (regno < FIRST_PSEUDO_REGISTER
2963                         || pseudo_for_reload_consideration_p (regno))
2964                       {
2965                         if (GET_CODE (reg) == SUBREG
2966                             && !DF_REF_FLAGS_IS_SET (use,
2967                                                      DF_REF_SIGN_EXTRACT
2968                                                      | DF_REF_ZERO_EXTRACT))
2969                           {
2970                             unsigned int start = SUBREG_BYTE (reg);
2971                             unsigned int last = start
2972                               + GET_MODE_SIZE (GET_MODE (reg));
2973
2974                             init_live_subregs
2975                               (bitmap_bit_p (live_relevant_regs, regno),
2976                                live_subregs, live_subregs_used, regno, reg);
2977
2978                             /* Ignore the paradoxical bits.  */
2979                             if ((int)last > live_subregs_used[regno])
2980                               last = live_subregs_used[regno];
2981
2982                             while (start < last)
2983                               {
2984                                 SET_BIT (live_subregs[regno], start);
2985                                 start++;
2986                               }
2987                           }
2988                         else
2989                           /* Resetting the live_subregs_used is
2990                              effectively saying do not use the subregs
2991                              because we are reading the whole
2992                              pseudo.  */
2993                           live_subregs_used[regno] = 0;
2994                         bitmap_set_bit (live_relevant_regs, regno);
2995                       }
2996                   }
2997             }
2998         }
2999
3000       /* FIXME!! The following code is a disaster.  Reload needs to see the
3001          labels and jump tables that are just hanging out in between
3002          the basic blocks.  See pr33676.  */
3003       insn = BB_HEAD (bb);
3004
3005       /* Skip over the barriers and cruft.  */
3006       while (insn && (BARRIER_P (insn) || NOTE_P (insn)
3007                       || BLOCK_FOR_INSN (insn) == bb))
3008         insn = PREV_INSN (insn);
3009
3010       /* While we add anything except barriers and notes, the focus is
3011          to get the labels and jump tables into the
3012          reload_insn_chain.  */
3013       while (insn)
3014         {
3015           if (!NOTE_P (insn) && !BARRIER_P (insn))
3016             {
3017               if (BLOCK_FOR_INSN (insn))
3018                 break;
3019
3020               c = new_insn_chain ();
3021               c->next = next;
3022               next = c;
3023               *p = c;
3024               p = &c->prev;
3025
3026               /* The block makes no sense here, but it is what the old
3027                  code did.  */
3028               c->block = bb->index;
3029               c->insn = insn;
3030               bitmap_copy (&c->live_throughout, live_relevant_regs);
3031             }
3032           insn = PREV_INSN (insn);
3033         }
3034     }
3035
3036   for (i = 0; i < (unsigned int) max_regno; i++)
3037     if (live_subregs[i])
3038       free (live_subregs[i]);
3039
3040   reload_insn_chain = c;
3041   *p = NULL;
3042
3043   free (live_subregs);
3044   free (live_subregs_used);
3045   BITMAP_FREE (live_relevant_regs);
3046   BITMAP_FREE (elim_regset);
3047
3048   if (dump_file)
3049     print_insn_chains (dump_file);
3050 }
3051 \f
3052 /* Allocate memory for reg_equiv_memory_loc.  */
3053 static void
3054 init_reg_equiv_memory_loc (void)
3055 {
3056   max_regno = max_reg_num ();
3057
3058   /* And the reg_equiv_memory_loc array.  */
3059   VEC_safe_grow (rtx, gc, reg_equiv_memory_loc_vec, max_regno);
3060   memset (VEC_address (rtx, reg_equiv_memory_loc_vec), 0,
3061           sizeof (rtx) * max_regno);
3062   reg_equiv_memory_loc = VEC_address (rtx, reg_equiv_memory_loc_vec);
3063 }
3064
3065 /* All natural loops.  */
3066 struct loops ira_loops;
3067
3068 /* True if we have allocno conflicts.  It is false for non-optimized
3069    mode or when the conflict table is too big.  */
3070 bool ira_conflicts_p;
3071
3072 /* This is the main entry of IRA.  */
3073 static void
3074 ira (FILE *f)
3075 {
3076   int overall_cost_before, allocated_reg_info_size;
3077   bool loops_p;
3078   int max_regno_before_ira, ira_max_point_before_emit;
3079   int rebuild_p;
3080   int saved_flag_ira_share_spill_slots;
3081   basic_block bb;
3082
3083   timevar_push (TV_IRA);
3084
3085   if (flag_caller_saves)
3086     init_caller_save ();
3087
3088   if (flag_ira_verbose < 10)
3089     {
3090       internal_flag_ira_verbose = flag_ira_verbose;
3091       ira_dump_file = f;
3092     }
3093   else
3094     {
3095       internal_flag_ira_verbose = flag_ira_verbose - 10;
3096       ira_dump_file = stderr;
3097     }
3098
3099   ira_conflicts_p = optimize > 0;
3100   setup_prohibited_mode_move_regs ();
3101
3102   df_note_add_problem ();
3103
3104   if (optimize == 1)
3105     {
3106       df_live_add_problem ();
3107       df_live_set_all_dirty ();
3108     }
3109 #ifdef ENABLE_CHECKING
3110   df->changeable_flags |= DF_VERIFY_SCHEDULED;
3111 #endif
3112   df_analyze ();
3113   df_clear_flags (DF_NO_INSN_RESCAN);
3114   regstat_init_n_sets_and_refs ();
3115   regstat_compute_ri ();
3116
3117   /* If we are not optimizing, then this is the only place before
3118      register allocation where dataflow is done.  And that is needed
3119      to generate these warnings.  */
3120   if (warn_clobbered)
3121     generate_setjmp_warnings ();
3122
3123   /* Determine if the current function is a leaf before running IRA
3124      since this can impact optimizations done by the prologue and
3125      epilogue thus changing register elimination offsets.  */
3126   current_function_is_leaf = leaf_function_p ();
3127
3128   if (resize_reg_info () && flag_ira_loop_pressure)
3129     ira_set_pseudo_classes (ira_dump_file);
3130
3131   rebuild_p = update_equiv_regs ();
3132
3133 #ifndef IRA_NO_OBSTACK
3134   gcc_obstack_init (&ira_obstack);
3135 #endif
3136   bitmap_obstack_initialize (&ira_bitmap_obstack);
3137   if (optimize)
3138     {
3139       max_regno = max_reg_num ();
3140       ira_reg_equiv_len = max_regno;
3141       ira_reg_equiv_invariant_p
3142         = (bool *) ira_allocate (max_regno * sizeof (bool));
3143       memset (ira_reg_equiv_invariant_p, 0, max_regno * sizeof (bool));
3144       ira_reg_equiv_const = (rtx *) ira_allocate (max_regno * sizeof (rtx));
3145       memset (ira_reg_equiv_const, 0, max_regno * sizeof (rtx));
3146       find_reg_equiv_invariant_const ();
3147       if (rebuild_p)
3148         {
3149           timevar_push (TV_JUMP);
3150           rebuild_jump_labels (get_insns ());
3151           purge_all_dead_edges ();
3152           timevar_pop (TV_JUMP);
3153         }
3154     }
3155
3156   max_regno_before_ira = allocated_reg_info_size = max_reg_num ();
3157   ira_setup_eliminable_regset ();
3158
3159   ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
3160   ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
3161   ira_move_loops_num = ira_additional_jumps_num = 0;
3162
3163   ira_assert (current_loops == NULL);
3164   flow_loops_find (&ira_loops);
3165   record_loop_exits ();
3166   current_loops = &ira_loops;
3167
3168   init_reg_equiv_memory_loc ();
3169
3170   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3171     fprintf (ira_dump_file, "Building IRA IR\n");
3172   loops_p = ira_build (optimize
3173                        && (flag_ira_region == IRA_REGION_ALL
3174                            || flag_ira_region == IRA_REGION_MIXED));
3175
3176   ira_assert (ira_conflicts_p || !loops_p);
3177
3178   saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
3179   if (too_high_register_pressure_p () || cfun->calls_setjmp)
3180     /* It is just wasting compiler's time to pack spilled pseudos into
3181        stack slots in this case -- prohibit it.  We also do this if
3182        there is setjmp call because a variable not modified between
3183        setjmp and longjmp the compiler is required to preserve its
3184        value and sharing slots does not guarantee it.  */
3185     flag_ira_share_spill_slots = FALSE;
3186
3187   ira_color ();
3188
3189   ira_max_point_before_emit = ira_max_point;
3190
3191   ira_emit (loops_p);
3192
3193   if (ira_conflicts_p)
3194     {
3195       max_regno = max_reg_num ();
3196
3197       if (! loops_p)
3198         ira_initiate_assign ();
3199       else
3200         {
3201           expand_reg_info (allocated_reg_info_size);
3202           setup_preferred_alternate_classes_for_new_pseudos
3203             (allocated_reg_info_size);
3204           allocated_reg_info_size = max_regno;
3205
3206           if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3207             fprintf (ira_dump_file, "Flattening IR\n");
3208           ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
3209           /* New insns were generated: add notes and recalculate live
3210              info.  */
3211           df_analyze ();
3212
3213           flow_loops_find (&ira_loops);
3214           record_loop_exits ();
3215           current_loops = &ira_loops;
3216
3217           setup_allocno_assignment_flags ();
3218           ira_initiate_assign ();
3219           ira_reassign_conflict_allocnos (max_regno);
3220         }
3221     }
3222
3223   setup_reg_renumber ();
3224
3225   calculate_allocation_cost ();
3226
3227 #ifdef ENABLE_IRA_CHECKING
3228   if (ira_conflicts_p)
3229     check_allocation ();
3230 #endif
3231
3232   delete_trivially_dead_insns (get_insns (), max_reg_num ());
3233
3234   init_reg_equiv_memory_loc ();
3235
3236   if (max_regno != max_regno_before_ira)
3237     {
3238       regstat_free_n_sets_and_refs ();
3239       regstat_free_ri ();
3240       regstat_init_n_sets_and_refs ();
3241       regstat_compute_ri ();
3242     }
3243
3244   allocate_initial_values (reg_equiv_memory_loc);
3245
3246   overall_cost_before = ira_overall_cost;
3247   if (ira_conflicts_p)
3248     {
3249       fix_reg_equiv_init ();
3250
3251 #ifdef ENABLE_IRA_CHECKING
3252       print_redundant_copies ();
3253 #endif
3254
3255       ira_spilled_reg_stack_slots_num = 0;
3256       ira_spilled_reg_stack_slots
3257         = ((struct ira_spilled_reg_stack_slot *)
3258            ira_allocate (max_regno
3259                          * sizeof (struct ira_spilled_reg_stack_slot)));
3260       memset (ira_spilled_reg_stack_slots, 0,
3261               max_regno * sizeof (struct ira_spilled_reg_stack_slot));
3262     }
3263
3264   timevar_pop (TV_IRA);
3265
3266   timevar_push (TV_RELOAD);
3267   df_set_flags (DF_NO_INSN_RESCAN);
3268   build_insn_chain ();
3269
3270   reload_completed = !reload (get_insns (), ira_conflicts_p);
3271
3272   finish_subregs_of_mode ();
3273
3274   timevar_pop (TV_RELOAD);
3275
3276   timevar_push (TV_IRA);
3277
3278   if (ira_conflicts_p)
3279     {
3280       ira_free (ira_spilled_reg_stack_slots);
3281
3282       ira_finish_assign ();
3283
3284     }
3285   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
3286       && overall_cost_before != ira_overall_cost)
3287     fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
3288   ira_destroy ();
3289
3290   flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
3291
3292   flow_loops_free (&ira_loops);
3293   free_dominance_info (CDI_DOMINATORS);
3294   FOR_ALL_BB (bb)
3295     bb->loop_father = NULL;
3296   current_loops = NULL;
3297
3298   regstat_free_ri ();
3299   regstat_free_n_sets_and_refs ();
3300
3301   if (optimize)
3302     {
3303       cleanup_cfg (CLEANUP_EXPENSIVE);
3304
3305       ira_free (ira_reg_equiv_invariant_p);
3306       ira_free (ira_reg_equiv_const);
3307     }
3308
3309   bitmap_obstack_release (&ira_bitmap_obstack);
3310 #ifndef IRA_NO_OBSTACK
3311   obstack_free (&ira_obstack, NULL);
3312 #endif
3313
3314   /* The code after the reload has changed so much that at this point
3315      we might as well just rescan everything.  Not that
3316      df_rescan_all_insns is not going to help here because it does not
3317      touch the artificial uses and defs.  */
3318   df_finish_pass (true);
3319   if (optimize > 1)
3320     df_live_add_problem ();
3321   df_scan_alloc (NULL);
3322   df_scan_blocks ();
3323
3324   if (optimize)
3325     df_analyze ();
3326
3327   timevar_pop (TV_IRA);
3328 }
3329
3330 \f
3331
3332 static bool
3333 gate_ira (void)
3334 {
3335   return true;
3336 }
3337
3338 /* Run the integrated register allocator.  */
3339 static unsigned int
3340 rest_of_handle_ira (void)
3341 {
3342   ira (dump_file);
3343   return 0;
3344 }
3345
3346 struct rtl_opt_pass pass_ira =
3347 {
3348  {
3349   RTL_PASS,
3350   "ira",                                /* name */
3351   gate_ira,                             /* gate */
3352   rest_of_handle_ira,                   /* execute */
3353   NULL,                                 /* sub */
3354   NULL,                                 /* next */
3355   0,                                    /* static_pass_number */
3356   TV_NONE,                              /* tv_id */
3357   0,                                    /* properties_required */
3358   0,                                    /* properties_provided */
3359   0,                                    /* properties_destroyed */
3360   0,                                    /* todo_flags_start */
3361   TODO_dump_func |
3362   TODO_ggc_collect                      /* todo_flags_finish */
3363  }
3364 };