X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=include%2Flibfirm%2Firdom.h;h=8626d7be916e44db39c11d366cca946f01befac6;hb=332cda9a138297c9852e2ef0f649c92b640723f4;hp=295b025afd4784c25cc868485b774879bf24b341;hpb=d38903b3463d9a6dbd4ba3b9f682f80723b4dda0;p=libfirm diff --git a/include/libfirm/irdom.h b/include/libfirm/irdom.h index 295b025af..8626d7be9 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. * @@ -22,9 +22,17 @@ * @brief Construct and access dominator tree. * @author Goetz Lindenmaier * @date 2.2002 - * @version $Id$ - * @summary - * This file contains routines to construct and access dominator information. + * @brief This file contains routines to construct and access dominator information. + */ +#ifndef FIRM_ANA_IRDOM_H +#define FIRM_ANA_IRDOM_H + +#include "firm_types.h" +#include "begin.h" + +/** + * @ingroup irana + * @defgroup irdom Dominance Information * * The dominator information is stored in three fields of block nodes: * - idom: a reference to the block that is the immediate dominator of @@ -32,83 +40,88 @@ * - 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" +/** return immediate dominator of block */ +FIRM_API ir_node *get_Block_idom(const ir_node *block); +/** return immediate postdominator of a block */ +FIRM_API ir_node *get_Block_ipostdom(const ir_node *block); -/** Accessing the dominator data structure. +/** + * Check, if a block dominates another block. * - * These routines only work properly if the ir_graph is in state - * dom_consistent or dom_inconsistent. + * @param a The potential dominator block. + * @param b The potentially dominated block. * - * If the block is not reachable from Start, returns a Bad node. + * @return 1, if @p a dominates @p b, else 0. */ -ir_node *get_Block_idom(const ir_node *bl); -void set_Block_idom(ir_node *bl, ir_node *n); +FIRM_API int block_dominates(const ir_node *a, const ir_node *b); -int get_Block_dom_depth(const ir_node *bl); -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); - -/** Accessing the post dominator data structure. +/** + * Check, if a block strictly dominates another block, i.e. a != b. * - * These routines only work properly if the ir_graph is in state - * dom_consistent or dom_inconsistent. + * @param a The potential dominator block. + * @param b The potentially dominated block. * - * If the block is not reachable from End, returns a Bad node. + * @return 1, if @p a strictly dominates @p b, else 0. */ -ir_node *get_Block_ipostdom(const ir_node *bl); -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); - -int get_Block_postdom_pre_num(const ir_node *bl); -void set_Block_postdom_pre_num(ir_node *bl, int num); +FIRM_API int block_strictly_dominates(const ir_node *a, const ir_node *b); /** - * Get the pre-order number of a block resulting from a - * Depth-First-Search walkover the dominator tree. + * Check, if a block post dominates another block. * - * @param bl The block. - * @return The pre-order number. + * @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. */ -unsigned get_Block_dom_tree_pre_num(const ir_node *bl); +FIRM_API int block_postdominates(const ir_node *a, const ir_node *b); /** - * Get the largest pre-order number found in the subtree of the - * dominator tree rooted at a given block. - * @param bl The block. - * @return The largest pre-order number of block's dominator subtree. + * 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. */ -unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl); +FIRM_API int block_strictly_postdominates(const ir_node *a, const ir_node *b); /** - * Get the first node in the list of nodes dominated by a given block. + * Returns the first node in the list of nodes dominated by a given block. * * Each node keeps a list of nodes which it immediately dominates. The * nodes are queued using the @c next pointer in the @c dom_info struct. * Each node keeps a head of this list using the pointer @c first in the * same structure. * - * @param bl The block for which to get the first node dominated by @c bl. + * @param block 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 *block); +/** + * Returns the first node in the list of nodes postdominated by a given blcok. + */ +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 + * Returns the next node in a list of nodes which are dominated by some * other node. * @see get_Block_dominated_first(). - * @param dom The previous node. + * @param node 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 *node); +/** + * Returns the next node in a list of nodes which are postdominated by another node + */ +FIRM_API ir_node *get_Block_postdominated_next(const ir_node *node); /** * Iterate over all nodes which are immediately dominated by a given @@ -130,67 +143,13 @@ ir_node *get_Block_dominated_next(const ir_node *dom); for(curr = get_Block_postdominated_first(bl); curr; \ curr = get_Block_postdominated_next(curr)) -/** - * Check, if a block dominates another 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); - -/** - * 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. - */ -int block_strictly_dominates(const ir_node *a, const ir_node *b); - /** * Returns the smallest common dominator block of two nodes. * @param a A node. * @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); - -/** - * Returns the smallest common dominator block of all users of a node - * BEWARE: @p irn must not be a block - * If on or more users are Phi nodes, one can request special handling - * with @p handle_phi = 1. In this case the cfg predecessor block - * corresponding to the position of the irn in the argument list of the - * Phi is determined and treated as user. - * - * @param irn A node. - * @param handle_phi 1 if Phis should be handled different - * @return The first block dominating all users of @irn - */ -ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi); - -/** - * Check, if a block post dominates another 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); - -/** - * 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. - */ -int block_strictly_postdominates(const ir_node *a, const ir_node *b); +FIRM_API ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b); /** * Visit all nodes in the dominator subtree of a given node. @@ -201,8 +160,8 @@ int block_strictly_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. @@ -213,8 +172,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. @@ -223,8 +182,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. @@ -233,12 +192,10 @@ 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 ----------- */ - -/** Computes the dominator trees. +/** Computes the dominance relation for all basic blocks of a given graph. * * Sets a flag in irg to "dom_consistent". * If the control flow of the graph is changed this flag must be set to @@ -253,12 +210,12 @@ 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); +/** Recomputes dominator relation of a graph if necessary */ +FIRM_API void assure_doms(ir_graph *irg); -/** Computes the post dominator trees. +/** Computes the post dominance relation for all basic blocks of a given graph. * * Sets a flag in irg to "dom_consistent". * If the control flow of the graph is changed this flag must be set to @@ -273,15 +230,21 @@ 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); + +/** Recompute postdominance relation if necessary */ +FIRM_API void assure_postdoms(ir_graph *irg); + +/** Frees the dominance data structures. Sets the flag in irg to "dom_none". */ +FIRM_API void free_dom(ir_graph *irg); -/** Computes the dominator trees on demand */ -void assure_postdoms(ir_graph *irg); +/** + * Frees the postdominance data structures. Sets the flag in irg to "dom_none". + */ +FIRM_API void free_postdom(ir_graph *irg); -/** Frees the dominator data structures. Sets the flag in irg to "dom_none". */ -void free_dom(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