OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [df-core.c] - Diff between revs 816 and 826

Only display areas with differences | Details | Blame | View Log

Rev 816 Rev 826
/* Allocation for dataflow support routines.
/* Allocation for dataflow support routines.
   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
   2008, 2009, 2010 Free Software Foundation, Inc.
   2008, 2009, 2010 Free Software Foundation, Inc.
   Originally contributed by Michael P. Hayes
   Originally contributed by Michael P. Hayes
             (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
             (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
   Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
   Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
             and Kenneth Zadeck (zadeck@naturalbridge.com).
             and Kenneth Zadeck (zadeck@naturalbridge.com).
 
 
This file is part of GCC.
This file is part of GCC.
 
 
GCC is free software; you can redistribute it and/or modify it under
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
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
Software Foundation; either version 3, or (at your option) any later
version.
version.
 
 
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.
for more details.
 
 
You should have received a copy of the GNU General Public License
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */
<http://www.gnu.org/licenses/>.  */
 
 
/*
/*
OVERVIEW:
OVERVIEW:
 
 
The files in this collection (df*.c,df.h) provide a general framework
The files in this collection (df*.c,df.h) provide a general framework
for solving dataflow problems.  The global dataflow is performed using
for solving dataflow problems.  The global dataflow is performed using
a good implementation of iterative dataflow analysis.
a good implementation of iterative dataflow analysis.
 
 
The file df-problems.c provides problem instance for the most common
The file df-problems.c provides problem instance for the most common
dataflow problems: reaching defs, upward exposed uses, live variables,
dataflow problems: reaching defs, upward exposed uses, live variables,
uninitialized variables, def-use chains, and use-def chains.  However,
uninitialized variables, def-use chains, and use-def chains.  However,
the interface allows other dataflow problems to be defined as well.
the interface allows other dataflow problems to be defined as well.
 
 
Dataflow analysis is available in most of the rtl backend (the parts
Dataflow analysis is available in most of the rtl backend (the parts
between pass_df_initialize and pass_df_finish).  It is quite likely
between pass_df_initialize and pass_df_finish).  It is quite likely
that these boundaries will be expanded in the future.  The only
that these boundaries will be expanded in the future.  The only
requirement is that there be a correct control flow graph.
requirement is that there be a correct control flow graph.
 
 
There are three variations of the live variable problem that are
There are three variations of the live variable problem that are
available whenever dataflow is available.  The LR problem finds the
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 reach a use of a variable, the UR problems finds the
areas that can be reached from a definition of a variable.  The LIVE
areas that can be reached from a definition of a variable.  The LIVE
problem finds the intersection of these two areas.
problem finds the intersection of these two areas.
 
 
There are several optional problems.  These can be enabled when they
There are several optional problems.  These can be enabled when they
are needed and disabled when they are not needed.
are needed and disabled when they are not needed.
 
 
Dataflow problems are generally solved in three layers.  The bottom
Dataflow problems are generally solved in three layers.  The bottom
layer is called scanning where a data structure is built for each rtl
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
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
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
version of that insn changes also.  There are various mechanisms for
making this happen and are described in the INCREMENTAL SCANNING
making this happen and are described in the INCREMENTAL SCANNING
section.
section.
 
 
In the middle layer, basic blocks are scanned to produce transfer
In the middle layer, basic blocks are scanned to produce transfer
functions which describe the effects of that block on the global
functions which describe the effects of that block on the global
dataflow solution.  The transfer functions are only rebuilt if the
dataflow solution.  The transfer functions are only rebuilt if the
some instruction within the block has changed.
some instruction within the block has changed.
 
 
The top layer is the dataflow solution itself.  The dataflow solution
The top layer is the dataflow solution itself.  The dataflow solution
is computed by using an efficient iterative solver and the transfer
is computed by using an efficient iterative solver and the transfer
functions.  The dataflow solution must be recomputed whenever the
functions.  The dataflow solution must be recomputed whenever the
control changes or if one of the transfer function changes.
control changes or if one of the transfer function changes.
 
 
 
 
USAGE:
USAGE:
 
 
Here is an example of using the dataflow routines.
Here is an example of using the dataflow routines.
 
 
      df_[chain,live,note,rd]_add_problem (flags);
      df_[chain,live,note,rd]_add_problem (flags);
 
 
      df_set_blocks (blocks);
      df_set_blocks (blocks);
 
 
      df_analyze ();
      df_analyze ();
 
 
      df_dump (stderr);
      df_dump (stderr);
 
 
      df_finish_pass (false);
      df_finish_pass (false);
 
 
DF_[chain,live,note,rd]_ADD_PROBLEM adds a problem, defined by an
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 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
instance of df.  All calls to add a problem for a given instance of df
must occur before the first call to DF_ANALYZE.
must occur before the first call to DF_ANALYZE.
 
 
Problems can be dependent on other problems.  For instance, solving
Problems can be dependent on other problems.  For instance, solving
def-use or use-def chains is dependent on solving reaching
def-use or use-def chains is dependent on solving reaching
definitions. As long as these dependencies are listed in the problem
definitions. As long as these dependencies are listed in the problem
definition, the order of adding the problems is not material.
definition, the order of adding the problems is not material.
Otherwise, the problems will be solved in the order of calls to
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
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.
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
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
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.
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
DF_SET_BLOCKS only effects the blocks that are effected when computing
the transfer functions and final solution.  The insn level information
the transfer functions and final solution.  The insn level information
is always kept up to date.
is always kept up to date.
 
 
When a subset is given, the analysis behaves as if the function only
When a subset is given, the analysis behaves as if the function only
contains those blocks and any edges that occur directly between the
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
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
before the call to analyze in order to eliminate the possibility that
optimizations that reorder blocks invalidate the bitvector.
optimizations that reorder blocks invalidate the bitvector.
 
 
DF_ANALYZE causes all of the defined problems to be (re)solved.  When
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
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
contain the computer information.  The DF_*_BB_INFO macros can be used
to access these bitvectors.  All deferred rescannings are down before
to access these bitvectors.  All deferred rescannings are down before
the transfer functions are recomputed.
the transfer functions are recomputed.
 
 
DF_DUMP can then be called to dump the information produce to some
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
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
basic block specific, and then calls DF_DUMP_TOP and DF_DUMP_BOTTOM
for each block to print the basic specific information.  These parts
for each block to print the basic specific information.  These parts
can all be called separately as part of a larger dump function.
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
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
optional problems.  It also causes any insns whose scanning has been
deferred to be rescanned as well as clears all of the changeable flags.
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
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
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
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
optional problems in the pass dumps, use the TODO flag rather than
calling the function yourself.
calling the function yourself.
 
 
INCREMENTAL SCANNING
INCREMENTAL SCANNING
 
 
There are four ways of doing the incremental scanning:
There are four ways of doing the incremental scanning:
 
 
1) Immediate rescanning - Calls to df_insn_rescan, df_notes_rescan,
1) Immediate rescanning - Calls to df_insn_rescan, df_notes_rescan,
   df_bb_delete, df_insn_change_bb have been added to most of
   df_bb_delete, df_insn_change_bb have been added to most of
   the low level service functions that maintain the cfg and change
   the low level service functions that maintain the cfg and change
   rtl.  Calling and of these routines many cause some number of insns
   rtl.  Calling and of these routines many cause some number of insns
   to be rescanned.
   to be rescanned.
 
 
   For most modern rtl passes, this is certainly the easiest way to
   For most modern rtl passes, this is certainly the easiest way to
   manage rescanning the insns.  This technique also has the advantage
   manage rescanning the insns.  This technique also has the advantage
   that the scanning information is always correct and can be relied
   that the scanning information is always correct and can be relied
   upon even after changes have been made to the instructions.  This
   upon even after changes have been made to the instructions.  This
   technique is contra indicated in several cases:
   technique is contra indicated in several cases:
 
 
   a) If def-use chains OR use-def chains (but not both) are built,
   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
      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
      deleted that is the target of an edge, there is not enough
      information to efficiently find the source of the edge and
      information to efficiently find the source of the edge and
      delete the edge.  This leaves a dangling reference that may
      delete the edge.  This leaves a dangling reference that may
      cause problems.
      cause problems.
 
 
   b) If def-use chains AND use-def chains are built, this may
   b) If def-use chains AND use-def chains are built, this may
      produce unexpected results.  The problem is that the incremental
      produce unexpected results.  The problem is that the incremental
      scanning of an insn does not know how to repair the chains that
      scanning of an insn does not know how to repair the chains that
      point into an insn when the insn changes.  So the incremental
      point into an insn when the insn changes.  So the incremental
      scanning just deletes the chains that enter and exit the insn
      scanning just deletes the chains that enter and exit the insn
      being changed.  The dangling reference issue in (a) is not a
      being changed.  The dangling reference issue in (a) is not a
      problem here, but if the pass is depending on the chains being
      problem here, but if the pass is depending on the chains being
      maintained after insns have been modified, this technique will
      maintained after insns have been modified, this technique will
      not do the correct thing.
      not do the correct thing.
 
 
   c) If the pass modifies insns several times, this incremental
   c) If the pass modifies insns several times, this incremental
      updating may be expensive.
      updating may be expensive.
 
 
   d) If the pass modifies all of the insns, as does register
   d) If the pass modifies all of the insns, as does register
      allocation, it is simply better to rescan the entire function.
      allocation, it is simply better to rescan the entire function.
 
 
2) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and
2) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and
   df_insn_delete do not immediately change the insn but instead make
   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
   a note that the insn needs to be rescanned.  The next call to
   df_analyze, df_finish_pass, or df_process_deferred_rescans will
   df_analyze, df_finish_pass, or df_process_deferred_rescans will
   cause all of the pending rescans to be processed.
   cause all of the pending rescans to be processed.
 
 
   This is the technique of choice if either 1a, 1b, or 1c are issues
   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
   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
   (either manually or via TODO_df_finish) should be made before the
   next call to df_analyze or df_process_deferred_rescans.
   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,
   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
   note_stores and for_each_rtx instead of using the DF data.  This
   can be said to fall under case 1c.
   can be said to fall under case 1c.
 
 
   To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN).
   To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN).
   (This mode can be cleared by calling df_clear_flags
   (This mode can be cleared by calling df_clear_flags
   (DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to
   (DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to
   be rescanned.
   be rescanned.
 
 
3) Total rescanning - In this mode the rescanning is disabled.
3) Total rescanning - In this mode the rescanning is disabled.
   Only when insns are deleted is the df information associated with
   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
   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
   df_insn_rescan_all.  This method is used by the register allocator
   since it generally changes each insn multiple times (once for each ref)
   since it generally changes each insn multiple times (once for each ref)
   and does not need to make use of the updated scanning information.
   and does not need to make use of the updated scanning information.
 
 
4) Do it yourself - In this mechanism, the pass updates the insns
4) Do it yourself - In this mechanism, the pass updates the insns
   itself using the low level df primitives.  Currently no pass does
   itself using the low level df primitives.  Currently no pass does
   this, but it has the advantage that it is quite efficient given
   this, but it has the advantage that it is quite efficient given
   that the pass generally has exact knowledge of what it is changing.
   that the pass generally has exact knowledge of what it is changing.
 
 
DATA STRUCTURES
DATA STRUCTURES
 
 
Scanning produces a `struct df_ref' data structure (ref) is allocated
Scanning produces a `struct df_ref' data structure (ref) is allocated
for every register reference (def or use) and this records the insn
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
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
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
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
the def refs for a use.  This is used to create use-def or def-use
chains.
chains.
 
 
Different optimizations have different needs.  Ultimately, only
Different optimizations have different needs.  Ultimately, only
register allocation and schedulers should be using the bitmaps
register allocation and schedulers should be using the bitmaps
produced for the live register and uninitialized register problems.
produced for the live register and uninitialized register problems.
The rest of the backend should be upgraded to using and maintaining
The rest of the backend should be upgraded to using and maintaining
the linked information such as def use or use def chains.
the linked information such as def use or use def chains.
 
 
 
 
PHILOSOPHY:
PHILOSOPHY:
 
 
While incremental bitmaps are not worthwhile to maintain, incremental
While incremental bitmaps are not worthwhile to maintain, incremental
chains may be perfectly reasonable.  The fastest way to build chains
chains may be perfectly reasonable.  The fastest way to build chains
from scratch or after significant modifications is to build reaching
from scratch or after significant modifications is to build reaching
definitions (RD) and build the chains from this.
definitions (RD) and build the chains from this.
 
 
However, general algorithms for maintaining use-def or def-use chains
However, general algorithms for maintaining use-def or def-use chains
are not practical.  The amount of work to recompute the chain any
are not practical.  The amount of work to recompute the chain any
chain after an arbitrary change is large.  However, with a modest
chain after an arbitrary change is large.  However, with a modest
amount of work it is generally possible to have the application that
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
uses the chains keep them up to date.  The high level knowledge of
what is really happening is essential to crafting efficient
what is really happening is essential to crafting efficient
incremental algorithms.
incremental algorithms.
 
 
As for the bit vector problems, there is no interface to give a set of
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
blocks over with to resolve the iteration.  In general, restarting a
dataflow iteration is difficult and expensive.  Again, the best way to
dataflow iteration is difficult and expensive.  Again, the best way to
keep the dataflow information up to data (if this is really what is
keep the dataflow information up to data (if this is really what is
needed) it to formulate a problem specific solution.
needed) it to formulate a problem specific solution.
 
 
There are fine grained calls for creating and deleting references from
There are fine grained calls for creating and deleting references from
instructions in df-scan.c.  However, these are not currently connected
instructions in df-scan.c.  However, these are not currently connected
to the engine that resolves the dataflow equations.
to the engine that resolves the dataflow equations.
 
 
 
 
DATA STRUCTURES:
DATA STRUCTURES:
 
 
The basic object is a DF_REF (reference) and this may either be a
The basic object is a DF_REF (reference) and this may either be a
DEF (definition) or a USE of a register.
DEF (definition) or a USE of a register.
 
 
These are linked into a variety of lists; namely reg-def, reg-use,
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
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
reg-def lists contain all the locations that define a given register
while the insn-use lists contain all the locations that use a
while the insn-use lists contain all the locations that use a
register.
register.
 
 
Note that the reg-def and reg-use chains are generally short for
Note that the reg-def and reg-use chains are generally short for
pseudos and long for the hard registers.
pseudos and long for the hard registers.
 
 
ACCESSING INSNS:
ACCESSING INSNS:
 
 
1) The df insn information is kept in an array of DF_INSN_INFO objects.
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
   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.
   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
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,
   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
   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
   (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_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).
   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
   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
   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
   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
   DF_REF_NEXT_REF macro.)  There is no significance to the ordering of
   the uses or refs in an instruction.
   the uses or refs in an instruction.
 
 
3) Each insn has a logical uid field (LUID) which is stored in the
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
   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.
   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
   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 basic block, in order from the start of the block.
   The numbers are only correct after a call to df_analyze.  They will
   The numbers are only correct after a call to df_analyze.  They will
   rot after insns are added deleted or moved round.
   rot after insns are added deleted or moved round.
 
 
ACCESSING REFS:
ACCESSING REFS:
 
 
There are 4 ways to obtain access to refs:
There are 4 ways to obtain access to refs:
 
 
1) References are divided into two categories, REAL and ARTIFICIAL.
1) References are divided into two categories, REAL and ARTIFICIAL.
 
 
   REAL refs are associated with instructions.
   REAL refs are associated with instructions.
 
 
   ARTIFICIAL refs are associated with basic blocks.  The heads of
   ARTIFICIAL refs are associated with basic blocks.  The heads of
   these lists can be accessed by calling df_get_artificial_defs or
   these lists can be accessed by calling df_get_artificial_defs or
   df_get_artificial_uses for the particular basic block.
   df_get_artificial_uses for the particular basic block.
 
 
   Artificial defs and uses occur both at the beginning and ends of blocks.
   Artificial defs and uses occur both at the beginning and ends of blocks.
 
 
     For blocks that area at the destination of eh edges, the
     For blocks that area at the destination of eh edges, the
     artificial uses and defs occur at the beginning.  The defs relate
     artificial uses and defs occur at the beginning.  The defs relate
     to the registers specified in EH_RETURN_DATA_REGNO and the uses
     to the registers specified in EH_RETURN_DATA_REGNO and the uses
     relate to the registers specified in ED_USES.  Logically these
     relate to the registers specified in ED_USES.  Logically these
     defs and uses should really occur along the eh edge, but there is
     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
     no convenient way to do this.  Artificial edges that occur at the
     beginning of the block have the DF_REF_AT_TOP flag set.
     beginning of the block have the DF_REF_AT_TOP flag set.
 
 
     Artificial uses occur at the end of all blocks.  These arise from
     Artificial uses occur at the end of all blocks.  These arise from
     the hard registers that are always live, such as the stack
     the hard registers that are always live, such as the stack
     register and are put there to keep the code from forgetting about
     register and are put there to keep the code from forgetting about
     them.
     them.
 
 
     Artificial defs occur at the end of the entry block.  These arise
     Artificial defs occur at the end of the entry block.  These arise
     from registers that are live at entry to the function.
     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
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.)
   uses that appear inside a REG_EQUAL or REG_EQUIV note.)
 
 
   All of the eq_uses, uses and defs associated with each pseudo or
   All of the eq_uses, uses and defs associated with each pseudo or
   hard register may be linked in a bidirectional chain.  These are
   hard register may be linked in a bidirectional chain.  These are
   called reg-use or reg_def chains.  If the changeable flag
   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
   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.
   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 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
   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
   macros.  Subsequent uses for the same regno can be obtained by
   following the next_reg field of the ref.  The number of elements in
   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,
   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.
   DF_REG_EQ_USE_COUNT or DF_REG_DEF_COUNT macros.
 
 
   In previous versions of this code, these chains were ordered.  It
   In previous versions of this code, these chains were ordered.  It
   has not been practical to continue this practice.
   has not been practical to continue this practice.
 
 
3) If def-use or use-def chains are built, these can be traversed to
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
   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
   include the eq_uses.  Otherwise these are ignored when building the
   chains.
   chains.
 
 
4) An array of all of the uses (and an array of all of the defs) can
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
   be built.  These arrays are indexed by the value in the id
   structure.  These arrays are only lazily kept up to date, and that
   structure.  These arrays are only lazily kept up to date, and that
   process can be expensive.  To have these arrays built, call
   process can be expensive.  To have these arrays built, call
   df_reorganize_defs or df_reorganize_uses.  If the flag DF_EQ_NOTES
   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
   has been set the array will contain the eq_uses.  Otherwise these
   are ignored when building the array and assigning the ids.  Note
   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
   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.
   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
   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
   better to traverse all of the registers and then traverse all of
   reg-use or reg-def chains.
   reg-use or reg-def chains.
 
 
NOTES:
NOTES:
 
 
Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
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
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))))
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
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))))
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),
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
even though reg 41 is decremented before it is used for the memory
address in this second example.
address in this second example.
 
 
A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
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
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
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
operation.  We generate both a use and a def and again mark them
read/write.
read/write.
 
 
Paradoxical subreg writes do not leave a trace of the old content, so they
Paradoxical subreg writes do not leave a trace of the old content, so they
are write-only operations.
are write-only operations.
*/
*/
 
 
 
 
#include "config.h"
#include "config.h"
#include "system.h"
#include "system.h"
#include "coretypes.h"
#include "coretypes.h"
#include "tm.h"
#include "tm.h"
#include "rtl.h"
#include "rtl.h"
#include "tm_p.h"
#include "tm_p.h"
#include "insn-config.h"
#include "insn-config.h"
#include "recog.h"
#include "recog.h"
#include "function.h"
#include "function.h"
#include "regs.h"
#include "regs.h"
#include "output.h"
#include "output.h"
#include "alloc-pool.h"
#include "alloc-pool.h"
#include "flags.h"
#include "flags.h"
#include "hard-reg-set.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "basic-block.h"
#include "sbitmap.h"
#include "sbitmap.h"
#include "bitmap.h"
#include "bitmap.h"
#include "timevar.h"
#include "timevar.h"
#include "df.h"
#include "df.h"
#include "tree-pass.h"
#include "tree-pass.h"
#include "params.h"
#include "params.h"
 
 
static void *df_get_bb_info (struct dataflow *, unsigned int);
static void *df_get_bb_info (struct dataflow *, unsigned int);
static void df_set_bb_info (struct dataflow *, unsigned int, void *);
static void df_set_bb_info (struct dataflow *, unsigned int, void *);
#ifdef DF_DEBUG_CFG
#ifdef DF_DEBUG_CFG
static void df_set_clean_cfg (void);
static void df_set_clean_cfg (void);
#endif
#endif
 
 
/* An obstack for bitmap not related to specific dataflow problems.
/* An obstack for bitmap not related to specific dataflow problems.
   This obstack should e.g. be used for bitmaps with a short life time
   This obstack should e.g. be used for bitmaps with a short life time
   such as temporary bitmaps.  */
   such as temporary bitmaps.  */
 
 
bitmap_obstack df_bitmap_obstack;
bitmap_obstack df_bitmap_obstack;
 
 
 
 
/*----------------------------------------------------------------------------
/*----------------------------------------------------------------------------
  Functions to create, destroy and manipulate an instance of df.
  Functions to create, destroy and manipulate an instance of df.
----------------------------------------------------------------------------*/
----------------------------------------------------------------------------*/
 
 
struct df *df;
struct df *df;
 
 
/* Add PROBLEM (and any dependent problems) to the DF instance.  */
/* Add PROBLEM (and any dependent problems) to the DF instance.  */
 
 
void
void
df_add_problem (struct df_problem *problem)
df_add_problem (struct df_problem *problem)
{
{
  struct dataflow *dflow;
  struct dataflow *dflow;
  int i;
  int i;
 
 
  /* First try to add the dependent problem. */
  /* First try to add the dependent problem. */
  if (problem->dependent_problem)
  if (problem->dependent_problem)
    df_add_problem (problem->dependent_problem);
    df_add_problem (problem->dependent_problem);
 
 
  /* Check to see if this problem has already been defined.  If it
  /* 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
     has, just return that instance, if not, add it to the end of the
     vector.  */
     vector.  */
  dflow = df->problems_by_index[problem->id];
  dflow = df->problems_by_index[problem->id];
  if (dflow)
  if (dflow)
    return;
    return;
 
 
  /* Make a new one and add it to the end.  */
  /* Make a new one and add it to the end.  */
  dflow = XCNEW (struct dataflow);
  dflow = XCNEW (struct dataflow);
  dflow->problem = problem;
  dflow->problem = problem;
  dflow->computed = false;
  dflow->computed = false;
  dflow->solutions_dirty = true;
  dflow->solutions_dirty = true;
  df->problems_by_index[dflow->problem->id] = dflow;
  df->problems_by_index[dflow->problem->id] = dflow;
 
 
  /* Keep the defined problems ordered by index.  This solves the
  /* Keep the defined problems ordered by index.  This solves the
     problem that RI will use the information from UREC if UREC has
     problem that RI will use the information from UREC if UREC has
     been defined, or from LIVE if LIVE is defined and otherwise LR.
     been defined, or from LIVE if LIVE is defined and otherwise LR.
     However for this to work, the computation of RI must be pushed
     However for this to work, the computation of RI must be pushed
     after which ever of those problems is defined, but we do not
     after which ever of those problems is defined, but we do not
     require any of those except for LR to have actually been
     require any of those except for LR to have actually been
     defined.  */
     defined.  */
  df->num_problems_defined++;
  df->num_problems_defined++;
  for (i = df->num_problems_defined - 2; i >= 0; i--)
  for (i = df->num_problems_defined - 2; i >= 0; i--)
    {
    {
      if (problem->id < df->problems_in_order[i]->problem->id)
      if (problem->id < df->problems_in_order[i]->problem->id)
        df->problems_in_order[i+1] = df->problems_in_order[i];
        df->problems_in_order[i+1] = df->problems_in_order[i];
      else
      else
        {
        {
          df->problems_in_order[i+1] = dflow;
          df->problems_in_order[i+1] = dflow;
          return;
          return;
        }
        }
    }
    }
  df->problems_in_order[0] = dflow;
  df->problems_in_order[0] = dflow;
}
}
 
 
 
 
/* Set the MASK flags in the DFLOW problem.  The old flags are
/* 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
   returned.  If a flag is not allowed to be changed this will fail if
   checking is enabled.  */
   checking is enabled.  */
int
int
df_set_flags (int changeable_flags)
df_set_flags (int changeable_flags)
{
{
  int old_flags = df->changeable_flags;
  int old_flags = df->changeable_flags;
  df->changeable_flags |= changeable_flags;
  df->changeable_flags |= changeable_flags;
  return old_flags;
  return old_flags;
}
}
 
 
 
 
/* Clear the MASK flags in the DFLOW problem.  The old flags are
/* 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
   returned.  If a flag is not allowed to be changed this will fail if
   checking is enabled.  */
   checking is enabled.  */
int
int
df_clear_flags (int changeable_flags)
df_clear_flags (int changeable_flags)
{
{
  int old_flags = df->changeable_flags;
  int old_flags = df->changeable_flags;
  df->changeable_flags &= ~changeable_flags;
  df->changeable_flags &= ~changeable_flags;
  return old_flags;
  return old_flags;
}
}
 
 
 
 
/* Set the blocks that are to be considered for analysis.  If this is
/* Set the blocks that are to be considered for analysis.  If this is
   not called or is called with null, the entire function in
   not called or is called with null, the entire function in
   analyzed.  */
   analyzed.  */
 
 
void
void
df_set_blocks (bitmap blocks)
df_set_blocks (bitmap blocks)
{
{
  if (blocks)
  if (blocks)
    {
    {
      if (dump_file)
      if (dump_file)
        bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
        bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
      if (df->blocks_to_analyze)
      if (df->blocks_to_analyze)
        {
        {
          /* This block is called to change the focus from one subset
          /* This block is called to change the focus from one subset
             to another.  */
             to another.  */
          int p;
          int p;
          bitmap diff = BITMAP_ALLOC (&df_bitmap_obstack);
          bitmap diff = BITMAP_ALLOC (&df_bitmap_obstack);
          bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
          bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
          for (p = 0; p < df->num_problems_defined; p++)
          for (p = 0; p < df->num_problems_defined; p++)
            {
            {
              struct dataflow *dflow = df->problems_in_order[p];
              struct dataflow *dflow = df->problems_in_order[p];
              if (dflow->optional_p && dflow->problem->reset_fun)
              if (dflow->optional_p && dflow->problem->reset_fun)
                dflow->problem->reset_fun (df->blocks_to_analyze);
                dflow->problem->reset_fun (df->blocks_to_analyze);
              else if (dflow->problem->free_blocks_on_set_blocks)
              else if (dflow->problem->free_blocks_on_set_blocks)
                {
                {
                  bitmap_iterator bi;
                  bitmap_iterator bi;
                  unsigned int bb_index;
                  unsigned int bb_index;
 
 
                  EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
                  EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
                    {
                    {
                      basic_block bb = BASIC_BLOCK (bb_index);
                      basic_block bb = BASIC_BLOCK (bb_index);
                      if (bb)
                      if (bb)
                        {
                        {
                          void *bb_info = df_get_bb_info (dflow, bb_index);
                          void *bb_info = df_get_bb_info (dflow, bb_index);
                          if (bb_info)
                          if (bb_info)
                            {
                            {
                              dflow->problem->free_bb_fun (bb, bb_info);
                              dflow->problem->free_bb_fun (bb, bb_info);
                              df_set_bb_info (dflow, bb_index, NULL);
                              df_set_bb_info (dflow, bb_index, NULL);
                            }
                            }
                        }
                        }
                    }
                    }
                }
                }
            }
            }
 
 
          BITMAP_FREE (diff);
          BITMAP_FREE (diff);
        }
        }
      else
      else
        {
        {
          /* This block of code is executed to change the focus from
          /* This block of code is executed to change the focus from
             the entire function to a subset.  */
             the entire function to a subset.  */
          bitmap blocks_to_reset = NULL;
          bitmap blocks_to_reset = NULL;
          int p;
          int p;
          for (p = 0; p < df->num_problems_defined; p++)
          for (p = 0; p < df->num_problems_defined; p++)
            {
            {
              struct dataflow *dflow = df->problems_in_order[p];
              struct dataflow *dflow = df->problems_in_order[p];
              if (dflow->optional_p && dflow->problem->reset_fun)
              if (dflow->optional_p && dflow->problem->reset_fun)
                {
                {
                  if (!blocks_to_reset)
                  if (!blocks_to_reset)
                    {
                    {
                      basic_block bb;
                      basic_block bb;
                      blocks_to_reset =
                      blocks_to_reset =
                        BITMAP_ALLOC (&df_bitmap_obstack);
                        BITMAP_ALLOC (&df_bitmap_obstack);
                      FOR_ALL_BB(bb)
                      FOR_ALL_BB(bb)
                        {
                        {
                          bitmap_set_bit (blocks_to_reset, bb->index);
                          bitmap_set_bit (blocks_to_reset, bb->index);
                        }
                        }
                    }
                    }
                  dflow->problem->reset_fun (blocks_to_reset);
                  dflow->problem->reset_fun (blocks_to_reset);
                }
                }
            }
            }
          if (blocks_to_reset)
          if (blocks_to_reset)
            BITMAP_FREE (blocks_to_reset);
            BITMAP_FREE (blocks_to_reset);
 
 
          df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);
          df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);
        }
        }
      bitmap_copy (df->blocks_to_analyze, blocks);
      bitmap_copy (df->blocks_to_analyze, blocks);
      df->analyze_subset = true;
      df->analyze_subset = true;
    }
    }
  else
  else
    {
    {
      /* This block is executed to reset the focus to the entire
      /* This block is executed to reset the focus to the entire
         function.  */
         function.  */
      if (dump_file)
      if (dump_file)
        fprintf (dump_file, "clearing blocks_to_analyze\n");
        fprintf (dump_file, "clearing blocks_to_analyze\n");
      if (df->blocks_to_analyze)
      if (df->blocks_to_analyze)
        {
        {
          BITMAP_FREE (df->blocks_to_analyze);
          BITMAP_FREE (df->blocks_to_analyze);
          df->blocks_to_analyze = NULL;
          df->blocks_to_analyze = NULL;
        }
        }
      df->analyze_subset = false;
      df->analyze_subset = false;
    }
    }
 
 
  /* Setting the blocks causes the refs to be unorganized since only
  /* Setting the blocks causes the refs to be unorganized since only
     the refs in the blocks are seen.  */
     the refs in the blocks are seen.  */
  df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
  df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
  df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
  df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
  df_mark_solutions_dirty ();
  df_mark_solutions_dirty ();
}
}
 
 
 
 
/* Delete a DFLOW problem (and any problems that depend on this
/* Delete a DFLOW problem (and any problems that depend on this
   problem).  */
   problem).  */
 
 
void
void
df_remove_problem (struct dataflow *dflow)
df_remove_problem (struct dataflow *dflow)
{
{
  struct df_problem *problem;
  struct df_problem *problem;
  int i;
  int i;
 
 
  if (!dflow)
  if (!dflow)
    return;
    return;
 
 
  problem = dflow->problem;
  problem = dflow->problem;
  gcc_assert (problem->remove_problem_fun);
  gcc_assert (problem->remove_problem_fun);
 
 
  /* Delete any problems that depended on this problem first.  */
  /* Delete any problems that depended on this problem first.  */
  for (i = 0; i < df->num_problems_defined; i++)
  for (i = 0; i < df->num_problems_defined; i++)
    if (df->problems_in_order[i]->problem->dependent_problem == problem)
    if (df->problems_in_order[i]->problem->dependent_problem == problem)
      df_remove_problem (df->problems_in_order[i]);
      df_remove_problem (df->problems_in_order[i]);
 
 
  /* Now remove this problem.  */
  /* Now remove this problem.  */
  for (i = 0; i < df->num_problems_defined; i++)
  for (i = 0; i < df->num_problems_defined; i++)
    if (df->problems_in_order[i] == dflow)
    if (df->problems_in_order[i] == dflow)
      {
      {
        int j;
        int j;
        for (j = i + 1; j < df->num_problems_defined; 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] = df->problems_in_order[j];
        df->problems_in_order[j-1] = NULL;
        df->problems_in_order[j-1] = NULL;
        df->num_problems_defined--;
        df->num_problems_defined--;
        break;
        break;
      }
      }
 
 
  (problem->remove_problem_fun) ();
  (problem->remove_problem_fun) ();
  df->problems_by_index[problem->id] = NULL;
  df->problems_by_index[problem->id] = NULL;
}
}
 
 
 
 
/* Remove all of the problems that are not permanent.  Scanning, LR
/* Remove all of the problems that are not permanent.  Scanning, LR
   and (at -O2 or higher) LIVE are permanent, the rest are removable.
   and (at -O2 or higher) LIVE are permanent, the rest are removable.
   Also clear all of the changeable_flags.  */
   Also clear all of the changeable_flags.  */
 
 
void
void
df_finish_pass (bool verify ATTRIBUTE_UNUSED)
df_finish_pass (bool verify ATTRIBUTE_UNUSED)
{
{
  int i;
  int i;
  int removed = 0;
  int removed = 0;
 
 
#ifdef ENABLE_DF_CHECKING
#ifdef ENABLE_DF_CHECKING
  int saved_flags;
  int saved_flags;
#endif
#endif
 
 
  if (!df)
  if (!df)
    return;
    return;
 
 
  df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
  df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
  df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
  df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
 
 
#ifdef ENABLE_DF_CHECKING
#ifdef ENABLE_DF_CHECKING
  saved_flags = df->changeable_flags;
  saved_flags = df->changeable_flags;
#endif
#endif
 
 
  for (i = 0; i < df->num_problems_defined; i++)
  for (i = 0; i < df->num_problems_defined; i++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[i];
      struct dataflow *dflow = df->problems_in_order[i];
      struct df_problem *problem = dflow->problem;
      struct df_problem *problem = dflow->problem;
 
 
      if (dflow->optional_p)
      if (dflow->optional_p)
        {
        {
          gcc_assert (problem->remove_problem_fun);
          gcc_assert (problem->remove_problem_fun);
          (problem->remove_problem_fun) ();
          (problem->remove_problem_fun) ();
          df->problems_in_order[i] = NULL;
          df->problems_in_order[i] = NULL;
          df->problems_by_index[problem->id] = NULL;
          df->problems_by_index[problem->id] = NULL;
          removed++;
          removed++;
        }
        }
    }
    }
  df->num_problems_defined -= removed;
  df->num_problems_defined -= removed;
 
 
  /* Clear all of the flags.  */
  /* Clear all of the flags.  */
  df->changeable_flags = 0;
  df->changeable_flags = 0;
  df_process_deferred_rescans ();
  df_process_deferred_rescans ();
 
 
  /* Set the focus back to the whole function.  */
  /* Set the focus back to the whole function.  */
  if (df->blocks_to_analyze)
  if (df->blocks_to_analyze)
    {
    {
      BITMAP_FREE (df->blocks_to_analyze);
      BITMAP_FREE (df->blocks_to_analyze);
      df->blocks_to_analyze = NULL;
      df->blocks_to_analyze = NULL;
      df_mark_solutions_dirty ();
      df_mark_solutions_dirty ();
      df->analyze_subset = false;
      df->analyze_subset = false;
    }
    }
 
 
#ifdef ENABLE_DF_CHECKING
#ifdef ENABLE_DF_CHECKING
  /* Verification will fail in DF_NO_INSN_RESCAN.  */
  /* Verification will fail in DF_NO_INSN_RESCAN.  */
  if (!(saved_flags & DF_NO_INSN_RESCAN))
  if (!(saved_flags & DF_NO_INSN_RESCAN))
    {
    {
      df_lr_verify_transfer_functions ();
      df_lr_verify_transfer_functions ();
      if (df_live)
      if (df_live)
        df_live_verify_transfer_functions ();
        df_live_verify_transfer_functions ();
    }
    }
 
 
#ifdef DF_DEBUG_CFG
#ifdef DF_DEBUG_CFG
  df_set_clean_cfg ();
  df_set_clean_cfg ();
#endif
#endif
#endif
#endif
 
 
#ifdef ENABLE_CHECKING
#ifdef ENABLE_CHECKING
  if (verify)
  if (verify)
    df->changeable_flags |= DF_VERIFY_SCHEDULED;
    df->changeable_flags |= DF_VERIFY_SCHEDULED;
#endif
#endif
}
}
 
 
 
 
/* Set up the dataflow instance for the entire back end.  */
/* Set up the dataflow instance for the entire back end.  */
 
 
static unsigned int
static unsigned int
rest_of_handle_df_initialize (void)
rest_of_handle_df_initialize (void)
{
{
  gcc_assert (!df);
  gcc_assert (!df);
  df = XCNEW (struct df);
  df = XCNEW (struct df);
  df->changeable_flags = 0;
  df->changeable_flags = 0;
 
 
  bitmap_obstack_initialize (&df_bitmap_obstack);
  bitmap_obstack_initialize (&df_bitmap_obstack);
 
 
  /* Set this to a conservative value.  Stack_ptr_mod will compute it
  /* Set this to a conservative value.  Stack_ptr_mod will compute it
     correctly later.  */
     correctly later.  */
  current_function_sp_is_unchanging = 0;
  current_function_sp_is_unchanging = 0;
 
 
  df_scan_add_problem ();
  df_scan_add_problem ();
  df_scan_alloc (NULL);
  df_scan_alloc (NULL);
 
 
  /* These three problems are permanent.  */
  /* These three problems are permanent.  */
  df_lr_add_problem ();
  df_lr_add_problem ();
  if (optimize > 1)
  if (optimize > 1)
    df_live_add_problem ();
    df_live_add_problem ();
 
 
  df->postorder = XNEWVEC (int, last_basic_block);
  df->postorder = XNEWVEC (int, last_basic_block);
  df->postorder_inverted = 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 = post_order_compute (df->postorder, true, true);
  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
  gcc_assert (df->n_blocks == df->n_blocks_inverted);
  gcc_assert (df->n_blocks == df->n_blocks_inverted);
 
 
  df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
  df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
  memset (df->hard_regs_live_count, 0,
  memset (df->hard_regs_live_count, 0,
          sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);
          sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);
 
 
  df_hard_reg_init ();
  df_hard_reg_init ();
  /* After reload, some ports add certain bits to regs_ever_live so
  /* After reload, some ports add certain bits to regs_ever_live so
     this cannot be reset.  */
     this cannot be reset.  */
  df_compute_regs_ever_live (true);
  df_compute_regs_ever_live (true);
  df_scan_blocks ();
  df_scan_blocks ();
  df_compute_regs_ever_live (false);
  df_compute_regs_ever_live (false);
  return 0;
  return 0;
}
}
 
 
 
 
static bool
static bool
gate_opt (void)
gate_opt (void)
{
{
  return optimize > 0;
  return optimize > 0;
}
}
 
 
 
 
struct rtl_opt_pass pass_df_initialize_opt =
struct rtl_opt_pass pass_df_initialize_opt =
{
{
 {
 {
  RTL_PASS,
  RTL_PASS,
  "dfinit",                             /* name */
  "dfinit",                             /* name */
  gate_opt,                             /* gate */
  gate_opt,                             /* gate */
  rest_of_handle_df_initialize,         /* execute */
  rest_of_handle_df_initialize,         /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  0,                                    /* static_pass_number */
  TV_NONE,                              /* tv_id */
  TV_NONE,                              /* tv_id */
  0,                                    /* properties_required */
  0,                                    /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  0,                                    /* properties_destroyed */
  0,                                    /* todo_flags_start */
  0,                                    /* todo_flags_start */
  0                                     /* todo_flags_finish */
  0                                     /* todo_flags_finish */
 }
 }
};
};
 
 
 
 
static bool
static bool
gate_no_opt (void)
gate_no_opt (void)
{
{
  return optimize == 0;
  return optimize == 0;
}
}
 
 
 
 
struct rtl_opt_pass pass_df_initialize_no_opt =
struct rtl_opt_pass pass_df_initialize_no_opt =
{
{
 {
 {
  RTL_PASS,
  RTL_PASS,
  "no-opt dfinit",                      /* name */
  "no-opt dfinit",                      /* name */
  gate_no_opt,                          /* gate */
  gate_no_opt,                          /* gate */
  rest_of_handle_df_initialize,         /* execute */
  rest_of_handle_df_initialize,         /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  0,                                    /* static_pass_number */
  TV_NONE,                              /* tv_id */
  TV_NONE,                              /* tv_id */
  0,                                    /* properties_required */
  0,                                    /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  0,                                    /* properties_destroyed */
  0,                                    /* todo_flags_start */
  0,                                    /* todo_flags_start */
  0                                     /* todo_flags_finish */
  0                                     /* todo_flags_finish */
 }
 }
};
};
 
 
 
 
/* Free all the dataflow info and the DF structure.  This should be
/* Free all the dataflow info and the DF structure.  This should be
   called from the df_finish macro which also NULLs the parm.  */
   called from the df_finish macro which also NULLs the parm.  */
 
 
static unsigned int
static unsigned int
rest_of_handle_df_finish (void)
rest_of_handle_df_finish (void)
{
{
  int i;
  int i;
 
 
  gcc_assert (df);
  gcc_assert (df);
 
 
  for (i = 0; i < df->num_problems_defined; i++)
  for (i = 0; i < df->num_problems_defined; i++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[i];
      struct dataflow *dflow = df->problems_in_order[i];
      dflow->problem->free_fun ();
      dflow->problem->free_fun ();
    }
    }
 
 
  if (df->postorder)
  if (df->postorder)
    free (df->postorder);
    free (df->postorder);
  if (df->postorder_inverted)
  if (df->postorder_inverted)
    free (df->postorder_inverted);
    free (df->postorder_inverted);
  free (df->hard_regs_live_count);
  free (df->hard_regs_live_count);
  free (df);
  free (df);
  df = NULL;
  df = NULL;
 
 
  bitmap_obstack_release (&df_bitmap_obstack);
  bitmap_obstack_release (&df_bitmap_obstack);
  return 0;
  return 0;
}
}
 
 
 
 
struct rtl_opt_pass pass_df_finish =
struct rtl_opt_pass pass_df_finish =
{
{
 {
 {
  RTL_PASS,
  RTL_PASS,
  "dfinish",                            /* name */
  "dfinish",                            /* name */
  NULL,                                 /* gate */
  NULL,                                 /* gate */
  rest_of_handle_df_finish,             /* execute */
  rest_of_handle_df_finish,             /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  0,                                    /* static_pass_number */
  TV_NONE,                              /* tv_id */
  TV_NONE,                              /* tv_id */
  0,                                    /* properties_required */
  0,                                    /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  0,                                    /* properties_destroyed */
  0,                                    /* todo_flags_start */
  0,                                    /* todo_flags_start */
  0                                     /* todo_flags_finish */
  0                                     /* todo_flags_finish */
 }
 }
};
};
 
 
 
 
 
 
 
 


/*----------------------------------------------------------------------------
/*----------------------------------------------------------------------------
   The general data flow analysis engine.
   The general data flow analysis engine.
----------------------------------------------------------------------------*/
----------------------------------------------------------------------------*/
 
 
 
 
/* Helper function for df_worklist_dataflow.
/* Helper function for df_worklist_dataflow.
   Propagate the dataflow forward.
   Propagate the dataflow forward.
   Given a BB_INDEX, do the dataflow propagation
   Given a BB_INDEX, do the dataflow propagation
   and set bits on for successors in PENDING
   and set bits on for successors in PENDING
   if the out set of the dataflow has changed. */
   if the out set of the dataflow has changed. */
 
 
static void
static void
df_worklist_propagate_forward (struct dataflow *dataflow,
df_worklist_propagate_forward (struct dataflow *dataflow,
                               unsigned bb_index,
                               unsigned bb_index,
                               unsigned *bbindex_to_postorder,
                               unsigned *bbindex_to_postorder,
                               bitmap pending,
                               bitmap pending,
                               sbitmap considered)
                               sbitmap considered)
{
{
  edge e;
  edge e;
  edge_iterator ei;
  edge_iterator ei;
  basic_block bb = BASIC_BLOCK (bb_index);
  basic_block bb = BASIC_BLOCK (bb_index);
 
 
  /*  Calculate <conf_op> of incoming edges.  */
  /*  Calculate <conf_op> of incoming edges.  */
  if (EDGE_COUNT (bb->preds) > 0)
  if (EDGE_COUNT (bb->preds) > 0)
    FOR_EACH_EDGE (e, ei, bb->preds)
    FOR_EACH_EDGE (e, ei, bb->preds)
      {
      {
        if (TEST_BIT (considered, e->src->index))
        if (TEST_BIT (considered, e->src->index))
          dataflow->problem->con_fun_n (e);
          dataflow->problem->con_fun_n (e);
      }
      }
  else if (dataflow->problem->con_fun_0)
  else if (dataflow->problem->con_fun_0)
    dataflow->problem->con_fun_0 (bb);
    dataflow->problem->con_fun_0 (bb);
 
 
  if (dataflow->problem->trans_fun (bb_index))
  if (dataflow->problem->trans_fun (bb_index))
    {
    {
      /* The out set of this block has changed.
      /* The out set of this block has changed.
         Propagate to the outgoing blocks.  */
         Propagate to the outgoing blocks.  */
      FOR_EACH_EDGE (e, ei, bb->succs)
      FOR_EACH_EDGE (e, ei, bb->succs)
        {
        {
          unsigned ob_index = e->dest->index;
          unsigned ob_index = e->dest->index;
 
 
          if (TEST_BIT (considered, ob_index))
          if (TEST_BIT (considered, ob_index))
            bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
            bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
        }
        }
    }
    }
}
}
 
 
 
 
/* Helper function for df_worklist_dataflow.
/* Helper function for df_worklist_dataflow.
   Propagate the dataflow backward.  */
   Propagate the dataflow backward.  */
 
 
static void
static void
df_worklist_propagate_backward (struct dataflow *dataflow,
df_worklist_propagate_backward (struct dataflow *dataflow,
                                unsigned bb_index,
                                unsigned bb_index,
                                unsigned *bbindex_to_postorder,
                                unsigned *bbindex_to_postorder,
                                bitmap pending,
                                bitmap pending,
                                sbitmap considered)
                                sbitmap considered)
{
{
  edge e;
  edge e;
  edge_iterator ei;
  edge_iterator ei;
  basic_block bb = BASIC_BLOCK (bb_index);
  basic_block bb = BASIC_BLOCK (bb_index);
 
 
  /*  Calculate <conf_op> of incoming edges.  */
  /*  Calculate <conf_op> of incoming edges.  */
  if (EDGE_COUNT (bb->succs) > 0)
  if (EDGE_COUNT (bb->succs) > 0)
    FOR_EACH_EDGE (e, ei, bb->succs)
    FOR_EACH_EDGE (e, ei, bb->succs)
      {
      {
        if (TEST_BIT (considered, e->dest->index))
        if (TEST_BIT (considered, e->dest->index))
          dataflow->problem->con_fun_n (e);
          dataflow->problem->con_fun_n (e);
      }
      }
  else if (dataflow->problem->con_fun_0)
  else if (dataflow->problem->con_fun_0)
    dataflow->problem->con_fun_0 (bb);
    dataflow->problem->con_fun_0 (bb);
 
 
  if (dataflow->problem->trans_fun (bb_index))
  if (dataflow->problem->trans_fun (bb_index))
    {
    {
      /* The out set of this block has changed.
      /* The out set of this block has changed.
         Propagate to the outgoing blocks.  */
         Propagate to the outgoing blocks.  */
      FOR_EACH_EDGE (e, ei, bb->preds)
      FOR_EACH_EDGE (e, ei, bb->preds)
        {
        {
          unsigned ob_index = e->src->index;
          unsigned ob_index = e->src->index;
 
 
          if (TEST_BIT (considered, ob_index))
          if (TEST_BIT (considered, ob_index))
            bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
            bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
        }
        }
    }
    }
}
}
 
 
 
 
 
 
/* This will free "pending". */
/* This will free "pending". */
 
 
static void
static void
df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
                                  bitmap pending,
                                  bitmap pending,
                                  sbitmap considered,
                                  sbitmap considered,
                                  int *blocks_in_postorder,
                                  int *blocks_in_postorder,
                                  unsigned *bbindex_to_postorder)
                                  unsigned *bbindex_to_postorder)
{
{
  enum df_flow_dir dir = dataflow->problem->dir;
  enum df_flow_dir dir = dataflow->problem->dir;
  int dcount = 0;
  int dcount = 0;
  bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
  bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
 
 
  /* Double-queueing. Worklist is for the current iteration,
  /* Double-queueing. Worklist is for the current iteration,
     and pending is for the next. */
     and pending is for the next. */
  while (!bitmap_empty_p (pending))
  while (!bitmap_empty_p (pending))
    {
    {
      /* Swap pending and worklist. */
      /* Swap pending and worklist. */
      bitmap temp = worklist;
      bitmap temp = worklist;
      worklist = pending;
      worklist = pending;
      pending = temp;
      pending = temp;
 
 
      do
      do
        {
        {
          int index;
          int index;
          unsigned bb_index;
          unsigned bb_index;
          dcount++;
          dcount++;
 
 
          index = bitmap_first_set_bit (worklist);
          index = bitmap_first_set_bit (worklist);
          bitmap_clear_bit (worklist, index);
          bitmap_clear_bit (worklist, index);
 
 
          bb_index = blocks_in_postorder[index];
          bb_index = blocks_in_postorder[index];
 
 
          if (dir == DF_FORWARD)
          if (dir == DF_FORWARD)
            df_worklist_propagate_forward (dataflow, bb_index,
            df_worklist_propagate_forward (dataflow, bb_index,
                                           bbindex_to_postorder,
                                           bbindex_to_postorder,
                                           pending, considered);
                                           pending, considered);
          else
          else
            df_worklist_propagate_backward (dataflow, bb_index,
            df_worklist_propagate_backward (dataflow, bb_index,
                                            bbindex_to_postorder,
                                            bbindex_to_postorder,
                                            pending, considered);
                                            pending, considered);
        }
        }
      while (!bitmap_empty_p (worklist));
      while (!bitmap_empty_p (worklist));
    }
    }
 
 
  BITMAP_FREE (worklist);
  BITMAP_FREE (worklist);
  BITMAP_FREE (pending);
  BITMAP_FREE (pending);
 
 
  /* Dump statistics. */
  /* Dump statistics. */
  if (dump_file)
  if (dump_file)
    fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
    fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
             "n_basic_blocks %d n_edges %d"
             "n_basic_blocks %d n_edges %d"
             " count %d (%5.2g)\n",
             " count %d (%5.2g)\n",
             n_basic_blocks, n_edges,
             n_basic_blocks, n_edges,
             dcount, dcount / (float)n_basic_blocks);
             dcount, dcount / (float)n_basic_blocks);
}
}
 
 
/* Worklist-based dataflow solver. It uses sbitmap as a worklist,
/* Worklist-based dataflow solver. It uses sbitmap as a worklist,
   with "n"-th bit representing the n-th block in the reverse-postorder order.
   with "n"-th bit representing the n-th block in the reverse-postorder order.
   The solver is a double-queue algorithm similar to the "double stack" solver
   The solver is a double-queue algorithm similar to the "double stack" solver
   from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
   from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
   The only significant difference is that the worklist in this implementation
   The only significant difference is that the worklist in this implementation
   is always sorted in RPO of the CFG visiting direction.  */
   is always sorted in RPO of the CFG visiting direction.  */
 
 
void
void
df_worklist_dataflow (struct dataflow *dataflow,
df_worklist_dataflow (struct dataflow *dataflow,
                      bitmap blocks_to_consider,
                      bitmap blocks_to_consider,
                      int *blocks_in_postorder,
                      int *blocks_in_postorder,
                      int n_blocks)
                      int n_blocks)
{
{
  bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
  bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
  sbitmap considered = sbitmap_alloc (last_basic_block);
  sbitmap considered = sbitmap_alloc (last_basic_block);
  bitmap_iterator bi;
  bitmap_iterator bi;
  unsigned int *bbindex_to_postorder;
  unsigned int *bbindex_to_postorder;
  int i;
  int i;
  unsigned int index;
  unsigned int index;
  enum df_flow_dir dir = dataflow->problem->dir;
  enum df_flow_dir dir = dataflow->problem->dir;
 
 
  gcc_assert (dir != DF_NONE);
  gcc_assert (dir != DF_NONE);
 
 
  /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder.  */
  /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder.  */
  bbindex_to_postorder =
  bbindex_to_postorder =
    (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
    (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
 
 
  /* Initialize the array to an out-of-bound value.  */
  /* Initialize the array to an out-of-bound value.  */
  for (i = 0; i < last_basic_block; i++)
  for (i = 0; i < last_basic_block; i++)
    bbindex_to_postorder[i] = last_basic_block;
    bbindex_to_postorder[i] = last_basic_block;
 
 
  /* Initialize the considered map.  */
  /* Initialize the considered map.  */
  sbitmap_zero (considered);
  sbitmap_zero (considered);
  EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
  EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
    {
    {
      SET_BIT (considered, index);
      SET_BIT (considered, index);
    }
    }
 
 
  /* Initialize the mapping of block index to postorder.  */
  /* Initialize the mapping of block index to postorder.  */
  for (i = 0; i < n_blocks; i++)
  for (i = 0; i < n_blocks; i++)
    {
    {
      bbindex_to_postorder[blocks_in_postorder[i]] = i;
      bbindex_to_postorder[blocks_in_postorder[i]] = i;
      /* Add all blocks to the worklist.  */
      /* Add all blocks to the worklist.  */
      bitmap_set_bit (pending, i);
      bitmap_set_bit (pending, i);
    }
    }
 
 
  /* Initialize the problem. */
  /* Initialize the problem. */
  if (dataflow->problem->init_fun)
  if (dataflow->problem->init_fun)
    dataflow->problem->init_fun (blocks_to_consider);
    dataflow->problem->init_fun (blocks_to_consider);
 
 
  /* Solve it.  */
  /* Solve it.  */
  df_worklist_dataflow_doublequeue (dataflow, pending, considered,
  df_worklist_dataflow_doublequeue (dataflow, pending, considered,
                                    blocks_in_postorder,
                                    blocks_in_postorder,
                                    bbindex_to_postorder);
                                    bbindex_to_postorder);
 
 
  sbitmap_free (considered);
  sbitmap_free (considered);
  free (bbindex_to_postorder);
  free (bbindex_to_postorder);
}
}
 
 
 
 
/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
/* 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
   the order of the remaining entries.  Returns the length of the resulting
   list.  */
   list.  */
 
 
static unsigned
static unsigned
df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
{
{
  unsigned act, last;
  unsigned act, last;
 
 
  for (act = 0, last = 0; act < len; act++)
  for (act = 0, last = 0; act < len; act++)
    if (bitmap_bit_p (blocks, list[act]))
    if (bitmap_bit_p (blocks, list[act]))
      list[last++] = list[act];
      list[last++] = list[act];
 
 
  return last;
  return last;
}
}
 
 
 
 
/* Execute dataflow analysis on a single dataflow problem.
/* Execute dataflow analysis on a single dataflow problem.
 
 
   BLOCKS_TO_CONSIDER are the blocks whose solution can either be
   BLOCKS_TO_CONSIDER are the blocks whose solution can either be
   examined or will be computed.  For calls from DF_ANALYZE, this is
   examined or will be computed.  For calls from DF_ANALYZE, this is
   the set of blocks that has been passed to DF_SET_BLOCKS.
   the set of blocks that has been passed to DF_SET_BLOCKS.
*/
*/
 
 
void
void
df_analyze_problem (struct dataflow *dflow,
df_analyze_problem (struct dataflow *dflow,
                    bitmap blocks_to_consider,
                    bitmap blocks_to_consider,
                    int *postorder, int n_blocks)
                    int *postorder, int n_blocks)
{
{
  timevar_push (dflow->problem->tv_id);
  timevar_push (dflow->problem->tv_id);
 
 
#ifdef ENABLE_DF_CHECKING
#ifdef ENABLE_DF_CHECKING
  if (dflow->problem->verify_start_fun)
  if (dflow->problem->verify_start_fun)
    dflow->problem->verify_start_fun ();
    dflow->problem->verify_start_fun ();
#endif
#endif
 
 
  /* (Re)Allocate the datastructures necessary to solve the problem.  */
  /* (Re)Allocate the datastructures necessary to solve the problem.  */
  if (dflow->problem->alloc_fun)
  if (dflow->problem->alloc_fun)
    dflow->problem->alloc_fun (blocks_to_consider);
    dflow->problem->alloc_fun (blocks_to_consider);
 
 
  /* Set up the problem and compute the local information.  */
  /* Set up the problem and compute the local information.  */
  if (dflow->problem->local_compute_fun)
  if (dflow->problem->local_compute_fun)
    dflow->problem->local_compute_fun (blocks_to_consider);
    dflow->problem->local_compute_fun (blocks_to_consider);
 
 
  /* Solve the equations.  */
  /* Solve the equations.  */
  if (dflow->problem->dataflow_fun)
  if (dflow->problem->dataflow_fun)
    dflow->problem->dataflow_fun (dflow, blocks_to_consider,
    dflow->problem->dataflow_fun (dflow, blocks_to_consider,
                                  postorder, n_blocks);
                                  postorder, n_blocks);
 
 
  /* Massage the solution.  */
  /* Massage the solution.  */
  if (dflow->problem->finalize_fun)
  if (dflow->problem->finalize_fun)
    dflow->problem->finalize_fun (blocks_to_consider);
    dflow->problem->finalize_fun (blocks_to_consider);
 
 
#ifdef ENABLE_DF_CHECKING
#ifdef ENABLE_DF_CHECKING
  if (dflow->problem->verify_end_fun)
  if (dflow->problem->verify_end_fun)
    dflow->problem->verify_end_fun ();
    dflow->problem->verify_end_fun ();
#endif
#endif
 
 
  timevar_pop (dflow->problem->tv_id);
  timevar_pop (dflow->problem->tv_id);
 
 
  dflow->computed = true;
  dflow->computed = true;
}
}
 
 
 
 
/* Analyze dataflow info for the basic blocks specified by the bitmap
/* Analyze dataflow info for the basic blocks specified by the bitmap
   BLOCKS, or for the whole CFG if BLOCKS is zero.  */
   BLOCKS, or for the whole CFG if BLOCKS is zero.  */
 
 
void
void
df_analyze (void)
df_analyze (void)
{
{
  bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
  bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
  bool everything;
  bool everything;
  int i;
  int i;
 
 
  if (df->postorder)
  if (df->postorder)
    free (df->postorder);
    free (df->postorder);
  if (df->postorder_inverted)
  if (df->postorder_inverted)
    free (df->postorder_inverted);
    free (df->postorder_inverted);
  df->postorder = XNEWVEC (int, last_basic_block);
  df->postorder = XNEWVEC (int, last_basic_block);
  df->postorder_inverted = 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 = post_order_compute (df->postorder, true, true);
  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
 
 
  /* These should be the same.  */
  /* These should be the same.  */
  gcc_assert (df->n_blocks == df->n_blocks_inverted);
  gcc_assert (df->n_blocks == df->n_blocks_inverted);
 
 
  /* We need to do this before the df_verify_all because this is
  /* We need to do this before the df_verify_all because this is
     not kept incrementally up to date.  */
     not kept incrementally up to date.  */
  df_compute_regs_ever_live (false);
  df_compute_regs_ever_live (false);
  df_process_deferred_rescans ();
  df_process_deferred_rescans ();
 
 
  if (dump_file)
  if (dump_file)
    fprintf (dump_file, "df_analyze called\n");
    fprintf (dump_file, "df_analyze called\n");
 
 
#ifndef ENABLE_DF_CHECKING
#ifndef ENABLE_DF_CHECKING
  if (df->changeable_flags & DF_VERIFY_SCHEDULED)
  if (df->changeable_flags & DF_VERIFY_SCHEDULED)
#endif
#endif
    df_verify ();
    df_verify ();
 
 
  for (i = 0; i < df->n_blocks; i++)
  for (i = 0; i < df->n_blocks; i++)
    bitmap_set_bit (current_all_blocks, df->postorder[i]);
    bitmap_set_bit (current_all_blocks, df->postorder[i]);
 
 
#ifdef ENABLE_CHECKING
#ifdef ENABLE_CHECKING
  /* Verify that POSTORDER_INVERTED only contains blocks reachable from
  /* Verify that POSTORDER_INVERTED only contains blocks reachable from
     the ENTRY block.  */
     the ENTRY block.  */
  for (i = 0; i < df->n_blocks_inverted; i++)
  for (i = 0; i < df->n_blocks_inverted; i++)
    gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
    gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
#endif
#endif
 
 
  /* Make sure that we have pruned any unreachable blocks from these
  /* Make sure that we have pruned any unreachable blocks from these
     sets.  */
     sets.  */
  if (df->analyze_subset)
  if (df->analyze_subset)
    {
    {
      everything = false;
      everything = false;
      bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
      bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
      df->n_blocks = df_prune_to_subcfg (df->postorder,
      df->n_blocks = df_prune_to_subcfg (df->postorder,
                                         df->n_blocks, df->blocks_to_analyze);
                                         df->n_blocks, df->blocks_to_analyze);
      df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
      df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
                                                  df->n_blocks_inverted,
                                                  df->n_blocks_inverted,
                                                  df->blocks_to_analyze);
                                                  df->blocks_to_analyze);
      BITMAP_FREE (current_all_blocks);
      BITMAP_FREE (current_all_blocks);
    }
    }
  else
  else
    {
    {
      everything = true;
      everything = true;
      df->blocks_to_analyze = current_all_blocks;
      df->blocks_to_analyze = current_all_blocks;
      current_all_blocks = NULL;
      current_all_blocks = NULL;
    }
    }
 
 
  /* Skip over the DF_SCAN problem. */
  /* Skip over the DF_SCAN problem. */
  for (i = 1; i < df->num_problems_defined; i++)
  for (i = 1; i < df->num_problems_defined; i++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[i];
      struct dataflow *dflow = df->problems_in_order[i];
      if (dflow->solutions_dirty)
      if (dflow->solutions_dirty)
        {
        {
          if (dflow->problem->dir == DF_FORWARD)
          if (dflow->problem->dir == DF_FORWARD)
            df_analyze_problem (dflow,
            df_analyze_problem (dflow,
                                df->blocks_to_analyze,
                                df->blocks_to_analyze,
                                df->postorder_inverted,
                                df->postorder_inverted,
                                df->n_blocks_inverted);
                                df->n_blocks_inverted);
          else
          else
            df_analyze_problem (dflow,
            df_analyze_problem (dflow,
                                df->blocks_to_analyze,
                                df->blocks_to_analyze,
                                df->postorder,
                                df->postorder,
                                df->n_blocks);
                                df->n_blocks);
        }
        }
    }
    }
 
 
  if (everything)
  if (everything)
    {
    {
      BITMAP_FREE (df->blocks_to_analyze);
      BITMAP_FREE (df->blocks_to_analyze);
      df->blocks_to_analyze = NULL;
      df->blocks_to_analyze = NULL;
    }
    }
 
 
#ifdef DF_DEBUG_CFG
#ifdef DF_DEBUG_CFG
  df_set_clean_cfg ();
  df_set_clean_cfg ();
#endif
#endif
}
}
 
 
 
 
/* Return the number of basic blocks from the last call to df_analyze.  */
/* Return the number of basic blocks from the last call to df_analyze.  */
 
 
int
int
df_get_n_blocks (enum df_flow_dir dir)
df_get_n_blocks (enum df_flow_dir dir)
{
{
  gcc_assert (dir != DF_NONE);
  gcc_assert (dir != DF_NONE);
 
 
  if (dir == DF_FORWARD)
  if (dir == DF_FORWARD)
    {
    {
      gcc_assert (df->postorder_inverted);
      gcc_assert (df->postorder_inverted);
      return df->n_blocks_inverted;
      return df->n_blocks_inverted;
    }
    }
 
 
  gcc_assert (df->postorder);
  gcc_assert (df->postorder);
  return df->n_blocks;
  return df->n_blocks;
}
}
 
 
 
 
/* Return a pointer to the array of basic blocks in the reverse postorder.
/* Return a pointer to the array of basic blocks in the reverse postorder.
   Depending on the direction of the dataflow problem,
   Depending on the direction of the dataflow problem,
   it returns either the usual reverse postorder array
   it returns either the usual reverse postorder array
   or the reverse postorder of inverted traversal. */
   or the reverse postorder of inverted traversal. */
int *
int *
df_get_postorder (enum df_flow_dir dir)
df_get_postorder (enum df_flow_dir dir)
{
{
  gcc_assert (dir != DF_NONE);
  gcc_assert (dir != DF_NONE);
 
 
  if (dir == DF_FORWARD)
  if (dir == DF_FORWARD)
    {
    {
      gcc_assert (df->postorder_inverted);
      gcc_assert (df->postorder_inverted);
      return df->postorder_inverted;
      return df->postorder_inverted;
    }
    }
  gcc_assert (df->postorder);
  gcc_assert (df->postorder);
  return df->postorder;
  return df->postorder;
}
}
 
 
static struct df_problem user_problem;
static struct df_problem user_problem;
static struct dataflow user_dflow;
static struct dataflow user_dflow;
 
 
/* Interface for calling iterative dataflow with user defined
/* Interface for calling iterative dataflow with user defined
   confluence and transfer functions.  All that is necessary is to
   confluence and transfer functions.  All that is necessary is to
   supply DIR, a direction, CONF_FUN_0, a confluence function for
   supply DIR, a direction, CONF_FUN_0, a confluence function for
   blocks with no logical preds (or NULL), CONF_FUN_N, the normal
   blocks with no logical preds (or NULL), CONF_FUN_N, the normal
   confluence function, TRANS_FUN, the basic block transfer function,
   confluence function, TRANS_FUN, the basic block transfer function,
   and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
   and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
   postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
   postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
 
 
void
void
df_simple_dataflow (enum df_flow_dir dir,
df_simple_dataflow (enum df_flow_dir dir,
                    df_init_function init_fun,
                    df_init_function init_fun,
                    df_confluence_function_0 con_fun_0,
                    df_confluence_function_0 con_fun_0,
                    df_confluence_function_n con_fun_n,
                    df_confluence_function_n con_fun_n,
                    df_transfer_function trans_fun,
                    df_transfer_function trans_fun,
                    bitmap blocks, int * postorder, int n_blocks)
                    bitmap blocks, int * postorder, int n_blocks)
{
{
  memset (&user_problem, 0, sizeof (struct df_problem));
  memset (&user_problem, 0, sizeof (struct df_problem));
  user_problem.dir = dir;
  user_problem.dir = dir;
  user_problem.init_fun = init_fun;
  user_problem.init_fun = init_fun;
  user_problem.con_fun_0 = con_fun_0;
  user_problem.con_fun_0 = con_fun_0;
  user_problem.con_fun_n = con_fun_n;
  user_problem.con_fun_n = con_fun_n;
  user_problem.trans_fun = trans_fun;
  user_problem.trans_fun = trans_fun;
  user_dflow.problem = &user_problem;
  user_dflow.problem = &user_problem;
  df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
  df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
}
}
 
 
 
 


/*----------------------------------------------------------------------------
/*----------------------------------------------------------------------------
   Functions to support limited incremental change.
   Functions to support limited incremental change.
----------------------------------------------------------------------------*/
----------------------------------------------------------------------------*/
 
 
 
 
/* Get basic block info.  */
/* Get basic block info.  */
 
 
static void *
static void *
df_get_bb_info (struct dataflow *dflow, unsigned int index)
df_get_bb_info (struct dataflow *dflow, unsigned int index)
{
{
  if (dflow->block_info == NULL)
  if (dflow->block_info == NULL)
    return NULL;
    return NULL;
  if (index >= dflow->block_info_size)
  if (index >= dflow->block_info_size)
    return NULL;
    return NULL;
  return (struct df_scan_bb_info *) dflow->block_info[index];
  return (struct df_scan_bb_info *) dflow->block_info[index];
}
}
 
 
 
 
/* Set basic block info.  */
/* Set basic block info.  */
 
 
static void
static void
df_set_bb_info (struct dataflow *dflow, unsigned int index,
df_set_bb_info (struct dataflow *dflow, unsigned int index,
                void *bb_info)
                void *bb_info)
{
{
  gcc_assert (dflow->block_info);
  gcc_assert (dflow->block_info);
  dflow->block_info[index] = bb_info;
  dflow->block_info[index] = bb_info;
}
}
 
 
 
 
/* Mark the solutions as being out of date.  */
/* Mark the solutions as being out of date.  */
 
 
void
void
df_mark_solutions_dirty (void)
df_mark_solutions_dirty (void)
{
{
  if (df)
  if (df)
    {
    {
      int p;
      int p;
      for (p = 1; p < df->num_problems_defined; p++)
      for (p = 1; p < df->num_problems_defined; p++)
        df->problems_in_order[p]->solutions_dirty = true;
        df->problems_in_order[p]->solutions_dirty = true;
    }
    }
}
}
 
 
 
 
/* Return true if BB needs it's transfer functions recomputed.  */
/* Return true if BB needs it's transfer functions recomputed.  */
 
 
bool
bool
df_get_bb_dirty (basic_block bb)
df_get_bb_dirty (basic_block bb)
{
{
  if (df && df_live)
  if (df && df_live)
    return bitmap_bit_p (df_live->out_of_date_transfer_functions, bb->index);
    return bitmap_bit_p (df_live->out_of_date_transfer_functions, bb->index);
  else
  else
    return false;
    return false;
}
}
 
 
 
 
/* Mark BB as needing it's transfer functions as being out of
/* Mark BB as needing it's transfer functions as being out of
   date.  */
   date.  */
 
 
void
void
df_set_bb_dirty (basic_block bb)
df_set_bb_dirty (basic_block bb)
{
{
  if (df)
  if (df)
    {
    {
      int p;
      int p;
      for (p = 1; p < df->num_problems_defined; p++)
      for (p = 1; p < df->num_problems_defined; p++)
        {
        {
          struct dataflow *dflow = df->problems_in_order[p];
          struct dataflow *dflow = df->problems_in_order[p];
          if (dflow->out_of_date_transfer_functions)
          if (dflow->out_of_date_transfer_functions)
            bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
            bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
        }
        }
      df_mark_solutions_dirty ();
      df_mark_solutions_dirty ();
    }
    }
}
}
 
 
 
 
/* Mark BB as needing it's transfer functions as being out of
/* Mark BB as needing it's transfer functions as being out of
   date, except for LR problem.  Used when analyzing DEBUG_INSNs,
   date, except for LR problem.  Used when analyzing DEBUG_INSNs,
   as LR problem can trigger DCE, and DEBUG_INSNs shouldn't ever
   as LR problem can trigger DCE, and DEBUG_INSNs shouldn't ever
   shorten or enlarge lifetime of regs.  */
   shorten or enlarge lifetime of regs.  */
 
 
void
void
df_set_bb_dirty_nonlr (basic_block bb)
df_set_bb_dirty_nonlr (basic_block bb)
{
{
  if (df)
  if (df)
    {
    {
      int p;
      int p;
      for (p = 1; p < df->num_problems_defined; p++)
      for (p = 1; p < df->num_problems_defined; p++)
        {
        {
          struct dataflow *dflow = df->problems_in_order[p];
          struct dataflow *dflow = df->problems_in_order[p];
          if (dflow == df_lr)
          if (dflow == df_lr)
            continue;
            continue;
          if (dflow->out_of_date_transfer_functions)
          if (dflow->out_of_date_transfer_functions)
            bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
            bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
          dflow->solutions_dirty = true;
          dflow->solutions_dirty = true;
        }
        }
    }
    }
}
}
 
 
 
 
/* Clear the dirty bits.  This is called from places that delete
/* Clear the dirty bits.  This is called from places that delete
   blocks.  */
   blocks.  */
static void
static void
df_clear_bb_dirty (basic_block bb)
df_clear_bb_dirty (basic_block bb)
{
{
  int p;
  int p;
  for (p = 1; p < df->num_problems_defined; p++)
  for (p = 1; p < df->num_problems_defined; p++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[p];
      struct dataflow *dflow = df->problems_in_order[p];
      if (dflow->out_of_date_transfer_functions)
      if (dflow->out_of_date_transfer_functions)
        bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
        bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
    }
    }
}
}
/* Called from the rtl_compact_blocks to reorganize the problems basic
/* Called from the rtl_compact_blocks to reorganize the problems basic
   block info.  */
   block info.  */
 
 
void
void
df_compact_blocks (void)
df_compact_blocks (void)
{
{
  int i, p;
  int i, p;
  basic_block bb;
  basic_block bb;
  void **problem_temps;
  void **problem_temps;
  int size = last_basic_block * sizeof (void *);
  int size = last_basic_block * sizeof (void *);
  bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
  bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
  problem_temps = XNEWVAR (void *, size);
  problem_temps = XNEWVAR (void *, size);
 
 
  for (p = 0; p < df->num_problems_defined; p++)
  for (p = 0; p < df->num_problems_defined; p++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[p];
      struct dataflow *dflow = df->problems_in_order[p];
 
 
      /* Need to reorganize the out_of_date_transfer_functions for the
      /* Need to reorganize the out_of_date_transfer_functions for the
         dflow problem.  */
         dflow problem.  */
      if (dflow->out_of_date_transfer_functions)
      if (dflow->out_of_date_transfer_functions)
        {
        {
          bitmap_copy (tmp, dflow->out_of_date_transfer_functions);
          bitmap_copy (tmp, dflow->out_of_date_transfer_functions);
          bitmap_clear (dflow->out_of_date_transfer_functions);
          bitmap_clear (dflow->out_of_date_transfer_functions);
          if (bitmap_bit_p (tmp, ENTRY_BLOCK))
          if (bitmap_bit_p (tmp, ENTRY_BLOCK))
            bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
            bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
          if (bitmap_bit_p (tmp, EXIT_BLOCK))
          if (bitmap_bit_p (tmp, EXIT_BLOCK))
            bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
            bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
 
 
          i = NUM_FIXED_BLOCKS;
          i = NUM_FIXED_BLOCKS;
          FOR_EACH_BB (bb)
          FOR_EACH_BB (bb)
            {
            {
              if (bitmap_bit_p (tmp, bb->index))
              if (bitmap_bit_p (tmp, bb->index))
                bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
                bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
              i++;
              i++;
            }
            }
        }
        }
 
 
      /* Now shuffle the block info for the problem.  */
      /* Now shuffle the block info for the problem.  */
      if (dflow->problem->free_bb_fun)
      if (dflow->problem->free_bb_fun)
        {
        {
          df_grow_bb_info (dflow);
          df_grow_bb_info (dflow);
          memcpy (problem_temps, dflow->block_info, size);
          memcpy (problem_temps, dflow->block_info, size);
 
 
          /* Copy the bb info from the problem tmps to the proper
          /* Copy the bb info from the problem tmps to the proper
             place in the block_info vector.  Null out the copied
             place in the block_info vector.  Null out the copied
             item.  The entry and exit blocks never move.  */
             item.  The entry and exit blocks never move.  */
          i = NUM_FIXED_BLOCKS;
          i = NUM_FIXED_BLOCKS;
          FOR_EACH_BB (bb)
          FOR_EACH_BB (bb)
            {
            {
              df_set_bb_info (dflow, i, problem_temps[bb->index]);
              df_set_bb_info (dflow, i, problem_temps[bb->index]);
              problem_temps[bb->index] = NULL;
              problem_temps[bb->index] = NULL;
              i++;
              i++;
            }
            }
          memset (dflow->block_info + i, 0,
          memset (dflow->block_info + i, 0,
                  (last_basic_block - i) *sizeof (void *));
                  (last_basic_block - i) *sizeof (void *));
 
 
          /* Free any block infos that were not copied (and NULLed).
          /* Free any block infos that were not copied (and NULLed).
             These are from orphaned blocks.  */
             These are from orphaned blocks.  */
          for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
          for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
            {
            {
              basic_block bb = BASIC_BLOCK (i);
              basic_block bb = BASIC_BLOCK (i);
              if (problem_temps[i] && bb)
              if (problem_temps[i] && bb)
                dflow->problem->free_bb_fun
                dflow->problem->free_bb_fun
                  (bb, problem_temps[i]);
                  (bb, problem_temps[i]);
            }
            }
        }
        }
    }
    }
 
 
  /* Shuffle the bits in the basic_block indexed arrays.  */
  /* Shuffle the bits in the basic_block indexed arrays.  */
 
 
  if (df->blocks_to_analyze)
  if (df->blocks_to_analyze)
    {
    {
      if (bitmap_bit_p (tmp, ENTRY_BLOCK))
      if (bitmap_bit_p (tmp, ENTRY_BLOCK))
        bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
        bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
      if (bitmap_bit_p (tmp, EXIT_BLOCK))
      if (bitmap_bit_p (tmp, EXIT_BLOCK))
        bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
        bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
      bitmap_copy (tmp, df->blocks_to_analyze);
      bitmap_copy (tmp, df->blocks_to_analyze);
      bitmap_clear (df->blocks_to_analyze);
      bitmap_clear (df->blocks_to_analyze);
      i = NUM_FIXED_BLOCKS;
      i = NUM_FIXED_BLOCKS;
      FOR_EACH_BB (bb)
      FOR_EACH_BB (bb)
        {
        {
          if (bitmap_bit_p (tmp, bb->index))
          if (bitmap_bit_p (tmp, bb->index))
            bitmap_set_bit (df->blocks_to_analyze, i);
            bitmap_set_bit (df->blocks_to_analyze, i);
          i++;
          i++;
        }
        }
    }
    }
 
 
  BITMAP_FREE (tmp);
  BITMAP_FREE (tmp);
 
 
  free (problem_temps);
  free (problem_temps);
 
 
  i = NUM_FIXED_BLOCKS;
  i = NUM_FIXED_BLOCKS;
  FOR_EACH_BB (bb)
  FOR_EACH_BB (bb)
    {
    {
      SET_BASIC_BLOCK (i, bb);
      SET_BASIC_BLOCK (i, bb);
      bb->index = i;
      bb->index = i;
      i++;
      i++;
    }
    }
 
 
  gcc_assert (i == n_basic_blocks);
  gcc_assert (i == n_basic_blocks);
 
 
  for (; i < last_basic_block; i++)
  for (; i < last_basic_block; i++)
    SET_BASIC_BLOCK (i, NULL);
    SET_BASIC_BLOCK (i, NULL);
 
 
#ifdef DF_DEBUG_CFG
#ifdef DF_DEBUG_CFG
  if (!df_lr->solutions_dirty)
  if (!df_lr->solutions_dirty)
    df_set_clean_cfg ();
    df_set_clean_cfg ();
#endif
#endif
}
}
 
 
 
 
/* Shove NEW_BLOCK in at OLD_INDEX.  Called from ifcvt to hack a
/* Shove NEW_BLOCK in at OLD_INDEX.  Called from ifcvt to hack a
   block.  There is no excuse for people to do this kind of thing.  */
   block.  There is no excuse for people to do this kind of thing.  */
 
 
void
void
df_bb_replace (int old_index, basic_block new_block)
df_bb_replace (int old_index, basic_block new_block)
{
{
  int new_block_index = new_block->index;
  int new_block_index = new_block->index;
  int p;
  int p;
 
 
  if (dump_file)
  if (dump_file)
    fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
    fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
 
 
  gcc_assert (df);
  gcc_assert (df);
  gcc_assert (BASIC_BLOCK (old_index) == NULL);
  gcc_assert (BASIC_BLOCK (old_index) == NULL);
 
 
  for (p = 0; p < df->num_problems_defined; p++)
  for (p = 0; p < df->num_problems_defined; p++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[p];
      struct dataflow *dflow = df->problems_in_order[p];
      if (dflow->block_info)
      if (dflow->block_info)
        {
        {
          df_grow_bb_info (dflow);
          df_grow_bb_info (dflow);
          gcc_assert (df_get_bb_info (dflow, old_index) == NULL);
          gcc_assert (df_get_bb_info (dflow, old_index) == NULL);
          df_set_bb_info (dflow, old_index,
          df_set_bb_info (dflow, old_index,
                          df_get_bb_info (dflow, new_block_index));
                          df_get_bb_info (dflow, new_block_index));
        }
        }
    }
    }
 
 
  df_clear_bb_dirty (new_block);
  df_clear_bb_dirty (new_block);
  SET_BASIC_BLOCK (old_index, new_block);
  SET_BASIC_BLOCK (old_index, new_block);
  new_block->index = old_index;
  new_block->index = old_index;
  df_set_bb_dirty (BASIC_BLOCK (old_index));
  df_set_bb_dirty (BASIC_BLOCK (old_index));
  SET_BASIC_BLOCK (new_block_index, NULL);
  SET_BASIC_BLOCK (new_block_index, NULL);
}
}
 
 
 
 
/* Free all of the per basic block dataflow from all of the problems.
/* 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
   This is typically called before a basic block is deleted and the
   problem will be reanalyzed.  */
   problem will be reanalyzed.  */
 
 
void
void
df_bb_delete (int bb_index)
df_bb_delete (int bb_index)
{
{
  basic_block bb = BASIC_BLOCK (bb_index);
  basic_block bb = BASIC_BLOCK (bb_index);
  int i;
  int i;
 
 
  if (!df)
  if (!df)
    return;
    return;
 
 
  for (i = 0; i < df->num_problems_defined; i++)
  for (i = 0; i < df->num_problems_defined; i++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[i];
      struct dataflow *dflow = df->problems_in_order[i];
      if (dflow->problem->free_bb_fun)
      if (dflow->problem->free_bb_fun)
        {
        {
          void *bb_info = df_get_bb_info (dflow, bb_index);
          void *bb_info = df_get_bb_info (dflow, bb_index);
          if (bb_info)
          if (bb_info)
            {
            {
              dflow->problem->free_bb_fun (bb, bb_info);
              dflow->problem->free_bb_fun (bb, bb_info);
              df_set_bb_info (dflow, bb_index, NULL);
              df_set_bb_info (dflow, bb_index, NULL);
            }
            }
        }
        }
    }
    }
  df_clear_bb_dirty (bb);
  df_clear_bb_dirty (bb);
  df_mark_solutions_dirty ();
  df_mark_solutions_dirty ();
}
}
 
 
 
 
/* Verify that there is a place for everything and everything is in
/* Verify that there is a place for everything and everything is in
   its place.  This is too expensive to run after every pass in the
   its place.  This is too expensive to run after every pass in the
   mainline.  However this is an excellent debugging tool if the
   mainline.  However this is an excellent debugging tool if the
   dataflow information is not being updated properly.  You can just
   dataflow information is not being updated properly.  You can just
   sprinkle calls in until you find the place that is changing an
   sprinkle calls in until you find the place that is changing an
   underlying structure without calling the proper updating
   underlying structure without calling the proper updating
   routine.  */
   routine.  */
 
 
void
void
df_verify (void)
df_verify (void)
{
{
  df_scan_verify ();
  df_scan_verify ();
#ifdef ENABLE_DF_CHECKING
#ifdef ENABLE_DF_CHECKING
  df_lr_verify_transfer_functions ();
  df_lr_verify_transfer_functions ();
  if (df_live)
  if (df_live)
    df_live_verify_transfer_functions ();
    df_live_verify_transfer_functions ();
#endif
#endif
}
}
 
 
#ifdef DF_DEBUG_CFG
#ifdef DF_DEBUG_CFG
 
 
/* Compute an array of ints that describes the cfg.  This can be used
/* Compute an array of ints that describes the cfg.  This can be used
   to discover places where the cfg is modified by the appropriate
   to discover places where the cfg is modified by the appropriate
   calls have not been made to the keep df informed.  The internals of
   calls have not been made to the keep df informed.  The internals of
   this are unexciting, the key is that two instances of this can be
   this are unexciting, the key is that two instances of this can be
   compared to see if any changes have been made to the cfg.  */
   compared to see if any changes have been made to the cfg.  */
 
 
static int *
static int *
df_compute_cfg_image (void)
df_compute_cfg_image (void)
{
{
  basic_block bb;
  basic_block bb;
  int size = 2 + (2 * n_basic_blocks);
  int size = 2 + (2 * n_basic_blocks);
  int i;
  int i;
  int * map;
  int * map;
 
 
  FOR_ALL_BB (bb)
  FOR_ALL_BB (bb)
    {
    {
      size += EDGE_COUNT (bb->succs);
      size += EDGE_COUNT (bb->succs);
    }
    }
 
 
  map = XNEWVEC (int, size);
  map = XNEWVEC (int, size);
  map[0] = size;
  map[0] = size;
  i = 1;
  i = 1;
  FOR_ALL_BB (bb)
  FOR_ALL_BB (bb)
    {
    {
      edge_iterator ei;
      edge_iterator ei;
      edge e;
      edge e;
 
 
      map[i++] = bb->index;
      map[i++] = bb->index;
      FOR_EACH_EDGE (e, ei, bb->succs)
      FOR_EACH_EDGE (e, ei, bb->succs)
        map[i++] = e->dest->index;
        map[i++] = e->dest->index;
      map[i++] = -1;
      map[i++] = -1;
    }
    }
  map[i] = -1;
  map[i] = -1;
  return map;
  return map;
}
}
 
 
static int *saved_cfg = NULL;
static int *saved_cfg = NULL;
 
 
 
 
/* This function compares the saved version of the cfg with the
/* This function compares the saved version of the cfg with the
   current cfg and aborts if the two are identical.  The function
   current cfg and aborts if the two are identical.  The function
   silently returns if the cfg has been marked as dirty or the two are
   silently returns if the cfg has been marked as dirty or the two are
   the same.  */
   the same.  */
 
 
void
void
df_check_cfg_clean (void)
df_check_cfg_clean (void)
{
{
  int *new_map;
  int *new_map;
 
 
  if (!df)
  if (!df)
    return;
    return;
 
 
  if (df_lr->solutions_dirty)
  if (df_lr->solutions_dirty)
    return;
    return;
 
 
  if (saved_cfg == NULL)
  if (saved_cfg == NULL)
    return;
    return;
 
 
  new_map = df_compute_cfg_image ();
  new_map = df_compute_cfg_image ();
  gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
  gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
  free (new_map);
  free (new_map);
}
}
 
 
 
 
/* This function builds a cfg fingerprint and squirrels it away in
/* This function builds a cfg fingerprint and squirrels it away in
   saved_cfg.  */
   saved_cfg.  */
 
 
static void
static void
df_set_clean_cfg (void)
df_set_clean_cfg (void)
{
{
  if (saved_cfg)
  if (saved_cfg)
    free (saved_cfg);
    free (saved_cfg);
  saved_cfg = df_compute_cfg_image ();
  saved_cfg = df_compute_cfg_image ();
}
}
 
 
#endif /* DF_DEBUG_CFG  */
#endif /* DF_DEBUG_CFG  */
/*----------------------------------------------------------------------------
/*----------------------------------------------------------------------------
   PUBLIC INTERFACES TO QUERY INFORMATION.
   PUBLIC INTERFACES TO QUERY INFORMATION.
----------------------------------------------------------------------------*/
----------------------------------------------------------------------------*/
 
 
 
 
/* Return first def of REGNO within BB.  */
/* Return first def of REGNO within BB.  */
 
 
df_ref
df_ref
df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
{
{
  rtx insn;
  rtx insn;
  df_ref *def_rec;
  df_ref *def_rec;
  unsigned int uid;
  unsigned int uid;
 
 
  FOR_BB_INSNS (bb, insn)
  FOR_BB_INSNS (bb, insn)
    {
    {
      if (!INSN_P (insn))
      if (!INSN_P (insn))
        continue;
        continue;
 
 
      uid = INSN_UID (insn);
      uid = INSN_UID (insn);
      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
        {
        {
          df_ref def = *def_rec;
          df_ref def = *def_rec;
          if (DF_REF_REGNO (def) == regno)
          if (DF_REF_REGNO (def) == regno)
            return def;
            return def;
        }
        }
    }
    }
  return NULL;
  return NULL;
}
}
 
 
 
 
/* Return last def of REGNO within BB.  */
/* Return last def of REGNO within BB.  */
 
 
df_ref
df_ref
df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
{
{
  rtx insn;
  rtx insn;
  df_ref *def_rec;
  df_ref *def_rec;
  unsigned int uid;
  unsigned int uid;
 
 
  FOR_BB_INSNS_REVERSE (bb, insn)
  FOR_BB_INSNS_REVERSE (bb, insn)
    {
    {
      if (!INSN_P (insn))
      if (!INSN_P (insn))
        continue;
        continue;
 
 
      uid = INSN_UID (insn);
      uid = INSN_UID (insn);
      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
        {
        {
          df_ref def = *def_rec;
          df_ref def = *def_rec;
          if (DF_REF_REGNO (def) == regno)
          if (DF_REF_REGNO (def) == regno)
            return def;
            return def;
        }
        }
    }
    }
 
 
  return NULL;
  return NULL;
}
}
 
 
/* Finds the reference corresponding to the definition of REG in INSN.
/* Finds the reference corresponding to the definition of REG in INSN.
   DF is the dataflow object.  */
   DF is the dataflow object.  */
 
 
df_ref
df_ref
df_find_def (rtx insn, rtx reg)
df_find_def (rtx insn, rtx reg)
{
{
  unsigned int uid;
  unsigned int uid;
  df_ref *def_rec;
  df_ref *def_rec;
 
 
  if (GET_CODE (reg) == SUBREG)
  if (GET_CODE (reg) == SUBREG)
    reg = SUBREG_REG (reg);
    reg = SUBREG_REG (reg);
  gcc_assert (REG_P (reg));
  gcc_assert (REG_P (reg));
 
 
  uid = INSN_UID (insn);
  uid = INSN_UID (insn);
  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
    {
    {
      df_ref def = *def_rec;
      df_ref def = *def_rec;
      if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
      if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
        return def;
        return def;
    }
    }
 
 
  return NULL;
  return NULL;
}
}
 
 
 
 
/* Return true if REG is defined in INSN, zero otherwise.  */
/* Return true if REG is defined in INSN, zero otherwise.  */
 
 
bool
bool
df_reg_defined (rtx insn, rtx reg)
df_reg_defined (rtx insn, rtx reg)
{
{
  return df_find_def (insn, reg) != NULL;
  return df_find_def (insn, reg) != NULL;
}
}
 
 
 
 
/* Finds the reference corresponding to the use of REG in INSN.
/* Finds the reference corresponding to the use of REG in INSN.
   DF is the dataflow object.  */
   DF is the dataflow object.  */
 
 
df_ref
df_ref
df_find_use (rtx insn, rtx reg)
df_find_use (rtx insn, rtx reg)
{
{
  unsigned int uid;
  unsigned int uid;
  df_ref *use_rec;
  df_ref *use_rec;
 
 
  if (GET_CODE (reg) == SUBREG)
  if (GET_CODE (reg) == SUBREG)
    reg = SUBREG_REG (reg);
    reg = SUBREG_REG (reg);
  gcc_assert (REG_P (reg));
  gcc_assert (REG_P (reg));
 
 
  uid = INSN_UID (insn);
  uid = INSN_UID (insn);
  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
    {
    {
      df_ref use = *use_rec;
      df_ref use = *use_rec;
      if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
      if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
        return use;
        return use;
    }
    }
  if (df->changeable_flags & DF_EQ_NOTES)
  if (df->changeable_flags & DF_EQ_NOTES)
    for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
    for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
      {
      {
        df_ref use = *use_rec;
        df_ref use = *use_rec;
        if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
        if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
          return use;
          return use;
      }
      }
  return NULL;
  return NULL;
}
}
 
 
 
 
/* Return true if REG is referenced in INSN, zero otherwise.  */
/* Return true if REG is referenced in INSN, zero otherwise.  */
 
 
bool
bool
df_reg_used (rtx insn, rtx reg)
df_reg_used (rtx insn, rtx reg)
{
{
  return df_find_use (insn, reg) != NULL;
  return df_find_use (insn, reg) != NULL;
}
}
 
 


/*----------------------------------------------------------------------------
/*----------------------------------------------------------------------------
   Debugging and printing functions.
   Debugging and printing functions.
----------------------------------------------------------------------------*/
----------------------------------------------------------------------------*/
 
 
 
 
/* Write information about registers and basic blocks into FILE.
/* Write information about registers and basic blocks into FILE.
   This is part of making a debugging dump.  */
   This is part of making a debugging dump.  */
 
 
void
void
df_print_regset (FILE *file, bitmap r)
df_print_regset (FILE *file, bitmap r)
{
{
  unsigned int i;
  unsigned int i;
  bitmap_iterator bi;
  bitmap_iterator bi;
 
 
  if (r == NULL)
  if (r == NULL)
    fputs (" (nil)", file);
    fputs (" (nil)", file);
  else
  else
    {
    {
      EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
      EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
        {
        {
          fprintf (file, " %d", i);
          fprintf (file, " %d", i);
          if (i < FIRST_PSEUDO_REGISTER)
          if (i < FIRST_PSEUDO_REGISTER)
            fprintf (file, " [%s]", reg_names[i]);
            fprintf (file, " [%s]", reg_names[i]);
        }
        }
    }
    }
  fprintf (file, "\n");
  fprintf (file, "\n");
}
}
 
 
 
 
/* Write information about registers and basic blocks into FILE.  The
/* Write information about registers and basic blocks into FILE.  The
   bitmap is in the form used by df_byte_lr.  This is part of making a
   bitmap is in the form used by df_byte_lr.  This is part of making a
   debugging dump.  */
   debugging dump.  */
 
 
void
void
df_print_byte_regset (FILE *file, bitmap r)
df_print_byte_regset (FILE *file, bitmap r)
{
{
  unsigned int max_reg = max_reg_num ();
  unsigned int max_reg = max_reg_num ();
  bitmap_iterator bi;
  bitmap_iterator bi;
 
 
  if (r == NULL)
  if (r == NULL)
    fputs (" (nil)", file);
    fputs (" (nil)", file);
  else
  else
    {
    {
      unsigned int i;
      unsigned int i;
      for (i = 0; i < max_reg; i++)
      for (i = 0; i < max_reg; i++)
        {
        {
          unsigned int first = df_byte_lr_get_regno_start (i);
          unsigned int first = df_byte_lr_get_regno_start (i);
          unsigned int len = df_byte_lr_get_regno_len (i);
          unsigned int len = df_byte_lr_get_regno_len (i);
 
 
          if (len > 1)
          if (len > 1)
            {
            {
              bool found = false;
              bool found = false;
              unsigned int j;
              unsigned int j;
 
 
              EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
              EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
                {
                {
                  found = j < first + len;
                  found = j < first + len;
                  break;
                  break;
                }
                }
              if (found)
              if (found)
                {
                {
                  const char * sep = "";
                  const char * sep = "";
                  fprintf (file, " %d", i);
                  fprintf (file, " %d", i);
                  if (i < FIRST_PSEUDO_REGISTER)
                  if (i < FIRST_PSEUDO_REGISTER)
                    fprintf (file, " [%s]", reg_names[i]);
                    fprintf (file, " [%s]", reg_names[i]);
                  fprintf (file, "(");
                  fprintf (file, "(");
                  EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
                  EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
                    {
                    {
                      if (j > first + len - 1)
                      if (j > first + len - 1)
                        break;
                        break;
                      fprintf (file, "%s%d", sep, j-first);
                      fprintf (file, "%s%d", sep, j-first);
                      sep = ", ";
                      sep = ", ";
                    }
                    }
                  fprintf (file, ")");
                  fprintf (file, ")");
                }
                }
            }
            }
          else
          else
            {
            {
              if (bitmap_bit_p (r, first))
              if (bitmap_bit_p (r, first))
                {
                {
                  fprintf (file, " %d", i);
                  fprintf (file, " %d", i);
                  if (i < FIRST_PSEUDO_REGISTER)
                  if (i < FIRST_PSEUDO_REGISTER)
                    fprintf (file, " [%s]", reg_names[i]);
                    fprintf (file, " [%s]", reg_names[i]);
                }
                }
            }
            }
 
 
        }
        }
    }
    }
  fprintf (file, "\n");
  fprintf (file, "\n");
}
}
 
 
 
 
/* Dump dataflow info.  */
/* Dump dataflow info.  */
 
 
void
void
df_dump (FILE *file)
df_dump (FILE *file)
{
{
  basic_block bb;
  basic_block bb;
  df_dump_start (file);
  df_dump_start (file);
 
 
  FOR_ALL_BB (bb)
  FOR_ALL_BB (bb)
    {
    {
      df_print_bb_index (bb, file);
      df_print_bb_index (bb, file);
      df_dump_top (bb, file);
      df_dump_top (bb, file);
      df_dump_bottom (bb, file);
      df_dump_bottom (bb, file);
    }
    }
 
 
  fprintf (file, "\n");
  fprintf (file, "\n");
}
}
 
 
 
 
/* Dump dataflow info for df->blocks_to_analyze.  */
/* Dump dataflow info for df->blocks_to_analyze.  */
 
 
void
void
df_dump_region (FILE *file)
df_dump_region (FILE *file)
{
{
  if (df->blocks_to_analyze)
  if (df->blocks_to_analyze)
    {
    {
      bitmap_iterator bi;
      bitmap_iterator bi;
      unsigned int bb_index;
      unsigned int bb_index;
 
 
      fprintf (file, "\n\nstarting region dump\n");
      fprintf (file, "\n\nstarting region dump\n");
      df_dump_start (file);
      df_dump_start (file);
 
 
      EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
      EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
        {
        {
          basic_block bb = BASIC_BLOCK (bb_index);
          basic_block bb = BASIC_BLOCK (bb_index);
 
 
          df_print_bb_index (bb, file);
          df_print_bb_index (bb, file);
          df_dump_top (bb, file);
          df_dump_top (bb, file);
          df_dump_bottom (bb, file);
          df_dump_bottom (bb, file);
        }
        }
      fprintf (file, "\n");
      fprintf (file, "\n");
    }
    }
  else
  else
    df_dump (file);
    df_dump (file);
}
}
 
 
 
 
/* Dump the introductory information for each problem defined.  */
/* Dump the introductory information for each problem defined.  */
 
 
void
void
df_dump_start (FILE *file)
df_dump_start (FILE *file)
{
{
  int i;
  int i;
 
 
  if (!df || !file)
  if (!df || !file)
    return;
    return;
 
 
  fprintf (file, "\n\n%s\n", current_function_name ());
  fprintf (file, "\n\n%s\n", current_function_name ());
  fprintf (file, "\nDataflow summary:\n");
  fprintf (file, "\nDataflow summary:\n");
  if (df->blocks_to_analyze)
  if (df->blocks_to_analyze)
    fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
    fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
             DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
             DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
 
 
  for (i = 0; i < df->num_problems_defined; i++)
  for (i = 0; i < df->num_problems_defined; i++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[i];
      struct dataflow *dflow = df->problems_in_order[i];
      if (dflow->computed)
      if (dflow->computed)
        {
        {
          df_dump_problem_function fun = dflow->problem->dump_start_fun;
          df_dump_problem_function fun = dflow->problem->dump_start_fun;
          if (fun)
          if (fun)
            fun(file);
            fun(file);
        }
        }
    }
    }
}
}
 
 
 
 
/* Dump the top of the block information for BB.  */
/* Dump the top of the block information for BB.  */
 
 
void
void
df_dump_top (basic_block bb, FILE *file)
df_dump_top (basic_block bb, FILE *file)
{
{
  int i;
  int i;
 
 
  if (!df || !file)
  if (!df || !file)
    return;
    return;
 
 
  for (i = 0; i < df->num_problems_defined; i++)
  for (i = 0; i < df->num_problems_defined; i++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[i];
      struct dataflow *dflow = df->problems_in_order[i];
      if (dflow->computed)
      if (dflow->computed)
        {
        {
          df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
          df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
          if (bbfun)
          if (bbfun)
            bbfun (bb, file);
            bbfun (bb, file);
        }
        }
    }
    }
}
}
 
 
 
 
/* Dump the bottom of the block information for BB.  */
/* Dump the bottom of the block information for BB.  */
 
 
void
void
df_dump_bottom (basic_block bb, FILE *file)
df_dump_bottom (basic_block bb, FILE *file)
{
{
  int i;
  int i;
 
 
  if (!df || !file)
  if (!df || !file)
    return;
    return;
 
 
  for (i = 0; i < df->num_problems_defined; i++)
  for (i = 0; i < df->num_problems_defined; i++)
    {
    {
      struct dataflow *dflow = df->problems_in_order[i];
      struct dataflow *dflow = df->problems_in_order[i];
      if (dflow->computed)
      if (dflow->computed)
        {
        {
          df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
          df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
          if (bbfun)
          if (bbfun)
            bbfun (bb, file);
            bbfun (bb, file);
        }
        }
    }
    }
}
}
 
 
 
 
void
void
df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file)
df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file)
{
{
  fprintf (file, "{ ");
  fprintf (file, "{ ");
  while (*ref_rec)
  while (*ref_rec)
    {
    {
      df_ref ref = *ref_rec;
      df_ref ref = *ref_rec;
      fprintf (file, "%c%d(%d)",
      fprintf (file, "%c%d(%d)",
               DF_REF_REG_DEF_P (ref) ? 'd' : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
               DF_REF_REG_DEF_P (ref) ? 'd' : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
               DF_REF_ID (ref),
               DF_REF_ID (ref),
               DF_REF_REGNO (ref));
               DF_REF_REGNO (ref));
      if (follow_chain)
      if (follow_chain)
        df_chain_dump (DF_REF_CHAIN (ref), file);
        df_chain_dump (DF_REF_CHAIN (ref), file);
      ref_rec++;
      ref_rec++;
    }
    }
  fprintf (file, "}");
  fprintf (file, "}");
}
}
 
 
 
 
/* Dump either a ref-def or reg-use chain.  */
/* Dump either a ref-def or reg-use chain.  */
 
 
void
void
df_regs_chain_dump (df_ref ref,  FILE *file)
df_regs_chain_dump (df_ref ref,  FILE *file)
{
{
  fprintf (file, "{ ");
  fprintf (file, "{ ");
  while (ref)
  while (ref)
    {
    {
      fprintf (file, "%c%d(%d) ",
      fprintf (file, "%c%d(%d) ",
               DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
               DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
               DF_REF_ID (ref),
               DF_REF_ID (ref),
               DF_REF_REGNO (ref));
               DF_REF_REGNO (ref));
      ref = DF_REF_NEXT_REG (ref);
      ref = DF_REF_NEXT_REG (ref);
    }
    }
  fprintf (file, "}");
  fprintf (file, "}");
}
}
 
 
 
 
static void
static void
df_mws_dump (struct df_mw_hardreg **mws, FILE *file)
df_mws_dump (struct df_mw_hardreg **mws, FILE *file)
{
{
  while (*mws)
  while (*mws)
    {
    {
      fprintf (file, "mw %c r[%d..%d]\n",
      fprintf (file, "mw %c r[%d..%d]\n",
               (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u',
               (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u',
               (*mws)->start_regno, (*mws)->end_regno);
               (*mws)->start_regno, (*mws)->end_regno);
      mws++;
      mws++;
    }
    }
}
}
 
 
 
 
static void
static void
df_insn_uid_debug (unsigned int uid,
df_insn_uid_debug (unsigned int uid,
                   bool follow_chain, FILE *file)
                   bool follow_chain, FILE *file)
{
{
  fprintf (file, "insn %d luid %d",
  fprintf (file, "insn %d luid %d",
           uid, DF_INSN_UID_LUID (uid));
           uid, DF_INSN_UID_LUID (uid));
 
 
  if (DF_INSN_UID_DEFS (uid))
  if (DF_INSN_UID_DEFS (uid))
    {
    {
      fprintf (file, " defs ");
      fprintf (file, " defs ");
      df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
      df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
    }
    }
 
 
  if (DF_INSN_UID_USES (uid))
  if (DF_INSN_UID_USES (uid))
    {
    {
      fprintf (file, " uses ");
      fprintf (file, " uses ");
      df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
      df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
    }
    }
 
 
  if (DF_INSN_UID_EQ_USES (uid))
  if (DF_INSN_UID_EQ_USES (uid))
    {
    {
      fprintf (file, " eq uses ");
      fprintf (file, " eq uses ");
      df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
      df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
    }
    }
 
 
  if (DF_INSN_UID_MWS (uid))
  if (DF_INSN_UID_MWS (uid))
    {
    {
      fprintf (file, " mws ");
      fprintf (file, " mws ");
      df_mws_dump (DF_INSN_UID_MWS (uid), file);
      df_mws_dump (DF_INSN_UID_MWS (uid), file);
    }
    }
  fprintf (file, "\n");
  fprintf (file, "\n");
}
}
 
 
 
 
void
void
df_insn_debug (rtx insn, bool follow_chain, FILE *file)
df_insn_debug (rtx insn, bool follow_chain, FILE *file)
{
{
  df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
  df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
}
}
 
 
void
void
df_insn_debug_regno (rtx insn, FILE *file)
df_insn_debug_regno (rtx insn, FILE *file)
{
{
  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 
 
  fprintf (file, "insn %d bb %d luid %d defs ",
  fprintf (file, "insn %d bb %d luid %d defs ",
           INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
           INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
           DF_INSN_INFO_LUID (insn_info));
           DF_INSN_INFO_LUID (insn_info));
  df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
  df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
 
 
  fprintf (file, " uses ");
  fprintf (file, " uses ");
  df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
  df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
 
 
  fprintf (file, " eq_uses ");
  fprintf (file, " eq_uses ");
  df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
  df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
  fprintf (file, "\n");
  fprintf (file, "\n");
}
}
 
 
void
void
df_regno_debug (unsigned int regno, FILE *file)
df_regno_debug (unsigned int regno, FILE *file)
{
{
  fprintf (file, "reg %d defs ", regno);
  fprintf (file, "reg %d defs ", regno);
  df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
  df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
  fprintf (file, " uses ");
  fprintf (file, " uses ");
  df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
  df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
  fprintf (file, " eq_uses ");
  fprintf (file, " eq_uses ");
  df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
  df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
  fprintf (file, "\n");
  fprintf (file, "\n");
}
}
 
 
 
 
void
void
df_ref_debug (df_ref ref, FILE *file)
df_ref_debug (df_ref ref, FILE *file)
{
{
  fprintf (file, "%c%d ",
  fprintf (file, "%c%d ",
           DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
           DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
           DF_REF_ID (ref));
           DF_REF_ID (ref));
  fprintf (file, "reg %d bb %d insn %d flag 0x%x type 0x%x ",
  fprintf (file, "reg %d bb %d insn %d flag 0x%x type 0x%x ",
           DF_REF_REGNO (ref),
           DF_REF_REGNO (ref),
           DF_REF_BBNO (ref),
           DF_REF_BBNO (ref),
           DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
           DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
           DF_REF_FLAGS (ref),
           DF_REF_FLAGS (ref),
           DF_REF_TYPE (ref));
           DF_REF_TYPE (ref));
  if (DF_REF_LOC (ref))
  if (DF_REF_LOC (ref))
    {
    {
      if (flag_dump_noaddr)
      if (flag_dump_noaddr)
        fprintf (file, "loc #(#) chain ");
        fprintf (file, "loc #(#) chain ");
      else
      else
        fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
        fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
                 (void *)*DF_REF_LOC (ref));
                 (void *)*DF_REF_LOC (ref));
    }
    }
  else
  else
    fprintf (file, "chain ");
    fprintf (file, "chain ");
  df_chain_dump (DF_REF_CHAIN (ref), file);
  df_chain_dump (DF_REF_CHAIN (ref), file);
  fprintf (file, "\n");
  fprintf (file, "\n");
}
}


/* Functions for debugging from GDB.  */
/* Functions for debugging from GDB.  */
 
 
void
void
debug_df_insn (rtx insn)
debug_df_insn (rtx insn)
{
{
  df_insn_debug (insn, true, stderr);
  df_insn_debug (insn, true, stderr);
  debug_rtx (insn);
  debug_rtx (insn);
}
}
 
 
 
 
void
void
debug_df_reg (rtx reg)
debug_df_reg (rtx reg)
{
{
  df_regno_debug (REGNO (reg), stderr);
  df_regno_debug (REGNO (reg), stderr);
}
}
 
 
 
 
void
void
debug_df_regno (unsigned int regno)
debug_df_regno (unsigned int regno)
{
{
  df_regno_debug (regno, stderr);
  df_regno_debug (regno, stderr);
}
}
 
 
 
 
void
void
debug_df_ref (df_ref ref)
debug_df_ref (df_ref ref)
{
{
  df_ref_debug (ref, stderr);
  df_ref_debug (ref, stderr);
}
}
 
 
 
 
void
void
debug_df_defno (unsigned int defno)
debug_df_defno (unsigned int defno)
{
{
  df_ref_debug (DF_DEFS_GET (defno), stderr);
  df_ref_debug (DF_DEFS_GET (defno), stderr);
}
}
 
 
 
 
void
void
debug_df_useno (unsigned int defno)
debug_df_useno (unsigned int defno)
{
{
  df_ref_debug (DF_USES_GET (defno), stderr);
  df_ref_debug (DF_USES_GET (defno), stderr);
}
}
 
 
 
 
void
void
debug_df_chain (struct df_link *link)
debug_df_chain (struct df_link *link)
{
{
  df_chain_dump (link, stderr);
  df_chain_dump (link, stderr);
  fputc ('\n', stderr);
  fputc ('\n', stderr);
}
}
 
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.