--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/ira.c	Fri Jul 17 14:47:48 2009 +0900
@@ -0,0 +1,3331 @@
+/* Integrated Register Allocator (IRA) entry point.
+   Copyright (C) 2006, 2007, 2008, 2009
+   Free Software Foundation, Inc.
+   Contributed by Vladimir Makarov <vmakarov@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* The integrated register allocator (IRA) is a
+   regional register allocator performing graph coloring on a top-down
+   traversal of nested regions.  Graph coloring in a region is based
+   on Chaitin-Briggs algorithm.  It is called integrated because
+   register coalescing, register live range splitting, and choosing a
+   better hard register are done on-the-fly during coloring.  Register
+   coalescing and choosing a cheaper hard register is done by hard
+   register preferencing during hard register assigning.  The live
+   range splitting is a byproduct of the regional register allocation.
+
+   Major IRA notions are:
+
+     o *Region* is a part of CFG where graph coloring based on
+       Chaitin-Briggs algorithm is done.  IRA can work on any set of
+       nested CFG regions forming a tree.  Currently the regions are
+       the entire function for the root region and natural loops for
+       the other regions.  Therefore data structure representing a
+       region is called loop_tree_node.
+
+     o *Cover class* is a register class belonging to a set of
+       non-intersecting register classes containing all of the
+       hard-registers available for register allocation.  The set of
+       all cover classes for a target is defined in the corresponding
+       machine-description file according some criteria.  Such notion
+       is needed because Chaitin-Briggs algorithm works on
+       non-intersected register classes.
+
+     o *Allocno* represents the live range of a pseudo-register in a
+       region.  Besides the obvious attributes like the corresponding
+       pseudo-register number, cover class, conflicting allocnos and
+       conflicting hard-registers, there are a few allocno attributes
+       which are important for understanding the allocation algorithm:
+
+       - *Live ranges*.  This is a list of ranges of *program
+         points* where the allocno lives.  Program points represent
+         places where a pseudo can be born or become dead (there are
+         approximately two times more program points than the insns)
+         and they are represented by integers starting with 0.  The
+         live ranges are used to find conflicts between allocnos of
+         different cover classes.  They also play very important role
+         for the transformation of the IRA internal representation of
+         several regions into a one region representation.  The later is
+         used during the reload pass work because each allocno
+         represents all of the corresponding pseudo-registers.
+
+       - *Hard-register costs*.  This is a vector of size equal to the
+         number of available hard-registers of the allocno's cover
+         class.  The cost of a callee-clobbered hard-register for an
+         allocno is increased by the cost of save/restore code around
+         the calls through the given allocno's life.  If the allocno
+         is a move instruction operand and another operand is a
+         hard-register of the allocno's cover class, the cost of the
+         hard-register is decreased by the move cost.
+
+         When an allocno is assigned, the hard-register with minimal
+         full cost is used.  Initially, a hard-register's full cost is
+         the corresponding value from the hard-register's cost vector.
+         If the allocno is connected by a *copy* (see below) to
+         another allocno which has just received a hard-register, the
+         cost of the hard-register is decreased.  Before choosing a
+         hard-register for an allocno, the allocno's current costs of
+         the hard-registers are modified by the conflict hard-register
+         costs of all of the conflicting allocnos which are not
+         assigned yet.
+
+       - *Conflict hard-register costs*.  This is a vector of the same
+         size as the hard-register costs vector.  To permit an
+         unassigned allocno to get a better hard-register, IRA uses
+         this vector to calculate the final full cost of the
+         available hard-registers.  Conflict hard-register costs of an
+         unassigned allocno are also changed with a change of the
+         hard-register cost of the allocno when a copy involving the
+         allocno is processed as described above.  This is done to
+         show other unassigned allocnos that a given allocno prefers
+         some hard-registers in order to remove the move instruction
+         corresponding to the copy.
+
+     o *Cap*.  If a pseudo-register does not live in a region but
+       lives in a nested region, IRA creates a special allocno called
+       a cap in the outer region.  A region cap is also created for a
+       subregion cap.
+
+     o *Copy*.  Allocnos can be connected by copies.  Copies are used
+       to modify hard-register costs for allocnos during coloring.
+       Such modifications reflects a preference to use the same
+       hard-register for the allocnos connected by copies.  Usually
+       copies are created for move insns (in this case it results in
+       register coalescing).  But IRA also creates copies for operands
+       of an insn which should be assigned to the same hard-register
+       due to constraints in the machine description (it usually
+       results in removing a move generated in reload to satisfy
+       the constraints) and copies referring to the allocno which is
+       the output operand of an instruction and the allocno which is
+       an input operand dying in the instruction (creation of such
+       copies results in less register shuffling).  IRA *does not*
+       create copies between the same register allocnos from different
+       regions because we use another technique for propagating
+       hard-register preference on the borders of regions.
+
+   Allocnos (including caps) for the upper region in the region tree
+   *accumulate* information important for coloring from allocnos with
+   the same pseudo-register from nested regions.  This includes
+   hard-register and memory costs, conflicts with hard-registers,
+   allocno conflicts, allocno copies and more.  *Thus, attributes for
+   allocnos in a region have the same values as if the region had no
+   subregions*.  It means that attributes for allocnos in the
+   outermost region corresponding to the function have the same values
+   as though the allocation used only one region which is the entire
+   function.  It also means that we can look at IRA work as if the
+   first IRA did allocation for all function then it improved the
+   allocation for loops then their subloops and so on.
+
+   IRA major passes are:
+
+     o Building IRA internal representation which consists of the
+       following subpasses:
+
+       * First, IRA builds regions and creates allocnos (file
+         ira-build.c) and initializes most of their attributes.
+
+       * Then IRA finds a cover class for each allocno and calculates
+         its initial (non-accumulated) cost of memory and each
+         hard-register of its cover class (file ira-cost.c).
+
+       * IRA creates live ranges of each allocno, calulates register
+         pressure for each cover class in each region, sets up
+         conflict hard registers for each allocno and info about calls
+         the allocno lives through (file ira-lives.c).
+
+       * IRA removes low register pressure loops from the regions
+         mostly to speed IRA up (file ira-build.c).
+
+       * IRA propagates accumulated allocno info from lower region
+         allocnos to corresponding upper region allocnos (file
+         ira-build.c).
+
+       * IRA creates all caps (file ira-build.c).
+
+       * Having live-ranges of allocnos and their cover classes, IRA
+         creates conflicting allocnos of the same cover class for each
+         allocno.  Conflicting allocnos are stored as a bit vector or
+         array of pointers to the conflicting allocnos whatever is
+         more profitable (file ira-conflicts.c).  At this point IRA
+         creates allocno copies.
+
+     o Coloring.  Now IRA has all necessary info to start graph coloring
+       process.  It is done in each region on top-down traverse of the
+       region tree (file ira-color.c).  There are following subpasses:
+        
+       * Optional aggressive coalescing of allocnos in the region.
+
+       * Putting allocnos onto the coloring stack.  IRA uses Briggs
+         optimistic coloring which is a major improvement over
+         Chaitin's coloring.  Therefore IRA does not spill allocnos at
+         this point.  There is some freedom in the order of putting
+         allocnos on the stack which can affect the final result of
+         the allocation.  IRA uses some heuristics to improve the order.
+
+       * Popping the allocnos from the stack and assigning them hard
+         registers.  If IRA can not assign a hard register to an
+         allocno and the allocno is coalesced, IRA undoes the
+         coalescing and puts the uncoalesced allocnos onto the stack in
+         the hope that some such allocnos will get a hard register
+         separately.  If IRA fails to assign hard register or memory
+         is more profitable for it, IRA spills the allocno.  IRA
+         assigns the allocno the hard-register with minimal full
+         allocation cost which reflects the cost of usage of the
+         hard-register for the allocno and cost of usage of the
+         hard-register for allocnos conflicting with given allocno.
+
+       * After allono assigning in the region, IRA modifies the hard
+         register and memory costs for the corresponding allocnos in
+         the subregions to reflect the cost of possible loads, stores,
+         or moves on the border of the region and its subregions.
+         When default regional allocation algorithm is used
+         (-fira-algorithm=mixed), IRA just propagates the assignment
+         for allocnos if the register pressure in the region for the
+         corresponding cover class is less than number of available
+         hard registers for given cover class.
+
+     o Spill/restore code moving.  When IRA performs an allocation
+       by traversing regions in top-down order, it does not know what
+       happens below in the region tree.  Therefore, sometimes IRA
+       misses opportunities to perform a better allocation.  A simple
+       optimization tries to improve allocation in a region having
+       subregions and containing in another region.  If the
+       corresponding allocnos in the subregion are spilled, it spills
+       the region allocno if it is profitable.  The optimization
+       implements a simple iterative algorithm performing profitable
+       transformations while they are still possible.  It is fast in
+       practice, so there is no real need for a better time complexity
+       algorithm.
+
+     o Code change.  After coloring, two allocnos representing the same
+       pseudo-register outside and inside a region respectively may be
+       assigned to different locations (hard-registers or memory).  In
+       this case IRA creates and uses a new pseudo-register inside the
+       region and adds code to move allocno values on the region's
+       borders.  This is done during top-down traversal of the regions
+       (file ira-emit.c).  In some complicated cases IRA can create a
+       new allocno to move allocno values (e.g. when a swap of values
+       stored in two hard-registers is needed).  At this stage, the
+       new allocno is marked as spilled.  IRA still creates the
+       pseudo-register and the moves on the region borders even when
+       both allocnos were assigned to the same hard-register.  If the
+       reload pass spills a pseudo-register for some reason, the
+       effect will be smaller because another allocno will still be in
+       the hard-register.  In most cases, this is better then spilling
+       both allocnos.  If reload does not change the allocation
+       for the two pseudo-registers, the trivial move will be removed
+       by post-reload optimizations.  IRA does not generate moves for
+       allocnos assigned to the same hard register when the default
+       regional allocation algorithm is used and the register pressure
+       in the region for the corresponding allocno cover class is less
+       than number of available hard registers for given cover class.
+       IRA also does some optimizations to remove redundant stores and
+       to reduce code duplication on the region borders.
+
+     o Flattening internal representation.  After changing code, IRA
+       transforms its internal representation for several regions into
+       one region representation (file ira-build.c).  This process is
+       called IR flattening.  Such process is more complicated than IR
+       rebuilding would be, but is much faster.
+
+     o After IR flattening, IRA tries to assign hard registers to all
+       spilled allocnos.  This is impelemented by a simple and fast
+       priority coloring algorithm (see function
+       ira_reassign_conflict_allocnos::ira-color.c).  Here new allocnos
+       created during the code change pass can be assigned to hard
+       registers.
+
+     o At the end IRA calls the reload pass.  The reload pass
+       communicates with IRA through several functions in file
+       ira-color.c to improve its decisions in
+
+       * sharing stack slots for the spilled pseudos based on IRA info
+         about pseudo-register conflicts.
+
+       * reassigning hard-registers to all spilled pseudos at the end
+         of each reload iteration.
+
+       * choosing a better hard-register to spill based on IRA info
+         about pseudo-register live ranges and the register pressure
+         in places where the pseudo-register lives.
+
+   IRA uses a lot of data representing the target processors.  These
+   data are initilized in file ira.c.
+
+   If function has no loops (or the loops are ignored when
+   -fira-algorithm=CB is used), we have classic Chaitin-Briggs
+   coloring (only instead of separate pass of coalescing, we use hard
+   register preferencing).  In such case, IRA works much faster
+   because many things are not made (like IR flattening, the
+   spill/restore optimization, and the code change).
+
+   Literature is worth to read for better understanding the code:
+
+   o Preston Briggs, Keith D. Cooper, Linda Torczon.  Improvements to
+     Graph Coloring Register Allocation.
+
+   o David Callahan, Brian Koblenz.  Register allocation via
+     hierarchical graph coloring.
+
+   o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
+     Coloring Register Allocation: A Study of the Chaitin-Briggs and
+     Callahan-Koblenz Algorithms.
+
+   o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
+     Register Allocation Based on Graph Fusion.
+
+   o Vladimir Makarov. The Integrated Register Allocator for GCC.
+
+   o Vladimir Makarov.  The top-down register allocator for irregular
+     register file architectures.
+
+*/
+
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "regs.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "target.h"
+#include "flags.h"
+#include "obstack.h"
+#include "bitmap.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "expr.h"
+#include "recog.h"
+#include "params.h"
+#include "timevar.h"
+#include "tree-pass.h"
+#include "output.h"
+#include "except.h"
+#include "reload.h"
+#include "errors.h"
+#include "integrate.h"
+#include "df.h"
+#include "ggc.h"
+#include "ira-int.h"
+
+
+/* A modified value of flag `-fira-verbose' used internally.  */
+int internal_flag_ira_verbose;
+
+/* Dump file of the allocator if it is not NULL.  */
+FILE *ira_dump_file;
+
+/* Pools for allocnos, copies, allocno live ranges.  */
+alloc_pool allocno_pool, copy_pool, allocno_live_range_pool;
+
+/* The number of elements in the following array.  */
+int ira_spilled_reg_stack_slots_num;
+
+/* The following array contains info about spilled pseudo-registers
+   stack slots used in current function so far.  */
+struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
+
+/* Correspondingly overall cost of the allocation, cost of the
+   allocnos assigned to hard-registers, cost of the allocnos assigned
+   to memory, cost of loads, stores and register move insns generated
+   for pseudo-register live range splitting (see ira-emit.c).  */
+int ira_overall_cost;
+int ira_reg_cost, ira_mem_cost;
+int ira_load_cost, ira_store_cost, ira_shuffle_cost;
+int ira_move_loops_num, ira_additional_jumps_num;
+
+/* All registers that can be eliminated.  */
+
+HARD_REG_SET eliminable_regset;
+
+/* Map: hard regs X modes -> set of hard registers for storing value
+   of given mode starting with given hard register.  */
+HARD_REG_SET ira_reg_mode_hard_regset[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
+
+/* The following two variables are array analogs of the macros
+   MEMORY_MOVE_COST and REGISTER_MOVE_COST.  */
+short int ira_memory_move_cost[MAX_MACHINE_MODE][N_REG_CLASSES][2];
+move_table *ira_register_move_cost[MAX_MACHINE_MODE];
+
+/* Similar to may_move_in_cost but it is calculated in IRA instead of
+   regclass.  Another difference is that we take only available hard
+   registers into account to figure out that one register class is a
+   subset of the another one.  */
+move_table *ira_may_move_in_cost[MAX_MACHINE_MODE];
+
+/* Similar to may_move_out_cost but it is calculated in IRA instead of
+   regclass.  Another difference is that we take only available hard
+   registers into account to figure out that one register class is a
+   subset of the another one.  */
+move_table *ira_may_move_out_cost[MAX_MACHINE_MODE];
+
+/* Register class subset relation: TRUE if the first class is a subset
+   of the second one considering only hard registers available for the
+   allocation.  */
+int ira_class_subset_p[N_REG_CLASSES][N_REG_CLASSES];
+
+/* Temporary hard reg set used for a different calculation.  */
+static HARD_REG_SET temp_hard_regset;
+
+
+
+/* The function sets up the map IRA_REG_MODE_HARD_REGSET.  */
+static void
+setup_reg_mode_hard_regset (void)
+{
+  int i, m, hard_regno;
+
+  for (m = 0; m < NUM_MACHINE_MODES; m++)
+    for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
+      {
+	CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
+	for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
+	  if (hard_regno + i < FIRST_PSEUDO_REGISTER)
+	    SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
+			      hard_regno + i);
+      }
+}
+
+
+
+/* Hard registers that can not be used for the register allocator for
+   all functions of the current compilation unit.  */
+static HARD_REG_SET no_unit_alloc_regs;
+
+/* Array of the number of hard registers of given class which are
+   available for allocation.  The order is defined by the
+   allocation order.  */
+short ira_class_hard_regs[N_REG_CLASSES][FIRST_PSEUDO_REGISTER];
+
+/* The number of elements of the above array for given register
+   class.  */
+int ira_class_hard_regs_num[N_REG_CLASSES];
+
+/* Index (in ira_class_hard_regs) for given register class and hard
+   register (in general case a hard register can belong to several
+   register classes).  The index is negative for hard registers
+   unavailable for the allocation. */
+short ira_class_hard_reg_index[N_REG_CLASSES][FIRST_PSEUDO_REGISTER];
+
+/* The function sets up the three arrays declared above.  */
+static void
+setup_class_hard_regs (void)
+{
+  int cl, i, hard_regno, n;
+  HARD_REG_SET processed_hard_reg_set;
+
+  ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
+  /* We could call ORDER_REGS_FOR_LOCAL_ALLOC here (it is usually
+     putting hard callee-used hard registers first).  But our
+     heuristics work better.  */
+  for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
+    {
+      COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
+      AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+      CLEAR_HARD_REG_SET (processed_hard_reg_set);
+      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+	ira_class_hard_reg_index[cl][0] = -1;
+      for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+	{
+#ifdef REG_ALLOC_ORDER
+	  hard_regno = reg_alloc_order[i];
+#else
+	  hard_regno = i;
+#endif	  
+	  if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
+	    continue;
+	  SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
+      	  if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
+	    ira_class_hard_reg_index[cl][hard_regno] = -1;
+	  else
+	    {
+	      ira_class_hard_reg_index[cl][hard_regno] = n;
+	      ira_class_hard_regs[cl][n++] = hard_regno;
+	    }
+	}
+      ira_class_hard_regs_num[cl] = n;
+    }
+}
+
+/* Number of given class hard registers available for the register
+   allocation for given classes.  */
+int ira_available_class_regs[N_REG_CLASSES];
+
+/* Set up IRA_AVAILABLE_CLASS_REGS.  */
+static void
+setup_available_class_regs (void)
+{
+  int i, j;
+
+  memset (ira_available_class_regs, 0, sizeof (ira_available_class_regs));
+  for (i = 0; i < N_REG_CLASSES; i++)
+    {
+      COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
+      AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+      for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
+	if (TEST_HARD_REG_BIT (temp_hard_regset, j))
+	  ira_available_class_regs[i]++;
+    }
+}
+
+/* Set up global variables defining info about hard registers for the
+   allocation.  These depend on USE_HARD_FRAME_P whose TRUE value means
+   that we can use the hard frame pointer for the allocation.  */
+static void
+setup_alloc_regs (bool use_hard_frame_p)
+{
+  COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
+  if (! use_hard_frame_p)
+    SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
+  setup_class_hard_regs ();
+  setup_available_class_regs ();
+}
+
+
+
+/* Set up IRA_MEMORY_MOVE_COST, IRA_REGISTER_MOVE_COST.  */
+static void
+setup_class_subset_and_memory_move_costs (void)
+{
+  int cl, cl2;
+  enum machine_mode mode;
+  HARD_REG_SET temp_hard_regset2;
+
+  for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
+    ira_memory_move_cost[mode][NO_REGS][0]
+      = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
+  for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
+    {
+      if (cl != (int) NO_REGS)
+	for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
+	  {
+	    ira_memory_move_cost[mode][cl][0] = MEMORY_MOVE_COST (mode, cl, 0);
+	    ira_memory_move_cost[mode][cl][1] = MEMORY_MOVE_COST (mode, cl, 1);
+	    /* Costs for NO_REGS are used in cost calculation on the
+	       1st pass when the preferred register classes are not
+	       known yet.  In this case we take the best scenario.  */
+	    if (ira_memory_move_cost[mode][NO_REGS][0]
+		> ira_memory_move_cost[mode][cl][0])
+	      ira_memory_move_cost[mode][NO_REGS][0]
+		= ira_memory_move_cost[mode][cl][0];
+	    if (ira_memory_move_cost[mode][NO_REGS][1]
+		> ira_memory_move_cost[mode][cl][1])
+	      ira_memory_move_cost[mode][NO_REGS][1]
+		= ira_memory_move_cost[mode][cl][1];
+	  }
+      for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
+	{
+	  COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
+	  AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+	  COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
+	  AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
+	  ira_class_subset_p[cl][cl2]
+	    = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
+	}
+    }
+}
+
+
+
+/* Define the following macro if allocation through malloc if
+   preferable.  */
+#define IRA_NO_OBSTACK
+
+#ifndef IRA_NO_OBSTACK
+/* Obstack used for storing all dynamic data (except bitmaps) of the
+   IRA.  */
+static struct obstack ira_obstack;
+#endif
+
+/* Obstack used for storing all bitmaps of the IRA.  */
+static struct bitmap_obstack ira_bitmap_obstack;
+
+/* Allocate memory of size LEN for IRA data.  */
+void *
+ira_allocate (size_t len)
+{
+  void *res;
+
+#ifndef IRA_NO_OBSTACK
+  res = obstack_alloc (&ira_obstack, len);
+#else
+  res = xmalloc (len);
+#endif
+  return res;
+}
+
+/* Reallocate memory PTR of size LEN for IRA data.  */
+void *
+ira_reallocate (void *ptr, size_t len)
+{
+  void *res;
+
+#ifndef IRA_NO_OBSTACK
+  res = obstack_alloc (&ira_obstack, len);
+#else
+  res = xrealloc (ptr, len);
+#endif
+  return res;
+}
+
+/* Free memory ADDR allocated for IRA data.  */
+void
+ira_free (void *addr ATTRIBUTE_UNUSED)
+{
+#ifndef IRA_NO_OBSTACK
+  /* do nothing */
+#else
+  free (addr);
+#endif
+}
+
+
+/* Allocate and returns bitmap for IRA.  */
+bitmap
+ira_allocate_bitmap (void)
+{
+  return BITMAP_ALLOC (&ira_bitmap_obstack);
+}
+
+/* Free bitmap B allocated for IRA.  */
+void
+ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
+{
+  /* do nothing */
+}
+
+
+
+/* Output information about allocation of all allocnos (except for
+   caps) into file F.  */
+void
+ira_print_disposition (FILE *f)
+{
+  int i, n, max_regno;
+  ira_allocno_t a;
+  basic_block bb;
+
+  fprintf (f, "Disposition:");
+  max_regno = max_reg_num ();
+  for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
+    for (a = ira_regno_allocno_map[i];
+	 a != NULL;
+	 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
+      {
+	if (n % 4 == 0)
+	  fprintf (f, "\n");
+	n++;
+	fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
+	if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
+	  fprintf (f, "b%-3d", bb->index);
+	else
+	  fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
+	if (ALLOCNO_HARD_REGNO (a) >= 0)
+	  fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
+	else
+	  fprintf (f, " mem");
+      }
+  fprintf (f, "\n");
+}
+
+/* Outputs information about allocation of all allocnos into
+   stderr.  */
+void
+ira_debug_disposition (void)
+{
+  ira_print_disposition (stderr);
+}
+
+
+
+/* For each reg class, table listing all the classes contained in it
+   (excluding the class itself.  Non-allocatable registers are
+   excluded from the consideration).  */
+static enum reg_class alloc_reg_class_subclasses[N_REG_CLASSES][N_REG_CLASSES];
+
+/* Initialize the table of subclasses of each reg class.  */
+static void
+setup_reg_subclasses (void)
+{
+  int i, j;
+  HARD_REG_SET temp_hard_regset2;
+
+  for (i = 0; i < N_REG_CLASSES; i++)
+    for (j = 0; j < N_REG_CLASSES; j++)
+      alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
+
+  for (i = 0; i < N_REG_CLASSES; i++)
+    {
+      if (i == (int) NO_REGS)
+	continue;
+
+      COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
+      AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+      if (hard_reg_set_empty_p (temp_hard_regset))
+	continue;
+      for (j = 0; j < N_REG_CLASSES; j++)
+	if (i != j)
+	  {
+	    enum reg_class *p;
+
+	    COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
+	    AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
+	    if (! hard_reg_set_subset_p (temp_hard_regset,
+					 temp_hard_regset2))
+	      continue;
+	    p = &alloc_reg_class_subclasses[j][0];
+	    while (*p != LIM_REG_CLASSES) p++;
+	    *p = (enum reg_class) i;
+	  }
+    }
+}
+
+
+
+/* Number of cover classes.  Cover classes is non-intersected register
+   classes containing all hard-registers available for the
+   allocation.  */
+int ira_reg_class_cover_size;
+
+/* The array containing cover classes (see also comments for macro
+   IRA_COVER_CLASSES).  Only first IRA_REG_CLASS_COVER_SIZE elements are
+   used for this.  */
+enum reg_class ira_reg_class_cover[N_REG_CLASSES];
+
+/* The number of elements in the subsequent array.  */
+int ira_important_classes_num;
+
+/* The array containing non-empty classes (including non-empty cover
+   classes) which are subclasses of cover classes.  Such classes is
+   important for calculation of the hard register usage costs.  */
+enum reg_class ira_important_classes[N_REG_CLASSES];
+
+/* The array containing indexes of important classes in the previous
+   array.  The array elements are defined only for important
+   classes.  */
+int ira_important_class_nums[N_REG_CLASSES];
+
+/* Set the four global variables defined above.  */
+static void
+setup_cover_and_important_classes (void)
+{
+  int i, j, n;
+  bool set_p, eq_p;
+  enum reg_class cl;
+  const enum reg_class *cover_classes;
+  HARD_REG_SET temp_hard_regset2;
+  static enum reg_class classes[LIM_REG_CLASSES + 1];
+
+  if (targetm.ira_cover_classes == NULL)
+    cover_classes = NULL;
+  else
+    cover_classes = targetm.ira_cover_classes ();
+  if (cover_classes == NULL)
+    ira_assert (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY);
+  else
+    {
+      for (i = 0; (cl = cover_classes[i]) != LIM_REG_CLASSES; i++)
+	classes[i] = cl;
+      classes[i] = LIM_REG_CLASSES;
+    }
+
+  if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
+    {
+      n = 0;
+      for (i = 0; i <= LIM_REG_CLASSES; i++)
+	{
+	  if (i == NO_REGS)
+	    continue;
+#ifdef CONSTRAINT__LIMIT
+	  for (j = 0; j < CONSTRAINT__LIMIT; j++)
+	    if ((int) regclass_for_constraint (j) == i)
+	      break;
+	  if (j < CONSTRAINT__LIMIT)
+	    {
+	      classes[n++] = i;
+	      continue;
+	    }
+#endif
+	  COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
+	  AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+	  for (j = 0; j < LIM_REG_CLASSES; j++)
+	    {
+	      if (i == j)
+		continue;
+	      COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
+	      AND_COMPL_HARD_REG_SET (temp_hard_regset2,
+				      no_unit_alloc_regs);
+	      if (hard_reg_set_equal_p (temp_hard_regset,
+					temp_hard_regset2))
+		    break;
+	    }
+	  if (j >= i)
+	    classes[n++] = i;
+	}
+      classes[n] = LIM_REG_CLASSES;
+    }
+
+  ira_reg_class_cover_size = 0;
+  for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
+    {
+      for (j = 0; j < i; j++)
+	if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
+	    && reg_classes_intersect_p (cl, classes[j]))
+	  gcc_unreachable ();
+      COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
+      AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+      if (! hard_reg_set_empty_p (temp_hard_regset))
+	ira_reg_class_cover[ira_reg_class_cover_size++] = cl;
+    }
+  ira_important_classes_num = 0;
+  for (cl = 0; cl < N_REG_CLASSES; cl++)
+    {
+      COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
+      AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+      if (! hard_reg_set_empty_p (temp_hard_regset))
+	{
+	  set_p = eq_p = false;
+	  for (j = 0; j < ira_reg_class_cover_size; j++)
+	    {
+	      COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
+	      AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+	      COPY_HARD_REG_SET (temp_hard_regset2,
+				 reg_class_contents[ira_reg_class_cover[j]]);
+	      AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
+	      if (cl == ira_reg_class_cover[j])
+		{
+		  eq_p = false;
+		  set_p = true;
+		  break;
+		}
+	      else if (hard_reg_set_equal_p (temp_hard_regset,
+					     temp_hard_regset2))
+		eq_p = true;
+	      else if (hard_reg_set_subset_p (temp_hard_regset,
+					      temp_hard_regset2))
+		set_p = true;
+	    }
+	  if (set_p && ! eq_p)
+	    {
+	      ira_important_class_nums[cl] = ira_important_classes_num;
+	      ira_important_classes[ira_important_classes_num++] = cl;
+	    }
+	}
+    }
+}
+
+/* Map of all register classes to corresponding cover class containing
+   the given class.  If given class is not a subset of a cover class,
+   we translate it into the cheapest cover class.  */
+enum reg_class ira_class_translate[N_REG_CLASSES];
+
+/* Set up array IRA_CLASS_TRANSLATE.  */
+static void
+setup_class_translate (void)
+{
+  enum reg_class cl, cover_class, best_class, *cl_ptr;
+  enum machine_mode mode;
+  int i, cost, min_cost, best_cost;
+
+  for (cl = 0; cl < N_REG_CLASSES; cl++)
+    ira_class_translate[cl] = NO_REGS;
+  
+  if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
+    for (cl = 0; cl < LIM_REG_CLASSES; cl++)
+      {
+	COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
+	AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+	for (i = 0; i < ira_reg_class_cover_size; i++)
+	  {
+	    HARD_REG_SET temp_hard_regset2;
+	    
+	    cover_class = ira_reg_class_cover[i];
+	    COPY_HARD_REG_SET (temp_hard_regset2,
+			       reg_class_contents[cover_class]);
+	    AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
+	    if (hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2))
+	      ira_class_translate[cl] = cover_class;
+	  }
+      }
+  for (i = 0; i < ira_reg_class_cover_size; i++)
+    {
+      cover_class = ira_reg_class_cover[i];
+      if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY)
+	for (cl_ptr = &alloc_reg_class_subclasses[cover_class][0];
+	     (cl = *cl_ptr) != LIM_REG_CLASSES;
+	     cl_ptr++)
+	  {
+	    if (ira_class_translate[cl] == NO_REGS)
+	      ira_class_translate[cl] = cover_class;
+#ifdef ENABLE_IRA_CHECKING
+	    else
+	      {
+		COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
+		AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+		if (! hard_reg_set_empty_p (temp_hard_regset))
+		  gcc_unreachable ();
+	      }
+#endif
+	  }
+      ira_class_translate[cover_class] = cover_class;
+    }
+  /* For classes which are not fully covered by a cover class (in
+     other words covered by more one cover class), use the cheapest
+     cover class.  */
+  for (cl = 0; cl < N_REG_CLASSES; cl++)
+    {
+      if (cl == NO_REGS || ira_class_translate[cl] != NO_REGS)
+	continue;
+      best_class = NO_REGS;
+      best_cost = INT_MAX;
+      for (i = 0; i < ira_reg_class_cover_size; i++)
+	{
+	  cover_class = ira_reg_class_cover[i];
+	  COPY_HARD_REG_SET (temp_hard_regset,
+			     reg_class_contents[cover_class]);
+	  AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
+	  AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+	  if (! hard_reg_set_empty_p (temp_hard_regset))
+	    {
+	      min_cost = INT_MAX;
+	      for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
+		{
+		  cost = (ira_memory_move_cost[mode][cl][0]
+			  + ira_memory_move_cost[mode][cl][1]);
+		  if (min_cost > cost)
+		    min_cost = cost;
+		}
+	      if (best_class == NO_REGS || best_cost > min_cost)
+		{
+		  best_class = cover_class;
+		  best_cost = min_cost;
+		}
+	    }
+	}
+      ira_class_translate[cl] = best_class;
+    }
+}
+
+/* The biggest important reg_class inside of intersection of the two
+   reg_classes (that is calculated taking only hard registers
+   available for allocation into account).  If the both reg_classes
+   contain no hard registers available for allocation, the value is
+   calculated by taking all hard-registers including fixed ones into
+   account.  */
+enum reg_class ira_reg_class_intersect[N_REG_CLASSES][N_REG_CLASSES];
+
+/* True if the two classes (that is calculated taking only hard
+   registers available for allocation into account) are
+   intersected.  */
+bool ira_reg_classes_intersect_p[N_REG_CLASSES][N_REG_CLASSES];
+
+/* Important classes with end marker LIM_REG_CLASSES which are
+   supersets with given important class (the first index).  That
+   includes given class itself.  This is calculated taking only hard
+   registers available for allocation into account.  */
+enum reg_class ira_reg_class_super_classes[N_REG_CLASSES][N_REG_CLASSES];
+
+/* The biggest important reg_class inside of union of the two
+   reg_classes (that is calculated taking only hard registers
+   available for allocation into account).  If the both reg_classes
+   contain no hard registers available for allocation, the value is
+   calculated by taking all hard-registers including fixed ones into
+   account.  In other words, the value is the corresponding
+   reg_class_subunion value.  */
+enum reg_class ira_reg_class_union[N_REG_CLASSES][N_REG_CLASSES];
+
+/* Set up the above reg class relations.  */
+static void
+setup_reg_class_relations (void)
+{
+  int i, cl1, cl2, cl3;
+  HARD_REG_SET intersection_set, union_set, temp_set2;
+  bool important_class_p[N_REG_CLASSES];
+
+  memset (important_class_p, 0, sizeof (important_class_p));
+  for (i = 0; i < ira_important_classes_num; i++)
+    important_class_p[ira_important_classes[i]] = true;
+  for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
+    {
+      ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
+      for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
+	{
+	  ira_reg_classes_intersect_p[cl1][cl2] = false;
+	  ira_reg_class_intersect[cl1][cl2] = NO_REGS;
+	  COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
+	  AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+	  COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
+	  AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
+	  if (hard_reg_set_empty_p (temp_hard_regset)
+	      && hard_reg_set_empty_p (temp_set2))
+	    {
+	      for (i = 0;; i++)
+		{
+		  cl3 = reg_class_subclasses[cl1][i];
+		  if (cl3 == LIM_REG_CLASSES)
+		    break;
+		  if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
+					  cl3))
+		    ira_reg_class_intersect[cl1][cl2] = cl3;
+		}
+	      ira_reg_class_union[cl1][cl2] = reg_class_subunion[cl1][cl2];
+	      continue;
+	    }
+	  ira_reg_classes_intersect_p[cl1][cl2]
+	    = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
+	  if (important_class_p[cl1] && important_class_p[cl2]
+	      && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
+	    {
+	      enum reg_class *p;
+
+	      p = &ira_reg_class_super_classes[cl1][0];
+	      while (*p != LIM_REG_CLASSES)
+		p++;
+	      *p++ = (enum reg_class) cl2;
+	      *p = LIM_REG_CLASSES;
+	    }
+	  ira_reg_class_union[cl1][cl2] = NO_REGS;
+	  COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
+	  AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
+	  AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
+	  COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
+	  IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
+	  AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
+	  for (i = 0; i < ira_important_classes_num; i++)
+	    {
+	      cl3 = ira_important_classes[i];
+	      COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
+	      AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
+	      if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
+		{
+		  COPY_HARD_REG_SET
+		    (temp_set2,
+		     reg_class_contents[(int)
+					ira_reg_class_intersect[cl1][cl2]]);
+		  AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
+	 	  if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
+		      /* Ignore unavailable hard registers and prefer
+			 smallest class for debugging purposes.  */
+		      || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
+			  && hard_reg_set_subset_p
+			     (reg_class_contents[cl3],
+			      reg_class_contents
+			      [(int) ira_reg_class_intersect[cl1][cl2]])))
+		    ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
+		}
+	      if (hard_reg_set_subset_p (temp_hard_regset, union_set))
+		{
+		  COPY_HARD_REG_SET
+		    (temp_set2,
+		     reg_class_contents[(int) ira_reg_class_union[cl1][cl2]]);
+		  AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
+	 	  if (ira_reg_class_union[cl1][cl2] == NO_REGS
+		      || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
+		      
+			  && (! hard_reg_set_equal_p (temp_set2,
+						      temp_hard_regset)
+			      /* Ignore unavailable hard registers and
+				 prefer smallest class for debugging
+				 purposes.  */
+			      || hard_reg_set_subset_p
+			         (reg_class_contents[cl3],
+				  reg_class_contents
+				  [(int) ira_reg_class_union[cl1][cl2]]))))
+		    ira_reg_class_union[cl1][cl2] = (enum reg_class) cl3;
+		}
+	    }
+	}
+    }
+}
+
+/* Output all cover classes and the translation map into file F.  */
+static void
+print_class_cover (FILE *f)
+{
+  static const char *const reg_class_names[] = REG_CLASS_NAMES;
+  int i;
+
+  fprintf (f, "Class cover:\n");
+  for (i = 0; i < ira_reg_class_cover_size; i++)
+    fprintf (f, " %s", reg_class_names[ira_reg_class_cover[i]]);
+  fprintf (f, "\nClass translation:\n");
+  for (i = 0; i < N_REG_CLASSES; i++)
+    fprintf (f, " %s -> %s\n", reg_class_names[i],
+	     reg_class_names[ira_class_translate[i]]);
+}
+
+/* Output all cover classes and the translation map into
+   stderr.  */
+void
+ira_debug_class_cover (void)
+{
+  print_class_cover (stderr);
+}
+
+/* Set up different arrays concerning class subsets, cover and
+   important classes.  */
+static void
+find_reg_class_closure (void)
+{
+  setup_reg_subclasses ();
+  setup_cover_and_important_classes ();
+  setup_class_translate ();
+  setup_reg_class_relations ();
+}
+
+
+
+/* Map: hard register number -> cover class it belongs to.  If the
+   corresponding class is NO_REGS, the hard register is not available
+   for allocation.  */
+enum reg_class ira_hard_regno_cover_class[FIRST_PSEUDO_REGISTER];
+
+/* Set up the array above.  */
+static void
+setup_hard_regno_cover_class (void)
+{
+  int i, j;
+  enum reg_class cl;
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    {
+      ira_hard_regno_cover_class[i] = NO_REGS;
+      for (j = 0; j < ira_reg_class_cover_size; j++)
+	{
+	  cl = ira_reg_class_cover[j];
+	  if (ira_class_hard_reg_index[cl][i] >= 0)
+	    {
+	      ira_hard_regno_cover_class[i] = cl;
+	      break;
+	    }
+	}
+	    
+    }
+}
+
+
+
+/* Map: register class x machine mode -> number of hard registers of
+   given class needed to store value of given mode.  If the number is
+   different, the size will be negative.  */
+int ira_reg_class_nregs[N_REG_CLASSES][MAX_MACHINE_MODE];
+
+/* Maximal value of the previous array elements.  */
+int ira_max_nregs;
+
+/* Form IRA_REG_CLASS_NREGS map.  */
+static void
+setup_reg_class_nregs (void)
+{
+  int m;
+  enum reg_class cl;
+
+  ira_max_nregs = -1;
+  for (cl = 0; cl < N_REG_CLASSES; cl++)
+    for (m = 0; m < MAX_MACHINE_MODE; m++)
+      {
+	ira_reg_class_nregs[cl][m] = CLASS_MAX_NREGS (cl, m);
+	if (ira_max_nregs < ira_reg_class_nregs[cl][m])
+	  ira_max_nregs = ira_reg_class_nregs[cl][m];
+      }
+}
+
+
+
+/* Array whose values are hard regset of hard registers available for
+   the allocation of given register class whose HARD_REGNO_MODE_OK
+   values for given mode are zero.  */
+HARD_REG_SET prohibited_class_mode_regs[N_REG_CLASSES][NUM_MACHINE_MODES];
+
+/* Set up PROHIBITED_CLASS_MODE_REGS.  */
+static void
+setup_prohibited_class_mode_regs (void)
+{
+  int i, j, k, hard_regno;
+  enum reg_class cl;
+
+  for (i = 0; i < ira_reg_class_cover_size; i++)
+    {
+      cl = ira_reg_class_cover[i];
+      for (j = 0; j < NUM_MACHINE_MODES; j++)
+	{
+	  CLEAR_HARD_REG_SET (prohibited_class_mode_regs[cl][j]);
+	  for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
+	    {
+	      hard_regno = ira_class_hard_regs[cl][k];
+	      if (! HARD_REGNO_MODE_OK (hard_regno, j))
+		SET_HARD_REG_BIT (prohibited_class_mode_regs[cl][j],
+				  hard_regno);
+	    }
+	}
+    }
+}
+
+
+
+/* Allocate and initialize IRA_REGISTER_MOVE_COST,
+   IRA_MAY_MOVE_IN_COST, and IRA_MAY_MOVE_OUT_COST for MODE if it is
+   not done yet.  */
+void
+ira_init_register_move_cost (enum machine_mode mode)
+{
+  int cl1, cl2;
+
+  ira_assert (ira_register_move_cost[mode] == NULL
+	      && ira_may_move_in_cost[mode] == NULL
+	      && ira_may_move_out_cost[mode] == NULL);
+  if (move_cost[mode] == NULL)
+    init_move_cost (mode);
+  ira_register_move_cost[mode] = move_cost[mode];
+  /* Don't use ira_allocate because the tables exist out of scope of a
+     IRA call.  */
+  ira_may_move_in_cost[mode]
+    = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
+  memcpy (ira_may_move_in_cost[mode], may_move_in_cost[mode],
+	  sizeof (move_table) * N_REG_CLASSES);
+  ira_may_move_out_cost[mode]
+    = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
+  memcpy (ira_may_move_out_cost[mode], may_move_out_cost[mode],
+	  sizeof (move_table) * N_REG_CLASSES);
+  for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
+    {
+      for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
+	{
+	  if (ira_class_subset_p[cl1][cl2])
+	    ira_may_move_in_cost[mode][cl1][cl2] = 0;
+	  if (ira_class_subset_p[cl2][cl1])
+	    ira_may_move_out_cost[mode][cl1][cl2] = 0;
+	}
+    }
+}
+
+
+
+/* This is called once during compiler work.  It sets up
+   different arrays whose values don't depend on the compiled
+   function.  */
+void
+ira_init_once (void)
+{
+  enum machine_mode mode;
+
+  for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
+    {
+      ira_register_move_cost[mode] = NULL;
+      ira_may_move_in_cost[mode] = NULL;
+      ira_may_move_out_cost[mode] = NULL;
+    }
+  ira_init_costs_once ();
+}
+
+/* Free ira_register_move_cost, ira_may_move_in_cost, and
+   ira_may_move_out_cost for each mode.  */
+static void
+free_register_move_costs (void)
+{
+  enum machine_mode mode;
+
+  for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
+    {
+      if (ira_may_move_in_cost[mode] != NULL)
+	free (ira_may_move_in_cost[mode]);
+      if (ira_may_move_out_cost[mode] != NULL)
+	free (ira_may_move_out_cost[mode]);
+      ira_register_move_cost[mode] = NULL;
+      ira_may_move_in_cost[mode] = NULL;
+      ira_may_move_out_cost[mode] = NULL;
+    }
+}
+
+/* This is called every time when register related information is
+   changed.  */
+void
+ira_init (void)
+{
+  free_register_move_costs ();
+  setup_reg_mode_hard_regset ();
+  setup_alloc_regs (flag_omit_frame_pointer != 0);
+  setup_class_subset_and_memory_move_costs ();
+  find_reg_class_closure ();
+  setup_hard_regno_cover_class ();
+  setup_reg_class_nregs ();
+  setup_prohibited_class_mode_regs ();
+  ira_init_costs ();
+}
+
+/* Function called once at the end of compiler work.  */
+void
+ira_finish_once (void)
+{
+  ira_finish_costs_once ();
+  free_register_move_costs ();
+}
+
+
+
+/* Array whose values are hard regset of hard registers for which
+   move of the hard register in given mode into itself is
+   prohibited.  */
+HARD_REG_SET ira_prohibited_mode_move_regs[NUM_MACHINE_MODES];
+
+/* Flag of that the above array has been initialized.  */
+static bool ira_prohibited_mode_move_regs_initialized_p = false;
+
+/* Set up IRA_PROHIBITED_MODE_MOVE_REGS.  */
+static void
+setup_prohibited_mode_move_regs (void)
+{
+  int i, j;
+  rtx test_reg1, test_reg2, move_pat, move_insn;
+
+  if (ira_prohibited_mode_move_regs_initialized_p)
+    return;
+  ira_prohibited_mode_move_regs_initialized_p = true;
+  test_reg1 = gen_rtx_REG (VOIDmode, 0);
+  test_reg2 = gen_rtx_REG (VOIDmode, 0);
+  move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2);
+  move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, 0, 0, move_pat, -1, 0);
+  for (i = 0; i < NUM_MACHINE_MODES; i++)
+    {
+      SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
+      for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
+	{
+	  if (! HARD_REGNO_MODE_OK (j, i))
+	    continue;
+	  SET_REGNO (test_reg1, j);
+	  PUT_MODE (test_reg1, i);
+	  SET_REGNO (test_reg2, j);
+	  PUT_MODE (test_reg2, i);
+	  INSN_CODE (move_insn) = -1;
+	  recog_memoized (move_insn);
+	  if (INSN_CODE (move_insn) < 0)
+	    continue;
+	  extract_insn (move_insn);
+	  if (! constrain_operands (1))
+	    continue;
+	  CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
+	}
+    }
+}
+
+
+
+/* Function specific hard registers that can not be used for the
+   register allocation.  */
+HARD_REG_SET ira_no_alloc_regs;
+
+/* Return TRUE if *LOC contains an asm.  */
+static int
+insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
+{
+  if ( !*loc)
+    return FALSE;
+  if (GET_CODE (*loc) == ASM_OPERANDS)
+    return TRUE;
+  return FALSE;
+}
+
+
+/* Return TRUE if INSN contains an ASM.  */
+static bool
+insn_contains_asm (rtx insn)
+{
+  return for_each_rtx (&insn, insn_contains_asm_1, NULL);
+}
+
+/* Set up regs_asm_clobbered.  */
+static void
+compute_regs_asm_clobbered (char *regs_asm_clobbered)
+{
+  basic_block bb;
+
+  memset (regs_asm_clobbered, 0, sizeof (char) * FIRST_PSEUDO_REGISTER);
+  
+  FOR_EACH_BB (bb)
+    {
+      rtx insn;
+      FOR_BB_INSNS_REVERSE (bb, insn)
+	{
+	  df_ref *def_rec;
+
+	  if (insn_contains_asm (insn))
+	    for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
+	      {
+		df_ref def = *def_rec;
+		unsigned int dregno = DF_REF_REGNO (def);
+		if (dregno < FIRST_PSEUDO_REGISTER)
+		  {
+		    unsigned int i;
+		    enum machine_mode mode = GET_MODE (DF_REF_REAL_REG (def));
+		    unsigned int end = dregno 
+		      + hard_regno_nregs[dregno][mode] - 1;
+
+		    for (i = dregno; i <= end; ++i)
+		      regs_asm_clobbered[i] = 1;
+		  }
+	      }
+	}
+    }
+}
+
+
+/* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE.  */
+static void
+setup_eliminable_regset (void)
+{
+  /* Like regs_ever_live, but 1 if a reg is set or clobbered from an
+     asm.  Unlike regs_ever_live, elements of this array corresponding
+     to eliminable regs (like the frame pointer) are set if an asm
+     sets them.  */
+  char *regs_asm_clobbered
+    = (char *) alloca (FIRST_PSEUDO_REGISTER * sizeof (char));
+#ifdef ELIMINABLE_REGS
+  int i;
+  static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
+#endif
+  /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
+     sp for alloca.  So we can't eliminate the frame pointer in that
+     case.  At some point, we should improve this by emitting the
+     sp-adjusting insns for this case.  */
+  int need_fp
+    = (! flag_omit_frame_pointer
+       || (cfun->calls_alloca && EXIT_IGNORE_STACK)
+       || crtl->accesses_prior_frames
+       || crtl->stack_realign_needed
+       || FRAME_POINTER_REQUIRED);
+
+  frame_pointer_needed = need_fp;
+
+  COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
+  CLEAR_HARD_REG_SET (eliminable_regset);
+
+  compute_regs_asm_clobbered (regs_asm_clobbered);
+  /* Build the regset of all eliminable registers and show we can't
+     use those that we already know won't be eliminated.  */
+#ifdef ELIMINABLE_REGS
+  for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
+    {
+      bool cannot_elim
+	= (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
+	   || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
+
+      if (! regs_asm_clobbered[eliminables[i].from])
+	{
+	    SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
+
+	    if (cannot_elim)
+	      SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
+	}
+      else if (cannot_elim)
+	error ("%s cannot be used in asm here",
+	       reg_names[eliminables[i].from]);
+      else
+	df_set_regs_ever_live (eliminables[i].from, true);
+    }
+#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
+  if (! regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM])
+    {
+      SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
+      if (need_fp)
+	SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
+    }
+  else if (need_fp)
+    error ("%s cannot be used in asm here",
+	   reg_names[HARD_FRAME_POINTER_REGNUM]);
+  else
+    df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
+#endif
+
+#else
+  if (! regs_asm_clobbered[FRAME_POINTER_REGNUM])
+    {
+      SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
+      if (need_fp)
+	SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
+    }
+  else if (need_fp)
+    error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
+  else
+    df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
+#endif
+}
+
+
+
+/* The length of the following two arrays.  */
+int ira_reg_equiv_len;
+
+/* The element value is TRUE if the corresponding regno value is
+   invariant.  */
+bool *ira_reg_equiv_invariant_p;
+
+/* The element value is equiv constant of given pseudo-register or
+   NULL_RTX.  */
+rtx *ira_reg_equiv_const;
+
+/* Set up the two arrays declared above.  */
+static void
+find_reg_equiv_invariant_const (void)
+{
+  int i;
+  bool invariant_p;
+  rtx list, insn, note, constant, x;
+
+  for (i = FIRST_PSEUDO_REGISTER; i < reg_equiv_init_size; i++)
+    {
+      constant = NULL_RTX;
+      invariant_p = false;
+      for (list = reg_equiv_init[i]; list != NULL_RTX; list = XEXP (list, 1))
+	{
+	  insn = XEXP (list, 0);
+	  note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
+	  
+	  if (note == NULL_RTX)
+	    continue;
+
+	  x = XEXP (note, 0);
+	  
+	  if (! function_invariant_p (x)
+	      || ! flag_pic
+	      /* A function invariant is often CONSTANT_P but may
+		 include a register.  We promise to only pass CONSTANT_P
+		 objects to LEGITIMATE_PIC_OPERAND_P.  */
+	      || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
+	    {
+	      /* It can happen that a REG_EQUIV note contains a MEM
+		 that is not a legitimate memory operand.  As later
+		 stages of the reload assume that all addresses found
+		 in the reg_equiv_* arrays were originally legitimate,
+		 we ignore such REG_EQUIV notes.  */
+	      if (memory_operand (x, VOIDmode))
+		invariant_p = MEM_READONLY_P (x);
+	      else if (function_invariant_p (x))
+		{
+		  if (GET_CODE (x) == PLUS
+		      || x == frame_pointer_rtx || x == arg_pointer_rtx)
+		    invariant_p = true;
+		  else
+		    constant = x;
+		}
+	    }
+	}
+      ira_reg_equiv_invariant_p[i] = invariant_p;
+      ira_reg_equiv_const[i] = constant;
+    }
+}
+
+
+
+/* Vector of substitutions of register numbers,
+   used to map pseudo regs into hardware regs.
+   This is set up as a result of register allocation.
+   Element N is the hard reg assigned to pseudo reg N,
+   or is -1 if no hard reg was assigned.
+   If N is a hard reg number, element N is N.  */
+short *reg_renumber;
+
+/* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
+   the allocation found by IRA.  */
+static void
+setup_reg_renumber (void)
+{
+  int regno, hard_regno;
+  ira_allocno_t a;
+  ira_allocno_iterator ai;
+
+  caller_save_needed = 0;
+  FOR_EACH_ALLOCNO (a, ai)
+    {
+      /* There are no caps at this point.  */
+      ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
+      if (! ALLOCNO_ASSIGNED_P (a))
+	/* It can happen if A is not referenced but partially anticipated
+	   somewhere in a region.  */
+	ALLOCNO_ASSIGNED_P (a) = true;
+      ira_free_allocno_updated_costs (a);
+      hard_regno = ALLOCNO_HARD_REGNO (a);
+      regno = (int) REGNO (ALLOCNO_REG (a));
+      reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
+      if (hard_regno >= 0 && ALLOCNO_CALLS_CROSSED_NUM (a) != 0
+	  && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
+					  call_used_reg_set))
+	{
+	  ira_assert (!optimize || flag_caller_saves
+		      || regno >= ira_reg_equiv_len
+		      || ira_reg_equiv_const[regno]
+		      || ira_reg_equiv_invariant_p[regno]);
+	  caller_save_needed = 1;
+	}
+    }
+}
+
+/* Set up allocno assignment flags for further allocation
+   improvements.  */
+static void
+setup_allocno_assignment_flags (void)
+{
+  int hard_regno;
+  ira_allocno_t a;
+  ira_allocno_iterator ai;
+
+  FOR_EACH_ALLOCNO (a, ai)
+    {
+      if (! ALLOCNO_ASSIGNED_P (a))
+	/* It can happen if A is not referenced but partially anticipated
+	   somewhere in a region.  */
+	ira_free_allocno_updated_costs (a);
+      hard_regno = ALLOCNO_HARD_REGNO (a);
+      /* Don't assign hard registers to allocnos which are destination
+	 of removed store at the end of loop.  It has no sense to keep
+	 the same value in different hard registers.  It is also
+	 impossible to assign hard registers correctly to such
+	 allocnos because the cost info and info about intersected
+	 calls are incorrect for them.  */
+      ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
+				|| ALLOCNO_MEM_OPTIMIZED_DEST_P (a)
+				|| (ALLOCNO_MEMORY_COST (a)
+				    - ALLOCNO_COVER_CLASS_COST (a)) < 0);
+      ira_assert (hard_regno < 0
+		  || ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
+						  reg_class_contents
+						  [ALLOCNO_COVER_CLASS (a)]));
+    }
+}
+
+/* Evaluate overall allocation cost and the costs for using hard
+   registers and memory for allocnos.  */
+static void
+calculate_allocation_cost (void)
+{
+  int hard_regno, cost;
+  ira_allocno_t a;
+  ira_allocno_iterator ai;
+
+  ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
+  FOR_EACH_ALLOCNO (a, ai)
+    {
+      hard_regno = ALLOCNO_HARD_REGNO (a);
+      ira_assert (hard_regno < 0
+		  || ! ira_hard_reg_not_in_set_p
+		       (hard_regno, ALLOCNO_MODE (a),
+			reg_class_contents[ALLOCNO_COVER_CLASS (a)])); 
+      if (hard_regno < 0)
+	{
+	  cost = ALLOCNO_MEMORY_COST (a);
+	  ira_mem_cost += cost;
+	}
+      else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
+	{
+	  cost = (ALLOCNO_HARD_REG_COSTS (a)
+		  [ira_class_hard_reg_index
+		   [ALLOCNO_COVER_CLASS (a)][hard_regno]]);
+	  ira_reg_cost += cost;
+	}
+      else
+	{
+	  cost = ALLOCNO_COVER_CLASS_COST (a);
+	  ira_reg_cost += cost;
+	}
+      ira_overall_cost += cost;
+    }
+
+  if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
+    {
+      fprintf (ira_dump_file,
+	       "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
+	       ira_overall_cost, ira_reg_cost, ira_mem_cost,
+	       ira_load_cost, ira_store_cost, ira_shuffle_cost);
+      fprintf (ira_dump_file, "+++       move loops %d, new jumps %d\n",
+	       ira_move_loops_num, ira_additional_jumps_num);
+    }
+
+}
+
+#ifdef ENABLE_IRA_CHECKING
+/* Check the correctness of the allocation.  We do need this because
+   of complicated code to transform more one region internal
+   representation into one region representation.  */
+static void
+check_allocation (void)
+{
+  ira_allocno_t a, conflict_a;
+  int hard_regno, conflict_hard_regno, nregs, conflict_nregs;
+  ira_allocno_conflict_iterator aci;
+  ira_allocno_iterator ai;
+
+  FOR_EACH_ALLOCNO (a, ai)
+    {
+      if (ALLOCNO_CAP_MEMBER (a) != NULL
+	  || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
+	continue;
+      nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
+      FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
+	if ((conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a)) >= 0)
+	  {
+	    conflict_nregs
+	      = (hard_regno_nregs
+		 [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
+	    if ((conflict_hard_regno <= hard_regno
+		 && hard_regno < conflict_hard_regno + conflict_nregs)
+		|| (hard_regno <= conflict_hard_regno
+		    && conflict_hard_regno < hard_regno + nregs))
+	      {
+		fprintf (stderr, "bad allocation for %d and %d\n",
+			 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
+		gcc_unreachable ();
+	      }
+	  }
+    }
+}
+#endif
+
+/* Fix values of array REG_EQUIV_INIT after live range splitting done
+   by IRA.  */
+static void
+fix_reg_equiv_init (void)
+{
+  int max_regno = max_reg_num ();
+  int i, new_regno;
+  rtx x, prev, next, insn, set;
+  
+  if (reg_equiv_init_size < max_regno)
+    {
+      reg_equiv_init
+	= (rtx *) ggc_realloc (reg_equiv_init, max_regno * sizeof (rtx));
+      while (reg_equiv_init_size < max_regno)
+	reg_equiv_init[reg_equiv_init_size++] = NULL_RTX;
+      for (i = FIRST_PSEUDO_REGISTER; i < reg_equiv_init_size; i++)
+	for (prev = NULL_RTX, x = reg_equiv_init[i]; x != NULL_RTX; x = next)
+	  {
+	    next = XEXP (x, 1);
+	    insn = XEXP (x, 0);
+	    set = single_set (insn);
+	    ira_assert (set != NULL_RTX
+			&& (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
+	    if (REG_P (SET_DEST (set))
+		&& ((int) REGNO (SET_DEST (set)) == i
+		    || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
+	      new_regno = REGNO (SET_DEST (set));
+	    else if (REG_P (SET_SRC (set))
+		     && ((int) REGNO (SET_SRC (set)) == i
+			 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
+	      new_regno = REGNO (SET_SRC (set));
+	    else
+ 	      gcc_unreachable ();
+	    if (new_regno == i)
+	      prev = x;
+	    else
+	      {
+		if (prev == NULL_RTX)
+		  reg_equiv_init[i] = next;
+		else
+		  XEXP (prev, 1) = next;
+		XEXP (x, 1) = reg_equiv_init[new_regno];
+		reg_equiv_init[new_regno] = x;
+	      }
+	  }
+    }
+}
+
+#ifdef ENABLE_IRA_CHECKING
+/* Print redundant memory-memory copies.  */
+static void
+print_redundant_copies (void)
+{
+  int hard_regno;
+  ira_allocno_t a;
+  ira_copy_t cp, next_cp;
+  ira_allocno_iterator ai;
+  
+  FOR_EACH_ALLOCNO (a, ai)
+    {
+      if (ALLOCNO_CAP_MEMBER (a) != NULL)
+	/* It is a cap. */
+	continue;
+      hard_regno = ALLOCNO_HARD_REGNO (a);
+      if (hard_regno >= 0)
+	continue;
+      for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
+	if (cp->first == a)
+	  next_cp = cp->next_first_allocno_copy;
+	else
+	  {
+	    next_cp = cp->next_second_allocno_copy;
+	    if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
+		&& cp->insn != NULL_RTX
+		&& ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
+	      fprintf (ira_dump_file,
+		       "        Redundant move from %d(freq %d):%d\n",
+		       INSN_UID (cp->insn), cp->freq, hard_regno);
+	  }
+    }
+}
+#endif
+
+/* Setup preferred and alternative classes for new pseudo-registers
+   created by IRA starting with START.  */
+static void
+setup_preferred_alternate_classes_for_new_pseudos (int start)
+{
+  int i, old_regno;
+  int max_regno = max_reg_num ();
+
+  for (i = start; i < max_regno; i++)
+    {
+      old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
+      ira_assert (i != old_regno); 
+      setup_reg_classes (i, reg_preferred_class (old_regno),
+			 reg_alternate_class (old_regno));
+      if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+	fprintf (ira_dump_file,
+		 "    New r%d: setting preferred %s, alternative %s\n",
+		 i, reg_class_names[reg_preferred_class (old_regno)],
+		 reg_class_names[reg_alternate_class (old_regno)]);
+    }
+}
+
+
+
+/* Regional allocation can create new pseudo-registers.  This function
+   expands some arrays for pseudo-registers.  */
+static void
+expand_reg_info (int old_size)
+{
+  int i;
+  int size = max_reg_num ();
+
+  resize_reg_info ();
+  for (i = old_size; i < size; i++)
+    {
+      reg_renumber[i] = -1;
+      setup_reg_classes (i, GENERAL_REGS, ALL_REGS);
+    }
+}
+
+/* Return TRUE if there is too high register pressure in the function.
+   It is used to decide when stack slot sharing is worth to do.  */
+static bool
+too_high_register_pressure_p (void)
+{
+  int i;
+  enum reg_class cover_class;
+  
+  for (i = 0; i < ira_reg_class_cover_size; i++)
+    {
+      cover_class = ira_reg_class_cover[i];
+      if (ira_loop_tree_root->reg_pressure[cover_class] > 10000)
+	return true;
+    }
+  return false;
+}
+
+
+
+/* Indicate that hard register number FROM was eliminated and replaced with
+   an offset from hard register number TO.  The status of hard registers live
+   at the start of a basic block is updated by replacing a use of FROM with
+   a use of TO.  */
+
+void
+mark_elimination (int from, int to)
+{
+  basic_block bb;
+
+  FOR_EACH_BB (bb)
+    {
+      /* We don't use LIVE info in IRA.  */
+      regset r = DF_LR_IN (bb);
+
+      if (REGNO_REG_SET_P (r, from))
+	{
+	  CLEAR_REGNO_REG_SET (r, from);
+	  SET_REGNO_REG_SET (r, to);
+	}
+    }
+}
+
+
+
+struct equivalence
+{
+  /* Set when a REG_EQUIV note is found or created.  Use to
+     keep track of what memory accesses might be created later,
+     e.g. by reload.  */
+  rtx replacement;
+  rtx *src_p;
+  /* The list of each instruction which initializes this register.  */
+  rtx init_insns;
+  /* Loop depth is used to recognize equivalences which appear
+     to be present within the same loop (or in an inner loop).  */
+  int loop_depth;
+  /* Nonzero if this had a preexisting REG_EQUIV note.  */
+  int is_arg_equivalence;
+  /* Set when an attempt should be made to replace a register
+     with the associated src_p entry.  */
+  char replace;
+};
+
+/* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
+   structure for that register.  */
+static struct equivalence *reg_equiv;
+
+/* Used for communication between the following two functions: contains
+   a MEM that we wish to ensure remains unchanged.  */
+static rtx equiv_mem;
+
+/* Set nonzero if EQUIV_MEM is modified.  */
+static int equiv_mem_modified;
+
+/* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
+   Called via note_stores.  */
+static void
+validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
+			       void *data ATTRIBUTE_UNUSED)
+{
+  if ((REG_P (dest)
+       && reg_overlap_mentioned_p (dest, equiv_mem))
+      || (MEM_P (dest)
+	  && true_dependence (dest, VOIDmode, equiv_mem, rtx_varies_p)))
+    equiv_mem_modified = 1;
+}
+
+/* Verify that no store between START and the death of REG invalidates
+   MEMREF.  MEMREF is invalidated by modifying a register used in MEMREF,
+   by storing into an overlapping memory location, or with a non-const
+   CALL_INSN.
+
+   Return 1 if MEMREF remains valid.  */
+static int
+validate_equiv_mem (rtx start, rtx reg, rtx memref)
+{
+  rtx insn;
+  rtx note;
+
+  equiv_mem = memref;
+  equiv_mem_modified = 0;
+
+  /* If the memory reference has side effects or is volatile, it isn't a
+     valid equivalence.  */
+  if (side_effects_p (memref))
+    return 0;
+
+  for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
+    {
+      if (! INSN_P (insn))
+	continue;
+
+      if (find_reg_note (insn, REG_DEAD, reg))
+	return 1;
+
+      if (CALL_P (insn) && ! MEM_READONLY_P (memref)
+	  && ! RTL_CONST_OR_PURE_CALL_P (insn))
+	return 0;
+
+      note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
+
+      /* If a register mentioned in MEMREF is modified via an
+	 auto-increment, we lose the equivalence.  Do the same if one
+	 dies; although we could extend the life, it doesn't seem worth
+	 the trouble.  */
+
+      for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
+	if ((REG_NOTE_KIND (note) == REG_INC
+	     || REG_NOTE_KIND (note) == REG_DEAD)
+	    && REG_P (XEXP (note, 0))
+	    && reg_overlap_mentioned_p (XEXP (note, 0), memref))
+	  return 0;
+    }
+
+  return 0;
+}
+
+/* Returns zero if X is known to be invariant.  */
+static int
+equiv_init_varies_p (rtx x)
+{
+  RTX_CODE code = GET_CODE (x);
+  int i;
+  const char *fmt;
+
+  switch (code)
+    {
+    case MEM:
+      return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
+
+    case CONST:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case CONST_FIXED:
+    case CONST_VECTOR:
+    case SYMBOL_REF:
+    case LABEL_REF:
+      return 0;
+
+    case REG:
+      return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
+
+    case ASM_OPERANDS:
+      if (MEM_VOLATILE_P (x))
+	return 1;
+
+      /* Fall through.  */
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    if (fmt[i] == 'e')
+      {
+	if (equiv_init_varies_p (XEXP (x, i)))
+	  return 1;
+      }
+    else if (fmt[i] == 'E')
+      {
+	int j;
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  if (equiv_init_varies_p (XVECEXP (x, i, j)))
+	    return 1;
+      }
+
+  return 0;
+}
+
+/* Returns nonzero if X (used to initialize register REGNO) is movable.
+   X is only movable if the registers it uses have equivalent initializations
+   which appear to be within the same loop (or in an inner loop) and movable
+   or if they are not candidates for local_alloc and don't vary.  */
+static int
+equiv_init_movable_p (rtx x, int regno)
+{
+  int i, j;
+  const char *fmt;
+  enum rtx_code code = GET_CODE (x);
+
+  switch (code)
+    {
+    case SET:
+      return equiv_init_movable_p (SET_SRC (x), regno);
+
+    case CC0:
+    case CLOBBER:
+      return 0;
+
+    case PRE_INC:
+    case PRE_DEC:
+    case POST_INC:
+    case POST_DEC:
+    case PRE_MODIFY:
+    case POST_MODIFY:
+      return 0;
+
+    case REG:
+      return (reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
+	      && reg_equiv[REGNO (x)].replace)
+	     || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS && ! rtx_varies_p (x, 0));
+
+    case UNSPEC_VOLATILE:
+      return 0;
+
+    case ASM_OPERANDS:
+      if (MEM_VOLATILE_P (x))
+	return 0;
+
+      /* Fall through.  */
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    switch (fmt[i])
+      {
+      case 'e':
+	if (! equiv_init_movable_p (XEXP (x, i), regno))
+	  return 0;
+	break;
+      case 'E':
+	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+	  if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
+	    return 0;
+	break;
+      }
+
+  return 1;
+}
+
+/* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true.  */
+static int
+contains_replace_regs (rtx x)
+{
+  int i, j;
+  const char *fmt;
+  enum rtx_code code = GET_CODE (x);
+
+  switch (code)
+    {
+    case CONST_INT:
+    case CONST:
+    case LABEL_REF:
+    case SYMBOL_REF:
+    case CONST_DOUBLE:
+    case CONST_FIXED:
+    case CONST_VECTOR:
+    case PC:
+    case CC0:
+    case HIGH:
+      return 0;
+
+    case REG:
+      return reg_equiv[REGNO (x)].replace;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    switch (fmt[i])
+      {
+      case 'e':
+	if (contains_replace_regs (XEXP (x, i)))
+	  return 1;
+	break;
+      case 'E':
+	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+	  if (contains_replace_regs (XVECEXP (x, i, j)))
+	    return 1;
+	break;
+      }
+
+  return 0;
+}
+
+/* TRUE if X references a memory location that would be affected by a store
+   to MEMREF.  */
+static int
+memref_referenced_p (rtx memref, rtx x)
+{
+  int i, j;
+  const char *fmt;
+  enum rtx_code code = GET_CODE (x);
+
+  switch (code)
+    {
+    case CONST_INT:
+    case CONST:
+    case LABEL_REF:
+    case SYMBOL_REF:
+    case CONST_DOUBLE:
+    case CONST_FIXED:
+    case CONST_VECTOR:
+    case PC:
+    case CC0:
+    case HIGH:
+    case LO_SUM:
+      return 0;
+
+    case REG:
+      return (reg_equiv[REGNO (x)].replacement
+	      && memref_referenced_p (memref,
+				      reg_equiv[REGNO (x)].replacement));
+
+    case MEM:
+      if (true_dependence (memref, VOIDmode, x, rtx_varies_p))
+	return 1;
+      break;
+
+    case SET:
+      /* If we are setting a MEM, it doesn't count (its address does), but any
+	 other SET_DEST that has a MEM in it is referencing the MEM.  */
+      if (MEM_P (SET_DEST (x)))
+	{
+	  if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
+	    return 1;
+	}
+      else if (memref_referenced_p (memref, SET_DEST (x)))
+	return 1;
+
+      return memref_referenced_p (memref, SET_SRC (x));
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    switch (fmt[i])
+      {
+      case 'e':
+	if (memref_referenced_p (memref, XEXP (x, i)))
+	  return 1;
+	break;
+      case 'E':
+	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+	  if (memref_referenced_p (memref, XVECEXP (x, i, j)))
+	    return 1;
+	break;
+      }
+
+  return 0;
+}
+
+/* TRUE if some insn in the range (START, END] references a memory location
+   that would be affected by a store to MEMREF.  */
+static int
+memref_used_between_p (rtx memref, rtx start, rtx end)
+{
+  rtx insn;
+
+  for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
+       insn = NEXT_INSN (insn))
+    {
+      if (!INSN_P (insn))
+	continue;
+      
+      if (memref_referenced_p (memref, PATTERN (insn)))
+	return 1;
+
+      /* Nonconst functions may access memory.  */
+      if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
+	return 1;
+    }
+
+  return 0;
+}
+
+/* Mark REG as having no known equivalence.
+   Some instructions might have been processed before and furnished
+   with REG_EQUIV notes for this register; these notes will have to be
+   removed.
+   STORE is the piece of RTL that does the non-constant / conflicting
+   assignment - a SET, CLOBBER or REG_INC note.  It is currently not used,
+   but needs to be there because this function is called from note_stores.  */
+static void
+no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
+{
+  int regno;
+  rtx list;
+
+  if (!REG_P (reg))
+    return;
+  regno = REGNO (reg);
+  list = reg_equiv[regno].init_insns;
+  if (list == const0_rtx)
+    return;
+  reg_equiv[regno].init_insns = const0_rtx;
+  reg_equiv[regno].replacement = NULL_RTX;
+  /* This doesn't matter for equivalences made for argument registers, we
+     should keep their initialization insns.  */
+  if (reg_equiv[regno].is_arg_equivalence)
+    return;
+  reg_equiv_init[regno] = NULL_RTX;
+  for (; list; list =  XEXP (list, 1))
+    {
+      rtx insn = XEXP (list, 0);
+      remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
+    }
+}
+
+/* Nonzero if we recorded an equivalence for a LABEL_REF.  */
+static int recorded_label_ref;
+
+/* Find registers that are equivalent to a single value throughout the
+   compilation (either because they can be referenced in memory or are set once
+   from a single constant).  Lower their priority for a register.
+
+   If such a register is only referenced once, try substituting its value
+   into the using insn.  If it succeeds, we can eliminate the register
+   completely.
+
+   Initialize the REG_EQUIV_INIT array of initializing insns.
+
+   Return non-zero if jump label rebuilding should be done.  */
+static int
+update_equiv_regs (void)
+{
+  rtx insn;
+  basic_block bb;
+  int loop_depth;
+  bitmap cleared_regs;
+  
+  /* We need to keep track of whether or not we recorded a LABEL_REF so
+     that we know if the jump optimizer needs to be rerun.  */
+  recorded_label_ref = 0;
+
+  reg_equiv = XCNEWVEC (struct equivalence, max_regno);
+  reg_equiv_init = GGC_CNEWVEC (rtx, max_regno);
+  reg_equiv_init_size = max_regno;
+
+  init_alias_analysis ();
+
+  /* Scan the insns and find which registers have equivalences.  Do this
+     in a separate scan of the insns because (due to -fcse-follow-jumps)
+     a register can be set below its use.  */
+  FOR_EACH_BB (bb)
+    {
+      loop_depth = bb->loop_depth;
+
+      for (insn = BB_HEAD (bb);
+	   insn != NEXT_INSN (BB_END (bb));
+	   insn = NEXT_INSN (insn))
+	{
+	  rtx note;
+	  rtx set;
+	  rtx dest, src;
+	  int regno;
+
+	  if (! INSN_P (insn))
+	    continue;
+
+	  for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
+	    if (REG_NOTE_KIND (note) == REG_INC)
+	      no_equiv (XEXP (note, 0), note, NULL);
+
+	  set = single_set (insn);
+
+	  /* If this insn contains more (or less) than a single SET,
+	     only mark all destinations as having no known equivalence.  */
+	  if (set == 0)
+	    {
+	      note_stores (PATTERN (insn), no_equiv, NULL);
+	      continue;
+	    }
+	  else if (GET_CODE (PATTERN (insn)) == PARALLEL)
+	    {
+	      int i;
+
+	      for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
+		{
+		  rtx part = XVECEXP (PATTERN (insn), 0, i);
+		  if (part != set)
+		    note_stores (part, no_equiv, NULL);
+		}
+	    }
+
+	  dest = SET_DEST (set);
+	  src = SET_SRC (set);
+
+	  /* See if this is setting up the equivalence between an argument
+	     register and its stack slot.  */
+	  note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
+	  if (note)
+	    {
+	      gcc_assert (REG_P (dest));
+	      regno = REGNO (dest);
+
+	      /* Note that we don't want to clear reg_equiv_init even if there
+		 are multiple sets of this register.  */
+	      reg_equiv[regno].is_arg_equivalence = 1;
+
+	      /* Record for reload that this is an equivalencing insn.  */
+	      if (rtx_equal_p (src, XEXP (note, 0)))
+		reg_equiv_init[regno]
+		  = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
+
+	      /* Continue normally in case this is a candidate for
+		 replacements.  */
+	    }
+
+	  if (!optimize)
+	    continue;
+
+	  /* We only handle the case of a pseudo register being set
+	     once, or always to the same value.  */
+	  /* ??? The mn10200 port breaks if we add equivalences for
+	     values that need an ADDRESS_REGS register and set them equivalent
+	     to a MEM of a pseudo.  The actual problem is in the over-conservative
+	     handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
+	     calculate_needs, but we traditionally work around this problem
+	     here by rejecting equivalences when the destination is in a register
+	     that's likely spilled.  This is fragile, of course, since the
+	     preferred class of a pseudo depends on all instructions that set
+	     or use it.  */
+
+	  if (!REG_P (dest)
+	      || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
+	      || reg_equiv[regno].init_insns == const0_rtx
+	      || (CLASS_LIKELY_SPILLED_P (reg_preferred_class (regno))
+		  && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
+	    {
+	      /* This might be setting a SUBREG of a pseudo, a pseudo that is
+		 also set somewhere else to a constant.  */
+	      note_stores (set, no_equiv, NULL);
+	      continue;
+	    }
+
+	  note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
+
+	  /* cse sometimes generates function invariants, but doesn't put a
+	     REG_EQUAL note on the insn.  Since this note would be redundant,
+	     there's no point creating it earlier than here.  */
+	  if (! note && ! rtx_varies_p (src, 0))
+	    note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
+
+	  /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
+	     since it represents a function call */
+	  if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
+	    note = NULL_RTX;
+
+	  if (DF_REG_DEF_COUNT (regno) != 1
+	      && (! note
+		  || rtx_varies_p (XEXP (note, 0), 0)
+		  || (reg_equiv[regno].replacement
+		      && ! rtx_equal_p (XEXP (note, 0),
+					reg_equiv[regno].replacement))))
+	    {
+	      no_equiv (dest, set, NULL);
+	      continue;
+	    }
+	  /* Record this insn as initializing this register.  */
+	  reg_equiv[regno].init_insns
+	    = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
+
+	  /* If this register is known to be equal to a constant, record that
+	     it is always equivalent to the constant.  */
+	  if (DF_REG_DEF_COUNT (regno) == 1
+	      && note && ! rtx_varies_p (XEXP (note, 0), 0))
+	    {
+	      rtx note_value = XEXP (note, 0);
+	      remove_note (insn, note);
+	      set_unique_reg_note (insn, REG_EQUIV, note_value);
+	    }
+
+	  /* If this insn introduces a "constant" register, decrease the priority
+	     of that register.  Record this insn if the register is only used once
+	     more and the equivalence value is the same as our source.
+
+	     The latter condition is checked for two reasons:  First, it is an
+	     indication that it may be more efficient to actually emit the insn
+	     as written (if no registers are available, reload will substitute
+	     the equivalence).  Secondly, it avoids problems with any registers
+	     dying in this insn whose death notes would be missed.
+
+	     If we don't have a REG_EQUIV note, see if this insn is loading
+	     a register used only in one basic block from a MEM.  If so, and the
+	     MEM remains unchanged for the life of the register, add a REG_EQUIV
+	     note.  */
+
+	  note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
+
+	  if (note == 0 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
+	      && MEM_P (SET_SRC (set))
+	      && validate_equiv_mem (insn, dest, SET_SRC (set)))
+	    note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
+
+	  if (note)
+	    {
+	      int regno = REGNO (dest);
+	      rtx x = XEXP (note, 0);
+
+	      /* If we haven't done so, record for reload that this is an
+		 equivalencing insn.  */
+	      if (!reg_equiv[regno].is_arg_equivalence)
+		reg_equiv_init[regno]
+		  = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
+
+	      /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
+		 We might end up substituting the LABEL_REF for uses of the
+		 pseudo here or later.  That kind of transformation may turn an
+		 indirect jump into a direct jump, in which case we must rerun the
+		 jump optimizer to ensure that the JUMP_LABEL fields are valid.  */
+	      if (GET_CODE (x) == LABEL_REF
+		  || (GET_CODE (x) == CONST
+		      && GET_CODE (XEXP (x, 0)) == PLUS
+		      && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
+		recorded_label_ref = 1;
+
+	      reg_equiv[regno].replacement = x;
+	      reg_equiv[regno].src_p = &SET_SRC (set);
+	      reg_equiv[regno].loop_depth = loop_depth;
+
+	      /* Don't mess with things live during setjmp.  */
+	      if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
+		{
+		  /* Note that the statement below does not affect the priority
+		     in local-alloc!  */
+		  REG_LIVE_LENGTH (regno) *= 2;
+
+		  /* If the register is referenced exactly twice, meaning it is
+		     set once and used once, indicate that the reference may be
+		     replaced by the equivalence we computed above.  Do this
+		     even if the register is only used in one block so that
+		     dependencies can be handled where the last register is
+		     used in a different block (i.e. HIGH / LO_SUM sequences)
+		     and to reduce the number of registers alive across
+		     calls.  */
+
+		  if (REG_N_REFS (regno) == 2
+		      && (rtx_equal_p (x, src)
+			  || ! equiv_init_varies_p (src))
+		      && NONJUMP_INSN_P (insn)
+		      && equiv_init_movable_p (PATTERN (insn), regno))
+		    reg_equiv[regno].replace = 1;
+		}
+	    }
+	}
+    }
+
+  if (!optimize)
+    goto out;
+
+  /* A second pass, to gather additional equivalences with memory.  This needs
+     to be done after we know which registers we are going to replace.  */
+
+  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+    {
+      rtx set, src, dest;
+      unsigned regno;
+
+      if (! INSN_P (insn))
+	continue;
+
+      set = single_set (insn);
+      if (! set)
+	continue;
+
+      dest = SET_DEST (set);
+      src = SET_SRC (set);
+
+      /* If this sets a MEM to the contents of a REG that is only used
+	 in a single basic block, see if the register is always equivalent
+	 to that memory location and if moving the store from INSN to the
+	 insn that set REG is safe.  If so, put a REG_EQUIV note on the
+	 initializing insn.
+
+	 Don't add a REG_EQUIV note if the insn already has one.  The existing
+	 REG_EQUIV is likely more useful than the one we are adding.
+
+	 If one of the regs in the address has reg_equiv[REGNO].replace set,
+	 then we can't add this REG_EQUIV note.  The reg_equiv[REGNO].replace
+	 optimization may move the set of this register immediately before
+	 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
+	 the mention in the REG_EQUIV note would be to an uninitialized
+	 pseudo.  */
+
+      if (MEM_P (dest) && REG_P (src)
+	  && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
+	  && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
+	  && DF_REG_DEF_COUNT (regno) == 1
+	  && reg_equiv[regno].init_insns != 0
+	  && reg_equiv[regno].init_insns != const0_rtx
+	  && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
+			      REG_EQUIV, NULL_RTX)
+	  && ! contains_replace_regs (XEXP (dest, 0)))
+	{
+	  rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
+	  if (validate_equiv_mem (init_insn, src, dest)
+	      && ! memref_used_between_p (dest, init_insn, insn)
+	      /* Attaching a REG_EQUIV note will fail if INIT_INSN has
+		 multiple sets.  */
+	      && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
+	    {
+	      /* This insn makes the equivalence, not the one initializing
+		 the register.  */
+	      reg_equiv_init[regno]
+		= gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
+	      df_notes_rescan (init_insn);
+	    }
+	}
+    }
+
+  cleared_regs = BITMAP_ALLOC (NULL);
+  /* Now scan all regs killed in an insn to see if any of them are
+     registers only used that once.  If so, see if we can replace the
+     reference with the equivalent form.  If we can, delete the
+     initializing reference and this register will go away.  If we
+     can't replace the reference, and the initializing reference is
+     within the same loop (or in an inner loop), then move the register
+     initialization just before the use, so that they are in the same
+     basic block.  */
+  FOR_EACH_BB_REVERSE (bb)
+    {
+      loop_depth = bb->loop_depth;
+      for (insn = BB_END (bb);
+	   insn != PREV_INSN (BB_HEAD (bb));
+	   insn = PREV_INSN (insn))
+	{
+	  rtx link;
+
+	  if (! INSN_P (insn))
+	    continue;
+
+	  /* Don't substitute into a non-local goto, this confuses CFG.  */
+	  if (JUMP_P (insn)
+	      && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
+	    continue;
+
+	  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+	    {
+	      if (REG_NOTE_KIND (link) == REG_DEAD
+		  /* Make sure this insn still refers to the register.  */
+		  && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
+		{
+		  int regno = REGNO (XEXP (link, 0));
+		  rtx equiv_insn;
+
+		  if (! reg_equiv[regno].replace
+		      || reg_equiv[regno].loop_depth < loop_depth)
+		    continue;
+
+		  /* reg_equiv[REGNO].replace gets set only when
+		     REG_N_REFS[REGNO] is 2, i.e. the register is set
+		     once and used once.  (If it were only set, but not used,
+		     flow would have deleted the setting insns.)  Hence
+		     there can only be one insn in reg_equiv[REGNO].init_insns.  */
+		  gcc_assert (reg_equiv[regno].init_insns
+			      && !XEXP (reg_equiv[regno].init_insns, 1));
+		  equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
+
+		  /* We may not move instructions that can throw, since
+		     that changes basic block boundaries and we are not
+		     prepared to adjust the CFG to match.  */
+		  if (can_throw_internal (equiv_insn))
+		    continue;
+
+		  if (asm_noperands (PATTERN (equiv_insn)) < 0
+		      && validate_replace_rtx (regno_reg_rtx[regno],
+					       *(reg_equiv[regno].src_p), insn))
+		    {
+		      rtx equiv_link;
+		      rtx last_link;
+		      rtx note;
+
+		      /* Find the last note.  */
+		      for (last_link = link; XEXP (last_link, 1);
+			   last_link = XEXP (last_link, 1))
+			;
+
+		      /* Append the REG_DEAD notes from equiv_insn.  */
+		      equiv_link = REG_NOTES (equiv_insn);
+		      while (equiv_link)
+			{
+			  note = equiv_link;
+			  equiv_link = XEXP (equiv_link, 1);
+			  if (REG_NOTE_KIND (note) == REG_DEAD)
+			    {
+			      remove_note (equiv_insn, note);
+			      XEXP (last_link, 1) = note;
+			      XEXP (note, 1) = NULL_RTX;
+			      last_link = note;
+			    }
+			}
+
+		      remove_death (regno, insn);
+		      SET_REG_N_REFS (regno, 0);
+		      REG_FREQ (regno) = 0;
+		      delete_insn (equiv_insn);
+
+		      reg_equiv[regno].init_insns
+			= XEXP (reg_equiv[regno].init_insns, 1);
+
+		      reg_equiv_init[regno] = NULL_RTX;
+		      bitmap_set_bit (cleared_regs, regno);
+		    }
+		  /* Move the initialization of the register to just before
+		     INSN.  Update the flow information.  */
+		  else if (PREV_INSN (insn) != equiv_insn)
+		    {
+		      rtx new_insn;
+
+		      new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
+		      REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
+		      REG_NOTES (equiv_insn) = 0;
+		      /* Rescan it to process the notes.  */
+		      df_insn_rescan (new_insn);
+
+		      /* Make sure this insn is recognized before
+			 reload begins, otherwise
+			 eliminate_regs_in_insn will die.  */
+		      INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
+
+		      delete_insn (equiv_insn);
+
+		      XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
+
+		      REG_BASIC_BLOCK (regno) = bb->index;
+		      REG_N_CALLS_CROSSED (regno) = 0;
+		      REG_FREQ_CALLS_CROSSED (regno) = 0;
+		      REG_N_THROWING_CALLS_CROSSED (regno) = 0;
+		      REG_LIVE_LENGTH (regno) = 2;
+
+		      if (insn == BB_HEAD (bb))
+			BB_HEAD (bb) = PREV_INSN (insn);
+
+		      reg_equiv_init[regno]
+			= gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
+		      bitmap_set_bit (cleared_regs, regno);
+		    }
+		}
+	    }
+	}
+    }
+
+  if (!bitmap_empty_p (cleared_regs))
+    FOR_EACH_BB (bb)
+      {
+	bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
+	bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
+	bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
+	bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
+      }
+
+  BITMAP_FREE (cleared_regs);
+
+  out:
+  /* Clean up.  */
+
+  end_alias_analysis ();
+  free (reg_equiv);
+  return recorded_label_ref;
+}
+
+
+
+/* Print chain C to FILE.  */
+static void
+print_insn_chain (FILE *file, struct insn_chain *c)
+{
+  fprintf (file, "insn=%d, ", INSN_UID(c->insn));
+  bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
+  bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
+}
+
+
+/* Print all reload_insn_chains to FILE.  */
+static void
+print_insn_chains (FILE *file)
+{
+  struct insn_chain *c;
+  for (c = reload_insn_chain; c ; c = c->next)
+    print_insn_chain (file, c);
+}
+
+/* Return true if pseudo REGNO should be added to set live_throughout
+   or dead_or_set of the insn chains for reload consideration.  */
+static bool
+pseudo_for_reload_consideration_p (int regno)
+{
+  /* Consider spilled pseudos too for IRA because they still have a
+     chance to get hard-registers in the reload when IRA is used.  */
+  return (reg_renumber[regno] >= 0
+	  || (ira_conflicts_p && flag_ira_share_spill_slots));
+}
+
+/* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
+   REG to the number of nregs, and INIT_VALUE to get the
+   initialization.  ALLOCNUM need not be the regno of REG.  */
+static void
+init_live_subregs (bool init_value, sbitmap *live_subregs,
+		   int *live_subregs_used, int allocnum, rtx reg)
+{
+  unsigned int regno = REGNO (SUBREG_REG (reg));
+  int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
+
+  gcc_assert (size > 0);
+
+  /* Been there, done that.  */
+  if (live_subregs_used[allocnum])
+    return;
+
+  /* Create a new one with zeros.  */
+  if (live_subregs[allocnum] == NULL)
+    live_subregs[allocnum] = sbitmap_alloc (size);
+
+  /* If the entire reg was live before blasting into subregs, we need
+     to init all of the subregs to ones else init to 0.  */
+  if (init_value)
+    sbitmap_ones (live_subregs[allocnum]);
+  else 
+    sbitmap_zero (live_subregs[allocnum]);
+
+  /* Set the number of bits that we really want.  */
+  live_subregs_used[allocnum] = size;
+}
+
+/* Walk the insns of the current function and build reload_insn_chain,
+   and record register life information.  */
+static void
+build_insn_chain (void)
+{
+  unsigned int i;
+  struct insn_chain **p = &reload_insn_chain;
+  basic_block bb;
+  struct insn_chain *c = NULL;
+  struct insn_chain *next = NULL;
+  bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
+  bitmap elim_regset = BITMAP_ALLOC (NULL);
+  /* live_subregs is a vector used to keep accurate information about
+     which hardregs are live in multiword pseudos.  live_subregs and
+     live_subregs_used are indexed by pseudo number.  The live_subreg
+     entry for a particular pseudo is only used if the corresponding
+     element is non zero in live_subregs_used.  The value in
+     live_subregs_used is number of bytes that the pseudo can
+     occupy.  */
+  sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
+  int *live_subregs_used = XNEWVEC (int, max_regno);
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    if (TEST_HARD_REG_BIT (eliminable_regset, i))
+      bitmap_set_bit (elim_regset, i);
+  FOR_EACH_BB_REVERSE (bb)
+    {
+      bitmap_iterator bi;
+      rtx insn;
+      
+      CLEAR_REG_SET (live_relevant_regs);
+      memset (live_subregs_used, 0, max_regno * sizeof (int));
+      
+      EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
+	{
+	  if (i >= FIRST_PSEUDO_REGISTER)
+	    break;
+	  bitmap_set_bit (live_relevant_regs, i);
+	}
+
+      EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb),
+				FIRST_PSEUDO_REGISTER, i, bi)
+	{
+	  if (pseudo_for_reload_consideration_p (i))
+	    bitmap_set_bit (live_relevant_regs, i);
+	}
+
+      FOR_BB_INSNS_REVERSE (bb, insn)
+	{
+	  if (!NOTE_P (insn) && !BARRIER_P (insn))
+	    {
+	      unsigned int uid = INSN_UID (insn);
+	      df_ref *def_rec;
+	      df_ref *use_rec;
+
+	      c = new_insn_chain ();
+	      c->next = next;
+	      next = c;
+	      *p = c;
+	      p = &c->prev;
+	      
+	      c->insn = insn;
+	      c->block = bb->index;
+
+	      if (INSN_P (insn))
+		for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+		  {
+		    df_ref def = *def_rec;
+		    unsigned int regno = DF_REF_REGNO (def);
+		    
+		    /* Ignore may clobbers because these are generated
+		       from calls. However, every other kind of def is
+		       added to dead_or_set.  */
+		    if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
+		      {
+			if (regno < FIRST_PSEUDO_REGISTER)
+			  {
+			    if (!fixed_regs[regno])
+			      bitmap_set_bit (&c->dead_or_set, regno);
+			  }
+			else if (pseudo_for_reload_consideration_p (regno))
+			  bitmap_set_bit (&c->dead_or_set, regno);
+		      }
+
+		    if ((regno < FIRST_PSEUDO_REGISTER
+			 || reg_renumber[regno] >= 0
+			 || ira_conflicts_p)
+			&& (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
+		      {
+			rtx reg = DF_REF_REG (def);
+
+			/* We can model subregs, but not if they are
+			   wrapped in ZERO_EXTRACTS.  */
+			if (GET_CODE (reg) == SUBREG
+			    && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
+			  {
+			    unsigned int start = SUBREG_BYTE (reg);
+			    unsigned int last = start 
+			      + GET_MODE_SIZE (GET_MODE (reg));
+
+			    init_live_subregs
+			      (bitmap_bit_p (live_relevant_regs, regno), 
+			       live_subregs, live_subregs_used, regno, reg);
+
+			    if (!DF_REF_FLAGS_IS_SET
+				(def, DF_REF_STRICT_LOW_PART))
+			      {
+				/* Expand the range to cover entire words.
+				   Bytes added here are "don't care".  */
+				start
+				  = start / UNITS_PER_WORD * UNITS_PER_WORD;
+				last = ((last + UNITS_PER_WORD - 1)
+					/ UNITS_PER_WORD * UNITS_PER_WORD);
+			      }
+
+			    /* Ignore the paradoxical bits.  */
+			    if ((int)last > live_subregs_used[regno])
+			      last = live_subregs_used[regno];
+
+			    while (start < last)
+			      {
+				RESET_BIT (live_subregs[regno], start);
+				start++;
+			      }
+			    
+			    if (sbitmap_empty_p (live_subregs[regno]))
+			      {
+				live_subregs_used[regno] = 0;
+				bitmap_clear_bit (live_relevant_regs, regno);
+			      }
+			    else
+			      /* Set live_relevant_regs here because
+				 that bit has to be true to get us to
+				 look at the live_subregs fields.  */
+			      bitmap_set_bit (live_relevant_regs, regno);
+			  }
+			else
+			  {
+			    /* DF_REF_PARTIAL is generated for
+			       subregs, STRICT_LOW_PART, and
+			       ZERO_EXTRACT.  We handle the subreg
+			       case above so here we have to keep from
+			       modeling the def as a killing def.  */
+			    if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
+			      {
+				bitmap_clear_bit (live_relevant_regs, regno);
+				live_subregs_used[regno] = 0;
+			      }
+			  }
+		      }
+		  }
+	  
+	      bitmap_and_compl_into (live_relevant_regs, elim_regset);
+	      bitmap_copy (&c->live_throughout, live_relevant_regs);
+
+	      if (INSN_P (insn))
+		for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+		  {
+		    df_ref use = *use_rec;
+		    unsigned int regno = DF_REF_REGNO (use);
+		    rtx reg = DF_REF_REG (use);
+		    
+		    /* DF_REF_READ_WRITE on a use means that this use
+		       is fabricated from a def that is a partial set
+		       to a multiword reg.  Here, we only model the
+		       subreg case that is not wrapped in ZERO_EXTRACT
+		       precisely so we do not need to look at the
+		       fabricated use. */
+		    if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE) 
+			&& !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT) 
+			&& DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
+		      continue;
+		    
+		    /* Add the last use of each var to dead_or_set.  */
+		    if (!bitmap_bit_p (live_relevant_regs, regno))
+		      {
+			if (regno < FIRST_PSEUDO_REGISTER)
+			  {
+			    if (!fixed_regs[regno])
+			      bitmap_set_bit (&c->dead_or_set, regno);
+			  }
+			else if (pseudo_for_reload_consideration_p (regno))
+			  bitmap_set_bit (&c->dead_or_set, regno);
+		      }
+		    
+		    if (regno < FIRST_PSEUDO_REGISTER
+			|| pseudo_for_reload_consideration_p (regno))
+		      {
+			if (GET_CODE (reg) == SUBREG
+			    && !DF_REF_FLAGS_IS_SET (use,
+						     DF_REF_SIGN_EXTRACT
+						     | DF_REF_ZERO_EXTRACT)) 
+			  {
+			    unsigned int start = SUBREG_BYTE (reg);
+			    unsigned int last = start 
+			      + GET_MODE_SIZE (GET_MODE (reg));
+			    
+			    init_live_subregs
+			      (bitmap_bit_p (live_relevant_regs, regno), 
+			       live_subregs, live_subregs_used, regno, reg);
+			    
+			    /* Ignore the paradoxical bits.  */
+			    if ((int)last > live_subregs_used[regno])
+			      last = live_subregs_used[regno];
+
+			    while (start < last)
+			      {
+				SET_BIT (live_subregs[regno], start);
+				start++;
+			      }
+			  }
+			else
+			  /* Resetting the live_subregs_used is
+			     effectively saying do not use the subregs
+			     because we are reading the whole
+			     pseudo.  */
+			  live_subregs_used[regno] = 0;
+			bitmap_set_bit (live_relevant_regs, regno);
+		      }
+		  }
+	    }
+	}
+
+      /* FIXME!! The following code is a disaster.  Reload needs to see the
+	 labels and jump tables that are just hanging out in between
+	 the basic blocks.  See pr33676.  */
+      insn = BB_HEAD (bb);
+      
+      /* Skip over the barriers and cruft.  */
+      while (insn && (BARRIER_P (insn) || NOTE_P (insn) 
+		      || BLOCK_FOR_INSN (insn) == bb))
+	insn = PREV_INSN (insn);
+      
+      /* While we add anything except barriers and notes, the focus is
+	 to get the labels and jump tables into the
+	 reload_insn_chain.  */
+      while (insn)
+	{
+	  if (!NOTE_P (insn) && !BARRIER_P (insn))
+	    {
+	      if (BLOCK_FOR_INSN (insn))
+		break;
+	      
+	      c = new_insn_chain ();
+	      c->next = next;
+	      next = c;
+	      *p = c;
+	      p = &c->prev;
+	      
+	      /* The block makes no sense here, but it is what the old
+		 code did.  */
+	      c->block = bb->index;
+	      c->insn = insn;
+	      bitmap_copy (&c->live_throughout, live_relevant_regs);
+	    }	  
+	  insn = PREV_INSN (insn);
+	}
+    }
+
+  for (i = 0; i < (unsigned int) max_regno; i++)
+    if (live_subregs[i])
+      free (live_subregs[i]);
+
+  reload_insn_chain = c;
+  *p = NULL;
+
+  free (live_subregs);
+  free (live_subregs_used);
+  BITMAP_FREE (live_relevant_regs);
+  BITMAP_FREE (elim_regset);
+
+  if (dump_file)
+    print_insn_chains (dump_file);
+}
+
+
+
+/* All natural loops.  */
+struct loops ira_loops;
+
+/* True if we have allocno conflicts.  It is false for non-optimized
+   mode or when the conflict table is too big.  */
+bool ira_conflicts_p;
+
+/* This is the main entry of IRA.  */
+static void
+ira (FILE *f)
+{
+  int overall_cost_before, allocated_reg_info_size;
+  bool loops_p;
+  int max_regno_before_ira, ira_max_point_before_emit;
+  int rebuild_p;
+  int saved_flag_ira_share_spill_slots;
+  basic_block bb;
+
+  timevar_push (TV_IRA);
+
+  if (flag_ira_verbose < 10)
+    {
+      internal_flag_ira_verbose = flag_ira_verbose;
+      ira_dump_file = f;
+    }
+  else
+    {
+      internal_flag_ira_verbose = flag_ira_verbose - 10;
+      ira_dump_file = stderr;
+    }
+
+  ira_conflicts_p = optimize > 0;
+  setup_prohibited_mode_move_regs ();
+
+  df_note_add_problem ();
+
+  if (optimize == 1)
+    {
+      df_live_add_problem ();
+      df_live_set_all_dirty ();
+    }
+#ifdef ENABLE_CHECKING
+  df->changeable_flags |= DF_VERIFY_SCHEDULED;
+#endif
+  df_analyze ();
+  df_clear_flags (DF_NO_INSN_RESCAN);
+  regstat_init_n_sets_and_refs ();
+  regstat_compute_ri ();
+
+  /* If we are not optimizing, then this is the only place before
+     register allocation where dataflow is done.  And that is needed
+     to generate these warnings.  */
+  if (warn_clobbered)
+    generate_setjmp_warnings ();
+
+  /* Determine if the current function is a leaf before running IRA
+     since this can impact optimizations done by the prologue and
+     epilogue thus changing register elimination offsets.  */
+  current_function_is_leaf = leaf_function_p ();
+
+  rebuild_p = update_equiv_regs ();
+
+#ifndef IRA_NO_OBSTACK
+  gcc_obstack_init (&ira_obstack);
+#endif
+  bitmap_obstack_initialize (&ira_bitmap_obstack);
+  if (optimize)
+    {      
+      max_regno = max_reg_num ();
+      ira_reg_equiv_len = max_regno;
+      ira_reg_equiv_invariant_p
+	= (bool *) ira_allocate (max_regno * sizeof (bool));
+      memset (ira_reg_equiv_invariant_p, 0, max_regno * sizeof (bool));
+      ira_reg_equiv_const = (rtx *) ira_allocate (max_regno * sizeof (rtx));
+      memset (ira_reg_equiv_const, 0, max_regno * sizeof (rtx));
+      find_reg_equiv_invariant_const ();
+      if (rebuild_p)
+	{
+	  timevar_push (TV_JUMP);
+	  rebuild_jump_labels (get_insns ());
+	  purge_all_dead_edges ();
+	  timevar_pop (TV_JUMP);
+	}
+    }
+
+  max_regno_before_ira = allocated_reg_info_size = max_reg_num ();
+  allocate_reg_info ();
+  setup_eliminable_regset ();
+      
+  ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
+  ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
+  ira_move_loops_num = ira_additional_jumps_num = 0;
+  
+  ira_assert (current_loops == NULL);
+  flow_loops_find (&ira_loops);
+  current_loops = &ira_loops;
+      
+  if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
+    fprintf (ira_dump_file, "Building IRA IR\n");
+  loops_p = ira_build (optimize
+		       && (flag_ira_region == IRA_REGION_ALL
+			   || flag_ira_region == IRA_REGION_MIXED));
+  
+  ira_assert (ira_conflicts_p || !loops_p);
+
+  saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
+  if (too_high_register_pressure_p ())
+    /* It is just wasting compiler's time to pack spilled pseudos into
+       stack slots in this case -- prohibit it.  */ 
+    flag_ira_share_spill_slots = FALSE;
+
+  ira_color ();
+      
+  ira_max_point_before_emit = ira_max_point;
+      
+  ira_emit (loops_p);
+  
+  if (ira_conflicts_p)
+    {
+      max_regno = max_reg_num ();
+      
+      if (! loops_p)
+	ira_initiate_assign ();
+      else
+	{
+	  expand_reg_info (allocated_reg_info_size);
+	  setup_preferred_alternate_classes_for_new_pseudos
+	    (allocated_reg_info_size);
+	  allocated_reg_info_size = max_regno;
+	  
+	  if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
+	    fprintf (ira_dump_file, "Flattening IR\n");
+	  ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
+	  /* New insns were generated: add notes and recalculate live
+	     info.  */
+	  df_analyze ();
+	  
+	  flow_loops_find (&ira_loops);
+	  current_loops = &ira_loops;
+
+	  setup_allocno_assignment_flags ();
+	  ira_initiate_assign ();
+	  ira_reassign_conflict_allocnos (max_regno);
+	}
+    }
+
+  setup_reg_renumber ();
+  
+  calculate_allocation_cost ();
+  
+#ifdef ENABLE_IRA_CHECKING
+  if (ira_conflicts_p)
+    check_allocation ();
+#endif
+      
+  delete_trivially_dead_insns (get_insns (), max_reg_num ());
+  max_regno = max_reg_num ();
+  
+  /* And the reg_equiv_memory_loc array.  */
+  VEC_safe_grow (rtx, gc, reg_equiv_memory_loc_vec, max_regno);
+  memset (VEC_address (rtx, reg_equiv_memory_loc_vec), 0,
+	  sizeof (rtx) * max_regno);
+  reg_equiv_memory_loc = VEC_address (rtx, reg_equiv_memory_loc_vec);
+
+  if (max_regno != max_regno_before_ira)
+    {
+      regstat_free_n_sets_and_refs ();
+      regstat_free_ri ();
+      regstat_init_n_sets_and_refs ();
+      regstat_compute_ri ();
+    }
+
+  allocate_initial_values (reg_equiv_memory_loc);
+
+  overall_cost_before = ira_overall_cost;
+  if (ira_conflicts_p)
+    {
+      fix_reg_equiv_init ();
+      
+#ifdef ENABLE_IRA_CHECKING
+      print_redundant_copies ();
+#endif
+
+      ira_spilled_reg_stack_slots_num = 0;
+      ira_spilled_reg_stack_slots
+	= ((struct ira_spilled_reg_stack_slot *)
+	   ira_allocate (max_regno
+			 * sizeof (struct ira_spilled_reg_stack_slot)));
+      memset (ira_spilled_reg_stack_slots, 0,
+	      max_regno * sizeof (struct ira_spilled_reg_stack_slot));
+    }
+  
+  timevar_pop (TV_IRA);
+
+  timevar_push (TV_RELOAD);
+  df_set_flags (DF_NO_INSN_RESCAN);
+  build_insn_chain ();
+
+  reload_completed = !reload (get_insns (), ira_conflicts_p);
+
+  timevar_pop (TV_RELOAD);
+
+  timevar_push (TV_IRA);
+
+  if (ira_conflicts_p)
+    {
+      ira_free (ira_spilled_reg_stack_slots);
+      
+      ira_finish_assign ();
+      
+    }  
+  if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
+      && overall_cost_before != ira_overall_cost)
+    fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
+  ira_destroy ();
+  
+  flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
+
+  flow_loops_free (&ira_loops);
+  free_dominance_info (CDI_DOMINATORS);
+  FOR_ALL_BB (bb)
+    bb->loop_father = NULL;
+  current_loops = NULL;
+
+  regstat_free_ri ();
+  regstat_free_n_sets_and_refs ();
+      
+  if (optimize)
+    {
+      cleanup_cfg (CLEANUP_EXPENSIVE);
+      
+      ira_free (ira_reg_equiv_invariant_p);
+      ira_free (ira_reg_equiv_const);
+    }
+
+  bitmap_obstack_release (&ira_bitmap_obstack);
+#ifndef IRA_NO_OBSTACK
+  obstack_free (&ira_obstack, NULL);
+#endif
+
+  /* The code after the reload has changed so much that at this point
+     we might as well just rescan everything.  Not that
+     df_rescan_all_insns is not going to help here because it does not
+     touch the artificial uses and defs.  */
+  df_finish_pass (true);
+  if (optimize > 1)
+    df_live_add_problem ();
+  df_scan_alloc (NULL);
+  df_scan_blocks ();
+
+  if (optimize)
+    df_analyze ();
+
+  timevar_pop (TV_IRA);
+}
+
+
+
+static bool
+gate_ira (void)
+{
+  return true;
+}
+
+/* Run the integrated register allocator.  */
+static unsigned int
+rest_of_handle_ira (void)
+{
+  ira (dump_file);
+  return 0;
+}
+
+struct rtl_opt_pass pass_ira =
+{
+ {
+  RTL_PASS,
+  "ira",                                /* name */
+  gate_ira,                             /* gate */
+  rest_of_handle_ira,		        /* execute */
+  NULL,                                 /* sub */
+  NULL,                                 /* next */
+  0,                                    /* static_pass_number */
+  0,		                        /* tv_id */
+  0,                                    /* properties_required */
+  0,                                    /* properties_provided */
+  0,                                    /* properties_destroyed */
+  0,                                    /* todo_flags_start */
+  TODO_dump_func |
+  TODO_ggc_collect                      /* todo_flags_finish */
+ }
+};