*** empty log message ***

[libfirm] / ir / ana / irextbb.c

diff --git a/ir/ana/irextbb.c b/ir/ana/irextbb.c
index 4c79163..5d95912 100644 (file)
--- a/ir/ana/irextbb.c
+++ b/ir/ana/irextbb.c
@@ -71,7 +71,6 @@ static void addto_extblk(ir_extblk *extblk, ir_node *block)
  * 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;
 
@@ -84,7 +83,6 @@ static int get_block_n_succs(ir_node *block) {
     edge = get_block_succ_next(block, edge);
     return edge ? 3 : 2;
   }
-#endif
   return get_Block_n_cfg_outs(block);
 }
 
@@ -197,6 +195,66 @@ static void post_walk_calc_extbb(ir_node *block, void *ctx)
   }
 }
 
+#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
  */
@@ -214,17 +272,13 @@ void compute_extbb(ir_graph *irg) {
   env.obst = irg->extbb_obst;
   env.head = NULL;
 
-#ifdef FIRM_EDGES_INPLACE
-  if (edges_activated(irg)) {
-    /* we have edges */
+  if (! edges_activated(irg)) {
+    /* we don't have edges */
+    assure_irg_outs(irg);
   }
-  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);
+  /* 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);
 
   /*
@@ -253,9 +307,20 @@ void compute_extbb(ir_graph *irg) {
 
     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. */
@@ -265,7 +330,7 @@ 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. */
@@ -360,16 +425,22 @@ static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk
    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;
+  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 (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++) {
@@ -386,13 +457,16 @@ void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *po
       }
     }
   }
+
+  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);