/*
- * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
+ * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
*
* This file is part of libFirm.
*
/**
* @file
+ * @brief Algorithms for computing dominance frontiers.
* @author Sebastian Hack, Daniel Grund
- * @date: 04.05.2005
+ * @date 04.05.2005
* @version $Id$
- * Copyright: (c) Universitaet Karlsruhe
- * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
-
-#include "bedomfront.h"
#include "obst.h"
#include "pmap.h"
#include "array.h"
#include "irgraph.h"
#include "iredges_t.h"
+#include "irnodeset.h"
+
+#include "bedomfront.h"
/**
* The dominance frontier for a graph.
*/
-struct _be_dom_front_info_t {
+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. */
};
* @param bl The block.
* @return The immediate dominator of the block.
*/
-static INLINE
-ir_node *get_idom(ir_node *bl)
+static inline ir_node *get_idom(ir_node *bl)
{
ir_node *idom = get_Block_idom(bl);
return idom == NULL ? bl : idom;
*
* @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, be_dom_front_info_t *info)
{
ir_node *c;
const ir_edge_t *edge;
ir_node **df_list = NEW_ARR_F(ir_node *, 0);
ir_node **df;
- int len;
+ size_t len;
/* Add local dominance frontiers */
foreach_block_succ(blk, edge) {
* dominated by the given block.
*/
for (c = get_Block_dominated_first(blk); c; c = get_Block_dominated_next(c)) {
- int i;
+ size_t i;
ir_node **df_c_list = compute_df(c, info);
- for (i = ARR_LEN(df_c_list) - 1; i >= 0; --i) {
- ir_node *w = df_c_list[i];
+ for (i = ARR_LEN(df_c_list); i > 0;) {
+ ir_node *w = df_c_list[--i];
if (get_idom(w) != blk)
ARR_APP1(ir_node *, df_list, w);
}
be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
{
- be_dom_front_info_t *info = xmalloc(sizeof(*info));
+ be_dom_front_info_t *info = XMALLOC(be_dom_front_info_t);
edges_assure(irg);
obstack_init(&info->obst);
ir_node **be_get_dominance_frontier(const be_dom_front_info_t *info,
ir_node *block)
{
- return pmap_get(info->df_map, block);
-}
-
-/**
- * Calculates the iterated dominance frontier of a set of blocks.
- * Also clears the link field of the returned blocks as a side effect
- */
-void be_get_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts,
- ir_nodeset_t *blocks)
-{
- ir_node *block;
- ir_nodeset_iterator_t iter;
- waitq *worklist = new_waitq();
-
- foreach_ir_nodeset(blocks, block, iter) {
- waitq_put(worklist, block);
- }
-
- while(!pdeq_empty(worklist)) {
- int i;
- ir_node *block = waitq_get(worklist);
- ir_node **domfront = be_get_dominance_frontier(domfronts, block);
- int domfront_len = ARR_LEN(domfront);
-
- for (i = 0; i < domfront_len; ++i) {
- ir_node *y = domfront[i];
- if(!ir_nodeset_insert(blocks, y))
- continue;
-
- waitq_put(worklist, y);
- }
- }
-
- del_waitq(worklist);
+ return (ir_node**)pmap_get(info->df_map, block);
}