X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firscc.c;h=b33af42d26d8c85320ea15e984d135d75c3e30cb;hb=4a8e1e93a0641224e54ab8c5d1b84b57da944472;hp=dd591015b8565af9218b275149ff56727cd3257c;hpb=dddcc630819f338c3b45e2bc646233e6872d5bb6;p=libfirm

diff --git a/ir/ana/irscc.c b/ir/ana/irscc.c
index dd591015b..b33af42d2 100644
--- a/ir/ana/irscc.c
+++ b/ir/ana/irscc.c
@@ -17,7 +17,11 @@
 #include "config.h"
 #endif
 
+#ifdef HAVE_STRING_H
 #include <string.h>
+#endif
+
+#include <stdlib.h>
 
 #include "irloop_t.h"
 
@@ -30,19 +34,21 @@
 
 #include "irdump.h"
 
-INLINE void add_loop_son(ir_loop *loop, ir_loop *son);
-
-INLINE void add_loop_node(ir_loop *loop, ir_node *n);
+/* A variant of the loop tree that avoids loops without head.
+   This reduces the depth of the loop tree. */
+#define NO_LOOPS_WITHOUT_HEAD 1
 
 static ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
-                      for */
+					     for */
 static ir_loop *current_loop;      /* Current loop construction is working
-                      on. */
+				      on. */
 static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
-                      Each loop node gets a unique number.
-                      What for? ev. remove. @@@ */
+				      Each loop 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);
@@ -76,68 +82,61 @@ static INLINE scc_info* new_scc_info(void) {
 
 static INLINE void
 mark_irn_in_stack (ir_node *n) {
-  assert(get_irn_link(n));
-  /*  to slow */
-  /* ((scc_info *)get_irn_link(n))->in_stack = true; */
-  ((scc_info *)n->link)->in_stack = true;
+  scc_info *scc = get_irn_link(n);
+  assert(scc);
+  scc->in_stack = true;
 }
 
 static INLINE void
 mark_irn_not_in_stack (ir_node *n) {
-  assert(get_irn_link(n));
-  /*  to slow */
-  /* ((scc_info *)get_irn_link(n))->in_stack = false; */
-  ((scc_info *)n->link)->in_stack = false;
+  scc_info *scc = get_irn_link(n);
+  assert(scc);
+  scc->in_stack = false;
 }
 
 static INLINE bool
 irn_is_in_stack (ir_node *n) {
-  assert(get_irn_link(n));
-  /*  to slow */
-  /* return ((scc_info *)get_irn_link(n))->in_stack; */
-  return ((scc_info *)n->link)->in_stack;
+  scc_info *scc = get_irn_link(n);
+  assert(scc);
+  return scc->in_stack;
 }
 
 static INLINE void
 set_irn_uplink (ir_node *n, int uplink) {
-  assert(get_irn_link(n));
-  /*  to slow */
-  /* ((scc_info *)get_irn_link(n))->uplink = uplink; */
-  ((scc_info *)n->link)->uplink = uplink;
+  scc_info *scc = get_irn_link(n);
+  assert(scc);
+  scc->uplink = uplink;
 }
 
-INLINE int
+int
 get_irn_uplink (ir_node *n) {
-  assert(get_irn_link(n));
-  /*  from fast to slow */
-  /* return ((scc_info *)get_irn_link(n))->uplink; */
-  return ((scc_info *)n->link)->uplink;
+  scc_info *scc = get_irn_link(n);
+  assert(scc);
+  return scc->uplink;
 }
 
 static INLINE void
 set_irn_dfn (ir_node *n, int dfn) {
-  assert(get_irn_link(n));
-  /*  to slow */
-  /* ((scc_info *)get_irn_link(n))->dfn = dfn; */
-  ((scc_info *)n->link)->dfn = dfn;
+  scc_info *scc = get_irn_link(n);
+  assert(scc);
+  scc->dfn = dfn;
 }
 
-INLINE int
+int
 get_irn_dfn (ir_node *n) {
-  assert(get_irn_link(n));
-  /*  to slow */
-  /* return ((scc_info *)get_irn_link(n))->dfn; */
-  return ((scc_info *)n->link)->dfn;
+  scc_info *scc = get_irn_link(n);
+  assert(scc);
+  return scc->dfn;
 }
 
 
-INLINE void
-set_irn_loop (ir_node *n, ir_loop* loop) {
+void
+set_irn_loop (ir_node *n, ir_loop *loop) {
   n->loop = loop;
 }
 
 /* Uses temporary information to get the loop */
-INLINE ir_loop *
+ir_loop *
 get_irn_loop (ir_node *n) {
   return n->loop;
 }
@@ -178,6 +177,9 @@ ir_loop * get_irn_loop(ir_node *n) {
 static ir_node **stack = NULL;
 static int tos = 0;                /* top of stack */
 
+/**
+ * initializes the stack
+ */
 static INLINE void init_stack(void) {
   if (stack) {
     ARR_RESIZE (ir_node *, stack, 1000);
@@ -195,6 +197,11 @@ static INLINE void free_stack(void) {
 }
 #endif
 
+/**
+ * push a node onto the stack
+ *
+ * @param n  The node to push
+ */
 static INLINE void
 push (ir_node *n)
 {
@@ -208,6 +215,11 @@ push (ir_node *n)
   mark_irn_in_stack(n);
 }
 
+/**
+ * pop a node from the stack
+ *
+ * @return  The topmost node
+ */
 static INLINE ir_node *
 pop (void)
 {
@@ -216,8 +228,10 @@ pop (void)
   return n;
 }
 
-/* The nodes up to n belong to the current loop.
-   Removes them from the stack and adds them to the current loop. */
+/**
+ * The nodes up to n belong to the current loop.
+ * Removes them from the stack and adds them to the current loop.
+ */
 static INLINE void
 pop_scc_to_loop (ir_node *n)
 {
@@ -234,6 +248,7 @@ pop_scc_to_loop (ir_node *n)
     add_loop_node(current_loop, m);
     set_irn_loop(m, current_loop);
     i++;
+
     /*    if (m==n) break;*/
   } while(m != n);
 
@@ -253,21 +268,20 @@ static void close_loop (ir_loop *l)
   ir_loop *last_son = lelement.son;
 
   if (get_kind(last_son) == k_ir_loop &&
-      get_loop_n_elements(last_son) == 1)
-    {
-      ir_loop *gson;
+      get_loop_n_elements(last_son) == 1) {
+    ir_loop *gson;
 
-      lelement = get_loop_element(last_son, 0);
-      gson = lelement.son;
-      if(get_kind(gson) == k_ir_loop)
-    {
-          loop_element new_last_son;
+    lelement = get_loop_element(last_son, 0);
+    gson = lelement.son;
 
-      gson -> outer_loop = l;
-          new_last_son.son = gson;
-      l -> children[last] = new_last_son;
-    }
+    if (get_kind(gson) == k_ir_loop) {
+      loop_element new_last_son;
+
+      gson->outer_loop = l;
+      new_last_son.son = gson;
+      l->children[last] = new_last_son;
     }
+  }
 
   current_loop = l;
 }
@@ -306,6 +320,7 @@ 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;
@@ -373,7 +388,7 @@ ir_loop *get_loop_son (ir_loop *loop, int pos) {
 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
    is invalid! */
 
-INLINE void
+void
 add_loop_son(ir_loop *loop, ir_loop *son) {
   loop_element lson;
   lson.son = son;
@@ -414,7 +429,7 @@ ir_node *get_loop_node (ir_loop *loop, int pos) {
 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
    is invalid! */
 
-INLINE void
+void
 add_loop_node(ir_loop *loop, ir_node *n) {
   loop_element ln;
   ln.node = n;
@@ -479,6 +494,10 @@ void *get_loop_link (const ir_loop *loop) {
 #endif
 }
 
+int is_ir_loop(const void *thing) {
+  return (get_kind(thing) == k_ir_loop);
+}
+
 /* The outermost loop is remarked in the surrounding graph. */
 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
   assert(irg);
@@ -500,32 +519,6 @@ static INLINE void
 init_node (ir_node *n, void *env) {
   set_irn_link (n, new_scc_info());
   clear_backedges(n);
-#if 0
-  /* Also init nodes not visible in intraproc_view. */
-    /* @@@ init_node is called for too many nodes -- this wastes memory!.
-       The mem is not lost as its on the obstack. */
-  if (get_irn_op(n) == op_Filter) {
-    for (i = 0; i < get_Filter_n_cg_preds(n); i++)
-      init_node(get_Filter_cg_pred(n, i), NULL);
-  }
-  if (get_irn_op(n) == op_Block) {
-    for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
-      init_node(get_Block_cg_cfgpred(n, i), NULL);
-    }
-  }
-  /* The following pattern matches only after a call from above pattern. */
-  if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
-    /* @@@ init_node is called for every proj -- this wastes memory!.
-       The mem is not lost as its on the obstack. */
-    ir_node *cb = get_Proj_pred(n);
-    if ((get_irn_op(cb) == op_CallBegin) ||
-    (get_irn_op(cb) == op_EndReg) ||
-    (get_irn_op(cb) == op_EndExcept)) {
-      init_node(cb, NULL);
-      init_node(get_nodes_block(cb), NULL);
-    }
-  }
-#endif
 }
 
 static INLINE void
@@ -571,7 +564,7 @@ static bool is_outermost_Start(ir_node *n) {
       Besides current_ir_graph is not set properly. */
   if ((get_irn_op(n) == op_Block) &&
       (n == get_irg_start_block(current_ir_graph))) {
-    if ((!interprocedural_view)  ||
+    if ((!get_interprocedural_view())  ||
     (current_ir_graph == outermost_ir_graph))
       return true;
   }
@@ -594,9 +587,9 @@ get_start_index(ir_node *n) {
      test showed the loop tree is deeper.   */
   if (get_irn_op(n) == op_Phi   ||
       get_irn_op(n) == op_Block ||
-      (get_irn_op(n) == op_Filter && interprocedural_view) ||
+      (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
       (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
-       get_op_pinned(get_irn_op(n)) == op_pin_state_floats))
+       get_irn_pinned(n) == op_pin_state_floats))
     // Here we could test for backedge at -1 which is illegal
     return 0;
   else
@@ -638,11 +631,11 @@ static void test(ir_node *pred, ir_node *root, ir_node *this) {
 #endif
 
 /* Test for legal loop header: Block, Phi, ... */
-INLINE static bool is_possible_loop_head(ir_node *n) {
+static INLINE bool is_possible_loop_head(ir_node *n) {
   ir_op *op = get_irn_op(n);
   return ((op == op_Block) ||
 	  (op == op_Phi) ||
-	  ((op == op_Filter) && interprocedural_view));
+	  ((op == op_Filter) && get_interprocedural_view()));
 }
 
 /* Returns true if n is a loop header, i.e., it is a Block, Phi
@@ -788,7 +781,7 @@ find_tail (ir_node *n) {
 	if (res_index == -2)  /* no smallest dfn pred found. */
 	  res_index = largest_dfn_pred (m);
 
-	if ((m == n) && (res_index == -2)) {
+	if ((m == n) && (res_index == -2)) {  /* dont walk past loop head. */
 	  i = -1;
 	}
 	break;
@@ -867,7 +860,8 @@ int search_endproj_in_stack(ir_node *start_block)
 	  int arity = get_irn_arity(start_block);
 	  for(j = 0; j < arity; j++)
 	    {
-	      ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
+	      ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
+						       get_Proj_proj(end_projx));
 	      DDMN(begin_projx);
 	      if(get_irn_n(start_block, j) == begin_projx)
 		{
@@ -884,11 +878,13 @@ int search_endproj_in_stack(ir_node *start_block)
 static pmap *projx_link = NULL;
 
 void link_to_reg_end (ir_node *n, void *env) {
-  if(get_irn_op(n) == op_Proj && get_irn_mode(n) == mode_X && get_irn_op(get_irn_n(n, 0)) == op_EndReg)
-    {
+  if(get_irn_op(n) == op_Proj &&
+     get_irn_mode(n) == mode_X &&
+     get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
       /* Reg End Projx -> Find the CallBegin Projx and hash it */
       ir_node *end_projx = n;
-      ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
+      ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
+					       get_Proj_proj(end_projx));
       printf("Linked the following ProjxNodes:\n");
       DDMN(begin_projx);
       DDMN(end_projx);
@@ -910,6 +906,10 @@ ir_node *get_projx_link(ir_node *cb_projx)
 
 #endif
 
+static INLINE int
+is_outermost_loop(ir_loop *l) {
+  return l == get_loop_outer_loop(l);
+}
 
 
 /*-----------------------------------------------------------*
@@ -970,18 +970,20 @@ static void scc (ir_node *n) {
 	 Next actions: Open a new loop on the loop tree and
 	               try to find inner loops */
 
-#define NO_LOOPS_WITHOUT_HEAD 1
 #if NO_LOOPS_WITHOUT_HEAD
       /* This is an adaption of the algorithm from fiasco / optscc to
        * avoid loops without Block or Phi as first node.  This should
        * severely reduce the number of evaluations of nodes to detect
        * a fixpoint in the heap analysis.
        * Further it avoids loops without firm nodes that cause errors
-       * in the heap analyses. */
+       * in the heap analyses.
+       * But attention:  don't do it for the outermost loop:  This loop
+       * is not iterated.  A first block can be a loop head in case of
+       * an endless recursion. */
 
       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 {
@@ -1069,7 +1071,6 @@ static void my_scc (ir_node *n) {
 	 Next actions: Open a new loop on the loop tree and
 	               try to find inner loops */
 
-#define NO_LOOPS_WITHOUT_HEAD 1
 #if NO_LOOPS_WITHOUT_HEAD
       /* This is an adaption of the algorithm from fiasco / optscc to
        * avoid loops without Block or Phi as first node.  This should
@@ -1080,7 +1081,7 @@ static void my_scc (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 {
@@ -1117,13 +1118,14 @@ static void my_scc (ir_node *n) {
 
 /* Constructs backedge information for irg. In interprocedural view constructs
    backedges for all methods called by irg, too. */
-void construct_backedges(ir_graph *irg) {
+int construct_backedges(ir_graph *irg) {
   ir_graph *rem = current_ir_graph;
   ir_loop *head_rem;
 
-  assert(!interprocedural_view &&
+  assert(!get_interprocedural_view() &&
      "not implemented, use construct_ip_backedges");
 
+  max_loop_depth = 0;
   current_ir_graph   = irg;
   outermost_ir_graph = irg;
 
@@ -1133,17 +1135,10 @@ void construct_backedges(ir_graph *irg) {
   new_loop();  /* sets current_loop */
   head_rem = current_loop; /* Just for assertion */
 
-  if (interprocedural_view) {
-    set_irg_visited(current_ir_graph, inc_max_irg_visited());
-    init_ip_walk ();
-  } else {
-    inc_irg_visited(current_ir_graph);
-  }
+  inc_irg_visited(current_ir_graph);
 
   scc(get_irg_end(current_ir_graph));
 
-  if (interprocedural_view) finish_ip_walk();
-
   assert(head_rem == current_loop);
   set_irg_loop(current_ir_graph, current_loop);
   set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
@@ -1158,55 +1153,17 @@ void construct_backedges(ir_graph *irg) {
   }
   */
   current_ir_graph = rem;
-}
-
 
-#if 0
-void construct_ip_backedges (void) {
-  ir_graph *rem = current_ir_graph;
-  int rem_ipv = interprocedural_view;
-  int i, j;
-
-  outermost_ir_graph = get_irp_main_irg();
-
-  init_ip_scc();
-
-  current_loop = NULL;
-  new_loop();  /* sets current_loop */
-  interprocedural_view = 1;
-
-  inc_max_irg_visited();
-  for (i = 0; i < get_irp_n_irgs(); i++)
-    set_irg_visited(get_irp_irg(i), get_max_irg_visited());
+  return max_loop_depth;
+}
 
-  for (i = 0; i < get_irp_n_irgs(); i++) {
-    ir_node *sb;
-    current_ir_graph = get_irp_irg(i);
-    /* Find real entry points */
-    sb = get_irg_start_block(current_ir_graph);
-    if ((get_Block_n_cfgpreds(sb) > 1) ||
-    (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
-    /* Compute scc for this graph */
-    outermost_ir_graph = current_ir_graph;
-    set_irg_visited(outermost_ir_graph, get_max_irg_visited());
-    scc(get_irg_end(current_ir_graph));
-    for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
-      scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
-  }
 
-  set_irg_loop(outermost_ir_graph, current_loop);
-  set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
-  assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
-
-  current_ir_graph = rem;
-  interprocedural_view = rem_ipv;
-}
-#else
-void construct_ip_backedges (void) {
+int construct_ip_backedges (void) {
   ir_graph *rem = current_ir_graph;
-  int rem_ipv = interprocedural_view;
+  int rem_ipv = get_interprocedural_view();
   int i;
 
+  max_loop_depth = 0;
   assert(get_irp_ip_view_state() == ip_view_valid);
 
   outermost_ir_graph = get_irp_main_irg();
@@ -1215,7 +1172,7 @@ void construct_ip_backedges (void) {
 
   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++)
@@ -1267,12 +1224,13 @@ void construct_ip_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;
 }
-#endif
+
 void my_construct_ip_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);
@@ -1283,7 +1241,7 @@ void my_construct_ip_backedges (void) {
 
   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++)
@@ -1335,17 +1293,18 @@ void my_construct_ip_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);
 }
 
 static void reset_backedges(ir_node *n) {
   if (is_possible_loop_head(n)) {
-    int rem = interprocedural_view;
-    interprocedural_view = 1;
+    int rem = get_interprocedural_view();
+
+    set_interprocedural_view(true);
     clear_backedges(n);
-    interprocedural_view = 0;
+    set_interprocedural_view(true);
     clear_backedges(n);
-    interprocedural_view = rem;
+    set_interprocedural_view(rem);
   }
 }
 
@@ -1385,12 +1344,12 @@ void free_loop_information(ir_graph *irg) {
 
 void free_all_loop_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_loop_information(get_irp_irg(i));
   }
-  interprocedural_view = rem;
+  set_interprocedural_view(rem);
 }
 
 
@@ -1452,9 +1411,6 @@ static int test_loop_node(ir_loop *l) {
     dump_loop(l, "-ha");
   }
 
-  if (get_loop_loop_nr(l) == 11819)
-    dump_loop(l, "-ha-debug");
-
   return found_problem;
 }
 
@@ -1470,3 +1426,37 @@ void find_strange_loop_nodes(ir_loop *l) {
   if (found_problem) exit(0);
 
 }
+
+/* ------------------------------------------------------------------- */
+/* Simple analyses based on the loop information                       */
+/* ------------------------------------------------------------------- */
+
+int is_loop_variant(ir_loop *l, ir_loop *b) {
+  int i, n_elems;
+
+  if (l == b) return true;
+
+  n_elems = get_loop_n_elements(l);
+  for (i = 0; i < n_elems; ++i) {
+    loop_element e = get_loop_element(l, i);
+    if (is_ir_loop(e.kind))
+      if (is_loop_variant(e.son, b))
+        return true;
+  }
+
+  return false;
+}
+
+/* Test whether a value is loop invariant.
+ *
+ * @param n      The node to be tested.
+ * @param block  A block node.  We pass the block, not the loop as we must
+ *               start off with a block loop to find all proper uses.
+ *
+ * Returns true, if the node n is not changed in the loop block
+ * belongs to or in inner loops of this blocks loop. */
+int is_loop_invariant(ir_node *n, ir_node *block) {
+  ir_loop *l = get_irn_loop(block);
+  ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
+  return !is_loop_variant(l, get_irn_loop(b));
+}