2007-05-04 Tobias Burnus <burnus@net-b.de>

[official-gcc.git] / gcc / df-core.c

/* Allocation for dataflow support routines.
   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
   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).

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING.  If not, write to the Free
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.  
*/

/*
OVERVIEW:

The files in this collection (df*.c,df.h) provide a general framework
for solving dataflow problems.  The global dataflow is performed using
a good implementation of iterative dataflow analysis.

The file df-problems.c provides problem instance for the most common
dataflow problems: reaching defs, upward exposed uses, live variables,
uninitialized variables, def-use chains, and use-def chains.  However,
the interface allows other dataflow problems to be defined as well.


USAGE:

Here is an example of using the dataflow routines.

      struct df *df;

      df = df_init (init_flags);
      
      df_add_problem (df, problem, flags);

      df_set_blocks (df, blocks);

      df_rescan_blocks (df, blocks);

      df_analyze (df);

      df_dump (df, stderr);

      df_finish (df);



DF_INIT simply creates a poor man's object (df) that needs to be
passed to all the dataflow routines.  df_finish destroys this object
and frees up any allocated memory.

There are three flags that can be passed to df_init, each of these
flags controls the scanning of the rtl:

DF_HARD_REGS means that the scanning is to build information about
both pseudo registers and hardware registers.  Without this
information, the problems will be solved only on pseudo registers.
DF_EQUIV_NOTES marks the uses present in EQUIV/EQUAL notes.
DF_SUBREGS return subregs rather than the inner reg.


DF_ADD_PROBLEM adds a problem, defined by an instance to struct
df_problem, to the set of problems solved in this instance of df.  All
calls to add a problem for a given instance of df must occur before
the first call to DF_RESCAN_BLOCKS, DF_SET_BLOCKS or DF_ANALYZE.

For all of the problems defined in df-problems.c, there are
convenience functions named DF_*_ADD_PROBLEM.


Problems can be dependent on other problems.  For instance, solving
def-use or use-def chains is dependent on solving reaching
definitions. As long as these dependencies are listed in the problem
definition, the order of adding the problems is not material.
Otherwise, the problems will be solved in the order of calls to
df_add_problem.  Note that it is not necessary to have a problem.  In
that case, df will just be used to do the scanning.



DF_SET_BLOCKS is an optional call used to define a region of the
function on which the analysis will be performed.  The normal case is
to analyze the entire function and no call to df_set_blocks is made.

When a subset is given, the analysis behaves as if the function only
contains those blocks and any edges that occur directly between the
blocks in the set.  Care should be taken to call df_set_blocks right
before the call to analyze in order to eliminate the possibility that
optimizations that reorder blocks invalidate the bitvector.



DF_RESCAN_BLOCKS is an optional call that causes the scanner to be
 (re)run over the set of blocks passed in.  If blocks is NULL, the entire
function (or all of the blocks defined in df_set_blocks) is rescanned.
If blocks contains blocks that were not defined in the call to
df_set_blocks, these blocks are added to the set of blocks.


DF_ANALYZE causes all of the defined problems to be (re)solved.  It
does not cause blocks to be (re)scanned at the rtl level unless no
prior call is made to df_rescan_blocks.  When DF_ANALYZE is completes,
the IN and OUT sets for each basic block contain the computer
information.  The DF_*_BB_INFO macros can be used to access these
bitvectors.


DF_DUMP can then be called to dump the information produce to some
file.



DF_FINISH causes all of the datastructures to be cleaned up and freed.
The df_instance is also freed and its pointer should be NULLed.




Scanning produces a `struct df_ref' data structure (ref) is allocated
for every register reference (def or use) and this records the insn
and bb the ref is found within.  The refs are linked together in
chains of uses and defs for each insn and for each register.  Each ref
also has a chain field that links all the use refs for a def or all
the def refs for a use.  This is used to create use-def or def-use
chains.

Different optimizations have different needs.  Ultimately, only
register allocation and schedulers should be using the bitmaps
produced for the live register and uninitialized register problems.
The rest of the backend should be upgraded to using and maintaining
the linked information such as def use or use def chains.



PHILOSOPHY:

While incremental bitmaps are not worthwhile to maintain, incremental
chains may be perfectly reasonable.  The fastest way to build chains
from scratch or after significant modifications is to build reaching
definitions (RD) and build the chains from this.

However, general algorithms for maintaining use-def or def-use chains
are not practical.  The amount of work to recompute the chain any
chain after an arbitrary change is large.  However, with a modest
amount of work it is generally possible to have the application that
uses the chains keep them up to date.  The high level knowledge of
what is really happening is essential to crafting efficient
incremental algorithms.

As for the bit vector problems, there is no interface to give a set of
blocks over with to resolve the iteration.  In general, restarting a
dataflow iteration is difficult and expensive.  Again, the best way to
keep the dataflow information up to data (if this is really what is
needed) it to formulate a problem specific solution.

There are fine grained calls for creating and deleting references from
instructions in df-scan.c.  However, these are not currently connected
to the engine that resolves the dataflow equations.


DATA STRUCTURES:

The basic object is a DF_REF (reference) and this may either be a 
DEF (definition) or a USE of a register.

These are linked into a variety of lists; namely reg-def, reg-use,
insn-def, insn-use, def-use, and use-def lists.  For example, the
reg-def lists contain all the locations that define a given register
while the insn-use lists contain all the locations that use a
register.

Note that the reg-def and reg-use chains are generally short for
pseudos and long for the hard registers.

ACCESSING REFS:

There are 4 ways to obtain access to refs:

1) References are divided into two categories, REAL and ARTIFICIAL.

   REAL refs are associated with instructions.  They are linked into
   either in the insn's defs list (accessed by the DF_INSN_DEFS or
   DF_INSN_UID_DEFS macros) or the insn's uses list (accessed by the
   DF_INSN_USES or DF_INSN_UID_USES macros).  These macros produce a
   ref (or NULL), the rest of the list can be obtained by traversal of
   the NEXT_REF field (accessed by the DF_REF_NEXT_REF macro.)  There
   is no significance to the ordering of the uses or refs in an
   instruction.

   ARTIFICIAL refs are associated with basic blocks.  The heads of
   these lists can be accessed by calling get_artificial_defs or
   get_artificial_uses for the particular basic block.  Artificial
   defs and uses are only there if DF_HARD_REGS was specified when the
   df instance was created.
 
   Artificial defs and uses occur both at the beginning and ends of blocks.

     For blocks that area at the destination of eh edges, the
     artificial uses and defs occur at the beginning.  The defs relate
     to the registers specified in EH_RETURN_DATA_REGNO and the uses
     relate to the registers specified in ED_USES.  Logically these
     defs and uses should really occur along the eh edge, but there is
     no convenient way to do this.  Artificial edges that occur at the
     beginning of the block have the DF_REF_AT_TOP flag set.

     Artificial uses occur at the end of all blocks.  These arise from
     the hard registers that are always live, such as the stack
     register and are put there to keep the code from forgetting about
     them.

     Artificial defs occur at the end of the entry block.  These arise
     from registers that are live at entry to the function.

2) All of the uses and defs associated with each pseudo or hard
   register are linked in a bidirectional chain.  These are called
   reg-use or reg_def chains.

   The first use (or def) for a register can be obtained using the
   DF_REG_USE_GET macro (or DF_REG_DEF_GET macro).  Subsequent uses
   for the same regno can be obtained by following the next_reg field
   of the ref.

   In previous versions of this code, these chains were ordered.  It
   has not been practical to continue this practice.

3) If def-use or use-def chains are built, these can be traversed to
   get to other refs.

4) An array of all of the uses (and an array of all of the defs) can
   be built.  These arrays are indexed by the value in the id
   structure.  These arrays are only lazily kept up to date, and that
   process can be expensive.  To have these arrays built, call
   df_reorganize_refs.   Note that the values in the id field of a ref
   may change across calls to df_analyze or df_reorganize refs.

   If the only use of this array is to find all of the refs, it is
   better to traverse all of the registers and then traverse all of
   reg-use or reg-def chains.



NOTES:
 
Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
both a use and a def.  These are both marked read/write to show that they
are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
will generate a use of reg 42 followed by a def of reg 42 (both marked
read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
generates a use of reg 41 then a def of reg 41 (both marked read/write),
even though reg 41 is decremented before it is used for the memory
address in this second example.

A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
for which the number of word_mode units covered by the outer mode is
smaller than that covered by the inner mode, invokes a read-modify-write.
operation.  We generate both a use and a def and again mark them
read/write.

Paradoxical subreg writes do not leave a trace of the old content, so they
are write-only operations.  
*/


#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "tm_p.h"
#include "insn-config.h"
#include "recog.h"
#include "function.h"
#include "regs.h"
#include "output.h"
#include "alloc-pool.h"
#include "flags.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "sbitmap.h"
#include "bitmap.h"
#include "timevar.h"
#include "df.h"
#include "tree-pass.h"

static struct df *ddf = NULL;
struct df *shared_df = NULL;

static void *df_get_bb_info (struct dataflow *, unsigned int);
static void df_set_bb_info (struct dataflow *, unsigned int, void *);
/*----------------------------------------------------------------------------
  Functions to create, destroy and manipulate an instance of df.
----------------------------------------------------------------------------*/


/* Initialize dataflow analysis and allocate and initialize dataflow
   memory.  */

struct df *
df_init (int flags)
{
  struct df *df = XCNEW (struct df);

  /* This is executed once per compilation to initialize platform
     specific data structures. */
  df_hard_reg_init ();
  
  /* All df instance must define the scanning problem.  */
  df_scan_add_problem (df, flags);
  ddf = df;
  return df;
}

/* Add PROBLEM to the DF instance.  */

struct dataflow *
df_add_problem (struct df *df, struct df_problem *problem, int flags)
{
  struct dataflow *dflow;

  /* First try to add the dependent problem. */
  if (problem->dependent_problem_fun)
    (problem->dependent_problem_fun) (df, 0);

  /* Check to see if this problem has already been defined.  If it
     has, just return that instance, if not, add it to the end of the
     vector.  */
  dflow = df->problems_by_index[problem->id];
  if (dflow)
    return dflow;

  /* Make a new one and add it to the end.  */
  dflow = XCNEW (struct dataflow);
  dflow->flags = flags;
  dflow->df = df;
  dflow->problem = problem;
  df->problems_in_order[df->num_problems_defined++] = dflow;
  df->problems_by_index[dflow->problem->id] = dflow;

  return dflow;
}


/* Set the MASK flags in the DFLOW problem.  The old flags are
   returned.  If a flag is not allowed to be changed this will fail if
   checking is enabled.  */
int 
df_set_flags (struct dataflow *dflow, int mask)
{
  int old_flags = dflow->flags;

  gcc_assert (!(mask & (~dflow->problem->changeable_flags)));

  dflow->flags |= mask;

  return old_flags;
}

/* Clear the MASK flags in the DFLOW problem.  The old flags are
   returned.  If a flag is not allowed to be changed this will fail if
   checking is enabled.  */
int 
df_clear_flags (struct dataflow *dflow, int mask)
{
  int old_flags = dflow->flags;

  gcc_assert (!(mask & (~dflow->problem->changeable_flags)));

  dflow->flags &= !mask;

  return old_flags;
}

/* Set the blocks that are to be considered for analysis.  If this is
   not called or is called with null, the entire function in
   analyzed.  */

void 
df_set_blocks (struct df *df, bitmap blocks)
{
  if (blocks)
    {
      if (df->blocks_to_analyze)
        {
          int p;
          bitmap diff = BITMAP_ALLOC (NULL);
          bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
          for (p = df->num_problems_defined - 1; p >= 0 ;p--)
            {
              struct dataflow *dflow = df->problems_in_order[p];
              if (dflow->problem->reset_fun)
                dflow->problem->reset_fun (dflow, df->blocks_to_analyze);
              else if (dflow->problem->free_bb_fun)
                {
                  bitmap_iterator bi;
                  unsigned int bb_index;
                  
                  EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
                    {
                      basic_block bb = BASIC_BLOCK (bb_index);
                      if (bb)
                        {
                          dflow->problem->free_bb_fun
                            (dflow, bb, df_get_bb_info (dflow, bb_index));
                          df_set_bb_info (dflow, bb_index, NULL); 
                        }
                    }
                }
            }

          BITMAP_FREE (diff);
        }
      else
        {
          /* If we have not actually run scanning before, do not try
             to clear anything.  */
          struct dataflow *scan_dflow = df->problems_by_index [DF_SCAN];
          if (scan_dflow->problem_data)
            {
              bitmap blocks_to_reset = NULL;
              int p;
              for (p = df->num_problems_defined - 1; p >= 0 ;p--)
                {
                  struct dataflow *dflow = df->problems_in_order[p];
                  if (dflow->problem->reset_fun)
                    {
                      if (!blocks_to_reset)
                        {
                          basic_block bb;
                          blocks_to_reset = BITMAP_ALLOC (NULL);
                          FOR_ALL_BB(bb)
                            {
                              bitmap_set_bit (blocks_to_reset, bb->index); 
                            }
                        }
                      dflow->problem->reset_fun (dflow, blocks_to_reset);
                    }
                }
              if (blocks_to_reset)
                BITMAP_FREE (blocks_to_reset);
            }
          df->blocks_to_analyze = BITMAP_ALLOC (NULL);
        }
      bitmap_copy (df->blocks_to_analyze, blocks);
    }
  else
    {
      if (df->blocks_to_analyze)
        {
          BITMAP_FREE (df->blocks_to_analyze);
          df->blocks_to_analyze = NULL;
        }
    }
}


/* Free all of the per basic block dataflow from all of the problems.
   This is typically called before a basic block is deleted and the
   problem will be reanalyzed.  */

void
df_delete_basic_block (struct df *df, int bb_index)
{
  basic_block bb = BASIC_BLOCK (bb_index);
  int i;
  
  for (i = 0; i < df->num_problems_defined; i++)
    {
      struct dataflow *dflow = df->problems_in_order[i];
      if (dflow->problem->free_bb_fun)
        dflow->problem->free_bb_fun 
          (dflow, bb, df_get_bb_info (dflow, bb_index)); 
    }
}


/* Free all the dataflow info and the DF structure.  This should be
   called from the df_finish macro which also NULLs the parm.  */

void
df_finish1 (struct df *df)
{
  int i;

  for (i = 0; i < df->num_problems_defined; i++)
    df->problems_in_order[i]->problem->free_fun (df->problems_in_order[i]); 

  free (df);
}

\f
/*----------------------------------------------------------------------------
   The general data flow analysis engine.
----------------------------------------------------------------------------*/


/* Hybrid search algorithm from "Implementation Techniques for
   Efficient Data-Flow Analysis of Large Programs".  */

static void
df_hybrid_search_forward (basic_block bb, 
                          struct dataflow *dataflow,
                          bool single_pass)
{
  int result_changed;
  int i = bb->index;
  edge e;
  edge_iterator ei;

  SET_BIT (dataflow->visited, bb->index);
  gcc_assert (TEST_BIT (dataflow->pending, bb->index));
  RESET_BIT (dataflow->pending, i);

  /*  Calculate <conf_op> of predecessor_outs.  */
  if (EDGE_COUNT (bb->preds) > 0)
    FOR_EACH_EDGE (e, ei, bb->preds)
      {
        if (!TEST_BIT (dataflow->considered, e->src->index))
          continue;
        
        dataflow->problem->con_fun_n (dataflow, e);
      }
  else if (dataflow->problem->con_fun_0)
    dataflow->problem->con_fun_0 (dataflow, bb);
  
  result_changed = dataflow->problem->trans_fun (dataflow, i);
  
  if (!result_changed || single_pass)
    return;
  
  FOR_EACH_EDGE (e, ei, bb->succs)
    {
      if (e->dest->index == i)
        continue;
      if (!TEST_BIT (dataflow->considered, e->dest->index))
        continue;
      SET_BIT (dataflow->pending, e->dest->index);
    }
  
  FOR_EACH_EDGE (e, ei, bb->succs)
    {
      if (e->dest->index == i)
        continue;
      
      if (!TEST_BIT (dataflow->considered, e->dest->index))
        continue;
      if (!TEST_BIT (dataflow->visited, e->dest->index))
        df_hybrid_search_forward (e->dest, dataflow, single_pass);
    }
}

static void
df_hybrid_search_backward (basic_block bb,
                           struct dataflow *dataflow,
                           bool single_pass)
{
  int result_changed;
  int i = bb->index;
  edge e;
  edge_iterator ei;
  
  SET_BIT (dataflow->visited, bb->index);
  gcc_assert (TEST_BIT (dataflow->pending, bb->index));
  RESET_BIT (dataflow->pending, i);

  /*  Calculate <conf_op> of predecessor_outs.  */
  if (EDGE_COUNT (bb->succs) > 0)
    FOR_EACH_EDGE (e, ei, bb->succs)                                    
      {                                                         
        if (!TEST_BIT (dataflow->considered, e->dest->index))           
          continue;                                                     
        
        dataflow->problem->con_fun_n (dataflow, e);
      }                                                         
  else if (dataflow->problem->con_fun_0)
    dataflow->problem->con_fun_0 (dataflow, bb);

  result_changed = dataflow->problem->trans_fun (dataflow, i);
  
  if (!result_changed || single_pass)
    return;
  
  FOR_EACH_EDGE (e, ei, bb->preds)
    {                                                           
      if (e->src->index == i)
        continue;
      
      if (!TEST_BIT (dataflow->considered, e->src->index))
        continue;

      SET_BIT (dataflow->pending, e->src->index);
    }                                                           
  
  FOR_EACH_EDGE (e, ei, bb->preds)
    {
      if (e->src->index == i)
        continue;

      if (!TEST_BIT (dataflow->considered, e->src->index))
        continue;
      
      if (!TEST_BIT (dataflow->visited, e->src->index))
        df_hybrid_search_backward (e->src, dataflow, single_pass);
    }
}


/* This function will perform iterative bitvector dataflow described
   by DATAFLOW, producing the in and out sets.  Only the part of the
   cfg induced by blocks in DATAFLOW->order is taken into account.

   SINGLE_PASS is true if you just want to make one pass over the
   blocks.  */

void
df_iterative_dataflow (struct dataflow *dataflow,
                       bitmap blocks_to_consider, bitmap blocks_to_init, 
                       int *blocks_in_postorder, int n_blocks, 
                       bool single_pass)
{
  unsigned int idx;
  int i;
  sbitmap visited = sbitmap_alloc (last_basic_block);
  sbitmap pending = sbitmap_alloc (last_basic_block);
  sbitmap considered = sbitmap_alloc (last_basic_block);
  bitmap_iterator bi;

  dataflow->visited = visited;
  dataflow->pending = pending;
  dataflow->considered = considered;

  sbitmap_zero (visited);
  sbitmap_zero (pending);
  sbitmap_zero (considered);

  gcc_assert (dataflow->problem->dir);

  EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi)
    {
      SET_BIT (considered, idx);
    }

  for (i = 0; i < n_blocks; i++)
    {
      idx = blocks_in_postorder[i];
      SET_BIT (pending, idx);
    };

  dataflow->problem->init_fun (dataflow, blocks_to_init);

  while (1)
    {

      /* For forward problems, you want to pass in reverse postorder
         and for backward problems you want postorder.  This has been
         shown to be as good as you can do by several people, the
         first being Mathew Hecht in his phd dissertation.

         The nodes are passed into this function in postorder.  */

      if (dataflow->problem->dir == DF_FORWARD)
        {
          for (i = n_blocks - 1 ; i >= 0 ; i--)
            {
              idx = blocks_in_postorder[i];
              
              if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
                df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass);
            }
        }
      else
        {
          for (i = 0; i < n_blocks; i++)
            {
              idx = blocks_in_postorder[i];
              
              if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
                df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass);
            }
        }

      if (sbitmap_first_set_bit (pending) == -1)
        break;

      sbitmap_zero (visited);
    }

  sbitmap_free (pending);
  sbitmap_free (visited);
  sbitmap_free (considered);
}


/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
   the order of the remaining entries.  Returns the length of the resulting
   list.  */

static unsigned
df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
{
  unsigned act, last;

  for (act = 0, last = 0; act < len; act++)
    if (bitmap_bit_p (blocks, list[act]))
      list[last++] = list[act];

  return last;
}


/* Execute dataflow analysis on a single dataflow problem. 

   There are three sets of blocks passed in: 

   BLOCKS_TO_CONSIDER are the blocks whose solution can either be
   examined or will be computed.  For calls from DF_ANALYZE, this is
   the set of blocks that has been passed to DF_SET_BLOCKS.  For calls
   from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of
   blocks in the fringe (the set of blocks passed in plus the set of
   immed preds and succs of those blocks).

   BLOCKS_TO_INIT are the blocks whose solution will be changed by
   this iteration.  For calls from DF_ANALYZE, this is the set of
   blocks that has been passed to DF_SET_BLOCKS.  For calls from
   DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks
   passed in.

   BLOCKS_TO_SCAN are the set of blocks that need to be rescanned.
   For calls from DF_ANALYZE, this is the accumulated set of blocks
   that has been passed to DF_RESCAN_BLOCKS since the last call to
   DF_ANALYZE.  For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS,
   this is the set of blocks passed in.
 
                   blocks_to_consider    blocks_to_init    blocks_to_scan
   full redo       all                   all               all
   partial redo    all                   all               sub
   small fixup     fringe                sub               sub
*/

void
df_analyze_problem (struct dataflow *dflow, 
                    bitmap blocks_to_consider, 
                    bitmap blocks_to_init,
                    bitmap blocks_to_scan,
                    int *postorder, int n_blocks, bool single_pass)
{
  /* (Re)Allocate the datastructures necessary to solve the problem.  */ 
  if (dflow->problem->alloc_fun)
    dflow->problem->alloc_fun (dflow, blocks_to_scan, blocks_to_init);

  /* Set up the problem and compute the local information.  This
     function is passed both the blocks_to_consider and the
     blocks_to_scan because the RD and RU problems require the entire
     function to be rescanned if they are going to be updated.  */
  if (dflow->problem->local_compute_fun)
    dflow->problem->local_compute_fun (dflow, blocks_to_consider, blocks_to_scan);

  /* Solve the equations.  */
  if (dflow->problem->dataflow_fun)
    dflow->problem->dataflow_fun (dflow, blocks_to_consider, blocks_to_init,
                                  postorder, n_blocks, single_pass);

  /* Massage the solution.  */
  if (dflow->problem->finalize_fun)
    dflow->problem->finalize_fun (dflow, blocks_to_consider);
}


/* Analyze dataflow info for the basic blocks specified by the bitmap
   BLOCKS, or for the whole CFG if BLOCKS is zero.  */

void
df_analyze (struct df *df)
{
  int *postorder = XNEWVEC (int, last_basic_block);
  bitmap current_all_blocks = BITMAP_ALLOC (NULL);
  int n_blocks;
  int i;
  bool everything;

  n_blocks = post_order_compute (postorder, true);

  if (n_blocks != n_basic_blocks)
    delete_unreachable_blocks ();

  for (i = 0; i < n_blocks; i++)
    bitmap_set_bit (current_all_blocks, postorder[i]);

  /* No one called df_rescan_blocks, so do it.  */
  if (!df->blocks_to_scan)
    df_rescan_blocks (df, NULL);

  /* Make sure that we have pruned any unreachable blocks from these
     sets.  */
  bitmap_and_into (df->blocks_to_scan, current_all_blocks);

  if (df->blocks_to_analyze)
    {
      everything = false;
      bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
      n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze);
      BITMAP_FREE (current_all_blocks);
    }
  else
    {
      everything = true;
      df->blocks_to_analyze = current_all_blocks;
      current_all_blocks = NULL;
    }

  /* Skip over the DF_SCAN problem. */
  for (i = 1; i < df->num_problems_defined; i++)
    df_analyze_problem (df->problems_in_order[i], 
                        df->blocks_to_analyze, df->blocks_to_analyze, 
                        df->blocks_to_scan,
                        postorder, n_blocks, false);

  if (everything)
    {
      BITMAP_FREE (df->blocks_to_analyze);
      df->blocks_to_analyze = NULL;
    }

  BITMAP_FREE (df->blocks_to_scan);
  df->blocks_to_scan = NULL;
  free (postorder);
}


\f
/*----------------------------------------------------------------------------
   Functions to support limited incremental change.
----------------------------------------------------------------------------*/


/* Get basic block info.  */

static void *
df_get_bb_info (struct dataflow *dflow, unsigned int index)
{
  return (struct df_scan_bb_info *) dflow->block_info[index];
}


/* Set basic block info.  */

static void
df_set_bb_info (struct dataflow *dflow, unsigned int index, 
                void *bb_info)
{
  dflow->block_info[index] = bb_info;
}


/* Called from the rtl_compact_blocks to reorganize the problems basic
   block info.  */

void 
df_compact_blocks (struct df *df)
{
  int i, p;
  basic_block bb;
  void **problem_temps;
  int size = last_basic_block *sizeof (void *);
  problem_temps = xmalloc (size);

  for (p = 0; p < df->num_problems_defined; p++)
    {
      struct dataflow *dflow = df->problems_in_order[p];
      if (dflow->problem->free_bb_fun)
        {
          df_grow_bb_info (dflow);
          memcpy (problem_temps, dflow->block_info, size);

          /* Copy the bb info from the problem tmps to the proper
             place in the block_info vector.  Null out the copied
             item.  */
          i = NUM_FIXED_BLOCKS;
          FOR_EACH_BB (bb) 
            {
              df_set_bb_info (dflow, i, problem_temps[bb->index]);
              problem_temps[bb->index] = NULL;
              i++;
            }
          memset (dflow->block_info + i, 0, 
                  (last_basic_block - i) *sizeof (void *));

          /* Free any block infos that were not copied (and NULLed).
             These are from orphaned blocks.  */
          for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
            {
              basic_block bb = BASIC_BLOCK (i); 
              if (problem_temps[i] && bb)
                dflow->problem->free_bb_fun
                  (dflow, bb, problem_temps[i]);
            }
        }
    }

  free (problem_temps);

  i = NUM_FIXED_BLOCKS;
  FOR_EACH_BB (bb) 
    {
      SET_BASIC_BLOCK (i, bb);
      bb->index = i;
      i++;
    }

  gcc_assert (i == n_basic_blocks);

  for (; i < last_basic_block; i++)
    SET_BASIC_BLOCK (i, NULL);
}


/* Shove NEW_BLOCK in at OLD_INDEX.  Called from if-cvt to hack a
   block.  There is no excuse for people to do this kind of thing.  */

void 
df_bb_replace (struct df *df, int old_index, basic_block new_block)
{
  int p;

  for (p = 0; p < df->num_problems_defined; p++)
    {
      struct dataflow *dflow = df->problems_in_order[p];
      if (dflow->block_info)
        {
          void *temp;

          df_grow_bb_info (dflow);

          /* The old switcheroo.  */

          temp = df_get_bb_info (dflow, old_index);
          df_set_bb_info (dflow, old_index, 
                          df_get_bb_info (dflow, new_block->index));
          df_set_bb_info (dflow, new_block->index, temp);
        }
    }

  SET_BASIC_BLOCK (old_index, new_block);
  new_block->index = old_index;
}

/*----------------------------------------------------------------------------
   PUBLIC INTERFACES TO QUERY INFORMATION.
----------------------------------------------------------------------------*/


/* Return last use of REGNO within BB.  */

struct df_ref *
df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
{
  rtx insn;
  struct df_ref *use;
  unsigned int uid;

  FOR_BB_INSNS_REVERSE (bb, insn)
    {
      if (!INSN_P (insn))
        continue;

      uid = INSN_UID (insn);
      for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
        if (DF_REF_REGNO (use) == regno)
          return use;
    }
  return NULL;
}


/* Return first def of REGNO within BB.  */

struct df_ref *
df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
{
  rtx insn;
  struct df_ref *def;
  unsigned int uid;

  FOR_BB_INSNS (bb, insn)
    {
      if (!INSN_P (insn))
        continue;

      uid = INSN_UID (insn);
      for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
        if (DF_REF_REGNO (def) == regno)
          return def;
    }
  return NULL;
}


/* Return last def of REGNO within BB.  */

struct df_ref *
df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
{
  rtx insn;
  struct df_ref *def;
  unsigned int uid;

  FOR_BB_INSNS_REVERSE (bb, insn)
    {
      if (!INSN_P (insn))
        continue;

      uid = INSN_UID (insn);
      for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
        if (DF_REF_REGNO (def) == regno)
          return def;
    }

  return NULL;
}

/* Return true if INSN defines REGNO.  */

bool
df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno)
{
  unsigned int uid;
  struct df_ref *def;

  uid = INSN_UID (insn);
  for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
    if (DF_REF_REGNO (def) == regno)
      return true;
  
  return false;
}


/* Finds the reference corresponding to the definition of REG in INSN.
   DF is the dataflow object.  */

struct df_ref *
df_find_def (struct df *df, rtx insn, rtx reg)
{
  unsigned int uid;
  struct df_ref *def;

  if (GET_CODE (reg) == SUBREG)
    reg = SUBREG_REG (reg);
  gcc_assert (REG_P (reg));

  uid = INSN_UID (insn);
  for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
    if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
      return def;

  return NULL;
}


/* Return true if REG is defined in INSN, zero otherwise.  */ 

bool
df_reg_defined (struct df *df, rtx insn, rtx reg)
{
  return df_find_def (df, insn, reg) != NULL;
}
  

/* Finds the reference corresponding to the use of REG in INSN.
   DF is the dataflow object.  */
  
struct df_ref *
df_find_use (struct df *df, rtx insn, rtx reg)
{
  unsigned int uid;
  struct df_ref *use;

  if (GET_CODE (reg) == SUBREG)
    reg = SUBREG_REG (reg);
  gcc_assert (REG_P (reg));

  uid = INSN_UID (insn);
  for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
    if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
      return use; 

  return NULL;
}


/* Return true if REG is referenced in INSN, zero otherwise.  */ 

bool
df_reg_used (struct df *df, rtx insn, rtx reg)
{
  return df_find_use (df, insn, reg) != NULL;
}
  
\f
/*----------------------------------------------------------------------------
   Debugging and printing functions.
----------------------------------------------------------------------------*/

/* Dump dataflow info.  */
void
df_dump (struct df *df, FILE *file)
{
  int i;

  if (!df || !file)
    return;

  fprintf (file, "\n\n%s\n", current_function_name ());
  fprintf (file, "\nDataflow summary:\n");
  fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
           df->def_info.bitmap_size, df->use_info.bitmap_size);

  for (i = 0; i < df->num_problems_defined; i++)
    df->problems_in_order[i]->problem->dump_fun (df->problems_in_order[i], file); 

  fprintf (file, "\n");
}


void
df_refs_chain_dump (struct df_ref *ref, bool follow_chain, FILE *file)
{
  fprintf (file, "{ ");
  while (ref)
    {
      fprintf (file, "%c%d(%d) ",
               DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
               DF_REF_ID (ref),
               DF_REF_REGNO (ref));
      if (follow_chain)
        df_chain_dump (DF_REF_CHAIN (ref), file);
      ref = ref->next_ref;
    }
  fprintf (file, "}");
}


/* Dump either a ref-def or reg-use chain.  */

void
df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref,  FILE *file)
{
  fprintf (file, "{ ");
  while (ref)
    {
      fprintf (file, "%c%d(%d) ",
               DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
               DF_REF_ID (ref),
               DF_REF_REGNO (ref));
      ref = ref->next_reg;
    }
  fprintf (file, "}");
}


static void
df_mws_dump (struct df_mw_hardreg *mws, FILE *file)
{
  while (mws)
    {
      struct df_link *regs = mws->regs;
      fprintf (file, "%c%d(", 
               (mws->type == DF_REF_REG_DEF) ? 'd' : 'u',
               DF_REF_REGNO (regs->ref));
      while (regs)
        {
          fprintf (file, "%d ", DF_REF_REGNO (regs->ref));
          regs = regs->next;
        }

      fprintf (file, ") "); 
      mws = mws->next;
    }
}


static void 
df_insn_uid_debug (struct df *df, unsigned int uid, 
                   bool follow_chain, FILE *file)
{
  int bbi;

  if (DF_INSN_UID_DEFS (df, uid))
    bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
  else if (DF_INSN_UID_USES(df, uid))
    bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
  else
    bbi = -1;

  fprintf (file, "insn %d bb %d luid %d",
           uid, bbi, DF_INSN_UID_LUID (df, uid));

  if (DF_INSN_UID_DEFS (df, uid))
    {
      fprintf (file, " defs ");
      df_refs_chain_dump (DF_INSN_UID_DEFS (df, uid), follow_chain, file);
    }

  if (DF_INSN_UID_USES (df, uid))
    {
      fprintf (file, " uses ");
      df_refs_chain_dump (DF_INSN_UID_USES (df, uid), follow_chain, file);
    }

  if (DF_INSN_UID_MWS (df, uid))
    {
      fprintf (file, " mws ");
      df_mws_dump (DF_INSN_UID_MWS (df, uid), file);
    }
  fprintf (file, "\n");
}


void
df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file)
{
  df_insn_uid_debug (df, INSN_UID (insn), follow_chain, file);
}

void
df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
{
  unsigned int uid;
  int bbi;

  uid = INSN_UID (insn);
  if (DF_INSN_UID_DEFS (df, uid))
    bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
  else if (DF_INSN_UID_USES(df, uid))
    bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
  else
    bbi = -1;

  fprintf (file, "insn %d bb %d luid %d defs ",
           uid, bbi, DF_INSN_LUID (df, insn));
  df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file);
    
  fprintf (file, " uses ");
  df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file);
  fprintf (file, "\n");
}

void
df_regno_debug (struct df *df, unsigned int regno, FILE *file)
{
  fprintf (file, "reg %d defs ", regno);
  df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file);
  fprintf (file, " uses ");
  df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file);
  fprintf (file, "\n");
}


void
df_ref_debug (struct df_ref *ref, FILE *file)
{
  fprintf (file, "%c%d ",
           DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
           DF_REF_ID (ref));
  fprintf (file, "reg %d bb %d insn %d flag %x chain ",
           DF_REF_REGNO (ref),
           DF_REF_BBNO (ref),
           DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1,
           DF_REF_FLAGS (ref));
  df_chain_dump (DF_REF_CHAIN (ref), file);
  fprintf (file, "\n");
}
\f
/* Functions for debugging from GDB.  */

void
debug_df_insn (rtx insn)
{
  df_insn_debug (ddf, insn, true, stderr);
  debug_rtx (insn);
}


void
debug_df_reg (rtx reg)
{
  df_regno_debug (ddf, REGNO (reg), stderr);
}


void
debug_df_regno (unsigned int regno)
{
  df_regno_debug (ddf, regno, stderr);
}


void
debug_df_ref (struct df_ref *ref)
{
  df_ref_debug (ref, stderr);
}


void
debug_df_defno (unsigned int defno)
{
  df_ref_debug (DF_DEFS_GET (ddf, defno), stderr);
}


void
debug_df_useno (unsigned int defno)
{
  df_ref_debug (DF_USES_GET (ddf, defno), stderr);
}


void
debug_df_chain (struct df_link *link)
{
  df_chain_dump (link, stderr);
  fputc ('\n', stderr);
}