For Marcus - Implement sync primitives inline for ARM.

[pf3gnuchains/gcc-fork.git] / gcc / df-problems.c

diff --git a/gcc/df-problems.c b/gcc/df-problems.c
index b3ae9a1..e18ffe3 100644 (file)
--- a/gcc/df-problems.c
+++ b/gcc/df-problems.c
@@ -1,7 +1,7 @@
 /* Standard problems for dataflow support routines.
 /* Standard problems for dataflow support routines.

-   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
-   Free Software Foundation, Inc.
-   Originally contributed by Michael P. Hayes 
+   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
+   2008, 2009, 2010 Free Software Foundation, Inc.
+   Originally contributed by Michael P. Hayes

              (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
    Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
              and Kenneth Zadeck (zadeck@naturalbridge.com).
              (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
    Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
              and Kenneth Zadeck (zadeck@naturalbridge.com).


@@ -47,15 +47,15 @@ along with GCC; see the file COPYING3.  If not see
 
 /* Note that turning REG_DEAD_DEBUGGING on will cause
    gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
 
 /* Note that turning REG_DEAD_DEBUGGING on will cause
    gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints

-   addresses in the dumps.  */  
+   addresses in the dumps.  */

 #if 0
 #define REG_DEAD_DEBUGGING
 #endif
 
 #define DF_SPARSE_THRESHOLD 32
 
 #if 0
 #define REG_DEAD_DEBUGGING
 #endif
 
 #define DF_SPARSE_THRESHOLD 32
 

-static bitmap seen_in_block = NULL;
-static bitmap seen_in_insn = NULL;
+static bitmap_head seen_in_block;
+static bitmap_head seen_in_insn;

 
 \f
 /*----------------------------------------------------------------------------
 
 \f
 /*----------------------------------------------------------------------------


@@ -71,11 +71,9 @@ df_get_live_out (basic_block bb)
 {
   gcc_assert (df_lr);
 
 {
   gcc_assert (df_lr);
 

-  if (df_urec)
-    return DF_RA_LIVE_OUT (bb);
-  else if (df_live)
+  if (df_live)

     return DF_LIVE_OUT (bb);
     return DF_LIVE_OUT (bb);

-  else 
+  else

     return DF_LR_OUT (bb);
 }
 
     return DF_LR_OUT (bb);
 }
 


@@ -89,31 +87,12 @@ df_get_live_in (basic_block bb)
 {
   gcc_assert (df_lr);
 
 {
   gcc_assert (df_lr);
 

-  if (df_urec)
-    return DF_RA_LIVE_IN (bb);
-  else if (df_live)
+  if (df_live)

     return DF_LIVE_IN (bb);
     return DF_LIVE_IN (bb);

-  else 
+  else

     return DF_LR_IN (bb);
 }
 
     return DF_LR_IN (bb);
 }
 

-/* Get the live at top set for BB no matter what problem happens to be
-   defined.  This function is used by the register allocators who
-   choose different dataflow problems depending on the optimization
-   level.  */
-
-bitmap
-df_get_live_top (basic_block bb)
-{
-  gcc_assert (df_lr);
-
-  if (df_urec)
-    return DF_RA_LIVE_TOP (bb);
-  else 
-    return DF_LR_TOP (bb);
-}
-
-

 /*----------------------------------------------------------------------------
    Utility functions.
 ----------------------------------------------------------------------------*/
 /*----------------------------------------------------------------------------
    Utility functions.
 ----------------------------------------------------------------------------*/


@@ -121,23 +100,6 @@ df_get_live_top (basic_block bb)
 /* Generic versions to get the void* version of the block info.  Only
    used inside the problem instance vectors.  */
 
 /* Generic versions to get the void* version of the block info.  Only
    used inside the problem instance vectors.  */
 

-/* Grow the bb_info array.  */
-
-void
-df_grow_bb_info (struct dataflow *dflow)
-{
-  unsigned int new_size = last_basic_block + 1;
-  if (dflow->block_info_size < new_size)
-    {
-      new_size += new_size / 4;
-      dflow->block_info = xrealloc (dflow->block_info, 
-                                   new_size *sizeof (void*));
-      memset (dflow->block_info + dflow->block_info_size, 0,
-             (new_size - dflow->block_info_size) *sizeof (void *));
-      dflow->block_info_size = new_size;
-    }
-}
-

 /* Dump a def-use or use-def chain for REF to FILE.  */
 
 void
 /* Dump a def-use or use-def chain for REF to FILE.  */
 
 void


@@ -150,7 +112,7 @@ df_chain_dump (struct df_link *link, FILE *file)
               DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
               DF_REF_ID (link->ref),
               DF_REF_BBNO (link->ref),
               DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
               DF_REF_ID (link->ref),
               DF_REF_BBNO (link->ref),

-              DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
+              DF_REF_IS_ARTIFICIAL (link->ref) ? -1 : DF_REF_INSN_UID (link->ref));

     }
   fprintf (file, "}");
 }
     }
   fprintf (file, "}");
 }


@@ -158,7 +120,7 @@ df_chain_dump (struct df_link *link, FILE *file)
 
 /* Print some basic block info as part of df_dump.  */
 
 
 /* Print some basic block info as part of df_dump.  */
 

-void 
+void

 df_print_bb_index (basic_block bb, FILE *file)
 {
   edge e;
 df_print_bb_index (basic_block bb, FILE *file)
 {
   edge e;


@@ -169,57 +131,36 @@ df_print_bb_index (basic_block bb, FILE *file)
     {
       basic_block pred = e->src;
       fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
     {
       basic_block pred = e->src;
       fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");

-    } 
+    }

   fprintf (file, ")->[%d]->( ", bb->index);
   FOR_EACH_EDGE (e, ei, bb->succs)
     {
       basic_block succ = e->dest;
       fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
   fprintf (file, ")->[%d]->( ", bb->index);
   FOR_EACH_EDGE (e, ei, bb->succs)
     {
       basic_block succ = e->dest;
       fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");

-    } 
+    }

   fprintf (file, ")\n");
 }
 
   fprintf (file, ")\n");
 }
 

-
-
-/* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
-   up correctly. */
-
-static void
-df_set_seen (void)
-{
-  seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
-  seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
-}
-
-
-static void
-df_unset_seen (void)
-{
-  BITMAP_FREE (seen_in_block);
-  BITMAP_FREE (seen_in_insn);
-}
-
-

 \f
 /*----------------------------------------------------------------------------
 \f
 /*----------------------------------------------------------------------------

-   REACHING USES
+   REACHING DEFINITIONS

 
 

-   Find the locations in the function where each use site for a pseudo
-   can reach backwards.  In and out bitvectors are built for each basic
+   Find the locations in the function where each definition site for a
+   pseudo reaches.  In and out bitvectors are built for each basic

    block.  The id field in the ref is used to index into these sets.
    See df.h for details.
    block.  The id field in the ref is used to index into these sets.
    See df.h for details.

-
-----------------------------------------------------------------------------*/
+   ----------------------------------------------------------------------------*/

 
 /* This problem plays a large number of games for the sake of
 
 /* This problem plays a large number of games for the sake of

-   efficiency.  
-   
+   efficiency.
+

    1) The order of the bits in the bitvectors.  After the scanning
    1) The order of the bits in the bitvectors.  After the scanning

-   phase, all of the uses are sorted.  All of the uses for the reg 0
-   are first, followed by all uses for reg 1 and so on.
-   
-   2) There are two kill sets, one if the number of uses is less or
-   equal to DF_SPARSE_THRESHOLD and another if it is greater.
+   phase, all of the defs are sorted.  All of the defs for the reg 0
+   are first, followed by all defs for reg 1 and so on.
+
+   2) There are two kill sets, one if the number of defs is less or
+   equal to DF_SPARSE_THRESHOLD and another if the number of defs is
+   greater.

 
    <= : Data is built directly in the kill set.
 
 
    <= : Data is built directly in the kill set.
 


@@ -235,358 +176,392 @@ df_unset_seen (void)
 
 /* Private data used to compute the solution for this problem.  These
    data structures are not accessible outside of this module.  */
 
 /* Private data used to compute the solution for this problem.  These
    data structures are not accessible outside of this module.  */

-struct df_ru_problem_data
+struct df_rd_problem_data

 {
   /* The set of defs to regs invalidated by call.  */
 {
   /* The set of defs to regs invalidated by call.  */

-  bitmap sparse_invalidated_by_call;  
-  /* The set of defs to regs invalidated by call for ru.  */  
-  bitmap dense_invalidated_by_call;
+  bitmap_head sparse_invalidated_by_call;
+  /* The set of defs to regs invalidate by call for rd.  */
+  bitmap_head dense_invalidated_by_call;

   /* An obstack for the bitmaps we need for this problem.  */
   /* An obstack for the bitmaps we need for this problem.  */

-  bitmap_obstack ru_bitmaps;
+  bitmap_obstack rd_bitmaps;

 };
 
 };
 

-/* Set basic block info.  */
-
-static void
-df_ru_set_bb_info (unsigned int index, struct df_ru_bb_info *bb_info)
-{
-  gcc_assert (df_ru);
-  gcc_assert (index < df_ru->block_info_size);
-  df_ru->block_info[index] = bb_info;
-}
-

 
 /* Free basic block info.  */
 
 static void
 
 /* Free basic block info.  */
 
 static void

-df_ru_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
+df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,

                    void *vbb_info)
 {
                    void *vbb_info)
 {

-  struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info;
+  struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;

   if (bb_info)
     {
   if (bb_info)
     {

-      BITMAP_FREE (bb_info->kill);
-      BITMAP_FREE (bb_info->sparse_kill);
-      BITMAP_FREE (bb_info->gen);
-      BITMAP_FREE (bb_info->in);
-      BITMAP_FREE (bb_info->out);
-      pool_free (df_ru->block_pool, bb_info);
+      bitmap_clear (&bb_info->kill);
+      bitmap_clear (&bb_info->sparse_kill);
+      bitmap_clear (&bb_info->gen);
+      bitmap_clear (&bb_info->in);
+      bitmap_clear (&bb_info->out);

     }
 }
 
 
     }
 }
 
 

-/* Allocate or reset bitmaps for DF_RU blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_RD blocks. The solution bits are

    not touched unless the block is new.  */
 
    not touched unless the block is new.  */
 

-static void 
-df_ru_alloc (bitmap all_blocks)
+static void
+df_rd_alloc (bitmap all_blocks)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 {
   unsigned int bb_index;
   bitmap_iterator bi;

-  struct df_ru_problem_data *problem_data;
-
-  if (!df_ru->block_pool)
-    df_ru->block_pool = create_alloc_pool ("df_ru_block pool", 
-                                          sizeof (struct df_ru_bb_info), 50);
+  struct df_rd_problem_data *problem_data;

 
 

-  if (df_ru->problem_data)
+  if (df_rd->problem_data)

     {
     {

-      problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
-      bitmap_clear (problem_data->sparse_invalidated_by_call);
-      bitmap_clear (problem_data->dense_invalidated_by_call);
+      problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
+      bitmap_clear (&problem_data->sparse_invalidated_by_call);
+      bitmap_clear (&problem_data->dense_invalidated_by_call);

     }
     }

-  else 
+  else

     {
     {

-      problem_data = XNEW (struct df_ru_problem_data);
-      df_ru->problem_data = problem_data;
-
-      bitmap_obstack_initialize (&problem_data->ru_bitmaps);
-      problem_data->sparse_invalidated_by_call
-       = BITMAP_ALLOC (&problem_data->ru_bitmaps);
-      problem_data->dense_invalidated_by_call
-       = BITMAP_ALLOC (&problem_data->ru_bitmaps);
+      problem_data = XNEW (struct df_rd_problem_data);
+      df_rd->problem_data = problem_data;
+
+      bitmap_obstack_initialize (&problem_data->rd_bitmaps);
+      bitmap_initialize (&problem_data->sparse_invalidated_by_call,
+                        &problem_data->rd_bitmaps);
+      bitmap_initialize (&problem_data->dense_invalidated_by_call,
+                        &problem_data->rd_bitmaps);

     }
 
     }
 

-  df_grow_bb_info (df_ru);
+  df_grow_bb_info (df_rd);

 
 

-  /* Because of the clustering of all def sites for the same pseudo,
+  /* Because of the clustering of all use sites for the same pseudo,

      we have to process all of the blocks before doing the
      analysis.  */
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
      we have to process all of the blocks before doing the
      analysis.  */
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {

-      struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
-      if (bb_info)
-       { 
-         bitmap_clear (bb_info->kill);
-         bitmap_clear (bb_info->sparse_kill);
-         bitmap_clear (bb_info->gen);
+      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
+      
+      /* When bitmaps are already initialized, just clear them.  */
+      if (bb_info->kill.obstack)
+       {
+         bitmap_clear (&bb_info->kill);
+         bitmap_clear (&bb_info->sparse_kill);
+         bitmap_clear (&bb_info->gen);

        }
       else
        }
       else

-       { 
-         bb_info = (struct df_ru_bb_info *) pool_alloc (df_ru->block_pool);
-         df_ru_set_bb_info (bb_index, bb_info);
-         bb_info->kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
-         bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
-         bb_info->gen = BITMAP_ALLOC (&problem_data->ru_bitmaps);
-         bb_info->in = BITMAP_ALLOC (&problem_data->ru_bitmaps);
-         bb_info->out = BITMAP_ALLOC (&problem_data->ru_bitmaps);
+       {
+         bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
+         bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
+         bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
+         bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
+         bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);

        }
     }
        }
     }

-  df_ru->optional_p = true;
+  df_rd->optional_p = true;

 }
 
 
 }
 
 

-/* Process a list of DEFs for df_ru_bb_local_compute.  */
+/* Add the effect of the top artificial defs of BB to the reaching definitions
+   bitmap LOCAL_RD.  */

 
 

-static void
-df_ru_bb_local_compute_process_def (struct df_ru_bb_info *bb_info, 
-                                   struct df_ref **def_rec,
-                                   enum df_ref_flags top_flag)
+void
+df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)

 {
 {

-  while (*def_rec)
+  int bb_index = bb->index;
+  df_ref *def_rec;
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)

     {
     {

-      struct df_ref *def = *def_rec;
-      if ((top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
-         /* If the def is to only part of the reg, it is as if it did
-            not happen, since some of the bits may get thru.  */
-         && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
+      df_ref def = *def_rec;
+      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)

        {
        {

-         unsigned int regno = DF_REF_REGNO (def);
-         unsigned int begin = DF_USES_BEGIN (regno);
-         unsigned int n_uses = DF_USES_COUNT (regno);
-
-         if (!bitmap_bit_p (seen_in_block, regno))
-           {
-             /* The first def for regno in the insn, causes the kill
-                info to be generated.  Do not modify the gen set
-                because the only values in it are the uses from here
-                to the top of the block and this def does not effect
-                them.  */
-             if (!bitmap_bit_p (seen_in_insn, regno))
-               {
-                 if (n_uses > DF_SPARSE_THRESHOLD)
-                   bitmap_set_bit (bb_info->sparse_kill, regno);
-                 else
-                   bitmap_set_range (bb_info->kill, begin, n_uses);
-               }
-             bitmap_set_bit (seen_in_insn, regno);
-           }
+         unsigned int dregno = DF_REF_REGNO (def);
+         if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+           bitmap_clear_range (local_rd,
+                               DF_DEFS_BEGIN (dregno),
+                               DF_DEFS_COUNT (dregno));
+         bitmap_set_bit (local_rd, DF_REF_ID (def));

        }
        }

-      def_rec++;

     }
 }
 
     }
 }
 

+/* Add the effect of the defs of INSN to the reaching definitions bitmap
+   LOCAL_RD.  */
+
+void
+df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
+                        bitmap local_rd)
+{
+  unsigned uid = INSN_UID (insn);
+  df_ref *def_rec;
+
+  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      unsigned int dregno = DF_REF_REGNO (def);
+      if ((!(df->changeable_flags & DF_NO_HARD_REGS))
+          || (dregno >= FIRST_PSEUDO_REGISTER))
+        {
+          if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+           bitmap_clear_range (local_rd,
+                               DF_DEFS_BEGIN (dregno),
+                               DF_DEFS_COUNT (dregno));
+         if (!(DF_REF_FLAGS (def)
+               & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
+           bitmap_set_bit (local_rd, DF_REF_ID (def));
+       }
+    }
+}

 
 

-/* Process a list of USEs for df_ru_bb_local_compute.  */
+/* Process a list of DEFs for df_rd_bb_local_compute.  This is a bit
+   more complicated than just simulating, because we must produce the
+   gen and kill sets and hence deal with the two possible representations
+   of kill sets.   */

 
 static void
 
 static void

-df_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info, 
-                                   struct df_ref **use_rec,
-                                   enum df_ref_flags top_flag)
+df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
+                                   df_ref *def_rec,
+                                   int top_flag)

 {
 {

-  while (*use_rec)
+  while (*def_rec)

     {
     {

-      struct df_ref *use = *use_rec;
-      if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
+      df_ref def = *def_rec;
+      if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))

        {
        {

-         /* Add use to set of gens in this BB unless we have seen a
-            def in a previous instruction.  */
-         unsigned int regno = DF_REF_REGNO (use);
-         if (!bitmap_bit_p (seen_in_block, regno))
-           bitmap_set_bit (bb_info->gen, DF_REF_ID (use));
+         unsigned int regno = DF_REF_REGNO (def);
+         unsigned int begin = DF_DEFS_BEGIN (regno);
+         unsigned int n_defs = DF_DEFS_COUNT (regno);
+
+         if ((!(df->changeable_flags & DF_NO_HARD_REGS))
+             || (regno >= FIRST_PSEUDO_REGISTER))
+           {
+             /* Only the last def(s) for a regno in the block has any
+                effect.  */
+             if (!bitmap_bit_p (&seen_in_block, regno))
+               {
+                 /* The first def for regno in insn gets to knock out the
+                    defs from other instructions.  */
+                 if ((!bitmap_bit_p (&seen_in_insn, regno))
+                     /* If the def is to only part of the reg, it does
+                        not kill the other defs that reach here.  */
+                     && (!(DF_REF_FLAGS (def) &
+                           (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
+                   {
+                     if (n_defs > DF_SPARSE_THRESHOLD)
+                       {
+                         bitmap_set_bit (&bb_info->sparse_kill, regno);
+                         bitmap_clear_range(&bb_info->gen, begin, n_defs);
+                       }
+                     else
+                       {
+                         bitmap_set_range (&bb_info->kill, begin, n_defs);
+                         bitmap_clear_range (&bb_info->gen, begin, n_defs);
+                       }
+                   }
+
+                 bitmap_set_bit (&seen_in_insn, regno);
+                 /* All defs for regno in the instruction may be put into
+                    the gen set.  */
+                 if (!(DF_REF_FLAGS (def)
+                       & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
+                   bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
+               }
+           }

        }
        }

-      use_rec++;
+      def_rec++;

     }
 }
 
     }
 }
 

-/* Compute local reaching use (upward exposed use) info for basic
-   block BB.  USE_INFO->REGS[R] caches the set of uses for register R.  */
+/* Compute local reaching def info for basic block BB.  */
+

 static void
 static void

-df_ru_bb_local_compute (unsigned int bb_index)
+df_rd_bb_local_compute (unsigned int bb_index)

 {
   basic_block bb = BASIC_BLOCK (bb_index);
 {
   basic_block bb = BASIC_BLOCK (bb_index);

-  struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
+  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);

   rtx insn;
 
   rtx insn;
 

-  /* Set when a def for regno is seen.  */
-  bitmap_clear (seen_in_block);
-  bitmap_clear (seen_in_insn);
+  bitmap_clear (&seen_in_block);
+  bitmap_clear (&seen_in_insn);

 
 

-#ifdef EH_USES
-  /* Variables defined in the prolog that are used by the exception
-     handler.  */
-  df_ru_bb_local_compute_process_use (bb_info, 
-                                     df_get_artificial_uses (bb_index),
-                                     DF_REF_AT_TOP);
-#endif
-  df_ru_bb_local_compute_process_def (bb_info, 
-                                     df_get_artificial_defs (bb_index),
-                                     DF_REF_AT_TOP);
+  /* Artificials are only hard regs.  */
+  if (!(df->changeable_flags & DF_NO_HARD_REGS))
+    df_rd_bb_local_compute_process_def (bb_info,
+                                       df_get_artificial_defs (bb_index),
+                                       0);

 
 

-  FOR_BB_INSNS (bb, insn)
+  FOR_BB_INSNS_REVERSE (bb, insn)

     {
       unsigned int uid = INSN_UID (insn);
     {
       unsigned int uid = INSN_UID (insn);

+

       if (!INSN_P (insn))
        continue;
 
       if (!INSN_P (insn))
        continue;
 

-      df_ru_bb_local_compute_process_use (bb_info, 
-                                         DF_INSN_UID_USES (uid), 0);
-
-      if (df->changeable_flags & DF_EQ_NOTES)
-       df_ru_bb_local_compute_process_use (bb_info, 
-                                           DF_INSN_UID_EQ_USES (uid), 0);
-
-      df_ru_bb_local_compute_process_def (bb_info, 
+      df_rd_bb_local_compute_process_def (bb_info,

                                          DF_INSN_UID_DEFS (uid), 0);
 
                                          DF_INSN_UID_DEFS (uid), 0);
 

-      bitmap_ior_into (seen_in_block, seen_in_insn);
-      bitmap_clear (seen_in_insn);
+      /* This complex dance with the two bitmaps is required because
+        instructions can assign twice to the same pseudo.  This
+        generally happens with calls that will have one def for the
+        result and another def for the clobber.  If only one vector
+        is used and the clobber goes first, the result will be
+        lost.  */
+      bitmap_ior_into (&seen_in_block, &seen_in_insn);
+      bitmap_clear (&seen_in_insn);

     }
 
     }
 

-  /* Process the hardware registers that are always live.  */
-  df_ru_bb_local_compute_process_use (bb_info, 
-                                     df_get_artificial_uses (bb_index), 0);
-
-  df_ru_bb_local_compute_process_def (bb_info, 
-                                     df_get_artificial_defs (bb_index), 0);
+  /* Process the artificial defs at the top of the block last since we
+     are going backwards through the block and these are logically at
+     the start.  */
+  if (!(df->changeable_flags & DF_NO_HARD_REGS))
+    df_rd_bb_local_compute_process_def (bb_info,
+                                       df_get_artificial_defs (bb_index),
+                                       DF_REF_AT_TOP);

 }
 
 
 }
 
 

-/* Compute local reaching use (upward exposed use) info for each basic
-   block within BLOCKS.  */
+/* Compute local reaching def info for each basic block within BLOCKS.  */
+

 static void
 static void

-df_ru_local_compute (bitmap all_blocks)
+df_rd_local_compute (bitmap all_blocks)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
   unsigned int regno;
 {
   unsigned int bb_index;
   bitmap_iterator bi;
   unsigned int regno;

-  struct df_ru_problem_data *problem_data
-    = (struct df_ru_problem_data *) df_ru->problem_data;
-  bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
-  bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
+  struct df_rd_problem_data *problem_data
+    = (struct df_rd_problem_data *) df_rd->problem_data;
+  bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
+  bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;

 
 

-  df_set_seen ();
+  bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
+  bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);

 
 

-  df_maybe_reorganize_use_refs (df->changeable_flags & DF_EQ_NOTES ? 
-                               DF_REF_ORDER_BY_REG_WITH_NOTES : DF_REF_ORDER_BY_REG);
+  df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);

 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {

-      df_ru_bb_local_compute (bb_index);
+      df_rd_bb_local_compute (bb_index);

     }
     }

-  
+

   /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
   /* Set up the knockout bit vectors to be applied across EH_EDGES.  */

-  EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
+  EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)

     {
     {

-      if (DF_USES_COUNT (regno) > DF_SPARSE_THRESHOLD)
+      if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)

        bitmap_set_bit (sparse_invalidated, regno);
       else
        bitmap_set_range (dense_invalidated,
        bitmap_set_bit (sparse_invalidated, regno);
       else
        bitmap_set_range (dense_invalidated,

-                         DF_USES_BEGIN (regno), 
-                         DF_USES_COUNT (regno));
+                         DF_DEFS_BEGIN (regno),
+                         DF_DEFS_COUNT (regno));

     }
 
     }
 

-  df_unset_seen ();
+  bitmap_clear (&seen_in_block);
+  bitmap_clear (&seen_in_insn);

 }
 
 
 /* Initialize the solution bit vectors for problem.  */
 
 }
 
 
 /* Initialize the solution bit vectors for problem.  */
 

-static void 
-df_ru_init_solution (bitmap all_blocks)
+static void
+df_rd_init_solution (bitmap all_blocks)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
 {
   unsigned int bb_index;
   bitmap_iterator bi;
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {

-      struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
-      bitmap_copy (bb_info->in, bb_info->gen);
-      bitmap_clear (bb_info->out);
+      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
+
+      bitmap_copy (&bb_info->out, &bb_info->gen);
+      bitmap_clear (&bb_info->in);

     }
 }
 
     }
 }
 

+/* In of target gets or of out of source.  */

 
 

-/* Out of target gets or of in of source.  */
-
-static void
-df_ru_confluence_n (edge e)
+static bool
+df_rd_confluence_n (edge e)

 {
 {

-  bitmap op1 = df_ru_get_bb_info (e->src->index)->out;
-  bitmap op2 = df_ru_get_bb_info (e->dest->index)->in;
+  bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
+  bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
+  bool changed = false;
+
+  if (e->flags & EDGE_FAKE)
+    return false;

 
   if (e->flags & EDGE_EH)
     {
 
   if (e->flags & EDGE_EH)
     {

-      struct df_ru_problem_data *problem_data
-       = (struct df_ru_problem_data *) df_ru->problem_data;
-      bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
-      bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
+      struct df_rd_problem_data *problem_data
+       = (struct df_rd_problem_data *) df_rd->problem_data;
+      bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
+      bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;

       bitmap_iterator bi;
       unsigned int regno;
       bitmap_iterator bi;
       unsigned int regno;

-      bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
+      bitmap_head tmp;

 
 

-      bitmap_copy (tmp, op2);
-      bitmap_and_compl_into (tmp, dense_invalidated);
+      bitmap_initialize (&tmp, &df_bitmap_obstack);
+      bitmap_copy (&tmp, op2);
+      bitmap_and_compl_into (&tmp, dense_invalidated);

 
       EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
 
       EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)

-       {
-         bitmap_clear_range (tmp, 
-                             DF_USES_BEGIN (regno), 
-                             DF_USES_COUNT (regno));
+       {
+         bitmap_clear_range (&tmp,
+                             DF_DEFS_BEGIN (regno),
+                             DF_DEFS_COUNT (regno));

        }
        }

-      bitmap_ior_into (op1, tmp);
-      BITMAP_FREE (tmp);
+      changed |= bitmap_ior_into (op1, &tmp);
+      bitmap_clear (&tmp);
+      return changed;

     }
   else
     }
   else

-    bitmap_ior_into (op1, op2);
+    return bitmap_ior_into (op1, op2);

 }
 
 
 /* Transfer function.  */
 
 static bool
 }
 
 
 /* Transfer function.  */
 
 static bool

-df_ru_transfer_function (int bb_index)
+df_rd_transfer_function (int bb_index)

 {
 {

-  struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
+  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);

   unsigned int regno;
   bitmap_iterator bi;
   unsigned int regno;
   bitmap_iterator bi;

-  bitmap in = bb_info->in;
-  bitmap out = bb_info->out;
-  bitmap gen = bb_info->gen;
-  bitmap kill = bb_info->kill;
-  bitmap sparse_kill = bb_info->sparse_kill;
+  bitmap in = &bb_info->in;
+  bitmap out = &bb_info->out;
+  bitmap gen = &bb_info->gen;
+  bitmap kill = &bb_info->kill;
+  bitmap sparse_kill = &bb_info->sparse_kill;

 
   if (bitmap_empty_p (sparse_kill))
 
   if (bitmap_empty_p (sparse_kill))

-    return  bitmap_ior_and_compl (in, gen, out, kill);
-  else 
+    return  bitmap_ior_and_compl (out, gen, in, kill);
+  else

     {
     {

-      struct df_ru_problem_data *problem_data;
-      bitmap tmp;
+      struct df_rd_problem_data *problem_data;

       bool changed = false;
       bool changed = false;

+      bitmap_head tmp;

 
       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
 
       /* Note that TMP is _not_ a temporary bitmap if we end up replacing

-        IN with TMP.  Therefore, allocate TMP in the RU bitmaps obstack.  */
-      problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
-      tmp = BITMAP_ALLOC (&problem_data->ru_bitmaps);
+        OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
+      problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
+      bitmap_initialize (&tmp, &problem_data->rd_bitmaps);

 
 

-      bitmap_copy (tmp, out);
+      bitmap_copy (&tmp, in);

       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
        {
       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
        {

-         bitmap_clear_range (tmp, 
-                             DF_USES_BEGIN (regno), 
-                             DF_USES_COUNT (regno));
+         bitmap_clear_range (&tmp,
+                             DF_DEFS_BEGIN (regno),
+                             DF_DEFS_COUNT (regno));

        }
        }

-      bitmap_and_compl_into (tmp, kill);
-      bitmap_ior_into (tmp, gen);
-      changed = !bitmap_equal_p (tmp, in);
+      bitmap_and_compl_into (&tmp, kill);
+      bitmap_ior_into (&tmp, gen);
+      changed = !bitmap_equal_p (&tmp, out);

       if (changed)
        {
       if (changed)
        {

-         BITMAP_FREE (in);
-         bb_info->in = tmp;
+         bitmap_clear (out);
+         bb_info->out = tmp;

        }
        }

-      else 
-       BITMAP_FREE (tmp);
+      else
+         bitmap_clear (&tmp);

       return changed;
     }
 }
       return changed;
     }
 }


@@ -595,497 +570,469 @@ df_ru_transfer_function (int bb_index)
 /* Free all storage associated with the problem.  */
 
 static void
 /* Free all storage associated with the problem.  */
 
 static void

-df_ru_free (void)
+df_rd_free (void)

 {
 {

-  unsigned int i;
-  struct df_ru_problem_data *problem_data
-    = (struct df_ru_problem_data *) df_ru->problem_data;
+  struct df_rd_problem_data *problem_data
+    = (struct df_rd_problem_data *) df_rd->problem_data;

 
   if (problem_data)
     {
 
   if (problem_data)
     {

-      for (i = 0; i < df_ru->block_info_size; i++)
-       {
-         struct df_ru_bb_info *bb_info = df_ru_get_bb_info (i);
-         if (bb_info)
-           {
-             BITMAP_FREE (bb_info->kill);
-             BITMAP_FREE (bb_info->sparse_kill);
-             BITMAP_FREE (bb_info->gen);
-             BITMAP_FREE (bb_info->in);
-             BITMAP_FREE (bb_info->out);
-           }
-       }
-      
-      free_alloc_pool (df_ru->block_pool);
-      BITMAP_FREE (problem_data->sparse_invalidated_by_call);
-      BITMAP_FREE (problem_data->dense_invalidated_by_call);
-      bitmap_obstack_release (&problem_data->ru_bitmaps);
-      
-      df_ru->block_info_size = 0;
-      free (df_ru->block_info);
-      free (df_ru->problem_data);
+      bitmap_obstack_release (&problem_data->rd_bitmaps);
+
+      df_rd->block_info_size = 0;
+      free (df_rd->block_info);
+      df_rd->block_info = NULL;
+      free (df_rd->problem_data);

     }
     }

-  free (df_ru);
+  free (df_rd);

 }
 
 
 /* Debugging info.  */
 
 static void
 }
 
 
 /* Debugging info.  */
 
 static void

-df_ru_start_dump (FILE *file)
+df_rd_start_dump (FILE *file)

 {
 {

-  struct df_ru_problem_data *problem_data
-    = (struct df_ru_problem_data *) df_ru->problem_data;
+  struct df_rd_problem_data *problem_data
+    = (struct df_rd_problem_data *) df_rd->problem_data;

   unsigned int m = DF_REG_SIZE(df);
   unsigned int regno;
   unsigned int m = DF_REG_SIZE(df);
   unsigned int regno;

-  
-  if (!df_ru->block_info) 
+
+  if (!df_rd->block_info)

     return;
 
     return;
 

-  fprintf (file, ";; Reaching uses:\n");
+  fprintf (file, ";; Reaching defs:\n\n");
+
+  fprintf (file, "  sparse invalidated \t");
+  dump_bitmap (file, &problem_data->sparse_invalidated_by_call);
+  fprintf (file, "  dense invalidated \t");
+  dump_bitmap (file, &problem_data->dense_invalidated_by_call);

 
 

-  fprintf (file, ";;   sparse invalidated \t");
-  dump_bitmap (file, problem_data->sparse_invalidated_by_call);
-  fprintf (file, " dense invalidated \t");
-  dump_bitmap (file, problem_data->dense_invalidated_by_call);
-  

   for (regno = 0; regno < m; regno++)
   for (regno = 0; regno < m; regno++)

-    if (DF_USES_COUNT (regno))
-      fprintf (file, "%d[%d,%d] ", regno, 
-              DF_USES_BEGIN (regno), 
-              DF_USES_COUNT (regno));
+    if (DF_DEFS_COUNT (regno))
+      fprintf (file, "%d[%d,%d] ", regno,
+              DF_DEFS_BEGIN (regno),
+              DF_DEFS_COUNT (regno));

   fprintf (file, "\n");
   fprintf (file, "\n");

+

 }
 
 
 /* Debugging info at top of bb.  */
 
 static void
 }
 
 
 /* Debugging info at top of bb.  */
 
 static void

-df_ru_top_dump (basic_block bb, FILE *file)
+df_rd_top_dump (basic_block bb, FILE *file)

 {
 {

-  struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
-  if (!bb_info || !bb_info->in)
+  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
+  if (!bb_info)

     return;
     return;

-  
-  fprintf (file, ";; ru  in  \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
-  dump_bitmap (file, bb_info->in);
-  fprintf (file, ";; ru  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
-  dump_bitmap (file, bb_info->gen);
-  fprintf (file, ";; ru  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
-  dump_bitmap (file, bb_info->kill);
-}  

 
 

+  fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (&bb_info->in));
+  dump_bitmap (file, &bb_info->in);
+  fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (&bb_info->gen));
+  dump_bitmap (file, &bb_info->gen);
+  fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (&bb_info->kill));
+  dump_bitmap (file, &bb_info->kill);
+}

 
 

-/* Debugging info at bottom of bb.  */
+
+/* Debugging info at top of bb.  */

 
 static void
 
 static void

-df_ru_bottom_dump (basic_block bb, FILE *file)
+df_rd_bottom_dump (basic_block bb, FILE *file)

 {
 {

-  struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
-  if (!bb_info || !bb_info->out)
+  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
+  if (!bb_info)

     return;
     return;

-  
-  fprintf (file, ";; ru  out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
-  dump_bitmap (file, bb_info->out);
-}  

 
 

+  fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (&bb_info->out));
+  dump_bitmap (file, &bb_info->out);
+}

 
 /* All of the information associated with every instance of the problem.  */
 
 
 /* All of the information associated with every instance of the problem.  */
 

-static struct df_problem problem_RU =
+static struct df_problem problem_RD =

 {
 {

-  DF_RU,                      /* Problem id.  */
-  DF_BACKWARD,                /* Direction.  */
-  df_ru_alloc,                /* Allocate the problem specific data.  */
+  DF_RD,                      /* Problem id.  */
+  DF_FORWARD,                 /* Direction.  */
+  df_rd_alloc,                /* Allocate the problem specific data.  */

   NULL,                       /* Reset global information.  */
   NULL,                       /* Reset global information.  */

-  df_ru_free_bb_info,         /* Free basic block info.  */
-  df_ru_local_compute,        /* Local compute function.  */
-  df_ru_init_solution,        /* Init the solution specific data.  */
+  df_rd_free_bb_info,         /* Free basic block info.  */
+  df_rd_local_compute,        /* Local compute function.  */
+  df_rd_init_solution,        /* Init the solution specific data.  */

   df_worklist_dataflow,       /* Worklist solver.  */
   df_worklist_dataflow,       /* Worklist solver.  */

-  NULL,                       /* Confluence operator 0.  */ 
-  df_ru_confluence_n,         /* Confluence operator n.  */ 
-  df_ru_transfer_function,    /* Transfer function.  */
+  NULL,                       /* Confluence operator 0.  */
+  df_rd_confluence_n,         /* Confluence operator n.  */
+  df_rd_transfer_function,    /* Transfer function.  */

   NULL,                       /* Finalize function.  */
   NULL,                       /* Finalize function.  */

-  df_ru_free,                 /* Free all of the problem information.  */
-  df_ru_free,                 /* Remove this problem from the stack of dataflow problems.  */
-  df_ru_start_dump,           /* Debugging.  */
-  df_ru_top_dump,             /* Debugging start block.  */
-  df_ru_bottom_dump,          /* Debugging end block.  */
+  df_rd_free,                 /* Free all of the problem information.  */
+  df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
+  df_rd_start_dump,           /* Debugging.  */
+  df_rd_top_dump,             /* Debugging start block.  */
+  df_rd_bottom_dump,          /* Debugging end block.  */

   NULL,                       /* Incremental solution verify start.  */
   NULL,                       /* Incremental solution verify end.  */
   NULL,                       /* Dependent problem.  */
   NULL,                       /* Incremental solution verify start.  */
   NULL,                       /* Incremental solution verify end.  */
   NULL,                       /* Dependent problem.  */

-  TV_DF_RU,                   /* Timing variable.  */
+  sizeof (struct df_rd_bb_info),/* Size of entry of block_info array.  */
+  TV_DF_RD,                   /* Timing variable.  */

   true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
 };
 
 
 
   true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
 };
 
 
 

-/* Create a new DATAFLOW instance and add it to an existing instance
-   of DF.  The returned structure is what is used to get at the
-   solution.  */
+/* Create a new RD instance and add it to the existing instance
+   of DF.  */

 
 void
 
 void

-df_ru_add_problem (void)
+df_rd_add_problem (void)

 {
 {

-  df_add_problem (&problem_RU);
+  df_add_problem (&problem_RD);

 }
 
 }
 

+

 \f
 /*----------------------------------------------------------------------------
 \f
 /*----------------------------------------------------------------------------

-   REACHING DEFINITIONS
+   LIVE REGISTERS

 
 

-   Find the locations in the function where each definition site for a
-   pseudo reaches.  In and out bitvectors are built for each basic
-   block.  The id field in the ref is used to index into these sets.
+   Find the locations in the function where any use of a pseudo can
+   reach in the backwards direction.  In and out bitvectors are built
+   for each basic block.  The regno is used to index into these sets.

    See df.h for details.
    ----------------------------------------------------------------------------*/
 
    See df.h for details.
    ----------------------------------------------------------------------------*/
 

-/* See the comment at the top of the Reaching Uses problem for how the
-   uses are represented in the kill sets. The same games are played
-   here for the defs.  */
-
-/* Private data used to compute the solution for this problem.  These
-   data structures are not accessible outside of this module.  */
-struct df_rd_problem_data
+/* Private data used to verify the solution for this problem.  */
+struct df_lr_problem_data

 {
 {

-  /* The set of defs to regs invalidated by call.  */
-  bitmap sparse_invalidated_by_call;  
-  /* The set of defs to regs invalidate by call for rd.  */  
-  bitmap dense_invalidated_by_call;
+  bitmap_head *in;
+  bitmap_head *out;

   /* An obstack for the bitmaps we need for this problem.  */
   /* An obstack for the bitmaps we need for this problem.  */

-  bitmap_obstack rd_bitmaps;
+  bitmap_obstack lr_bitmaps;

 };
 
 };
 

-/* Set basic block info.  */
-
-static void
-df_rd_set_bb_info (unsigned int index, 
-                  struct df_rd_bb_info *bb_info)
-{
-  gcc_assert (df_rd);
-  gcc_assert (index < df_rd->block_info_size);
-  df_rd->block_info[index] = bb_info;
-}
-
-

 /* Free basic block info.  */
 
 static void
 /* Free basic block info.  */
 
 static void

-df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
+df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,

                    void *vbb_info)
 {
                    void *vbb_info)
 {

-  struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
+  struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;

   if (bb_info)
     {
   if (bb_info)
     {

-      BITMAP_FREE (bb_info->kill);
-      BITMAP_FREE (bb_info->sparse_kill);
-      BITMAP_FREE (bb_info->gen);
-      BITMAP_FREE (bb_info->in);
-      BITMAP_FREE (bb_info->out);
-      pool_free (df_rd->block_pool, bb_info);
+      bitmap_clear (&bb_info->use);
+      bitmap_clear (&bb_info->def);
+      bitmap_clear (&bb_info->in);
+      bitmap_clear (&bb_info->out);

     }
 }
 
 
     }
 }
 
 

-/* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_LR blocks. The solution bits are

    not touched unless the block is new.  */
 
    not touched unless the block is new.  */
 

-static void 
-df_rd_alloc (bitmap all_blocks)
+static void
+df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 {
   unsigned int bb_index;
   bitmap_iterator bi;

-  struct df_rd_problem_data *problem_data;
-
-  if (!df_rd->block_pool)
-    df_rd->block_pool = create_alloc_pool ("df_rd_block pool", 
-                                          sizeof (struct df_rd_bb_info), 50);
+  struct df_lr_problem_data *problem_data;

 
 

-  if (df_rd->problem_data)
-    {
-      problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
-      bitmap_clear (problem_data->sparse_invalidated_by_call);
-      bitmap_clear (problem_data->dense_invalidated_by_call);
-    }
-  else 
+  df_grow_bb_info (df_lr);
+  if (df_lr->problem_data)
+    problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
+  else

     {
     {

-      problem_data = XNEW (struct df_rd_problem_data);
-      df_rd->problem_data = problem_data;
+      problem_data = XNEW (struct df_lr_problem_data);
+      df_lr->problem_data = problem_data;

 
 

-      bitmap_obstack_initialize (&problem_data->rd_bitmaps);
-      problem_data->sparse_invalidated_by_call
-       = BITMAP_ALLOC (&problem_data->rd_bitmaps);
-      problem_data->dense_invalidated_by_call
-       = BITMAP_ALLOC (&problem_data->rd_bitmaps);
+      problem_data->out = NULL;
+      problem_data->in = NULL;
+      bitmap_obstack_initialize (&problem_data->lr_bitmaps);

     }
 
     }
 

-  df_grow_bb_info (df_rd);
-
-  /* Because of the clustering of all use sites for the same pseudo,
-     we have to process all of the blocks before doing the
-     analysis.  */
-
-  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+  EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)

     {
     {

-      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
-      if (bb_info)
-       { 
-         bitmap_clear (bb_info->kill);
-         bitmap_clear (bb_info->sparse_kill);
-         bitmap_clear (bb_info->gen);
+      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+      
+      /* When bitmaps are already initialized, just clear them.  */
+      if (bb_info->use.obstack)
+       {
+         bitmap_clear (&bb_info->def);
+         bitmap_clear (&bb_info->use);

        }
       else
        }
       else

-       { 
-         bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
-         df_rd_set_bb_info (bb_index, bb_info);
-         bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
-         bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
-         bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
-         bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
-         bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
+       {
+         bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
+         bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
+         bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
+         bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);

        }
     }
        }
     }

-  df_rd->optional_p = true;
+
+  df_lr->optional_p = false;

 }
 
 
 }
 
 

-/* Process a list of DEFs for df_rd_bb_local_compute.  */
+/* Reset the global solution for recalculation.  */

 
 static void
 
 static void

-df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info, 
-                                   struct df_ref **def_rec,
-                                   enum df_ref_flags top_flag)
+df_lr_reset (bitmap all_blocks)

 {
 {

-  while (*def_rec)
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)

     {
     {

-      struct df_ref *def = *def_rec;
-      if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
-       {
-         unsigned int regno = DF_REF_REGNO (def);
-         unsigned int begin = DF_DEFS_BEGIN (regno);
-         unsigned int n_defs = DF_DEFS_COUNT (regno);
-         
-         if ((!(df->changeable_flags & DF_NO_HARD_REGS))
-             || (regno >= FIRST_PSEUDO_REGISTER))
-           {
-             /* Only the last def(s) for a regno in the block has any
-                effect.  */ 
-             if (!bitmap_bit_p (seen_in_block, regno))
-               {
-                 /* The first def for regno in insn gets to knock out the
-                    defs from other instructions.  */
-                 if ((!bitmap_bit_p (seen_in_insn, regno))
-                     /* If the def is to only part of the reg, it does
-                        not kill the other defs that reach here.  */
-                     && (!(DF_REF_FLAGS (def) & 
-                           (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
-                   {
-                     if (n_defs > DF_SPARSE_THRESHOLD)
-                       {
-                         bitmap_set_bit (bb_info->sparse_kill, regno);
-                         bitmap_clear_range(bb_info->gen, begin, n_defs);
-                       }
-                     else
-                       {
-                         bitmap_set_range (bb_info->kill, begin, n_defs);
-                         bitmap_clear_range (bb_info->gen, begin, n_defs);
-                       }
-                   }
-                 
-                 bitmap_set_bit (seen_in_insn, regno);
-                 /* All defs for regno in the instruction may be put into
-                    the gen set.  */
-                 if (!(DF_REF_FLAGS (def) 
-                       & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
-                   bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
-               }
-           }
-       }
-      def_rec++;
+      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+      gcc_assert (bb_info);
+      bitmap_clear (&bb_info->in);
+      bitmap_clear (&bb_info->out);

     }
 }
 
     }
 }
 

-/* Compute local reaching def info for basic block BB.  */
+
+/* Compute local live register info for basic block BB.  */

 
 static void
 
 static void

-df_rd_bb_local_compute (unsigned int bb_index)
+df_lr_bb_local_compute (unsigned int bb_index)

 {
   basic_block bb = BASIC_BLOCK (bb_index);
 {
   basic_block bb = BASIC_BLOCK (bb_index);

-  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
+  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);

   rtx insn;
   rtx insn;

+  df_ref *def_rec;
+  df_ref *use_rec;

 
 

-  bitmap_clear (seen_in_block);
-  bitmap_clear (seen_in_insn);
+  /* Process the registers set in an exception handler.  */
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+       {
+         unsigned int dregno = DF_REF_REGNO (def);
+         bitmap_set_bit (&bb_info->def, dregno);
+         bitmap_clear_bit (&bb_info->use, dregno);
+       }
+    }

 
 

-  /* Artificials are only hard regs.  */
-  if (!(df->changeable_flags & DF_NO_HARD_REGS))
-    df_rd_bb_local_compute_process_def (bb_info, 
-                                       df_get_artificial_defs (bb_index),
-                                       0);
+  /* Process the hardware registers that are always live.  */
+  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+    {
+      df_ref use = *use_rec;
+      /* Add use to set of uses in this BB.  */
+      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
+       bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
+    }

 
   FOR_BB_INSNS_REVERSE (bb, insn)
     {
       unsigned int uid = INSN_UID (insn);
 
 
   FOR_BB_INSNS_REVERSE (bb, insn)
     {
       unsigned int uid = INSN_UID (insn);
 

-      if (!INSN_P (insn))
+      if (!NONDEBUG_INSN_P (insn))

        continue;
 
        continue;
 

-      df_rd_bb_local_compute_process_def (bb_info, 
-                                         DF_INSN_UID_DEFS (uid), 0);
+      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+       {
+         df_ref def = *def_rec;
+         /* If the def is to only part of the reg, it does
+            not kill the other defs that reach here.  */
+         if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+           {
+             unsigned int dregno = DF_REF_REGNO (def);
+             bitmap_set_bit (&bb_info->def, dregno);
+             bitmap_clear_bit (&bb_info->use, dregno);
+           }
+       }

 
 

-      /* This complex dance with the two bitmaps is required because
-        instructions can assign twice to the same pseudo.  This
-        generally happens with calls that will have one def for the
-        result and another def for the clobber.  If only one vector
-        is used and the clobber goes first, the result will be
-        lost.  */
-      bitmap_ior_into (seen_in_block, seen_in_insn);
-      bitmap_clear (seen_in_insn);
+      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+       {
+         df_ref use = *use_rec;
+         /* Add use to set of uses in this BB.  */
+         bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
+       }

     }
 
     }
 

-  /* Process the artificial defs at the top of the block last since we
-     are going backwards through the block and these are logically at
-     the start.  */
-  if (!(df->changeable_flags & DF_NO_HARD_REGS))
-    df_rd_bb_local_compute_process_def (bb_info, 
-                                       df_get_artificial_defs (bb_index),
-                                       DF_REF_AT_TOP);
+  /* Process the registers set in an exception handler or the hard
+     frame pointer if this block is the target of a non local
+     goto.  */
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+       {
+         unsigned int dregno = DF_REF_REGNO (def);
+         bitmap_set_bit (&bb_info->def, dregno);
+         bitmap_clear_bit (&bb_info->use, dregno);
+       }
+    }
+
+#ifdef EH_USES
+  /* Process the uses that are live into an exception handler.  */
+  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+    {
+      df_ref use = *use_rec;
+      /* Add use to set of uses in this BB.  */
+      if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
+       bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
+    }
+#endif
+
+  /* If the df_live problem is not defined, such as at -O0 and -O1, we
+     still need to keep the luids up to date.  This is normally done
+     in the df_live problem since this problem has a forwards
+     scan.  */
+  if (!df_live)
+    df_recompute_luids (bb);

 }
 
 
 }
 
 

-/* Compute local reaching def info for each basic block within BLOCKS.  */
+/* Compute local live register info for each basic block within BLOCKS.  */

 
 static void
 
 static void

-df_rd_local_compute (bitmap all_blocks)
+df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 {
   unsigned int bb_index;
   bitmap_iterator bi;

-  unsigned int regno;
-  struct df_rd_problem_data *problem_data
-    = (struct df_rd_problem_data *) df_rd->problem_data;
-  bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
-  bitmap dense_invalidated = problem_data->dense_invalidated_by_call;

 
 

-  df_set_seen ();
+  bitmap_clear (&df->hardware_regs_used);

 
 

-  df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
+  /* The all-important stack pointer must always be live.  */
+  bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);

 
 

-  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+  /* Before reload, there are a few registers that must be forced
+     live everywhere -- which might not already be the case for
+     blocks within infinite loops.  */
+  if (!reload_completed)

     {
     {

-      df_rd_bb_local_compute (bb_index);
+      /* Any reference to any pseudo before reload is a potential
+        reference of the frame pointer.  */
+      bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
+
+#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
+      /* Pseudos with argument area equivalences may require
+        reloading via the argument pointer.  */
+      if (fixed_regs[ARG_POINTER_REGNUM])
+       bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
+#endif
+
+      /* Any constant, or pseudo with constant equivalences, may
+        require reloading from memory using the pic register.  */
+      if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
+         && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
+       bitmap_set_bit (&df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);

     }
     }

-  
-  /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
-  EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
+
+  EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)

     {
     {

-      if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
-       bitmap_set_bit (sparse_invalidated, regno);
+      if (bb_index == EXIT_BLOCK)
+       {
+         /* The exit block is special for this problem and its bits are
+            computed from thin air.  */
+         struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
+         bitmap_copy (&bb_info->use, df->exit_block_uses);
+       }

       else
       else

-       bitmap_set_range (dense_invalidated, 
-                         DF_DEFS_BEGIN (regno), 
-                         DF_DEFS_COUNT (regno));
+       df_lr_bb_local_compute (bb_index);

     }
     }

-  df_unset_seen ();
+
+  bitmap_clear (df_lr->out_of_date_transfer_functions);

 }
 
 
 }
 
 

-/* Initialize the solution bit vectors for problem.  */
+/* Initialize the solution vectors.  */

 
 

-static void 
-df_rd_init_solution (bitmap all_blocks)
+static void
+df_lr_init (bitmap all_blocks)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
 {
   unsigned int bb_index;
   bitmap_iterator bi;
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {

-      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
-      
-      bitmap_copy (bb_info->out, bb_info->gen);
-      bitmap_clear (bb_info->in);
+      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+      bitmap_copy (&bb_info->in, &bb_info->use);
+      bitmap_clear (&bb_info->out);

     }
 }
 
     }
 }
 

-/* In of target gets or of out of source.  */

 
 

+/* Confluence function that processes infinite loops.  This might be a
+   noreturn function that throws.  And even if it isn't, getting the
+   unwind info right helps debugging.  */

 static void
 static void

-df_rd_confluence_n (edge e)
+df_lr_confluence_0 (basic_block bb)

 {
 {

-  bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
-  bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
+  bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
+  if (bb != EXIT_BLOCK_PTR)
+    bitmap_copy (op1, &df->hardware_regs_used);
+}

 
 

-  if (e->flags & EDGE_EH)
-    {
-      struct df_rd_problem_data *problem_data
-       = (struct df_rd_problem_data *) df_rd->problem_data;
-      bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
-      bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
-      bitmap_iterator bi;
-      unsigned int regno;
-      bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);

 
 

-      bitmap_copy (tmp, op2);
-      bitmap_and_compl_into (tmp, dense_invalidated);
+/* Confluence function that ignores fake edges.  */

 
 

-      EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
-       {
-         bitmap_clear_range (tmp, 
-                             DF_DEFS_BEGIN (regno), 
-                             DF_DEFS_COUNT (regno));
-       }
-      bitmap_ior_into (op1, tmp);
-      BITMAP_FREE (tmp);
-    }
+static bool
+df_lr_confluence_n (edge e)
+{
+  bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
+  bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
+  bool changed = false;
+
+  /* Call-clobbered registers die across exception and call edges.  */
+  /* ??? Abnormal call edges ignored for the moment, as this gets
+     confused by sibling call edges, which crashes reg-stack.  */
+  if (e->flags & EDGE_EH)
+    changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);

   else
   else

-    bitmap_ior_into (op1, op2);
+    changed = bitmap_ior_into (op1, op2);
+
+  changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
+  return changed;

 }
 
 
 /* Transfer function.  */
 
 static bool
 }
 
 
 /* Transfer function.  */
 
 static bool

-df_rd_transfer_function (int bb_index)
+df_lr_transfer_function (int bb_index)

 {
 {

-  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
-  unsigned int regno;
-  bitmap_iterator bi;
-  bitmap in = bb_info->in;
-  bitmap out = bb_info->out;
-  bitmap gen = bb_info->gen;
-  bitmap kill = bb_info->kill;
-  bitmap sparse_kill = bb_info->sparse_kill;
+  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+  bitmap in = &bb_info->in;
+  bitmap out = &bb_info->out;
+  bitmap use = &bb_info->use;
+  bitmap def = &bb_info->def;

 
 

-  if (bitmap_empty_p (sparse_kill))
-    return  bitmap_ior_and_compl (out, gen, in, kill);
-  else 
-    {
-      struct df_rd_problem_data *problem_data;
-      bool changed = false;
-      bitmap tmp;
+  return bitmap_ior_and_compl (in, use, out, def);
+}

 
 

-      /* Note that TMP is _not_ a temporary bitmap if we end up replacing
-        OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
-      problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
-      tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);

 
 

-      bitmap_copy (tmp, in);
-      EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
-       {
-         bitmap_clear_range (tmp, 
-                             DF_DEFS_BEGIN (regno), 
-                             DF_DEFS_COUNT (regno));
-       }
-      bitmap_and_compl_into (tmp, kill);
-      bitmap_ior_into (tmp, gen);
-      changed = !bitmap_equal_p (tmp, out);
-      if (changed)
+/* Run the fast dce as a side effect of building LR.  */
+
+static void
+df_lr_finalize (bitmap all_blocks)
+{
+  df_lr->solutions_dirty = false;
+  if (df->changeable_flags & DF_LR_RUN_DCE)
+    {
+      run_fast_df_dce ();
+
+      /* If dce deletes some instructions, we need to recompute the lr
+        solution before proceeding further.  The problem is that fast
+        dce is a pessimestic dataflow algorithm.  In the case where
+        it deletes a statement S inside of a loop, the uses inside of
+        S may not be deleted from the dataflow solution because they
+        were carried around the loop.  While it is conservatively
+        correct to leave these extra bits, the standards of df
+        require that we maintain the best possible (least fixed
+        point) solution.  The only way to do that is to redo the
+        iteration from the beginning.  See PR35805 for an
+        example.  */
+      if (df_lr->solutions_dirty)

        {
        {

-         BITMAP_FREE (out);
-         bb_info->out = tmp;
+         df_clear_flags (DF_LR_RUN_DCE);
+         df_lr_alloc (all_blocks);
+         df_lr_local_compute (all_blocks);
+         df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
+         df_lr_finalize (all_blocks);
+         df_set_flags (DF_LR_RUN_DCE);

        }
        }

-      else 
-         BITMAP_FREE (tmp);
-      return changed;

     }
 }
 
     }
 }
 


@@ -1093,674 +1040,637 @@ df_rd_transfer_function (int bb_index)
 /* Free all storage associated with the problem.  */
 
 static void
 /* Free all storage associated with the problem.  */
 
 static void

-df_rd_free (void)
+df_lr_free (void)

 {
 {

-  unsigned int i;
-  struct df_rd_problem_data *problem_data
-    = (struct df_rd_problem_data *) df_rd->problem_data;
-
-  if (problem_data)
+  struct df_lr_problem_data *problem_data
+    = (struct df_lr_problem_data *) df_lr->problem_data;
+  if (df_lr->block_info)

     {
     {

-      for (i = 0; i < df_rd->block_info_size; i++)
-       {
-         struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i);
-         if (bb_info)
-           {
-             BITMAP_FREE (bb_info->kill);
-             BITMAP_FREE (bb_info->sparse_kill);
-             BITMAP_FREE (bb_info->gen);
-             BITMAP_FREE (bb_info->in);
-             BITMAP_FREE (bb_info->out);
-           }
-       }
-      
-      free_alloc_pool (df_rd->block_pool);
-      BITMAP_FREE (problem_data->sparse_invalidated_by_call);
-      BITMAP_FREE (problem_data->dense_invalidated_by_call);
-      bitmap_obstack_release (&problem_data->rd_bitmaps);
-      
-      df_rd->block_info_size = 0;
-      free (df_rd->block_info);
-      free (df_rd->problem_data);
+
+      df_lr->block_info_size = 0;
+      free (df_lr->block_info);
+      df_lr->block_info = NULL;
+      bitmap_obstack_release (&problem_data->lr_bitmaps);
+      free (df_lr->problem_data);
+      df_lr->problem_data = NULL;

     }
     }

-  free (df_rd);
+
+  BITMAP_FREE (df_lr->out_of_date_transfer_functions);
+  free (df_lr);

 }
 
 
 }
 
 

-/* Debugging info.  */
+/* Debugging info at top of bb.  */

 
 static void
 
 static void

-df_rd_start_dump (FILE *file)
+df_lr_top_dump (basic_block bb, FILE *file)

 {
 {

-  struct df_rd_problem_data *problem_data
-    = (struct df_rd_problem_data *) df_rd->problem_data;
-  unsigned int m = DF_REG_SIZE(df);
-  unsigned int regno;
-  
-  if (!df_rd->block_info) 
+  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
+  struct df_lr_problem_data *problem_data;
+  if (!bb_info)

     return;
 
     return;
 

-  fprintf (file, ";; Reaching defs:\n\n");
+  fprintf (file, ";; lr  in  \t");
+  df_print_regset (file, &bb_info->in);
+  if (df_lr->problem_data)
+    {
+      problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
+      if (problem_data->in)
+       {
+         fprintf (file, ";;  old in  \t");
+         df_print_regset (file, &problem_data->in[bb->index]);
+       }
+    }
+  fprintf (file, ";; lr  use \t");
+  df_print_regset (file, &bb_info->use);
+  fprintf (file, ";; lr  def \t");
+  df_print_regset (file, &bb_info->def);
+}

 
 

-  fprintf (file, "  sparse invalidated \t");
-  dump_bitmap (file, problem_data->sparse_invalidated_by_call);
-  fprintf (file, "  dense invalidated \t");
-  dump_bitmap (file, problem_data->dense_invalidated_by_call);

 
 

-  for (regno = 0; regno < m; regno++)
-    if (DF_DEFS_COUNT (regno))
-      fprintf (file, "%d[%d,%d] ", regno, 
-              DF_DEFS_BEGIN (regno), 
-              DF_DEFS_COUNT (regno));
-  fprintf (file, "\n");
+/* Debugging info at bottom of bb.  */
+
+static void
+df_lr_bottom_dump (basic_block bb, FILE *file)
+{
+  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
+  struct df_lr_problem_data *problem_data;
+  if (!bb_info)
+    return;

 
 

+  fprintf (file, ";; lr  out \t");
+  df_print_regset (file, &bb_info->out);
+  if (df_lr->problem_data)
+    {
+      problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
+      if (problem_data->out)
+       {
+          fprintf (file, ";;  old out  \t");
+          df_print_regset (file, &problem_data->out[bb->index]);
+       }
+    }

 }
 
 
 }
 
 

-/* Debugging info at top of bb.  */
+/* Build the datastructure to verify that the solution to the dataflow
+   equations is not dirty.  */

 
 static void
 
 static void

-df_rd_top_dump (basic_block bb, FILE *file)
+df_lr_verify_solution_start (void)

 {
 {

-  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
-  if (!bb_info || !bb_info->in)
+  basic_block bb;
+  struct df_lr_problem_data *problem_data;
+  if (df_lr->solutions_dirty)

     return;
     return;

-  
-  fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
-  dump_bitmap (file, bb_info->in);
-  fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
-  dump_bitmap (file, bb_info->gen);
-  fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
-  dump_bitmap (file, bb_info->kill);
+
+  /* Set it true so that the solution is recomputed.  */
+  df_lr->solutions_dirty = true;
+
+  problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
+  problem_data->in = XNEWVEC (bitmap_head, last_basic_block);
+  problem_data->out = XNEWVEC (bitmap_head, last_basic_block);
+
+  FOR_ALL_BB (bb)
+    {
+      bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
+      bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
+      bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
+      bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
+    }

 }
 
 
 }
 
 

-/* Debugging info at top of bb.  */
+/* Compare the saved datastructure and the new solution to the dataflow
+   equations.  */

 
 static void
 
 static void

-df_rd_bottom_dump (basic_block bb, FILE *file)
+df_lr_verify_solution_end (void)

 {
 {

-  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
-  if (!bb_info || !bb_info->out)
+  struct df_lr_problem_data *problem_data;
+  basic_block bb;
+
+  problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
+
+  if (!problem_data->out)

     return;
     return;

-  
-  fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
-  dump_bitmap (file, bb_info->out);
+
+  if (df_lr->solutions_dirty)
+    /* Do not check if the solution is still dirty.  See the comment
+       in df_lr_finalize for details.  */
+    df_lr->solutions_dirty = false;
+  else
+    FOR_ALL_BB (bb)
+      {
+       if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
+           || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
+         {
+           /*df_dump (stderr);*/
+           gcc_unreachable ();
+         }
+      }
+
+  /* Cannot delete them immediately because you may want to dump them
+     if the comparison fails.  */
+  FOR_ALL_BB (bb)
+    {
+      bitmap_clear (&problem_data->in[bb->index]);
+      bitmap_clear (&problem_data->out[bb->index]);
+    }
+
+  free (problem_data->in);
+  free (problem_data->out);
+  problem_data->in = NULL;
+  problem_data->out = NULL;

 }
 
 }
 

+

 /* All of the information associated with every instance of the problem.  */
 
 /* All of the information associated with every instance of the problem.  */
 

-static struct df_problem problem_RD =
+static struct df_problem problem_LR =

 {
 {

-  DF_RD,                      /* Problem id.  */
-  DF_FORWARD,                 /* Direction.  */
-  df_rd_alloc,                /* Allocate the problem specific data.  */
-  NULL,                       /* Reset global information.  */
-  df_rd_free_bb_info,         /* Free basic block info.  */
-  df_rd_local_compute,        /* Local compute function.  */
-  df_rd_init_solution,        /* Init the solution specific data.  */
+  DF_LR,                      /* Problem id.  */
+  DF_BACKWARD,                /* Direction.  */
+  df_lr_alloc,                /* Allocate the problem specific data.  */
+  df_lr_reset,                /* Reset global information.  */
+  df_lr_free_bb_info,         /* Free basic block info.  */
+  df_lr_local_compute,        /* Local compute function.  */
+  df_lr_init,                 /* Init the solution specific data.  */

   df_worklist_dataflow,       /* Worklist solver.  */
   df_worklist_dataflow,       /* Worklist solver.  */

-  NULL,                       /* Confluence operator 0.  */ 
-  df_rd_confluence_n,         /* Confluence operator n.  */ 
-  df_rd_transfer_function,    /* Transfer function.  */
-  NULL,                       /* Finalize function.  */
-  df_rd_free,                 /* Free all of the problem information.  */
-  df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
-  df_rd_start_dump,           /* Debugging.  */
-  df_rd_top_dump,             /* Debugging start block.  */
-  df_rd_bottom_dump,          /* Debugging end block.  */
-  NULL,                       /* Incremental solution verify start.  */
-  NULL,                       /* Incremental solution verify end.  */
+  df_lr_confluence_0,         /* Confluence operator 0.  */
+  df_lr_confluence_n,         /* Confluence operator n.  */
+  df_lr_transfer_function,    /* Transfer function.  */
+  df_lr_finalize,             /* Finalize function.  */
+  df_lr_free,                 /* Free all of the problem information.  */
+  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
+  NULL,                       /* Debugging.  */
+  df_lr_top_dump,             /* Debugging start block.  */
+  df_lr_bottom_dump,          /* Debugging end block.  */
+  df_lr_verify_solution_start,/* Incremental solution verify start.  */
+  df_lr_verify_solution_end,  /* Incremental solution verify end.  */

   NULL,                       /* Dependent problem.  */
   NULL,                       /* Dependent problem.  */

-  TV_DF_RD,                   /* Timing variable.  */ 
-  true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
+  sizeof (struct df_lr_bb_info),/* Size of entry of block_info array.  */
+  TV_DF_LR,                   /* Timing variable.  */
+  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */

 };
 
 
 };
 
 

-

 /* Create a new DATAFLOW instance and add it to an existing instance
    of DF.  The returned structure is what is used to get at the
    solution.  */
 
 void
 /* Create a new DATAFLOW instance and add it to an existing instance
    of DF.  The returned structure is what is used to get at the
    solution.  */
 
 void

-df_rd_add_problem (void)
+df_lr_add_problem (void)

 {
 {

-  df_add_problem (&problem_RD);
+  df_add_problem (&problem_LR);
+  /* These will be initialized when df_scan_blocks processes each
+     block.  */
+  df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
+}
+
+
+/* Verify that all of the lr related info is consistent and
+   correct.  */
+
+void
+df_lr_verify_transfer_functions (void)
+{
+  basic_block bb;
+  bitmap_head saved_def;
+  bitmap_head saved_use;
+  bitmap_head all_blocks;
+
+  if (!df)
+    return;
+
+  bitmap_initialize (&saved_def, &bitmap_default_obstack); 
+  bitmap_initialize (&saved_use, &bitmap_default_obstack);
+  bitmap_initialize (&all_blocks, &bitmap_default_obstack);
+
+  FOR_ALL_BB (bb)
+    {
+      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
+      bitmap_set_bit (&all_blocks, bb->index);
+
+      if (bb_info)
+       {
+         /* Make a copy of the transfer functions and then compute
+            new ones to see if the transfer functions have
+            changed.  */
+         if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
+                            bb->index))
+           {
+             bitmap_copy (&saved_def, &bb_info->def);
+             bitmap_copy (&saved_use, &bb_info->use);
+             bitmap_clear (&bb_info->def);
+             bitmap_clear (&bb_info->use);
+
+             df_lr_bb_local_compute (bb->index);
+             gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
+             gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
+           }
+       }
+      else
+       {
+         /* If we do not have basic block info, the block must be in
+            the list of dirty blocks or else some one has added a
+            block behind our backs. */
+         gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
+                                   bb->index));
+       }
+      /* Make sure no one created a block without following
+        procedures.  */
+      gcc_assert (df_scan_get_bb_info (bb->index));
+    }
+
+  /* Make sure there are no dirty bits in blocks that have been deleted.  */
+  gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
+                                        &all_blocks));
+
+  bitmap_clear (&saved_def);
+  bitmap_clear (&saved_use);
+  bitmap_clear (&all_blocks);

 }
 
 
 \f
 /*----------------------------------------------------------------------------
 }
 
 
 \f
 /*----------------------------------------------------------------------------

-   LIVE REGISTERS
-
-   Find the locations in the function where any use of a pseudo can
-   reach in the backwards direction.  In and out bitvectors are built
-   for each basic block.  The regnum is used to index into these sets.
-   See df.h for details.
-   ----------------------------------------------------------------------------*/
+   LIVE AND MUST-INITIALIZED REGISTERS.
+
+   This problem first computes the IN and OUT bitvectors for the
+   must-initialized registers problems, which is a forward problem.
+   It gives the set of registers for which we MUST have an available
+   definition on any path from the entry block to the entry/exit of
+   a basic block.  Sets generate a definition, while clobbers kill
+   a definition.
+
+   In and out bitvectors are built for each basic block and are indexed by
+   regnum (see df.h for details).  In and out bitvectors in struct
+   df_live_bb_info actually refers to the must-initialized problem;
+
+   Then, the in and out sets for the LIVE problem itself are computed.
+   These are the logical AND of the IN and OUT sets from the LR problem
+   and the must-initialized problem.
+----------------------------------------------------------------------------*/

 
 /* Private data used to verify the solution for this problem.  */
 
 /* Private data used to verify the solution for this problem.  */

-struct df_lr_problem_data
+struct df_live_problem_data

 {
 {

-  bitmap *in;
-  bitmap *out;
+  bitmap_head *in;
+  bitmap_head *out;
+  /* An obstack for the bitmaps we need for this problem.  */
+  bitmap_obstack live_bitmaps;

 };
 
 };
 

+/* Scratch var used by transfer functions.  This is used to implement
+   an optimization to reduce the amount of space used to compute the
+   combined lr and live analysis.  */
+static bitmap_head df_live_scratch;

 
 

-/* Set basic block info.  */
-
-static void
-df_lr_set_bb_info (unsigned int index, 
-                  struct df_lr_bb_info *bb_info)
-{
-  gcc_assert (df_lr);
-  gcc_assert (index < df_lr->block_info_size);
-  df_lr->block_info[index] = bb_info;
-}

 
 

- 

 /* Free basic block info.  */
 
 static void
 /* Free basic block info.  */
 
 static void

-df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
+df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,

                    void *vbb_info)
 {
                    void *vbb_info)
 {

-  struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
+  struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;

   if (bb_info)
     {
   if (bb_info)
     {

-      BITMAP_FREE (bb_info->use);
-      BITMAP_FREE (bb_info->def);
-      if (bb_info->in == bb_info->top)
-        bb_info->top = NULL;
-      else
-       {
-          BITMAP_FREE (bb_info->top);
-          BITMAP_FREE (bb_info->ause);
-          BITMAP_FREE (bb_info->adef);
-       }
-      BITMAP_FREE (bb_info->in);
-      BITMAP_FREE (bb_info->out);
-      pool_free (df_lr->block_pool, bb_info);
+      bitmap_clear (&bb_info->gen);
+      bitmap_clear (&bb_info->kill);
+      bitmap_clear (&bb_info->in);
+      bitmap_clear (&bb_info->out);

     }
 }
 
 
     }
 }
 
 

-/* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are

    not touched unless the block is new.  */
 
    not touched unless the block is new.  */
 

-static void 
-df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
+static void
+df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 {
   unsigned int bb_index;
   bitmap_iterator bi;

+  struct df_live_problem_data *problem_data;

 
 

-  if (!df_lr->block_pool)
-    df_lr->block_pool = create_alloc_pool ("df_lr_block pool", 
-                                          sizeof (struct df_lr_bb_info), 50);
-
-  df_grow_bb_info (df_lr);
+  if (df_live->problem_data)
+    problem_data = (struct df_live_problem_data *) df_live->problem_data;
+  else
+    {
+      problem_data = XNEW (struct df_live_problem_data);
+      df_live->problem_data = problem_data;

 
 

-  EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
+      problem_data->out = NULL;
+      problem_data->in = NULL;
+      bitmap_obstack_initialize (&problem_data->live_bitmaps);
+      bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
+    }
+
+  df_grow_bb_info (df_live);
+
+  EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)

     {
     {

-      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
-      if (bb_info)
-       { 
-         bitmap_clear (bb_info->def);
-         bitmap_clear (bb_info->use);
-         if (bb_info->adef)
-           {
-             bitmap_clear (bb_info->adef);
-             bitmap_clear (bb_info->ause);
-           }
+      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
+      
+      /* When bitmaps are already initialized, just clear them.  */
+      if (bb_info->kill.obstack)
+       {
+         bitmap_clear (&bb_info->kill);
+         bitmap_clear (&bb_info->gen);

        }
       else
        }
       else

-       { 
-         bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
-         df_lr_set_bb_info (bb_index, bb_info);
-         bb_info->use = BITMAP_ALLOC (NULL);
-         bb_info->def = BITMAP_ALLOC (NULL);
-         bb_info->in = BITMAP_ALLOC (NULL);
-         bb_info->out = BITMAP_ALLOC (NULL);
-          bb_info->top = bb_info->in;
-          bb_info->adef = NULL;
-          bb_info->ause = NULL;
+       {
+         bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
+         bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
+         bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
+         bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);

        }
     }
        }
     }

-
-  df_lr->optional_p = false;
+  df_live->optional_p = (optimize <= 1);

 }
 
 
 /* Reset the global solution for recalculation.  */
 
 }
 
 
 /* Reset the global solution for recalculation.  */
 

-static void 
-df_lr_reset (bitmap all_blocks)
+static void
+df_live_reset (bitmap all_blocks)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
 {
   unsigned int bb_index;
   bitmap_iterator bi;
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {

-      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);

       gcc_assert (bb_info);
       gcc_assert (bb_info);

-      bitmap_clear (bb_info->in);
-      bitmap_clear (bb_info->out);
-      bitmap_clear (bb_info->top);
+      bitmap_clear (&bb_info->in);
+      bitmap_clear (&bb_info->out);

     }
 }
 
 
     }
 }
 
 

-/* Compute local live register info for basic block BB.  */
+/* Compute local uninitialized register info for basic block BB.  */

 
 static void
 
 static void

-df_lr_bb_local_compute (unsigned int bb_index)
+df_live_bb_local_compute (unsigned int bb_index)

 {
   basic_block bb = BASIC_BLOCK (bb_index);
 {
   basic_block bb = BASIC_BLOCK (bb_index);

-  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);

   rtx insn;
   rtx insn;

-  struct df_ref **def_rec;
-  struct df_ref **use_rec;
+  df_ref *def_rec;
+  int luid = 0;

 
 

-  /* Process the registers set in an exception handler.  */
-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+  FOR_BB_INSNS (bb, insn)

     {
     {

-      struct df_ref *def = *def_rec;
-      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+      unsigned int uid = INSN_UID (insn);
+      struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
+
+      /* Inserting labels does not always trigger the incremental
+        rescanning.  */
+      if (!insn_info)

        {
        {

-         unsigned int dregno = DF_REF_REGNO (def);
-         bitmap_set_bit (bb_info->def, dregno);
-         bitmap_clear_bit (bb_info->use, dregno);
+         gcc_assert (!INSN_P (insn));
+         insn_info = df_insn_create_insn_record (insn);

        }
        }

-    }
-
-  /* Process the hardware registers that are always live.  */
-  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
-    {
-      struct df_ref *use = *use_rec;
-      /* Add use to set of uses in this BB.  */
-      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
-       bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
-    }
-
-  FOR_BB_INSNS_REVERSE (bb, insn)
-    {
-      unsigned int uid = INSN_UID (insn);

 
 

+      DF_INSN_INFO_LUID (insn_info) = luid;

       if (!INSN_P (insn))
       if (!INSN_P (insn))

-       continue;       
+       continue;

 
 

-      if (CALL_P (insn))
-       {
-         for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
-           {
-             struct df_ref *def = *def_rec;
-             unsigned int dregno = DF_REF_REGNO (def);
-             
-             if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
-               {
-                 if (dregno >= FIRST_PSEUDO_REGISTER
-                     || !(SIBLING_CALL_P (insn)
-                          && bitmap_bit_p (df->exit_block_uses, dregno)
-                          && !refers_to_regno_p (dregno, dregno+1,
-                                                 current_function_return_rtx,
-                                                 (rtx *)0)))
-                   {
-                     /* If the def is to only part of the reg, it does
-                        not kill the other defs that reach here.  */
-                     if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-                       {
-                         bitmap_set_bit (bb_info->def, dregno);
-                         bitmap_clear_bit (bb_info->use, dregno);
-                       }
-                   }
-               }
-             else
-               /* This is the return value.  */
-               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-                 {
-                   bitmap_set_bit (bb_info->def, dregno);
-                   bitmap_clear_bit (bb_info->use, dregno);
-                 }
-           }
-       }
-      else
+      luid++;
+      for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)

        {
        {

-         for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
-           {
-             struct df_ref *def = *def_rec;
-             /* If the def is to only part of the reg, it does
-                    not kill the other defs that reach here.  */
-             if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-               {
-                 unsigned int dregno = DF_REF_REGNO (def);
-                 bitmap_set_bit (bb_info->def, dregno);
-                 bitmap_clear_bit (bb_info->use, dregno);
-               }
-           }
-       }
+         df_ref def = *def_rec;
+         unsigned int regno = DF_REF_REGNO (def);

 
 

-      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
-       {
-         struct df_ref *use = *use_rec;
-         /* Add use to set of uses in this BB.  */
-         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
+         if (DF_REF_FLAGS_IS_SET (def,
+                                  DF_REF_PARTIAL | DF_REF_CONDITIONAL))
+           /* All partial or conditional def
+              seen are included in the gen set. */
+           bitmap_set_bit (&bb_info->gen, regno);
+         else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
+           /* Only must clobbers for the entire reg destroy the
+              value.  */
+           bitmap_set_bit (&bb_info->kill, regno);
+         else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
+           bitmap_set_bit (&bb_info->gen, regno);

        }
     }
        }
     }

-  /* Process the registers set in an exception handler.  */
+

   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
     {
   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
     {

-      struct df_ref *def = *def_rec;
-      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
-         && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
-       {
-         unsigned int dregno = DF_REF_REGNO (def);
-         if (bb_info->adef == NULL)
-           {
-             gcc_assert (bb_info->ause == NULL);
-             gcc_assert (bb_info->top == bb_info->in);
-             bb_info->adef = BITMAP_ALLOC (NULL);
-             bb_info->ause = BITMAP_ALLOC (NULL);
-             bb_info->top = BITMAP_ALLOC (NULL);
-           }
-         bitmap_set_bit (bb_info->adef, dregno);
-       }
-    }
-  
-#ifdef EH_USES
-  /* Process the uses that are live into an exception handler.  */
-  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
-    {
-      struct df_ref *use = *use_rec;
-      /* Add use to set of uses in this BB.  */
-      if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
-       {
-         if (bb_info->adef == NULL)
-           {
-             gcc_assert (bb_info->ause == NULL);
-             gcc_assert (bb_info->top == bb_info->in);
-             bb_info->adef = BITMAP_ALLOC (NULL);
-             bb_info->ause = BITMAP_ALLOC (NULL);
-             bb_info->top = BITMAP_ALLOC (NULL);
-           }
-         bitmap_set_bit (bb_info->ause, DF_REF_REGNO (use));
-       }
+      df_ref def = *def_rec;
+      bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));

     }
     }

-#endif
-
-  /* If the df_live problem is not defined, such as at -O0 and -O1, we
-     still need to keep the luids up to date.  This is normally done
-     in the df_live problem since this problem has a forwards
-     scan.  */
-  if (!df_live)
-    df_recompute_luids (bb);

 }
 
 
 }
 
 

-/* Compute local live register info for each basic block within BLOCKS.  */
+/* Compute local uninitialized register info.  */

 
 static void
 
 static void

-df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
+df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 {
   unsigned int bb_index;
   bitmap_iterator bi;

-    
-  bitmap_clear (df->hardware_regs_used);
-  
-  /* The all-important stack pointer must always be live.  */
-  bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
-  
-  /* Before reload, there are a few registers that must be forced
-     live everywhere -- which might not already be the case for
-     blocks within infinite loops.  */
-  if (!reload_completed)
-    {
-      /* Any reference to any pseudo before reload is a potential
-        reference of the frame pointer.  */
-      bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
-      
-#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
-      /* Pseudos with argument area equivalences may require
-        reloading via the argument pointer.  */
-      if (fixed_regs[ARG_POINTER_REGNUM])
-       bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
-#endif
-      
-      /* Any constant, or pseudo with constant equivalences, may
-        require reloading from memory using the pic register.  */
-      if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
-         && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
-       bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
-    }
-  
-  EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
+
+  df_grow_insn_info ();
+
+  EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
+                           0, bb_index, bi)

     {
     {

-      if (bb_index == EXIT_BLOCK)
-       {
-         /* The exit block is special for this problem and its bits are
-            computed from thin air.  */
-         struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
-         bitmap_copy (bb_info->use, df->exit_block_uses);
-       }
-      else
-       df_lr_bb_local_compute (bb_index);
+      df_live_bb_local_compute (bb_index);

     }
 
     }
 

-  bitmap_clear (df_lr->out_of_date_transfer_functions);
+  bitmap_clear (df_live->out_of_date_transfer_functions);

 }
 
 
 /* Initialize the solution vectors.  */
 
 }
 
 
 /* Initialize the solution vectors.  */
 

-static void 
-df_lr_init (bitmap all_blocks)
+static void
+df_live_init (bitmap all_blocks)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
 {
   unsigned int bb_index;
   bitmap_iterator bi;
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {

-      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
-      bitmap_copy (bb_info->in, bb_info->use);
-      bitmap_clear (bb_info->out);
+      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
+      struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
+
+      /* No register may reach a location where it is not used.  Thus
+        we trim the rr result to the places where it is used.  */
+      bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
+      bitmap_clear (&bb_info->in);

     }
 }
 
     }
 }
 

+/* Forward confluence function that ignores fake edges.  */

 
 

-/* Confluence function that processes infinite loops.  This might be a
-   noreturn function that throws.  And even if it isn't, getting the
-   unwind info right helps debugging.  */
-static void
-df_lr_confluence_0 (basic_block bb)
+static bool
+df_live_confluence_n (edge e)

 {
 {

-  bitmap op1 = df_lr_get_bb_info (bb->index)->out;
-  if (bb != EXIT_BLOCK_PTR)
-    bitmap_copy (op1, df->hardware_regs_used);
-} 
+  bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
+  bitmap op2 = &df_live_get_bb_info (e->src->index)->out;

 
 

+  if (e->flags & EDGE_FAKE)
+    return false;

 
 

-/* Confluence function that ignores fake edges.  */
-
-static void
-df_lr_confluence_n (edge e)
-{
-  bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
-  bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
- 
-  /* Call-clobbered registers die across exception and call edges.  */
-  /* ??? Abnormal call edges ignored for the moment, as this gets
-     confused by sibling call edges, which crashes reg-stack.  */
-  if (e->flags & EDGE_EH)
-    bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
-  else
-    bitmap_ior_into (op1, op2);
-
-  bitmap_ior_into (op1, df->hardware_regs_used);
-} 
+  return bitmap_ior_into (op1, op2);
+}

 
 
 
 

-/* Transfer function.  */
+/* Transfer function for the forwards must-initialized problem.  */

 
 static bool
 
 static bool

-df_lr_transfer_function (int bb_index)
+df_live_transfer_function (int bb_index)

 {
 {

-  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
-  bitmap in = bb_info->in;
-  bitmap out = bb_info->out;
-  bitmap use = bb_info->use;
-  bitmap def = bb_info->def;
-  bitmap top = bb_info->top;
-  bitmap ause = bb_info->ause;
-  bitmap adef = bb_info->adef;
-  bool changed;
-
-  changed = bitmap_ior_and_compl (top, use, out, def);
-  if (in != top)
-    {
-      gcc_assert (ause && adef);
-      changed |= bitmap_ior_and_compl (in, ause, top, adef);
-    }
-
-  return changed;
+  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
+  struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
+  bitmap in = &bb_info->in;
+  bitmap out = &bb_info->out;
+  bitmap gen = &bb_info->gen;
+  bitmap kill = &bb_info->kill;
+
+  /* We need to use a scratch set here so that the value returned from this
+     function invocation properly reflects whether the sets changed in a
+     significant way; i.e. not just because the lr set was anded in.  */
+  bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
+  /* No register may reach a location where it is not used.  Thus
+     we trim the rr result to the places where it is used.  */
+  bitmap_and_into (in, &bb_lr_info->in);
+
+  return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);

 }
 
 
 }
 
 

-/* Run the fast dce as a side effect of building LR.  */
+/* And the LR info with the must-initialized registers, to produce the LIVE info.  */

 
 static void
 
 static void

-df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
+df_live_finalize (bitmap all_blocks)

 {
 {

-  if (df->changeable_flags & DF_LR_RUN_DCE)
+
+  if (df_live->solutions_dirty)

     {
     {

-      run_fast_df_dce ();
-      if (df_lr->problem_data && df_lr->solutions_dirty)
+      bitmap_iterator bi;
+      unsigned int bb_index;
+
+      EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)

        {
        {

-         /* If we are here, then it is because we are both verifying
-         the solution and the dce changed the function.  In that case
-         the verification info built will be wrong.  So we leave the
-         dirty flag true so that the verifier will skip the checking
-         part and just clean up.*/
-         df_lr->solutions_dirty = true;
+         struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
+         struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
+
+         /* No register may reach a location where it is not used.  Thus
+            we trim the rr result to the places where it is used.  */
+         bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
+         bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);

        }
        }

-      else
-       df_lr->solutions_dirty = false;
+
+      df_live->solutions_dirty = false;

     }
     }

-  else
-    df_lr->solutions_dirty = false;

 }
 
 
 /* Free all storage associated with the problem.  */
 
 static void
 }
 
 
 /* Free all storage associated with the problem.  */
 
 static void

-df_lr_free (void)
+df_live_free (void)

 {
 {

-  if (df_lr->block_info)
+  struct df_live_problem_data *problem_data
+    = (struct df_live_problem_data *) df_live->problem_data;
+  if (df_live->block_info)

     {
     {

-      unsigned int i;
-      for (i = 0; i < df_lr->block_info_size; i++)
-       {
-         struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
-         if (bb_info)
-           {
-             BITMAP_FREE (bb_info->use);
-             BITMAP_FREE (bb_info->def);
-             if (bb_info->in == bb_info->top)
-               bb_info->top = NULL;
-             else
-               {
-                 BITMAP_FREE (bb_info->top);
-                  BITMAP_FREE (bb_info->ause);
-                  BITMAP_FREE (bb_info->adef);
-               }
-             BITMAP_FREE (bb_info->in);
-             BITMAP_FREE (bb_info->out);
-           }
-       }
-      free_alloc_pool (df_lr->block_pool);
-      
-      df_lr->block_info_size = 0;
-      free (df_lr->block_info);
+      df_live->block_info_size = 0;
+      free (df_live->block_info);
+      df_live->block_info = NULL;
+      bitmap_clear (&df_live_scratch);
+      bitmap_obstack_release (&problem_data->live_bitmaps);
+      free (problem_data);
+      df_live->problem_data = NULL;

     }
     }

-
-  BITMAP_FREE (df_lr->out_of_date_transfer_functions);
-  free (df_lr);
+  BITMAP_FREE (df_live->out_of_date_transfer_functions);
+  free (df_live);

 }
 
 
 /* Debugging info at top of bb.  */
 
 static void
 }
 
 
 /* Debugging info at top of bb.  */
 
 static void

-df_lr_top_dump (basic_block bb, FILE *file)
+df_live_top_dump (basic_block bb, FILE *file)

 {
 {

-  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
-  struct df_lr_problem_data *problem_data;
-  if (!bb_info || !bb_info->in)
+  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
+  struct df_live_problem_data *problem_data;
+
+  if (!bb_info)

     return;
     return;

-      
-  fprintf (file, ";; lr  in  \t");
-  df_print_regset (file, bb_info->in);
-  if (df_lr->problem_data)
+
+  fprintf (file, ";; live  in  \t");
+  df_print_regset (file, &bb_info->in);
+  if (df_live->problem_data)

     {
     {

-      problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
-      fprintf (file, ";;  old in  \t");
-      df_print_regset (file, problem_data->in[bb->index]);
+      problem_data = (struct df_live_problem_data *)df_live->problem_data;
+      if (problem_data->in)
+       {
+         fprintf (file, ";;  old in  \t");
+         df_print_regset (file, &problem_data->in[bb->index]);
+       }

     }
     }

-  fprintf (file, ";; lr  use \t");
-  df_print_regset (file, bb_info->use);
-  fprintf (file, ";; lr  def \t");
-  df_print_regset (file, bb_info->def);
-}  
+  fprintf (file, ";; live  gen \t");
+  df_print_regset (file, &bb_info->gen);
+  fprintf (file, ";; live  kill\t");
+  df_print_regset (file, &bb_info->kill);
+}

 
 
 /* Debugging info at bottom of bb.  */
 
 static void
 
 
 /* Debugging info at bottom of bb.  */
 
 static void

-df_lr_bottom_dump (basic_block bb, FILE *file)
+df_live_bottom_dump (basic_block bb, FILE *file)

 {
 {

-  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
-  struct df_lr_problem_data *problem_data;
-  if (!bb_info || !bb_info->out)
+  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
+  struct df_live_problem_data *problem_data;
+
+  if (!bb_info)

     return;
     return;

-  
-  fprintf (file, ";; lr  out \t");
-  df_print_regset (file, bb_info->out);
-  if (df_lr->problem_data)
+
+  fprintf (file, ";; live  out \t");
+  df_print_regset (file, &bb_info->out);
+  if (df_live->problem_data)

     {
     {

-      problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
-      fprintf (file, ";;  old out  \t");
-      df_print_regset (file, problem_data->out[bb->index]);
+      problem_data = (struct df_live_problem_data *)df_live->problem_data;
+      if (problem_data->out)
+       {
+         fprintf (file, ";;  old out  \t");
+         df_print_regset (file, &problem_data->out[bb->index]);
+       }

     }
     }

-}  
+}

 
 
 /* Build the datastructure to verify that the solution to the dataflow
    equations is not dirty.  */
 
 static void
 
 
 /* Build the datastructure to verify that the solution to the dataflow
    equations is not dirty.  */
 
 static void

-df_lr_verify_solution_start (void)
+df_live_verify_solution_start (void)

 {
   basic_block bb;
 {
   basic_block bb;

-  struct df_lr_problem_data *problem_data;
-  if (df_lr->solutions_dirty)
-    {
-      df_lr->problem_data = NULL;
-      return;
-    }
+  struct df_live_problem_data *problem_data;
+  if (df_live->solutions_dirty)
+    return;

 
 

-  /* Set it true so that the solution is recomputed.  */ 
-  df_lr->solutions_dirty = true;
+  /* Set it true so that the solution is recomputed.  */
+  df_live->solutions_dirty = true;

 
 

-  problem_data = XNEW (struct df_lr_problem_data);
-  df_lr->problem_data = problem_data;
-  problem_data->in = XNEWVEC (bitmap, last_basic_block);
-  problem_data->out = XNEWVEC (bitmap, last_basic_block);
+  problem_data = (struct df_live_problem_data *)df_live->problem_data;
+  problem_data->in = XNEWVEC (bitmap_head, last_basic_block);
+  problem_data->out = XNEWVEC (bitmap_head, last_basic_block);

 
   FOR_ALL_BB (bb)
     {
 
   FOR_ALL_BB (bb)
     {

-      problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
-      problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
-      bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
-      bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
+      bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
+      bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
+      bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
+      bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));

     }
 }
 
     }
 }
 


@@ -1769,72 +1679,67 @@ df_lr_verify_solution_start (void)
    equations.  */
 
 static void
    equations.  */
 
 static void

-df_lr_verify_solution_end (void)
+df_live_verify_solution_end (void)

 {
 {

-  struct df_lr_problem_data *problem_data;
+  struct df_live_problem_data *problem_data;

   basic_block bb;
 
   basic_block bb;
 

-  if (df_lr->problem_data == NULL)
+  problem_data = (struct df_live_problem_data *)df_live->problem_data;
+  if (!problem_data->out)

     return;
 
     return;
 

-  problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
-
-  if (df_lr->solutions_dirty)
-    /* Do not check if the solution is still dirty.  See the comment
-       in df_lr_local_finalize for details.  */
-    df_lr->solutions_dirty = false;
-  else
-    FOR_ALL_BB (bb)
-      {
-       if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
-           || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
-         {
-           /*df_dump (stderr);*/
-           gcc_unreachable ();
-         }
-      }
+  FOR_ALL_BB (bb)
+    {
+      if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
+         || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
+       {
+         /*df_dump (stderr);*/
+         gcc_unreachable ();
+       }
+    }

 
   /* Cannot delete them immediately because you may want to dump them
      if the comparison fails.  */
   FOR_ALL_BB (bb)
     {
 
   /* Cannot delete them immediately because you may want to dump them
      if the comparison fails.  */
   FOR_ALL_BB (bb)
     {

-      BITMAP_FREE (problem_data->in[bb->index]);
-      BITMAP_FREE (problem_data->out[bb->index]);
+      bitmap_clear (&problem_data->in[bb->index]);
+      bitmap_clear (&problem_data->out[bb->index]);

     }
 
   free (problem_data->in);
   free (problem_data->out);
   free (problem_data);
     }
 
   free (problem_data->in);
   free (problem_data->out);
   free (problem_data);

-  df_lr->problem_data = NULL;
+  df_live->problem_data = NULL;

 }
 
 
 /* All of the information associated with every instance of the problem.  */
 
 }
 
 
 /* All of the information associated with every instance of the problem.  */
 

-static struct df_problem problem_LR =
+static struct df_problem problem_LIVE =

 {
 {

-  DF_LR,                      /* Problem id.  */
-  DF_BACKWARD,                /* Direction.  */
-  df_lr_alloc,                /* Allocate the problem specific data.  */
-  df_lr_reset,                /* Reset global information.  */
-  df_lr_free_bb_info,         /* Free basic block info.  */
-  df_lr_local_compute,        /* Local compute function.  */
-  df_lr_init,                 /* Init the solution specific data.  */
-  df_worklist_dataflow,       /* Worklist solver.  */
-  df_lr_confluence_0,         /* Confluence operator 0.  */ 
-  df_lr_confluence_n,         /* Confluence operator n.  */ 
-  df_lr_transfer_function,    /* Transfer function.  */
-  df_lr_local_finalize,       /* Finalize function.  */
-  df_lr_free,                 /* Free all of the problem information.  */
-  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
-  NULL,                       /* Debugging.  */
-  df_lr_top_dump,             /* Debugging start block.  */
-  df_lr_bottom_dump,          /* Debugging end block.  */
-  df_lr_verify_solution_start,/* Incremental solution verify start.  */
-  df_lr_verify_solution_end,  /* Incremental solution verify end.  */
-  NULL,                       /* Dependent problem.  */
-  TV_DF_LR,                   /* Timing variable.  */ 
-  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
+  DF_LIVE,                      /* Problem id.  */
+  DF_FORWARD,                   /* Direction.  */
+  df_live_alloc,                /* Allocate the problem specific data.  */
+  df_live_reset,                /* Reset global information.  */
+  df_live_free_bb_info,         /* Free basic block info.  */
+  df_live_local_compute,        /* Local compute function.  */
+  df_live_init,                 /* Init the solution specific data.  */
+  df_worklist_dataflow,         /* Worklist solver.  */
+  NULL,                         /* Confluence operator 0.  */
+  df_live_confluence_n,         /* Confluence operator n.  */
+  df_live_transfer_function,    /* Transfer function.  */
+  df_live_finalize,             /* Finalize function.  */
+  df_live_free,                 /* Free all of the problem information.  */
+  df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
+  NULL,                         /* Debugging.  */
+  df_live_top_dump,             /* Debugging start block.  */
+  df_live_bottom_dump,          /* Debugging end block.  */
+  df_live_verify_solution_start,/* Incremental solution verify start.  */
+  df_live_verify_solution_end,  /* Incremental solution verify end.  */
+  &problem_LR,                  /* Dependent problem.  */
+  sizeof (struct df_live_bb_info),/* Size of entry of block_info array.  */
+  TV_DF_LIVE,                   /* Timing variable.  */
+  false                         /* Reset blocks on dropping out of blocks_to_analyze.  */

 };
 
 
 };
 
 


@@ -1843,12 +1748,25 @@ static struct df_problem problem_LR =
    solution.  */
 
 void
    solution.  */
 
 void

-df_lr_add_problem (void)
+df_live_add_problem (void)

 {
 {

-  df_add_problem (&problem_LR);
+  df_add_problem (&problem_LIVE);

   /* These will be initialized when df_scan_blocks processes each
      block.  */
   /* These will be initialized when df_scan_blocks processes each
      block.  */

-  df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
+  df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
+}
+
+
+/* Set all of the blocks as dirty.  This needs to be done if this
+   problem is added after all of the insns have been scanned.  */
+
+void
+df_live_set_all_dirty (void)
+{
+  basic_block bb;
+  FOR_ALL_BB (bb)
+    bitmap_set_bit (df_live->out_of_date_transfer_functions,
+                   bb->index);

 }
 
 
 }
 
 


@@ -1856,70 +1774,43 @@ df_lr_add_problem (void)
    correct.  */
 
 void
    correct.  */
 
 void

-df_lr_verify_transfer_functions (void)
+df_live_verify_transfer_functions (void)

 {
   basic_block bb;
 {
   basic_block bb;

-  bitmap saved_def;
-  bitmap saved_use;
-  bitmap saved_adef;
-  bitmap saved_ause;
-  bitmap all_blocks;
-  bool need_as;
+  bitmap_head saved_gen;
+  bitmap_head saved_kill;
+  bitmap_head all_blocks;

 
   if (!df)
     return;
 
 
   if (!df)
     return;
 

-  saved_def = BITMAP_ALLOC (NULL);
-  saved_use = BITMAP_ALLOC (NULL);
-  saved_adef = BITMAP_ALLOC (NULL);
-  saved_ause = BITMAP_ALLOC (NULL);
-  all_blocks = BITMAP_ALLOC (NULL);
+  bitmap_initialize (&saved_gen, &bitmap_default_obstack);
+  bitmap_initialize (&saved_kill, &bitmap_default_obstack);
+  bitmap_initialize (&all_blocks, &bitmap_default_obstack);
+
+  df_grow_insn_info ();

 
   FOR_ALL_BB (bb)
     {
 
   FOR_ALL_BB (bb)
     {

-      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
-      bitmap_set_bit (all_blocks, bb->index);
+      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
+      bitmap_set_bit (&all_blocks, bb->index);

 
       if (bb_info)
        {
          /* Make a copy of the transfer functions and then compute
             new ones to see if the transfer functions have
             changed.  */
 
       if (bb_info)
        {
          /* Make a copy of the transfer functions and then compute
             new ones to see if the transfer functions have
             changed.  */

-         if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions, 
+         if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,

                             bb->index))
            {
                             bb->index))
            {

-             bitmap_copy (saved_def, bb_info->def);
-             bitmap_copy (saved_use, bb_info->use);
-             bitmap_clear (bb_info->def);
-             bitmap_clear (bb_info->use);
-
-             if (bb_info->adef)
-               {
-                 need_as = true;
-                 bitmap_copy (saved_adef, bb_info->adef);
-                 bitmap_copy (saved_ause, bb_info->ause);
-                 bitmap_clear (bb_info->adef);
-                 bitmap_clear (bb_info->ause);
-               }
-             else
-               need_as = false;
+             bitmap_copy (&saved_gen, &bb_info->gen);
+             bitmap_copy (&saved_kill, &bb_info->kill);
+             bitmap_clear (&bb_info->gen);
+             bitmap_clear (&bb_info->kill);

 
 

-             df_lr_bb_local_compute (bb->index);
-             gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
-             gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
-
-             if (need_as)
-               {
-                 gcc_assert (bb_info->adef);
-                 gcc_assert (bb_info->ause);
-                 gcc_assert (bitmap_equal_p (saved_adef, bb_info->adef));
-                 gcc_assert (bitmap_equal_p (saved_ause, bb_info->ause));
-               }
-             else
-               {
-                 gcc_assert (!bb_info->adef);
-                 gcc_assert (!bb_info->ause);
-               }
+             df_live_bb_local_compute (bb->index);
+             gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
+             gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));

            }
        }
       else
            }
        }
       else


@@ -1927,7 +1818,7 @@ df_lr_verify_transfer_functions (void)
          /* If we do not have basic block info, the block must be in
             the list of dirty blocks or else some one has added a
             block behind our backs. */
          /* If we do not have basic block info, the block must be in
             the list of dirty blocks or else some one has added a
             block behind our backs. */

-         gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions, 
+         gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,

                                    bb->index));
        }
       /* Make sure no one created a block without following
                                    bb->index));
        }
       /* Make sure no one created a block without following


@@ -1936,457 +1827,446 @@ df_lr_verify_transfer_functions (void)
     }
 
   /* Make sure there are no dirty bits in blocks that have been deleted.  */
     }
 
   /* Make sure there are no dirty bits in blocks that have been deleted.  */

-  gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions, 
-                                        all_blocks)); 
-
-  BITMAP_FREE (saved_def);
-  BITMAP_FREE (saved_use);
-  BITMAP_FREE (saved_adef);
-  BITMAP_FREE (saved_ause);
-  BITMAP_FREE (all_blocks);
+  gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
+                                        &all_blocks));
+  bitmap_clear (&saved_gen);
+  bitmap_clear (&saved_kill);
+  bitmap_clear (&all_blocks);

 }
 }

-
-

 \f
 /*----------------------------------------------------------------------------
 \f
 /*----------------------------------------------------------------------------

-   COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
+   CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS

 
 

-   First find the set of uses for registers that are reachable from
-   the entry block without passing thru a definition.  In and out
-   bitvectors are built for each basic block.  The regnum is used to
-   index into these sets.  See df.h for details.
+   Link either the defs to the uses and / or the uses to the defs.

 
 

-   Then the in and out sets here are the anded results of the in and
-   out sets from the lr and ur
-   problems. 
+   These problems are set up like the other dataflow problems so that
+   they nicely fit into the framework.  They are much simpler and only
+   involve a single traversal of instructions and an examination of
+   the reaching defs information (the dependent problem).

 ----------------------------------------------------------------------------*/
 
 ----------------------------------------------------------------------------*/
 

-/* Private data used to verify the solution for this problem.  */
-struct df_live_problem_data
-{
-  bitmap *in;
-  bitmap *out;
-};
-
+#define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))

 
 

-/* Set basic block info.  */
+/* Create a du or ud chain from SRC to DST and link it into SRC.   */

 
 

-static void
-df_live_set_bb_info (unsigned int index, 
-                  struct df_live_bb_info *bb_info)
+struct df_link *
+df_chain_create (df_ref src, df_ref dst)

 {
 {

-  gcc_assert (df_live);
-  gcc_assert (index < df_live->block_info_size);
-  df_live->block_info[index] = bb_info;
-}
+  struct df_link *head = DF_REF_CHAIN (src);
+  struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);

 
 

+  DF_REF_CHAIN (src) = link;
+  link->next = head;
+  link->ref = dst;
+  return link;
+}

 
 

-/* Free basic block info.  */

 
 

+/* Delete any du or ud chains that start at REF and point to
+   TARGET.  */

 static void
 static void

-df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
-                   void *vbb_info)
+df_chain_unlink_1 (df_ref ref, df_ref target)

 {
 {

-  struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
-  if (bb_info)
+  struct df_link *chain = DF_REF_CHAIN (ref);
+  struct df_link *prev = NULL;
+
+  while (chain)

     {
     {

-      BITMAP_FREE (bb_info->gen);
-      BITMAP_FREE (bb_info->kill);
-      BITMAP_FREE (bb_info->in);
-      BITMAP_FREE (bb_info->out);
-      pool_free (df_live->block_pool, bb_info);
+      if (chain->ref == target)
+       {
+         if (prev)
+           prev->next = chain->next;
+         else
+           DF_REF_CHAIN (ref) = chain->next;
+         pool_free (df_chain->block_pool, chain);
+         return;
+       }
+      prev = chain;
+      chain = chain->next;

     }
 }
 
 
     }
 }
 
 

-/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
-   not touched unless the block is new.  */
+/* Delete a du or ud chain that leave or point to REF.  */

 
 

-static void 
-df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
+void
+df_chain_unlink (df_ref ref)

 {
 {

-  unsigned int bb_index;
-  bitmap_iterator bi;
-
-  if (!df_live->block_pool)
-    df_live->block_pool = create_alloc_pool ("df_live_block pool", 
-                                          sizeof (struct df_live_bb_info), 100);
-
-  df_grow_bb_info (df_live);
-
-  EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
+  struct df_link *chain = DF_REF_CHAIN (ref);
+  while (chain)

     {
     {

-      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
-      if (bb_info)
-       { 
-         bitmap_clear (bb_info->kill);
-         bitmap_clear (bb_info->gen);
-       }
-      else
-       { 
-         bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
-         df_live_set_bb_info (bb_index, bb_info);
-         bb_info->kill = BITMAP_ALLOC (NULL);
-         bb_info->gen = BITMAP_ALLOC (NULL);
-         bb_info->in = BITMAP_ALLOC (NULL);
-         bb_info->out = BITMAP_ALLOC (NULL);
-       }
+      struct df_link *next = chain->next;
+      /* Delete the other side if it exists.  */
+      df_chain_unlink_1 (chain->ref, ref);
+      pool_free (df_chain->block_pool, chain);
+      chain = next;

     }
     }

-  df_live->optional_p = (optimize <= 1);
+  DF_REF_CHAIN (ref) = NULL;

 }
 
 
 }
 
 

-/* Reset the global solution for recalculation.  */
+/* Copy the du or ud chain starting at FROM_REF and attach it to
+   TO_REF.  */

 
 

-static void 
-df_live_reset (bitmap all_blocks)
+void
+df_chain_copy (df_ref to_ref,
+              struct df_link *from_ref)

 {
 {

-  unsigned int bb_index;
-  bitmap_iterator bi;
-
-  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+  while (from_ref)

     {
     {

-      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
-      gcc_assert (bb_info);
-      bitmap_clear (bb_info->in);
-      bitmap_clear (bb_info->out);
+      df_chain_create (to_ref, from_ref->ref);
+      from_ref = from_ref->next;

     }
 }
 
 
     }
 }
 
 

-/* Compute local uninitialized register info for basic block BB.  */
+/* Remove this problem from the stack of dataflow problems.  */

 
 static void
 
 static void

-df_live_bb_local_compute (unsigned int bb_index)
+df_chain_remove_problem (void)

 {
 {

-  basic_block bb = BASIC_BLOCK (bb_index);
-  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
-  rtx insn;
-  struct df_ref **def_rec;
-  int luid = 0;
+  bitmap_iterator bi;
+  unsigned int bb_index;

 
 

-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
-    {
-      struct df_ref *def = *def_rec;
-      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
-       bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
-    }
+  /* Wholesale destruction of the old chains.  */
+  if (df_chain->block_pool)
+    free_alloc_pool (df_chain->block_pool);

 
 

-  FOR_BB_INSNS (bb, insn)
+  EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)

     {
     {

-      unsigned int uid = INSN_UID (insn);
-      struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
+      rtx insn;
+      df_ref *def_rec;
+      df_ref *use_rec;
+      basic_block bb = BASIC_BLOCK (bb_index);

 
 

-      /* Inserting labels does not always trigger the incremental
-        rescanning.  */
-      if (!insn_info)
-       {
-         gcc_assert (!INSN_P (insn));
-         df_insn_create_insn_record (insn);
-       }
+      if (df_chain_problem_p (DF_DU_CHAIN))
+       for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
+         DF_REF_CHAIN (*def_rec) = NULL;
+      if (df_chain_problem_p (DF_UD_CHAIN))
+       for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
+         DF_REF_CHAIN (*use_rec) = NULL;

 
 

-      DF_INSN_LUID (insn) = luid;
-      if (!INSN_P (insn))
-       continue;
-
-      luid++;
-      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+      FOR_BB_INSNS (bb, insn)

        {
        {

-         struct df_ref *def = *def_rec;
-         unsigned int regno = DF_REF_REGNO (def);
+         unsigned int uid = INSN_UID (insn);

 
 

-         if (DF_REF_FLAGS_IS_SET (def,
-                                  DF_REF_PARTIAL | DF_REF_CONDITIONAL))
-           /* All partial or conditional def
-              seen are included in the gen set. */
-           bitmap_set_bit (bb_info->gen, regno);
-         else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
-           /* Only must clobbers for the entire reg destroy the
-              value.  */
-           bitmap_set_bit (bb_info->kill, regno);
-         else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
-           bitmap_set_bit (bb_info->gen, regno);
+         if (INSN_P (insn))
+           {
+             if (df_chain_problem_p (DF_DU_CHAIN))
+               for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+                 DF_REF_CHAIN (*def_rec) = NULL;
+             if (df_chain_problem_p (DF_UD_CHAIN))
+               {
+                 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+                   DF_REF_CHAIN (*use_rec) = NULL;
+                 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
+                   DF_REF_CHAIN (*use_rec) = NULL;
+               }
+           }

        }
     }
 
        }
     }
 

-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
-    {
-      struct df_ref *def = *def_rec;
-      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
-       bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
-    }
+  bitmap_clear (df_chain->out_of_date_transfer_functions);
+  df_chain->block_pool = NULL;

 }
 
 
 }
 
 

-/* Compute local uninitialized register info.  */
+/* Remove the chain problem completely.  */

 
 static void
 
 static void

-df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
+df_chain_fully_remove_problem (void)

 {
 {

-  unsigned int bb_index;
-  bitmap_iterator bi;
+  df_chain_remove_problem ();
+  BITMAP_FREE (df_chain->out_of_date_transfer_functions);
+  free (df_chain);
+}

 
 

-  df_grow_insn_info ();

 
 

-  EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 
-                           0, bb_index, bi)
-    {
-      df_live_bb_local_compute (bb_index);
-    }
+/* Create def-use or use-def chains.  */

 
 

-  bitmap_clear (df_live->out_of_date_transfer_functions);
+static void
+df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
+{
+  df_chain_remove_problem ();
+  df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
+                                        sizeof (struct df_link), 50);
+  df_chain->optional_p = true;

 }
 
 
 }
 
 

-/* Initialize the solution vectors.  */
+/* Reset all of the chains when the set of basic blocks changes.  */

 
 

-static void 
-df_live_init (bitmap all_blocks)
+static void
+df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)

 {
 {

-  unsigned int bb_index;
-  bitmap_iterator bi;
-
-  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
-    {
-      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
-
-      bitmap_copy (bb_info->out, bb_info->gen);
-      bitmap_clear (bb_info->in);
-    }
+  df_chain_remove_problem ();

 }
 
 }
 

-/* Confluence function that ignores fake edges.  */
+
+/* Create the chains for a list of USEs.  */

 
 static void
 
 static void

-df_live_confluence_n (edge e)
+df_chain_create_bb_process_use (bitmap local_rd,
+                               df_ref *use_rec,
+                               int top_flag)

 {
 {

-  bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
-  bitmap op2 = df_live_get_bb_info (e->src->index)->out;
- 
-  if (e->flags & EDGE_FAKE) 
-    return;
-
-  bitmap_ior_into (op1, op2);
-} 
+  bitmap_iterator bi;
+  unsigned int def_index;

 
 

+  while (*use_rec)
+    {
+      df_ref use = *use_rec;
+      unsigned int uregno = DF_REF_REGNO (use);
+      if ((!(df->changeable_flags & DF_NO_HARD_REGS))
+         || (uregno >= FIRST_PSEUDO_REGISTER))
+       {
+         /* Do not want to go through this for an uninitialized var.  */
+         int count = DF_DEFS_COUNT (uregno);
+         if (count)
+           {
+             if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
+               {
+                 unsigned int first_index = DF_DEFS_BEGIN (uregno);
+                 unsigned int last_index = first_index + count - 1;

 
 

-/* Transfer function.  */
+                 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
+                   {
+                     df_ref def;
+                     if (def_index > last_index)
+                       break;

 
 

-static bool
-df_live_transfer_function (int bb_index)
-{
-  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
-  bitmap in = bb_info->in;
-  bitmap out = bb_info->out;
-  bitmap gen = bb_info->gen;
-  bitmap kill = bb_info->kill;
+                     def = DF_DEFS_GET (def_index);
+                     if (df_chain_problem_p (DF_DU_CHAIN))
+                       df_chain_create (def, use);
+                     if (df_chain_problem_p (DF_UD_CHAIN))
+                       df_chain_create (use, def);
+                   }
+               }
+           }
+       }

 
 

-  return bitmap_ior_and_compl (out, gen, in, kill);
+      use_rec++;
+    }

 }
 
 
 }
 
 

-/* And the LR and UR info to produce the LIVE info.  */
+/* Create chains from reaching defs bitmaps for basic block BB.  */

 
 static void
 
 static void

-df_live_local_finalize (bitmap all_blocks)
+df_chain_create_bb (unsigned int bb_index)

 {
 {

+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
+  rtx insn;
+  bitmap_head cpy;

 
 

-  if (df_live->solutions_dirty)
-    {
-      bitmap_iterator bi;
-      unsigned int bb_index;
+  bitmap_initialize (&cpy, &bitmap_default_obstack);
+  bitmap_copy (&cpy, &bb_info->in);
+  bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);

 
 

-      EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
-       {
-         struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
-         struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
-         
-         /* No register may reach a location where it is not used.  Thus
-            we trim the rr result to the places where it is used.  */
-         bitmap_and_into (bb_live_info->in, bb_lr_info->in);
-         bitmap_and_into (bb_live_info->out, bb_lr_info->out);
-       }
-      
-      df_live->solutions_dirty = false;
-    }
-}
+  /* Since we are going forwards, process the artificial uses first
+     then the artificial defs second.  */

 
 

+#ifdef EH_USES
+  /* Create the chains for the artificial uses from the EH_USES at the
+     beginning of the block.  */

 
 

-/* Free all storage associated with the problem.  */
+  /* Artificials are only hard regs.  */
+  if (!(df->changeable_flags & DF_NO_HARD_REGS))
+    df_chain_create_bb_process_use (&cpy,
+                                   df_get_artificial_uses (bb->index),
+                                   DF_REF_AT_TOP);
+#endif

 
 

-static void
-df_live_free (void)
-{
-  if (df_live->block_info)
-    {
-      unsigned int i;
-      
-      for (i = 0; i < df_live->block_info_size; i++)
-       {
-         struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
-         if (bb_info)
-           {
-             BITMAP_FREE (bb_info->gen);
-             BITMAP_FREE (bb_info->kill);
-             BITMAP_FREE (bb_info->in);
-             BITMAP_FREE (bb_info->out);
-           }
-       }
-      
-      free_alloc_pool (df_live->block_pool);
-      df_live->block_info_size = 0;
-      free (df_live->block_info);
-    }
-  BITMAP_FREE (df_live->out_of_date_transfer_functions);
-  free (df_live);
-}
+  df_rd_simulate_artificial_defs_at_top (bb, &cpy);
+
+  /* Process the regular instructions next.  */
+  FOR_BB_INSNS (bb, insn)
+    if (INSN_P (insn))
+      {
+        unsigned int uid = INSN_UID (insn);

 
 

+        /* First scan the uses and link them up with the defs that remain
+          in the cpy vector.  */
+        df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
+        if (df->changeable_flags & DF_EQ_NOTES)
+         df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);

 
 

-/* Debugging info at top of bb.  */
+        /* Since we are going forwards, process the defs second.  */
+        df_rd_simulate_one_insn (bb, insn, &cpy);
+      }
+
+  /* Create the chains for the artificial uses of the hard registers
+     at the end of the block.  */
+  if (!(df->changeable_flags & DF_NO_HARD_REGS))
+    df_chain_create_bb_process_use (&cpy,
+                                   df_get_artificial_uses (bb->index),
+                                   0);
+
+  bitmap_clear (&cpy);
+}
+
+/* Create def-use chains from reaching use bitmaps for basic blocks
+   in BLOCKS.  */

 
 static void
 
 static void

-df_live_top_dump (basic_block bb, FILE *file)
+df_chain_finalize (bitmap all_blocks)

 {
 {

-  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
-  struct df_live_problem_data *problem_data;
+  unsigned int bb_index;
+  bitmap_iterator bi;

 
 

-  if (!bb_info || !bb_info->in)
-    return;
-      
-  fprintf (file, ";; live  in  \t");
-  df_print_regset (file, bb_info->in);
-  if (df_live->problem_data)
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)

     {
     {

-      problem_data = (struct df_live_problem_data *)df_live->problem_data;
-      fprintf (file, ";;  old in  \t");
-      df_print_regset (file, problem_data->in[bb->index]);
+      df_chain_create_bb (bb_index);

     }
     }

-  fprintf (file, ";; live  gen \t");
-  df_print_regset (file, bb_info->gen);
-  fprintf (file, ";; live  kill\t");
-  df_print_regset (file, bb_info->kill);

 }
 
 
 }
 
 

-/* Debugging info at bottom of bb.  */
+/* Free all storage associated with the problem.  */

 
 static void
 
 static void

-df_live_bottom_dump (basic_block bb, FILE *file)
+df_chain_free (void)

 {
 {

-  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
-  struct df_live_problem_data *problem_data;
-
-  if (!bb_info || !bb_info->out)
-    return;
-      
-  fprintf (file, ";; live  out \t");
-  df_print_regset (file, bb_info->out);
-  if (df_live->problem_data)
-    {
-      problem_data = (struct df_live_problem_data *)df_live->problem_data;
-      fprintf (file, ";;  old out  \t");
-      df_print_regset (file, problem_data->out[bb->index]);
-    }
+  free_alloc_pool (df_chain->block_pool);
+  BITMAP_FREE (df_chain->out_of_date_transfer_functions);
+  free (df_chain);

 }
 
 
 }
 
 

-/* Build the datastructure to verify that the solution to the dataflow
-   equations is not dirty.  */
+/* Debugging info.  */

 
 static void
 
 static void

-df_live_verify_solution_start (void)
+df_chain_top_dump (basic_block bb, FILE *file)

 {
 {

-  basic_block bb;
-  struct df_live_problem_data *problem_data;
-  if (df_live->solutions_dirty)
+  if (df_chain_problem_p (DF_DU_CHAIN))

     {
     {

-      df_live->problem_data = NULL;
-      return;
-    }
+      rtx insn;
+      df_ref *def_rec = df_get_artificial_defs (bb->index);
+      if (*def_rec)
+       {

 
 

-  /* Set it true so that the solution is recomputed.  */ 
-  df_live->solutions_dirty = true;
+         fprintf (file, ";;  DU chains for artificial defs\n");
+         while (*def_rec)
+           {
+             df_ref def = *def_rec;
+             fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
+             df_chain_dump (DF_REF_CHAIN (def), file);
+             fprintf (file, "\n");
+             def_rec++;
+           }
+       }

 
 

-  problem_data = XNEW (struct df_live_problem_data);
-  df_live->problem_data = problem_data;
-  problem_data->in = XNEWVEC (bitmap, last_basic_block);
-  problem_data->out = XNEWVEC (bitmap, last_basic_block);
+      FOR_BB_INSNS (bb, insn)
+       {
+         if (INSN_P (insn))
+           {
+             struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
+             def_rec = DF_INSN_INFO_DEFS (insn_info);
+             if (*def_rec)
+               {
+                 fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
+                          DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));

 
 

-  FOR_ALL_BB (bb)
-    {
-      problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
-      problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
-      bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
-      bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
+                 while (*def_rec)
+                   {
+                     df_ref def = *def_rec;
+                     fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
+                     if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
+                       fprintf (file, "read/write ");
+                     df_chain_dump (DF_REF_CHAIN (def), file);
+                     fprintf (file, "\n");
+                     def_rec++;
+                   }
+               }
+           }
+       }

     }
 }
 
 
     }
 }
 
 

-/* Compare the saved datastructure and the new solution to the dataflow
-   equations.  */
-

 static void
 static void

-df_live_verify_solution_end (void)
+df_chain_bottom_dump (basic_block bb, FILE *file)

 {
 {

-  struct df_live_problem_data *problem_data;
-  basic_block bb;
-
-  if (df_live->problem_data == NULL)
-    return;
-
-  problem_data = (struct df_live_problem_data *)df_live->problem_data;
-
-  FOR_ALL_BB (bb)
+  if (df_chain_problem_p (DF_UD_CHAIN))

     {
     {

-      if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
-         || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
+      rtx insn;
+      df_ref *use_rec = df_get_artificial_uses (bb->index);
+
+      if (*use_rec)

        {
        {

-         /*df_dump (stderr);*/
-         gcc_unreachable ();
+         fprintf (file, ";;  UD chains for artificial uses\n");
+         while (*use_rec)
+           {
+             df_ref use = *use_rec;
+             fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
+             df_chain_dump (DF_REF_CHAIN (use), file);
+             fprintf (file, "\n");
+             use_rec++;
+           }

        }
        }

-    }

 
 

-  /* Cannot delete them immediately because you may want to dump them
-     if the comparison fails.  */
-  FOR_ALL_BB (bb)
-    {
-      BITMAP_FREE (problem_data->in[bb->index]);
-      BITMAP_FREE (problem_data->out[bb->index]);
-    }
+      FOR_BB_INSNS (bb, insn)
+       {
+         if (INSN_P (insn))
+           {
+             struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
+             df_ref *eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
+             use_rec = DF_INSN_INFO_USES (insn_info);
+             if (*use_rec || *eq_use_rec)
+               {
+                 fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
+                          DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));

 
 

-  free (problem_data->in);
-  free (problem_data->out);
-  free (problem_data);
-  df_live->problem_data = NULL;
+                 while (*use_rec)
+                   {
+                     df_ref use = *use_rec;
+                     fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
+                     if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
+                       fprintf (file, "read/write ");
+                     df_chain_dump (DF_REF_CHAIN (use), file);
+                     fprintf (file, "\n");
+                     use_rec++;
+                   }
+                 while (*eq_use_rec)
+                   {
+                     df_ref use = *eq_use_rec;
+                     fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
+                     df_chain_dump (DF_REF_CHAIN (use), file);
+                     fprintf (file, "\n");
+                     eq_use_rec++;
+                   }
+               }
+           }
+       }
+    }

 }
 
 
 }
 
 

-/* All of the information associated with every instance of the problem.  */
-
-static struct df_problem problem_LIVE =
+static struct df_problem problem_CHAIN =

 {
 {

-  DF_LIVE,                      /* Problem id.  */
-  DF_FORWARD,                   /* Direction.  */
-  df_live_alloc,                /* Allocate the problem specific data.  */
-  df_live_reset,                /* Reset global information.  */
-  df_live_free_bb_info,         /* Free basic block info.  */
-  df_live_local_compute,        /* Local compute function.  */
-  df_live_init,                 /* Init the solution specific data.  */
-  df_worklist_dataflow,         /* Worklist solver.  */
-  NULL,                         /* Confluence operator 0.  */ 
-  df_live_confluence_n,         /* Confluence operator n.  */ 
-  df_live_transfer_function,    /* Transfer function.  */
-  df_live_local_finalize,       /* Finalize function.  */
-  df_live_free,                 /* Free all of the problem information.  */
-  df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
-  NULL,                         /* Debugging.  */
-  df_live_top_dump,             /* Debugging start block.  */
-  df_live_bottom_dump,          /* Debugging end block.  */
-  df_live_verify_solution_start,/* Incremental solution verify start.  */
-  df_live_verify_solution_end,  /* Incremental solution verify end.  */
-  &problem_LR,                  /* Dependent problem.  */
-  TV_DF_LIVE,                   /* Timing variable.  */
-  false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
+  DF_CHAIN,                   /* Problem id.  */
+  DF_NONE,                    /* Direction.  */
+  df_chain_alloc,             /* Allocate the problem specific data.  */
+  df_chain_reset,             /* Reset global information.  */
+  NULL,                       /* Free basic block info.  */
+  NULL,                       /* Local compute function.  */
+  NULL,                       /* Init the solution specific data.  */
+  NULL,                       /* Iterative solver.  */
+  NULL,                       /* Confluence operator 0.  */
+  NULL,                       /* Confluence operator n.  */
+  NULL,                       /* Transfer function.  */
+  df_chain_finalize,          /* Finalize function.  */
+  df_chain_free,              /* Free all of the problem information.  */
+  df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
+  NULL,                       /* Debugging.  */
+  df_chain_top_dump,          /* Debugging start block.  */
+  df_chain_bottom_dump,       /* Debugging end block.  */
+  NULL,                       /* Incremental solution verify start.  */
+  NULL,                       /* Incremental solution verify end.  */
+  &problem_RD,                /* Dependent problem.  */
+  sizeof (struct df_scan_bb_info),/* Size of entry of block_info array.  */
+  TV_DF_CHAIN,                /* Timing variable.  */
+  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */

 };
 
 
 };
 
 


@@ -2395,686 +2275,376 @@ static struct df_problem problem_LIVE =
    solution.  */
 
 void
    solution.  */
 
 void

-df_live_add_problem (void)
-{
-  df_add_problem (&problem_LIVE);
-  /* These will be initialized when df_scan_blocks processes each
-     block.  */
-  df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
-}
-
-
-/* Set all of the blocks as dirty.  This needs to be done if this
-   problem is added after all of the insns have been scanned.  */
-
-void
-df_live_set_all_dirty (void)
-{
-  basic_block bb;
-  FOR_ALL_BB (bb)
-    bitmap_set_bit (df_live->out_of_date_transfer_functions, 
-                   bb->index);
-}
-
-
-/* Verify that all of the lr related info is consistent and
-   correct.  */
-
-void
-df_live_verify_transfer_functions (void)
+df_chain_add_problem (unsigned int chain_flags)

 {
 {

-  basic_block bb;
-  bitmap saved_gen;
-  bitmap saved_kill;
-  bitmap all_blocks;
-
-  if (!df)
-    return;
-
-  saved_gen = BITMAP_ALLOC (NULL);
-  saved_kill = BITMAP_ALLOC (NULL);
-  all_blocks = BITMAP_ALLOC (NULL);
-
-  df_grow_insn_info ();
-
-  FOR_ALL_BB (bb)
-    {
-      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
-      bitmap_set_bit (all_blocks, bb->index);
-
-      if (bb_info)
-       {
-         /* Make a copy of the transfer functions and then compute
-            new ones to see if the transfer functions have
-            changed.  */
-         if (!bitmap_bit_p (df_live->out_of_date_transfer_functions, 
-                            bb->index))
-           {
-             bitmap_copy (saved_gen, bb_info->gen);
-             bitmap_copy (saved_kill, bb_info->kill);
-             bitmap_clear (bb_info->gen);
-             bitmap_clear (bb_info->kill);
-
-             df_live_bb_local_compute (bb->index);
-             gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
-             gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
-           }
-       }
-      else
-       {
-         /* If we do not have basic block info, the block must be in
-            the list of dirty blocks or else some one has added a
-            block behind our backs. */
-         gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions, 
-                                   bb->index));
-       }
-      /* Make sure no one created a block without following
-        procedures.  */
-      gcc_assert (df_scan_get_bb_info (bb->index));
-    }
-
-  /* Make sure there are no dirty bits in blocks that have been deleted.  */
-  gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions, 
-                                        all_blocks)); 
-  BITMAP_FREE (saved_gen);
-  BITMAP_FREE (saved_kill);
-  BITMAP_FREE (all_blocks);
+  df_add_problem (&problem_CHAIN);
+  df_chain->local_flags = chain_flags;
+  df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);

 }
 
 }
 

+#undef df_chain_problem_p

 
 \f
 /*----------------------------------------------------------------------------
 
 \f
 /*----------------------------------------------------------------------------

-   UNINITIALIZED REGISTERS WITH EARLYCLOBBER
-
-   Find the set of uses for registers that are reachable from the entry
-   block without passing thru a definition.  In and out bitvectors are built
-   for each basic block.  The regnum is used to index into these sets.
-   See df.h for details.
+   WORD LEVEL LIVE REGISTERS

 
 

-   This is a variant of the UR problem above that has a lot of special
-   features just for the register allocation phase.  This problem
-   should go away if someone would fix the interference graph.
+   Find the locations in the function where any use of a pseudo can
+   reach in the backwards direction.  In and out bitvectors are built
+   for each basic block.  We only track pseudo registers that have a
+   size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
+   contain two bits corresponding to each of the subwords.

 
    ----------------------------------------------------------------------------*/
 
 
    ----------------------------------------------------------------------------*/
 

-/* Private data used to compute the solution for this problem.  These
-   data structures are not accessible outside of this module.  */
-struct df_urec_problem_data
+/* Private data used to verify the solution for this problem.  */
+struct df_word_lr_problem_data

 {
 {

-  bool earlyclobbers_found;     /* True if any instruction contains an
-                                  earlyclobber.  */
-#ifdef STACK_REGS
-  bitmap stack_regs;           /* Registers that may be allocated to a STACK_REGS.  */
-#endif
+  /* An obstack for the bitmaps we need for this problem.  */
+  bitmap_obstack word_lr_bitmaps;

 };
 
 
 };
 
 

-/* Set basic block info.  */
-
-static void
-df_urec_set_bb_info (unsigned int index, 
-                    struct df_urec_bb_info *bb_info)
-{
-  gcc_assert (df_urec);
-  gcc_assert (index < df_urec->block_info_size);
-  df_urec->block_info[index] = bb_info;
-}
-
-

 /* Free basic block info.  */
 
 static void
 /* Free basic block info.  */
 
 static void

-df_urec_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
-                     void *vbb_info)
+df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
+                        void *vbb_info)

 {
 {

-  struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info;
+  struct df_word_lr_bb_info *bb_info = (struct df_word_lr_bb_info *) vbb_info;

   if (bb_info)
     {
   if (bb_info)
     {

-      BITMAP_FREE (bb_info->gen);
-      BITMAP_FREE (bb_info->kill);
-      BITMAP_FREE (bb_info->in);
-      BITMAP_FREE (bb_info->out);
-      BITMAP_FREE (bb_info->earlyclobber);
-      pool_free (df_urec->block_pool, bb_info);
+      bitmap_clear (&bb_info->use);
+      bitmap_clear (&bb_info->def);
+      bitmap_clear (&bb_info->in);
+      bitmap_clear (&bb_info->out);

     }
 }
 
 
     }
 }
 
 

-/* Allocate or reset bitmaps for DF_UREC blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are

    not touched unless the block is new.  */
 
    not touched unless the block is new.  */
 

-static void 
-df_urec_alloc (bitmap all_blocks)
-
+static void
+df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 {
   unsigned int bb_index;
   bitmap_iterator bi;

-  struct df_urec_problem_data *problem_data
-    = (struct df_urec_problem_data *) df_urec->problem_data;
+  basic_block bb;
+  struct df_word_lr_problem_data *problem_data
+    = XNEW (struct df_word_lr_problem_data);

 
 

-  if (!df_urec->block_pool)
-    df_urec->block_pool = create_alloc_pool ("df_urec_block pool", 
-                                          sizeof (struct df_urec_bb_info), 50);
+  df_word_lr->problem_data = problem_data;

 
 

-  if (!df_urec->problem_data)
-    {
-      problem_data = XNEW (struct df_urec_problem_data);
-      df_urec->problem_data = problem_data;
-    }
-  problem_data->earlyclobbers_found = false;
+  df_grow_bb_info (df_word_lr);

 
 

-  df_grow_bb_info (df_urec);
+  /* Create the mapping from regnos to slots. This does not change
+     unless the problem is destroyed and recreated.  In particular, if
+     we end up deleting the only insn that used a subreg, we do not
+     want to redo the mapping because this would invalidate everything
+     else.  */

 
 

-  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+  bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
+
+  FOR_EACH_BB (bb)
+    bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
+
+  bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
+  bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
+
+  EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)

     {
     {

-      struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
-      if (bb_info)
-       { 
-         bitmap_clear (bb_info->kill);
-         bitmap_clear (bb_info->gen);
-         bitmap_clear (bb_info->earlyclobber);
+      struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
+      
+      /* When bitmaps are already initialized, just clear them.  */
+      if (bb_info->use.obstack)
+       {
+         bitmap_clear (&bb_info->def);
+         bitmap_clear (&bb_info->use);

        }
       else
        }
       else

-       { 
-         bb_info = (struct df_urec_bb_info *) pool_alloc (df_urec->block_pool);
-         df_urec_set_bb_info (bb_index, bb_info);
-         bb_info->kill = BITMAP_ALLOC (NULL);
-         bb_info->gen = BITMAP_ALLOC (NULL);
-         bb_info->in = BITMAP_ALLOC (NULL);
-         bb_info->out = BITMAP_ALLOC (NULL);
-          bb_info->top = BITMAP_ALLOC (NULL);
-         bb_info->earlyclobber = BITMAP_ALLOC (NULL);
+       {
+         bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
+         bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
+         bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
+         bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);

        }
     }
        }
     }

-  df_urec->optional_p = true;
+
+  df_word_lr->optional_p = true;

 }
 
 
 }
 
 

-/* The function modifies local info for register REG being changed in
-   SETTER.  DATA is used to pass the current basic block info.  */
+/* Reset the global solution for recalculation.  */

 
 static void
 
 static void

-df_urec_mark_reg_change (rtx reg, rtx setter, void *data)
+df_word_lr_reset (bitmap all_blocks)

 {
 {

-  int regno;
-  int endregno;
-  int i;
-  struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
+  unsigned int bb_index;
+  bitmap_iterator bi;

 
 

-  if (GET_CODE (reg) == SUBREG)
-    reg = SUBREG_REG (reg);
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
+      gcc_assert (bb_info);
+      bitmap_clear (&bb_info->in);
+      bitmap_clear (&bb_info->out);
+    }
+}

 
 

-  if (!REG_P (reg))
-    return;
-  
+/* Examine REF, and if it is for a reg we're interested in, set or
+   clear the bits corresponding to its subwords from the bitmap
+   according to IS_SET.  LIVE is the bitmap we should update.  We do
+   not track hard regs or pseudos of any size other than 2 *
+   UNITS_PER_WORD.
+   We return true if we changed the bitmap, or if we encountered a register
+   we're not tracking.  */
+
+bool
+df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
+{
+  rtx orig_reg = DF_REF_REG (ref);
+  rtx reg = orig_reg;
+  enum machine_mode reg_mode;
+  unsigned regno;
+  /* Left at -1 for whole accesses.  */
+  int which_subword = -1;
+  bool changed = false;
+
+  if (GET_CODE (reg) == SUBREG)
+    reg = SUBREG_REG (orig_reg);

   regno = REGNO (reg);
   regno = REGNO (reg);

-  if (regno < FIRST_PSEUDO_REGISTER)
+  reg_mode = GET_MODE (reg);
+  if (regno < FIRST_PSEUDO_REGISTER
+      || GET_MODE_SIZE (reg_mode) != 2 * UNITS_PER_WORD)
+    return true;
+
+  if (GET_CODE (orig_reg) == SUBREG
+      && df_read_modify_subreg_p (orig_reg))

     {
     {

-      endregno = END_HARD_REGNO (reg);
-      for (i = regno; i < endregno; i++)
-       {
-         bitmap_set_bit (bb_info->kill, i);
-         
-         if (GET_CODE (setter) != CLOBBER)
-           bitmap_set_bit (bb_info->gen, i);
-         else
-           bitmap_clear_bit (bb_info->gen, i);
-       }
+      gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
+      if (subreg_lowpart_p (orig_reg))
+       which_subword = 0;
+      else
+       which_subword = 1;
+    }
+  if (is_set)
+    {
+      if (which_subword != 1)
+       changed |= bitmap_set_bit (live, regno * 2);
+      if (which_subword != 0)
+       changed |= bitmap_set_bit (live, regno * 2 + 1);

     }
   else
     {
     }
   else
     {

-      bitmap_set_bit (bb_info->kill, regno);
-      
-      if (GET_CODE (setter) != CLOBBER)
-       bitmap_set_bit (bb_info->gen, regno);
-      else
-       bitmap_clear_bit (bb_info->gen, regno);
+      if (which_subword != 1)
+       changed |= bitmap_clear_bit (live, regno * 2);
+      if (which_subword != 0)
+       changed |= bitmap_clear_bit (live, regno * 2 + 1);

     }
     }

+  return changed;

 }
 }

-/* Classes of registers which could be early clobbered in the current
-   insn.  */

 
 

-static VEC(int,heap) *earlyclobber_regclass;
-
-/* This function finds and stores register classes that could be early
-   clobbered in INSN.  If any earlyclobber classes are found, the function
-   returns TRUE, in all other cases it returns FALSE.  */
+/* Compute local live register info for basic block BB.  */

 
 

-static bool
-df_urec_check_earlyclobber (rtx insn)
+static void
+df_word_lr_bb_local_compute (unsigned int bb_index)

 {
 {

-  int opno;
-  bool found = false;
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
+  rtx insn;
+  df_ref *def_rec;
+  df_ref *use_rec;

 
 

-  extract_insn (insn);
+  /* Ensure that artificial refs don't contain references to pseudos.  */
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
+    }

 
 

-  VEC_truncate (int, earlyclobber_regclass, 0);
-  for (opno = 0; opno < recog_data.n_operands; opno++)
+  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)

     {
     {

-      char c;
-      bool amp_p;
-      int i;
-      enum reg_class class;
-      const char *p = recog_data.constraints[opno];
-
-      class = NO_REGS;
-      amp_p = false;
-      for (;;)
-       {
-         c = *p;
-         switch (c)
-           {
-           case '=':  case '+':  case '?':
-           case '#':  case '!':
-           case '*':  case '%':
-           case 'm':  case '<':  case '>':  case 'V':  case 'o':
-           case 'E':  case 'F':  case 'G':  case 'H':
-           case 's':  case 'i':  case 'n':
-           case 'I':  case 'J':  case 'K':  case 'L':
-           case 'M':  case 'N':  case 'O':  case 'P':
-           case 'X':
-           case '0': case '1':  case '2':  case '3':  case '4':
-           case '5': case '6':  case '7':  case '8':  case '9':
-             /* These don't say anything we care about.  */
-             break;
-
-           case '&':
-             amp_p = true;
-             break;
-           case '\0':
-           case ',':
-             if (amp_p && class != NO_REGS)
-               {
-                 int rc;
+      df_ref use = *use_rec;
+      gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
+    }

 
 

-                 found = true;
-                 for (i = 0;
-                      VEC_iterate (int, earlyclobber_regclass, i, rc);
-                      i++)
-                   {
-                     if (rc == (int) class)
-                       goto found_rc;
-                   }
+  FOR_BB_INSNS_REVERSE (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);

 
 

-                 /* We use VEC_quick_push here because
-                    earlyclobber_regclass holds no more than
-                    N_REG_CLASSES elements. */
-                 VEC_quick_push (int, earlyclobber_regclass, (int) class);
-               found_rc:
-                 ;
-               }
-             
-             amp_p = false;
-             class = NO_REGS;
-             break;
-
-           case 'r':
-             class = GENERAL_REGS;
-             break;
-
-           default:
-             class = REG_CLASS_FROM_CONSTRAINT (c, p);
-             break;
+      if (!NONDEBUG_INSN_P (insn))
+       continue;
+      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+       {
+         df_ref def = *def_rec;
+         /* If the def is to only part of the reg, it does
+            not kill the other defs that reach here.  */
+         if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
+           {
+             df_word_lr_mark_ref (def, true, &bb_info->def);
+             df_word_lr_mark_ref (def, false, &bb_info->use);

            }
            }

-         if (c == '\0')
-           break;
-         p += CONSTRAINT_LEN (c, p);
+       }
+      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+       {
+         df_ref use = *use_rec;
+         df_word_lr_mark_ref (use, true, &bb_info->use);

        }
     }
        }
     }

-
-  return found;

 }
 
 }
 

-/* The function checks that pseudo-register *X has a class
-   intersecting with the class of pseudo-register could be early
-   clobbered in the same insn.

 
 

-   This function is a no-op if earlyclobber_regclass is empty. 
-
-   Reload can assign the same hard register to uninitialized
-   pseudo-register and early clobbered pseudo-register in an insn if
-   the pseudo-register is used first time in given BB and not lived at
-   the BB start.  To prevent this we don't change life information for
-   such pseudo-registers.  */
+/* Compute local live register info for each basic block within BLOCKS.  */

 
 

-static int
-df_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data)
+static void
+df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)

 {
 {

-  enum reg_class pref_class, alt_class;
-  int i, regno;
-  struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
+  unsigned int bb_index;
+  bitmap_iterator bi;

 
 

-  if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER)
+  EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)

     {
     {

-      int rc;
-
-      regno = REGNO (*x);
-      if (bitmap_bit_p (bb_info->kill, regno)
-         || bitmap_bit_p (bb_info->gen, regno))
-       return 0;
-      pref_class = reg_preferred_class (regno);
-      alt_class = reg_alternate_class (regno);
-      for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++)
+      if (bb_index == EXIT_BLOCK)

        {
        {

-         if (reg_classes_intersect_p (rc, pref_class)
-             || (rc != NO_REGS
-                 && reg_classes_intersect_p (rc, alt_class)))
-           {
-             bitmap_set_bit (bb_info->earlyclobber, regno);
-             break;
-           }
-       }
-    }
-  return 0;
-}
-
-/* The function processes all pseudo-registers in *X with the aid of
-   previous function.  */
-
-static void
-df_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data)
-{
-  for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data);
-}
-
-
-/* Compute local uninitialized register info for basic block BB.  */
-
-static void
-df_urec_bb_local_compute (unsigned int bb_index)
-{
-  basic_block bb = BASIC_BLOCK (bb_index);
-  struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
-  rtx insn;
-  struct df_ref **def_rec;
-
-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
-    {
-      struct df_ref *def = *def_rec;
-      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
-       {
-         unsigned int regno = DF_REF_REGNO (def);
-         bitmap_set_bit (bb_info->gen, regno);
-       }
-    }
-  
-  FOR_BB_INSNS (bb, insn)
-    {
-      if (INSN_P (insn))
-       {
-         note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info);
-         if (df_urec_check_earlyclobber (insn))
-           {
-             struct df_urec_problem_data *problem_data
-               = (struct df_urec_problem_data *) df_urec->problem_data;
-             problem_data->earlyclobbers_found = true;
-             note_uses (&PATTERN (insn), 
-                        df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
-           }
-       }
-    }
-
-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
-    {
-      struct df_ref *def = *def_rec;
-      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
-       {
-         unsigned int regno = DF_REF_REGNO (def);
-         bitmap_set_bit (bb_info->gen, regno);
+         unsigned regno;
+         bitmap_iterator bi;
+         EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
+                                   regno, bi)
+           gcc_unreachable ();

        }
        }

-    }
-}
-
-
-/* Compute local uninitialized register info.  */
-
-static void
-df_urec_local_compute (bitmap all_blocks)
-{
-  unsigned int bb_index;
-  bitmap_iterator bi;
-#ifdef STACK_REGS
-  int i;
-  HARD_REG_SET stack_hard_regs, used;
-  struct df_urec_problem_data *problem_data
-    = (struct df_urec_problem_data *) df_urec->problem_data;
-  
-  /* Any register that MAY be allocated to a register stack (like the
-     387) is treated poorly.  Each such register is marked as being
-     live everywhere.  This keeps the register allocator and the
-     subsequent passes from doing anything useful with these values.
-
-     FIXME: This seems like an incredibly poor idea.  */
-
-  CLEAR_HARD_REG_SET (stack_hard_regs);
-  for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
-    SET_HARD_REG_BIT (stack_hard_regs, i);
-  problem_data->stack_regs = BITMAP_ALLOC (NULL);
-  for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
-    {
-      COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]);
-      IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]);
-      AND_HARD_REG_SET (used, stack_hard_regs);
-      if (!hard_reg_set_empty_p (used))
-       bitmap_set_bit (problem_data->stack_regs, i);
-    }
-#endif
-
-  /* We know that earlyclobber_regclass holds no more than
-    N_REG_CLASSES elements.  See df_urec_check_earlyclobber.  */
-  earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES);
-
-  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
-    {
-      df_urec_bb_local_compute (bb_index);
+      else
+       df_word_lr_bb_local_compute (bb_index);

     }
 
     }
 

-  VEC_free (int, heap, earlyclobber_regclass);
+  bitmap_clear (df_word_lr->out_of_date_transfer_functions);

 }
 
 
 /* Initialize the solution vectors.  */
 
 }
 
 
 /* Initialize the solution vectors.  */
 

-static void 
-df_urec_init (bitmap all_blocks)
-{
-  unsigned int bb_index;
-  bitmap_iterator bi;
-
-  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
-    {
-      struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
-
-      bitmap_copy (bb_info->out, bb_info->gen);
-      bitmap_clear (bb_info->in);
-    }
-}
-
-
-/* Or in the stack regs, hard regs and early clobber regs into the
-   urec_in sets of all of the blocks.  */
- 
-

 static void
 static void

-df_urec_local_finalize (bitmap all_blocks)
+df_word_lr_init (bitmap all_blocks)

 {
 {

-  bitmap tmp = BITMAP_ALLOC (NULL);
-  bitmap_iterator bi;

   unsigned int bb_index;
   unsigned int bb_index;

-  struct df_urec_problem_data *problem_data
-    = (struct df_urec_problem_data *) df_urec->problem_data;
+  bitmap_iterator bi;

 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {

-      struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
-      struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
-
-      if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK)
-       {
-         if (problem_data->earlyclobbers_found)
-           bitmap_ior_into (bb_info->in, bb_info->earlyclobber);
-       
-#ifdef STACK_REGS
-         /* We can not use the same stack register for uninitialized
-            pseudo-register and another living pseudo-register
-            because if the uninitialized pseudo-register dies,
-            subsequent pass reg-stack will be confused (it will
-            believe that the other register dies).  */
-         bitmap_ior_into (bb_info->in, problem_data->stack_regs);
-         bitmap_ior_into (bb_info->out, problem_data->stack_regs);
-#endif
-       }
-
-      /* No register may reach a location where it is not used.  Thus
-        we trim the rr result to the places where it is used.  */
-      bitmap_and_into (bb_info->in, bb_lr_info->in);
-      bitmap_and_into (bb_info->out, bb_lr_info->out);
-      bitmap_copy (bb_info->top, bb_info->in);
-      if (bb_lr_info->adef)
-        bitmap_ior_into (bb_info->top, bb_lr_info->adef);
-      bitmap_and_into (bb_info->top, bb_lr_info->top);
-#if 0
-      /* Hard registers may still stick in the ur_out set, but not
-        be in the ur_in set, if their only mention was in a call
-        in this block.  This is because a call kills in the lr
-        problem but does not kill in the rr problem.  To clean
-        this up, we execute the transfer function on the lr_in
-        set and then use that to knock bits out of ur_out.  */
-      bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in, 
-                           bb_info->kill);
-      bitmap_and_into (bb_info->out, tmp);
-#endif
+      struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
+      bitmap_copy (&bb_info->in, &bb_info->use);
+      bitmap_clear (&bb_info->out);

     }
     }

-  
-#ifdef STACK_REGS
-  BITMAP_FREE (problem_data->stack_regs);
-#endif
-  BITMAP_FREE (tmp);

 }
 
 
 /* Confluence function that ignores fake edges.  */
 
 }
 
 
 /* Confluence function that ignores fake edges.  */
 

-static void
-df_urec_confluence_n (edge e)
+static bool
+df_word_lr_confluence_n (edge e)

 {
 {

-  bitmap op1 = df_urec_get_bb_info (e->dest->index)->in;
-  bitmap op2 = df_urec_get_bb_info (e->src->index)->out;
- 
-  if (e->flags & EDGE_FAKE) 
-    return;
+  bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
+  bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;

 
 

-  bitmap_ior_into (op1, op2);
-} 
+  return bitmap_ior_into (op1, op2);
+}

 
 
 /* Transfer function.  */
 
 static bool
 
 
 /* Transfer function.  */
 
 static bool

-df_urec_transfer_function (int bb_index)
+df_word_lr_transfer_function (int bb_index)

 {
 {

-  struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
-  bitmap in = bb_info->in;
-  bitmap out = bb_info->out;
-  bitmap gen = bb_info->gen;
-  bitmap kill = bb_info->kill;
+  struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
+  bitmap in = &bb_info->in;
+  bitmap out = &bb_info->out;
+  bitmap use = &bb_info->use;
+  bitmap def = &bb_info->def;

 
 

-  return bitmap_ior_and_compl (out, gen, in, kill);
+  return bitmap_ior_and_compl (in, use, out, def);

 }
 
 
 /* Free all storage associated with the problem.  */
 
 static void
 }
 
 
 /* Free all storage associated with the problem.  */
 
 static void

-df_urec_free (void)
+df_word_lr_free (void)

 {
 {

-  if (df_urec->block_info)
+  struct df_word_lr_problem_data *problem_data
+    = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
+
+  if (df_word_lr->block_info)

     {
     {

-      unsigned int i;
-      
-      for (i = 0; i < df_urec->block_info_size; i++)
-       {
-         struct df_urec_bb_info *bb_info = df_urec_get_bb_info (i);
-         if (bb_info)
-           {
-             BITMAP_FREE (bb_info->gen);
-             BITMAP_FREE (bb_info->kill);
-             BITMAP_FREE (bb_info->in);
-             BITMAP_FREE (bb_info->out);
-             BITMAP_FREE (bb_info->earlyclobber);
-              BITMAP_FREE (bb_info->top);
-           }
-       }
-      
-      free_alloc_pool (df_urec->block_pool);
-      
-      df_urec->block_info_size = 0;
-      free (df_urec->block_info);
-      free (df_urec->problem_data);
+      df_word_lr->block_info_size = 0;
+      free (df_word_lr->block_info);
+      df_word_lr->block_info = NULL;

     }
     }

-  free (df_urec);
+
+  BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
+  bitmap_obstack_release (&problem_data->word_lr_bitmaps);
+  free (problem_data);
+  free (df_word_lr);

 }
 
 
 /* Debugging info at top of bb.  */
 
 static void
 }
 
 
 /* Debugging info at top of bb.  */
 
 static void

-df_urec_top_dump (basic_block bb, FILE *file)
+df_word_lr_top_dump (basic_block bb, FILE *file)

 {
 {

-  struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
-  if (!bb_info || !bb_info->in)
+  struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
+  if (!bb_info)

     return;
     return;

-      
-  fprintf (file, ";; urec  in  \t");
-  df_print_regset (file, bb_info->in);
-  fprintf (file, ";; urec  gen \t");
-  df_print_regset (file, bb_info->gen);
-  fprintf (file, ";; urec  kill\t");
-  df_print_regset (file, bb_info->kill);
-  fprintf (file, ";; urec  ec\t");
-  df_print_regset (file, bb_info->earlyclobber);
+
+  fprintf (file, ";; blr  in  \t");
+  df_print_word_regset (file, &bb_info->in);
+  fprintf (file, ";; blr  use \t");
+  df_print_word_regset (file, &bb_info->use);
+  fprintf (file, ";; blr  def \t");
+  df_print_word_regset (file, &bb_info->def);

 }
 
 
 /* Debugging info at bottom of bb.  */
 
 static void
 }
 
 
 /* Debugging info at bottom of bb.  */
 
 static void

-df_urec_bottom_dump (basic_block bb, FILE *file)
+df_word_lr_bottom_dump (basic_block bb, FILE *file)

 {
 {

-  struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
-  if (!bb_info || !bb_info->out)
+  struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
+  if (!bb_info)

     return;
     return;

-  fprintf (file, ";; urec  out \t");
-  df_print_regset (file, bb_info->out);
+
+  fprintf (file, ";; blr  out \t");
+  df_print_word_regset (file, &bb_info->out);

 }
 
 
 /* All of the information associated with every instance of the problem.  */
 
 }
 
 
 /* All of the information associated with every instance of the problem.  */
 

-static struct df_problem problem_UREC =
-{
-  DF_UREC,                    /* Problem id.  */
-  DF_FORWARD,                 /* Direction.  */
-  df_urec_alloc,              /* Allocate the problem specific data.  */
-  NULL,                       /* Reset global information.  */
-  df_urec_free_bb_info,       /* Free basic block info.  */
-  df_urec_local_compute,      /* Local compute function.  */
-  df_urec_init,               /* Init the solution specific data.  */
-  df_worklist_dataflow,       /* Worklist solver.  */
-  NULL,                       /* Confluence operator 0.  */ 
-  df_urec_confluence_n,       /* Confluence operator n.  */ 
-  df_urec_transfer_function,  /* Transfer function.  */
-  df_urec_local_finalize,     /* Finalize function.  */
-  df_urec_free,               /* Free all of the problem information.  */
-  df_urec_free,               /* Remove this problem from the stack of dataflow problems.  */
-  NULL,                       /* Debugging.  */
-  df_urec_top_dump,           /* Debugging start block.  */
-  df_urec_bottom_dump,        /* Debugging end block.  */
-  NULL,                       /* Incremental solution verify start.  */
-  NULL,                       /* Incremental solution verify end.  */
-  &problem_LR,                /* Dependent problem.  */
-  TV_DF_UREC,                 /* Timing variable.  */ 
-  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
+static struct df_problem problem_WORD_LR =
+{
+  DF_WORD_LR,                      /* Problem id.  */
+  DF_BACKWARD,                     /* Direction.  */
+  df_word_lr_alloc,                /* Allocate the problem specific data.  */
+  df_word_lr_reset,                /* Reset global information.  */
+  df_word_lr_free_bb_info,         /* Free basic block info.  */
+  df_word_lr_local_compute,        /* Local compute function.  */
+  df_word_lr_init,                 /* Init the solution specific data.  */
+  df_worklist_dataflow,            /* Worklist solver.  */
+  NULL,                            /* Confluence operator 0.  */
+  df_word_lr_confluence_n,         /* Confluence operator n.  */
+  df_word_lr_transfer_function,    /* Transfer function.  */
+  NULL,                            /* Finalize function.  */
+  df_word_lr_free,                 /* Free all of the problem information.  */
+  df_word_lr_free,                 /* Remove this problem from the stack of dataflow problems.  */
+  NULL,                            /* Debugging.  */
+  df_word_lr_top_dump,             /* Debugging start block.  */
+  df_word_lr_bottom_dump,          /* Debugging end block.  */
+  NULL,                            /* Incremental solution verify start.  */
+  NULL,                            /* Incremental solution verify end.  */
+  NULL,                       /* Dependent problem.  */
+  sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array.  */
+  TV_DF_WORD_LR,                   /* Timing variable.  */
+  false                            /* Reset blocks on dropping out of blocks_to_analyze.  */

 };
 
 
 };
 
 


@@ -3083,478 +2653,803 @@ static struct df_problem problem_UREC =
    solution.  */
 
 void
    solution.  */
 
 void

-df_urec_add_problem (void)
+df_word_lr_add_problem (void)

 {
 {

-  df_add_problem (&problem_UREC);
+  df_add_problem (&problem_WORD_LR);
+  /* These will be initialized when df_scan_blocks processes each
+     block.  */
+  df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);

 }
 
 
 }
 
 

-\f
-/*----------------------------------------------------------------------------
-   CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
+/* Simulate the effects of the defs of INSN on LIVE.  Return true if we changed
+   any bits, which is used by the caller to determine whether a set is
+   necessary.  We also return true if there are other reasons not to delete
+   an insn.  */

 
 

-   Link either the defs to the uses and / or the uses to the defs.
+bool
+df_word_lr_simulate_defs (rtx insn, bitmap live)
+{
+  bool changed = false;
+  df_ref *def_rec;
+  unsigned int uid = INSN_UID (insn);

 
 

-   These problems are set up like the other dataflow problems so that
-   they nicely fit into the framework.  They are much simpler and only
-   involve a single traversal of instructions and an examination of
-   the reaching defs information (the dependent problem).
-----------------------------------------------------------------------------*/
+  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
+       changed = true;
+      else
+       changed |= df_word_lr_mark_ref (*def_rec, false, live);
+    }
+  return changed;
+}

 
 

-#define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))

 
 

-/* Create a du or ud chain from SRC to DST and link it into SRC.   */
+/* Simulate the effects of the uses of INSN on LIVE.  */

 
 

-struct df_link *
-df_chain_create (struct df_ref *src, struct df_ref *dst)
+void
+df_word_lr_simulate_uses (rtx insn, bitmap live)

 {
 {

-  struct df_link *head = DF_REF_CHAIN (src);
-  struct df_link *link = pool_alloc (df_chain->block_pool);;
-  
-  DF_REF_CHAIN (src) = link;
-  link->next = head;
-  link->ref = dst;
-  return link;
-}
+  df_ref *use_rec;
+  unsigned int uid = INSN_UID (insn);

 
 

+  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+    df_word_lr_mark_ref (*use_rec, true, live);
+}
+\f
+/*----------------------------------------------------------------------------
+   This problem computes REG_DEAD and REG_UNUSED notes.
+   ----------------------------------------------------------------------------*/

 
 

-/* Delete any du or ud chains that start at REF and point to
-   TARGET.  */ 

 static void
 static void

-df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
+df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)

 {
 {

-  struct df_link *chain = DF_REF_CHAIN (ref);
-  struct df_link *prev = NULL;
-
-  while (chain)
-    {
-      if (chain->ref == target)
-       {
-         if (prev)
-           prev->next = chain->next;
-         else
-           DF_REF_CHAIN (ref) = chain->next;
-         pool_free (df_chain->block_pool, chain);
-         return;
-       }
-      prev = chain;
-      chain = chain->next;
-    }
+  df_note->optional_p = true;

 }
 
 }
 

-
-/* Delete a du or ud chain that leave or point to REF.  */
-
-void
-df_chain_unlink (struct df_ref *ref)
+#ifdef REG_DEAD_DEBUGGING
+static void
+df_print_note (const char *prefix, rtx insn, rtx note)

 {
 {

-  struct df_link *chain = DF_REF_CHAIN (ref);
-  while (chain)
+  if (dump_file)

     {
     {

-      struct df_link *next = chain->next;
-      /* Delete the other side if it exists.  */
-      df_chain_unlink_1 (chain->ref, ref);
-      pool_free (df_chain->block_pool, chain);
-      chain = next;
+      fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
+      print_rtl (dump_file, note);
+      fprintf (dump_file, "\n");

     }
     }

-  DF_REF_CHAIN (ref) = NULL;

 }
 }

+#endif

 
 
 
 

-/* Copy the du or ud chain starting at FROM_REF and attach it to
-   TO_REF.  */ 
+/* After reg-stack, the x86 floating point stack regs are difficult to
+   analyze because of all of the pushes, pops and rotations.  Thus, we
+   just leave the notes alone. */

 
 

-void 
-df_chain_copy (struct df_ref *to_ref, 
-              struct df_link *from_ref)
+#ifdef STACK_REGS
+static inline bool
+df_ignore_stack_reg (int regno)

 {
 {

-  while (from_ref)
-    {
-      df_chain_create (to_ref, from_ref->ref);
-      from_ref = from_ref->next;
-    }
+  return regstack_completed
+    && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);

 }
 }

+#else
+static inline bool
+df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
+{
+  return false;
+}
+#endif

 
 
 
 

-/* Remove this problem from the stack of dataflow problems.  */
+/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
+   them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */

 
 static void
 
 static void

-df_chain_remove_problem (void)
+df_kill_notes (rtx insn)

 {
 {

-  bitmap_iterator bi;
-  unsigned int bb_index;
-
-  /* Wholesale destruction of the old chains.  */ 
-  if (df_chain->block_pool)
-    free_alloc_pool (df_chain->block_pool);
+  rtx *pprev = &REG_NOTES (insn);
+  rtx link = *pprev;

 
 

-  EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
+  while (link)

     {
     {

-      rtx insn;
-      struct df_ref **def_rec;
-      struct df_ref **use_rec;
-      basic_block bb = BASIC_BLOCK (bb_index);
-
-      if (df_chain_problem_p (DF_DU_CHAIN))
-       for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
-         DF_REF_CHAIN (*def_rec) = NULL;
-      if (df_chain_problem_p (DF_UD_CHAIN))
-       for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
-         DF_REF_CHAIN (*use_rec) = NULL;
-      
-      FOR_BB_INSNS (bb, insn)
+      switch (REG_NOTE_KIND (link))

        {
        {

-         unsigned int uid = INSN_UID (insn);
-         
-         if (INSN_P (insn))
+       case REG_DEAD:
+         /* After reg-stack, we need to ignore any unused notes
+            for the stack registers.  */
+         if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))

            {
            {

-             if (df_chain_problem_p (DF_DU_CHAIN))
-               for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
-                 DF_REF_CHAIN (*def_rec) = NULL;
-             if (df_chain_problem_p (DF_UD_CHAIN))
-               {
-                 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
-                   DF_REF_CHAIN (*use_rec) = NULL;
-                 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
-                   DF_REF_CHAIN (*use_rec) = NULL;
-               }
+             pprev = &XEXP (link, 1);
+             link = *pprev;

            }
            }

-       }
-    }
-
-  bitmap_clear (df_chain->out_of_date_transfer_functions);
-  df_chain->block_pool = NULL;
-}
-
-
-/* Remove the chain problem completely.  */
+         else
+           {
+             rtx next = XEXP (link, 1);
+#ifdef REG_DEAD_DEBUGGING
+             df_print_note ("deleting: ", insn, link);
+#endif
+             free_EXPR_LIST_node (link);
+             *pprev = link = next;
+           }
+         break;

 
 

-static void
-df_chain_fully_remove_problem (void)
-{
-  df_chain_remove_problem ();
-  BITMAP_FREE (df_chain->out_of_date_transfer_functions);
-  free (df_chain);
+       case REG_UNUSED:
+         /* After reg-stack, we need to ignore any unused notes
+            for the stack registers.  */
+         if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
+           {
+             pprev = &XEXP (link, 1);
+             link = *pprev;
+           }
+         else
+           {
+             rtx next = XEXP (link, 1);
+#ifdef REG_DEAD_DEBUGGING
+             df_print_note ("deleting: ", insn, link);
+#endif
+             free_EXPR_LIST_node (link);
+             *pprev = link = next;
+           }
+         break;
+
+       default:
+         pprev = &XEXP (link, 1);
+         link = *pprev;
+         break;
+       }
+    }

 }
 
 
 }
 
 

-/* Create def-use or use-def chains.  */
+/* Set a NOTE_TYPE note for REG in INSN.  */

 
 

-static void  
-df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
+static inline void
+df_set_note (enum reg_note note_type, rtx insn, rtx reg)

 {
 {

-  df_chain_remove_problem ();
-  df_chain->block_pool = create_alloc_pool ("df_chain_block pool", 
-                                        sizeof (struct df_link), 50);
-  df_chain->optional_p = true;
+  gcc_checking_assert (!DEBUG_INSN_P (insn));
+  add_reg_note (insn, note_type, reg);

 }
 
 }
 

+/* A subroutine of df_set_unused_notes_for_mw, with a selection of its
+   arguments.  Return true if the register value described by MWS's
+   mw_reg is known to be completely unused, and if mw_reg can therefore
+   be used in a REG_UNUSED note.  */
+
+static bool
+df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
+                         bitmap live, bitmap artificial_uses)
+{
+  unsigned int r;

 
 

-/* Reset all of the chains when the set of basic blocks changes.  */
+  /* If MWS describes a partial reference, create REG_UNUSED notes for
+     individual hard registers.  */
+  if (mws->flags & DF_REF_PARTIAL)
+    return false;
+
+  /* Likewise if some part of the register is used.  */
+  for (r = mws->start_regno; r <= mws->end_regno; r++)
+    if (bitmap_bit_p (live, r)
+       || bitmap_bit_p (artificial_uses, r))
+      return false;
+
+  gcc_assert (REG_P (mws->mw_reg));
+  return true;
+}
+
+/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
+   based on the bits in LIVE.  Do not generate notes for registers in
+   artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
+   not generated if the reg is both read and written by the
+   instruction.
+*/

 
 static void
 
 static void

-df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
+df_set_unused_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
+                           bitmap live, bitmap do_not_gen,
+                           bitmap artificial_uses)

 {
 {

-  df_chain_remove_problem ();
+  unsigned int r;
+
+#ifdef REG_DEAD_DEBUGGING
+  if (dump_file)
+    fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
+            mws->start_regno, mws->end_regno);
+#endif
+
+  if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
+    {
+      unsigned int regno = mws->start_regno;
+      df_set_note (REG_UNUSED, insn, mws->mw_reg);
+
+#ifdef REG_DEAD_DEBUGGING
+      df_print_note ("adding 1: ", insn, REG_NOTES (insn));
+#endif
+      bitmap_set_bit (do_not_gen, regno);
+      /* Only do this if the value is totally dead.  */
+    }
+  else
+    for (r = mws->start_regno; r <= mws->end_regno; r++)
+      {
+       if (!bitmap_bit_p (live, r)
+           && !bitmap_bit_p (artificial_uses, r))
+         {
+           df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
+#ifdef REG_DEAD_DEBUGGING
+           df_print_note ("adding 2: ", insn, REG_NOTES (insn));
+#endif
+         }
+       bitmap_set_bit (do_not_gen, r);
+      }

 }
 
 
 }
 
 

-/* Create the chains for a list of USEs.  */
+/* A subroutine of df_set_dead_notes_for_mw, with a selection of its
+   arguments.  Return true if the register value described by MWS's
+   mw_reg is known to be completely dead, and if mw_reg can therefore
+   be used in a REG_DEAD note.  */
+
+static bool
+df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
+                       bitmap live, bitmap artificial_uses,
+                       bitmap do_not_gen)
+{
+  unsigned int r;
+
+  /* If MWS describes a partial reference, create REG_DEAD notes for
+     individual hard registers.  */
+  if (mws->flags & DF_REF_PARTIAL)
+    return false;
+
+  /* Likewise if some part of the register is not dead.  */
+  for (r = mws->start_regno; r <= mws->end_regno; r++)
+    if (bitmap_bit_p (live, r)
+       || bitmap_bit_p (artificial_uses, r)
+       || bitmap_bit_p (do_not_gen, r))
+      return false;
+
+  gcc_assert (REG_P (mws->mw_reg));
+  return true;
+}
+
+/* Set the REG_DEAD notes for the multiword hardreg use in INSN based
+   on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
+   from being set if the instruction both reads and writes the
+   register.  */

 
 static void
 
 static void

-df_chain_create_bb_process_use (bitmap local_rd,
-                               struct df_ref **use_rec,
-                               enum df_ref_flags top_flag)
+df_set_dead_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
+                         bitmap live, bitmap do_not_gen,
+                         bitmap artificial_uses, bool *added_notes_p)

 {
 {

-  bitmap_iterator bi;
-  unsigned int def_index;
-  
-  while (*use_rec)
+  unsigned int r;
+  bool is_debug = *added_notes_p;
+
+  *added_notes_p = false;
+
+#ifdef REG_DEAD_DEBUGGING
+  if (dump_file)

     {
     {

-      struct df_ref *use = *use_rec;
-      unsigned int uregno = DF_REF_REGNO (use);
-      if ((!(df->changeable_flags & DF_NO_HARD_REGS))
-         || (uregno >= FIRST_PSEUDO_REGISTER))
+      fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
+              mws->start_regno, mws->end_regno);
+      df_print_regset (dump_file, do_not_gen);
+      fprintf (dump_file, "  live =");
+      df_print_regset (dump_file, live);
+      fprintf (dump_file, "  artificial uses =");
+      df_print_regset (dump_file, artificial_uses);
+    }
+#endif
+
+  if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
+    {
+      /* Add a dead note for the entire multi word register.  */
+      if (is_debug)

        {
        {

-         /* Do not want to go through this for an uninitialized var.  */
-         int count = DF_DEFS_COUNT (uregno);
-         if (count)
-           {
-             if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
-               {
-                 unsigned int first_index = DF_DEFS_BEGIN (uregno);
-                 unsigned int last_index = first_index + count - 1;
-                 
-                 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
-                   {
-                     struct df_ref *def;
-                     if (def_index > last_index) 
-                       break;
-                     
-                     def = DF_DEFS_GET (def_index);
-                     if (df_chain_problem_p (DF_DU_CHAIN))
-                       df_chain_create (def, use);
-                     if (df_chain_problem_p (DF_UD_CHAIN))
-                       df_chain_create (use, def);
-                   }
-               }
-           }
+         *added_notes_p = true;
+         return;

        }
        }

-
-      use_rec++;
+      df_set_note (REG_DEAD, insn, mws->mw_reg);
+#ifdef REG_DEAD_DEBUGGING
+      df_print_note ("adding 1: ", insn, REG_NOTES (insn));
+#endif
+    }
+  else
+    {
+      for (r = mws->start_regno; r <= mws->end_regno; r++)
+       if (!bitmap_bit_p (live, r)
+           && !bitmap_bit_p (artificial_uses, r)
+           && !bitmap_bit_p (do_not_gen, r))
+         {
+           if (is_debug)
+             {
+               *added_notes_p = true;
+               return;
+             }
+           df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
+#ifdef REG_DEAD_DEBUGGING
+           df_print_note ("adding 2: ", insn, REG_NOTES (insn));
+#endif
+         }

     }
     }

+  return;

 }
 
 
 }
 
 

-/* Create chains from reaching defs bitmaps for basic block BB.  */
+/* Create a REG_UNUSED note if necessary for DEF in INSN updating
+   LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */

 
 static void
 
 static void

-df_chain_create_bb (unsigned int bb_index)
+df_create_unused_note (rtx insn, df_ref def,
+                      bitmap live, bitmap artificial_uses)

 {
 {

-  basic_block bb = BASIC_BLOCK (bb_index);
-  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
-  rtx insn;
-  bitmap cpy = BITMAP_ALLOC (NULL);
-  struct df_ref **def_rec;
-
-  bitmap_copy (cpy, bb_info->in);
-  bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
+  unsigned int dregno = DF_REF_REGNO (def);

 
 

-  /* Since we are going forwards, process the artificial uses first
-     then the artificial defs second.  */
+#ifdef REG_DEAD_DEBUGGING
+  if (dump_file)
+    {
+      fprintf (dump_file, "  regular looking at def ");
+      df_ref_debug (def, dump_file);
+    }
+#endif

 
 

-#ifdef EH_USES
-  /* Create the chains for the artificial uses from the EH_USES at the
-     beginning of the block.  */
-  
-  /* Artificials are only hard regs.  */
-  if (!(df->changeable_flags & DF_NO_HARD_REGS))
-    df_chain_create_bb_process_use (cpy,
-                                   df_get_artificial_uses (bb->index), 
-                                   DF_REF_AT_TOP);
+  if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
+       || bitmap_bit_p (live, dregno)
+       || bitmap_bit_p (artificial_uses, dregno)
+       || df_ignore_stack_reg (dregno)))
+    {
+      rtx reg = (DF_REF_LOC (def))
+                ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
+      df_set_note (REG_UNUSED, insn, reg);
+#ifdef REG_DEAD_DEBUGGING
+      df_print_note ("adding 3: ", insn, REG_NOTES (insn));

 #endif
 #endif

+    }

 
 

-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+  return;
+}
+
+/* Node of a linked list of uses of dead REGs in debug insns.  */
+struct dead_debug_use
+{
+  df_ref use;
+  struct dead_debug_use *next;
+};
+
+/* Linked list of the above, with a bitmap of the REGs in the
+   list.  */
+struct dead_debug
+{
+  struct dead_debug_use *head;
+  bitmap used;
+  bitmap to_rescan;
+};
+
+/* Initialize DEBUG to an empty list, and clear USED, if given.  */
+static inline void
+dead_debug_init (struct dead_debug *debug, bitmap used)
+{
+  debug->head = NULL;
+  debug->used = used;
+  debug->to_rescan = NULL;
+  if (used)
+    bitmap_clear (used);
+}
+
+/* Reset all debug insns with pending uses.  Release the bitmap in it,
+   unless it is USED.  USED must be the same bitmap passed to
+   dead_debug_init.  */
+static inline void
+dead_debug_finish (struct dead_debug *debug, bitmap used)
+{
+  struct dead_debug_use *head;
+  rtx insn = NULL;
+
+  if (debug->used != used)
+    BITMAP_FREE (debug->used);
+
+  while ((head = debug->head))

     {
     {

-      struct df_ref *def = *def_rec;
-      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+      insn = DF_REF_INSN (head->use);
+      if (!head->next || DF_REF_INSN (head->next->use) != insn)

        {
        {

-         unsigned int dregno = DF_REF_REGNO (def);
-         if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-           bitmap_clear_range (cpy, 
-                               DF_DEFS_BEGIN (dregno), 
-                               DF_DEFS_COUNT (dregno));
-         bitmap_set_bit (cpy, DF_REF_ID (def));
+         INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
+         df_insn_rescan_debug_internal (insn);
+         if (debug->to_rescan)
+           bitmap_clear_bit (debug->to_rescan, INSN_UID (insn));

        }
        }

+      debug->head = head->next;
+      XDELETE (head);

     }
     }

-  
-  /* Process the regular instructions next.  */
-  FOR_BB_INSNS (bb, insn)
+
+  if (debug->to_rescan)

     {
     {

-      struct df_ref **def_rec;
-      unsigned int uid = INSN_UID (insn);
+      bitmap_iterator bi;
+      unsigned int uid;

 
 

-      if (!INSN_P (insn))
-       continue;
+      EXECUTE_IF_SET_IN_BITMAP (debug->to_rescan, 0, uid, bi)
+       {
+         struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
+         if (insn_info)
+           df_insn_rescan (insn_info->insn);
+       }
+      BITMAP_FREE (debug->to_rescan);
+    }
+}

 
 

-      /* Now scan the uses and link them up with the defs that remain
-        in the cpy vector.  */
-      
-      df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
+/* Add USE to DEBUG.  It must be a dead reference to UREGNO in a debug
+   insn.  Create a bitmap for DEBUG as needed.  */
+static inline void
+dead_debug_add (struct dead_debug *debug, df_ref use, unsigned int uregno)
+{
+  struct dead_debug_use *newddu = XNEW (struct dead_debug_use);

 
 

-      if (df->changeable_flags & DF_EQ_NOTES)
-       df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
+  newddu->use = use;
+  newddu->next = debug->head;
+  debug->head = newddu;

 
 

+  if (!debug->used)
+    debug->used = BITMAP_ALLOC (NULL);

 
 

-      /* Since we are going forwards, process the defs second.  This
-         pass only changes the bits in cpy.  */
-      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+  bitmap_set_bit (debug->used, uregno);
+}
+
+/* If UREGNO is referenced by any entry in DEBUG, emit a debug insn
+   before INSN that binds the REG to a debug temp, and replace all
+   uses of UREGNO in DEBUG with uses of the debug temp.  INSN must be
+   the insn where UREGNO dies.  */
+static inline void
+dead_debug_insert_before (struct dead_debug *debug, unsigned int uregno,
+                         rtx insn)
+{
+  struct dead_debug_use **tailp = &debug->head;
+  struct dead_debug_use *cur;
+  struct dead_debug_use *uses = NULL;
+  struct dead_debug_use **usesp = &uses;
+  rtx reg = NULL;
+  rtx dval;
+  rtx bind;
+
+  if (!debug->used || !bitmap_clear_bit (debug->used, uregno))
+    return;
+
+  /* Move all uses of uregno from debug->head to uses, setting mode to
+     the widest referenced mode.  */
+  while ((cur = *tailp))
+    {
+      if (DF_REF_REGNO (cur->use) == uregno)

        {
        {

-         struct df_ref *def = *def_rec;
-         unsigned int dregno = DF_REF_REGNO (def);
-         if ((!(df->changeable_flags & DF_NO_HARD_REGS))
-             || (dregno >= FIRST_PSEUDO_REGISTER))
-           {
-             if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-               bitmap_clear_range (cpy, 
-                                   DF_DEFS_BEGIN (dregno), 
-                                   DF_DEFS_COUNT (dregno));
-             if (!(DF_REF_FLAGS (def) 
-                   & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
-               bitmap_set_bit (cpy, DF_REF_ID (def));
-           }
+         *usesp = cur;
+         usesp = &cur->next;
+         *tailp = cur->next;
+         cur->next = NULL;
+         if (!reg
+             || (GET_MODE_BITSIZE (GET_MODE (reg))
+                 < GET_MODE_BITSIZE (GET_MODE (*DF_REF_REAL_LOC (cur->use)))))
+           reg = *DF_REF_REAL_LOC (cur->use);

        }
        }

+      else
+       tailp = &(*tailp)->next;

     }
 
     }
 

-  /* Create the chains for the artificial uses of the hard registers
-     at the end of the block.  */
-  if (!(df->changeable_flags & DF_NO_HARD_REGS))
-    df_chain_create_bb_process_use (cpy,
-                                   df_get_artificial_uses (bb->index), 
-                                   0);
+  gcc_assert (reg);
+
+  /* Create DEBUG_EXPR (and DEBUG_EXPR_DECL).  */
+  dval = make_debug_expr_from_rtl (reg);
+
+  /* Emit a debug bind insn before the insn in which reg dies.  */
+  bind = gen_rtx_VAR_LOCATION (GET_MODE (reg),
+                              DEBUG_EXPR_TREE_DECL (dval), reg,
+                              VAR_INIT_STATUS_INITIALIZED);
+
+  bind = emit_debug_insn_before (bind, insn);
+  df_insn_rescan (bind);

 
 

-  BITMAP_FREE (cpy);
+  /* Adjust all uses.  */
+  while ((cur = uses))
+    {
+      if (GET_MODE (*DF_REF_REAL_LOC (cur->use)) == GET_MODE (reg))
+       *DF_REF_REAL_LOC (cur->use) = dval;
+      else
+       *DF_REF_REAL_LOC (cur->use)
+         = gen_lowpart_SUBREG (GET_MODE (*DF_REF_REAL_LOC (cur->use)), dval);
+      /* ??? Should we simplify subreg of subreg?  */
+      if (debug->to_rescan == NULL)
+       debug->to_rescan = BITMAP_ALLOC (NULL);
+      bitmap_set_bit (debug->to_rescan, INSN_UID (DF_REF_INSN (cur->use)));
+      uses = cur->next;
+      XDELETE (cur);
+    }

 }
 
 }
 

-/* Create def-use chains from reaching use bitmaps for basic blocks
-   in BLOCKS.  */
+/* Recompute the REG_DEAD and REG_UNUSED notes and compute register
+   info: lifetime, bb, and number of defs and uses for basic block
+   BB.  The three bitvectors are scratch regs used here.  */

 
 static void
 
 static void

-df_chain_finalize (bitmap all_blocks)
+df_note_bb_compute (unsigned int bb_index,
+                   bitmap live, bitmap do_not_gen, bitmap artificial_uses)

 {
 {

-  unsigned int bb_index;
-  bitmap_iterator bi;
-  
-  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+  basic_block bb = BASIC_BLOCK (bb_index);
+  rtx insn;
+  df_ref *def_rec;
+  df_ref *use_rec;
+  struct dead_debug debug;
+
+  dead_debug_init (&debug, NULL);
+
+  bitmap_copy (live, df_get_live_out (bb));
+  bitmap_clear (artificial_uses);
+
+#ifdef REG_DEAD_DEBUGGING
+  if (dump_file)

     {
     {

-      df_chain_create_bb (bb_index);
+      fprintf (dump_file, "live at bottom ");
+      df_print_regset (dump_file, live);

     }
     }

-}
+#endif

 
 

+  /* Process the artificial defs and uses at the bottom of the block
+     to begin processing.  */
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+#ifdef REG_DEAD_DEBUGGING
+      if (dump_file)
+       fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
+#endif

 
 

-/* Free all storage associated with the problem.  */
+      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+       bitmap_clear_bit (live, DF_REF_REGNO (def));
+    }

 
 

-static void
-df_chain_free (void)
-{
-  free_alloc_pool (df_chain->block_pool);
-  BITMAP_FREE (df_chain->out_of_date_transfer_functions);
-  free (df_chain);
-}
+  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+    {
+      df_ref use = *use_rec;
+      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
+       {
+         unsigned int regno = DF_REF_REGNO (use);
+         bitmap_set_bit (live, regno);

 
 

+         /* Notes are not generated for any of the artificial registers
+            at the bottom of the block.  */
+         bitmap_set_bit (artificial_uses, regno);
+       }
+    }

 
 

-/* Debugging info.  */
+#ifdef REG_DEAD_DEBUGGING
+  if (dump_file)
+    {
+      fprintf (dump_file, "live before artificials out ");
+      df_print_regset (dump_file, live);
+    }
+#endif

 
 

-static void
-df_chain_top_dump (basic_block bb, FILE *file)
-{
-  if (df_chain_problem_p (DF_DU_CHAIN))
+  FOR_BB_INSNS_REVERSE (bb, insn)

     {
     {

-      rtx insn;
-      struct df_ref **def_rec = df_get_artificial_defs (bb->index);
-      if (*def_rec)
+      unsigned int uid = INSN_UID (insn);
+      struct df_mw_hardreg **mws_rec;
+      int debug_insn;
+
+      if (!INSN_P (insn))
+       continue;
+
+      debug_insn = DEBUG_INSN_P (insn);
+
+      bitmap_clear (do_not_gen);
+      df_kill_notes (insn);
+
+      /* Process the defs.  */
+      if (CALL_P (insn))

        {
        {

-         
-         fprintf (file, ";;  DU chains for artificial defs\n");
-         while (*def_rec)
+#ifdef REG_DEAD_DEBUGGING
+         if (dump_file)

            {
            {

-             struct df_ref *def = *def_rec;
-             fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
-             df_chain_dump (DF_REF_CHAIN (def), file);
-             fprintf (file, "\n");
-             def_rec++;
+             fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
+             df_print_regset (dump_file, live);
+           }
+#endif
+         /* We only care about real sets for calls.  Clobbers cannot
+            be depended on to really die.  */
+         mws_rec = DF_INSN_UID_MWS (uid);
+         while (*mws_rec)
+           {
+             struct df_mw_hardreg *mws = *mws_rec;
+             if ((DF_MWS_REG_DEF_P (mws))
+                 && !df_ignore_stack_reg (mws->start_regno))
+             df_set_unused_notes_for_mw (insn,
+                                         mws, live, do_not_gen,
+                                         artificial_uses);
+             mws_rec++;

            }
            }

-       }      

 
 

-      FOR_BB_INSNS (bb, insn)
-       {
-         unsigned int uid = INSN_UID (insn);
-         if (INSN_P (insn))
+         /* All of the defs except the return value are some sort of
+            clobber.  This code is for the return.  */
+         for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)

            {
            {

-             def_rec = DF_INSN_UID_DEFS (uid);
-             if (*def_rec)
+             df_ref def = *def_rec;
+             unsigned int dregno = DF_REF_REGNO (def);
+             if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))

                {
                {

-                 fprintf (file, ";;   DU chains for insn luid %d uid %d\n", 
-                          DF_INSN_LUID (insn), uid);
-                 
-                 while (*def_rec)
-                   {
-                     struct df_ref *def = *def_rec;
-                     fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
-                     if (def->flags & DF_REF_READ_WRITE)
-                       fprintf (file, "read/write ");
-                     df_chain_dump (DF_REF_CHAIN (def), file);
-                     fprintf (file, "\n");
-                     def_rec++;
-                   }
+                 df_create_unused_note (insn,
+                                        def, live, artificial_uses);
+                 bitmap_set_bit (do_not_gen, dregno);

                }
                }

+
+             if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
+               bitmap_clear_bit (live, dregno);

            }
        }
            }
        }

-    }
-}
+      else
+       {
+         /* Regular insn.  */
+         mws_rec = DF_INSN_UID_MWS (uid);
+         while (*mws_rec)
+           {
+             struct df_mw_hardreg *mws = *mws_rec;
+             if (DF_MWS_REG_DEF_P (mws))
+               df_set_unused_notes_for_mw (insn,
+                                           mws, live, do_not_gen,
+                                           artificial_uses);
+             mws_rec++;
+           }

 
 

+         for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+           {
+             df_ref def = *def_rec;
+             unsigned int dregno = DF_REF_REGNO (def);
+             df_create_unused_note (insn,
+                                    def, live, artificial_uses);

 
 

-static void
-df_chain_bottom_dump (basic_block bb, FILE *file)
-{
-  if (df_chain_problem_p (DF_UD_CHAIN))
-    {
-      rtx insn;
-      struct df_ref **use_rec = df_get_artificial_uses (bb->index);
+             if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
+               bitmap_set_bit (do_not_gen, dregno);

 
 

-      if (*use_rec)
+             if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
+               bitmap_clear_bit (live, dregno);
+           }
+       }
+
+      /* Process the uses.  */
+      mws_rec = DF_INSN_UID_MWS (uid);
+      while (*mws_rec)

        {
        {

-         fprintf (file, ";;  UD chains for artificial uses\n");
-         while (*use_rec)
+         struct df_mw_hardreg *mws = *mws_rec;
+         if ((DF_MWS_REG_DEF_P (mws))
+             && !df_ignore_stack_reg (mws->start_regno))

            {
            {

-             struct df_ref *use = *use_rec;
-             fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
-             df_chain_dump (DF_REF_CHAIN (use), file);
-             fprintf (file, "\n");
-             use_rec++;
+             bool really_add_notes = debug_insn != 0;
+
+             df_set_dead_notes_for_mw (insn,
+                                       mws, live, do_not_gen,
+                                       artificial_uses,
+                                       &really_add_notes);
+
+             if (really_add_notes)
+               debug_insn = -1;

            }
            }

-       }      
+         mws_rec++;
+       }

 
 

-      FOR_BB_INSNS (bb, insn)
+      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)

        {
        {

-         unsigned int uid = INSN_UID (insn);
-         if (INSN_P (insn))
+         df_ref use = *use_rec;
+         unsigned int uregno = DF_REF_REGNO (use);
+
+#ifdef REG_DEAD_DEBUGGING
+         if (dump_file && !debug_insn)

            {
            {

-             struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
-             use_rec = DF_INSN_UID_USES (uid);
-             if (*use_rec || *eq_use_rec)
+             fprintf (dump_file, "  regular looking at use ");
+             df_ref_debug (use, dump_file);
+           }
+#endif
+         if (!bitmap_bit_p (live, uregno))
+           {
+             if (debug_insn)

                {
                {

-                 fprintf (file, ";;   UD chains for insn luid %d uid %d\n", 
-                          DF_INSN_LUID (insn), uid);
-                 
-                 while (*use_rec)
+                 if (debug_insn > 0)

                    {
                    {

-                     struct df_ref *use = *use_rec;
-                     fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
-                     if (use->flags & DF_REF_READ_WRITE)
-                       fprintf (file, "read/write ");
-                     df_chain_dump (DF_REF_CHAIN (use), file);
-                     fprintf (file, "\n");
-                     use_rec++;
-                   }
-                 while (*eq_use_rec)
-                   {
-                     struct df_ref *use = *eq_use_rec;
-                     fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
-                     df_chain_dump (DF_REF_CHAIN (use), file);
-                     fprintf (file, "\n");
-                     eq_use_rec++;
+                     dead_debug_add (&debug, use, uregno);
+                     continue;

                    }
                    }

+                 break;
+               }
+             else
+               dead_debug_insert_before (&debug, uregno, insn);
+
+             if ( (!(DF_REF_FLAGS (use)
+                     & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
+                  && (!bitmap_bit_p (do_not_gen, uregno))
+                  && (!bitmap_bit_p (artificial_uses, uregno))
+                  && (!df_ignore_stack_reg (uregno)))
+               {
+                 rtx reg = (DF_REF_LOC (use))
+                            ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
+                 df_set_note (REG_DEAD, insn, reg);
+
+#ifdef REG_DEAD_DEBUGGING
+                 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
+#endif

                }
                }

+             /* This register is now live.  */
+             bitmap_set_bit (live, uregno);

            }
        }
            }
        }

+
+      if (debug_insn == -1)
+       {
+         /* ??? We could probably do better here, replacing dead
+            registers with their definitions.  */
+         INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
+         df_insn_rescan_debug_internal (insn);
+       }

     }
     }

+
+  dead_debug_finish (&debug, NULL);

 }
 
 
 }
 
 

-static struct df_problem problem_CHAIN =
+/* Compute register info: lifetime, bb, and number of defs and uses.  */
+static void
+df_note_compute (bitmap all_blocks)

 {
 {

-  DF_CHAIN,                   /* Problem id.  */
+  unsigned int bb_index;
+  bitmap_iterator bi;
+  bitmap_head live, do_not_gen, artificial_uses;
+
+  bitmap_initialize (&live, &df_bitmap_obstack);
+  bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
+  bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
+
+#ifdef REG_DEAD_DEBUGGING
+  if (dump_file)
+    print_rtl_with_bb (dump_file, get_insns());
+#endif
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+  {
+    df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
+  }
+
+  bitmap_clear (&live);
+  bitmap_clear (&do_not_gen);
+  bitmap_clear (&artificial_uses);
+}
+
+
+/* Free all storage associated with the problem.  */
+
+static void
+df_note_free (void)
+{
+  free (df_note);
+}
+
+
+/* All of the information associated every instance of the problem.  */
+
+static struct df_problem problem_NOTE =
+{
+  DF_NOTE,                    /* Problem id.  */

   DF_NONE,                    /* Direction.  */
   DF_NONE,                    /* Direction.  */

-  df_chain_alloc,             /* Allocate the problem specific data.  */
-  df_chain_reset,             /* Reset global information.  */
+  df_note_alloc,              /* Allocate the problem specific data.  */
+  NULL,                       /* Reset global information.  */

   NULL,                       /* Free basic block info.  */
   NULL,                       /* Free basic block info.  */

-  NULL,                       /* Local compute function.  */
+  df_note_compute,            /* Local compute function.  */

   NULL,                       /* Init the solution specific data.  */
   NULL,                       /* Iterative solver.  */
   NULL,                       /* Init the solution specific data.  */
   NULL,                       /* Iterative solver.  */

-  NULL,                       /* Confluence operator 0.  */ 
-  NULL,                       /* Confluence operator n.  */ 
+  NULL,                       /* Confluence operator 0.  */
+  NULL,                       /* Confluence operator n.  */

   NULL,                       /* Transfer function.  */
   NULL,                       /* Transfer function.  */

-  df_chain_finalize,          /* Finalize function.  */
-  df_chain_free,              /* Free all of the problem information.  */
-  df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
+  NULL,                       /* Finalize function.  */
+  df_note_free,               /* Free all of the problem information.  */
+  df_note_free,               /* Remove this problem from the stack of dataflow problems.  */

   NULL,                       /* Debugging.  */
   NULL,                       /* Debugging.  */

-  df_chain_top_dump,          /* Debugging start block.  */
-  df_chain_bottom_dump,       /* Debugging end block.  */
+  NULL,                       /* Debugging start block.  */
+  NULL,                       /* Debugging end block.  */

   NULL,                       /* Incremental solution verify start.  */
   NULL,                       /* Incremental solution verify end.  */
   NULL,                       /* Incremental solution verify start.  */
   NULL,                       /* Incremental solution verify end.  */

-  &problem_RD,                /* Dependent problem.  */
-  TV_DF_CHAIN,                /* Timing variable.  */
+  &problem_LR,                /* Dependent problem.  */
+  sizeof (struct df_scan_bb_info),/* Size of entry of block_info array.  */
+  TV_DF_NOTE,                 /* Timing variable.  */

   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
 };
 
   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
 };
 


@@ -3564,863 +3459,726 @@ static struct df_problem problem_CHAIN =
    solution.  */
 
 void
    solution.  */
 
 void

-df_chain_add_problem (enum df_chain_flags chain_flags)
+df_note_add_problem (void)

 {
 {

-  df_add_problem (&problem_CHAIN);
-  df_chain->local_flags = (unsigned int)chain_flags;
-  df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
+  df_add_problem (&problem_NOTE);

 }
 
 }
 

-#undef df_chain_problem_p
+

 
 \f
 /*----------------------------------------------------------------------------
 
 \f
 /*----------------------------------------------------------------------------

-   This pass computes REG_DEAD and REG_UNUSED notes.
-   ----------------------------------------------------------------------------*/
-
-static void 
-df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
-{
-  df_note->optional_p = true;
-}
-
-#ifdef REG_DEAD_DEBUGGING
-static void 
-df_print_note (const char *prefix, rtx insn, rtx note)
-{
-  if (dump_file)
-    {
-      fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
-      print_rtl (dump_file, note);
-      fprintf (dump_file, "\n");
-    }
-}
-#endif
-
+   Functions for simulating the effects of single insns.

 
 

-/* After reg-stack, the x86 floating point stack regs are difficult to
-   analyze because of all of the pushes, pops and rotations.  Thus, we
-   just leave the notes alone. */
+   You can either simulate in the forwards direction, starting from
+   the top of a block or the backwards direction from the end of the
+   block.  If you go backwards, defs are examined first to clear bits,
+   then uses are examined to set bits.  If you go forwards, defs are
+   examined first to set bits, then REG_DEAD and REG_UNUSED notes
+   are examined to clear bits.  In either case, the result of examining
+   a def can be undone (respectively by a use or a REG_UNUSED note).

 
 

-#ifdef STACK_REGS
-static inline bool 
-df_ignore_stack_reg (int regno)
-{
-  return regstack_completed
-    && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
-}
-#else
-static inline bool 
-df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
-{
-  return false;
-}
-#endif
+   If you start at the top of the block, use one of DF_LIVE_IN or
+   DF_LR_IN.  If you start at the bottom of the block use one of
+   DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
+   THEY WILL BE DESTROYED.
+----------------------------------------------------------------------------*/

 
 
 
 

-/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
-   them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */
+/* Find the set of DEFs for INSN.  */

 
 

-static void
-df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
+void
+df_simulate_find_defs (rtx insn, bitmap defs)

 {
 {

-  rtx *pprev = &REG_NOTES (insn);
-  rtx link = *pprev;
-  rtx dead = NULL;
-  rtx unused = NULL;
+  df_ref *def_rec;
+  unsigned int uid = INSN_UID (insn);

 
 

-  while (link)
+  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)

     {
     {

-      switch (REG_NOTE_KIND (link))
-       {
-       case REG_DEAD:
-         /* After reg-stack, we need to ignore any unused notes 
-            for the stack registers.  */
-         if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
-           {
-             pprev = &XEXP (link, 1);
-             link = *pprev;
-           }
-         else
-           {
-             rtx next = XEXP (link, 1);
-#ifdef REG_DEAD_DEBUGGING
-             df_print_note ("deleting: ", insn, link);
-#endif
-             XEXP (link, 1) = dead;
-             dead = link;
-             *pprev = link = next;
-           }
-         break;
-
-       case REG_UNUSED:
-         /* After reg-stack, we need to ignore any unused notes 
-            for the stack registers.  */
-         if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
-           {
-             pprev = &XEXP (link, 1);
-             link = *pprev;
-           }
-         else
-           {
-             rtx next = XEXP (link, 1);
-#ifdef REG_DEAD_DEBUGGING
-             df_print_note ("deleting: ", insn, link);
-#endif
-             XEXP (link, 1) = unused;
-             unused = link;
-             *pprev = link = next;
-           }
-         break;
-         
-       default:
-         pprev = &XEXP (link, 1);
-         link = *pprev;
-         break;
-       }
+      df_ref def = *def_rec;
+      bitmap_set_bit (defs, DF_REF_REGNO (def));

     }
     }

-
-  *old_dead_notes = dead;
-  *old_unused_notes = unused;
-}
-
-
-/* Set a NOTE_TYPE note for REG in INSN.  Try to pull it from the OLD
-   list, otherwise create a new one.  */
-
-static inline rtx
-df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
-{
-  rtx this = old;
-  rtx prev = NULL;
-
-  while (this)
-    if (XEXP (this, 0) == reg)
-      {
-       if (prev)
-         XEXP (prev, 1) = XEXP (this, 1);
-       else
-         old = XEXP (this, 1);
-       XEXP (this, 1) = REG_NOTES (insn);
-       REG_NOTES (insn) = this;
-       return old;
-      }
-    else
-      {
-       prev = this;
-       this = XEXP (this, 1);
-      }
-  
-  /* Did not find the note.  */
-  REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
-  return old;
-}
-
-/* A subroutine of df_set_unused_notes_for_mw, with a selection of its
-   arguments.  Return true if the register value described by MWS's
-   mw_reg is known to be completely unused, and if mw_reg can therefore
-   be used in a REG_UNUSED note.  */
-
-static bool
-df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
-                         bitmap live, bitmap artificial_uses)
-{
-  unsigned int r;
-
-  /* If MWS describes a partial reference, create REG_UNUSED notes for
-     individual hard registers.  */
-  if (mws->flags & DF_REF_PARTIAL)
-    return false;
-
-  /* Likewise if some part of the register is used.  */
-  for (r = mws->start_regno; r <= mws->end_regno; r++)
-    if (bitmap_bit_p (live, r)
-       || bitmap_bit_p (artificial_uses, r))
-      return false;
-
-  gcc_assert (REG_P (mws->mw_reg));
-  return true;

 }
 
 }
 

-/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
-   based on the bits in LIVE.  Do not generate notes for registers in
-   artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
-   not generated if the reg is both read and written by the
-   instruction.
-*/
+/* Find the set of real DEFs, which are not clobbers, for INSN.  */

 
 

-static rtx
-df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
-                           bitmap live, bitmap do_not_gen, 
-                           bitmap artificial_uses)
+void
+df_simulate_find_noclobber_defs (rtx insn, bitmap defs)

 {
 {

-  unsigned int r;
-  
-#ifdef REG_DEAD_DEBUGGING
-  if (dump_file)
-    fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n", 
-            mws->start_regno, mws->end_regno);
-#endif
+  df_ref *def_rec;
+  unsigned int uid = INSN_UID (insn);

 
 

-  if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
+  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)

     {
     {

-      unsigned int regno = mws->start_regno;
-      old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
-
-#ifdef REG_DEAD_DEBUGGING
-      df_print_note ("adding 1: ", insn, REG_NOTES (insn));
-#endif
-      bitmap_set_bit (do_not_gen, regno);
-      /* Only do this if the value is totally dead.  */
+      df_ref def = *def_rec;
+      if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
+       bitmap_set_bit (defs, DF_REF_REGNO (def));

     }
     }

-  else
-    for (r = mws->start_regno; r <= mws->end_regno; r++)
-      {
-       if (!bitmap_bit_p (live, r)
-           && !bitmap_bit_p (artificial_uses, r))
-         {
-           old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
-#ifdef REG_DEAD_DEBUGGING
-           df_print_note ("adding 2: ", insn, REG_NOTES (insn));
-#endif
-         }
-       bitmap_set_bit (do_not_gen, r);
-      }
-  return old;

 }
 
 
 }
 
 

-/* A subroutine of df_set_dead_notes_for_mw, with a selection of its
-   arguments.  Return true if the register value described by MWS's
-   mw_reg is known to be completely dead, and if mw_reg can therefore
-   be used in a REG_DEAD note.  */
+/* Simulate the effects of the defs of INSN on LIVE.  */

 
 

-static bool
-df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
-                       bitmap live, bitmap artificial_uses,
-                       bitmap do_not_gen)
+void
+df_simulate_defs (rtx insn, bitmap live)

 {
 {

-  unsigned int r;
-
-  /* If MWS describes a partial reference, create REG_DEAD notes for
-     individual hard registers.  */
-  if (mws->flags & DF_REF_PARTIAL)
-    return false;
+  df_ref *def_rec;
+  unsigned int uid = INSN_UID (insn);

 
 

-  /* Likewise if some part of the register is not dead.  */
-  for (r = mws->start_regno; r <= mws->end_regno; r++)
-    if (bitmap_bit_p (live, r)
-       || bitmap_bit_p (artificial_uses, r)
-       || bitmap_bit_p (do_not_gen, r))
-      return false;
+  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      unsigned int dregno = DF_REF_REGNO (def);

 
 

-  gcc_assert (REG_P (mws->mw_reg));
-  return true;
+      /* If the def is to only part of the reg, it does
+        not kill the other defs that reach here.  */
+      if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+       bitmap_clear_bit (live, dregno);
+    }

 }
 
 }
 

-/* Set the REG_DEAD notes for the multiword hardreg use in INSN based
-   on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
-   from being set if the instruction both reads and writes the
-   register.  */

 
 

-static rtx
-df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
-                         bitmap live, bitmap do_not_gen,
-                         bitmap artificial_uses)
+/* Simulate the effects of the uses of INSN on LIVE.  */
+
+void
+df_simulate_uses (rtx insn, bitmap live)

 {
 {

-  unsigned int r;
-  
-#ifdef REG_DEAD_DEBUGGING
-  if (dump_file)
-    {
-      fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =", 
-              mws->start_regno, mws->end_regno);
-      df_print_regset (dump_file, do_not_gen);
-      fprintf (dump_file, "  live =");
-      df_print_regset (dump_file, live);
-      fprintf (dump_file, "  artificial uses =");
-      df_print_regset (dump_file, artificial_uses);
-    }
-#endif
+  df_ref *use_rec;
+  unsigned int uid = INSN_UID (insn);

 
 

-  if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
+  if (DEBUG_INSN_P (insn))
+    return;
+
+  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)

     {
     {

-      /* Add a dead note for the entire multi word register.  */
-      old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
-#ifdef REG_DEAD_DEBUGGING
-      df_print_note ("adding 1: ", insn, REG_NOTES (insn));
-#endif
+      df_ref use = *use_rec;
+      /* Add use to set of uses in this BB.  */
+      bitmap_set_bit (live, DF_REF_REGNO (use));

     }
     }

+}
+
+
+/* Add back the always live regs in BB to LIVE.  */
+
+static inline void
+df_simulate_fixup_sets (basic_block bb, bitmap live)
+{
+  /* These regs are considered always live so if they end up dying
+     because of some def, we need to bring the back again.  */
+  if (bb_has_eh_pred (bb))
+    bitmap_ior_into (live, &df->eh_block_artificial_uses);

   else
   else

-    {
-      for (r = mws->start_regno; r <= mws->end_regno; r++)
-       if (!bitmap_bit_p (live, r)
-           && !bitmap_bit_p (artificial_uses, r)
-           && !bitmap_bit_p (do_not_gen, r))
-         {
-           old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
-#ifdef REG_DEAD_DEBUGGING
-           df_print_note ("adding 2: ", insn, REG_NOTES (insn));
-#endif
-         }
-    }
-  return old;
+    bitmap_ior_into (live, &df->regular_block_artificial_uses);

 }
 
 
 }
 
 

-/* Create a REG_UNUSED note if necessary for DEF in INSN updating LIVE
-   and DO_NOT_GEN.  Do not generate notes for registers in artificial
-   uses.  */
+/*----------------------------------------------------------------------------
+   The following three functions are used only for BACKWARDS scanning:
+   i.e. they process the defs before the uses.
+
+   df_simulate_initialize_backwards should be called first with a
+   bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
+   df_simulate_one_insn_backwards should be called for each insn in
+   the block, starting with the last one.  Finally,
+   df_simulate_finalize_backwards can be called to get a new value
+   of the sets at the top of the block (this is rarely used).
+   ----------------------------------------------------------------------------*/
+
+/* Apply the artificial uses and defs at the end of BB in a backwards
+   direction.  */

 
 

-static rtx
-df_create_unused_note (rtx insn, rtx old, struct df_ref *def, 
-                      bitmap live, bitmap do_not_gen, bitmap artificial_uses)
+void
+df_simulate_initialize_backwards (basic_block bb, bitmap live)

 {
 {

-  unsigned int dregno = DF_REF_REGNO (def);
-  
-#ifdef REG_DEAD_DEBUGGING
-  if (dump_file)
+  df_ref *def_rec;
+  df_ref *use_rec;
+  int bb_index = bb->index;
+
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)

     {
     {

-      fprintf (dump_file, "  regular looking at def ");
-      df_ref_debug (def, dump_file);
+      df_ref def = *def_rec;
+      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+       bitmap_clear_bit (live, DF_REF_REGNO (def));

     }
     }

-#endif

 
 

-  if (!(bitmap_bit_p (live, dregno)
-       || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
-       || bitmap_bit_p (artificial_uses, dregno)
-       || df_ignore_stack_reg (dregno)))
+  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)

     {
     {

-      rtx reg = (DF_REF_LOC (def)) 
-                ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
-      old = df_set_note (REG_UNUSED, insn, old, reg);
-#ifdef REG_DEAD_DEBUGGING
-      df_print_note ("adding 3: ", insn, REG_NOTES (insn));
-#endif
+      df_ref use = *use_rec;
+      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
+       bitmap_set_bit (live, DF_REF_REGNO (use));

     }
     }

-  
-  if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
-    bitmap_set_bit (do_not_gen, dregno);
-  
-  /* Kill this register if it is not a subreg store or conditional store.  */
-  if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-    bitmap_clear_bit (live, dregno);
-  return old;

 }
 
 
 }
 
 

-/* Recompute the REG_DEAD and REG_UNUSED notes and compute register
-   info: lifetime, bb, and number of defs and uses for basic block
-   BB.  The three bitvectors are scratch regs used here.  */
+/* Simulate the backwards effects of INSN on the bitmap LIVE.  */

 
 

-static void
-df_note_bb_compute (unsigned int bb_index, 
-                 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
+void
+df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)

 {
 {

-  basic_block bb = BASIC_BLOCK (bb_index);
-  rtx insn;
-  struct df_ref **def_rec;
-  struct df_ref **use_rec;
+  if (!NONDEBUG_INSN_P (insn))
+    return;

 
 

-  bitmap_copy (live, df_get_live_out (bb));
-  bitmap_clear (artificial_uses);
+  df_simulate_defs (insn, live);
+  df_simulate_uses (insn, live);
+  df_simulate_fixup_sets (bb, live);
+}

 
 

-#ifdef REG_DEAD_DEBUGGING
-  if (dump_file)
-    {
-      fprintf (dump_file, "live at bottom ");
-      df_print_regset (dump_file, live);
-    }
+
+/* Apply the artificial uses and defs at the top of BB in a backwards
+   direction.  */
+
+void
+df_simulate_finalize_backwards (basic_block bb, bitmap live)
+{
+  df_ref *def_rec;
+#ifdef EH_USES
+  df_ref *use_rec;

 #endif
 #endif

+  int bb_index = bb->index;

 
 

-  /* Process the artificial defs and uses at the bottom of the block
-     to begin processing.  */

   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
     {
   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
     {

-      struct df_ref *def = *def_rec;
-#ifdef REG_DEAD_DEBUGGING
-      if (dump_file)
-       fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
-#endif
-
-      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+      df_ref def = *def_rec;
+      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)

        bitmap_clear_bit (live, DF_REF_REGNO (def));
     }
 
        bitmap_clear_bit (live, DF_REF_REGNO (def));
     }
 

+#ifdef EH_USES

   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
     {
   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
     {

-      struct df_ref *use = *use_rec;
-      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
-       {
-         unsigned int regno = DF_REF_REGNO (use);
-         bitmap_set_bit (live, regno);
-         
-         /* Notes are not generated for any of the artificial registers
-            at the bottom of the block.  */
-         bitmap_set_bit (artificial_uses, regno);
-       }
-    }
-  
-#ifdef REG_DEAD_DEBUGGING
-  if (dump_file)
-    {
-      fprintf (dump_file, "live before artificials out ");
-      df_print_regset (dump_file, live);
+      df_ref use = *use_rec;
+      if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
+       bitmap_set_bit (live, DF_REF_REGNO (use));

     }
 #endif
     }
 #endif

+}
+/*----------------------------------------------------------------------------
+   The following three functions are used only for FORWARDS scanning:
+   i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
+   Thus it is important to add the DF_NOTES problem to the stack of
+   problems computed before using these functions.
+
+   df_simulate_initialize_forwards should be called first with a
+   bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
+   df_simulate_one_insn_forwards should be called for each insn in
+   the block, starting with the first one.
+   ----------------------------------------------------------------------------*/

 
 

-  FOR_BB_INSNS_REVERSE (bb, insn)
+/* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
+   DF_LR_IN for basic block BB, for forward scanning by marking artificial
+   defs live.  */
+
+void
+df_simulate_initialize_forwards (basic_block bb, bitmap live)
+{
+  df_ref *def_rec;
+  int bb_index = bb->index;
+
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)

     {
     {

-      unsigned int uid = INSN_UID (insn);
-      struct df_mw_hardreg **mws_rec;
-      rtx old_dead_notes;
-      rtx old_unused_notes;
- 
-      if (!INSN_P (insn))
-       continue;
+      df_ref def = *def_rec;
+      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+       bitmap_set_bit (live, DF_REF_REGNO (def));
+    }
+}

 
 

-      bitmap_clear (do_not_gen);
-      df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
+/* Simulate the forwards effects of INSN on the bitmap LIVE.  */

 
 

-      /* Process the defs.  */
-      if (CALL_P (insn))
-       {
-#ifdef REG_DEAD_DEBUGGING
-         if (dump_file)
-           {
-             fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
-             df_print_regset (dump_file, live);
-           }
-#endif
-         /* We only care about real sets for calls.  Clobbers cannot
-            be depended on to really die.  */
-         mws_rec = DF_INSN_UID_MWS (uid);
-         while (*mws_rec)
-           {
-             struct df_mw_hardreg *mws = *mws_rec; 
-             if ((mws->type == DF_REF_REG_DEF) 
-                 && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
-               old_unused_notes 
-                 = df_set_unused_notes_for_mw (insn, old_unused_notes, 
-                                               mws, live, do_not_gen, 
-                                               artificial_uses);
-             mws_rec++;
-           }
+void
+df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
+{
+  rtx link;
+  if (! INSN_P (insn))
+    return;

 
 

-         /* All of the defs except the return value are some sort of
-            clobber.  This code is for the return.  */
-         for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
-           {
-             struct df_ref *def = *def_rec;
-             if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
-               old_unused_notes
-                 = df_create_unused_note (insn, old_unused_notes, 
-                                          def, live, do_not_gen, 
-                                          artificial_uses);
-
-             /* However a may or must clobber still needs to kill the
-                reg so that REG_DEAD notes are later placed
-                appropriately.  */ 
-             else 
-               bitmap_clear_bit (live, DF_REF_REGNO (def));
-           }
-       }
-      else
-       {
-         /* Regular insn.  */
-         mws_rec = DF_INSN_UID_MWS (uid);
-         while (*mws_rec)
-           {
-             struct df_mw_hardreg *mws = *mws_rec; 
-             if (mws->type == DF_REF_REG_DEF)
-               old_unused_notes
-                 = df_set_unused_notes_for_mw (insn, old_unused_notes, 
-                                               mws, live, do_not_gen, 
-                                               artificial_uses);
-             mws_rec++;
-           }
+  /* Make sure that DF_NOTE really is an active df problem.  */
+  gcc_assert (df_note);

 
 

-         for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
-           {
-             struct df_ref *def = *def_rec;
-             old_unused_notes
-               = df_create_unused_note (insn, old_unused_notes, 
-                                        def, live, do_not_gen, 
-                                        artificial_uses);
-           }
-       }
-      
-      /* Process the uses.  */
-      mws_rec = DF_INSN_UID_MWS (uid);
-      while (*mws_rec)
+  /* Note that this is the opposite as how the problem is defined, because
+     in the LR problem defs _kill_ liveness.  However, they do so backwards,
+     while here the scan is performed forwards!  So, first assume that the
+     def is live, and if this is not true REG_UNUSED notes will rectify the
+     situation.  */
+  df_simulate_find_noclobber_defs (insn, live);
+
+  /* Clear all of the registers that go dead.  */
+  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+    {
+      switch (REG_NOTE_KIND (link))

        {
        {

-         struct df_mw_hardreg *mws = *mws_rec; 
-         if ((mws->type != DF_REF_REG_DEF)  
-             && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
-           old_dead_notes
-             = df_set_dead_notes_for_mw (insn, old_dead_notes, 
-                                         mws, live, do_not_gen,
-                                         artificial_uses);
-         mws_rec++;
+       case REG_DEAD:
+       case REG_UNUSED:
+         {
+           rtx reg = XEXP (link, 0);
+           int regno = REGNO (reg);
+           if (regno < FIRST_PSEUDO_REGISTER)
+             {
+               int n = hard_regno_nregs[regno][GET_MODE (reg)];
+               while (--n >= 0)
+                 bitmap_clear_bit (live, regno + n);
+             }
+           else
+             bitmap_clear_bit (live, regno);
+         }
+         break;
+       default:
+         break;

        }
        }

+    }
+  df_simulate_fixup_sets (bb, live);
+}

 
 

-      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
-       {
-         struct df_ref *use = *use_rec;
-         unsigned int uregno = DF_REF_REGNO (use);

 
 

-#ifdef REG_DEAD_DEBUGGING
-         if (dump_file)
-           {
-             fprintf (dump_file, "  regular looking at use ");
-             df_ref_debug (use, dump_file);
-           }
-#endif
-         if (!bitmap_bit_p (live, uregno))
-           {
-             if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
-                  && (!bitmap_bit_p (do_not_gen, uregno))
-                  && (!bitmap_bit_p (artificial_uses, uregno))
-                  && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
-                  && (!df_ignore_stack_reg (uregno)))
-               {
-                 rtx reg = (DF_REF_LOC (use)) 
-                            ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
-                 old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
+\f
+/*----------------------------------------------------------------------------
+   MULTIPLE DEFINITIONS

 
 

-#ifdef REG_DEAD_DEBUGGING
-                 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
-#endif
-               }
-             /* This register is now live.  */
-             bitmap_set_bit (live, uregno);
-           }
-       }
+   Find the locations in the function reached by multiple definition sites
+   for a live pseudo.  In and out bitvectors are built for each basic
+   block.  They are restricted for efficiency to live registers.
+
+   The gen and kill sets for the problem are obvious.  Together they
+   include all defined registers in a basic block; the gen set includes
+   registers where a partial or conditional or may-clobber definition is
+   last in the BB, while the kill set includes registers with a complete
+   definition coming last.  However, the computation of the dataflow
+   itself is interesting.
+
+   The idea behind it comes from SSA form's iterated dominance frontier
+   criterion for inserting PHI functions.  Just like in that case, we can use
+   the dominance frontier to find places where multiple definitions meet;
+   a register X defined in a basic block BB1 has multiple definitions in
+   basic blocks in BB1's dominance frontier.
+
+   So, the in-set of a basic block BB2 is not just the union of the
+   out-sets of BB2's predecessors, but includes some more bits that come
+   from the basic blocks of whose dominance frontier BB2 is part (BB1 in
+   the previous paragraph).  I called this set the init-set of BB2.
+
+      (Note: I actually use the kill-set only to build the init-set.
+      gen bits are anyway propagated from BB1 to BB2 by dataflow).
+
+    For example, if you have
+
+       BB1 : r10 = 0
+             r11 = 0
+             if <...> goto BB2 else goto BB3;
+
+       BB2 : r10 = 1
+             r12 = 1
+             goto BB3;
+
+       BB3 :
+
+    you have BB3 in BB2's dominance frontier but not in BB1's, so that the
+    init-set of BB3 includes r10 and r12, but not r11.  Note that we do
+    not need to iterate the dominance frontier, because we do not insert
+    anything like PHI functions there!  Instead, dataflow will take care of
+    propagating the information to BB3's successors.
+   ---------------------------------------------------------------------------*/
+
+/* Private data used to verify the solution for this problem.  */
+struct df_md_problem_data
+{
+  /* An obstack for the bitmaps we need for this problem.  */
+  bitmap_obstack md_bitmaps;
+};
+
+/* Scratch var used by transfer functions.  This is used to do md analysis
+   only for live registers.  */
+static bitmap_head df_md_scratch;

 
 

-      while (old_unused_notes)
-       {
-         rtx next = XEXP (old_unused_notes, 1);
-         free_EXPR_LIST_node (old_unused_notes);
-         old_unused_notes = next;
-       }
-      while (old_dead_notes)
-       {
-         rtx next = XEXP (old_dead_notes, 1);
-         free_EXPR_LIST_node (old_dead_notes);
-         old_dead_notes = next;
-       }
+
+static void
+df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
+                    void *vbb_info)
+{
+  struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
+  if (bb_info)
+    {
+      bitmap_clear (&bb_info->kill);
+      bitmap_clear (&bb_info->gen);
+      bitmap_clear (&bb_info->init);
+      bitmap_clear (&bb_info->in);
+      bitmap_clear (&bb_info->out);

     }
 }
 
 
     }
 }
 
 

-/* Compute register info: lifetime, bb, and number of defs and uses.  */
+/* Allocate or reset bitmaps for DF_MD. The solution bits are
+   not touched unless the block is new.  */
+

 static void
 static void

-df_note_compute (bitmap all_blocks)
+df_md_alloc (bitmap all_blocks)

 {
   unsigned int bb_index;
   bitmap_iterator bi;
 {
   unsigned int bb_index;
   bitmap_iterator bi;

-  bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
-  bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
-  bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
+  struct df_md_problem_data *problem_data;

 
 

-#ifdef REG_DEAD_DEBUGGING
-  if (dump_file)
-    print_rtl_with_bb (dump_file, get_insns());
-#endif
+  df_grow_bb_info (df_md);
+  if (df_md->problem_data)
+    problem_data = (struct df_md_problem_data *) df_md->problem_data;
+  else
+    {
+      problem_data = XNEW (struct df_md_problem_data);
+      df_md->problem_data = problem_data;
+      bitmap_obstack_initialize (&problem_data->md_bitmaps);
+    }
+  bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);

 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)

-  {
-    df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
-  }
+    {
+      struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+      /* When bitmaps are already initialized, just clear them.  */
+      if (bb_info->init.obstack)
+        {
+          bitmap_clear (&bb_info->init);
+          bitmap_clear (&bb_info->gen);
+          bitmap_clear (&bb_info->kill);
+          bitmap_clear (&bb_info->in);
+          bitmap_clear (&bb_info->out);
+        }
+      else
+        {
+         bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
+         bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
+         bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
+         bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
+         bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
+        }
+    }

 
 

-  BITMAP_FREE (live);
-  BITMAP_FREE (do_not_gen);
-  BITMAP_FREE (artificial_uses);
+  df_md->optional_p = true;

 }
 
 }
 

+/* Add the effect of the top artificial defs of BB to the multiple definitions
+   bitmap LOCAL_MD.  */

 
 

-/* Free all storage associated with the problem.  */
-
-static void
-df_note_free (void)
+void
+df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)

 {
 {

-  free (df_note);
+  int bb_index = bb->index;
+  df_ref *def_rec;
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+       {
+         unsigned int dregno = DF_REF_REGNO (def);
+         if (DF_REF_FLAGS (def)
+             & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
+           bitmap_set_bit (local_md, dregno);
+         else
+           bitmap_clear_bit (local_md, dregno);
+       }
+    }

 }
 
 
 }
 
 

-/* All of the information associated every instance of the problem.  */
+/* Add the effect of the defs of INSN to the reaching definitions bitmap
+   LOCAL_MD.  */

 
 

-static struct df_problem problem_NOTE =
+void
+df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
+                        bitmap local_md)

 {
 {

-  DF_NOTE,                    /* Problem id.  */
-  DF_NONE,                    /* Direction.  */
-  df_note_alloc,              /* Allocate the problem specific data.  */
-  NULL,                       /* Reset global information.  */
-  NULL,                       /* Free basic block info.  */
-  df_note_compute,            /* Local compute function.  */
-  NULL,                       /* Init the solution specific data.  */
-  NULL,                       /* Iterative solver.  */
-  NULL,                       /* Confluence operator 0.  */ 
-  NULL,                       /* Confluence operator n.  */ 
-  NULL,                       /* Transfer function.  */
-  NULL,                       /* Finalize function.  */
-  df_note_free,               /* Free all of the problem information.  */
-  df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
-  NULL,                       /* Debugging.  */
-  NULL,                       /* Debugging start block.  */
-  NULL,                       /* Debugging end block.  */
-  NULL,                       /* Incremental solution verify start.  */
-  NULL,                       /* Incremental solution verify end.  */
-
-  /* Technically this is only dependent on the live registers problem
-     but it will produce information if built one of uninitialized
-     register problems (UR, UREC) is also run.  */
-  &problem_LR,                /* Dependent problem.  */
-  TV_DF_NOTE,                 /* Timing variable.  */
-  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
-};
-
+  unsigned uid = INSN_UID (insn);
+  df_ref *def_rec;

 
 

-/* Create a new DATAFLOW instance and add it to an existing instance
-   of DF.  The returned structure is what is used to get at the
-   solution.  */
+  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      unsigned int dregno = DF_REF_REGNO (def);
+      if ((!(df->changeable_flags & DF_NO_HARD_REGS))
+          || (dregno >= FIRST_PSEUDO_REGISTER))
+        {
+          if (DF_REF_FLAGS (def)
+             & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
+           bitmap_set_bit (local_md, DF_REF_ID (def));
+         else
+           bitmap_clear_bit (local_md, DF_REF_ID (def));
+        }
+    }
+}

 
 

-void
-df_note_add_problem (void)
+static void
+df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
+                                    df_ref *def_rec,
+                                    int top_flag)

 {
 {

-  df_add_problem (&problem_NOTE);
+  df_ref def;
+  bitmap_clear (&seen_in_insn);
+
+  while ((def = *def_rec++) != NULL)
+    {
+      unsigned int dregno = DF_REF_REGNO (def);
+      if (((!(df->changeable_flags & DF_NO_HARD_REGS))
+           || (dregno >= FIRST_PSEUDO_REGISTER))
+         && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
+       {
+          if (!bitmap_bit_p (&seen_in_insn, dregno))
+           {
+             if (DF_REF_FLAGS (def)
+                 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
+               {
+                 bitmap_set_bit (&bb_info->gen, dregno);
+                 bitmap_clear_bit (&bb_info->kill, dregno);
+               }
+             else
+               {
+                 /* When we find a clobber and a regular def,
+                    make sure the regular def wins.  */
+                 bitmap_set_bit (&seen_in_insn, dregno);
+                 bitmap_set_bit (&bb_info->kill, dregno);
+                 bitmap_clear_bit (&bb_info->gen, dregno);
+               }
+           }
+       }
+    }

 }
 
 
 }
 
 

+/* Compute local multiple def info for basic block BB.  */

 
 

-\f
-/*----------------------------------------------------------------------------
-   Functions for simulating the effects of single insns.  
+static void
+df_md_bb_local_compute (unsigned int bb_index)
+{
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+  rtx insn;

 
 

-   You can either simulate in the forwards direction, starting from
-   the top of a block or the backwards direction from the end of the
-   block.  The main difference is that if you go forwards, the uses
-   are examined first then the defs, and if you go backwards, the defs
-   are examined first then the uses.
+  /* Artificials are only hard regs.  */
+  if (!(df->changeable_flags & DF_NO_HARD_REGS))
+    df_md_bb_local_compute_process_def (bb_info,
+                                        df_get_artificial_defs (bb_index),
+                                        DF_REF_AT_TOP);

 
 

-   If you start at the top of the block, use one of DF_LIVE_IN or
-   DF_LR_IN.  If you start at the bottom of the block use one of
-   DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
-   THEY WILL BE DESTROYED.
+  FOR_BB_INSNS (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+      if (!INSN_P (insn))
+        continue;

 
 

-----------------------------------------------------------------------------*/
+      df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
+    }

 
 

+  if (!(df->changeable_flags & DF_NO_HARD_REGS))
+    df_md_bb_local_compute_process_def (bb_info,
+                                        df_get_artificial_defs (bb_index),
+                                        0);
+}

 
 

-/* Find the set of DEFs for INSN.  */
+/* Compute local reaching def info for each basic block within BLOCKS.  */

 
 

-void
-df_simulate_find_defs (rtx insn, bitmap defs)
+static void
+df_md_local_compute (bitmap all_blocks)

 {
 {

-  struct df_ref **def_rec;
-  unsigned int uid = INSN_UID (insn);
+  unsigned int bb_index, df_bb_index;
+  bitmap_iterator bi1, bi2;
+  basic_block bb;
+  bitmap_head *frontiers;

 
 

-  if (CALL_P (insn))
+  bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)

     {
     {

-      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
-       {
-         struct df_ref *def = *def_rec;
-         unsigned int dregno = DF_REF_REGNO (def);
-         
-         if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
-           {
-             if (dregno >= FIRST_PSEUDO_REGISTER
-                 || !(SIBLING_CALL_P (insn)
-                      && bitmap_bit_p (df->exit_block_uses, dregno)
-                      && !refers_to_regno_p (dregno, dregno+1,
-                                             current_function_return_rtx,
-                                             (rtx *)0)))
-               {
-                 /* If the def is to only part of the reg, it does
-                    not kill the other defs that reach here.  */
-                 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-                   bitmap_set_bit (defs, dregno);
-               }
-           }
-         else
-           /* This is the return value.  */
-           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-             bitmap_set_bit (defs, dregno);
-       }
+      df_md_bb_local_compute (bb_index);

     }
     }

-  else
+
+  bitmap_clear (&seen_in_insn);
+
+  frontiers = XNEWVEC (bitmap_head, last_basic_block);
+  FOR_ALL_BB (bb)
+    bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
+
+  compute_dominance_frontiers (frontiers);
+
+  /* Add each basic block's kills to the nodes in the frontier of the BB.  */
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)

     {
     {

-      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+      bitmap kill = &df_md_get_bb_info (bb_index)->kill;
+      EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)

        {
        {

-         struct df_ref *def = *def_rec;
-         /* If the def is to only part of the reg, it does
-            not kill the other defs that reach here.  */
-         if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-           bitmap_set_bit (defs, DF_REF_REGNO (def));
+         basic_block bb = BASIC_BLOCK (df_bb_index);
+         if (bitmap_bit_p (all_blocks, df_bb_index))
+           bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
+                                df_get_live_in (bb));

        }
     }
        }
     }

+
+  FOR_ALL_BB (bb)
+    bitmap_clear (&frontiers[bb->index]);
+  free (frontiers);

 }
 
 
 }
 
 

-/* Simulate the effects of the defs of INSN on LIVE.  */
+/* Reset the global solution for recalculation.  */

 
 

-void
-df_simulate_defs (rtx insn, bitmap live)
+static void
+df_md_reset (bitmap all_blocks)

 {
 {

-  struct df_ref **def_rec;
-  unsigned int uid = INSN_UID (insn);
+  unsigned int bb_index;
+  bitmap_iterator bi;

 
 

-  if (CALL_P (insn))
-    {
-      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
-       {
-         struct df_ref *def = *def_rec;
-         unsigned int dregno = DF_REF_REGNO (def);
-         
-         if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
-           {
-             if (dregno >= FIRST_PSEUDO_REGISTER
-                 || !(SIBLING_CALL_P (insn)
-                      && bitmap_bit_p (df->exit_block_uses, dregno)
-                      && !refers_to_regno_p (dregno, dregno+1,
-                                             current_function_return_rtx,
-                                             (rtx *)0)))
-               {
-                 /* If the def is to only part of the reg, it does
-                    not kill the other defs that reach here.  */
-                 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-                   bitmap_clear_bit (live, dregno);
-               }
-           }
-         else
-           /* This is the return value.  */
-           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-             bitmap_clear_bit (live, dregno);
-       }
-    }
-  else
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)

     {
     {

-      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
-       {
-         struct df_ref *def = *def_rec;
-         unsigned int dregno = DF_REF_REGNO (def);
-  
-         /* If the def is to only part of the reg, it does
-            not kill the other defs that reach here.  */
-         if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
-           bitmap_clear_bit (live, dregno);
-       }
+      struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+      gcc_assert (bb_info);
+      bitmap_clear (&bb_info->in);
+      bitmap_clear (&bb_info->out);

     }
     }

-}  
+}

 
 

+static bool
+df_md_transfer_function (int bb_index)
+{
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+  bitmap in = &bb_info->in;
+  bitmap out = &bb_info->out;
+  bitmap gen = &bb_info->gen;
+  bitmap kill = &bb_info->kill;
+
+  /* We need to use a scratch set here so that the value returned from this
+     function invocation properly reflects whether the sets changed in a
+     significant way; i.e. not just because the live set was anded in.  */
+  bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
+
+  /* Multiple definitions of a register are not relevant if it is not
+     live.  Thus we trim the result to the places where it is live.  */
+  bitmap_and_into (in, df_get_live_in (bb));
+
+  return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
+}

 
 

-/* Simulate the effects of the uses of INSN on LIVE.  */
+/* Initialize the solution bit vectors for problem.  */

 
 

-void 
-df_simulate_uses (rtx insn, bitmap live)
+static void
+df_md_init (bitmap all_blocks)

 {
 {

-  struct df_ref **use_rec;
-  unsigned int uid = INSN_UID (insn);
+  unsigned int bb_index;
+  bitmap_iterator bi;

 
 

-  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)

     {
     {

-      struct df_ref *use = *use_rec;
-      /* Add use to set of uses in this BB.  */
-      bitmap_set_bit (live, DF_REF_REGNO (use));
+      struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+
+      bitmap_copy (&bb_info->in, &bb_info->init);
+      df_md_transfer_function (bb_index);

     }
 }
 
     }
 }
 

+static void
+df_md_confluence_0 (basic_block bb)
+{
+  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
+  bitmap_copy (&bb_info->in, &bb_info->init);
+}

 
 

-/* Add back the always live regs in BB to LIVE.  */
+/* In of target gets or of out of source.  */

 
 

-static inline void
-df_simulate_fixup_sets (basic_block bb, bitmap live)
+static bool
+df_md_confluence_n (edge e)

 {
 {

-  /* These regs are considered always live so if they end up dying
-     because of some def, we need to bring the back again.  */
-  if (df_has_eh_preds (bb))
-    bitmap_ior_into (live, df->eh_block_artificial_uses);
+  bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
+  bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
+
+  if (e->flags & EDGE_FAKE)
+    return false;
+
+  if (e->flags & EDGE_EH)
+    return bitmap_ior_and_compl_into (op1, op2,
+                                     regs_invalidated_by_call_regset);

   else
   else

-    bitmap_ior_into (live, df->regular_block_artificial_uses);
+    return bitmap_ior_into (op1, op2);

 }
 
 }
 

+/* Free all storage associated with the problem.  */

 
 

-/* Apply the artificial uses and defs at the top of BB in a forwards
-   direction.  */
-
-void 
-df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
+static void
+df_md_free (void)

 {
 {

-  struct df_ref **def_rec;
-  struct df_ref **use_rec;
-  int bb_index = bb->index;
-  
-  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
-    {
-      struct df_ref *use = *use_rec;
-      if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
-       bitmap_set_bit (live, DF_REF_REGNO (use));
-    }
+  struct df_md_problem_data *problem_data
+    = (struct df_md_problem_data *) df_md->problem_data;

 
 

-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
-    {
-      struct df_ref *def = *def_rec;
-      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
-       bitmap_clear_bit (live, DF_REF_REGNO (def));
-    }
+  bitmap_obstack_release (&problem_data->md_bitmaps);
+  free (problem_data);
+  df_md->problem_data = NULL;
+
+  df_md->block_info_size = 0;
+  free (df_md->block_info);
+  df_md->block_info = NULL;
+  free (df_md);

 }
 
 
 }
 
 

-/* Simulate the forwards effects of INSN on the bitmap LIVE.  */
+/* Debugging info at top of bb.  */

 
 

-void 
-df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
+static void
+df_md_top_dump (basic_block bb, FILE *file)

 {
 {

-  if (! INSN_P (insn))
-    return;    
-  
-  df_simulate_uses (insn, live);
-  df_simulate_defs (insn, live);
-  df_simulate_fixup_sets (bb, live);
-}
+  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
+  if (!bb_info)
+    return;

 
 

+  fprintf (file, ";; md  in  \t");
+  df_print_regset (file, &bb_info->in);
+  fprintf (file, ";; md  init  \t");
+  df_print_regset (file, &bb_info->init);
+  fprintf (file, ";; md  gen \t");
+  df_print_regset (file, &bb_info->gen);
+  fprintf (file, ";; md  kill \t");
+  df_print_regset (file, &bb_info->kill);
+}

 
 

-/* Apply the artificial uses and defs at the end of BB in a backwards
-   direction.  */
+/* Debugging info at bottom of bb.  */

 
 

-void 
-df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
+static void
+df_md_bottom_dump (basic_block bb, FILE *file)

 {
 {

-  struct df_ref **def_rec;
-  struct df_ref **use_rec;
-  int bb_index = bb->index;
-  
-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
-    {
-      struct df_ref *def = *def_rec;
-      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
-       bitmap_clear_bit (live, DF_REF_REGNO (def));
-    }
+  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
+  if (!bb_info)
+    return;

 
 

-  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
-    {
-      struct df_ref *use = *use_rec;
-      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
-       bitmap_set_bit (live, DF_REF_REGNO (use));
-    }
+  fprintf (file, ";; md  out \t");
+  df_print_regset (file, &bb_info->out);

 }
 
 }
 

+static struct df_problem problem_MD =
+{
+  DF_MD,                      /* Problem id.  */
+  DF_FORWARD,                 /* Direction.  */
+  df_md_alloc,                /* Allocate the problem specific data.  */
+  df_md_reset,                /* Reset global information.  */
+  df_md_free_bb_info,         /* Free basic block info.  */
+  df_md_local_compute,        /* Local compute function.  */
+  df_md_init,                 /* Init the solution specific data.  */
+  df_worklist_dataflow,       /* Worklist solver.  */
+  df_md_confluence_0,         /* Confluence operator 0.  */
+  df_md_confluence_n,         /* Confluence operator n.  */
+  df_md_transfer_function,    /* Transfer function.  */
+  NULL,                       /* Finalize function.  */
+  df_md_free,                 /* Free all of the problem information.  */
+  df_md_free,                 /* Remove this problem from the stack of dataflow problems.  */
+  NULL,                       /* Debugging.  */
+  df_md_top_dump,             /* Debugging start block.  */
+  df_md_bottom_dump,          /* Debugging end block.  */
+  NULL,                              /* Incremental solution verify start.  */
+  NULL,                              /* Incremental solution verify end.  */
+  NULL,                       /* Dependent problem.  */
+  sizeof (struct df_md_bb_info),/* Size of entry of block_info array.  */
+  TV_DF_MD,                   /* Timing variable.  */
+  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
+};

 
 

-/* Simulate the backwards effects of INSN on the bitmap LIVE.  */
+/* Create a new MD instance and add it to the existing instance
+   of DF.  */

 
 

-void 
-df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
+void
+df_md_add_problem (void)

 {
 {

-  if (! INSN_P (insn))
-    return;    
-  
-  df_simulate_defs (insn, live);
-  df_simulate_uses (insn, live);
-  df_simulate_fixup_sets (bb, live);
+  df_add_problem (&problem_MD);

 }
 
 
 }
 
 

+