* Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*/
-/*
- * traverse the type information. The walker walks the whole ir graph
+/**
+ * @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_t.h"
-#include "irnode.h"
-#include "irprog.h"
-#include "type_or_entity.h"
-#include "typegmod.h"
-#include "typewalk.h"
-/* Make types visible to allow most efficient access */
+#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 {
- type_walk_func *pre;
- type_walk_func *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);
-static 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;
+ ir_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((ir_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:
- {
-
- 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);
+ 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:
- {
- type *tp = (type *)tore;
- mark_type_visited(tp);
- switch (get_type_tpop_code(tp)) {
- case tpo_class:
- {
- for (i=0; i<get_class_n_supertypes(tp); i++)
- type_walk_2((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
- for (i=0; i<get_class_n_members(tp); i++)
- type_walk_2((type_or_ent *)get_class_member(tp, i), pre, post, env);
- for (i=0; i<get_class_n_subtypes(tp); i++)
- type_walk_2((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
- }
- break;
- case tpo_struct:
- {
- for (i=0; i<get_struct_n_members(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_ress(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);
- type_walk_2((type_or_ent *)get_array_element_entity(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;
- default:
- printf(" *** Faulty type! \n");
- break;
- }
- } break; /* end 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)
+ if (post)
post(tore, env);
return;
}
-/** Check wether node contains types or entities as an attribute.
+/** 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 *env) {
- type_walk_func *pre;
- type_walk_func *post;
- void *envi;
-
- pre = ((type_walk_env *)env)->pre;
- post = ((type_walk_env *)env)->post;
- envi = ((type_walk_env *)env)->env;
+static void irn_type_walker(
+ ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
+{
+ entity *ent;
+ ir_type *tp;
assert(node);
- 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);
- break;
- case iro_Call:
- type_walk_2((type_or_ent *)get_Call_type(node), pre, post, envi);
- break;
- case iro_Alloc:
- type_walk_2((type_or_ent *)get_Alloc_type(node), pre, post, envi);
- break;
- case iro_Free:
- type_walk_2((type_or_ent *)get_Free_type(node), pre, post, envi);
- break;
- case iro_Cast:
- type_walk_2((type_or_ent *)get_Cast_type(node), pre, post, envi);
- break;
- default:
- break;
- }
+ ent = get_irn_entity_attr(node);
+ if (ent)
+ do_type_walk((type_or_ent *)ent, pre, post, env);
+ tp = get_irn_type_attr(node);
+ if (tp)
+ do_type_walk((type_or_ent *)tp, pre, post, env);
}
-void type_walk(type_walk_func pre,
- type_walk_func post,
- void *env) {
- int i;
- ++type_visited;
- /*type_walk_2((type_or_ent *)get_glob_type(), pre, post, env);
- global type is on the list visited below, too. */
- for (i = 0; i < get_irp_n_types(); i++) {
- type_walk_2((type_or_ent *)get_irp_type(i), pre, post, env);
+/** 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);
}
- type_walk_2((type_or_ent *)get_glob_type(), pre, post, env);
+ do_type_walk((type_or_ent *)get_glob_type(), pre, post, env);
}
void type_walk_irg (ir_graph *irg,
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 type_walk_2 that does
+ Here we initially increase the flag. We only call do_type_walk that does
not increase the flag.
*/
- ++type_visited;
+ inc_master_type_visited();
irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
- type_walk_2((type_or_ent *)get_irg_ent(irg), pre, post, env);
+ do_type_walk((type_or_ent *)get_irg_entity(irg), pre, post, env);
- type_walk_2((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
+ do_type_walk((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
current_ir_graph = rem;
return;
void (*post)(type_or_ent*, void*),
void *env)
{
- int i;
+ int i, n;
/* marked? */
switch (get_kind(tore)) {
case k_entity:
- if (((entity *)tore)->visit >= type_visited) return;
+ 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);
+ if (type_id == get_type_tpop((ir_type*)tore)) {
+ type_walk_s2s_2((type_or_ent *)skip_tid((ir_type *)tore), pre, post, env);
return;
}
- if (((type *)tore)->visit >= type_visited) return;
+ if (type_visited((ir_type *)tore)) return;
break;
default:
break;
switch (get_kind(tore)) {
case k_type:
{
- type *tp = (type *)tore;
+ ir_type *tp = (ir_type *)tore;
mark_type_visited(tp);
switch (get_type_tpop_code(tp)) {
case tpo_class:
- {
- for (i = 0; i < get_class_n_supertypes(tp); 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);
-
- for (i = 0; i < get_class_n_subtypes(tp); 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;
+ {
+ 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((ir_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:
case tpo_method:
case tpo_union:
case tpo_pointer:
case tpo_primitive:
case tpo_id:
- /* dont care */
- break;
+ /* dont care */
+ break;
default:
- printf(" *** Faulty type! \n");
- break;
+ printf(" *** Faulty type! \n");
+ break;
}
} break; /* end case k_type */
case k_entity:
void (*post)(type_or_ent*, void*),
void *env)
{
- int i;
- type *tp;
- ++type_visited;
+ int i, n_types = get_irp_n_types();
+ ir_type *tp;
+
+ inc_master_type_visited();
type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
- for (i = 0; i < get_irp_n_types(); i++) {
+ for (i = 0; i < n_types; ++i) {
tp = get_irp_type(i);
type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
}
void (*post)(type_or_ent*, void*),
void *env)
{
- int i;
+ int i, n;
/* marked? */
switch (get_kind(tore)) {
case k_entity:
- if (((entity *)tore)->visit >= type_visited) return;
+ if (entity_visited((entity *)tore)) return;
break;
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);
+ if (type_id == get_type_tpop((ir_type*)tore)) {
+ type_walk_super_2((type_or_ent *)skip_tid((ir_type *)tore), pre, post, env);
return;
}
- if (((type *)tore)->visit >= type_visited) return;
+ if (type_visited((ir_type *)tore)) return;
break;
default:
break;
switch (get_kind(tore)) {
case k_type:
{
- type *tp = (type *)tore;
+ ir_type *tp = (ir_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);
-
- for (i = 0; i < get_class_n_supertypes(tp); 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;
+ {
+ /* execute pre method */
+ if (pre)
+ pre(tore, env);
+ tp = skip_tid((ir_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_pointer:
case tpo_primitive:
case tpo_id:
- /* dont care */
- break;
+ /* dont care */
+ break;
default:
- printf(" *** Faulty type! \n");
- break;
+ printf(" *** Faulty type! \n");
+ break;
}
} break; /* end case k_type */
case k_entity:
void (*pre)(type_or_ent*, void*),
void (*post)(type_or_ent*, void*),
void *env) {
- int i;
- type *tp;
- ++type_visited;
+ int i, n_types = get_irp_n_types();
+ ir_type *tp;
+
+ inc_master_type_visited();
type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
- for (i = 0; i < get_irp_n_types(); i++) {
+ for (i = 0; i < n_types; ++i) {
tp = get_irp_type(i);
type_walk_super_2((type_or_ent *)tp, pre, post, env);
}
static void
-class_walk_s2s_2(type *tp,
- void (*pre)(type*, void*),
- void (*post)(type*, void*),
+class_walk_s2s_2(ir_type *tp,
+ void (*pre)(ir_type*, void*),
+ void (*post)(ir_type*, void*),
void *env)
{
- int i;
+ int i, n;
/* marked? */
- if (tp->visit >= type_visited) return;
+ if (type_visited(tp)) return;
- assert(is_class_type(tp));
+ assert(is_Class_type(tp));
/* Assure all supertypes are visited before */
- for (i=0; i < get_class_n_supertypes(tp); i++) {
- if (get_type_visited(get_class_supertype(tp, i)) < type_visited)
+ 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);
/* execute pre method */
- if(pre)
+ if (pre)
pre(tp, env);
- tp = skip_tid((type*)tp);
- for (i=0; i<get_class_n_subtypes(tp); i++) {
+ 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)
+ if (post)
post(tp, env);
return;
}
-#if 0
void class_walk_super2sub(
- void (*pre)(type*, void*),
- void (*post)(type*, void*),
+ void (*pre)(ir_type*, void*),
+ void (*post)(ir_type*, void*),
void *env)
{
- int i;
- type *tp;
+ int i, n_types = get_irp_n_types();
+ ir_type *tp;
- ++type_visited;
- for (i = 0; i < get_irp_n_types(); i++) {
+ 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) &&
- (tp->visit < type_visited) &&
- (!is_frame_type(tp)) &&
- (tp != get_glob_type())) {
- class_walk_s2s_2(tp, pre, post, env);
- }
- }
-}
-#endif
-void class_walk_super2sub(
- void (*pre)(type*, void*),
- void (post)(type*, void*),
- void *env)
-{
- int i;
- type *tp;
-
- ++type_visited;
- for (i = 0; i < get_irp_n_types(); i++) {
- tp = get_irp_type(i);
- if (is_class_type(tp) &&
- (get_class_n_supertypes(tp) == 0) &&
- (tp->visit < type_visited)) {
- assert(!is_frame_type(tp));
+ 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,
+ ir_type *tp,
void (*doit)(entity*, void*),
void *env)
{
- int i;
- switch(get_type_tpop_code(tp)) {
- case tpo_class: {
- for (i=0; i<get_class_n_members(tp); i++)
+ 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: {
- for (i=0; i<get_struct_n_members(tp); i++)
+ 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: {
- for (i = 0; i < get_union_n_members(tp); i++)
+ 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;
+ break;
+ case tpo_array:
+ doit(get_array_element_entity(tp), env);
+ break;
case tpo_method:
case tpo_enumeration:
case tpo_pointer: