/*
- * 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.
*
* @date 5.4.2007
* @version $Id$
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
#include "firm_common.h"
#include "irnode_t.h"
};
/* The debug handle. */
-DEBUG_ONLY(firm_dbg_module_t *dbg;)
+DEBUG_ONLY(static firm_dbg_module_t *dbg;)
/**
* Returns the link of a region.
*/
-void *get_region_link(const ir_region *reg) {
+void *get_region_link(const ir_region *reg)
+{
return reg->link;
}
/**
* Sets the link of a region.
*/
-void set_region_link(ir_region *reg, void *data) {
+void set_region_link(ir_region *reg, void *data)
+{
reg->link = data;
}
/**
* Get the immediate region of a block.
*/
-ir_region *get_block_region(const ir_node *block) {
+ir_region *get_block_region(const ir_node *block)
+{
assert(is_Block(block));
return block->attr.block.region;
}
/**
* Sets the immediate region of a block.
*/
-void set_block_region(ir_node *block, ir_region *reg) {
+void set_block_region(ir_node *block, ir_region *reg)
+{
assert(is_Block(block));
block->attr.block.region = reg;
}
/**
* Get the immediate region of a node.
*/
-ir_region *get_irn_region(ir_node *n) {
- if (is_no_Block(n))
+ir_region *get_irn_region(ir_node *n)
+{
+ if (!is_Block(n))
n = get_nodes_block(n);
return get_block_region(n);
}
/**
- * Return non-if a given firm thing is a region.
+ * Return non-zero if a given firm thing is a region.
*/
-int is_region(const void *thing) {
+int is_region(const void *thing)
+{
const firm_kind *kind = thing;
return *kind == k_ir_region;
}
/**
- * Return the number of predecessors in a region.
+ * Return the number of predecessors of a region.
*/
-int get_region_n_preds(const ir_region *reg) {
+int get_region_n_preds(const ir_region *reg)
+{
return ARR_LEN(reg->pred);
}
/**
* Return the predecessor region at position pos.
*/
-ir_region *get_region_pred(const ir_region *reg, int pos) {
+ir_region *get_region_pred(const ir_region *reg, int pos)
+{
assert(0 <= pos && pos <= get_region_n_preds(reg));
return reg->pred[pos];
}
/**
* Set the predecessor region at position pos.
*/
-void set_region_pred(ir_region *reg, int pos, ir_region *n) {
+void set_region_pred(ir_region *reg, int pos, ir_region *n)
+{
assert(0 <= pos && pos <= get_region_n_preds(reg));
reg->pred[pos] = n;
}
/**
* Return the number of successors in a region.
*/
-int get_region_n_succs(const ir_region *reg) {
+int get_region_n_succs(const ir_region *reg)
+{
return ARR_LEN(reg->succ);
}
/**
* Return the successor region at position pos.
*/
-ir_region *get_region_succ(const ir_region *reg, int pos) {
+ir_region *get_region_succ(const ir_region *reg, int pos)
+{
assert(0 <= pos && pos <= get_region_n_succs(reg));
return reg->succ[pos];
}
/**
* Set the successor region at position pos.
*/
-void set_region_succ(ir_region *reg, int pos, ir_region *n) {
+void set_region_succ(ir_region *reg, int pos, ir_region *n)
+{
assert(0 <= pos && pos <= get_region_n_succs(reg));
reg->succ[pos] = n;
}
/** Walker environment. */
typedef struct walk_env {
- struct obstack *obst; /**< an obstack to allocate from. */
+ struct obstack *obst; /**< An obstack to allocate from. */
ir_region **post; /**< The list of all currently existent top regions. */
- unsigned l_post; /**< length of the allocated regions array. */
+ unsigned l_post; /**< The length of the allocated regions array. */
unsigned premax; /**< maximum pre counter */
unsigned postmax; /**< maximum post counter */
- ir_node *start_block; /**< the start block of the graph. */
- ir_node *end_block; /**< the end block of the graph. */
+ ir_node *start_block; /**< The start block of the graph. */
+ ir_node *end_block; /**< The end block of the graph. */
} walk_env;
/**
* Do a DFS search on the initial regions, assign a prenum and a postnum to every
* node and store the region nodes into the post array.
*/
-static void dfs_walk2(ir_region *reg, walk_env *env) {
+static void dfs_walk2(ir_region *reg, walk_env *env)
+{
int i, n;
if (reg->visited == 0) {
* Do a DFS search on the initial regions, assign a prenum and a postnum to every
* node and store the region nodes into the post array.
*/
-static void dfs_walk(ir_graph *irg, walk_env *env) {
+static void dfs_walk(ir_graph *irg, walk_env *env)
+{
ir_graph *rem = current_ir_graph;
ir_region *reg;
* Post-walker: wrap all blocks with a BasicBlock region
* and count them
*/
-static void wrap_BasicBlocks(ir_node *block, void *ctx) {
+static void wrap_BasicBlocks(ir_node *block, void *ctx)
+{
walk_env *env = ctx;
ir_region *reg;
/* Allocate a Block wrapper */
- reg = obstack_alloc(env->obst, sizeof(*reg));
+ reg = OALLOC(env->obst, ir_region);
reg->kind = k_ir_region;
reg->type = ir_rk_BasicBlock;
reg->parent = NULL;
} /* wrap_BasicBlocks */
/**
- * Create the pred and succ edges for Block wrapper.
+ * Post-walker: Create the pred and succ edges for Block wrapper.
* Kill edges to the Start and End blocks.
*/
-static void update_BasicBlock_regions(ir_node *blk, void *ctx) {
+static void update_BasicBlock_regions(ir_node *blk, void *ctx)
+{
walk_env *env = ctx;
ir_region *reg = get_irn_link(blk);
int i, j, len;
if (blk == env->start_block) {
- /* handle Firm's self loop */
+ /* handle Firm's self loop: Start block has no predecessors */
reg->pred = NEW_ARR_D(ir_region *, env->obst, 0);
} else {
len = get_Block_n_cfgpreds(blk);
ARR_SHRINKLEN(reg->succ, j);
} /* update_BasicBlock_regions */
-/** Allocate a new region of a obstack */
+/** Allocate a new region on an obstack */
#define ALLOC_REG(obst, reg, tp) \
do { \
- (reg) = obstack_alloc((obst), sizeof(*(reg))); \
+ (reg) = OALLOC((obst), ir_region); \
(reg)->kind = k_ir_region; \
(reg)->type = tp; \
(reg)->parent = NULL; \
/**
* Creates a new Sequence region.
*/
-static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len) {
+static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len)
+{
ir_region *reg, *next;
int i;
/**
* Create a new IfThenElse region.
*/
-static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b) {
+static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b)
+{
ir_region *reg;
ALLOC_REG(obst, reg, ir_rk_IfThenElse);
/**
* Create a new IfThen region.
*/
-static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b) {
+static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b)
+{
ir_region *reg;
ALLOC_REG(obst, reg, ir_rk_IfThen);
* Create a new Switch/case region.
*/
static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *exit,
- ir_region *cases, int cases_len) {
+ ir_region *cases, int cases_len)
+{
ir_region *reg, *c, *n;
int i;
int add = 1;
/**
* Create a new SelfLoop region.
*/
-static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) {
+static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head)
+{
ir_region *reg, *succ;
int i, j, len;
/**
* Create a new RepeatLoop region.
*/
-static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body) {
+static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body)
+{
ir_region *reg, *succ;
ALLOC_REG(obst, reg, ir_rk_RepeatLoop);
/**
* Create a new WhileLoop region.
*/
-static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) {
+static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head)
+{
ir_region *reg, *succ;
ir_region *body = head->link;
int i, j, len;
/**
* Create a new new_NaturalLoop region.
*/
-static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head) {
+static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head)
+{
ir_region *reg, *c, *n;
int i, j, k, len, n_pred, n_succ;
/* count number of succs */
n_succ = 0;
for (j = 0; j < len; ++j) {
- ir_region *c = reg->parts[j].region;
- for (i = get_region_n_succs(c) - 1; i >= 0; --i) {
- ir_region *succ = get_region_succ(c, i);
+ ir_region *pc = reg->parts[j].region;
+ for (i = get_region_n_succs(pc) - 1; i >= 0; --i) {
+ ir_region *succ = get_region_succ(pc, i);
if (succ->parent != reg)
++n_succ;
}
reg->succ = NEW_ARR_D(ir_region *, obst, n_succ);
k = 0;
for (j = 0; j < len; ++j) {
- ir_region *c = reg->parts[j].region;
- for (i = get_region_n_succs(c) - 1; i >= 0; --i) {
- ir_region *succ = get_region_succ(c, i);
+ ir_region *pc = reg->parts[j].region;
+ for (i = get_region_n_succs(pc) - 1; i >= 0; --i) {
+ ir_region *succ = get_region_succ(pc, i);
if (succ->parent != reg)
reg->succ[k++] = succ;
}
} /* new_NaturalLoop */
/**
- * Return true if a is an ancestor of b in DFS search.
+ * Return true if region a is an ancestor of region b in DFS search.
*/
-static int is_ancestor(const ir_region *a, const ir_region *b) {
+static int is_ancestor(const ir_region *a, const ir_region *b)
+{
return (a->prenum <= b->prenum && a->postnum > b->postnum);
}
/**
- * Return true if region pred is a predecessor of region n.
+ * Return true if region pred is a predecessor of region n.
*/
-static int pred_of(const ir_region *pred, const ir_region *n) {
+static int pred_of(const ir_region *pred, const ir_region *n)
+{
int i;
for (i = get_region_n_preds(n) - 1; i >= 0; --i) {
if (get_region_pred(n, i) == pred)
}
/**
- * Return true if region succ is a successor of region n.
+ * Return true if region succ is a successor of region n.
*/
-static int succ_of(const ir_region *succ, const ir_region *n) {
+static int succ_of(const ir_region *succ, const ir_region *n)
+{
int i;
for (i = get_region_n_succs(n) - 1; i >= 0; --i) {
if (get_region_succ(n, i) == succ)
}
/**
- * Reverse linked list.
+ * Reverse a linked list of regions.
*/
-static struct ir_region *reverse_list(ir_region *n) {
+static struct ir_region *reverse_list(ir_region *n)
+{
ir_region *prev = NULL, *next;
for (; n; n = next) {
/**
* Find the cyclic region in the subgraph entered by node.
*/
-static ir_region *find_cyclic_region(ir_region *node) {
+static ir_region *find_cyclic_region(ir_region *node)
+{
int i;
ir_region *last = node;
int improper = 0;
/**
* Detect a cyclic region.
*/
-static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) {
+static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node)
+{
ir_region *list;
/* simple cases first */
}
/**
- * Clear all links on a list. Needed, because we expect cleared links-
+ * Clear all links on a list. Needed, because we expect cleared links.
*/
-static void clear_list(ir_region *list) {
+static void clear_list(ir_region *list)
+{
ir_region *next;
for (next = list; next; list = next) {
}
}
-#define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while(0)
+#define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while (0)
/**
* Detect an acyclic region.
*/
-static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) {
+static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node)
+{
ir_region *n, *m;
int p, s, i, k;
ir_region *nset = NULL;
}
/* check for Switch, case */
if (k > 0) {
- ir_region *exit = NULL;
+ ir_region *rexit = NULL;
nset = NULL; nset_len = 0;
p = 0;
for (i = k - 1; i >= 0; --i) {
ADD_LIST(nset, n);
if (get_region_n_succs(n) != 1) {
/* must be the exit */
- exit = n;
+ rexit = n;
++p;
if (p > 1)
break;
for (m = nset; m != NULL; m = m->link) {
if (get_region_n_succs(m) != 1) {
/* must be the exit block */
- if (exit == NULL) {
- exit = m;
- } else if (exit != m) {
+ if (rexit == NULL) {
+ rexit = m;
+ } else if (rexit != m) {
/* two exits */
- exit = NULL;
+ rexit = NULL;
break;
}
} else {
ir_region *succ = get_region_succ(m, 0);
if (succ->link == NULL) {
- if (exit == NULL) {
+ if (rexit == NULL) {
if (succ == pos_exit_1)
- exit = succ;
+ rexit = succ;
else if (succ == pos_exit_2)
- exit = succ;
+ rexit = succ;
else if (pos_exit_1 == NULL)
pos_exit_1 = succ;
else if (pos_exit_2 == NULL)
/* more than two possible exits */
break;
}
- } else if (exit != succ) {
+ } else if (rexit != succ) {
/* two exits */
- exit = NULL;
+ rexit = NULL;
break;
}
}
}
}
- if (exit != NULL) {
+ if (rexit != NULL) {
/* do the checks */
for (n = nset; n != NULL; n = n->link) {
ir_region *succ;
- if (n == exit) {
+ if (n == rexit) {
/* good, default fall through */
continue;
}
succ = get_region_succ(n, 0);
- if (succ == exit) {
+ if (succ == rexit) {
/* good, switch to exit */
continue;
}
if (n == NULL) {
/* detected */
- return new_SwitchCase(obst, kind, node, exit, nset, nset_len);
+ return new_SwitchCase(obst, kind, node, rexit, nset, nset_len);
}
}
}
* replace all pred edges from region pred that points to any of the set set
* to ONE edge to reg.
*/
-static void replace_pred(ir_region *succ, ir_region *reg) {
+static void replace_pred(ir_region *succ, ir_region *reg)
+{
int i, len = get_region_n_preds(succ);
int have_one = 0;
* replace all succ edges from region pred that points to any of the set set
* to ONE edge to reg.
*/
-static void replace_succ(ir_region *pred, ir_region *reg) {
+static void replace_succ(ir_region *pred, ir_region *reg)
+{
int i, len = get_region_n_succs(pred);
int have_one = 0;
/**
* Reduce the graph by the node reg.
*/
-static void reduce(walk_env *env, ir_region *reg) {
+static void reduce(walk_env *env, ir_region *reg)
+{
int i;
ir_region *head = reg->parts[0].region;
unsigned maxorder = head->postnum;
replace_pred(succ, reg);
}
- /* second third: replace all succs in predessors */
+ /* third step: replace all succs in predessors */
for (i = get_region_n_preds(reg) - 1; i >= 0; --i) {
ir_region *pred = get_region_pred(reg, i);
*
* @param irg the graph
*/
-ir_reg_tree *construct_region_tree(ir_graph *irg) {
+ir_reg_tree *construct_region_tree(ir_graph *irg)
+{
walk_env env;
ir_graph *rem = current_ir_graph;
- ir_reg_tree *res = xmalloc(sizeof(*res));
+ ir_reg_tree *res = XMALLOC(ir_reg_tree);
obstack_init(&res->obst);
DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg));
- dump_ir_block_graph(irg, "-structure_start");
-
/* we need dominance info */
assure_doms(irg);
/* and out edges */
do {
ir_region *reg, *n = env.post[postctr];
do {
- if (n->parent) {
+ if (n->parent != NULL) {
/* already folded */
break;
}
* @param post walker function, executed after the children of a tree node are visited
* @param env environment, passed to pre and post
*/
-static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
+static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
+{
int i, n;
if (pre)
* @param post walker function, executed after the children of a tree node are visited
* @param env environment, passed to pre and post
*/
-void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
+void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
+{
region_tree_walk2(tree->top, pre, post, env);
}