#include "irgwalk.h"
#include "irnode_t.h"
#include "irgraph_t.h"
+#include "iredges_t.h"
+#include "irouts.h"
#include "xmalloc.h"
#include "irprintf.h"
ir_extblk *head; /**< head of the list of all extended blocks */
} env_t;
+int (is_ir_extbb)(const void *thing) {
+ return _is_ir_extbb(thing);
+}
+
/**
* allocate a new extended block header.
*/
set_Block_extbb(block, extblk);
}
+/**
+ * Returns the number of block successors.
+ * we are interested only in 1, 2 and >2.
+ */
+static int get_block_n_succs(ir_node *block) {
+#ifdef FIRM_EDGES_INPLACE
+ if (edges_activated(current_ir_graph)) {
+ const ir_edge_t *edge;
+
+ edge = get_block_succ_first(block);
+ if (! edge)
+ return 0;
+ edge = get_block_succ_next(block, edge);
+ if (! edge)
+ return 1;
+ edge = get_block_succ_next(block, edge);
+ return edge ? 3 : 2;
+ }
+#endif
+ return get_Block_n_cfg_outs(block);
+}
/**
* Pre block-walker. Calculates the extended block info.
env_t *env = ctx;
if (n <= 0 || n > 1 ||
- block == get_irg_start_block(current_ir_graph) ||
- block == get_irg_end_block(current_ir_graph)) {
+ block == get_irg_start_block(current_ir_graph)) {
/*
* block is a JOIN-node ie the control flow from
* many other blocks joins here. block is a leader.
* Only one control flow predecessor. This block belongs
* to the same extended basic block as its predecessor.
*/
- set_Block_extbb(block, NULL);
+ ir_node *cf_op = skip_Proj(get_Block_cfgpred(block, 0));
+
+ if (irn_not_visited(cf_op)) {
+ ir_node *pred_bl = get_nodes_block(cf_op);
+ if (get_block_n_succs(pred_bl) > 2) {
+ /* More than two successors means we have a jump table.
+ * we cannot include a jump target into the current extended
+ * basic block, so create a new one here.
+ */
+ allocate_extblk(block, env);
+ }
+ else {
+ /* either the previous block has only one successor or
+ * this is the first successor after an if, include it.
+ */
+ set_Block_extbb(block, NULL);
+ }
+ mark_irn_visited(cf_op);
+ }
+ else {
+ /* already marked, so begin a new extended block here */
+ allocate_extblk(block, env);
+ }
}
}
}
-static int _sentinel;
+/** A special extended block used as sentinel */
+static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD };
/**
* Post block-walker. Calculates the extended block info.
{
ir_extblk *extbb = get_Block_extbb(block);
env_t *env = ctx;
- ir_extblk *sentinel = (ir_extblk *)&_sentinel;
+ ir_extblk *sentinel = &_sentinel;
if (! extbb) {
ir_node *curr, *prev;
}
}
+#ifdef NEED_SORT
+/**
+ * Walker for cf_dependent_on().
+ * This function searches a node tgt recursively from a given node
+ * but is restricted to the given extended basic block.
+ *
+ * @return 1 if tgt was reachable from curr, 0 if not.
+ */
+static int check_cf_dependence(ir_node *curr, ir_node *tgt, ir_extblk *extbb)
+{
+ int n, i;
+
+ /* Note: we did not include the leader in our serach, so
+ there could not be any loops here. */
+ if (get_Block_extbb(curr) != extbb)
+ return 0;
+
+ if (curr == tgt)
+ return 1;
+
+ for (i = 0, n = get_Block_n_cfgpreds(curr); i < n; ++i) {
+ if (check_cf_dependence(get_Block_cfgpred_block(curr, i), tgt, extbb))
+ return 1;
+ }
+ return 0;
+}
+
+/**
+ * Check if a block is control dependent on another one.
+ * Both blocks must be in the same extended basic block.
+ * @param blk1 The first block.
+ * @param blk2 The second block.
+ * @return 1, if blk1 is control dependent (transitively) on blk2, 0 if not.
+ */
+static int cf_dependent_on(ir_node *blk1, ir_node *blk2)
+{
+ ir_extblk *extbb = get_Block_extbb(blk1);
+ ir_graph *irg = get_irn_irg(blk1);
+
+ assert(extbb == get_Block_extbb(blk2));
+ return check_cf_dependence(blk1, blk2, extbb);
+}
+
+/**
+ * Compare two blocks for dependency.
+ *
+ * @return
+ * 0 if both blocks nodes are equal
+ * 1 block b1 depends on block b2
+ * -1 block b2 depends on block d2
+ */
+static int block_order(const void *b1, const void *b2)
+{
+ ir_node *n1 = *(ir_node **)b1;
+ ir_node *n2 = *(ir_node **)b2;
+
+ return n1 == n2 ? 0 : (cf_dependent_on(n1, n2) ? -1 : 1);
+}
+#endif /* NEED_SORT */
+
/*
* Compute the extended basic blocks for a graph
*/
env.obst = irg->extbb_obst;
env.head = NULL;
+#ifdef FIRM_EDGES_INPLACE
+ if (edges_activated(irg)) {
+ /* we have edges */
+ }
+ else
+#endif
+ if (get_irg_outs_state(irg) != outs_consistent)
+ compute_irg_outs(irg);
+
+ /* we must mark nodes, so increase the visited flag */
+ inc_irg_visited(irg);
irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);
/*
extbb->link = NULL;
extbb->visited = 0;
+
+#ifdef NEED_SORT
+ /* we want the blocks in scheduled order, so sort them */
+ /* FIXME: is this really needed? Or generates the algorithm automagically ordered ones? */
+ if (len > 1) {
+ /* temporary remove the leader from the extended block to break loops */
+ set_Block_extbb(extbb->blks[0], NULL);
+ qsort(&extbb->blks[1], len-1, sizeof(extbb->blks[0]), block_order);
+ set_Block_extbb(extbb->blks[0], extbb);
+ }
+#endif
}
- irg->extblk_state = ir_extblk_info_valid;
+ irg->extblk_state = extblk_valid;
}
/* free all extended block info. */
xfree(irg->extbb_obst);
irg->extbb_obst = NULL;
}
- irg->extblk_state = ir_extblk_info_none;
+ irg->extblk_state = extblk_none;
}
/* Return the extended block of a node. */
flag, so that it can be interleaved with the other walker. */
void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
{
- ir_node *block, *pred;
+ ir_node *pred, *start_bl = get_irg_start_block(current_ir_graph);
+ ir_extblk *start_blk = get_Block_extbb(start_bl);
int i;
assert(blk);
assert(!get_interprocedural_view()); /* interprocedural_view not implemented */
inc_irg_block_visited(current_ir_graph);
- irg_extblock_walk_2(block, pre, post, env);
+
+ /* assure the start block is the first one */
+ mark_extbb_visited(start_blk);
+ if (post)
+ post(start_blk, env);
+ irg_extblock_walk_2(blk, pre, post, env);
/* keepalive: the endless loops ... */
- if (get_extbb_leader(blk) == get_irg_end_block(current_ir_graph)) {
+ if (blk == get_Block_extbb(get_irg_end_block(current_ir_graph))) {
ir_node *node = get_irg_end(current_ir_graph);
int arity = get_irn_arity(node);
for (i = 0; i < arity; i++) {
}
}
}
+
+ if (pre)
+ pre(start_blk, env);
}
/* Walks only over reachable Extended Basic Block nodes in the graph. */
void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env)
{
- ir_node *end = get_irg_end(irg);
- ir_extblk *blk = get_Block_extbb(end);
+ ir_node *endbl = get_irg_end_block(irg);
+ ir_extblk *blk = get_Block_extbb(endbl);
ir_graph *rem = current_ir_graph;
current_ir_graph = irg;
irg_extblock_walk(blk, pre, post, env);
projects / libfirm / blobdiff