X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Ftr%2Ftypewalk.c;h=e7baf6461cb57bda3fb574a3de1938c7544bc5c9;hb=59856977857ca10af2919790348deecbfe05ed1b;hp=a7ef5ec884ae4842229c7d960383002784d47939;hpb=b636c7a78245056138a2ab87f5c9f58c8e2bd029;p=libfirm

diff --git a/ir/tr/typewalk.c b/ir/tr/typewalk.c
index a7ef5ec88..e7baf6461 100644
--- a/ir/tr/typewalk.c
+++ b/ir/tr/typewalk.c
@@ -1,202 +1,571 @@
-/* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
-** All rights reserved.
-**
-** Author: Goetz Lindenmaier
-**
-** traverse the type information.  The walker walks the whole ir graph
-** to find the distinct type trees in the type graph forest.
-** - execute the pre function before recursion
-** - execute the post function after recursion
-*/
+/*
+ * Project:     libFIRM
+ * File name:   ir/tr/typewalk.c
+ * Purpose:     Traverse the type information.
+ * Author:      Goetz Lindenmaier
+ * Modified by:
+ * Created:
+ * CVS-ID:      $Id$
+ * Copyright:   (c) 1999-2003 Universität Karlsruhe
+ * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
+ */
+
+/**
+ * @file typewalk.c
+ *
+ * Traverse the type information.  The walker walks the whole ir graph
+ * to find the distinct type trees in the type graph forest.
+ * - execute the pre function before recursion
+ * - execute the post function after recursion
+ */
 
 #ifdef HAVE_CONFIG_H
-# include <config.h>
+# include "config.h"
+#endif
+
+#ifdef HAVE_STDLIB_H
+# include <stdlib.h>
 #endif
 
-#include <stdlib.h>
 #include <stdio.h>
-#include "irgwalk.h"
-#include "irgraph.h"
-#include "irnode.h"
-#include "irprog.h"
-#include "type_or_entity.h"
 
-/* Make types visible to allow most efficient access */
-# include "entity_t.h"
+#include "typewalk.h"
+#include "entity_t.h"
 #include "type_t.h"
+#include "type_or_entity.h"
+#include "typegmod.h"
 
+#include "irprog_t.h"
+#include "irgraph_t.h"
+#include "irnode_t.h"
+#include "irgwalk.h"
+
+/**
+ * The walker environment
+ */
 typedef struct type_walk_env {
-  void *pre;
-  void *post;
-  void *env;
+  type_walk_func *pre;    /**< Pre-walker function */
+  type_walk_func *post;   /**< Post-walker function */
+  void *env;              /**< environment for walker functions */
 } type_walk_env;
 
+/* a walker for irn's */
+static void irn_type_walker(
+  ir_node *node, type_walk_func *pre, type_walk_func *post, void *env);
 
-void type_walk_2(type_or_ent *tore,
-	       void (pre)(type_or_ent*, void*),
-	       void (post)(type_or_ent*, void*),
-	       void *env)
+/**
+ * Main walker: walks over all used types/entities of a
+ * type entity.
+ */
+static void do_type_walk(type_or_ent *tore,
+			type_walk_func *pre,
+			type_walk_func *post,
+			void *env)
 {
-  int i;
+  int     i, n_types, n_mem;
+  entity  *ent;
+  type    *tp;
+  ir_node *n;
 
   /* marked? */
   switch (get_kind(tore)) {
   case k_entity:
-    if (((entity *)tore)->visit >= type_visited) return;
+    ent = (entity *)tore;
+    if (entity_visited(ent)) return;
     break;
   case k_type:
-    if(type_id == get_type_tpop((type*)tore)) {
-      type_walk_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
-      return;
-    }
-    if (((type *)tore)->visit >= type_visited) return;
+    tp = skip_tid((type *)tore);
+    if (type_visited(tp)) return;
     break;
   default:
     break;
   }
 
   /* execute pre method */
-  if(pre)
+  if (pre)
     pre(tore, env);
 
   /* iterate */
   switch (get_kind(tore)) {
   case k_entity:
-    {
+    mark_entity_visited(ent);
+    do_type_walk((type_or_ent *)get_entity_owner(ent), pre, post, env);
+    do_type_walk((type_or_ent *)get_entity_type(ent), pre, post, env);
+
+    if (get_entity_variability(ent) != variability_uninitialized) {
+      /* walk over the value types */
+      if (is_atomic_entity(ent)) {
+        n = get_atomic_ent_value(ent);
+        irn_type_walker(n, pre, post, env);
+      }
+      else {
+        n_mem = get_compound_ent_n_values(ent);
+        for (i = 0; i < n_mem; ++i) {
+          n = get_compound_ent_value(ent, i);
+          irn_type_walker(n, pre, post, env);
+        }
+      }
+    }
+    break;
+  case k_type:
+    mark_type_visited(tp);
+    switch (get_type_tpop_code(tp)) {
+
+    case tpo_class:
+      n_types = get_class_n_supertypes(tp);
+      for (i = 0; i < n_types; ++i)
+        do_type_walk((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
+
+      n_mem = get_class_n_members(tp);
+      for (i = 0; i < n_mem; ++i)
+        do_type_walk((type_or_ent *)get_class_member(tp, i), pre, post, env);
+
+      n_types = get_class_n_subtypes(tp);
+      for (i = 0; i < n_types; ++i)
+        do_type_walk((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
+      break;
+
+    case tpo_struct:
+      n_mem = get_struct_n_members(tp);
+      for (i = 0; i < n_mem; ++i)
+        do_type_walk((type_or_ent *)get_struct_member(tp, i), pre, post, env);
+      break;
+
+    case tpo_method:
+      n_mem = get_method_n_params(tp);
+      for (i = 0; i < n_mem; ++i)
+        do_type_walk((type_or_ent *)get_method_param_type(tp, i), pre, post, env);
+
+      n_mem = get_method_n_ress(tp);
+      for (i = 0; i < n_mem; ++i)
+        do_type_walk((type_or_ent *)get_method_res_type(tp, i), pre, post, env);
+      break;
+
+    case tpo_union:
+      n_mem = get_union_n_members(tp);
+      for (i = 0; i < n_mem; ++i)
+        do_type_walk((type_or_ent *)get_union_member(tp, i), pre, post, env);
+  	  break;
+
+    case tpo_array:
+      do_type_walk((type_or_ent *)get_array_element_type(tp),
+		        pre, post, env);
+      do_type_walk((type_or_ent *)get_array_element_entity(tp),
+		        pre, post, env);
+      break;
+
+    case tpo_enumeration:
+      /* a leave */
+      break;
+
+    case tpo_pointer:
+      do_type_walk((type_or_ent *)get_pointer_points_to_type(tp),
+		        pre, post, env);
+      break;
+
+    case tpo_primitive:
+    case tpo_id:
+    case tpo_none:
+    case tpo_unknown:
+      /* a leave. */
+      break;
+    default:
+      assert(0 && "Faulty type");
+      break;
+    }
+    break; /* end case k_type */
+
+  default:
+    printf(" *** Faulty type or entity! \n");
+    break;
+  }
+
+  /* execute post method */
+  if (post)
+    post(tore, env);
+
+  return;
+}
+
+/**  Check whether node contains types or entities as an attribute.
+     If so start a walk over that information. */
+static void irn_type_walker(
+  ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
+{
+  symconst_kind kind;
+
+  assert(node);
+
+  switch (get_irn_opcode(node)) {  /* node label */
+  case iro_SymConst:
+    kind = get_SymConst_kind(node);
+    if (kind == symconst_type_tag || kind == symconst_size)
+      do_type_walk((type_or_ent *)get_SymConst_type(node), pre, post, env);
+    else if (kind == symconst_addr_ent)
+      do_type_walk((type_or_ent *)get_SymConst_entity(node), pre, post, env);
+    break;
+  case iro_Sel:
+    do_type_walk((type_or_ent *)get_Sel_entity(node), pre, post, env);
+    break;
+  case iro_Call:
+    do_type_walk((type_or_ent *)get_Call_type(node), pre, post, env);
+    break;
+  case iro_Alloc:
+    do_type_walk((type_or_ent *)get_Alloc_type(node), pre, post, env);
+    break;
+  case iro_Free:
+    do_type_walk((type_or_ent *)get_Free_type(node), pre, post, env);
+    break;
+  case iro_Cast:
+    do_type_walk((type_or_ent *)get_Cast_type(node), pre, post, env);
+    break;
+  default:
+    break;
+  }
+}
+
+/**  Check whether node contains types or entities as an attribute.
+     If so start a walk over that information. */
+static void start_type_walk(ir_node *node, void *ctx) {
+  type_walk_env *env = ctx;
+  type_walk_func *pre;
+  type_walk_func *post;
+  void *envi;
+
+  pre  = env->pre;
+  post = env->post;
+  envi = env->env;
+
+  irn_type_walker(node, pre, post, envi);
+}
+
+/* walker: walks over all types */
+void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
+  int i, n_types = get_irp_n_types();
+
+  inc_master_type_visited();
+  for (i = 0; i < n_types; ++i) {
+    do_type_walk((type_or_ent *)get_irp_type(i), pre, post, env);
+  }
+  do_type_walk((type_or_ent *)get_glob_type(), pre, post, env);
+}
 
-      entity *ent = (entity *)tore;
-      ent->visit = type_visited;
-      type_walk_2((type_or_ent *)get_entity_owner(ent), pre, post, env);
-      type_walk_2((type_or_ent *)get_entity_type(ent), pre, post, env);
+void type_walk_irg (ir_graph *irg,
+		    void (*pre)(type_or_ent*, void*),
+		    void (*post)(type_or_ent*, void*),
+		    void *env)
+{
+  ir_graph *rem = current_ir_graph;
+  /* this is needed to pass the parameters to the walker that actually
+     walks the type information */
+  type_walk_env type_env;
+
+  type_env.pre  = pre;
+  type_env.post = post;
+  type_env.env  = env;
+
+  current_ir_graph = irg;
+
+  /* We walk over the irg to find all irnodes that contain an attribute
+     with type information.  If we find one we call a type walker to
+     touch the reachable type information.
+     The same type can be referenced by several irnodes.  To avoid
+     repeated visits of the same type node we must decrease the
+     type visited flag for each walk.  This is done in start_type_walk().
+     Here we initially increase the flag.  We only call do_type_walk that does
+     not increase the flag.
+  */
+  inc_master_type_visited();
+  irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
+
+  do_type_walk((type_or_ent *)get_irg_entity(irg), pre, post, env);
+
+  do_type_walk((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
+
+  current_ir_graph = rem;
+  return;
+}
+
+static void type_walk_s2s_2(type_or_ent *tore,
+			    void (*pre)(type_or_ent*, void*),
+			    void (*post)(type_or_ent*, void*),
+			    void *env)
+{
+  int i, n;
+
+  /* marked? */
+  switch (get_kind(tore)) {
+  case k_entity:
+    if (entity_visited((entity *)tore)) return;
+    break;
+  case k_type:
+    if (type_id == get_type_tpop((type*)tore)) {
+      type_walk_s2s_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
+      return;
     }
+    if (type_visited((type *)tore)) return;
+    break;
+  default:
     break;
+  }
+
+  /* iterate */
+  switch (get_kind(tore)) {
   case k_type:
     {
       type *tp = (type *)tore;
       mark_type_visited(tp);
       switch (get_type_tpop_code(tp)) {
       case tpo_class:
-	{
-	  for (i=0; i<get_class_n_supertype(tp); i++)
-	    type_walk_2((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
-	  for (i=0; i<get_class_n_member(tp); i++)
-	    type_walk_2((type_or_ent *)get_class_member(tp, i), pre, post, env);
-	  for (i=0; i<get_class_n_subtype(tp); i++)
-	    type_walk_2((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
-	}
-	break;
+        {
+          n = get_class_n_supertypes(tp);
+          for (i = 0; i < n; ++i) {
+            type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre,
+                            post, env);
+          }
+          /* execute pre method */
+          if (pre)
+            pre(tore, env);
+          tp = skip_tid((type*)tore);
+
+          n = get_class_n_subtypes(tp);
+          for (i = 0; i < n; ++i) {
+            type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre,
+                            post, env);
+          }
+
+          /* execute post method */
+          if (post)
+            post(tore, env);
+        }
+        break;
       case tpo_struct:
-	{
-	  for (i=0; i<get_struct_n_member(tp); i++)
-	    type_walk_2((type_or_ent *)get_struct_member(tp, i), pre, post, env);
-	}
-	break;
       case tpo_method:
-	{
-	  for (i = 0; i < get_method_n_params(tp); i++)
-	    type_walk_2((type_or_ent *)get_method_param_type(tp, i), pre, post, env);
-	  for (i = 0; i < get_method_n_res(tp); i++)
-	    type_walk_2((type_or_ent *)get_method_res_type(tp, i), pre, post, env);
-	}
-	break;
       case tpo_union:
-	{
-	  for (i = 0; i < get_union_n_members(tp); i++)
-	    type_walk_2((type_or_ent *)get_union_member(tp, i), pre, post, env);
-	}
-	break;
       case tpo_array:
-	type_walk_2((type_or_ent *)get_array_element_type(tp),
-		    pre, post, env);
-	break;
       case tpo_enumeration:
-	/* a leave */
-	break;
       case tpo_pointer:
-	type_walk_2((type_or_ent *)get_pointer_points_to_type(tp),
-		    pre, post, env);
-	break;
       case tpo_primitive:
       case tpo_id:
-	/* a leave. */
-	break;
+        /* dont care */
+        break;
       default:
-	printf(" *** Faulty type! \n");
-	break;
+        printf(" *** Faulty type! \n");
+        break;
       }
     } break; /* end case k_type */
+  case k_entity:
+    /* dont care */
+    break;
   default:
     printf(" *** Faulty type or entity! \n");
     break;
   }
+  return;
+}
 
-  /* execute post method */
-  if(post)
-    post(tore, env);
+void type_walk_super2sub(
+		  void (*pre)(type_or_ent*, void*),
+		  void (*post)(type_or_ent*, void*),
+		  void *env)
+{
+  int i, n_types = get_irp_n_types();
+  type *tp;
 
-  return;
+  inc_master_type_visited();
+  type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
+  for (i = 0; i < n_types; ++i) {
+    tp = get_irp_type(i);
+    type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
+  }
 }
 
-void start_type_walk(ir_node *node, void *env) {
-  void *pre  = ((type_walk_env *)env)->pre;
-  void *post = ((type_walk_env *)env)->post;
-  void *envi = ((type_walk_env *)env)->env;
+/*****************************************************************************/
 
-  assert(node);
+static void
+type_walk_super_2(type_or_ent *tore,
+		  void (*pre)(type_or_ent*, void*),
+		  void (*post)(type_or_ent*, void*),
+		  void *env)
+{
+  int i, n;
 
-  switch (get_irn_opcode(node)) {  /* node label */
-  case iro_SymConst:
-    if (   (get_SymConst_kind(node) == type_tag)
-	   || (get_SymConst_kind(node) == size))
-      type_walk_2((type_or_ent *)get_SymConst_type(node), pre, post, envi);
-    break;
-  case iro_Sel:
-    type_walk_2((type_or_ent *)get_Sel_entity(node), pre, post, envi);
+  /* marked? */
+  switch (get_kind(tore)) {
+  case k_entity:
+    if (entity_visited((entity *)tore)) return;
     break;
-  case iro_Call:
-    type_walk_2((type_or_ent *)get_Call_type(node), pre, post, envi);
+  case k_type:
+    if (type_id == get_type_tpop((type*)tore)) {
+      type_walk_super_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
+      return;
+    }
+    if (type_visited((type *)tore)) return;
     break;
-  case iro_Alloc:
-    type_walk_2((type_or_ent *)get_Alloc_type(node), pre, post, envi);
+  default:
     break;
-  case iro_Free:
-    printf("here in typewalk\n");
-    type_walk_2((type_or_ent *)get_Free_type(node), pre, post, envi);
+  }
+
+  /* iterate */
+  switch (get_kind(tore)) {
+  case k_type:
+    {
+      type *tp = (type *)tore;
+      mark_type_visited(tp);
+      switch (get_type_tpop_code(tp)) {
+      case tpo_class:
+        {
+          /* execute pre method */
+          if (pre)
+            pre(tore, env);
+          tp = skip_tid((type*)tore);
+
+          n = get_class_n_supertypes(tp);
+          for (i = 0; i < n; ++i) {
+            type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
+                              post, env);
+          }
+
+          /* execute post method */
+          if (post)
+            post(tore, env);
+        }
+        break;
+      case tpo_struct:
+      case tpo_method:
+      case tpo_union:
+      case tpo_array:
+      case tpo_enumeration:
+      case tpo_pointer:
+      case tpo_primitive:
+      case tpo_id:
+        /* dont care */
+        break;
+      default:
+        printf(" *** Faulty type! \n");
+        break;
+      }
+    } break; /* end case k_type */
+  case k_entity:
+    /* dont care */
     break;
   default:
+    printf(" *** Faulty type or entity! \n");
     break;
   }
+  return;
 }
 
-void type_walk(void (pre)(type_or_ent*, void*),
-	       void (post)(type_or_ent*, void*),
-	       void *env) {
-  int i;
-  ++type_visited;
-  type_walk_2((type_or_ent *)get_glob_type(), pre, post, env);
-  for (i = 0; i < get_irp_n_types(); i++) {
-    type_walk_2((type_or_ent *)get_irp_type(i), pre, post, env);
+void type_walk_super(
+		  void (*pre)(type_or_ent*, void*),
+		  void (*post)(type_or_ent*, void*),
+		  void *env) {
+  int i, n_types = get_irp_n_types();
+  type *tp;
+
+  inc_master_type_visited();
+  type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
+  for (i = 0; i < n_types; ++i) {
+    tp = get_irp_type(i);
+    type_walk_super_2((type_or_ent *)tp, pre, post, env);
   }
 }
 
-void type_walk_irg (ir_graph *irg,
-		    void (pre)(type_or_ent*, void*),
-		    void (post)(type_or_ent*, void*),
-		    void *env)
+/*****************************************************************************/
+
+
+static void
+class_walk_s2s_2(type *tp,
+		 void (*pre)(type*, void*),
+		 void (*post)(type*, void*),
+		 void *env)
 {
-  /* this is needed to pass the parameters to the walker that actually
-     walks the type information */
-  type_walk_env* type_env;
-  type_env = (type_walk_env *) malloc (sizeof(type_walk_env));
-  type_env->pre = pre;
-  type_env->post = post;
-  type_env->env = env;
+  int i, n;
+
+  /* marked? */
+  if (type_visited(tp)) return;
+
+  assert(is_Class_type(tp));
+  /* Assure all supertypes are visited before */
+  n = get_class_n_supertypes(tp);
+  for (i = 0; i < n; ++i) {
+    if (type_not_visited(get_class_supertype(tp, i)))
+      return;
+  }
+
+  mark_type_visited(tp);
 
-  ++type_visited;
-  irg_walk(get_irg_end(irg), start_type_walk, NULL, type_env);
+  /* execute pre method */
+  if (pre)
+    pre(tp, env);
 
-  type_walk_2((type_or_ent *)get_irg_ent(irg), pre, post, env);
+  tp = skip_tid(tp);
+  n = get_class_n_subtypes(tp);
+  for (i = 0; i < n; ++i) {
+    class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
+  }
+  /* execute post method */
+  if (post)
+    post(tp, env);
 
-  free(type_env);
   return;
 }
+
+void class_walk_super2sub(
+		  void (*pre)(type*, void*),
+		  void (*post)(type*, void*),
+		  void *env)
+{
+  int i, n_types = get_irp_n_types();
+  type *tp;
+
+  inc_master_type_visited();
+  for (i = 0; i < n_types; i++) {
+    tp = get_irp_type(i);
+    if (is_Class_type(tp) &&
+	      (get_class_n_supertypes(tp) == 0) &&
+	      type_not_visited(tp)) {
+      assert(! is_frame_type(tp));
+      assert(tp != get_glob_type());
+      class_walk_s2s_2(tp, pre, post, env);
+    }
+  }
+}
+
+
+/* Walks over all entities in the type */
+void walk_types_entities(
+		  type *tp,
+		  void (*doit)(entity*, void*),
+		  void *env)
+{
+  int i, n;
+
+  switch (get_type_tpop_code(tp)) {
+  case tpo_class:
+    n = get_class_n_members(tp);
+    for (i = 0; i < n; ++i)
+      doit(get_class_member(tp, i), env);
+    break;
+  case tpo_struct:
+    n = get_struct_n_members(tp);
+    for (i = 0; i < n; ++i)
+      doit(get_struct_member(tp, i), env);
+    break;
+  case tpo_union:
+    n = get_union_n_members(tp);
+    for (i = 0; i < n; ++i)
+      doit(get_union_member(tp, i), env);
+    break;
+  case tpo_array:
+    doit(get_array_element_entity(tp), env);
+    break;
+  case tpo_method:
+  case tpo_enumeration:
+  case tpo_pointer:
+  case tpo_primitive:
+  case tpo_id:
+  default:
+    break;
+  }
+}