aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--gc.cpp59
-rw-r--r--gclib.cpp22
-rw-r--r--llvm.cpp41
-rwxr-xr-xtest.sh2
-rw-r--r--tuplr.hpp35
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 <http://www.gnu.org/licenses/>.
*/
+#include <cassert>
#include <set>
#include <iostream>
#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<const ATuple*>(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<const AST*>(obj);
+ const ATuple* tup = dynamic_cast<const ATuple*>(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<AType*>(*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<AType*>());
+ (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<ATuple*>();
+ vector<string> 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<AType*>()),
- *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<const Type*> 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<ADefinition*>())
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<const Type*> argsT(1, Type::Int32Ty);
+ std::vector<const Type*> 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<const Object*> Roots;
typedef std::list<Object*> 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<AST*> {
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<const ATuple*>();
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;
};
generated by cgit v1.2.1 (git 2.18.0) at 2024-06-26 09:18:39 +0000