diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/df-core.c')
-rw-r--r-- | gcc-4.2.1-5666.3/gcc/df-core.c | 1337 |
1 files changed, 0 insertions, 1337 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/df-core.c b/gcc-4.2.1-5666.3/gcc/df-core.c deleted file mode 100644 index 7f89fccdf..000000000 --- a/gcc-4.2.1-5666.3/gcc/df-core.c +++ /dev/null @@ -1,1337 +0,0 @@ -/* 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 <conf_op> of predecessor_outs. */ - if (EDGE_COUNT (bb->preds) > 0) - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (!TEST_BIT (dataflow->considered, e->src->index)) - continue; - - dataflow->problem->con_fun_n (dataflow, e); - } - else if (dataflow->problem->con_fun_0) - dataflow->problem->con_fun_0 (dataflow, bb); - - result_changed = dataflow->problem->trans_fun (dataflow, i); - - if (!result_changed || single_pass) - return; - - FOR_EACH_EDGE (e, ei, bb->succs) - { - if (e->dest->index == i) - continue; - if (!TEST_BIT (dataflow->considered, e->dest->index)) - continue; - SET_BIT (dataflow->pending, e->dest->index); - } - - FOR_EACH_EDGE (e, ei, bb->succs) - { - if (e->dest->index == i) - continue; - - if (!TEST_BIT (dataflow->considered, e->dest->index)) - continue; - if (!TEST_BIT (dataflow->visited, e->dest->index)) - df_hybrid_search_forward (e->dest, dataflow, single_pass); - } -} - -static void -df_hybrid_search_backward (basic_block bb, - struct dataflow *dataflow, - bool single_pass) -{ - int result_changed; - int i = bb->index; - edge e; - edge_iterator ei; - - SET_BIT (dataflow->visited, bb->index); - gcc_assert (TEST_BIT (dataflow->pending, bb->index)); - RESET_BIT (dataflow->pending, i); - - /* Calculate <conf_op> of predecessor_outs. */ - if (EDGE_COUNT (bb->succs) > 0) - FOR_EACH_EDGE (e, ei, bb->succs) - { - if (!TEST_BIT (dataflow->considered, e->dest->index)) - continue; - - dataflow->problem->con_fun_n (dataflow, e); - } - else if (dataflow->problem->con_fun_0) - dataflow->problem->con_fun_0 (dataflow, bb); - - result_changed = dataflow->problem->trans_fun (dataflow, i); - - if (!result_changed || single_pass) - return; - - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (e->src->index == i) - continue; - - if (!TEST_BIT (dataflow->considered, e->src->index)) - continue; - - SET_BIT (dataflow->pending, e->src->index); - } - - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (e->src->index == i) - continue; - - if (!TEST_BIT (dataflow->considered, e->src->index)) - continue; - - if (!TEST_BIT (dataflow->visited, e->src->index)) - df_hybrid_search_backward (e->src, dataflow, single_pass); - } -} - - -/* This function will perform iterative bitvector dataflow described - by DATAFLOW, producing the in and out sets. Only the part of the - cfg induced by blocks in DATAFLOW->order is taken into account. - - SINGLE_PASS is true if you just want to make one pass over the - blocks. */ - -void -df_iterative_dataflow (struct dataflow *dataflow, - bitmap blocks_to_consider, bitmap blocks_to_init, - int *blocks_in_postorder, int n_blocks, - bool single_pass) -{ - unsigned int idx; - int i; - sbitmap visited = sbitmap_alloc (last_basic_block); - sbitmap pending = sbitmap_alloc (last_basic_block); - sbitmap considered = sbitmap_alloc (last_basic_block); - bitmap_iterator bi; - - dataflow->visited = visited; - dataflow->pending = pending; - dataflow->considered = considered; - - sbitmap_zero (visited); - sbitmap_zero (pending); - sbitmap_zero (considered); - - gcc_assert (dataflow->problem->dir); - - EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi) - { - SET_BIT (considered, idx); - } - - for (i = 0; i < n_blocks; i++) - { - idx = blocks_in_postorder[i]; - SET_BIT (pending, idx); - }; - - dataflow->problem->init_fun (dataflow, blocks_to_init); - - while (1) - { - - /* For forward problems, you want to pass in reverse postorder - and for backward problems you want postorder. This has been - shown to be as good as you can do by several people, the - first being Mathew Hecht in his phd dissertation. - - The nodes are passed into this function in postorder. */ - - if (dataflow->problem->dir == DF_FORWARD) - { - for (i = n_blocks - 1 ; i >= 0 ; i--) - { - idx = blocks_in_postorder[i]; - - if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx)) - df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass); - } - } - else - { - for (i = 0; i < n_blocks; i++) - { - idx = blocks_in_postorder[i]; - - if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx)) - df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass); - } - } - - if (sbitmap_first_set_bit (pending) == -1) - break; - - sbitmap_zero (visited); - } - - sbitmap_free (pending); - sbitmap_free (visited); - sbitmap_free (considered); -} - - -/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving - the order of the remaining entries. Returns the length of the resulting - list. */ - -static unsigned -df_prune_to_subcfg (int list[], unsigned len, bitmap blocks) -{ - unsigned act, last; - - for (act = 0, last = 0; act < len; act++) - if (bitmap_bit_p (blocks, list[act])) - list[last++] = list[act]; - - return last; -} - - -/* Execute dataflow analysis on a single dataflow problem. - - There are three sets of blocks passed in: - - BLOCKS_TO_CONSIDER are the blocks whose solution can either be - examined or will be computed. For calls from DF_ANALYZE, this is - the set of blocks that has been passed to DF_SET_BLOCKS. For calls - from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of - blocks in the fringe (the set of blocks passed in plus the set of - immed preds and succs of those blocks). - - BLOCKS_TO_INIT are the blocks whose solution will be changed by - this iteration. For calls from DF_ANALYZE, this is the set of - blocks that has been passed to DF_SET_BLOCKS. For calls from - DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks - passed in. - - BLOCKS_TO_SCAN are the set of blocks that need to be rescanned. - For calls from DF_ANALYZE, this is the accumulated set of blocks - that has been passed to DF_RESCAN_BLOCKS since the last call to - DF_ANALYZE. For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, - this is the set of blocks passed in. - - blocks_to_consider blocks_to_init blocks_to_scan - full redo all all all - partial redo all all sub - small fixup fringe sub sub -*/ - -void -df_analyze_problem (struct dataflow *dflow, - bitmap blocks_to_consider, - bitmap blocks_to_init, - bitmap blocks_to_scan, - int *postorder, int n_blocks, bool single_pass) -{ - /* (Re)Allocate the datastructures necessary to solve the problem. */ - if (dflow->problem->alloc_fun) - dflow->problem->alloc_fun (dflow, blocks_to_scan, blocks_to_init); - - /* Set up the problem and compute the local information. This - function is passed both the blocks_to_consider and the - blocks_to_scan because the RD and RU problems require the entire - function to be rescanned if they are going to be updated. */ - if (dflow->problem->local_compute_fun) - dflow->problem->local_compute_fun (dflow, blocks_to_consider, blocks_to_scan); - - /* Solve the equations. */ - if (dflow->problem->dataflow_fun) - dflow->problem->dataflow_fun (dflow, blocks_to_consider, blocks_to_init, - postorder, n_blocks, single_pass); - - /* Massage the solution. */ - if (dflow->problem->finalize_fun) - dflow->problem->finalize_fun (dflow, blocks_to_consider); -} - - -/* Analyze dataflow info for the basic blocks specified by the bitmap - BLOCKS, or for the whole CFG if BLOCKS is zero. */ - -void -df_analyze (struct df *df) -{ - int *postorder = XNEWVEC (int, last_basic_block); - bitmap current_all_blocks = BITMAP_ALLOC (NULL); - int n_blocks; - int i; - bool everything; - - n_blocks = post_order_compute (postorder, true); - - if (n_blocks != n_basic_blocks) - delete_unreachable_blocks (); - - for (i = 0; i < n_blocks; i++) - bitmap_set_bit (current_all_blocks, postorder[i]); - - /* No one called df_rescan_blocks, so do it. */ - if (!df->blocks_to_scan) - df_rescan_blocks (df, NULL); - - /* Make sure that we have pruned any unreachable blocks from these - sets. */ - bitmap_and_into (df->blocks_to_scan, current_all_blocks); - - if (df->blocks_to_analyze) - { - everything = false; - bitmap_and_into (df->blocks_to_analyze, current_all_blocks); - n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze); - BITMAP_FREE (current_all_blocks); - } - else - { - everything = true; - df->blocks_to_analyze = current_all_blocks; - current_all_blocks = NULL; - } - - /* Skip over the DF_SCAN problem. */ - for (i = 1; i < df->num_problems_defined; i++) - df_analyze_problem (df->problems_in_order[i], - df->blocks_to_analyze, df->blocks_to_analyze, - df->blocks_to_scan, - postorder, n_blocks, false); - - if (everything) - { - BITMAP_FREE (df->blocks_to_analyze); - df->blocks_to_analyze = NULL; - } - - BITMAP_FREE (df->blocks_to_scan); - df->blocks_to_scan = NULL; - free (postorder); -} - - - -/*---------------------------------------------------------------------------- - 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); -} |