Subversion Repositories openrisc

/* Allocation for dataflow support routines.

   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).

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free

Software Foundation; either version 3, or (at your option) any later

version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

/*

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.

Dataflow analysis is available in most of the rtl backend (the parts

between pass_df_initialize and pass_df_finish).  It is quite likely

that these boundaries will be expanded in the future.  The only

requirement is that there be a correct control flow graph.

There are three variations of the live variable problem that are

available whenever dataflow is available.  The LR problem finds the

areas that can reach a use of a variable, the UR problems finds the

areas that can be reached from a definition of a variable.  The LIVE

problem finds the intersection of these two areas.

There are several optional problems.  These can be enabled when they

are needed and disabled when they are not needed.

Dataflow problems are generally solved in three layers.  The bottom

layer is called scanning where a data structure is built for each rtl

insn that describes the set of defs and uses of that insn.  Scanning

is generally kept up to date, i.e. as the insns changes, the scanned

version of that insn changes also.  There are various mechanisms for

making this happen and are described in the INCREMENTAL SCANNING

section.

In the middle layer, basic blocks are scanned to produce transfer

functions which describe the effects of that block on the global

dataflow solution.  The transfer functions are only rebuilt if the

some instruction within the block has changed.

The top layer is the dataflow solution itself.  The dataflow solution

is computed by using an efficient iterative solver and the transfer

functions.  The dataflow solution must be recomputed whenever the

control changes or if one of the transfer function changes.

USAGE:

Here is an example of using the dataflow routines.

      df_[chain,live,note,rd]_add_problem (flags);

      df_set_blocks (blocks);

      df_analyze ();

      df_dump (stderr);

      df_finish_pass (false);

DF_[chain,live,note,rd]_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_ANALYZE.

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.

DF_SET_BLOCKS only effects the blocks that are effected when computing

the transfer functions and final solution.  The insn level information

is always kept up to date.

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_ANALYZE causes all of the defined problems to be (re)solved.  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.  All deferred rescannings are down before

the transfer functions are recomputed.

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

file.  This calls DF_DUMP_START, to print the information that is not

basic block specific, and then calls DF_DUMP_TOP and DF_DUMP_BOTTOM

for each block to print the basic specific information.  These parts

can all be called separately as part of a larger dump function.

DF_FINISH_PASS causes df_remove_problem to be called on all of the

optional problems.  It also causes any insns whose scanning has been

deferred to be rescanned as well as clears all of the changeable flags.

Setting the pass manager TODO_df_finish flag causes this function to

be run.  However, the pass manager will call df_finish_pass AFTER the

pass dumping has been done, so if you want to see the results of the

optional problems in the pass dumps, use the TODO flag rather than

calling the function yourself.

INCREMENTAL SCANNING

There are four ways of doing the incremental scanning:

1) Immediate rescanning - Calls to df_insn_rescan, df_notes_rescan,

   df_bb_delete, df_insn_change_bb have been added to most of

   the low level service functions that maintain the cfg and change

   rtl.  Calling and of these routines many cause some number of insns

   to be rescanned.

   For most modern rtl passes, this is certainly the easiest way to

   manage rescanning the insns.  This technique also has the advantage

   that the scanning information is always correct and can be relied

   upon even after changes have been made to the instructions.  This

   technique is contra indicated in several cases:

   a) If def-use chains OR use-def chains (but not both) are built,

      using this is SIMPLY WRONG.  The problem is that when a ref is

      deleted that is the target of an edge, there is not enough

      information to efficiently find the source of the edge and

      delete the edge.  This leaves a dangling reference that may

      cause problems.

   b) If def-use chains AND use-def chains are built, this may

      produce unexpected results.  The problem is that the incremental

      scanning of an insn does not know how to repair the chains that

      point into an insn when the insn changes.  So the incremental

      scanning just deletes the chains that enter and exit the insn

      being changed.  The dangling reference issue in (a) is not a

      problem here, but if the pass is depending on the chains being

      maintained after insns have been modified, this technique will

      not do the correct thing.

   c) If the pass modifies insns several times, this incremental

      updating may be expensive.

   d) If the pass modifies all of the insns, as does register

      allocation, it is simply better to rescan the entire function.

2) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and

   df_insn_delete do not immediately change the insn but instead make

   a note that the insn needs to be rescanned.  The next call to

   df_analyze, df_finish_pass, or df_process_deferred_rescans will

   cause all of the pending rescans to be processed.

   This is the technique of choice if either 1a, 1b, or 1c are issues

   in the pass.  In the case of 1a or 1b, a call to df_finish_pass

   (either manually or via TODO_df_finish) should be made before the

   next call to df_analyze or df_process_deferred_rescans.

   This mode is also used by a few passes that still rely on note_uses,

   note_stores and for_each_rtx instead of using the DF data.  This

   can be said to fall under case 1c.

   To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN).

   (This mode can be cleared by calling df_clear_flags

   (DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to

   be rescanned.

3) Total rescanning - In this mode the rescanning is disabled.

   Only when insns are deleted is the df information associated with

   it also deleted.  At the end of the pass, a call must be made to

   df_insn_rescan_all.  This method is used by the register allocator

   since it generally changes each insn multiple times (once for each ref)

   and does not need to make use of the updated scanning information.

4) Do it yourself - In this mechanism, the pass updates the insns

   itself using the low level df primitives.  Currently no pass does

   this, but it has the advantage that it is quite efficient given

   that the pass generally has exact knowledge of what it is changing.

DATA STRUCTURES

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 INSNS:

1) The df insn information is kept in an array of DF_INSN_INFO objects.

   The array is indexed by insn uid, and every DF_REF points to the

   DF_INSN_INFO object of the insn that contains the reference.

2) Each insn has three sets of refs, which are linked into one of three

   lists: The insn's defs list (accessed by the DF_INSN_INFO_DEFS,

   DF_INSN_DEFS, or DF_INSN_UID_DEFS macros), the insn's uses list

   (accessed by the DF_INSN_INFO_USES, DF_INSN_USES, or

   DF_INSN_UID_USES macros) or the insn's eq_uses list (accessed by the

   DF_INSN_INFO_EQ_USES, DF_INSN_EQ_USES or DF_INSN_UID_EQ_USES macros).

   The latter list are the list of references in REG_EQUAL or REG_EQUIV

   notes.  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.

3) Each insn has a logical uid field (LUID) which is stored in the

   DF_INSN_INFO object for the insn.  The LUID field is accessed by

   the DF_INSN_INFO_LUID, DF_INSN_LUID, and DF_INSN_UID_LUID macros.

   When properly set, the LUID is an integer that numbers each insn in

   the basic block, in order from the start of the block.

   The numbers are only correct after a call to df_analyze.  They will

   rot after insns are added deleted or moved round.

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.

   ARTIFICIAL refs are associated with basic blocks.  The heads of

   these lists can be accessed by calling df_get_artificial_defs or

   df_get_artificial_uses for the particular basic block.

   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) There are three types of refs: defs, uses and eq_uses.  (Eq_uses are

   uses that appear inside a REG_EQUAL or REG_EQUIV note.)

   All of the eq_uses, uses and defs associated with each pseudo or

   hard register may be linked in a bidirectional chain.  These are

   called reg-use or reg_def chains.  If the changeable flag

   DF_EQ_NOTES is set when the chains are built, the eq_uses will be

   treated like uses.  If it is not set they are ignored.

   The first use, eq_use or def for a register can be obtained using

   the DF_REG_USE_CHAIN, DF_REG_EQ_USE_CHAIN or DF_REG_DEF_CHAIN

   macros.  Subsequent uses for the same regno can be obtained by

   following the next_reg field of the ref.  The number of elements in

   each of the chains can be found by using the DF_REG_USE_COUNT,

   DF_REG_EQ_USE_COUNT or DF_REG_DEF_COUNT macros.

   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.  If the flag DF_EQ_NOTES has been set, the chains

   include the eq_uses.  Otherwise these are ignored when building the

   chains.

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_defs or df_reorganize_uses.  If the flag DF_EQ_NOTES

   has been set the array will contain the eq_uses.  Otherwise these

   are ignored when building the array and assigning the ids.  Note

   that the values in the id field of a ref may change across calls to

   df_analyze or df_reorganize_defs or df_reorganize_uses.

   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"

#include "params.h"

static void *df_get_bb_info (struct dataflow *, unsigned int);

static void df_set_bb_info (struct dataflow *, unsigned int, void *);

#ifdef DF_DEBUG_CFG

static void df_set_clean_cfg (void);

#endif

/* An obstack for bitmap not related to specific dataflow problems.

   This obstack should e.g. be used for bitmaps with a short life time

   such as temporary bitmaps.  */

bitmap_obstack df_bitmap_obstack;

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

  Functions to create, destroy and manipulate an instance of df.

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

struct df *df;

/* Add PROBLEM (and any dependent problems) to the DF instance.  */

void

df_add_problem (struct df_problem *problem)

{

  struct dataflow *dflow;

  int i;

  /* First try to add the dependent problem. */

  if (problem->dependent_problem)

    df_add_problem (problem->dependent_problem);

  /* 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;

  /* Make a new one and add it to the end.  */

  dflow = XCNEW (struct dataflow);

  dflow->problem = problem;

  dflow->computed = false;

  dflow->solutions_dirty = true;

  df->problems_by_index[dflow->problem->id] = dflow;

  /* Keep the defined problems ordered by index.  This solves the

     problem that RI will use the information from UREC if UREC has

     been defined, or from LIVE if LIVE is defined and otherwise LR.

     However for this to work, the computation of RI must be pushed

     after which ever of those problems is defined, but we do not

     require any of those except for LR to have actually been

     defined.  */

  df->num_problems_defined++;

  for (i = df->num_problems_defined - 2; i >= 0; i--)

    {

      if (problem->id < df->problems_in_order[i]->problem->id)

        df->problems_in_order[i+1] = df->problems_in_order[i];

      else

        {

          df->problems_in_order[i+1] = dflow;

          return;

        }

    }

  df->problems_in_order[0] = 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 (int changeable_flags)

{

  int old_flags = df->changeable_flags;

  df->changeable_flags |= changeable_flags;

  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 (int changeable_flags)

{

  int old_flags = df->changeable_flags;

  df->changeable_flags &= ~changeable_flags;

  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 (bitmap blocks)

{

  if (blocks)

    {

      if (dump_file)

        bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");

      if (df->blocks_to_analyze)

        {

          /* This block is called to change the focus from one subset

             to another.  */

          int p;

          bitmap diff = BITMAP_ALLOC (&df_bitmap_obstack);

          bitmap_and_compl (diff, df->blocks_to_analyze, blocks);

          for (p = 0; p < df->num_problems_defined; p++)

            {

              struct dataflow *dflow = df->problems_in_order[p];

              if (dflow->optional_p && dflow->problem->reset_fun)

                dflow->problem->reset_fun (df->blocks_to_analyze);

              else if (dflow->problem->free_blocks_on_set_blocks)

                {

                  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)

                        {

                          void *bb_info = df_get_bb_info (dflow, bb_index);

                          if (bb_info)

                            {

                              dflow->problem->free_bb_fun (bb, bb_info);

                              df_set_bb_info (dflow, bb_index, NULL);

                            }

                        }

                    }

                }

            }

          BITMAP_FREE (diff);

        }

      else

        {

          /* This block of code is executed to change the focus from

             the entire function to a subset.  */

          bitmap blocks_to_reset = NULL;

          int p;

          for (p = 0; p < df->num_problems_defined; p++)

            {

              struct dataflow *dflow = df->problems_in_order[p];

              if (dflow->optional_p && dflow->problem->reset_fun)

                {

                  if (!blocks_to_reset)

                    {

                      basic_block bb;

                      blocks_to_reset =

                        BITMAP_ALLOC (&df_bitmap_obstack);

                      FOR_ALL_BB(bb)

                        {

                          bitmap_set_bit (blocks_to_reset, bb->index);

                        }

                    }

                  dflow->problem->reset_fun (blocks_to_reset);

                }

            }

          if (blocks_to_reset)

            BITMAP_FREE (blocks_to_reset);

          df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);

        }

      bitmap_copy (df->blocks_to_analyze, blocks);

      df->analyze_subset = true;

    }

  else

    {

      /* This block is executed to reset the focus to the entire

         function.  */

      if (dump_file)

        fprintf (dump_file, "clearing blocks_to_analyze\n");

      if (df->blocks_to_analyze)

        {

          BITMAP_FREE (df->blocks_to_analyze);

          df->blocks_to_analyze = NULL;

        }

      df->analyze_subset = false;

    }

  /* Setting the blocks causes the refs to be unorganized since only

     the refs in the blocks are seen.  */

  df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);

  df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);

  df_mark_solutions_dirty ();

}

/* Delete a DFLOW problem (and any problems that depend on this

   problem).  */

void

df_remove_problem (struct dataflow *dflow)

{

  struct df_problem *problem;

  int i;

  if (!dflow)

    return;

  problem = dflow->problem;

  gcc_assert (problem->remove_problem_fun);

  /* Delete any problems that depended on this problem first.  */

  for (i = 0; i < df->num_problems_defined; i++)

    if (df->problems_in_order[i]->problem->dependent_problem == problem)

      df_remove_problem (df->problems_in_order[i]);

  /* Now remove this problem.  */

  for (i = 0; i < df->num_problems_defined; i++)

    if (df->problems_in_order[i] == dflow)

      {

        int j;

        for (j = i + 1; j < df->num_problems_defined; j++)

          df->problems_in_order[j-1] = df->problems_in_order[j];

        df->problems_in_order[j-1] = NULL;

        df->num_problems_defined--;

        break;

      }

  (problem->remove_problem_fun) ();

  df->problems_by_index[problem->id] = NULL;

}

/* Remove all of the problems that are not permanent.  Scanning, LR

   and (at -O2 or higher) LIVE are permanent, the rest are removable.

   Also clear all of the changeable_flags.  */

void

df_finish_pass (bool verify ATTRIBUTE_UNUSED)

{

  int i;

  int removed = 0;

#ifdef ENABLE_DF_CHECKING

  int saved_flags;

#endif

  if (!df)

    return;

  df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);

  df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);

#ifdef ENABLE_DF_CHECKING

  saved_flags = df->changeable_flags;

#endif

  for (i = 0; i < df->num_problems_defined; i++)

    {

      struct dataflow *dflow = df->problems_in_order[i];

      struct df_problem *problem = dflow->problem;

      if (dflow->optional_p)

        {

          gcc_assert (problem->remove_problem_fun);

          (problem->remove_problem_fun) ();

          df->problems_in_order[i] = NULL;

          df->problems_by_index[problem->id] = NULL;

          removed++;

        }

    }

  df->num_problems_defined -= removed;

  /* Clear all of the flags.  */

  df->changeable_flags = 0;

  df_process_deferred_rescans ();

  /* Set the focus back to the whole function.  */

  if (df->blocks_to_analyze)

    {

      BITMAP_FREE (df->blocks_to_analyze);

      df->blocks_to_analyze = NULL;

      df_mark_solutions_dirty ();

      df->analyze_subset = false;

    }

#ifdef ENABLE_DF_CHECKING

  /* Verification will fail in DF_NO_INSN_RESCAN.  */

  if (!(saved_flags & DF_NO_INSN_RESCAN))

    {

      df_lr_verify_transfer_functions ();

      if (df_live)

        df_live_verify_transfer_functions ();

    }

#ifdef DF_DEBUG_CFG

  df_set_clean_cfg ();

#endif

#endif

#ifdef ENABLE_CHECKING

  if (verify)

    df->changeable_flags |= DF_VERIFY_SCHEDULED;

#endif

}

/* Set up the dataflow instance for the entire back end.  */

static unsigned int

rest_of_handle_df_initialize (void)

{

  gcc_assert (!df);

  df = XCNEW (struct df);

  df->changeable_flags = 0;

  bitmap_obstack_initialize (&df_bitmap_obstack);

  /* Set this to a conservative value.  Stack_ptr_mod will compute it

     correctly later.  */

  current_function_sp_is_unchanging = 0;

  df_scan_add_problem ();

  df_scan_alloc (NULL);

  /* These three problems are permanent.  */

  df_lr_add_problem ();

  if (optimize > 1)

    df_live_add_problem ();

  df->postorder = XNEWVEC (int, last_basic_block);

  df->postorder_inverted = XNEWVEC (int, last_basic_block);

  df->n_blocks = post_order_compute (df->postorder, true, true);

  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);

  gcc_assert (df->n_blocks == df->n_blocks_inverted);

  df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);

  memset (df->hard_regs_live_count, 0,

          sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);

  df_hard_reg_init ();

  /* After reload, some ports add certain bits to regs_ever_live so

     this cannot be reset.  */

  df_compute_regs_ever_live (true);

  df_scan_blocks ();

  df_compute_regs_ever_live (false);

  return 0;

}

static bool

gate_opt (void)

{

  return optimize > 0;

}

struct rtl_opt_pass pass_df_initialize_opt =

{

 {

  RTL_PASS,

  "dfinit",                             /* name */

  gate_opt,                             /* gate */

  rest_of_handle_df_initialize,         /* execute */

  NULL,                                 /* sub */

  NULL,                                 /* next */

  0,                                    /* static_pass_number */

  TV_NONE,                              /* tv_id */

  0,                                    /* properties_required */

  0,                                    /* properties_provided */

  0,                                    /* properties_destroyed */

  0,                                    /* todo_flags_start */

 }

};

static bool

gate_no_opt (void)

{

  return optimize == 0;

}

struct rtl_opt_pass pass_df_initialize_no_opt =

{

 {

  RTL_PASS,

  "no-opt dfinit",                      /* name */

  gate_no_opt,                          /* gate */

  rest_of_handle_df_initialize,         /* execute */

  NULL,                                 /* sub */

  NULL,                                 /* next */

  0,                                    /* static_pass_number */

  TV_NONE,                              /* tv_id */

  0,                                    /* properties_required */

  0,                                    /* properties_provided */

  0,                                    /* properties_destroyed */

  0,                                    /* todo_flags_start */

 }

};

/* Free all the dataflow info and the DF structure.  This should be

   called from the df_finish macro which also NULLs the parm.  */

static unsigned int

rest_of_handle_df_finish (void)