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