X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firgwalk.c;h=3c5ddac35f2872c96468f498e462e7b7f930ad13;hb=a226465c4f00c94b3e94a7c717e04061625e7a33;hp=7221ba3cb5edfeef7e9dadec377ff51be46cbcc6;hpb=c2e377ee1536c04c8b00d241fb2d63a4061732bc;p=libfirm

diff --git a/ir/ir/irgwalk.c b/ir/ir/irgwalk.c
index 7221ba3cb..3c5ddac35 100644
--- a/ir/ir/irgwalk.c
+++ b/ir/ir/irgwalk.c
@@ -1,14 +1,21 @@
-/* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
-** All rights reserved.
-**
-** Author: Boris Boesler
-**
-** traverse an ir graph
-** - execute the pre function before recursion
-** - execute the post function after recursion
+/*
+ * Project:     libFIRM
+ * File name:   ir/ir/irgwalk.c
+ * Purpose:
+ * Author:      Boris Boesler
+ * Modified by: Goetz Lindenmaier
+ * Created:
+ * CVS-ID:      $Id$
+ * Copyright:   (c) 1999-2003 Universität Karlsruhe
+ * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
+ */
+
+/**
+* traverse an ir graph
+* - execute the pre function before recursion
+* - execute the post function after recursion
 */
 
-/* $Id$ */
 
 #ifdef HAVE_CONFIG_H
 # include <config.h>
@@ -16,22 +23,25 @@
 
 # include <stdlib.h>
 
-# include "irnode.h"
-# include "irgraph.h" /* visited flag */
+# include "irnode_t.h"
+# include "irgraph_t.h" /* visited flag */
 # include "irprog.h"
 # include "irgwalk.h"
+# include "typewalk.h"
+# include "firmstat.h"
+# include "ircgcons.h"
 
 # include "eset.h"
 # include "array.h"
 
 /* walk over an interprocedural graph (callgraph). Visits only graphs in irg_set. */
 static void irg_walk_cg(ir_node * node, int visited, eset * irg_set,
-			irg_walk_func pre, irg_walk_func post, void * env) {
+			irg_walk_func *pre, irg_walk_func *post, void * env) {
   int i;
   ir_graph * rem = current_ir_graph;
   ir_node * pred;
 
-  assert(node);
+  assert(node && node->kind == k_ir_node);
   if (get_irn_visited(node) >= visited) return;
 
   set_irn_visited(node, visited);
@@ -46,7 +56,7 @@ static void irg_walk_cg(ir_node * node, int visited, eset * irg_set,
   if (pre) pre(node, env);
 
   if (is_no_Block(node))
-    irg_walk_cg(get_nodes_Block(node), visited, irg_set, pre, post, env);
+    irg_walk_cg(get_nodes_block(node), visited, irg_set, pre, post, env);
 
   if (get_irn_op(node) == op_Block) { /* block */
     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
@@ -66,7 +76,7 @@ static void irg_walk_cg(ir_node * node, int visited, eset * irg_set,
 	irg_walk_cg(pred, visited, irg_set, pre, post, env);
       } else {
 	ir_node * exec;
-	exec = skip_Proj(get_Block_cfgpred(get_nodes_Block(node), i));
+	exec = skip_Proj(get_Block_cfgpred(get_nodes_block(node), i));
 	assert(get_irn_op(exec) == op_CallBegin
 	       || get_irn_op(exec) == op_EndReg
 	       || get_irn_op(exec) == op_EndExcept);
@@ -98,49 +108,66 @@ static void collect_irgs(ir_node * node, eset * irg_set) {
       ir_graph * irg = ent ? get_entity_irg(ent) : NULL;
       if (irg && !eset_contains(irg_set, irg)) {
 	eset_insert(irg_set, irg);
-	irg_walk_graph(irg, (irg_walk_func) collect_irgs, NULL, irg_set);
+	irg_walk_graph(irg, (irg_walk_func *) collect_irgs, NULL, irg_set);
       }
     }
   }
 }
 
-void irg_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void * env)
+static void
+irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env)
 {
   int i;
-  assert(node);
-
+  assert(node && node->kind==k_ir_node);
+#if 0 /* safe */
   if (get_irn_visited(node) < get_irg_visited(current_ir_graph)) {
     set_irn_visited(node, get_irg_visited(current_ir_graph));
 
     if (pre) pre(node, env);
 
     if (is_no_Block(node))
-      irg_walk_2(get_nodes_Block(node), pre, post, env);
+      irg_walk_2(get_nodes_block(node), pre, post, env);
     for (i = get_irn_arity(node) - 1; i >= 0; --i)
       irg_walk_2(get_irn_n(node, i), pre, post, env);
 
     if (post) post(node, env);
   }
-  return;
+#else /* faster */
+  if (node->visited < current_ir_graph->visited) {
+    set_irn_visited(node, current_ir_graph->visited);
+
+    if (pre) pre(node, env);
+
+    if (node->op != op_Block)
+      irg_walk_2(get_irn_n(node, -1), pre, post, env);
+    for (i = get_irn_arity(node) - 1; i >= 0; --i)
+      irg_walk_2(get_irn_n(node, i), pre, post, env);
+
+    if (post) post(node, env);
+  }
+#endif
 }
 
 
-void irg_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
+void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 {
-  assert(node);
+  assert(node  && node->kind==k_ir_node);
+
   if (interprocedural_view) {
     eset * irg_set = eset_create();
     int visited;
     ir_graph * irg;
+    assert(get_irp_ip_view_state() == ip_view_valid);
+
     interprocedural_view = false;
     eset_insert(irg_set, current_ir_graph);
-    irg_walk(node, (irg_walk_func) collect_irgs, NULL, irg_set);
+    irg_walk(node, (irg_walk_func *) collect_irgs, NULL, irg_set);
     interprocedural_view = true;
     visited = get_max_irg_visited() + 1;
-    irg_walk_cg(node, visited, irg_set, pre, post, env);
     for (irg = eset_first(irg_set); irg; irg = eset_next(irg_set)) {
       set_irg_visited(irg, visited);
     }
+    irg_walk_cg(node, visited, irg_set, pre, post, env);
     eset_destroy(irg_set);
   } else {
     inc_irg_visited(current_ir_graph);
@@ -150,8 +177,10 @@ void irg_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
 }
 
 
-void irg_walk_graph(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *env) {
+void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) {
   ir_graph * rem = current_ir_graph;
+
+  stat_irg_walk(irg, (void *)pre, (void *)post);
   current_ir_graph = irg;
   irg_walk(get_irg_end(irg), pre, post, env);
   current_ir_graph = rem;
@@ -160,7 +189,7 @@ void irg_walk_graph(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *
 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
    Sets current_ir_graph properly for each walk.  Conserves current
    current_ir_graph. */
-void all_irg_walk(irg_walk_func pre, irg_walk_func post, void *env) {
+void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) {
   int i;
   ir_graph *irg, *rem;
 
@@ -185,7 +214,7 @@ switch_irg (ir_node *n, int index) {
   if (interprocedural_view) {
     /* Only Filter and Block nodes can have predecessors in other graphs. */
     if (get_irn_op(n) == op_Filter)
-      n = get_nodes_Block(n);
+      n = get_nodes_block(n);
     if (get_irn_op(n) == op_Block) {
       ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
       if (is_ip_cfop(cfop)) {
@@ -197,7 +226,8 @@ switch_irg (ir_node *n, int index) {
   return old_current;
 }
 
-void cg_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void * env)
+static void
+cg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env)
 {
   int i;
   ir_graph *rem = NULL;
@@ -209,9 +239,10 @@ void cg_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void * env)
     if (pre) pre(node, env);
 
     if (is_no_Block(node))
-      cg_walk_2(get_nodes_Block(node), pre, post, env);
+      cg_walk_2(get_nodes_block(node), pre, post, env);
     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
-      rem = switch_irg(node, i);
+      rem = switch_irg(node, i);  /* @@@ AS: Is this wrong? We do have to
+                                             switch to the irg of the predecessor, don't we? */
       cg_walk_2(get_irn_n(node, i), pre, post, env);
       current_ir_graph = rem;
     }
@@ -223,7 +254,7 @@ void cg_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void * env)
 
 
 /* Walks all irgs in interprocedural view.  Visits each node only once. */
-void cg_walk(irg_walk_func pre, irg_walk_func post, void *env) {
+void cg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) {
   int i;
   ir_graph *rem = current_ir_graph;
   int rem_view = interprocedural_view;
@@ -235,18 +266,48 @@ void cg_walk(irg_walk_func pre, irg_walk_func post, void *env) {
   for (i = 0; i < get_irp_n_irgs(); i++)
     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 
-  /* Walk starting at unreachable procedures. */
+  /* Walk starting at unreachable procedures. Only these
+   * have End blocks visible in interprocedural view. */
   for (i = 0; i < get_irp_n_irgs(); i++) {
     ir_node *sb;
     current_ir_graph = get_irp_irg(i);
 
     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;
+	(get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 
     cg_walk_2(get_irg_end(current_ir_graph), pre, post, env);
   }
 
+  /* Check whether we walked all procedures: there could be procedures
+     with cyclic calls but no call from the outside. */
+  for (i = 0; i < get_irp_n_irgs(); i++) {
+    ir_node *sb;
+    current_ir_graph = get_irp_irg(i);
+
+    /* Test start block: if inner procedure end and end block are not
+     * visible and therefore not marked. */
+    sb = get_irg_start_block(current_ir_graph);
+    if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) {
+      cg_walk_2(sb, pre, post, env);
+    }
+  }
+
+  /* Walk all endless loops in inner procedures.
+   * We recognize an inner procedure if the End node is not visited. */
+  for (i = 0; i < get_irp_n_irgs(); i++) {
+    ir_node *e;
+    current_ir_graph = get_irp_irg(i);
+    e = get_irg_end(current_ir_graph);
+    if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
+      int j;
+      /* Don't visit the End node. */
+      for (j = 0; j < get_End_n_keepalives(e); j++)
+	cg_walk_2(get_End_keepalive(e, j), pre, post, env);
+    }
+  }
+
   interprocedural_view = rem_view;
   current_ir_graph = rem;
 }
@@ -255,7 +316,7 @@ void cg_walk(irg_walk_func pre, irg_walk_func post, void *env) {
 /***************************************************************************/
 
 /* Walks back from n until it finds a real cf op. */
-ir_node *get_cf_op(ir_node *n) {
+static ir_node *get_cf_op(ir_node *n) {
   ir_node *pred;
 
   n = skip_nop(n);
@@ -268,10 +329,9 @@ ir_node *get_cf_op(ir_node *n) {
   return skip_Proj(n);
 }
 
-void irg_block_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
+static void irg_block_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 {
   int i;
-  assert(get_irn_opcode(node) == iro_Block);
 
   if(get_Block_block_visited(node) < get_irg_block_visited(current_ir_graph)) {
     set_Block_block_visited(node, get_irg_block_visited(current_ir_graph));
@@ -281,7 +341,7 @@ void irg_block_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void
     for(i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
       /* find the corresponding predecessor block. */
       ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
-      pred = get_nodes_Block(pred);
+      pred = get_nodes_block(pred);
       if(get_irn_opcode(pred) == iro_Block) {
 	/* recursion */
 	irg_block_walk_2(pred, pre, post, env);
@@ -299,32 +359,36 @@ void irg_block_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void
 
 /* walks only over Block nodes in the graph.  Has it's own visited
    flag, so that it can be interleaved with the other walker.         */
-void irg_block_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
+void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 {
   ir_node *block, *pred;
   int i;
 
+  stat_irg_block_walk(current_ir_graph, node, (void *)pre, (void *)post);
+
   assert(node);
   assert(!interprocedural_view);   /* interprocedural_view not implemented, because it
 				    * interleaves with irg_walk */
   inc_irg_block_visited(current_ir_graph);
-  if (is_no_Block(node)) block = get_nodes_Block(node); else block = node;
+  if (is_no_Block(node)) block = get_nodes_block(node); else block = node;
   assert(get_irn_opcode(block)  == iro_Block);
   irg_block_walk_2(block, pre, post, env);
   /* keepalive: the endless loops ... */
-  if (get_irn_op(node) == op_End)
-    for (i = 0; i < get_irn_arity(node); i++) {
+  if (get_irn_op(node) == op_End) {
+    int arity = get_irn_arity(node);
+    for (i = 0; i < arity; i++) {
       pred = get_irn_n(node, i);
       if (get_irn_op(pred) == op_Block)
 	irg_block_walk_2(pred, pre, post, env);
     }
+  }
 
   return;
 }
 
 
-void irg_block_walk_graph(ir_graph *irg, irg_walk_func pre,
-			  irg_walk_func post, void *env) {
+void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
+			  irg_walk_func *post, void *env) {
   ir_graph * rem = current_ir_graph;
   current_ir_graph = irg;
   irg_block_walk(get_irg_end(irg), pre, post, env);
@@ -334,28 +398,31 @@ void irg_block_walk_graph(ir_graph *irg, irg_walk_func pre,
 /********************************************************************/
 
 typedef struct walk_env {
-  void *pre;
-  void *post;
+  irg_walk_func *pre;
+  irg_walk_func *post;
   void *env;
 } walk_env;
 
 /* Walk to all constant expressions in this entity. */
-void walk_entity(entity *ent, void *env) {
+static void walk_entity(entity *ent, void *env)
+{
   walk_env *my_env = (walk_env *)env;
-  if (get_entity_variability(ent) != uninitialized) {
+
+  if (get_entity_variability(ent) != variability_uninitialized) {
     if (is_atomic_entity(ent)) {
       irg_walk(get_atomic_ent_value(ent), my_env->pre, my_env->post, my_env->env);
-    } else {
-      int i;
-      for (i = 0; i < get_compound_ent_n_values(ent); i++) {
+    }
+    else {
+      int i, n = get_compound_ent_n_values(ent);
+
+      for (i = 0; i < n; i++)
 	irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env);
-      }
     }
   }
 }
 
 /* Walks over all code in const_code_irg. */
-void walk_const_code(irg_walk_func pre, irg_walk_func post, void *env) {
+void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env) {
   int i, j;
   walk_env my_env;
 
@@ -368,11 +435,11 @@ void walk_const_code(irg_walk_func pre, irg_walk_func post, void *env) {
   my_env.env = env;
 
   /* Walk all types that can contain constant entities.  */
-  walk_types_entities(get_glob_type(), &walk_entity, &env);
+  walk_types_entities(get_glob_type(), &walk_entity, &my_env);
   for (i = 0; i < get_irp_n_types(); i++)
-    walk_types_entities(get_irp_type(i), &walk_entity, &env);
+    walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
   for (i = 0; i < get_irp_n_irgs(); i++)
-    walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &env);
+    walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
 
   /* Walk constant array bounds. */
   for (i = 0; i < get_irp_n_types(); i++) {
@@ -422,11 +489,6 @@ void walk_const_code(irg_walk_func pre, irg_walk_func post, void *env) {
 /** }                                                              **/
 /********************************************************************/
 
-/* Allocates some necessary datastructures. */
-void init_ip_walk ();
-/* Frees some necessary datastructures. */
-void finish_ip_walk();
-
 /* Call for i in {0|-1 ... get_irn_arity(n)}.
    If n is a conventional node returns the same node as get_irn_n(n, i).
    If the predecessors of n are in the callee of the procedure n belongs
@@ -513,13 +575,13 @@ ir_node * pop_callsite(ir_graph *callee) {
 
 /* Initialization routines ******************************************/
 
-void init_ip_walk () {
+void init_ip_walk (void) {
   int i;
   for (i = 0; i < get_irp_n_irgs(); i++)
     new_callsite_stack(get_irp_irg(i));
 }
 
-void finish_ip_walk() {
+void finish_ip_walk(void) {
   int i;
   for (i = 0; i < get_irp_n_irgs(); i++)
     free_callsite_stack(get_irp_irg(i));
@@ -570,7 +632,7 @@ ir_node *get_irn_ip_pred(ir_node *n, int pos) {
     /* Find the cf_pred refering to pos. */
     ir_node *block = n;
     ir_node *cf_pred;
-    if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
+    if (get_irn_opcode(n) == iro_Filter) block = get_nodes_block(n);
     cf_pred = skip_Proj(get_irn_n(block, pos));
 
     /* Check whether we enter or leave a procedure and act according. */
@@ -616,7 +678,7 @@ return_recur(ir_node *n, int pos) {
 
   /* Find the cf_pred refering to pos. */
   block = n;
-  if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
+  if (get_irn_opcode(n) == iro_Filter) block = get_nodes_block(n);
   cf_pred = skip_Proj(get_irn_n(block, pos));
 
   /* Check whether we re_enter or re_leave a procedure and act according. */