This add a linearization phase. It's not even close to done

yet, but the framework is there. When we linearize the tree we just generate a list of basic blocks of statement expressions (and branches between them, although that "small details" isn't actually done yet ;).
author: Linus Torvalds <torvalds@home.osdl.org> 2004-02-11 14:53:39 -0700
committer: Linus Torvalds <torvalds@ppc970.osdl.org> 2005-04-07 21:01:20 -0700
commit: 7f2bd1a27e9df408cbae57cf2aa9aa45383a7bb7 (patch)
tree: 5074b20247dbc3ce9ed5296ddc42fc0a4ba872d6
parent: 3ffb6bac9871d6e2ed08ffbd61835561c48e9608 (diff)
download: sparse-dev-7f2bd1a27e9df408cbae57cf2aa9aa45383a7bb7.tar.gz
4 files changed, 160 insertions, 0 deletions
diff --git a/lib.c b/lib.c
index 249b6798..40c512de 100644
--- a/lib.c
+++ b/lib.c
@@ -24,6 +24,7 @@
 #include "symbol.h"
 #include "expression.h"
 #include "scope.h"
+#include "linearize.h"
 
 struct token *skip_to(struct token *token, int op)
 {
@@ -155,6 +156,8 @@ struct allocator_struct statement_allocator = { "statements", NULL, __alignof__(
 struct allocator_struct string_allocator = { "strings", NULL, __alignof__(struct statement), CHUNK };
 struct allocator_struct scope_allocator = { "scopes", NULL, __alignof__(struct scope), CHUNK };
 struct allocator_struct bytes_allocator = { "bytes", NULL, 1, CHUNK };
+struct allocator_struct basic_block_allocator = { "basic_block", NULL, __alignof__(struct basic_block), CHUNK };
+struct allocator_struct entrypoint_allocator = { "entrypoint", NULL, __alignof__(struct entrypoint), CHUNK };
 
 #define __ALLOCATOR(type, size, x)				\
 	type *__alloc_##x(int extra)				\
@@ -174,6 +177,7 @@ struct allocator_struct bytes_allocator = { "bytes", NULL, 1, CHUNK };
 ALLOCATOR(ident); ALLOCATOR(token); ALLOCATOR(symbol);
 ALLOCATOR(expression); ALLOCATOR(statement); ALLOCATOR(string);
 ALLOCATOR(scope); __ALLOCATOR(void, 0, bytes);
+ALLOCATOR(basic_block); ALLOCATOR(entrypoint);
 
 int ptr_list_size(struct ptr_list *head)
 {
@@ -235,6 +239,14 @@ void add_ptr_list(struct ptr_list **listp, void *ptr)
 	list->nr = nr;
 }
 
+void copy_ptr_list(struct ptr_list *a, struct ptr_list **b)
+{
+	void *entry;
+	FOR_EACH_PTR(a, entry) {
+		add_ptr_list(b, entry);
+	} END_FOR_EACH_PTR;
+}
+
 void free_ptr_list(struct ptr_list **listp)
 {
 	struct ptr_list *tmp, *list = *listp;
diff --git a/lib.h b/lib.h
index 5409e2c4..6a6cc119 100644
--- a/lib.h
+++ b/lib.h
@@ -28,6 +28,8 @@ struct statement;
 struct statement_list;
 struct expression;
 struct expression_list;
+struct basic_block;
+struct entrypoint;
 
 struct token *skip_to(struct token *, int);
 struct token *expect(struct token *, int, const char *);
@@ -48,6 +50,9 @@ DECLARE_ALLOCATOR(statement);
 DECLARE_ALLOCATOR(string);
 DECLARE_ALLOCATOR(scope);
 __DECLARE_ALLOCATOR(void, bytes);
+DECLARE_ALLOCATOR(basic_block);
+DECLARE_ALLOCATOR(entrypoint);
+
 
 #define LIST_NODE_NR (29)
 
@@ -62,6 +67,7 @@ struct ptr_list {
 #define ITERATE_LAST 2
 void iterate(struct ptr_list *,void (*callback)(void *, void *, int), void*);
 extern void add_ptr_list(struct ptr_list **, void *);
+extern void copy_ptr_list(struct ptr_list *a, struct ptr_list **b);
 extern void free_ptr_list(struct ptr_list **);
 extern int ptr_list_size(struct ptr_list *);
 extern char **handle_switch(char *arg, char **next);
@@ -79,6 +85,11 @@ extern void create_builtin_stream(void);
 #define statement_list_size(list) ptr_list_size((struct ptr_list *)(list))
 #define expression_list_size(list) ptr_list_size((struct ptr_list *)(list))
 
+static inline void copy_symbol_list(struct symbol_list *from, struct symbol_list **to)
+{
+	copy_ptr_list((struct ptr_list *)from, (struct ptr_list **)to);
+}
+
 static inline void add_symbol(struct symbol_list **list, struct symbol *sym)
 {
 	add_ptr_list((struct ptr_list **)list, sym);
diff --git a/linearize.c b/linearize.c
new file mode 100644
index 00000000..ccaca661
--- /dev/null
+++ b/linearize.c
@@ -0,0 +1,110 @@
+/*
+ * Linearize - walk the statement tree (but _not_ the expressions)
+ * to generate a linear version of it and the basic blocks. 
+ *
+ * NOTE! We're not interested in the actual sub-expressions yet,
+ * even though they can generate conditional branches and
+ * subroutine calls. That's all "local" behaviour.
+ *
+ * Copyright (C) 2004 Linus Torvalds
+ */
+
+#include <string.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "linearize.h"
+
+static struct entrypoint *alloc_entrypoint(void)
+{
+	return __alloc_entrypoint(0);
+}
+
+static struct basic_block *alloc_basic_block(void)
+{
+	return __alloc_basic_block(0);
+}
+
+static void show_bb(struct basic_block *bb)
+{
+	struct statement *stmt;
+
+	printf("bb: %p\n", bb);
+	FOR_EACH_PTR(bb->stmts, stmt) {
+		show_statement(stmt);
+	} END_FOR_EACH_PTR;
+}
+
+static void show_entry(struct entrypoint *ep)
+{
+	struct symbol *sym;
+	struct basic_block *bb;
+
+	printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
+
+	FOR_EACH_PTR(ep->syms, sym) {
+		printf("   sym: %p %s\n", sym, show_ident(sym->ident));
+	} END_FOR_EACH_PTR;
+
+	printf("\n");
+
+	FOR_EACH_PTR(ep->bbs, bb) {
+		show_bb(bb);
+	} END_FOR_EACH_PTR;
+
+	printf("\n");
+}
+
+static struct basic_block * linearize_statement(struct symbol_list **syms,
+	struct basic_block_list **bbs,
+	struct basic_block *bb,
+	struct statement *stmt)
+{
+	if (!stmt)
+		return bb;
+
+	switch (stmt->type) {
+	case STMT_NONE:
+		return bb;
+
+	case STMT_EXPRESSION:
+		add_statement(&bb->stmts, stmt);
+		break;
+
+	case STMT_COMPOUND: {
+		struct statement *s;
+		copy_symbol_list(stmt->syms, syms);
+		FOR_EACH_PTR(stmt->stmts, s) {
+			bb = linearize_statement(syms, bbs, bb, s);
+		} END_FOR_EACH_PTR;
+		break;
+	}
+
+	default:
+		break;
+	}
+	return bb;
+}
+
+void linearize_symbol(struct symbol *sym)
+{
+	struct symbol *base_type;
+
+	if (!sym)
+		return;
+	base_type = sym->ctype.base_type;
+	if (!base_type)
+		return;
+	if (base_type->type == SYM_FN) {
+		if (base_type->stmt) {
+			struct entrypoint *ep = alloc_entrypoint();
+			struct basic_block *bb = alloc_basic_block();
+			ep->name = sym;
+			add_bb(&ep->bbs, bb);
+			copy_symbol_list(base_type->arguments, &ep->syms);
+			linearize_statement(&ep->syms, &ep->bbs, bb, base_type->stmt);
+			show_entry(ep);
+		}
+	}
+}
diff --git a/linearize.h b/linearize.h
new file mode 100644
index 00000000..22761dfc
--- /dev/null
+++ b/linearize.h
@@ -0,0 +1,27 @@
+#ifndef LINEARIZE_H
+#define LINEARIZE_H
+
+#include "lib.h"
+#include "token.h"
+#include "parse.h"
+#include "symbol.h"
+
+struct basic_block_list;
+
+struct basic_block {
+	struct statement_list *stmts;
+};
+
+static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
+{
+	add_ptr_list((struct ptr_list **)list, bb);
+}
+
+struct entrypoint {
+	struct symbol *name;
+	struct symbol_list *syms;
+	struct basic_block_list *bbs;
+};
+
+#endif /* LINEARIZE_H */
+
author	Linus Torvalds <torvalds@home.osdl.org>	2004-02-11 14:53:39 -0700
committer	Linus Torvalds <torvalds@ppc970.osdl.org>	2005-04-07 21:01:20 -0700
commit	7f2bd1a27e9df408cbae57cf2aa9aa45383a7bb7 (patch)
tree	5074b20247dbc3ce9ed5296ddc42fc0a4ba872d6
parent	3ffb6bac9871d6e2ed08ffbd61835561c48e9608 (diff)
download	sparse-dev-7f2bd1a27e9df408cbae57cf2aa9aa45383a7bb7.tar.gz