From 2b8985608d33abaae7b201a008e292cbbe2167ef Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Thu, 27 Jul 2023 14:26:33 -0700 Subject: add automated refcounting pass --- python/examples/refcounting/.gitignore | 1 + python/examples/refcounting/Makefile | 8 ++ python/examples/refcounting/dietc.py | 1 + python/examples/refcounting/dietpass | 76 +++++++++++++++ python/examples/refcounting/runtime/refcounting.c | 114 ++++++++++++++++++++++ python/examples/refcounting/runtime/refcounting.h | 8 ++ python/examples/refcounting/test.c | 34 +++++++ 7 files changed, 242 insertions(+) create mode 100644 python/examples/refcounting/.gitignore create mode 100644 python/examples/refcounting/Makefile create mode 120000 python/examples/refcounting/dietc.py create mode 100755 python/examples/refcounting/dietpass create mode 100644 python/examples/refcounting/runtime/refcounting.c create mode 100644 python/examples/refcounting/runtime/refcounting.h create mode 100644 python/examples/refcounting/test.c (limited to 'python/examples') diff --git a/python/examples/refcounting/.gitignore b/python/examples/refcounting/.gitignore new file mode 100644 index 0000000..9daeafb --- /dev/null +++ b/python/examples/refcounting/.gitignore @@ -0,0 +1 @@ +test diff --git a/python/examples/refcounting/Makefile b/python/examples/refcounting/Makefile new file mode 100644 index 0000000..2d5e9d5 --- /dev/null +++ b/python/examples/refcounting/Makefile @@ -0,0 +1,8 @@ +test: test.c runtime/refcounting.o + dietcc -I $(PWD)/runtime -o $@ $^ --dietc-pass $(PWD)/dietpass + +runtime/refcounting.o: runtime/refcounting.c + gcc -c -o $@ $^ + +clean: + rm -f runtime/refcounting.o test diff --git a/python/examples/refcounting/dietc.py b/python/examples/refcounting/dietc.py new file mode 120000 index 0000000..8cb9097 --- /dev/null +++ b/python/examples/refcounting/dietc.py @@ -0,0 +1 @@ +../../dietc.py \ No newline at end of file diff --git a/python/examples/refcounting/dietpass b/python/examples/refcounting/dietpass new file mode 100755 index 0000000..9a7b0e8 --- /dev/null +++ b/python/examples/refcounting/dietpass @@ -0,0 +1,76 @@ +#!/bin/python3 +import os +import sys +from dietc import * + +def eprint(*args): print(*args, file=sys.stderr) + +def main(): + prog = Program(open(sys.argv[1], "rb").read()) + prog.preamble.append("#include ") + for function in prog.functions: + # (1) rewrite calloc, free, ... calls to refcount_* + for name in ("calloc", "free", "malloc", "realloc"): + function.body = [instr.replace_token(name, f"refcount_{name}") + for instr in function.body] + new_body = function.body[:function.code_start()] + # (2a) initialize all pointer expressions to 0 + for local in function.locals(): + for p in ptr_exprs(local, prog.object_types[local]): + new_body.append(Instruction(f"{p} = 0 ;")) + # (2b) whenever a pointer is written to, call refcount_write + for instr in function.body[function.code_start():]: + if instr[0] == "*" and instr[2] == "=": + refcount_pairs = [] + ty = prog.object_types[instr[1]].base + for expr in ptr_exprs(f"(*{instr[1]})", ty): + backup = f"_refcount_ptr_backup_{count()}" + new_body.append(Instruction(f"void * {backup} = {expr} ;")) + refcount_pairs.append((backup, expr)) + new_body.append(instr) + for old, new in refcount_pairs: + new_body.append(Instruction(f"refcount_write({new},{old});")) + elif instr[1] == "=": + refcount_pairs = [] + ty = prog.object_types[instr[0]] + for expr in ptr_exprs(instr[0], ty): + backup = f"_refcount_ptr_backup_{count()}" + new_body.append(Instruction(f"void * {backup} = {expr} ;")) + refcount_pairs.append((backup, expr)) + new_body.append(instr) + for old, new in refcount_pairs: + new_body.append(Instruction(f"refcount_write({new},{old});")) + elif instr[0] == "return": + for local in function.locals(): + if local == instr[1]: continue + for expr in ptr_exprs(local, prog.object_types[local]): + new_body.append(Instruction(f"refcount_write(0,({expr}));")) + if instr[1] != ";": + for expr in ptr_exprs(instr[1], prog.object_types[instr[1]]): + new_body.append(Instruction(f"refcount_returning({expr});")) + new_body.append(instr) + else: + new_body.append(instr) + function.body = new_body + prog.print() + +# given an object and its type, returns a list of l-value expression strings, +# representing all of the pointers in that object +def ptr_exprs(name, ty): + if isinstance(ty, PointerType): + return [name] + elif isinstance(ty, AggregateType): + exprs = [] + for fname, ftype in ty.fields: + exprs.extend(ptr_exprs(f"{name}.{fname}", ftype)) + return exprs + elif isinstance(ty, (BasicType, FunctionType)): + return [] + elif isinstance(ty, ArrayType): + # TODO + return [] + else: + print(ty.classify(), file=sys.stderr) + raise NotImplementedError + +main() diff --git a/python/examples/refcounting/runtime/refcounting.c b/python/examples/refcounting/runtime/refcounting.c new file mode 100644 index 0000000..ba8cacc --- /dev/null +++ b/python/examples/refcounting/runtime/refcounting.c @@ -0,0 +1,114 @@ +#include +#include +#include + +struct data { + void *start; + size_t len; + size_t refcount; +}; + +struct node { + struct data data; + + struct node *left; + struct node *right; +}; + +static struct node *ROOT = 0; +static int TOTAL = 0; + +static struct node *lookup_interval(struct node *root, void *ptr) { + if (!root) return 0; + + if (ptr < root->data.start) + return lookup_interval(root->left, ptr); + + if (ptr < (root->data.start + root->data.len)) + return root; + + // our last hope is something on the right + return lookup_interval(root->right, ptr); +} + +// exact lookup, ignoring range len +static struct node **lookup(void *ptr) { + struct node **node = &ROOT; + while (*node) { + if ((*node)->data.start == ptr) + return node; + if (ptr > (*node)->data.start) + node = &((*node)->right); + else + node = &((*node)->left); + } + return node; +} + +static struct node *insert(void *ptr, size_t len) { + struct node **loc = lookup(ptr); + assert(!(*loc)); + *loc = calloc(1, sizeof(struct node)); + (*loc)->data.start = ptr; + (*loc)->data.len = len; + return *loc; +} + +static void remove_root(struct node **tree) { + if (!(*tree)) { + return; + } else if (!((*tree)->right)) { + *tree = (*tree)->left; + } else if (!((*tree)->left)) { + *tree = (*tree)->right; + } else { + // swap *tree and (*tree)->right, then delete the root in tree->right + struct data root_data = (*tree)->data; + (*tree)->data = (*tree)->right->data; + (*tree)->right->data = root_data; + remove_root(&((*tree)->right)); + } +} + +static struct node *remove_node(void *ptr) { + remove_root(lookup(ptr)); +} + +void *refcount_calloc(unsigned long count, unsigned long size) { + void *data = calloc(count, size); + TOTAL += 1; + printf("Allocated: %p ; now tracking %d regions\n", data, TOTAL); + insert(data, count * size); + return data; +} + +void refcount_write(void *new, void *old) { + // printf("Refcount write new: %p old: %p\n", new, old); + if (new) { + struct node *new_node = lookup_interval(ROOT, new); + if (new_node) { + // printf("Incrementing refcount ...\n"); + new_node->data.refcount++; + } + } + if (old) { + struct node *old_node = lookup_interval(ROOT, old); + if (old_node) { + // printf("Decrementing refcount ...\n"); + old_node->data.refcount--; + if (!(old_node->data.refcount)) { + TOTAL -= 1; + printf("Freeing! Left: %d\n", TOTAL); + remove_node(old_node->data.start); + free(old); + } + } + } +} + +void refcount_returning(void *ptr) { + if (!ptr) return; + struct node *ptr_node = lookup_interval(ROOT, ptr); + if (!ptr_node) return; + ptr_node->data.refcount--; +} diff --git a/python/examples/refcounting/runtime/refcounting.h b/python/examples/refcounting/runtime/refcounting.h new file mode 100644 index 0000000..139f09a --- /dev/null +++ b/python/examples/refcounting/runtime/refcounting.h @@ -0,0 +1,8 @@ +#pragma once + +// wrapper for calloc +void *refcount_calloc(unsigned long count, unsigned long size); +// overwrite a pointer that pointed to 'old' to now point to 'new' +void refcount_write(void *new, void *old); +// decrement the refcount, but do not free if the refcount hits 0 +void refcount_returning(void *ptr); diff --git a/python/examples/refcounting/test.c b/python/examples/refcounting/test.c new file mode 100644 index 0000000..212bb8b --- /dev/null +++ b/python/examples/refcounting/test.c @@ -0,0 +1,34 @@ +#include +#include + +int *foo(void) { + int *ptr = 0; + for (int i = 0; i < 5; i++) { + ptr = calloc(1, sizeof(*ptr)); + } + ptr = calloc(1, sizeof(*ptr)); + ptr = calloc(1, sizeof(*ptr)); + *ptr = 5; + return ptr; +} + +struct bar { + int x; + int *y; +}; + +int *bar(void) { + struct bar bar; + bar.x = 5; + bar.y = calloc(1, sizeof(int)); + *bar.y = bar.x; + return bar.y; +} + +int main(void) { + int *x = foo(); + printf("Result of foo(): %d\n", *x); + x = bar(); + printf("Result of bar(): %d\n", *x); + return 0; +} -- cgit v1.2.3