X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=include%2Flibfirm%2Firdom.h;h=aae72931d95f7a117b7be1f09bd25d88cc1d92fb;hb=2232b14b4acf810ae96a69d1d2a33cf150b695d9;hp=2c6e10390bdc89fb40caf44ff515ca33c8a2da62;hpb=1ec30d95387eb392ba5a1adc7958ebd91383d59c;p=libfirm diff --git a/include/libfirm/irdom.h b/include/libfirm/irdom.h index 2c6e10390..aae72931d 100644 --- a/include/libfirm/irdom.h +++ b/include/libfirm/irdom.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -23,7 +23,7 @@ * @author Goetz Lindenmaier * @date 2.2002 * @version $Id$ - * @summary + * @brief * This file contains routines to construct and access dominator information. * * The dominator information is stored in three fields of block nodes: @@ -32,12 +32,15 @@ * - dom_depth: a number giving the depth of the block in the dominator * tree. * - pre_num: Number in preorder traversal. + * + * We generally presume (like Tarjan) that endless loops do not exist. The + * implementation assumes a control dependency from End to loop header. */ #ifndef FIRM_ANA_IRDOM_H #define FIRM_ANA_IRDOM_H #include "firm_types.h" - +#include "begin.h" /** Accessing the dominator data structure. * @@ -46,30 +49,28 @@ * * If the block is not reachable from Start, returns a Bad node. */ -ir_node *get_Block_idom(const ir_node *bl); -void set_Block_idom(ir_node *bl, ir_node *n); +FIRM_API ir_node *get_Block_idom(const ir_node *bl); +FIRM_API void set_Block_idom(ir_node *bl, ir_node *n); -int get_Block_dom_depth(const ir_node *bl); -void set_Block_dom_depth(ir_node *bl, int depth); +FIRM_API int get_Block_dom_depth(const ir_node *bl); +FIRM_API void set_Block_dom_depth(ir_node *bl, int depth); -int get_Block_dom_pre_num(const ir_node *bl); -void set_Block_dom_pre_num(ir_node *bl, int num); +FIRM_API int get_Block_dom_pre_num(const ir_node *bl); +FIRM_API void set_Block_dom_pre_num(ir_node *bl, int num); /** Accessing the post dominator data structure. * * These routines only work properly if the ir_graph is in state * dom_consistent or dom_inconsistent. - * - * If the block is not reachable from End, returns a Bad node. */ -ir_node *get_Block_ipostdom(const ir_node *bl); -void set_Block_ipostdom(ir_node *bl, ir_node *n); +FIRM_API ir_node *get_Block_ipostdom(const ir_node *bl); +FIRM_API void set_Block_ipostdom(ir_node *bl, ir_node *n); -int get_Block_postdom_depth(const ir_node *bl); -void set_Block_postdom_depth(ir_node *bl, int depth); +FIRM_API int get_Block_postdom_depth(const ir_node *bl); +FIRM_API void set_Block_postdom_depth(ir_node *bl, int depth); -int get_Block_postdom_pre_num(const ir_node *bl); -void set_Block_postdom_pre_num(ir_node *bl, int num); +FIRM_API int get_Block_postdom_pre_num(const ir_node *bl); +FIRM_API void set_Block_postdom_pre_num(ir_node *bl, int num); /** * Get the pre-order number of a block resulting from a @@ -78,7 +79,8 @@ void set_Block_postdom_pre_num(ir_node *bl, int num); * @param bl The block. * @return The pre-order number. */ -unsigned get_Block_dom_tree_pre_num(const ir_node *bl); +FIRM_API unsigned get_Block_dom_tree_pre_num(const ir_node *bl); +FIRM_API unsigned get_Block_pdom_tree_pre_num(const ir_node *bl); /** * Get the largest pre-order number found in the subtree of the @@ -86,7 +88,8 @@ unsigned get_Block_dom_tree_pre_num(const ir_node *bl); * @param bl The block. * @return The largest pre-order number of block's dominator subtree. */ -unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl); +FIRM_API unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl); +FIRM_API unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl); /** * Get the first node in the list of nodes dominated by a given block. @@ -99,7 +102,8 @@ unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl); * @param bl The block for which to get the first node dominated by @c bl. * @return The first node dominated by @p bl. */ -ir_node *get_Block_dominated_first(const ir_node *bl); +FIRM_API ir_node *get_Block_dominated_first(const ir_node *bl); +FIRM_API ir_node *get_Block_postdominated_first(const ir_node *bl); /** * Get the next node in a list of nodes which are dominated by some @@ -108,7 +112,8 @@ ir_node *get_Block_dominated_first(const ir_node *bl); * @param dom The previous node. * @return The next node in this list or NULL if it was the last. */ -ir_node *get_Block_dominated_next(const ir_node *dom); +FIRM_API ir_node *get_Block_dominated_next(const ir_node *dom); +FIRM_API ir_node *get_Block_postdominated_next(const ir_node *dom); /** * Iterate over all nodes which are immediately dominated by a given @@ -132,11 +137,23 @@ ir_node *get_Block_dominated_next(const ir_node *dom); /** * Check, if a block dominates another block. - * @param a The first block. - * @param b The second block. + * + * @param a The potential dominator block. + * @param b The potentially dominated block. + * * @return 1, if @p a dominates @p b, else 0. */ -int block_dominates(const ir_node *a, const ir_node *b); +FIRM_API int block_dominates(const ir_node *a, const ir_node *b); + +/** + * Check, if a block strictly dominates another block, i.e. a != b. + * + * @param a The potential dominator block. + * @param b The potentially dominated block. + * + * @return 1, if @p a strictly dominates @p b, else 0. + */ +FIRM_API int block_strictly_dominates(const ir_node *a, const ir_node *b); /** * Returns the smallest common dominator block of two nodes. @@ -144,7 +161,7 @@ int block_dominates(const ir_node *a, const ir_node *b); * @param b Another node. * @return The first block dominating @p a and @p b */ -ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b); +FIRM_API ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b); /** * Returns the smallest common dominator block of all users of a node @@ -156,17 +173,30 @@ ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b); * * @param irn A node. * @param handle_phi 1 if Phis should be handled different - * @return The first block dominating all users of @irn + * @return The first block dominating all users of @p irn */ -ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi); +FIRM_API ir_node *node_users_smallest_common_dominator(ir_node *irn, + int handle_phi); /** * Check, if a block post dominates another block. - * @param a The first block. - * @param b The second block. + * + * @param a The potential post dominator block. + * @param b The potentially post dominated block. + * * @return 1, if @p a post dominates @p b, else 0. */ -int block_postdominates(const ir_node *a, const ir_node *b); +FIRM_API int block_postdominates(const ir_node *a, const ir_node *b); + +/** + * Check, if a block strictly post dominates another block, i.e. a != b. + * + * @param a The potential post dominator block. + * @param b The potentially post dominated block. + * + * @return 1, if @p a strictly post dominates @p b, else 0. + */ +FIRM_API int block_strictly_postdominates(const ir_node *a, const ir_node *b); /** * Visit all nodes in the dominator subtree of a given node. @@ -177,8 +207,8 @@ int block_postdominates(const ir_node *a, const ir_node *b); * @param post The post-visitor callback. * @param env Some custom data passed to the visitors. */ -void dom_tree_walk(ir_node *n, irg_walk_func *pre, - irg_walk_func *post, void *env); +FIRM_API void dom_tree_walk(ir_node *n, irg_walk_func *pre, + irg_walk_func *post, void *env); /** * Visit all nodes in the post dominator subtree of a given node. @@ -189,8 +219,8 @@ void dom_tree_walk(ir_node *n, irg_walk_func *pre, * @param post The post-visitor callback. * @param env Some custom data passed to the visitors. */ -void postdom_tree_walk(ir_node *n, irg_walk_func *pre, - irg_walk_func *post, void *env); +FIRM_API void postdom_tree_walk(ir_node *n, irg_walk_func *pre, + irg_walk_func *post, void *env); /** * Walk over the dominator tree of an irg starting at the root. @@ -199,8 +229,8 @@ void postdom_tree_walk(ir_node *n, irg_walk_func *pre, * @param post A post-visitor to call. * @param env Some private data to give to the visitors. */ -void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre, - irg_walk_func *post, void *env); +FIRM_API void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre, + irg_walk_func *post, void *env); /** * Walk over the post dominator tree of an irg starting at the root. @@ -209,8 +239,8 @@ void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre, * @param post A post-visitor to call. * @param env Some private data to give to the visitors. */ -void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre, - irg_walk_func *post, void *env); +FIRM_API void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre, + irg_walk_func *post, void *env); /* ------------ Building and Removing the dominator data structure ----------- */ @@ -229,10 +259,10 @@ void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre, * Also constructs outs information. As this information is correct after * the run does not free the outs information. */ -void compute_doms(ir_graph *irg); +FIRM_API void compute_doms(ir_graph *irg); -/** Computes the dominator trees on demand */ -void assure_doms(ir_graph *irg); +/** Computes the dominator trees on demand, @see compute_doms(). */ +FIRM_API void assure_doms(ir_graph *irg); /** Computes the post dominator trees. * @@ -249,15 +279,20 @@ void assure_doms(ir_graph *irg); * Also constructs outs information. As this information is correct after * the run does not free the outs information. */ -void compute_postdoms(ir_graph *irg); +FIRM_API void compute_postdoms(ir_graph *irg); /** Computes the dominator trees on demand */ -void assure_postdoms(ir_graph *irg); +FIRM_API void assure_postdoms(ir_graph *irg); /** Frees the dominator data structures. Sets the flag in irg to "dom_none". */ -void free_dom(ir_graph *irg); +FIRM_API void free_dom(ir_graph *irg); + +/** + * Frees the post dominator data structures. + * Sets the flag in irg to "dom_none". + */ +FIRM_API void free_postdom(ir_graph *irg); -/** Frees the post dominator data structures. Sets the flag in irg to "dom_none". */ -void free_postdom(ir_graph *irg); +#include "end.h" #endif