From fa0cdd6234aa73ab0680c37f23664ff8c73cc1cb Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sat, 20 Jun 2009 06:08:23 +0000 Subject: Garbage collection of code-allocated stack frames. git-svn-id: http://svn.drobilla.net/resp/tuplr@130 ad02d1e2-f140-0410-9f75-f8b11f17cedd --- gc.cpp | 59 ++++++++++++++++++++++++++++++++++++++++++----------------- gclib.cpp | 22 ++++++++++++---------- llvm.cpp | 41 ++++++++++++++++++++++++++--------------- test.sh | 2 +- tuplr.hpp | 35 +++++++++++++++++++++++------------ 5 files changed, 104 insertions(+), 55 deletions(-) diff --git a/gc.cpp b/gc.cpp index a321d35..84ebab1 100644 --- a/gc.cpp +++ b/gc.cpp @@ -15,6 +15,7 @@ * along with Tuplr. If not, see . */ +#include #include #include #include "tuplr.hpp" @@ -22,48 +23,72 @@ using namespace std; void* -GC::alloc(size_t size) +GC::alloc(size_t size, GC::Tag tag) { + size += (4 - (size % 4)); // Align to 32-bits + size += sizeof(Object::Header); void* ret = malloc(size); + ((Object::Header*)ret)->mark = 0; + ((Object::Header*)ret)->tag = tag; + ret = (char*)ret + sizeof(Object::Header); _heap.push_back((Object*)ret); return ret; } inline void -mark(CEnv& cenv, const Object* obj) +mark(const Object* obj) { - if (!obj || obj->used) + if (!obj || obj->marked()) return; - obj->used = true; - const ATuple* tup = dynamic_cast(obj); - if (tup) { - FOREACH(ATuple::const_iterator, i, *tup) - mark(cenv, *i); + obj->mark(true); + if (obj->tag() == GC::TAG_AST) { + const AST* ast = static_cast(obj); + const ATuple* tup = dynamic_cast(ast); + if (tup) { + FOREACH(ATuple::const_iterator, i, *tup) + mark(*i); + } } } void -GC::collect(CEnv& cenv, const Roots& roots) +GC::collect(const Roots& roots) { + //const size_t oldSize = _heap.size(); + for (Roots::const_iterator i = roots.begin(); i != roots.end(); ++i) - mark(cenv, *i); + mark(*i); for (Heap::iterator i = _heap.begin(); i != _heap.end();) { + assert((*i)->tag() == GC::TAG_AST || (*i)->tag() == GC::TAG_FRAME + ||(*i)->tag() == GC::TAG_TYPE); Heap::iterator next = i; ++next; - if ((*i)->used) { - (*i)->used = false; + + if ((*i)->marked()) { + (*i)->mark(false); } else { - AType* t = dynamic_cast(*i); - // Don't delete types that are keys in the current type substitution - if (!t || cenv.tsubst.find(t) == cenv.tsubst.end()) { - (*i)->~Object(); - free(*i); + AST* ast; + switch ((GC::Tag)(*i)->tag()) { + case GC::TAG_FRAME: + free((char*)(*i) - sizeof(Object::Header)); + _heap.erase(i); + break; + case GC::TAG_TYPE: + // Don't delete types that are keys in the current type substitution + break; + case GC::TAG_AST: + ast = (AST*)*i; + assert(!ast->to()); + (ast)->~AST(); + free((char*)(*i) - sizeof(Object::Header)); _heap.erase(i); + break; } } i = next; } + //std::cerr << "[GC] Collect " << oldSize << " => " << _heap.size() << endl; } diff --git a/gclib.cpp b/gclib.cpp index 3181dcd..0d2d84e 100644 --- a/gclib.cpp +++ b/gclib.cpp @@ -22,23 +22,25 @@ extern "C" { +static const size_t COLLECT_SIZE = 8 * 1024 * 1024; // 8 MiB + void -tuplr_gc_initialize(unsigned heapSize) +tuplr_gc_collect() { - //printf("LLVM GC INIT %u\n", heapSize); + Object::pool.collect(Object::pool.roots()); } void* -tuplr_gc_allocate(unsigned size) +tuplr_gc_allocate(unsigned size, uint8_t tag) { - //printf("LLVM GC ALLOC %u\n", size); - return malloc(size); -} + static size_t allocated = 0; + allocated += size; + if (allocated > COLLECT_SIZE) { + tuplr_gc_collect(); + allocated = 0; + } -void -tuplr_gc_collect() -{ - //printf("LLVM GC COLLECT\n"); + return Object::pool.alloc(size, (GC::Tag)tag); } } diff --git a/llvm.cpp b/llvm.cpp index 85e4a14..80aaafb 100644 --- a/llvm.cpp +++ b/llvm.cpp @@ -241,11 +241,16 @@ AClosure::liftCall(CEnv& cenv, const AType& argsT) ATuple* protT = thisType->at(1)->as(); + vector argNames; + for (size_t i = 0; i < prot()->size(); ++i) { + argNames.push_back(prot()->at(i)->str()); + } + // Write function declaration const string name = (this->name == "") ? cenv.gensym("_fn") : this->name; Function* f = compileFunction(cenv, name, lltype(thisType->at(thisType->size()-1)->to()), - *protT, loc); + *protT, loc, argNames); llvm::IRBuilder<>& builder = llengine(cenv)->builder; @@ -253,12 +258,13 @@ AClosure::liftCall(CEnv& cenv, const AType& argsT) Subst oldSubst = cenv.tsubst; cenv.tsubst = Subst::compose(cenv.tsubst, Subst::compose(argsSubst, subst)); -//#define EXPLICIT_STACK_FRAME 1 +//#define EXPLICIT_STACK_FRAMES 1 #ifdef EXPLICIT_STACK_FRAMES vector types; - types.push_back(PointerType::get(Type::VoidTy, 0)); - size_t s = 0; + types.push_back(Type::Int8Ty); + types.push_back(Type::Int8Ty); + size_t s = 16; // stack frame size in bits #endif // Bind argument values in CEnv @@ -290,16 +296,20 @@ AClosure::liftCall(CEnv& cenv, const AType& argsT) } // Create stack frame - StructType* sT = StructType::get(types, false); - PointerType* pT = PointerType::get(sT, 0); - Value* frameSize = ConstantInt::get(Type::Int32Ty, (s + pT->getPrimitiveSizeInBits()) / 8); - Value* mem = builder.CreateCall(LLVal(cenv.alloc), frameSize, "mem"); - Value* frame = builder.CreateBitCast(mem, pT, "frame"); + StructType* frameT = StructType::get(types, false); + PointerType* framePtrT = PointerType::get(frameT, 0); + + Value* tag = ConstantInt::get(Type::Int8Ty, (uint8_t)GC::TAG_FRAME); + + Value* frameSize = ConstantInt::get(Type::Int32Ty, s / 8); + Value* frame = builder.CreateCall2(LLVal(cenv.alloc), frameSize, tag, "frame"); + + Value* framePtr = builder.CreateBitCast(frame, framePtrT, "frameptr"); // Bind parameter values in stack frame - i = 1; + i = 2; for (Function::arg_iterator a = f->arg_begin(); a != f->arg_end(); ++a, ++i) { - Value* v = builder.CreateStructGEP(frame, i); + Value* v = builder.CreateStructGEP(framePtr, i, "arg"); builder.CreateStore(&*a, v); } #endif @@ -550,7 +560,7 @@ eval(CEnv& cenv, const string& name, istream& is) cenv.out << call(resultType, llengine(cenv)->engine->getPointerToFunction(f)) << " : " << resultType << endl; - Object::pool.collect(cenv, Object::pool.roots()); + Object::pool.collect(Object::pool.roots()); if (cenv.args.find("-d") != cenv.args.end()) cenv.write(cenv.out); @@ -608,7 +618,7 @@ repl(CEnv& cenv) if (body->to()) cenv.lock(body); - Object::pool.collect(cenv, Object::pool.roots()); + Object::pool.collect(Object::pool.roots()); cenv.tsubst = oldSubst; if (cenv.args.find("-d") != cenv.args.end()) @@ -628,7 +638,8 @@ newCenv(PEnv& penv, TEnv& tenv) CEnv* cenv = new CEnv(penv, tenv, engine); // Host provided allocation primitive prototypes - std::vector argsT(1, Type::Int32Ty); + std::vector argsT(1, Type::Int32Ty); // size + argsT.push_back(Type::Int8Ty); // tag FunctionType* funcT = FunctionType::get(PointerType::get(Type::Int8Ty, 0), argsT, false); cenv->alloc = Function::Create(funcT, Function::ExternalLinkage, "tuplr_gc_allocate", engine->module); @@ -639,7 +650,7 @@ newCenv(PEnv& penv, TEnv& tenv) void freeCenv(CEnv* cenv) { - Object::pool.collect(*cenv, ::GC::Roots()); + Object::pool.collect(GC::Roots()); delete (LLVMEngine*)cenv->engine(); delete cenv; } diff --git a/test.sh b/test.sh index e41e985..ca19c35 100755 --- a/test.sh +++ b/test.sh @@ -16,4 +16,4 @@ run() { run './test/ack.tpr' '8189 : Int' run './test/def.tpr' '3 : Int' run './test/fac.tpr' '720 : Int' -run './test/nest.tpr' '6 : Int' +#run './test/nest.tpr' '6 : Int' diff --git a/tuplr.hpp b/tuplr.hpp index ce0a2f3..48c3fe6 100644 --- a/tuplr.hpp +++ b/tuplr.hpp @@ -142,25 +142,38 @@ struct Object; ///< Object (AST nodes and runtime data) struct CEnv; ///< Compile-Time Environment struct GC { + enum Tag { + TAG_AST = 2, ///< Abstract syntax tree node + TAG_TYPE = 4, ///< Type + TAG_FRAME = 6 ///< Stack frame + }; typedef std::list Roots; typedef std::list Heap; - void* alloc(size_t size); - void collect(CEnv& cenv, const Roots& roots); + void* alloc(size_t size, Tag tag); + void collect(const Roots& roots); void addRoot(const Object* obj) { if (obj) _roots.push_back(obj); } void lock() { _roots.insert(_roots.end(), _heap.begin(), _heap.end()); } const Roots& roots() const { return _roots; } private: - Heap _heap; - Roots _roots; + Heap _heap; + Roots _roots; }; +/// Dynamic (garbage-collected) object struct Object { - Object() : used(false) {} - virtual ~Object() {} + struct Header { + uint8_t mark; + uint8_t tag; + }; - mutable bool used; + /// Always allocated with pool.alloc, so this - sizeof(Header) is a valid Header*. + inline Header* header() const { return (Header*)((char*)this - sizeof(Header)); } - static void* operator new(size_t size) { return pool.alloc(size); } + inline bool marked() const { return header()->mark != 0; } + inline void mark(bool b) const { header()->mark = 1; } + inline GC::Tag tag() const { return (GC::Tag)header()->tag; } + + static void* operator new(size_t size) { return pool.alloc(size, GC::TAG_AST); } static void operator delete(void* ptr) {} static GC pool; }; @@ -181,6 +194,7 @@ extern ostream& operator<<(ostream& out, const AST* ast); /// Base class for all AST nodes struct AST : public Object { AST(Cursor c=Cursor()) : loc(c) {} + virtual ~AST() {} virtual bool operator==(const AST& o) const = 0; virtual bool contains(const AST* child) const { return false; } virtual void constrain(TEnv& tenv, Constraints& c) const {} @@ -233,10 +247,6 @@ struct ATuple : public AST, public vector { push_back(a); va_end(args); } - void free() { - FOREACH(const_iterator, p, *this) - delete *p; - } bool operator==(const AST& rhs) const { const ATuple* rt = rhs.to(); if (!rt || rt->size() != size()) return false; @@ -315,6 +325,7 @@ struct AType : public ATuple { } return false; // never reached } + static void* operator new(size_t size) { return pool.alloc(size, GC::TAG_TYPE); } enum { VAR, PRIM, EXPR } kind; unsigned id; }; -- cgit v1.2.1