From e011eba9edce426cbde12b0b43cd4b274b2172d0 Mon Sep 17 00:00:00 2001 From: zadeck Date: Wed, 11 Jan 2006 12:57:18 +0000 Subject: 2005-01-11 Danny Berlin Kenneth Zadeck * df.h (DF_SCAN, DF_RU, DF_RD, DF_LR, DF_UR, DF_UREC, DF_CHAIN, DF_RI, DF_LAST_PROBLEM_PLUS1, DF_DU_CHAIN, DF_UD_CHAIN, DF_REF_TYPE_NAMES, DF_HARD_REGS, DF_EQUIV_NOTES, DF_SUBREGS, DF_SCAN_BB_INFO, DF_RU_BB_INFO, DF_RD_BB_INFO, DF_LR_BB_INFO, DF_UR_BB_INFO, DF_UREC_BB_INFO, DF_LIVE_IN, DF_LIVE_OUT, DF_RA_LIVE_IN, DF_RA_LIVE_OUT, DF_UPWARD_LIVE_IN, DF_UPWARD_LIVE_OUT, DF_REF_REAL_REG, DF_REF_REGNO, DF_REF_REAL_LOC, DF_REF_REG, DF_REF_LOC, DF_REF_BB, DF_REF_BBNO, DF_REF_INSN, DF_REF_INSN_UID, DF_REF_TYPE, DF_REF_CHAIN, DF_REF_ID, DF_REF_FLAGS, DF_REF_NEXT_REG, DF_REF_PREV_REG, DF_REF_NEXT_REF, DF_REF_DATA, DF_REF_REG_DEF_P, DF_REF_REG_USE_P, DF_REF_REG_MEM_STORE_P, DF_REF_REG_MEM_LOAD_P, DF_REF_REG_MEM_P, DF_DEFS_SIZE, DF_DEFS_GET, DF_DEFS_SET, DF_USES_SIZE, DF_USES_GET, DF_USES_SET, DF_REG_SIZE, DF_REG_DEF_GET, DF_REG_DEF_SET, DF_REG_USE_GET, DF_REG_USE_SET, DF_REGNO_FIRST_DEF, DF_REGNO_LAST_USE, DF_INSN_SIZE, DF_INSN_GET, DF_INSN_SET, DF_INSN_CONTAINS_ASM, DF_INSN_LUID, DF_INSN_DEFS, DF_INSN_USES, DF_INSN_UID_GET, DF_INSN_UID_LUID, DF_INSN_UID_DEFS, DF_INSN_UID_USES, DF_SCAN_INITIAL, DF_SCAN_GLOBAL, DF_SCAN_POST_ALLOC): New macros. (df_flow_dir, df_ref_type, df_ref_flags, df_alloc_function, df_free_bb_function, df_local_compute_function, df_init_function, df_dataflow_function, df_confluence_function_0, df_confluence_function_n, df_transfer_function, df_finalizer_function, df_free_function, df_dump_problem_function, df_problem, dataflow, df_insn_info, df_reg_info, df_ref, df_link, df_ref_info, df, df_map, df_scan_bb_info, df_ru_bb_info, df_ru_bb_info, df_rd_bb_info, df_lr_bb_info, df_ur_bb_info, df_urec_bb_info, ) New types. (df_invalidated_by_call, df_all_hard_regs, df_state) New public variables. (df_init, df_add_problem, df_set_blocks, df_finish, df_analyze, df_analyze_simple_change_some_blocks, df_analyze_simple_change_one_block, df_compact_blocks, df_bb_replace, df_bb_regno_last_use_find, df_bb_regno_first_def_find, df_bb_regno_last_def_find, df_insn_regno_def_p, df_find_def, df_find_use, df_iterative_dataflow, df_dump, df_chain_dump, df_refs_chain_dump, df_regs_chain_dump, df_insn_debug, df_insn_debug_regno, df_regno_debug, df_ref_debug, debug_df_insn, debug_df_regno, debug_df_reg, debug_df_defno, debug_df_useno, debug_df_ref, debug_df_chain, df_get_dependent_problem, df_chain_create, df_chain_unlink, df_chain_copy, df_get_live_in, df_get_live_out, df_grow_bb_info, df_chain_dump, df_print_bb_index, df_ru_add_problem, df_ru_get_bb_info, df_rd_add_problem, df_rd_get_bb_info, df_lr_add_problem, df_lr_get_bb_info, df_ur_add_problem, df_ur_get_bb_info, df_urec_add_problem, df_urec_get_bb_info, df_chain_add_problem, df_ri_add_problem, df_reg_lifetime, df_scan_get_bb_info, df_scan_add_problem, df_rescan_blocks, df_ref_create, df_get_artificial_defs, df_get_artificial_uses, df_reg_chain_create, df_reg_chain_unlink, df_ref_remove, df_insn_refs_delete, df_refs_delete, df_reorganize_refs, df_set_state, df_hard_reg_init, df_read_modify_subreg_p) New public functions. * df-core.c: The core dataflow solver and glue routines for rtl dataflow. (df_init, df_add_problem, df_set_blocks, df_finish, df_hybrid_search_forward, df_hybrid_search_backward, df_iterative_dataflow, df_prune_to_subcfg, df_analyze_problem, df_analyze, df_get_bb_info, df_set_bb_info, df_bb_replace, df_bb_regno_last_use_find, df_bb_regno_first_def_find, df_bb_regno_last_def_find, df_insn_regno_def_p, df_find_def, df_reg_defined, df_find_use, df_reg_used, df_dump, df_refs_chain_dump, df_regs_chain_dump, df_insn_debug, df_insn_debug_regno, df_regno_debug, df_ref_debug, debug_df_insn, debug_df_reg, debug_df_regno, debug_df_ref debug_df_defno, debug_df_useno, reset_df_after_reload): New functions. * df-scan.c: The scanning fuctions, once in df.c, completely rewritten so that they now fully model the functionality of register usage at the backend. (df_scan_free_internal, df_scan_get_bb_info, df_scan_set_bb_info, df_scan_free_bb_info, df_scan_alloc, df_scan_free, df_scan_dump, df_scan_add_problem, df_grow_reg_info, df_grow_ref_info, df_grow_insn_info, df_rescan_blocks, df_ref_create, df_get_artificial_defs, df_get_artificial_uses, df_reg_chain_create, df_ref_unlink, df_reg_chain_unlink, df_ref_remove, df_insn_create_insn_record, df_insn_refs_delete, df_refs_delete, df_reorganize_refs, df_set_state, df_ref_create_structure, df_ref_record, df_read_modify_subreg_p, df_def_record_1, df_defs_record, df_uses_record, df_insn_contains_asm_1, df_insn_contains_asm, df_insn_refs_record, df_has_eh_preds, df_bb_refs_record, df_refs_record, df_mark_reg, df_record_exit_block_uses, df_hard_reg_init): New functions. * df-problems.c: Seven concrete dataflow problems that use the scanning in df-scan.c and are solved by the engine in df-core.c. (df_get_dependent_problem, df_chain_create, df_chain_unlink, df_chain_copy, df_get_live_in, df_get_live_out, df_grow_bb_info, df_chain_dump, df_print_bb_index, df_ref_bitmap, df_set_seen, df_unset_seen, df_ru_get_bb_info, df_ru_set_bb_info, df_ru_free_bb_info, df_ru_alloc, df_ru_bb_local_compute_process_def, df_ru_bb_local_compute_process_use, df_ru_bb_local_compute, df_ru_local_compute, df_ru_init_solution, df_ru_confluence_n, df_ru_transfer_function, df_ru_free, df_ru_dump, df_ru_add_problem, df_rd_get_bb_info, df_rd_set_bb_info, df_rd_free_bb_info, df_rd_alloc, df_rd_bb_local_compute_process_def, df_rd_bb_local_compute, df_rd_local_compute, df_rd_init_solution, df_rd_confluence_n, df_rd_transfer_function, df_rd_free, df_rd_dump, df_rd_add_problem, df_lr_get_bb_info, df_lr_set_bb_info, df_lr_free_bb_info, df_lr_alloc, df_lr_bb_local_compute, df_lr_local_compute, df_lr_init, df_lr_confluence_0, df_lr_confluence_n, df_lr_transfer_function, df_lr_free, df_lr_dump, df_lr_add_problem, df_ur_get_bb_info, df_ur_set_bb_info, df_ur_free_bb_info, df_ur_alloc, df_ur_bb_local_compute, df_ur_local_compute, df_ur_init, df_ur_local_finalize, df_ur_confluence_n, df_ur_transfer_function, df_ur_free, df_ur_dump, df_ur_add_problem, df_urec_get_bb_info, df_urec_set_bb_info, df_urec_free_bb_info, df_urec_alloc, df_urec_mark_reg_change, df_urec_check_earlyclobber, df_urec_mark_reg_use_for_earlyclobber, df_urec_mark_reg_use_for_earlyclobber_1, df_urec_bb_local_compute, df_urec_local_compute, df_urec_init, df_urec_local_finalize, df_urec_confluence_n, df_urec_transfer_function, df_urec_free, df_urec_dump, df_urec_add_problem, df_chain_alloc, df_chain_create_bb_process_use, df_chain_create_bb, df_chain_finalize, df_chain_free, df_chains_dump, df_chain_add_problem, df_ri_alloc, df_ri_bb_compute, df_ri_compute, df_ri_free, df_ri_dump, df_ri_add_problem, df_reg_lifetime): New functions. * df.c: Deleted file. * ddg.c (create_ddg_dep_no_link, build_inter_loop_deps): Made code consistent with new df api. * modulo-sched.c (sms_schedule, rest_of_handle_sms, rest_of_handle_sms): Ditto. * web.c (unionfind_union, union_defs, entry_register, web_main): Ditto. * loop_invariant.c (invariant_for_use, hash_invariant_expr_1, invariant_expr_equal_p, find_defs, check_dependencies, find_invariant_insn, find_invariants_to_move, move_invariant_reg, free_inv_motion_data, move_loop_invariants): Ditto. * sched-deps.c (sched_analyze_1): Ditto. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@109577 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/df-core.c | 1164 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1164 insertions(+) create mode 100644 gcc/df-core.c (limited to 'gcc/df-core.c') diff --git a/gcc/df-core.c b/gcc/df-core.c new file mode 100644 index 00000000000..aef38cb4354 --- /dev/null +++ b/gcc/df-core.c @@ -0,0 +1,1164 @@ +/* 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); + + 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 two flags that can be passed to df_init: + +DF_NO_SCAN means that no scanning of the rtl code is performed. This +is used if the problem instance is to do it's own scanning. + +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_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 or DF_ANALYZE. + +For all of the problems defined in df-problems.c, there are +convienence functions named DF_*_ADD_PROBLEM. + + +Problems can be dependent on other problems. For instance, solving +def-use or use-def chains is dependant on solving reaching +definitions. As long as these dependancies 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 possiblity 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. + + +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 infomation 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 at the beginning blocks that are the + destination of eh edges. The defs come from the registers + specified in EH_RETURN_DATA_REGNO and the uses come from the + registers specified in ED_USES. Logically these defs and uses + should really occur along the eh edge, but there is no convienent + way to do this. Artificial edges that occur at the beginning of + the block have the DF_REF_AT_TOP flag set. + + Artificial uses also 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. + +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; + +/*---------------------------------------------------------------------------- + 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 = xcalloc (1, sizeof (struct df)); + df->flags = flags; + + /* 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); + ddf = df; + return df; +} + +/* Add PROBLEM to the DF instance. */ + +struct dataflow * +df_add_problem (struct df *df, struct df_problem *problem) +{ + struct dataflow *dflow; + + /* First try to add the dependent problem. */ + if (problem->dependent_problem) + df_add_problem (df, problem->dependent_problem); + + /* Check to see if this problem has already been defined. If it + has, just return that instance, if not, add it to the end of the + vector. */ + dflow = df->problems_by_index[problem->id]; + if (dflow) + return dflow; + + /* Make a new one and add it to the end. */ + dflow = xcalloc (1, sizeof (struct dataflow)); + 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 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) + 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 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); + + 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 +*/ + +static 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); + + /* 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 = xmalloc (sizeof (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; +} + + + +/*---------------------------------------------------------------------------- + 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++) + { + if (problem_temps[i]) + (*dflow->problem->free_bb_fun) (dflow, problem_temps[i]); + } + } + } + + free (problem_temps); + + i = NUM_FIXED_BLOCKS; + FOR_EACH_BB (bb) + { + BASIC_BLOCK (i) = bb; + bb->index = i; + i++; + } + + gcc_assert (i == n_basic_blocks); + + for (; i < last_basic_block; i++) + 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); + } + } + + 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; + + FOR_BB_INSNS_REVERSE (bb, insn) + { + unsigned int 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; + + FOR_BB_INSNS (bb, insn) + { + unsigned int 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; + + FOR_BB_INSNS_REVERSE (bb, insn) + { + unsigned int 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 *df, 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, 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, "}"); +} + + +void +df_insn_debug (struct df *df, rtx insn, bool follow_chain, 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_refs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), follow_chain, file); + fprintf (file, " defs "); + df_refs_chain_dump (df, DF_INSN_UID_USES (df, uid), follow_chain, file); + fprintf (file, "\n"); +} + +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 *df, 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 luid %d insn %d chain ", + DF_REF_REGNO (ref), + DF_REF_BBNO (ref), + DF_REF_INSN (ref) ? DF_INSN_LUID (df, DF_REF_INSN (ref)) : -1, + DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1); + df_chain_dump (df, 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 (ddf, ref, stderr); +} + + +void +debug_df_defno (unsigned int defno) +{ + df_ref_debug (ddf, DF_DEFS_GET (ddf, defno), stderr); +} + + +void +debug_df_useno (unsigned int defno) +{ + df_ref_debug (ddf, DF_USES_GET (ddf, defno), stderr); +} + + +void +debug_df_chain (struct df_link *link) +{ + df_chain_dump (ddf, link, stderr); + fputc ('\n', stderr); +} -- cgit v1.2.1