From fab5da4b7215a533d35fa244135dae84652e725b Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Wed, 11 Jul 2012 13:46:36 +0200 Subject: [PATCH] move domfront from be to ana Also add a GRAPH_PROPERTY for the analysis state. --- include/libfirm/irdom.h | 14 +++++++ include/libfirm/irgraph.h | 31 ++++++++------- ir/{be/bedomfront.c => ana/domfront.c} | 35 ++++++++--------- ir/ana/irdom.c | 6 ++- ir/ana/irdom_t.h | 9 +++++ ir/be/be_types.h | 2 - ir/be/bedomfront.h | 54 -------------------------- ir/be/beirg.c | 24 ------------ ir/be/beirg.h | 11 +----- ir/be/bessaconstr.c | 7 ++-- ir/be/bessaconstr.h | 5 +-- ir/be/betranshlp.c | 9 +---- ir/be/beutil.h | 3 -- ir/ir/irgraph.c | 3 ++ ir/ir/irtypes.h | 7 +--- 15 files changed, 73 insertions(+), 147 deletions(-) rename ir/{be/bedomfront.c => ana/domfront.c} (80%) delete mode 100644 ir/be/bedomfront.h diff --git a/include/libfirm/irdom.h b/include/libfirm/irdom.h index 8626d7be9..2091f3889 100644 --- a/include/libfirm/irdom.h +++ b/include/libfirm/irdom.h @@ -243,6 +243,20 @@ FIRM_API void free_dom(ir_graph *irg); */ FIRM_API void free_postdom(ir_graph *irg); +/** + * Compute the dominance frontiers for a given graph. + * The information is freed automatically when dominance info is freed. + */ +FIRM_API void ir_compute_dominance_frontiers(ir_graph *irg); + +/** + * Get the dominance frontier of a block. + * @param block The block whose dominance frontier you want. + * @return A list containing all blocks in the dominance frontier of + * @p block (as array, use ARR_LEN() to determine the size) + */ +FIRM_API ir_node **ir_get_dominance_frontier(const ir_node *block); + /** @} */ #include "end.h" diff --git a/include/libfirm/irgraph.h b/include/libfirm/irgraph.h index 5fbe89c50..e8049ad96 100644 --- a/include/libfirm/irgraph.h +++ b/include/libfirm/irgraph.h @@ -459,38 +459,40 @@ FIRM_API int irg_is_constrained(const ir_graph *irg, * state when they did not affect some properties and want to keep them. */ typedef enum ir_graph_properties_t { - IR_GRAPH_PROPERTIES_NONE = 0, + IR_GRAPH_PROPERTIES_NONE = 0, /** graph contains no critical edges */ - IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES = 1U << 0, + IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES = 1U << 0, /** graph contains no Bad nodes */ - IR_GRAPH_PROPERTY_NO_BADS = 1U << 1, + IR_GRAPH_PROPERTY_NO_BADS = 1U << 1, /** No tuple nodes exist in the graph */ - IR_GRAPH_PROPERTY_NO_TUPLES = 1U << 2, + IR_GRAPH_PROPERTY_NO_TUPLES = 1U << 2, /** * there exists no (obviously) unreachable code in the graph. * Unreachable in this context is code that you can't reach by following * execution flow from the start block. */ - IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE = 1U << 3, + IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE = 1U << 3, /** graph contains at most one return */ - IR_GRAPH_PROPERTY_ONE_RETURN = 1U << 4, + IR_GRAPH_PROPERTY_ONE_RETURN = 1U << 4, /** dominance information about the graph is valid */ - IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE = 1U << 5, + IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE = 1U << 5, /** postdominance information about the graph is valid */ - IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE = 1U << 6, + IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE = 1U << 6, + /** dominance frontiers information is calculated */ + IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS = 1U << 7, /** * out edges (=iredges) are enable and there is no dead code that can be * reached by following them */ - IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES = 1U << 7, + IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES = 1U << 8, /** outs (irouts) are computed and up to date */ - IR_GRAPH_PROPERTY_CONSISTENT_OUTS = 1U << 8, + IR_GRAPH_PROPERTY_CONSISTENT_OUTS = 1U << 9, /** loopinfo is computed and up to date */ - IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO = 1U << 9, + IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO = 1U << 10, /** entity usage information is computed and up to date */ - IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE = 1U << 10, + IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE = 1U << 11, /** graph contains as many returns as possible */ - IR_GRAPH_PROPERTY_MANY_RETURNS = 1U << 11, + IR_GRAPH_PROPERTY_MANY_RETURNS = 1U << 12, /** * List of all graph properties that are only affected byt control flow @@ -502,7 +504,8 @@ typedef enum ir_graph_properties_t { | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE - | IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE, + | IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE + | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS, /** * List of all graph properties. diff --git a/ir/be/bedomfront.c b/ir/ana/domfront.c similarity index 80% rename from ir/be/bedomfront.c rename to ir/ana/domfront.c index 60ec228a0..3865e0cfb 100644 --- a/ir/be/bedomfront.c +++ b/ir/ana/domfront.c @@ -34,16 +34,6 @@ #include "iredges_t.h" #include "irnodeset.h" -#include "bedomfront.h" - -/** - * The dominance frontier for a graph. - */ -struct be_dom_front_info_t { - pmap *df_map; /**< A map, mapping every block to a list of its dominance frontier blocks. */ - struct obstack obst; /**< An obstack holding all the frontier data. */ -}; - /** * A wrapper for get_Block_idom. * This function returns the block itself, if the block is the start @@ -65,7 +55,7 @@ static inline ir_node *get_idom(ir_node *bl) * * @return the list of all blocks in the dominance frontier of blk */ -static ir_node **compute_df(ir_node *blk, be_dom_front_info_t *info) +static ir_node **compute_df(ir_node *blk, ir_dom_front_info_t *info) { ir_node *c; const ir_edge_t *edge; @@ -108,29 +98,36 @@ static ir_node **compute_df(ir_node *blk, be_dom_front_info_t *info) return df; } -be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg) +void ir_compute_dominance_frontiers(ir_graph *irg) { - be_dom_front_info_t *info = XMALLOC(be_dom_front_info_t); + ir_dom_front_info_t *info = &irg->domfront; assure_edges(irg); obstack_init(&info->obst); info->df_map = pmap_create(); assure_doms(irg); - (void)compute_df(get_irg_start_block(irg), info); + compute_df(get_irg_start_block(irg), info); - return info; + add_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS); } -void be_free_dominance_frontiers(be_dom_front_info_t *info) +void ir_free_dominance_frontiers(ir_graph *irg) { + clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS); + + ir_dom_front_info_t *info = &irg->domfront; + if (info->df_map == NULL) + return; + obstack_free(&info->obst, NULL); pmap_destroy(info->df_map); - free(info); + info->df_map = NULL; } /* Get the dominance frontier of a block. */ -ir_node **be_get_dominance_frontier(const be_dom_front_info_t *info, - ir_node *block) +ir_node **ir_get_dominance_frontier(const ir_node *block) { + ir_graph *irg = get_irn_irg(block); + ir_dom_front_info_t *info = &irg->domfront; return (ir_node**)pmap_get(info->df_map, block); } diff --git a/ir/ana/irdom.c b/ir/ana/irdom.c index e757a55b8..4dcfac74d 100644 --- a/ir/ana/irdom.c +++ b/ir/ana/irdom.c @@ -699,8 +699,10 @@ void free_dom(ir_graph *irg) assert(get_irg_phase_state(irg) != phase_building); clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE); - /* With the implementation right now there is nothing to free, - but better call it anyways... */ + /* With the implementation right now there is nothing to free */ + + /* free dominance frontiers */ + ir_free_dominance_frontiers(irg); } void compute_postdoms(ir_graph *irg) diff --git a/ir/ana/irdom_t.h b/ir/ana/irdom_t.h index bae45413b..517cd4049 100644 --- a/ir/ana/irdom_t.h +++ b/ir/ana/irdom_t.h @@ -27,6 +27,8 @@ #define FIRM_ANA_IRDOM_T_H #include "irdom.h" +#include "pmap.h" +#include "obst.h" /** For dominator information */ typedef struct ir_dom_info { @@ -42,6 +44,11 @@ typedef struct ir_dom_info { int dom_depth; /**< depth in dominator-tree */ } ir_dom_info; +typedef struct ir_dom_front_info_t { + pmap *df_map; /**< A map, mapping every block to a list of its dominance frontier blocks. */ + struct obstack obst; /**< An obstack holding all the frontier data. */ +} ir_dom_front_info_t; + void set_Block_idom(ir_node *bl, ir_node *n); int get_Block_dom_depth(const ir_node *bl); @@ -64,4 +71,6 @@ unsigned get_Block_pdom_tree_pre_num(const ir_node *bl); unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl); unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl); +void ir_free_dominance_frontiers(ir_graph *irg); + #endif diff --git a/ir/be/be_types.h b/ir/be/be_types.h index f79439f15..284e10e57 100644 --- a/ir/be/be_types.h +++ b/ir/be/be_types.h @@ -64,8 +64,6 @@ typedef struct be_abi_call_t be_abi_call_t; typedef struct be_abi_irg_t be_abi_irg_t; typedef struct be_stack_layout_t be_stack_layout_t; -typedef struct be_dom_front_info_t be_dom_front_info_t; - typedef struct backend_info_t backend_info_t; typedef struct sched_info_t sched_info_t; typedef struct reg_out_info_t reg_out_info_t; diff --git a/ir/be/bedomfront.h b/ir/be/bedomfront.h deleted file mode 100644 index 537c82233..000000000 --- a/ir/be/bedomfront.h +++ /dev/null @@ -1,54 +0,0 @@ -/* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. - * - * This file is part of libFirm. - * - * This file may be distributed and/or modified under the terms of the - * GNU General Public License version 2 as published by the Free Software - * Foundation and appearing in the file LICENSE.GPL included in the - * packaging of this file. - * - * Licensees holding valid libFirm Professional Edition licenses may use - * this file in accordance with the libFirm Commercial License. - * Agreement provided with the Software. - * - * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE - * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE. - */ - -/** - * @file - * @brief Algorithms for computing dominance frontiers - * @author Sebastian Hack, Daniel Grund - * @date: 04.05.2005 - */ -#ifndef FIRM_BE_BEDOMFRONT_H -#define FIRM_BE_BEDOMFRONT_H - -#include "firm_types.h" -#include "be_types.h" - -/** - * Compute the dominance frontiers for a given graph. - * @param irg The graphs. - * @return A pointer to the dominance frontier information. - */ -be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg); - -/** - * Free some dominance frontier information. - * @param info Some dominance frontier information. - */ -void be_free_dominance_frontiers(be_dom_front_info_t *info); - -/** - * Get the dominance frontier of a block. - * @param info A pointer to the dominance frontier information. - * @param block The block whose dominance frontier you want. - * @return A list containing the all blocks in the dominance frontier of - * @p block. - */ -ir_node **be_get_dominance_frontier(const be_dom_front_info_t *info, ir_node *block); - -#endif diff --git a/ir/be/beirg.c b/ir/be/beirg.c index 36504b558..da0add18a 100644 --- a/ir/be/beirg.c +++ b/ir/be/beirg.c @@ -29,26 +29,6 @@ #include "beirg.h" #include "absgraph.h" #include "belive.h" -#include "bedomfront.h" - -void be_assure_dom_front(ir_graph *irg) -{ - be_irg_t *birg = be_birg_from_irg(irg); - if (birg->dom_front != NULL) - return; - - birg->dom_front = be_compute_dominance_frontiers(birg->irg); -} - -void be_invalidate_dom_front(ir_graph *irg) -{ - be_irg_t *birg = be_birg_from_irg(irg); - if (birg->dom_front == NULL) - return; - - be_free_dominance_frontiers(birg->dom_front); - birg->dom_front = NULL; -} void be_invalidate_live_sets(ir_graph *irg) { @@ -80,10 +60,6 @@ void be_free_birg(ir_graph *irg) free_execfreq(birg->exec_freq); birg->exec_freq = NULL; - if (birg->dom_front != NULL) { - be_free_dominance_frontiers(birg->dom_front); - birg->dom_front = NULL; - } if (birg->lv != NULL) { be_liveness_free(birg->lv); birg->lv = NULL; diff --git a/ir/be/beirg.h b/ir/be/beirg.h index 8970cf481..9abac301b 100644 --- a/ir/be/beirg.h +++ b/ir/be/beirg.h @@ -31,9 +31,6 @@ #include "be_t.h" #include "irtypes.h" -void be_assure_dom_front(ir_graph *irg); -void be_invalidate_dom_front(ir_graph *irg); - void be_assure_live_sets(ir_graph *irg); void be_assure_live_chk(ir_graph *irg); /** @@ -48,7 +45,7 @@ void be_invalidate_live_sets(ir_graph *irg); void be_invalidate_live_chk(ir_graph *irg); /** - * frees all memory allocated by birg structures (liveness, dom_front, ...). + * frees all memory allocated by birg structures (liveness, ...). * The memory of the birg structure itself is not freed. */ void be_free_birg(ir_graph *irg); @@ -87,7 +84,6 @@ typedef struct be_irg_t { be_main_env_t *main_env; be_abi_irg_t *abi; ir_exec_freq *exec_freq; - be_dom_front_info_t *dom_front; be_lv_t *lv; be_stack_layout_t stack_layout; unsigned *allocatable_regs; /**< registers available for the @@ -121,11 +117,6 @@ static inline ir_exec_freq *be_get_irg_exec_freq(const ir_graph *irg) return be_birg_from_irg(irg)->exec_freq; } -static inline be_dom_front_info_t *be_get_irg_dom_front(const ir_graph *irg) -{ - return be_birg_from_irg(irg)->dom_front; -} - static inline be_abi_irg_t *be_get_irg_abi(const ir_graph *irg) { return be_birg_from_irg(irg)->abi; diff --git a/ir/be/bessaconstr.c b/ir/be/bessaconstr.c index 04aa9addd..2c10cf70b 100644 --- a/ir/be/bessaconstr.c +++ b/ir/be/bessaconstr.c @@ -198,7 +198,7 @@ static void mark_iterated_dominance_frontiers( while (!waitq_empty(env->worklist)) { int i; ir_node *block = (ir_node*)waitq_get(env->worklist); - ir_node **domfront = be_get_dominance_frontier(env->domfronts, block); + ir_node **domfront = ir_get_dominance_frontier(block); int domfront_len = ARR_LEN(domfront); for (i = 0; i < domfront_len; ++i) { @@ -423,15 +423,16 @@ void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg) stat_ev_dbl("bessaconstr_n_blocks", n_blocks); memset(env, 0, sizeof(env[0])); - be_assure_dom_front(irg); env->irg = irg; - env->domfronts = be_get_irg_dom_front(irg); env->new_phis = NEW_ARR_F(ir_node*, 0); env->worklist = new_waitq(); ir_nodemap_init(&env->infos, irg); obstack_init(&env->obst); + assure_irg_properties(env->irg, + IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS); + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_BLOCK_VISITED | IR_RESOURCE_IRN_LINK); diff --git a/ir/be/bessaconstr.h b/ir/be/bessaconstr.h index c44ee65f6..bc63d7e1e 100644 --- a/ir/be/bessaconstr.h +++ b/ir/be/bessaconstr.h @@ -48,8 +48,8 @@ #ifndef FIRM_BE_BESSACONSTR_H #define FIRM_BE_BESSACONSTR_H +#include #include "firm_types.h" -#include "bedomfront.h" #include "irnodeset.h" #include "belive.h" #include "bitset.h" @@ -60,13 +60,12 @@ typedef struct be_ssa_construction_env_t { ir_graph *irg; - const be_dom_front_info_t *domfronts; ir_mode *mode; const arch_register_req_t *phi_req; waitq *worklist; const ir_nodeset_t *ignore_uses; ir_node **new_phis; - int iterated_domfront_calculated; + bool iterated_domfront_calculated; ir_nodemap infos; struct obstack obst; } be_ssa_construction_env_t; diff --git a/ir/be/betranshlp.c b/ir/be/betranshlp.c index 324e4107c..c1023f02d 100644 --- a/ir/be/betranshlp.c +++ b/ir/be/betranshlp.c @@ -414,16 +414,9 @@ void be_transform_graph(ir_graph *irg, arch_pretrans_nodes *func) current_ir_graph = old_current_ir_graph; /* most analysis info is wrong after transformation */ - free_callee_info(irg); - free_irg_outs(irg); - free_trouts(); - free_loop_information(irg); - clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE); - be_invalidate_live_chk(irg); - be_invalidate_dom_front(irg); + confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE); /* recalculate edges */ - edges_deactivate(irg); edges_activate(irg); } diff --git a/ir/be/beutil.h b/ir/be/beutil.h index 8dbb7a580..fdddf335b 100644 --- a/ir/be/beutil.h +++ b/ir/be/beutil.h @@ -32,9 +32,6 @@ #include "bearch.h" -/* iterate over a list of ir_nodes linked by link field */ -#define foreach_linked_irns(head, iter) for ((iter) = (head); (iter); (iter) = get_irn_link((iter))) - /** * Convenient block getter. * Works also, if the given node is a block. diff --git a/ir/ir/irgraph.c b/ir/ir/irgraph.c index aeea92b9c..75f83573b 100644 --- a/ir/ir/irgraph.c +++ b/ir/ir/irgraph.c @@ -820,6 +820,7 @@ void assure_irg_properties(ir_graph *irg, ir_graph_properties_t props) { IR_GRAPH_PROPERTY_CONSISTENT_OUTS, assure_irg_outs }, { IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO, assure_loopinfo }, { IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE, assure_irg_entity_usage_computed }, + { IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS, ir_compute_dominance_frontiers }, }; size_t i; for (i = 0; i < ARRAY_SIZE(property_functions); ++i) { @@ -838,4 +839,6 @@ void confirm_irg_properties(ir_graph *irg, ir_graph_properties_t props) if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_OUTS) && (irg->properties & IR_GRAPH_PROPERTY_CONSISTENT_OUTS)) free_irg_outs(irg); + if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS)) + ir_free_dominance_frontiers(irg); } diff --git a/ir/ir/irtypes.h b/ir/ir/irtypes.h index ae49aad76..e69392c03 100644 --- a/ir/ir/irtypes.h +++ b/ir/ir/irtypes.h @@ -204,11 +204,7 @@ typedef struct block_attr { unsigned marked:1; /**< Can be set/unset to temporary mark a block. */ ir_node **graph_arr; /**< An array to store all parameters. */ /* Attributes holding analyses information */ - ir_dom_info dom; /**< Datastructure that holds information about dominators. - @@@ @todo - Eventually overlay with graph_arr as only valid - in different phases. Eventually inline the whole - datastructure. */ + ir_dom_info dom; /**< Datastructure that holds information about dominators. */ ir_dom_info pdom; /**< Datastructure that holds information about post-dominators. */ bitset_t *backedge; /**< Bitfield n set to true if pred n is backedge.*/ ir_entity *entity; /**< entitiy representing this block */ @@ -546,6 +542,7 @@ struct ir_graph { ir_vrp_info vrp; /**< vrp info */ ir_loop *loop; /**< The outermost loop for this graph. */ + ir_dom_front_info_t domfront; /**< dominance frontier analysis data */ void *link; /**< A void* field to link any information to the node. */ -- 2.20.1