Index: src/Common/GC.cc =================================================================== --- src/Common/GC.cc (revision 824a2dcc9b7c965dd21a755754670cb17b8d43e0) +++ src/Common/GC.cc (revision 824a2dcc9b7c965dd21a755754670cb17b8d43e0) @@ -0,0 +1,163 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// GC.cc -- +// +// Author : Aaron B. Moss +// Created On : Thu Mar 15 14:47:00 2018 +// Last Modified By : Aaron B. Moss +// Last Modified On : Thu Mar 15 14:47:00 2018 +// Update Count : 1 +// + +#include "GC.h" + +#include "Common/PassVisitor.h" + +#include "SynTree/GcTracer.h" + +#include +#include + +GC& GC::get() { + static GC gc; + return gc; +} + +GC::GC() : gens(1), static_roots(), mark(false), g(0) { + gens[0].reserve(70000); +} + +GC::~GC() { + for ( unsigned i = 0; i <= g; ++i ) { + for ( GC_Object* o : gens[i] ) { + delete o; + } + } +} + +const GC& GC::operator<< (const GC_Object* obj) const { + if( obj ) + { + if( obj->mark != this->mark ) { + obj->mark = this->mark; + obj->trace( *this ); + } + } + return *this; +} + +// build with flag GC_TRAP to compile in a breakpoint on register and sweep of a dynamically +// chosen object. Process to use: +// break GC::register_object +// run +// set variable GC_TRAP_OBJ = +// disable +// continue +#ifdef GC_TRAP +#include + +/// Set to object to check in debugger +void* GC_TRAP_OBJ = nullptr; +#endif + +void GC::register_object(GC_Object* obj) { + #ifdef GC_TRAP + if ( obj == GC_TRAP_OBJ ) std::raise(SIGTRAP); + #endif + gens[g].push_back(obj); + obj->mark = !this->mark; // initialize as un-marked +} + +void GC::register_static_root(BaseSyntaxNode* root) { + static_roots.push_back(root); +} + +GC_Guard GC::new_generation() { + if ( ++g == gens.size() ) { gens.emplace_back(); } // ensure new generation available + mark = !mark; // switch mark so aged young objects will still be unmarked in old + return { *this, g }; +} + +void GC::trace_static_roots() { + PassVisitor tracer{ *this }; + for ( BaseSyntaxNode* root : static_roots ) { + root->accept( tracer ); + } +} + +void GC::collect_young() { + // get generations and decrement generation + assert(g > 0 && "Cannot collect_young without young generation"); + Generation& young = gens[g]; + Generation& old = gens[--g]; + + // ensure static roots traced + trace_static_roots(); + + // collect young gen + for ( GC_Object*& obj : young ) { + if ( obj->mark != mark ) { + #ifdef GC_TRAP + if ( obj == GC_TRAP_OBJ ) std::raise(SIGTRAP); + #endif + delete obj; + obj = nullptr; + } + } + + // move uncollected elements into old gen + auto end_live = std::remove( young.begin(), young.end(), nullptr ); + old.insert( old.end(), young.begin(), end_live ); + + // clear young gen and reset mark to return to old generation mark + young.clear(); + mark = !mark; +} + +void GC::collect() { + // ensure not called when young gen is active + assert(g == 0 && "Cannot do old collection when young generation is active"); + Generation& old = gens[0]; + + // ensure static roots traced + trace_static_roots(); + + // collect old gen + for ( GC_Object*& obj : old ) { + if ( obj->mark != mark ) { + #ifdef GC_TRAP + if ( obj == GC_TRAP_OBJ ) std::raise(SIGTRAP); + #endif + delete obj; + obj = nullptr; + } + } + + // clear collected elements + old.erase( std::remove( old.begin(), old.end(), nullptr ), old.end() ); + + // reset mark + mark = !mark; +} + +GC_Object::GC_Object() { + GC::get().register_object( this ); +} + +GC_Object::GC_Object( const GC_Object& ) { + GC::get().register_object( this ); +} + +GC_Object::GC_Object( GC_Object&& ) { + GC::get().register_object( this ); +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/GC.h =================================================================== --- src/Common/GC.h (revision 824a2dcc9b7c965dd21a755754670cb17b8d43e0) +++ src/Common/GC.h (revision 824a2dcc9b7c965dd21a755754670cb17b8d43e0) @@ -0,0 +1,156 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// GC.h -- +// +// Author : Aaron B. Moss +// Created On : Thu Mar 15 14:47:00 2018 +// Last Modified By : Aaron B. Moss +// Last Modified On : Thu Mar 15 14:47:00 2018 +// Update Count : 1 +// + +#pragma once + +#include +#include + +class GC_Object; +class BaseSyntaxNode; +class GC_Guard; + +/// Manually traced and called garbage collector +class GC { + friend class GcTracer; + friend class GC_Guard; + + /// Collects the youngest generation, placing survivors in previous generation. + /// Young generation objects cannot be kept alive by pointers from older generation. + /// Older generation is used for subsequent new objects. + void collect_young(); +public: + /// Gets singleton GC instance + static GC& get(); + + /// Traces a traceable object + const GC& operator<< (const GC_Object*) const; + + /// Adds a new object to garbage collection + void register_object(GC_Object*); + + /// Adds an object to the set of static roots + void register_static_root(BaseSyntaxNode*); + + /// Start new generation for subsequent new objects + GC_Guard new_generation(); + + /// Traces all static roots + void trace_static_roots(); + + /// Collects oldest generation; use oldest generation afterward. + /// Error if currently using younger generation + void collect(); + + /// Collects all contained objects + ~GC(); + +private: + GC(); + + using Generation = std::vector; + std::vector gens; ///< Set of generations; always at least one + + using StaticRoots = std::vector; + StaticRoots static_roots; ///< Set of static-lifetime roots + + bool mark; ///< The current collection's mark bit + unsigned g; ///< The current number generation in use +}; + +/// Cleanup object for young generation +class GC_Guard { + friend class GC; + + GC& gc; ///< GC associated with + unsigned g; ///< Generation constructed for + + GC_Guard( GC& gc, unsigned g ) : gc(gc), g(g) {} + +public: + ~GC_Guard() { + assert( gc.g == g && "collecting current generation" ); + gc.collect_young(); + } +}; + +/// Use young generation until next collection +inline GC_Guard new_generation() { return GC::get().new_generation(); } + +// /// no-op default trace +// template +// inline const GC& operator<< (const GC& gc, const T& x) { return gc; } + +inline void traceAll(const GC&) {} + +/// Marks all arguments as live in current generation +template +inline void traceAll(const GC& gc, T& x, Args&... xs) { + gc << x; + traceAll(gc, xs...); +} + +/// Traces roots without collecting +template +inline void trace(Args&... roots) { + GC& gc = GC::get(); + traceAll(gc, roots...); +} + +/// Traces roots and collects other elements; should not be any young generations live +template +inline void collect(Args&... roots) { + GC& gc = GC::get(); + traceAll(gc, roots...); + gc.collect(); +} + +/// Makes a new expression as a static root +template +inline T* new_static_root( Args&&... args ) { + T* root = new T( std::forward(args)... ); + GC::get().register_static_root( root ); + return root; +} + +/// Class that is managed by the GC +class GC_Object { + friend class GC; +protected: + mutable bool mark; + + // Override default constructors to ensure clones are registered and properly marked + GC_Object(); + + GC_Object(const GC_Object&); + + GC_Object(GC_Object&&); + + GC_Object& operator= (const GC_Object&) { /* do not assign mark */ return *this; } + + GC_Object& operator= (GC_Object&&) { /* do not assign mark */ return *this; } + + // Ensure subclasses can be deleted by garbage collector + virtual ~GC_Object() {} + + /// override to trace any child objects + virtual void trace(const GC&) const {} +}; + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/PassVisitor.h =================================================================== --- src/Common/PassVisitor.h (revision 4358c1e0834c47bfa838495f2b075911cb513d38) +++ src/Common/PassVisitor.h (revision 824a2dcc9b7c965dd21a755754670cb17b8d43e0) @@ -151,7 +151,9 @@ virtual void visit( Subrange * subrange ) override final; - virtual void visit( Constant * constant ) override final; + virtual void visit( Constant * constant ) final; virtual void visit( Attribute * attribute ) override final; + + virtual void visit( TypeSubstitution * sub ) final; virtual DeclarationWithType * mutate( ObjectDecl * objectDecl ) override final; @@ -249,5 +251,5 @@ virtual Subrange * mutate( Subrange * subrange ) override final; - virtual Constant * mutate( Constant * constant ) override final; + virtual Constant * mutate( Constant * constant ) final; virtual Attribute * mutate( Attribute * attribute ) override final; Index: src/Common/PassVisitor.impl.h =================================================================== --- src/Common/PassVisitor.impl.h (revision 4358c1e0834c47bfa838495f2b075911cb513d38) +++ src/Common/PassVisitor.impl.h (revision 824a2dcc9b7c965dd21a755754670cb17b8d43e0) @@ -38,5 +38,5 @@ MUTATE_END( type, node ); \ - +#include "Common/GC.h" template @@ -397,10 +397,10 @@ auto guard = makeFuncGuard( [this]() { indexerScopeEnter(); }, [this]() { indexerScopeLeave(); } ); // implicit add __func__ identifier as specified in the C manual 6.4.2.2 - static ObjectDecl func( + static ObjectDecl* func = new_static_root( "__func__", noStorageClasses, LinkageSpec::C, nullptr, new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers( Type::Const ), BasicType::Char ), nullptr, true, false ), nullptr ); - indexerAddId( &func ); + indexerAddId( func ); maybeAccept_impl( node->type, *this ); maybeAccept_impl( node->statements, *this ); @@ -427,10 +427,10 @@ auto guard = makeFuncGuard( [this]() { indexerScopeEnter(); }, [this]() { indexerScopeLeave(); } ); // implicit add __func__ identifier as specified in the C manual 6.4.2.2 - static ObjectDecl func( + static ObjectDecl* func = new_static_root( "__func__", noStorageClasses, LinkageSpec::C, nullptr, new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers( Type::Const ), BasicType::Char ), nullptr, true, false ), nullptr ); - indexerAddId( &func ); + indexerAddId( func ); maybeMutate_impl( node->type, *this ); maybeMutate_impl( node->statements, *this ); @@ -1209,4 +1209,5 @@ indexerScopedAccept( node->result, *this ); + // xxx - not quite sure why this doesn't visit( node->function ); for ( auto expr : node->args ) { visitExpression( expr ); @@ -2615,4 +2616,18 @@ // TypeSubstitution template< typename pass_type > +void PassVisitor< pass_type >::visit( TypeSubstitution * node ) { + VISIT_START( node ); + + for ( auto & p : node->typeEnv ) { + indexerScopedAccept( p.second, *this ); + } + for ( auto & p : node->varEnv ) { + indexerScopedAccept( p.second, *this ); + } + + VISIT_END( node ); +} + +template< typename pass_type > TypeSubstitution * PassVisitor< pass_type >::mutate( TypeSubstitution * node ) { MUTATE_START( node ); Index: src/Common/module.mk =================================================================== --- src/Common/module.mk (revision 4358c1e0834c47bfa838495f2b075911cb513d38) +++ src/Common/module.mk (revision 824a2dcc9b7c965dd21a755754670cb17b8d43e0) @@ -6,5 +6,5 @@ ## file "LICENCE" distributed with Cforall. ## -## module.mk -- +## module.mk -- ## ## Author : Richard C. Bilson @@ -18,4 +18,5 @@ Common/UniqueName.cc \ Common/DebugMalloc.cc \ + Common/GC.cc \ Common/Assert.cc \ Common/Heap.cc Index: src/Common/utility.h =================================================================== --- src/Common/utility.h (revision 4358c1e0834c47bfa838495f2b075911cb513d38) +++ src/Common/utility.h (revision 824a2dcc9b7c965dd21a755754670cb17b8d43e0) @@ -190,12 +190,9 @@ template class Container, typename... Args > -void filter( Container< E *, Args... > & container, UnaryPredicate pred, bool doDelete ) { +void filter( Container< E *, Args... > & container, UnaryPredicate pred ) { auto i = begin( container ); while ( i != end( container ) ) { auto it = next( i ); if ( pred( *i ) ) { - if ( doDelete ) { - delete *i; - } // if container.erase( i ); } // if