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

diff --git a/ir/ana/irscc.c b/ir/ana/irscc.c
index 8af9abdc1..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"
 
@@ -34,11 +38,6 @@
    This reduces the depth of the loop tree. */
 #define NO_LOOPS_WITHOUT_HEAD 1
 
-
-INLINE void add_loop_son(ir_loop *loop, ir_loop *son);
-
-INLINE void add_loop_node(ir_loop *loop, ir_node *n);
-
 static ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
 					     for */
 static ir_loop *current_loop;      /* Current loop construction is working
@@ -83,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;
 }
@@ -185,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);
@@ -202,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)
 {
@@ -215,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)
 {
@@ -223,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)
 {
@@ -241,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);
 
@@ -260,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;
 }
@@ -381,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;
@@ -422,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;
@@ -487,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);
@@ -508,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
@@ -579,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;
   }
@@ -602,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
@@ -646,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
@@ -921,7 +906,7 @@ ir_node *get_projx_link(ir_node *cb_projx)
 
 #endif
 
-INLINE static int
+static INLINE int
 is_outermost_loop(ir_loop *l) {
   return l == get_loop_outer_loop(l);
 }
@@ -1137,7 +1122,7 @@ 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;
@@ -1175,7 +1160,7 @@ int construct_backedges(ir_graph *irg) {
 
 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;
@@ -1187,7 +1172,7 @@ int 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++)
@@ -1239,13 +1224,13 @@ int 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;
 }
 
 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);
@@ -1256,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++)
@@ -1308,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);
   }
 }
 
@@ -1358,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);
 }
 
 
@@ -1425,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;
 }
 
@@ -1443,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));
+}