/* Allocation for dataflow support routines. Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. Originally contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com) Major rewrite contributed by Danny Berlin (dberlin@dberlin.org) and Kenneth Zadeck (zadeck@naturalbridge.com). This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ /* OVERVIEW: The files in this collection (df*.c,df.h) provide a general framework for solving dataflow problems. The global dataflow is performed using a good implementation of iterative dataflow analysis. The file df-problems.c provides problem instance for the most common dataflow problems: reaching defs, upward exposed uses, live variables, uninitialized variables, def-use chains, and use-def chains. However, the interface allows other dataflow problems to be defined as well. USAGE: Here is an example of using the dataflow routines. struct df *df; df = df_init (init_flags); df_add_problem (df, problem, flags); df_set_blocks (df, blocks); df_rescan_blocks (df, blocks); df_analyze (df); df_dump (df, stderr); df_finish (df); DF_INIT simply creates a poor man's object (df) that needs to be passed to all the dataflow routines. df_finish destroys this object and frees up any allocated memory. There are three flags that can be passed to df_init, each of these flags controls the scanning of the rtl: DF_HARD_REGS means that the scanning is to build information about both pseudo registers and hardware registers. Without this information, the problems will be solved only on pseudo registers. DF_EQUIV_NOTES marks the uses present in EQUIV/EQUAL notes. DF_SUBREGS return subregs rather than the inner reg. DF_ADD_PROBLEM adds a problem, defined by an instance to struct df_problem, to the set of problems solved in this instance of df. All calls to add a problem for a given instance of df must occur before the first call to DF_RESCAN_BLOCKS, DF_SET_BLOCKS or DF_ANALYZE. For all of the problems defined in df-problems.c, there are convenience functions named DF_*_ADD_PROBLEM. Problems can be dependent on other problems. For instance, solving def-use or use-def chains is dependent on solving reaching definitions. As long as these dependencies are listed in the problem definition, the order of adding the problems is not material. Otherwise, the problems will be solved in the order of calls to df_add_problem. Note that it is not necessary to have a problem. In that case, df will just be used to do the scanning. DF_SET_BLOCKS is an optional call used to define a region of the function on which the analysis will be performed. The normal case is to analyze the entire function and no call to df_set_blocks is made. When a subset is given, the analysis behaves as if the function only contains those blocks and any edges that occur directly between the blocks in the set. Care should be taken to call df_set_blocks right before the call to analyze in order to eliminate the possibility that optimizations that reorder blocks invalidate the bitvector. DF_RESCAN_BLOCKS is an optional call that causes the scanner to be (re)run over the set of blocks passed in. If blocks is NULL, the entire function (or all of the blocks defined in df_set_blocks) is rescanned. If blocks contains blocks that were not defined in the call to df_set_blocks, these blocks are added to the set of blocks. DF_ANALYZE causes all of the defined problems to be (re)solved. It does not cause blocks to be (re)scanned at the rtl level unless no prior call is made to df_rescan_blocks. When DF_ANALYZE is completes, the IN and OUT sets for each basic block contain the computer information. The DF_*_BB_INFO macros can be used to access these bitvectors. DF_DUMP can then be called to dump the information produce to some file. DF_FINISH causes all of the datastructures to be cleaned up and freed. The df_instance is also freed and its pointer should be NULLed. Scanning produces a `struct df_ref' data structure (ref) is allocated for every register reference (def or use) and this records the insn and bb the ref is found within. The refs are linked together in chains of uses and defs for each insn and for each register. Each ref also has a chain field that links all the use refs for a def or all the def refs for a use. This is used to create use-def or def-use chains. Different optimizations have different needs. Ultimately, only register allocation and schedulers should be using the bitmaps produced for the live register and uninitialized register problems. The rest of the backend should be upgraded to using and maintaining the linked information such as def use or use def chains. PHILOSOPHY: While incremental bitmaps are not worthwhile to maintain, incremental chains may be perfectly reasonable. The fastest way to build chains from scratch or after significant modifications is to build reaching definitions (RD) and build the chains from this. However, general algorithms for maintaining use-def or def-use chains are not practical. The amount of work to recompute the chain any chain after an arbitrary change is large. However, with a modest amount of work it is generally possible to have the application that uses the chains keep them up to date. The high level knowledge of what is really happening is essential to crafting efficient incremental algorithms. As for the bit vector problems, there is no interface to give a set of blocks over with to resolve the iteration. In general, restarting a dataflow iteration is difficult and expensive. Again, the best way to keep the dataflow information up to data (if this is really what is needed) it to formulate a problem specific solution. There are fine grained calls for creating and deleting references from instructions in df-scan.c. However, these are not currently connected to the engine that resolves the dataflow equations. DATA STRUCTURES: The basic object is a DF_REF (reference) and this may either be a DEF (definition) or a USE of a register. These are linked into a variety of lists; namely reg-def, reg-use, insn-def, insn-use, def-use, and use-def lists. For example, the reg-def lists contain all the locations that define a given register while the insn-use lists contain all the locations that use a register. Note that the reg-def and reg-use chains are generally short for pseudos and long for the hard registers. ACCESSING REFS: There are 4 ways to obtain access to refs: 1) References are divided into two categories, REAL and ARTIFICIAL. REAL refs are associated with instructions. They are linked into either in the insn's defs list (accessed by the DF_INSN_DEFS or DF_INSN_UID_DEFS macros) or the insn's uses list (accessed by the DF_INSN_USES or DF_INSN_UID_USES macros). These macros produce a ref (or NULL), the rest of the list can be obtained by traversal of the NEXT_REF field (accessed by the DF_REF_NEXT_REF macro.) There is no significance to the ordering of the uses or refs in an instruction. ARTIFICIAL refs are associated with basic blocks. The heads of these lists can be accessed by calling get_artificial_defs or get_artificial_uses for the particular basic block. Artificial defs and uses are only there if DF_HARD_REGS was specified when the df instance was created. Artificial defs and uses occur both at the beginning and ends of blocks. For blocks that area at the destination of eh edges, the artificial uses and defs occur at the beginning. The defs relate to the registers specified in EH_RETURN_DATA_REGNO and the uses relate to the registers specified in ED_USES. Logically these defs and uses should really occur along the eh edge, but there is no convenient way to do this. Artificial edges that occur at the beginning of the block have the DF_REF_AT_TOP flag set. Artificial uses occur at the end of all blocks. These arise from the hard registers that are always live, such as the stack register and are put there to keep the code from forgetting about them. Artificial defs occur at the end of the entry block. These arise from registers that are live at entry to the function. 2) All of the uses and defs associated with each pseudo or hard register are linked in a bidirectional chain. These are called reg-use or reg_def chains. The first use (or def) for a register can be obtained using the DF_REG_USE_GET macro (or DF_REG_DEF_GET macro). Subsequent uses for the same regno can be obtained by following the next_reg field of the ref. In previous versions of this code, these chains were ordered. It has not been practical to continue this practice. 3) If def-use or use-def chains are built, these can be traversed to get to other refs. 4) An array of all of the uses (and an array of all of the defs) can be built. These arrays are indexed by the value in the id structure. These arrays are only lazily kept up to date, and that process can be expensive. To have these arrays built, call df_reorganize_refs. Note that the values in the id field of a ref may change across calls to df_analyze or df_reorganize refs. If the only use of this array is to find all of the refs, it is better to traverse all of the registers and then traverse all of reg-use or reg-def chains. NOTES: Embedded addressing side-effects, such as POST_INC or PRE_INC, generate both a use and a def. These are both marked read/write to show that they are dependent. For example, (set (reg 40) (mem (post_inc (reg 42)))) will generate a use of reg 42 followed by a def of reg 42 (both marked read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41)))) generates a use of reg 41 then a def of reg 41 (both marked read/write), even though reg 41 is decremented before it is used for the memory address in this second example. A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG for which the number of word_mode units covered by the outer mode is smaller than that covered by the inner mode, invokes a read-modify-write. operation. We generate both a use and a def and again mark them read/write. Paradoxical subreg writes do not leave a trace of the old content, so they are write-only operations. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" #include "rtl.h" #include "tm_p.h" #include "insn-config.h" #include "recog.h" #include "function.h" #include "regs.h" #include "output.h" #include "alloc-pool.h" #include "flags.h" #include "hard-reg-set.h" #include "basic-block.h" #include "sbitmap.h" #include "bitmap.h" #include "timevar.h" #include "df.h" #include "tree-pass.h" static struct df *ddf = NULL; struct df *shared_df = NULL; static void *df_get_bb_info (struct dataflow *, unsigned int); static void df_set_bb_info (struct dataflow *, unsigned int, void *); /*---------------------------------------------------------------------------- Functions to create, destroy and manipulate an instance of df. ----------------------------------------------------------------------------*/ /* Initialize dataflow analysis and allocate and initialize dataflow memory. */ struct df * df_init (int flags) { struct df *df = XCNEW (struct df); /* This is executed once per compilation to initialize platform specific data structures. */ df_hard_reg_init (); /* All df instance must define the scanning problem. */ df_scan_add_problem (df, flags); ddf = df; return df; } /* Add PROBLEM to the DF instance. */ struct dataflow * df_add_problem (struct df *df, struct df_problem *problem, int flags) { struct dataflow *dflow; /* First try to add the dependent problem. */ if (problem->dependent_problem_fun) (problem->dependent_problem_fun) (df, 0); /* Check to see if this problem has already been defined. If it has, just return that instance, if not, add it to the end of the vector. */ dflow = df->problems_by_index[problem->id]; if (dflow) return dflow; /* Make a new one and add it to the end. */ dflow = XCNEW (struct dataflow); dflow->flags = flags; dflow->df = df; dflow->problem = problem; df->problems_in_order[df->num_problems_defined++] = dflow; df->problems_by_index[dflow->problem->id] = dflow; return dflow; } /* Set the MASK flags in the DFLOW problem. The old flags are returned. If a flag is not allowed to be changed this will fail if checking is enabled. */ int df_set_flags (struct dataflow *dflow, int mask) { int old_flags = dflow->flags; gcc_assert (!(mask & (~dflow->problem->changeable_flags))); dflow->flags |= mask; return old_flags; } /* Clear the MASK flags in the DFLOW problem. The old flags are returned. If a flag is not allowed to be changed this will fail if checking is enabled. */ int df_clear_flags (struct dataflow *dflow, int mask) { int old_flags = dflow->flags; gcc_assert (!(mask & (~dflow->problem->changeable_flags))); dflow->flags &= !mask; return old_flags; } /* Set the blocks that are to be considered for analysis. If this is not called or is called with null, the entire function in analyzed. */ void df_set_blocks (struct df *df, bitmap blocks) { if (blocks) { if (df->blocks_to_analyze) { int p; bitmap diff = BITMAP_ALLOC (NULL); bitmap_and_compl (diff, df->blocks_to_analyze, blocks); for (p = df->num_problems_defined - 1; p >= 0 ;p--) { struct dataflow *dflow = df->problems_in_order[p]; if (dflow->problem->reset_fun) dflow->problem->reset_fun (dflow, df->blocks_to_analyze); else if (dflow->problem->free_bb_fun) { bitmap_iterator bi; unsigned int bb_index; EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi) { basic_block bb = BASIC_BLOCK (bb_index); if (bb) { dflow->problem->free_bb_fun (dflow, bb, df_get_bb_info (dflow, bb_index)); df_set_bb_info (dflow, bb_index, NULL); } } } } BITMAP_FREE (diff); } else { /* If we have not actually run scanning before, do not try to clear anything. */ struct dataflow *scan_dflow = df->problems_by_index [DF_SCAN]; if (scan_dflow->problem_data) { bitmap blocks_to_reset = NULL; int p; for (p = df->num_problems_defined - 1; p >= 0 ;p--) { struct dataflow *dflow = df->problems_in_order[p]; if (dflow->problem->reset_fun) { if (!blocks_to_reset) { basic_block bb; blocks_to_reset = BITMAP_ALLOC (NULL); FOR_ALL_BB(bb) { bitmap_set_bit (blocks_to_reset, bb->index); } } dflow->problem->reset_fun (dflow, blocks_to_reset); } } if (blocks_to_reset) BITMAP_FREE (blocks_to_reset); } df->blocks_to_analyze = BITMAP_ALLOC (NULL); } bitmap_copy (df->blocks_to_analyze, blocks); } else { if (df->blocks_to_analyze) { BITMAP_FREE (df->blocks_to_analyze); df->blocks_to_analyze = NULL; } } } /* Free all of the per basic block dataflow from all of the problems. This is typically called before a basic block is deleted and the problem will be reanalyzed. */ void df_delete_basic_block (struct df *df, int bb_index) { basic_block bb = BASIC_BLOCK (bb_index); int i; for (i = 0; i < df->num_problems_defined; i++) { struct dataflow *dflow = df->problems_in_order[i]; if (dflow->problem->free_bb_fun) dflow->problem->free_bb_fun (dflow, bb, df_get_bb_info (dflow, bb_index)); } } /* Free all the dataflow info and the DF structure. This should be called from the df_finish macro which also NULLs the parm. */ void df_finish1 (struct df *df) { int i; for (i = 0; i < df->num_problems_defined; i++) df->problems_in_order[i]->problem->free_fun (df->problems_in_order[i]); free (df); } /*---------------------------------------------------------------------------- The general data flow analysis engine. ----------------------------------------------------------------------------*/ /* Hybrid search algorithm from "Implementation Techniques for Efficient Data-Flow Analysis of Large Programs". */ static void df_hybrid_search_forward (basic_block bb, struct dataflow *dataflow, bool single_pass) { int result_changed; int i = bb->index; edge e; edge_iterator ei; SET_BIT (dataflow->visited, bb->index); gcc_assert (TEST_BIT (dataflow->pending, bb->index)); RESET_BIT (dataflow->pending, i); /* Calculate of predecessor_outs. */ if (EDGE_COUNT (bb->preds) > 0) FOR_EACH_EDGE (e, ei, bb->preds) { if (!TEST_BIT (dataflow->considered, e->src->index)) continue; dataflow->problem->con_fun_n (dataflow, e); } else if (dataflow->problem->con_fun_0) dataflow->problem->con_fun_0 (dataflow, bb); result_changed = dataflow->problem->trans_fun (dataflow, i); if (!result_changed || single_pass) return; FOR_EACH_EDGE (e, ei, bb->succs) { if (e->dest->index == i) continue; if (!TEST_BIT (dataflow->considered, e->dest->index)) continue; SET_BIT (dataflow->pending, e->dest->index); } FOR_EACH_EDGE (e, ei, bb->succs) { if (e->dest->index == i) continue; if (!TEST_BIT (dataflow->considered, e->dest->index)) continue; if (!TEST_BIT (dataflow->visited, e->dest->index)) df_hybrid_search_forward (e->dest, dataflow, single_pass); } } static void df_hybrid_search_backward (basic_block bb, struct dataflow *dataflow, bool single_pass) { int result_changed; int i = bb->index; edge e; edge_iterator ei; SET_BIT (dataflow->visited, bb->index); gcc_assert (TEST_BIT (dataflow->pending, bb->index)); RESET_BIT (dataflow->pending, i); /* Calculate of predecessor_outs. */ if (EDGE_COUNT (bb->succs) > 0) FOR_EACH_EDGE (e, ei, bb->succs) { if (!TEST_BIT (dataflow->considered, e->dest->index)) continue; dataflow->problem->con_fun_n (dataflow, e); } else if (dataflow->problem->con_fun_0) dataflow->problem->con_fun_0 (dataflow, bb); result_changed = dataflow->problem->trans_fun (dataflow, i); if (!result_changed || single_pass) return; FOR_EACH_EDGE (e, ei, bb->preds) { if (e->src->index == i) continue; if (!TEST_BIT (dataflow->considered, e->src->index)) continue; SET_BIT (dataflow->pending, e->src->index); } FOR_EACH_EDGE (e, ei, bb->preds) { if (e->src->index == i) continue; if (!TEST_BIT (dataflow->considered, e->src->index)) continue; if (!TEST_BIT (dataflow->visited, e->src->index)) df_hybrid_search_backward (e->src, dataflow, single_pass); } } /* This function will perform iterative bitvector dataflow described by DATAFLOW, producing the in and out sets. Only the part of the cfg induced by blocks in DATAFLOW->order is taken into account. SINGLE_PASS is true if you just want to make one pass over the blocks. */ void df_iterative_dataflow (struct dataflow *dataflow, bitmap blocks_to_consider, bitmap blocks_to_init, int *blocks_in_postorder, int n_blocks, bool single_pass) { unsigned int idx; int i; sbitmap visited = sbitmap_alloc (last_basic_block); sbitmap pending = sbitmap_alloc (last_basic_block); sbitmap considered = sbitmap_alloc (last_basic_block); bitmap_iterator bi; dataflow->visited = visited; dataflow->pending = pending; dataflow->considered = considered; sbitmap_zero (visited); sbitmap_zero (pending); sbitmap_zero (considered); gcc_assert (dataflow->problem->dir); EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi) { SET_BIT (considered, idx); } for (i = 0; i < n_blocks; i++) { idx = blocks_in_postorder[i]; SET_BIT (pending, idx); }; dataflow->problem->init_fun (dataflow, blocks_to_init); while (1) { /* For forward problems, you want to pass in reverse postorder and for backward problems you want postorder. This has been shown to be as good as you can do by several people, the first being Mathew Hecht in his phd dissertation. The nodes are passed into this function in postorder. */ if (dataflow->problem->dir == DF_FORWARD) { for (i = n_blocks - 1 ; i >= 0 ; i--) { idx = blocks_in_postorder[i]; if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx)) df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass); } } else { for (i = 0; i < n_blocks; i++) { idx = blocks_in_postorder[i]; if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx)) df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass); } } if (sbitmap_first_set_bit (pending) == -1) break; sbitmap_zero (visited); } sbitmap_free (pending); sbitmap_free (visited); sbitmap_free (considered); } /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving the order of the remaining entries. Returns the length of the resulting list. */ static unsigned df_prune_to_subcfg (int list[], unsigned len, bitmap blocks) { unsigned act, last; for (act = 0, last = 0; act < len; act++) if (bitmap_bit_p (blocks, list[act])) list[last++] = list[act]; return last; } /* Execute dataflow analysis on a single dataflow problem. There are three sets of blocks passed in: BLOCKS_TO_CONSIDER are the blocks whose solution can either be examined or will be computed. For calls from DF_ANALYZE, this is the set of blocks that has been passed to DF_SET_BLOCKS. For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks in the fringe (the set of blocks passed in plus the set of immed preds and succs of those blocks). BLOCKS_TO_INIT are the blocks whose solution will be changed by this iteration. For calls from DF_ANALYZE, this is the set of blocks that has been passed to DF_SET_BLOCKS. For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks passed in. BLOCKS_TO_SCAN are the set of blocks that need to be rescanned. For calls from DF_ANALYZE, this is the accumulated set of blocks that has been passed to DF_RESCAN_BLOCKS since the last call to DF_ANALYZE. For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks passed in. blocks_to_consider blocks_to_init blocks_to_scan full redo all all all partial redo all all sub small fixup fringe sub sub */ void df_analyze_problem (struct dataflow *dflow, bitmap blocks_to_consider, bitmap blocks_to_init, bitmap blocks_to_scan, int *postorder, int n_blocks, bool single_pass) { /* (Re)Allocate the datastructures necessary to solve the problem. */ if (dflow->problem->alloc_fun) dflow->problem->alloc_fun (dflow, blocks_to_scan, blocks_to_init); /* Set up the problem and compute the local information. This function is passed both the blocks_to_consider and the blocks_to_scan because the RD and RU problems require the entire function to be rescanned if they are going to be updated. */ if (dflow->problem->local_compute_fun) dflow->problem->local_compute_fun (dflow, blocks_to_consider, blocks_to_scan); /* Solve the equations. */ if (dflow->problem->dataflow_fun) dflow->problem->dataflow_fun (dflow, blocks_to_consider, blocks_to_init, postorder, n_blocks, single_pass); /* Massage the solution. */ if (dflow->problem->finalize_fun) dflow->problem->finalize_fun (dflow, blocks_to_consider); } /* Analyze dataflow info for the basic blocks specified by the bitmap BLOCKS, or for the whole CFG if BLOCKS is zero. */ void df_analyze (struct df *df) { int *postorder = XNEWVEC (int, last_basic_block); bitmap current_all_blocks = BITMAP_ALLOC (NULL); int n_blocks; int i; bool everything; n_blocks = post_order_compute (postorder, true); if (n_blocks != n_basic_blocks) delete_unreachable_blocks (); for (i = 0; i < n_blocks; i++) bitmap_set_bit (current_all_blocks, postorder[i]); /* No one called df_rescan_blocks, so do it. */ if (!df->blocks_to_scan) df_rescan_blocks (df, NULL); /* Make sure that we have pruned any unreachable blocks from these sets. */ bitmap_and_into (df->blocks_to_scan, current_all_blocks); if (df->blocks_to_analyze) { everything = false; bitmap_and_into (df->blocks_to_analyze, current_all_blocks); n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze); BITMAP_FREE (current_all_blocks); } else { everything = true; df->blocks_to_analyze = current_all_blocks; current_all_blocks = NULL; } /* Skip over the DF_SCAN problem. */ for (i = 1; i < df->num_problems_defined; i++) df_analyze_problem (df->problems_in_order[i], df->blocks_to_analyze, df->blocks_to_analyze, df->blocks_to_scan, postorder, n_blocks, false); if (everything) { BITMAP_FREE (df->blocks_to_analyze); df->blocks_to_analyze = NULL; } BITMAP_FREE (df->blocks_to_scan); df->blocks_to_scan = NULL; free (postorder); } /*---------------------------------------------------------------------------- Functions to support limited incremental change. ----------------------------------------------------------------------------*/ /* Get basic block info. */ static void * df_get_bb_info (struct dataflow *dflow, unsigned int index) { return (struct df_scan_bb_info *) dflow->block_info[index]; } /* Set basic block info. */ static void df_set_bb_info (struct dataflow *dflow, unsigned int index, void *bb_info) { dflow->block_info[index] = bb_info; } /* Called from the rtl_compact_blocks to reorganize the problems basic block info. */ void df_compact_blocks (struct df *df) { int i, p; basic_block bb; void **problem_temps; int size = last_basic_block *sizeof (void *); problem_temps = xmalloc (size); for (p = 0; p < df->num_problems_defined; p++) { struct dataflow *dflow = df->problems_in_order[p]; if (dflow->problem->free_bb_fun) { df_grow_bb_info (dflow); memcpy (problem_temps, dflow->block_info, size); /* Copy the bb info from the problem tmps to the proper place in the block_info vector. Null out the copied item. */ i = NUM_FIXED_BLOCKS; FOR_EACH_BB (bb) { df_set_bb_info (dflow, i, problem_temps[bb->index]); problem_temps[bb->index] = NULL; i++; } memset (dflow->block_info + i, 0, (last_basic_block - i) *sizeof (void *)); /* Free any block infos that were not copied (and NULLed). These are from orphaned blocks. */ for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++) { basic_block bb = BASIC_BLOCK (i); if (problem_temps[i] && bb) dflow->problem->free_bb_fun (dflow, bb, problem_temps[i]); } } } free (problem_temps); i = NUM_FIXED_BLOCKS; FOR_EACH_BB (bb) { SET_BASIC_BLOCK (i, bb); bb->index = i; i++; } gcc_assert (i == n_basic_blocks); for (; i < last_basic_block; i++) SET_BASIC_BLOCK (i, NULL); } /* Shove NEW_BLOCK in at OLD_INDEX. Called from if-cvt to hack a block. There is no excuse for people to do this kind of thing. */ void df_bb_replace (struct df *df, int old_index, basic_block new_block) { int p; for (p = 0; p < df->num_problems_defined; p++) { struct dataflow *dflow = df->problems_in_order[p]; if (dflow->block_info) { void *temp; df_grow_bb_info (dflow); /* The old switcheroo. */ temp = df_get_bb_info (dflow, old_index); df_set_bb_info (dflow, old_index, df_get_bb_info (dflow, new_block->index)); df_set_bb_info (dflow, new_block->index, temp); } } SET_BASIC_BLOCK (old_index, new_block); new_block->index = old_index; } /*---------------------------------------------------------------------------- PUBLIC INTERFACES TO QUERY INFORMATION. ----------------------------------------------------------------------------*/ /* Return last use of REGNO within BB. */ struct df_ref * df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno) { rtx insn; struct df_ref *use; unsigned int uid; FOR_BB_INSNS_REVERSE (bb, insn) { if (!INSN_P (insn)) continue; uid = INSN_UID (insn); for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref) if (DF_REF_REGNO (use) == regno) return use; } return NULL; } /* Return first def of REGNO within BB. */ struct df_ref * df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno) { rtx insn; struct df_ref *def; unsigned int uid; FOR_BB_INSNS (bb, insn) { if (!INSN_P (insn)) continue; uid = INSN_UID (insn); for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) if (DF_REF_REGNO (def) == regno) return def; } return NULL; } /* Return last def of REGNO within BB. */ struct df_ref * df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno) { rtx insn; struct df_ref *def; unsigned int uid; FOR_BB_INSNS_REVERSE (bb, insn) { if (!INSN_P (insn)) continue; uid = INSN_UID (insn); for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) if (DF_REF_REGNO (def) == regno) return def; } return NULL; } /* Return true if INSN defines REGNO. */ bool df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno) { unsigned int uid; struct df_ref *def; uid = INSN_UID (insn); for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) if (DF_REF_REGNO (def) == regno) return true; return false; } /* Finds the reference corresponding to the definition of REG in INSN. DF is the dataflow object. */ struct df_ref * df_find_def (struct df *df, rtx insn, rtx reg) { unsigned int uid; struct df_ref *def; if (GET_CODE (reg) == SUBREG) reg = SUBREG_REG (reg); gcc_assert (REG_P (reg)); uid = INSN_UID (insn); for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) if (rtx_equal_p (DF_REF_REAL_REG (def), reg)) return def; return NULL; } /* Return true if REG is defined in INSN, zero otherwise. */ bool df_reg_defined (struct df *df, rtx insn, rtx reg) { return df_find_def (df, insn, reg) != NULL; } /* Finds the reference corresponding to the use of REG in INSN. DF is the dataflow object. */ struct df_ref * df_find_use (struct df *df, rtx insn, rtx reg) { unsigned int uid; struct df_ref *use; if (GET_CODE (reg) == SUBREG) reg = SUBREG_REG (reg); gcc_assert (REG_P (reg)); uid = INSN_UID (insn); for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref) if (rtx_equal_p (DF_REF_REAL_REG (use), reg)) return use; return NULL; } /* Return true if REG is referenced in INSN, zero otherwise. */ bool df_reg_used (struct df *df, rtx insn, rtx reg) { return df_find_use (df, insn, reg) != NULL; } /*---------------------------------------------------------------------------- Debugging and printing functions. ----------------------------------------------------------------------------*/ /* Dump dataflow info. */ void df_dump (struct df *df, FILE *file) { int i; if (!df || !file) return; fprintf (file, "\n\n%s\n", current_function_name ()); fprintf (file, "\nDataflow summary:\n"); fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n", df->def_info.bitmap_size, df->use_info.bitmap_size); for (i = 0; i < df->num_problems_defined; i++) df->problems_in_order[i]->problem->dump_fun (df->problems_in_order[i], file); fprintf (file, "\n"); } void df_refs_chain_dump (struct df_ref *ref, bool follow_chain, FILE *file) { fprintf (file, "{ "); while (ref) { fprintf (file, "%c%d(%d) ", DF_REF_REG_DEF_P (ref) ? 'd' : 'u', DF_REF_ID (ref), DF_REF_REGNO (ref)); if (follow_chain) df_chain_dump (DF_REF_CHAIN (ref), file); ref = ref->next_ref; } fprintf (file, "}"); } /* Dump either a ref-def or reg-use chain. */ void df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref, FILE *file) { fprintf (file, "{ "); while (ref) { fprintf (file, "%c%d(%d) ", DF_REF_REG_DEF_P (ref) ? 'd' : 'u', DF_REF_ID (ref), DF_REF_REGNO (ref)); ref = ref->next_reg; } fprintf (file, "}"); } static void df_mws_dump (struct df_mw_hardreg *mws, FILE *file) { while (mws) { struct df_link *regs = mws->regs; fprintf (file, "%c%d(", (mws->type == DF_REF_REG_DEF) ? 'd' : 'u', DF_REF_REGNO (regs->ref)); while (regs) { fprintf (file, "%d ", DF_REF_REGNO (regs->ref)); regs = regs->next; } fprintf (file, ") "); mws = mws->next; } } static void df_insn_uid_debug (struct df *df, unsigned int uid, bool follow_chain, FILE *file) { int bbi; if (DF_INSN_UID_DEFS (df, uid)) bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid)); else if (DF_INSN_UID_USES(df, uid)) bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid)); else bbi = -1; fprintf (file, "insn %d bb %d luid %d", uid, bbi, DF_INSN_UID_LUID (df, uid)); if (DF_INSN_UID_DEFS (df, uid)) { fprintf (file, " defs "); df_refs_chain_dump (DF_INSN_UID_DEFS (df, uid), follow_chain, file); } if (DF_INSN_UID_USES (df, uid)) { fprintf (file, " uses "); df_refs_chain_dump (DF_INSN_UID_USES (df, uid), follow_chain, file); } if (DF_INSN_UID_MWS (df, uid)) { fprintf (file, " mws "); df_mws_dump (DF_INSN_UID_MWS (df, uid), file); } fprintf (file, "\n"); } void df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file) { df_insn_uid_debug (df, INSN_UID (insn), follow_chain, file); } void df_insn_debug_regno (struct df *df, rtx insn, FILE *file) { unsigned int uid; int bbi; uid = INSN_UID (insn); if (DF_INSN_UID_DEFS (df, uid)) bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid)); else if (DF_INSN_UID_USES(df, uid)) bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid)); else bbi = -1; fprintf (file, "insn %d bb %d luid %d defs ", uid, bbi, DF_INSN_LUID (df, insn)); df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file); fprintf (file, " uses "); df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file); fprintf (file, "\n"); } void df_regno_debug (struct df *df, unsigned int regno, FILE *file) { fprintf (file, "reg %d defs ", regno); df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file); fprintf (file, " uses "); df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file); fprintf (file, "\n"); } void df_ref_debug (struct df_ref *ref, FILE *file) { fprintf (file, "%c%d ", DF_REF_REG_DEF_P (ref) ? 'd' : 'u', DF_REF_ID (ref)); fprintf (file, "reg %d bb %d insn %d flag %x chain ", DF_REF_REGNO (ref), DF_REF_BBNO (ref), DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1, DF_REF_FLAGS (ref)); df_chain_dump (DF_REF_CHAIN (ref), file); fprintf (file, "\n"); } /* Functions for debugging from GDB. */ void debug_df_insn (rtx insn) { df_insn_debug (ddf, insn, true, stderr); debug_rtx (insn); } void debug_df_reg (rtx reg) { df_regno_debug (ddf, REGNO (reg), stderr); } void debug_df_regno (unsigned int regno) { df_regno_debug (ddf, regno, stderr); } void debug_df_ref (struct df_ref *ref) { df_ref_debug (ref, stderr); } void debug_df_defno (unsigned int defno) { df_ref_debug (DF_DEFS_GET (ddf, defno), stderr); } void debug_df_useno (unsigned int defno) { df_ref_debug (DF_USES_GET (ddf, defno), stderr); } void debug_df_chain (struct df_link *link) { df_chain_dump (link, stderr); fputc ('\n', stderr); }