#include "irextbb_t.h"
#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.
- * Currently, we use the (free) block input of all basis blocks
- * to point to the leader block.
*/
static void pre_walk_calc_extbb(ir_node *block, void *ctx)
{
int n = get_Block_n_cfgpreds(block);
env_t *env = ctx;
- if (n > 1 || block == get_irg_start_block(current_ir_graph)) {
+ if (n <= 0 || n > 1 ||
+ block == get_irg_start_block(current_ir_graph)) {
/*
- * block is a JOIN-node ie he control flow from
+ * block is a JOIN-node ie the control flow from
* many other blocks joins here. block is a leader.
+ * Note that we handle unreachable blocks (n <= 0) here too.
*/
allocate_extblk(block, env);
}
- else {
- ir_node *add_to = get_Block_cfgpred(block, 0);
-
- if (! is_Bad(add_to))
- add_to = get_nodes_block(add_to);
+ else { /* we have only one control flow predecessor */
+ ir_node *add_to = get_Block_cfgpred_block(block, 0);
/* blocks with only one BAD predecessors are leaders too */
if (is_Bad(add_to)) {
}
else {
/*
- * Only on control flow predecessor. This block belongs
+ * 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);
+ }
}
}
}
+/** A special extended block used as sentinel */
+static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD };
+
/**
* Post block-walker. Calculates the extended block info.
* During construction, we use the (free) block input of all basic blocks
* to point to there previous block.
*/
-static void post_walk_calc_extbb(ir_node *block, void *env)
+static void post_walk_calc_extbb(ir_node *block, void *ctx)
{
ir_extblk *extbb = get_Block_extbb(block);
+ env_t *env = ctx;
+ ir_extblk *sentinel = &_sentinel;
if (! extbb) {
- ir_node *prev = block;
+ ir_node *curr, *prev;
- /* search the leader */
- do {
- prev = get_nodes_block(get_Block_cfgpred(prev, 0));
+ /*
+ * Search the leader. It can happen, that we fall into an endless
+ * loop, because we enter an unreachable loop that is not yet detected.
+ * We break the loop using a sentinel.
+ */
+ for (curr = block; !extbb; curr = prev) {
+ prev = get_Block_cfgpred_block(curr, 0);
extbb = get_Block_extbb(prev);
- } while (! extbb);
+ set_Block_extbb(curr, sentinel);
+ }
+
+ if (extbb == sentinel) {
+ /* We detect a dead loop. We fix this by allocating an
+ * special Extended block
+ */
+ ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);
- addto_extblk(extbb, block);
+ allocate_extblk(block, env);
+ extbb = get_Block_extbb(block);
+ set_Block_extbb(block, sentinel);
+ }
+
+ /* replace all sentinels by the extbb info */
+ prev = block;
+ while (1) {
+ if (get_Block_extbb(prev) != sentinel)
+ break;
+ set_Block_extbb(prev, extbb);
+ ++extbb->visited;
+ set_irn_link(prev, extbb->link);
+ extbb->link = prev;
+ prev = get_Block_cfgpred_block(prev, 0);
+ }
}
}
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);
/*
for (block = extbb->link, i = 0; i < len; ++i) {
ir_node *nblock = get_irn_link(block);
- extbb->blks[i] = block;
+ /* ensure that the leader is the first one */
+ extbb->blks[len - 1 - i] = block;
set_irn_link(block, NULL);
block = nblock;
}
/* Return the extended block of a node. */
ir_extblk *get_nodes_extbb(ir_node *node) {
- ir_node *block = is_Block(node) ? node : get_nodes_block(node);
+ ir_node *block = is_Block(node) ? node : get_irn_n(node, -1);
return get_Block_extbb(block);
}
_set_extbb_link(blk, link);
}
-/* Return the number of basis blocks of an extended block */
+/* Return the number of basic blocks of an extended block */
int (get_extbb_n_blocks)(const ir_extblk *blk) {
return _get_extbb_n_blocks(blk);
}
-/* Return the i'th basis block of an extended block */
+/* Return the i'th basic block of an extended block */
ir_node *(get_extbb_block)(ir_extblk *blk, int pos) {
return _get_extbb_block(blk, pos);
}
+
+/* Return the leader basis block of an extended block. */
+ir_node *(get_extbb_leader)(ir_extblk *blk) {
+ return _get_extbb_leader(blk);
+}
+
+/* Return the node number of an extended block. */
+long get_extbb_node_nr(ir_extblk *blk) {
+ return get_irn_node_nr(get_extbb_leader(blk));
+}
+
+static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
+{
+ int i;
+ ir_node *node;
+
+ if (extbb_not_visited(blk)) {
+ mark_extbb_visited(blk);
+
+ if (pre) pre(blk, env);
+
+ node = get_extbb_leader(blk);
+ for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
+ /* find the corresponding predecessor block. */
+ ir_node *pred = get_Block_cfgpred_block(node, i);
+ if (is_Block(pred)) {
+ /* recursion */
+ irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
+ }
+ else {
+ assert(is_Bad(pred));
+ }
+ }
+
+ if (post) post(blk, env);
+ }
+}
+
+/* walks only over extended Block nodes in the graph. Has it's own visited
+ 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 *pred;
+ int i;
+
+ assert(blk);
+ assert(!get_interprocedural_view()); /* interprocedural_view not implemented */
+ inc_irg_block_visited(current_ir_graph);
+ irg_extblock_walk_2(blk, pre, post, env);
+
+ /* keepalive: the endless loops ... */
+ if (get_extbb_leader(blk) == 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++) {
+ pred = get_irn_n(node, i);
+ if (is_Block(pred))
+ irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
+ else if (is_Phi(pred)) {
+ /* Sometimes the blocks died, but are still reachable through Phis.
+ * Make sure the algorithms that try to remove these reach them. */
+ ir_node *block = get_nodes_block(pred);
+
+ if (! is_Bad(block))
+ irg_extblock_walk_2(get_Block_extbb(block), pre, post, 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_graph *rem = current_ir_graph;
+ current_ir_graph = irg;
+ irg_extblock_walk(blk, pre, post, env);
+ current_ir_graph = rem;
+}
projects / libfirm / blobdiff