GCC Middle and Back End API Reference
df-core.c File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
Include dependency graph for df-core.c:


static void * df_get_bb_info (struct dataflow *, unsigned int)
static void df_set_bb_info (struct dataflow *, unsigned int, void *)
static void df_clear_bb_info (struct dataflow *, unsigned int)
static void df_set_clean_cfg (void)
void df_add_problem ()
int df_set_flags ()
int df_clear_flags ()
void df_set_blocks ()
void df_remove_problem ()
void df_finish_pass ()
static unsigned int rest_of_handle_df_initialize ()
static bool gate_opt ()
rtl_opt_passmake_pass_df_initialize_opt ()
static bool gate_no_opt ()
rtl_opt_passmake_pass_df_initialize_no_opt ()
static unsigned int rest_of_handle_df_finish ()
rtl_opt_passmake_pass_df_finish ()
static bool df_worklist_propagate_forward (struct dataflow *dataflow, unsigned bb_index, unsigned *bbindex_to_postorder, bitmap pending, sbitmap considered, ptrdiff_t age)
static bool df_worklist_propagate_backward (struct dataflow *dataflow, unsigned bb_index, unsigned *bbindex_to_postorder, bitmap pending, sbitmap considered, ptrdiff_t age)
static void df_worklist_dataflow_doublequeue (struct dataflow *dataflow, bitmap pending, sbitmap considered, int *blocks_in_postorder, unsigned *bbindex_to_postorder, int n_blocks)
void df_worklist_dataflow (struct dataflow *dataflow, bitmap blocks_to_consider, int *blocks_in_postorder, int n_blocks)
static unsigned df_prune_to_subcfg ()
void df_analyze_problem (struct dataflow *dflow, bitmap blocks_to_consider, int *postorder, int n_blocks)
void df_analyze ()
int df_get_n_blocks ()
int * df_get_postorder ()
void df_simple_dataflow (enum df_flow_dir dir, df_init_function init_fun, df_confluence_function_0 con_fun_0, df_confluence_function_n con_fun_n, df_transfer_function trans_fun, bitmap blocks, int *postorder, int n_blocks)
static void * df_get_bb_info ()
static void df_clear_bb_info ()
void df_mark_solutions_dirty ()
bool df_get_bb_dirty ()
void df_set_bb_dirty ()
void df_grow_bb_info ()
static void df_clear_bb_dirty ()
void df_compact_blocks ()
void df_bb_replace ()
void df_bb_delete ()
void df_verify ()
static int * df_compute_cfg_image ()
void df_check_cfg_clean ()
df_ref df_bb_regno_first_def_find ()
df_ref df_bb_regno_last_def_find ()
df_ref df_find_def ()
bool df_reg_defined ()
df_ref df_find_use ()
bool df_reg_used ()
void dump_regset ()
void debug_regset (regset)
DEBUG_FUNCTION void debug_regset ()
void df_print_regset ()
void df_print_word_regset ()
void df_dump ()
void df_dump_region ()
void df_dump_start ()
static void df_dump_bb_problem_data ()
void df_dump_top ()
void df_dump_bottom ()
static void df_dump_insn_problem_data ()
void df_dump_insn_top ()
void df_dump_insn_bottom ()
static void df_ref_dump ()
void df_refs_chain_dump ()
void df_regs_chain_dump ()
static void df_mws_dump ()
static void df_insn_uid_debug (unsigned int uid, bool follow_chain, FILE *file)
DEBUG_FUNCTION void df_insn_debug ()
DEBUG_FUNCTION void df_insn_debug_regno ()
DEBUG_FUNCTION void df_regno_debug ()
DEBUG_FUNCTION void df_ref_debug ()
DEBUG_FUNCTION void debug_df_insn ()
DEBUG_FUNCTION void debug_df_reg ()
DEBUG_FUNCTION void debug_df_regno ()
DEBUG_FUNCTION void debug_df_ref ()
DEBUG_FUNCTION void debug_df_defno ()
DEBUG_FUNCTION void debug_df_useno ()
DEBUG_FUNCTION void debug_df_chain ()


struct bitmap_obstack reg_obstack
bitmap_obstack df_bitmap_obstack
struct df_ddf
static struct df_problem user_problem
static struct dataflow user_dflow
static int * saved_cfg = NULL

Function Documentation

DEBUG_FUNCTION void debug_df_chain ( )
DEBUG_FUNCTION void debug_df_defno ( )
DEBUG_FUNCTION void debug_df_insn ( )
   Functions for debugging from GDB.  
DEBUG_FUNCTION void debug_df_ref ( )
DEBUG_FUNCTION void debug_df_reg ( )
DEBUG_FUNCTION void debug_df_regno ( )
DEBUG_FUNCTION void debug_df_useno ( )
void debug_regset ( regset  )
   Print a human-readable representation of R on the standard error
   stream.  This function is designed to be used from within the
DEBUG_FUNCTION void debug_regset ( )
void df_add_problem ( )
   Add PROBLEM (and any dependent problems) to the DF instance.  
     First try to add the dependent problem. 
     Check to see if this problem has already been defined.  If it
     has, just return that instance, if not, add it to the end of the
     Make a new one and add it to the end.  
     Keep the defined problems ordered by index.  This solves the
     problem that RI will use the information from UREC if UREC has
     been defined, or from LIVE if LIVE is defined and otherwise LR.
     However for this to work, the computation of RI must be pushed
     after which ever of those problems is defined, but we do not
     require any of those except for LR to have actually been

Referenced by df_lr_verify_solution_end().

void df_analyze ( void  )
   Analyze dataflow info for the basic blocks specified by the bitmap
   BLOCKS, or for the whole CFG if BLOCKS is zero.  
     These should be the same.  
     We need to do this before the df_verify_all because this is
     not kept incrementally up to date.  
     Verify that POSTORDER_INVERTED only contains blocks reachable from
     the ENTRY block.  
     Make sure that we have pruned any unreachable blocks from these
     Skip over the DF_SCAN problem. 

Referenced by compute_bb_for_insn(), copyprop_hardreg_forward(), dse_step4(), duplicate_computed_gotos(), mark_artificial_uses(), move_insn_for_shrink_wrap(), move_unallocated_pseudos(), and split_live_ranges_for_shrink_wrap().

void df_analyze_problem ( struct dataflow dflow,
bitmap  blocks_to_consider,
int *  postorder,
int  n_blocks 

Execute dataflow analysis on a single dataflow problem.

BLOCKS_TO_CONSIDER are the blocks whose solution can either be examined or will be computed. For calls from DF_ANALYZE, this is the set of blocks that has been passed to DF_SET_BLOCKS.

     (Re)Allocate the datastructures necessary to solve the problem.  
     Set up the problem and compute the local information.  
     Solve the equations.  
     Massage the solution.  

Referenced by fast_dce().

void df_bb_delete ( )
   Free all of the per basic block dataflow from all of the problems.
   This is typically called before a basic block is deleted and the
   problem will be reanalyzed.  

References df_compute_cfg_image(), free(), and saved_cfg.

df_ref df_bb_regno_first_def_find ( )
   Return first def of REGNO within BB.  

References df_d::changeable_flags, and DF_EQ_NOTES.

df_ref df_bb_regno_last_def_find ( )
   Return last def of REGNO within BB.  
void df_bb_replace ( )
   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.  
void df_check_cfg_clean ( void  )
   This function compares the saved version of the cfg with the
   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
   the same.  
static void df_clear_bb_dirty ( )
   Clear the dirty bits.  This is called from places that delete
static void df_clear_bb_info ( struct dataflow ,
unsigned  int 
static void df_clear_bb_info ( )
   Clear basic block info.  
int df_clear_flags ( )
   Clear the MASK flags in the DFLOW problem.  The old flags are
   returned.  If a flag is not allowed to be changed this will fail if
   checking is enabled.  

References bitmap_print(), df_d::blocks_to_analyze, and dump_file.

Referenced by df_insn_rescan_debug_internal(), df_lr_confluence_0(), fast_dce(), and split_live_ranges_for_shrink_wrap().

void df_compact_blocks ( void  )
   Called from the rtl_compact_blocks to reorganize the problems basic
   block info.  
         Need to reorganize the out_of_date_transfer_functions for the
         dflow problem.  
         Now shuffle the block info for the problem.  
             Copy the bb info from the problem tmps to the proper
             place in the block_info vector.  Null out the copied
             item.  The entry and exit blocks never move.  
     Shuffle the bits in the basic_block indexed arrays.  

Referenced by unlink_block().

static int* df_compute_cfg_image ( )
   Compute an array of ints that describes the cfg.  This can be used
   to discover places where the cfg is modified by the appropriate
   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
   compared to see if any changes have been made to the cfg.  

Referenced by df_bb_delete(), and df_verify().

void df_dump ( )
   Dump dataflow info.  

Referenced by mark_artificial_uses().

static void df_dump_bb_problem_data ( )
   Dump the top or bottom of the block information for BB.  

References df_chain_dump(), and df_ref_dump().

void df_dump_bottom ( )
   Dump the bottom of the block information for BB.  
void df_dump_insn_bottom ( )
   Dump information about INSN after dumping INSN itself.  
static void df_dump_insn_problem_data ( )
   Dump information about INSN just before or after dumping INSN itself.  

References df_mws_dump(), and df_refs_chain_dump().

Referenced by df_dump_start().

void df_dump_insn_top ( )
   Dump information about INSN before dumping INSN itself.  

References df_insn_uid_debug().

void df_dump_region ( )
void df_dump_start ( )
   Dump the introductory information for each problem defined.  

References df_dump_insn_problem_data().

Referenced by debug_regset().

void df_dump_top ( )
   Dump the top of the block information for BB.  

Referenced by commit_one_edge_insertion().

df_ref df_find_def ( )
   Finds the reference corresponding to the definition of REG in INSN.
   DF is the dataflow object.  
df_ref df_find_use ( )
   Finds the reference corresponding to the use of REG in INSN.
   DF is the dataflow object.  

Referenced by invariant_for_use().

void df_finish_pass ( )
   Remove all of the problems that are not permanent.  Scanning, LR
   and (at -O2 or higher) LIVE are permanent, the rest are removable.
   Also clear all of the changeable_flags.  
     Clear all of the flags.  
     Set the focus back to the whole function.  
     Verification will fail in DF_NO_INSN_RESCAN.  

References df_problem::id, dataflow::optional_p, dataflow::problem, df_d::problems_by_index, df_d::problems_in_order, and df_problem::remove_problem_fun.

Referenced by biv_p(), and duplicate_computed_gotos().

bool df_get_bb_dirty ( )
   Return true if BB needs it's transfer functions recomputed.  

References df_d::num_problems_defined, and df_d::problems_in_order.

static void* df_get_bb_info ( struct dataflow ,
unsigned  int 

Allocation for dataflow support routines. Copyright (C) 1999-2013 Free Software Foundation, Inc. Originally contributed by Michael P. Hayes (m.hay.nosp@m.es@e.nosp@m.lec.c.nosp@m.ante.nosp@m.rbury.nosp@m..ac..nosp@m.nz, mhaye.nosp@m.s@re.nosp@m.dhat..nosp@m.com) Major rewrite contributed by Danny Berlin (dberl.nosp@m.in@d.nosp@m.berli.nosp@m.n.or.nosp@m.g) and Kenneth Zadeck (zadec.nosp@m.k@na.nosp@m.tural.nosp@m.brid.nosp@m.ge.co.nosp@m.m).

This file is part of GCC.

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

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

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.

int df_get_n_blocks ( )
   Return the number of basic blocks from the last call to df_analyze.  

References dataflow::block_info, df_problem::block_info_elt_size, dataflow::block_info_size, and dataflow::problem.

int* df_get_postorder ( )
   Return a pointer to the array of basic blocks in the reverse postorder.
   Depending on the direction of the dataflow problem,
   it returns either the usual reverse postorder array
   or the reverse postorder of inverted traversal. 

References dataflow::block_info, df_problem::block_info_elt_size, memcpy(), and dataflow::problem.

DEBUG_FUNCTION void df_insn_debug ( )
DEBUG_FUNCTION void df_insn_debug_regno ( )

References df_chain_dump().

static void df_insn_uid_debug ( unsigned int  uid,
bool  follow_chain,
FILE *  file 

Referenced by df_dump_insn_top().

void df_mark_solutions_dirty ( void  )
static void df_mws_dump ( )
void df_print_regset ( )
   Write information about registers and basic blocks into FILE.
   This is part of making a debugging dump.  

Referenced by df_live_confluence_n(), df_live_transfer_function(), df_lr_finalize(), df_lr_transfer_function(), df_remove_dead_eq_notes(), df_scan_free(), df_whole_mw_reg_dead_p(), and get_stored_val().

void df_print_word_regset ( )
   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
   debugging dump.  

References dataflow::computed, df_problem::dump_start_fun, dataflow::problem, and df_d::problems_in_order.

Referenced by df_word_lr_bb_local_compute(), and gate_ud_dce().

static unsigned df_prune_to_subcfg ( )
   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
DEBUG_FUNCTION void df_ref_debug ( )

Referenced by df_create_unused_note().

static void df_ref_dump ( )

Referenced by df_dump_bb_problem_data().

void df_refs_chain_dump ( )
bool df_reg_defined ( )
   Return true if REG is defined in INSN, zero otherwise.  
bool df_reg_used ( )
   Return true if REG is referenced in INSN, zero otherwise.  
DEBUG_FUNCTION void df_regno_debug ( )
void df_regs_chain_dump ( )
   Dump either a ref-def or reg-use chain.  

Referenced by df_refs_chain_dump().

void df_remove_problem ( )
   Delete a DFLOW problem (and any problems that depend on this
     Delete any problems that depended on this problem first.  
     Now remove this problem.  

References df_d::num_problems_defined, and df_d::problems_in_order.

Referenced by init_dce(), and split_live_ranges_for_shrink_wrap().

static void df_set_bb_info ( struct dataflow dflow,
unsigned int  index,
void *  bb_info 
   Set basic block info.  

Referenced by df_grow_bb_info().

void df_set_blocks ( )
   Set the blocks that are to be considered for analysis.  If this is
   not called or is called with null, the entire function in
             This block is called to change the focus from one subset
             to another.  
             This block of code is executed to change the focus from
             the entire function to a subset.  
         This block is executed to reset the focus to the entire
     Setting the blocks causes the refs to be unorganized since only
     the refs in the blocks are seen.  
static void df_set_clean_cfg ( )
   This function builds a cfg fingerprint and squirrels it away in
int df_set_flags ( )
   Set the MASK flags in the DFLOW problem.  The old flags are
   returned.  If a flag is not allowed to be changed this will fail if
   checking is enabled.  

References df_d::changeable_flags.

Referenced by clear_iv_info(), df_insn_rescan_debug_internal(), df_lr_confluence_0(), dse_step4(), duplicate_computed_gotos(), fast_dce(), and mark_artificial_uses().

void df_simple_dataflow ( enum df_flow_dir  dir,
df_init_function  init_fun,
df_confluence_function_0  con_fun_0,
df_confluence_function_n  con_fun_n,
df_transfer_function  trans_fun,
bitmap  blocks,
int *  postorder,
int  n_blocks 
   Interface for calling iterative dataflow with user defined
   confluence and transfer functions.  All that is necessary is to
   supply DIR, a direction, CONF_FUN_0, a confluence function for
   blocks with no logical preds (or NULL), CONF_FUN_N, the normal
   confluence function, TRANS_FUN, the basic block transfer function,
   and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
   postorder, and N_BLOCKS, the number of blocks in POSTORDER. 

References df_d::num_problems_defined, df_d::problems_in_order, and dataflow::solutions_dirty.

void df_verify ( void  )
   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
   mainline.  However this is an excellent debugging tool if the
   dataflow information is not being updated properly.  You can just
   sprinkle calls in until you find the place that is changing an
   underlying structure without calling the proper updating

References df_compute_cfg_image(), free(), and saved_cfg.

void df_worklist_dataflow ( struct dataflow dataflow,
bitmap  blocks_to_consider,
int *  blocks_in_postorder,
int  n_blocks 
   Worklist-based dataflow solver. It uses sbitmap as a worklist,
   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
   from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
   The only significant difference is that the worklist in this implementation
   is always sorted in RPO of the CFG visiting direction.  
     BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder.  
     Initialize the array to an out-of-bound value.  
     Initialize the considered map.  
     Initialize the mapping of block index to postorder.  
         Add all blocks to the worklist.  
     Initialize the problem. 
     Solve it.  

Referenced by df_lr_confluence_0().

static void df_worklist_dataflow_doublequeue ( struct dataflow dataflow,
bitmap  pending,
sbitmap  considered,
int *  blocks_in_postorder,
unsigned *  bbindex_to_postorder,
int  n_blocks 
   Main dataflow solver loop.

   DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we
   need to visit.
   BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and
   BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder position.
   PENDING will be freed.

   The worklists are bitmaps indexed by postorder positions.  

   The function implements standard algorithm for dataflow solving with two
   worklists (we are processing WORKLIST and storing new BBs to visit in

   As an optimization we maintain ages when BB was changed (stored in bb->aux)
   and when it was last visited (stored in last_visit_age).  This avoids need
   to re-do confluence function for edges to basic blocks whose source
   did not change since destination was visited last time.  
     Double-queueing. Worklist is for the current iteration,
     and pending is for the next. 
         Swap pending and worklist. 
     Dump statistics. 
static bool df_worklist_propagate_backward ( struct dataflow dataflow,
unsigned  bb_index,
unsigned *  bbindex_to_postorder,
bitmap  pending,
sbitmap  considered,
ptrdiff_t  age 
   Helper function for df_worklist_dataflow.
   Propagate the dataflow backward.  
      Calculate <conf_op> of incoming edges.  
         The out set of this block has changed.
         Propagate to the outgoing blocks.  
static bool df_worklist_propagate_forward ( struct dataflow dataflow,
unsigned  bb_index,
unsigned *  bbindex_to_postorder,
bitmap  pending,
sbitmap  considered,
ptrdiff_t  age 
   Helper function for df_worklist_dataflow.
   Propagate the dataflow forward.
   Given a BB_INDEX, do the dataflow propagation
   and set bits on for successors in PENDING
   if the out set of the dataflow has changed.

   AGE specify time when BB was visited last time.
   AGE of 0 means we are visiting for first time and need to
   compute transfer function to initialize datastructures.
   Otherwise we re-do transfer function only if something change
   while computing confluence functions.
   We need to compute confluence only of basic block that are younger
   then last visit of the BB.

   Return true if BB info has changed.  This is always the case
   in the first visit.  
      Calculate <conf_op> of incoming edges.  
         The out set of this block has changed.
         Propagate to the outgoing blocks.  
void dump_regset ( )
   Write information about registers and basic blocks into FILE.
   This is part of making a debugging dump.  
static bool gate_no_opt ( )
static bool gate_opt ( )
rtl_opt_pass* make_pass_df_initialize_no_opt ( )
rtl_opt_pass* make_pass_df_initialize_opt ( )
static unsigned int rest_of_handle_df_finish ( )
   Free all the dataflow info and the DF structure.  This should be
   called from the df_finish macro which also NULLs the parm.  
static unsigned int rest_of_handle_df_initialize ( )
   Set up the dataflow instance for the entire back end.  
     Set this to a conservative value.  Stack_ptr_mod will compute it
     correctly later.  
     These three problems are permanent.  
     After reload, some ports add certain bits to regs_ever_live so
     this cannot be reset.  

Variable Documentation

bitmap_obstack df_bitmap_obstack
   An obstack for bitmap not related to specific dataflow problems.
   This obstack should e.g. be used for bitmaps with a short life time
   such as temporary bitmaps.  

Referenced by df_get_eh_block_artificial_uses(), df_insn_rescan_debug_internal(), and df_lr_verify_solution_end().

struct bitmap_obstack reg_obstack
   The obstack on which regsets are allocated.  

Referenced by get_stored_val(), and remove_pseudos().

int* saved_cfg = NULL

Referenced by df_bb_delete(), and df_verify().

struct dataflow user_dflow
struct df_problem user_problem