X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firextbb.c;h=5d9591261dd3764cd3ed49bbbef1e30b4bef7fa6;hb=d2dc2564b47d9c113d7e6e598574e9733627fcca;hp=d06c3debb56de71f7b2c5d17ea7505cf97102527;hpb=97ff748cc2cc50aef20d0bab162a2f3fbc1f014a;p=libfirm

diff --git a/ir/ana/irextbb.c b/ir/ana/irextbb.c
index d06c3debb..5d9591261 100644
--- a/ir/ana/irextbb.c
+++ b/ir/ana/irextbb.c
@@ -20,6 +20,9 @@
 #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"
 
@@ -28,6 +31,10 @@ typedef struct _env {
   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.
  */
@@ -59,6 +66,25 @@ static void addto_extblk(ir_extblk *extblk, ir_node *block)
   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) {
+  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;
+  }
+  return get_Block_n_cfg_outs(block);
+}
 
 /**
  * Pre block-walker. Calculates the extended block info.
@@ -68,18 +94,17 @@ 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)) {
@@ -90,33 +115,146 @@ static void pre_walk_calc_extbb(ir_node *block, void *ctx)
        * 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);
+
+      allocate_extblk(block, env);
+      extbb = get_Block_extbb(block);
+      set_Block_extbb(block, sentinel);
+    }
 
-    addto_extblk(extbb, block);
+    /* 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);
+    }
   }
 }
 
+#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
  */
@@ -134,6 +272,13 @@ void compute_extbb(ir_graph *irg) {
   env.obst = irg->extbb_obst;
   env.head = NULL;
 
+  if (! edges_activated(irg)) {
+    /* we don't have edges */
+    assure_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);
 
   /*
@@ -154,16 +299,28 @@ void compute_extbb(ir_graph *irg) {
     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;
     }
 
     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. */
@@ -173,12 +330,12 @@ void free_extbb(ir_graph *irg) {
     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. */
 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);
 }
 
@@ -226,3 +383,92 @@ int (get_extbb_n_blocks)(const ir_extblk *blk) {
 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, *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);
+
+  /* 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 (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++) {
+      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);
+      }
+    }
+  }
+
+  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 *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);
+  current_ir_graph = rem;
+}