X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fircfscc.c;h=0e50feb66affb5b35c810b78e877b5125d758112;hb=4bad1346ff2abc3923beea23e5ac949acc7ca514;hp=3a86c1089b1b521c5422fe96ca904a0cc0a7ddcd;hpb=ac7a8d6d17e3080b94233fb5ab099591b9dc757b;p=libfirm

diff --git a/ir/ana/ircfscc.c b/ir/ana/ircfscc.c
index 3a86c1089..0e50feb66 100644
--- a/ir/ana/ircfscc.c
+++ b/ir/ana/ircfscc.c
@@ -17,7 +17,9 @@
 #include "config.h"
 #endif
 
+#ifdef HAVE_STRING_H
 #include <string.h>
+#endif
 
 #include "irloop_t.h"
 #include "irnode_t.h"
@@ -28,27 +30,26 @@
 #include "irprog_t.h"
 #include "irdump.h"
 
-ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
+#define NO_CFLOOPS_WITHOUT_HEAD 1
+
+static ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
                       for */
 static ir_loop *current_loop;      /* Current cfloop construction is working
                       on. */
 static int loop_node_cnt = 0;      /* Counts the number of allocated cfloop nodes.
-                      Each cfloop node gets a unique number.
-                      What for? ev. remove. @@@ */
+				      Each cfloop node gets a unique number.
+				      What for? ev. remove. @@@ */
 static int current_dfn = 1;        /* Counter to generate depth first numbering
-                      of visited nodes.  */
+				      of visited nodes.  */
+
+static int max_loop_depth = 0;
 
 void link_to_reg_end (ir_node *n, void *env);
-void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
-ir_node *get_projx_link(ir_node *cb_projx);
 
 /**********************************************************************/
 /* Node attributes                                                   **/
 /**********************************************************************/
 
-/* A map to get from irnodes to loop nodes. */
-static pmap *node_loop_map = NULL;
-
 /**********************************************************************/
 /* Node attributes needed for the construction.                      **/
 /**********************************************************************/
@@ -222,6 +223,7 @@ static ir_loop *new_loop (void) {
     son->outer_loop = father;
     add_loop_son(father, son);
     son->depth = father->depth+1;
+    if (son->depth > max_loop_depth) max_loop_depth = son->depth;
   } else {  /* The root loop */
     son->outer_loop = son;
     son->depth = 0;
@@ -253,7 +255,6 @@ static INLINE void
 init_scc_common (void) {
   current_dfn = 1;
   loop_node_cnt = 0;
-  if (!node_loop_map) node_loop_map = pmap_create();
   init_stack();
 }
 
@@ -280,7 +281,7 @@ static bool is_outermost_StartBlock(ir_node *n) {
   assert(is_Block(n));
   if ((get_Block_n_cfgpreds(n) == 1)  &&
       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
-      (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
+      (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
     return true;
   }
   return false;
@@ -318,6 +319,39 @@ is_head (ir_node *n, ir_node *root)
   return some_outof_loop && some_in_loop;
 }
 
+
+/* Returns true if n is possible loop head of an endless loop.
+   I.e., it is a Block, Phi or Filter node and has only predecessors
+   within the loop.
+   @arg root: only needed for assertion. */
+static bool
+is_endless_head (ir_node *n, ir_node *root)
+{
+  int i, arity;
+  int some_outof_loop = 0, some_in_loop = 0;
+
+  assert(is_Block(n));
+  /* Test for legal loop header: Block, Phi, ... */
+  if (!is_outermost_StartBlock(n)) {
+    arity = get_irn_arity(n);
+    for (i = 0; i < arity; i++) {
+      ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
+      assert(pred);
+      if (is_backedge(n, i)) { continue; }
+      if (!irn_is_in_stack(pred)) {
+	some_outof_loop = 1; //printf(" some out of loop ");
+      } else {
+	if(get_irn_uplink(pred) < get_irn_uplink(root)) {
+	  DDMN(pred); DDMN(root);
+	  assert(get_irn_uplink(pred) >= get_irn_uplink(root));
+	}
+	some_in_loop = 1;
+      }
+    }
+  }
+  return !some_outof_loop && some_in_loop;
+}
+
 /* Returns index of the predecessor with the smallest dfn number
    greater-equal than limit. */
 static int
@@ -362,8 +396,7 @@ largest_dfn_pred (ir_node *n)
 /* Searches the stack for possible loop heads.  Tests these for backedges.
    If it finds a head with an unmarked backedge it marks this edge and
    returns the tail of the loop.
-   If it finds no backedge returns NULL.
-   ("disable_backedge" in fiasco) */
+   If it finds no backedge returns NULL. */
 static ir_node *
 find_tail (ir_node *n) {
   ir_node *m;
@@ -377,15 +410,46 @@ find_tail (ir_node *n) {
       return NULL;
   } else {
     if (m == n) return NULL;
-    for (i = tos-2; ; --i) {
+    for (i = tos-2; i >= 0; --i) {
+
       m = stack[i];
       if (is_head (m, n)) {
 	res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 	if (res_index == -2)  /* no smallest dfn pred found. */
 	  res_index = largest_dfn_pred (m);
+
+	if ((m == n) && (res_index == -2)) {
+	  i = -1;
+	}
 	break;
       }
+
+
+      /* We should not walk past our selves on the stack:  The upcoming nodes
+	 are not in this loop. We assume a loop not reachable from Start. */
+      if (m == n) {
+	i = -1;
+	break;
+      }
+
     }
+
+
+    if (i < 0) {
+      /* A dead loop not reachable from Start. */
+      for (i = tos-2; i >= 0; --i) {
+	m = stack[i];
+	if (is_endless_head (m, n)) {
+	  res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
+	  if (res_index == -2)  /* no smallest dfn pred found. */
+	    res_index = largest_dfn_pred (m);
+	  break;
+	}
+	if (m == n) { break; }  /* It's not an unreachable loop, either. */
+      }
+      //assert(0 && "no head found on stack");
+    }
+
   }
   assert (res_index > -2);
 
@@ -393,6 +457,11 @@ find_tail (ir_node *n) {
   return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
 }
 
+INLINE static int
+is_outermost_loop(ir_loop *l) {
+  return l == get_loop_outer_loop(l);
+}
+
 /*-----------------------------------------------------------*
  *                   The core algorithm.                     *
  *-----------------------------------------------------------*/
@@ -454,8 +523,6 @@ static void cfscc (ir_node *n) {
 	 Next actions: Open a new cfloop on the cfloop tree and
 	               try to find inner cfloops */
 
-
-#define NO_CFLOOPS_WITHOUT_HEAD 1
 #if NO_CFLOOPS_WITHOUT_HEAD
 
       /* This is an adaption of the algorithm from fiasco / optscc to
@@ -467,7 +534,7 @@ static void cfscc (ir_node *n) {
 
       ir_loop *l;
       int close;
-      if (get_loop_n_elements(current_loop) > 0) {
+      if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 	l = new_loop();
 	close = 1;
       } else {
@@ -507,14 +574,15 @@ static void cfscc (ir_node *n) {
 }
 
 /* Constructs backedge information for irg. */
-void construct_cf_backedges(ir_graph *irg) {
+int construct_cf_backedges(ir_graph *irg) {
   ir_graph *rem = current_ir_graph;
   ir_loop *head_rem;
   ir_node *end = get_irg_end(irg);
   int i;
 
-  assert(!interprocedural_view &&
+  assert(!get_interprocedural_view() &&
      "use construct_ip_backedges");
+  max_loop_depth = 0;
 
   current_ir_graph = irg;
   outermost_ir_graph = irg;
@@ -539,23 +607,24 @@ void construct_cf_backedges(ir_graph *irg) {
   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
 
   current_ir_graph = rem;
+  return max_loop_depth;
 }
 
 
-void construct_ip_cf_backedges (void) {
+int construct_ip_cf_backedges (void) {
   ir_graph *rem = current_ir_graph;
-  int rem_ipv = interprocedural_view;
+  int rem_ipv = get_interprocedural_view();
   int i;
 
   assert(get_irp_ip_view_state() == ip_view_valid);
-
+  max_loop_depth = 0;
   outermost_ir_graph = get_irp_main_irg();
 
   init_ip_scc();
 
   current_loop = NULL;
   new_loop();  /* sets current_loop */
-  interprocedural_view = 1;
+  set_interprocedural_view(true);
 
   inc_max_irg_visited();
   for (i = 0; i < get_irp_n_irgs(); i++)
@@ -610,18 +679,20 @@ void construct_ip_cf_backedges (void) {
   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
 
   current_ir_graph = rem;
-  interprocedural_view = rem_ipv;
+  set_interprocedural_view(rem_ipv);
+  return max_loop_depth;
 }
 
 
 static void reset_backedges(ir_node *n) {
+  int rem = get_interprocedural_view();
+
   assert(is_Block(n));
-  int rem = interprocedural_view;
-  interprocedural_view = 1;
+  set_interprocedural_view(true);
   clear_backedges(n);
-  interprocedural_view = 0;
+  set_interprocedural_view(false);
   clear_backedges(n);
-  interprocedural_view = rem;
+  set_interprocedural_view(rem);
 }
 
 static void loop_reset_backedges(ir_loop *l) {
@@ -647,12 +718,10 @@ void free_cfloop_information(ir_graph *irg) {
 
 void free_all_cfloop_information (void) {
   int i;
-  int rem = interprocedural_view;
-  interprocedural_view = 1;  /* To visit all filter nodes */
+  int rem = get_interprocedural_view();
+  set_interprocedural_view(true);  /* To visit all filter nodes */
   for (i = 0; i < get_irp_n_irgs(); i++) {
     free_cfloop_information(get_irp_irg(i));
   }
-  pmap_destroy(node_loop_map);
-  node_loop_map = NULL;
-  interprocedural_view = rem;
+  set_interprocedural_view(rem);
 }