add dynamic typing example

12 files changed, 269 insertions, 1 deletions

diff --git a/python/examples/dynamic_typing/.gitignore b/python/examples/dynamic_typing/.gitignore
new file mode 100644
index 0000000..9daeafb
--- /dev/null
+++ b/python/examples/dynamic_typing/.gitignore
@@ -0,0 +1 @@
+test
diff --git a/python/examples/dynamic_typing/Makefile b/python/examples/dynamic_typing/Makefile
new file mode 100644
index 0000000..b32e6cb
--- /dev/null
+++ b/python/examples/dynamic_typing/Makefile
@@ -0,0 +1,8 @@
+test: test.c runtime/dynamic_typing.o
+	dietcc -I $(PWD)/runtime -o $@ $^ --dietc-pass $(PWD)/dietpass
+
+runtime/dynamic_typing.o: runtime/dynamic_typing.c
+	gcc -c -o $@ $^
+
+clean:
+	rm -f runtime/dynamic_typing.o test
diff --git a/python/examples/dynamic_typing/dietc.py b/python/examples/dynamic_typing/dietc.py
new file mode 120000
index 0000000..8cb9097
--- /dev/null
+++ b/python/examples/dynamic_typing/dietc.py
@@ -0,0 +1 @@
+../../dietc.py
\ No newline at end of file
diff --git a/python/examples/dynamic_typing/dietpass b/python/examples/dynamic_typing/dietpass
new file mode 100755
index 0000000..5d15e19
--- /dev/null
+++ b/python/examples/dynamic_typing/dietpass
@@ -0,0 +1,50 @@
+#!/bin/python3
+import os
+import sys
+from dietc import *
+
+def main():
+    prog = Program(open(sys.argv[1], "rb").read())
+    for function in prog.functions:
+        fn_locals = function.locals()
+        start_i = function.code_start()
+        new_body = []
+        for op in function.body:
+            new_body.append(op)
+            # only look for casts to void
+            if " = ( " not in op.line: continue
+            if op.lhs_type(prog) != PointerType(BasicType("void")): continue
+            # if one is found, construct & annotate its type
+            rhs_type = prog.object_types[op[-2]]
+            type_ptr = describe_type(prog, rhs_type, new_body)
+            new_body.append(Instruction(
+                f"annotate_type({op[0]}, {type_ptr});"))
+        function.body = new_body
+    prog.preamble.append("#include <stddef.h>")
+    prog.print()
+
+def describe_type(prog, type_, new_body):
+    name = f"type_{count()}"
+    if isinstance(type_, BasicType):
+        new_body.append(Instruction(
+            f"void *{name} = make_basic(\"{type_.name}\", sizeof({type_.name}));"))
+    elif isinstance(type_, ArrayType):
+        base = describe_type(prog, type_.base, new_body)
+        new_body.append(Instruction(
+            f"void *{name} = make_array({base}, {type_.length});"))
+    elif isinstance(type_, PointerType):
+        base = describe_type(prog, type_.base, new_body)
+        new_body.append(Instruction(
+            f"void *{name} = make_pointer({base});"))
+    elif isinstance(type_, AggregateType):
+        tname = prog.type_to_name[type_]
+        new_body.append(Instruction(
+            f"void *{name} = make_struct(sizeof({tname}));"))
+        for fn, ft in reversed(type_.fields):
+            field = describe_type(prog, ft, new_body)
+            new_body.append(Instruction(
+                f"prepend_member({name}, {field}, \"{fn}\", offsetof({tname}, {fn}));"))
+    else: raise NotImplementedError
+    return name
+
+main()
diff --git a/python/examples/dynamic_typing/runtime/dynamic_typing.c b/python/examples/dynamic_typing/runtime/dynamic_typing.c
new file mode 100644
index 0000000..4e47bc9
--- /dev/null
+++ b/python/examples/dynamic_typing/runtime/dynamic_typing.c
@@ -0,0 +1,72 @@
+#include <stdlib.h>
+#include "dynamic_typing.h"
+
+struct entry {
+    void *start;
+    void *end;
+    struct type *type;
+};
+
+static struct entry *ENTRIES;
+static unsigned long N_ENTRIES;
+
+void annotate_type(void *ptr, struct type *type) {
+    ENTRIES = realloc(ENTRIES, (++N_ENTRIES) * sizeof(ENTRIES[0]));
+    ENTRIES[N_ENTRIES - 1] = (struct entry){
+        .start = ptr,
+        .end = ptr + 1,
+        .type = type,
+    };
+}
+
+struct type *dynamic_typeof(void *ptr) {
+    for (unsigned long i = N_ENTRIES; i --> 0;)
+        if (ENTRIES[i].start <= ptr && ptr < ENTRIES[i].end)
+            return ENTRIES[i].type;
+    return 0;
+}
+
+struct type *make_basic(const char *type, unsigned long size) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_BASIC;
+    t->basic = type;
+    t->size = size;
+    return t;
+}
+
+struct type *make_array(struct type *base, unsigned long len) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_ARRAY;
+    t->base = base;
+    t->length = len;
+    t->size = len * t->base->size;
+    return t;
+}
+
+struct type *make_pointer(struct type *base) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_POINTER;
+    t->base = base;
+    t->size = sizeof(void*);
+    return t;
+}
+
+// function not supported yet
+// for struct & union, the members are initialized by the caller
+struct type *make_struct(unsigned long size) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_STRUCT;
+    return t;
+}
+
+struct type *make_union(unsigned long size) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_UNION;
+    return t;
+}
+void prepend_member(struct type *aggregate, struct type *member, const char *name, unsigned long offset) {
+    member->offset = offset;
+    member->next_member = aggregate->members;
+    member->field_name = name;
+    aggregate->members = member;
+}
diff --git a/python/examples/dynamic_typing/runtime/dynamic_typing.h b/python/examples/dynamic_typing/runtime/dynamic_typing.h
new file mode 100644
index 0000000..4f7b1aa
--- /dev/null
+++ b/python/examples/dynamic_typing/runtime/dynamic_typing.h
@@ -0,0 +1,48 @@
+#ifndef DYNAMIC_TYPING_
+#define DYNAMIC_TYPING_
+
+enum TYPE_KIND {
+    TY_BASIC,
+    TY_ARRAY,
+    TY_POINTER,
+    TY_FUNCTION,
+    TY_STRUCT,
+    TY_UNION,
+};
+
+struct type {
+    enum TYPE_KIND kind;
+    unsigned long size;
+
+    // basic types:
+    const char *basic;
+
+    // array & pointer types:
+    struct type *base;
+    unsigned long length;
+
+    // struct & union types
+    struct type *members;
+    struct type *next_member;
+    unsigned long offset;
+    const char *field_name;
+
+    // function types:
+    struct type *return_type;
+    struct type *params;
+    struct type *next_param;
+};
+
+struct type *dynamic_typeof(void *ptr);
+
+struct type *make_basic(const char *type, unsigned long size);
+struct type *make_array(struct type *base, unsigned long len);
+struct type *make_pointer(struct type *base);
+// function not supported yet
+// for struct & union, the members are initialized by the caller
+struct type *make_struct(unsigned long size);
+struct type *make_union(unsigned long size);
+void prepend_member(struct type *aggregate, struct type *member, const char *name, unsigned long offset);
+void annotate_type(void *ptr, struct type *type);
+
+#endif
diff --git a/python/examples/dynamic_typing/test.c b/python/examples/dynamic_typing/test.c
new file mode 100644
index 0000000..86e2229
--- /dev/null
+++ b/python/examples/dynamic_typing/test.c
@@ -0,0 +1,76 @@
+#include <string.h>
+#include <stdio.h>
+#include <dynamic_typing.h>
+
+void pprint_(void *obj, struct type *type) {
+    switch (type->kind) {
+    case TY_BASIC:
+        switch (type->size) {
+        case sizeof(char):
+            printf("(%s)%lu", type->basic, (unsigned long)*(unsigned char *)obj);
+            break;
+        case sizeof(short):
+            printf("(%s)%lu", type->basic, (unsigned long)*(unsigned short *)obj);
+            break;
+        case sizeof(int):
+            printf("(%s)%lu", type->basic, (unsigned long)*(unsigned int *)obj);
+            break;
+        case sizeof(long):
+            printf("(%s)%lu", type->basic, (unsigned long)*(unsigned long *)obj);
+            break;
+        default:
+            printf("?");
+            break;
+        }
+        break;
+    case TY_ARRAY:
+        printf("{ ");
+        void *ptr = obj;
+        for (unsigned long i = 0; i < type->length; i++) {
+            pprint_(obj, type->base);
+            obj += type->base->size;
+            if (i + 1 < type->length) printf(", ");
+            else printf(" ");
+        }
+        printf("}");
+        break;
+    case TY_POINTER:
+        printf("%p[%ld]", *(void **)obj, type->length);
+        break;
+    case TY_FUNCTION:
+        printf("<function>");
+        break;
+    case TY_STRUCT:
+        printf("{ ");
+        for (struct type *member = type->members; member; member = member->next_member) {
+            printf(".%s = ", member->field_name);
+            pprint_((void*)obj + member->offset, member);
+            if (member->next_member) printf(", ");
+            else printf(" ");
+        }
+        printf("}");
+        break;
+    case TY_UNION:
+        printf("<union>");
+        break;
+    }
+}
+
+void pprint(void *obj) {
+    pprint_(obj, dynamic_typeof(obj)->base);
+    printf("\n");
+}
+
+int main() {
+    struct {
+        char x;
+        int y;
+        int z[3];
+    } foo = {1, 2, {3, 4, 5}};
+    pprint(&foo);
+    struct {
+        char a;
+        int b;
+    } bar = {100, 200};
+    pprint(&bar);
+}
diff --git a/python/examples/zero_init/.gitignore b/python/examples/zero_init/.gitignore
new file mode 100644
index 0000000..b74bd7f
--- /dev/null
+++ b/python/examples/zero_init/.gitignore
@@ -0,0 +1,2 @@
+default
+instrumented
diff --git a/python/examples/zero_init/Makefile b/python/examples/zero_init/Makefile
new file mode 100644
index 0000000..92f29b7
--- /dev/null
+++ b/python/examples/zero_init/Makefile
@@ -0,0 +1,10 @@
+all: default instrumented
+
+default: test.c
+	gcc -O0 $^ -o $@
+
+instrumented: test.c
+	dietcc -O0 $^ -o $@ --dietc-pass $(PWD)/dietpass
+
+clean:
+	rm -f default instrumented
diff --git a/python/examples/zero_init/dietc.py b/python/examples/zero_init/dietc.py
new file mode 120000
index 0000000..8cb9097
--- /dev/null
+++ b/python/examples/zero_init/dietc.py
@@ -0,0 +1 @@
+../../dietc.py
\ No newline at end of file
diff --git a/python/examples/zero_init b/python/examples/zero_init/dietpass
index e2ab92e..1984d81 100755
--- a/python/examples/zero_init
+++ b/python/examples/zero_init/dietpass
@@ -1,7 +1,6 @@
 #!/bin/python3
 import os
 import sys
-sys.path.append(os.path.dirname(os.path.dirname(os.path.realpath(__file__))))
 import dietc
 
 prog = dietc.Program(open(sys.argv[1], "rb").read())
diff --git a/python/examples/test_files/zero_init.c b/python/examples/zero_init/test.c
index 5db109a..5db109a 100644
--- a/python/examples/test_files/zero_init.c
+++ b/python/examples/zero_init/test.c