/*
- * 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.
*
* @brief Construct and access dominator tree.
* @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:
* - 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.
*
*
* 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
* @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
* @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.
* @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
* @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
*
* @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.
*
* @return 1, if @p a strictly dominates @p b, else 0.
*/
-int block_strictly_dominates(const ir_node *a, const ir_node *b);
+FIRM_API int block_strictly_dominates(const ir_node *a, const ir_node *b);
/**
* Returns the smallest common dominator block of two nodes.
* @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
*
* @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.
*
* @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.
*
* @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 int block_strictly_postdominates(const ir_node *a, const ir_node *b);
/**
* Visit all nodes in the dominator subtree of a given node.
* @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.
* @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.
* @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.
* @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 ----------- */
* 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.
*
* 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
projects / libfirm / blobdiff