Changeset e8032b0

Timestamp:

Mar 8, 2016, 1:51:25 PM (8 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, ctor, deferred_resn, demangler, enum, forall-pointer-decay, gc_noraii, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, string, with_gc

Children:

52c2a72

Parents:

4e284ea6

Message:

Switch Indexer over to copy-on-write semantics for dramatic speedup

Location:

src

Files:

• CodeGen/CodeGenerator.cc (modified) (1 diff)
• CodeGen/CodeGenerator.h (modified) (1 diff)
• CodeGen/GenType.cc (modified) (1 diff)
• SymTab/Indexer.cc (modified) (15 diffs)
• SymTab/Indexer.h (modified) (4 diffs)

src/CodeGen/CodeGenerator.cc

@@ -21 +21 @@
 #include "Parser/ParseNode.h"
 
-#include "SynTree/Type.h"
+#include "SynTree/Declaration.h"
 #include "SynTree/Expression.h"
 #include "SynTree/Initializer.h"
 #include "SynTree/Statement.h"
+#include "SynTree/Type.h"
 
 #include "Common/utility.h"

src/CodeGen/CodeGenerator.h

@@ -19 +19 @@
 #include <list>
 
+#include "SynTree/Declaration.h"
 #include "SynTree/SynTree.h"
 #include "SynTree/Visitor.h"
+
 #include "SymTab/Indexer.h"
 

src/CodeGen/GenType.cc

@@ -19 +19 @@
 #include "GenType.h"
 #include "CodeGenerator.h"
+
+#include "SynTree/Declaration.h"
+#include "SynTree/Expression.h"
+#include "SynTree/Type.h"
 #include "SynTree/Visitor.h"
-#include "SynTree/Type.h"
-#include "SynTree/Expression.h"
 
 namespace CodeGen {

src/SymTab/Indexer.cc

@@ -14 +14 @@
 //
 
+#include "Indexer.h"
+
+#include "IdTable.h"
+#include "AggregateTable.h"
+#include "TypeTable.h"
+
 #include "SynTree/Declaration.h"
 #include "SynTree/Type.h"
@@ -19 +25 @@
 #include "SynTree/Initializer.h"
 #include "SynTree/Statement.h"
-#include "Indexer.h"
+
 #include <typeinfo>
+#include <utility>
 #include "Common/utility.h"
 
@@ -33 +40 @@
         }
 
-        Indexer::Indexer( bool useDebug ) : doDebug( useDebug ) {}
-
-        Indexer::~Indexer() {}
+        struct Indexer::Impl {
+                Impl() : refCount(1), size(0), base(),
+                                idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {}
+                Impl( const Indexer &_base ) : refCount(1), size(0), base( _base ),
+                                idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {}
+                unsigned long refCount;   ///< Number of references to these tables
+                unsigned long size;       ///< Number of elements stored in this table
+                const Indexer base;       ///< Base indexer this extends
+                
+                IdTable idTable;          ///< Identifier namespace
+                TypeTable typeTable;      ///< Type namespace
+                StructTable structTable;  ///< Struct namespace
+                EnumTable enumTable;      ///< Enum namespace
+                UnionTable unionTable;    ///< Union namespace
+                TraitTable traitTable;    ///< Trait namespace
+        };
+
+        Indexer::Impl *Indexer::newRef( Indexer::Impl *toClone ) {
+                if ( ! toClone ) return 0;
+
+                // shorten the search chain by skipping empty links
+                Indexer::Impl *ret = toClone->size == 0 ? toClone->base.tables : toClone;
+                if ( ret ) { ++ret->refCount; }
+
+                return ret;
+        }
+
+        void Indexer::deleteRef( Indexer::Impl *toFree ) {
+                if ( ! toFree ) return;
+
+                if ( --toFree->refCount == 0 ) delete toFree;
+        }
+
+        void Indexer::makeWritable() {
+                if ( ! tables ) {
+                        tables = new Indexer::Impl;
+                } else if ( tables->refCount > 1 ) {
+                        // tables->base inherits the ref that used to belong to this indexer
+                        // this is basically equivalent to std::move( *this ) as the argument
+                        tables = new Indexer::Impl( Indexer( tables, doDebug ) );
+                }
+        }
+
+        Indexer::Indexer( bool _doDebug ) : tables(0), doDebug( _doDebug ) {}
+
+        Indexer::Indexer( const Indexer &that ) : tables( newRef( that.tables ) ), doDebug( that.doDebug ) {}
+
+        Indexer::Indexer( Indexer &&that ) : tables( that.tables ), doDebug( that.doDebug ) {
+                that.tables = 0;
+        }
+
+        Indexer::~Indexer() {
+                deleteRef( tables );
+        }
+
+        Indexer& Indexer::operator= ( const Indexer &that ) {
+                deleteRef( tables );
+
+                tables = newRef( that.tables );
+                doDebug = that.doDebug;
+
+                return *this;
+        }
+
+        Indexer& Indexer::operator= ( Indexer &&that ) {
+                deleteRef( tables );
+
+                tables = that.tables;
+                doDebug = that.doDebug;
+
+                that.tables = 0;
+
+                return *this;
+        }
 
         void Indexer::visit( ObjectDecl *objectDecl ) {
@@ -45 +123 @@
                 if ( objectDecl->get_name() != "" ) {
                         debugPrint( "Adding object " << objectDecl->get_name() << std::endl );
-                        idTable.addDecl( objectDecl );
+                        addId( objectDecl );
                 } // if
         }
@@ -52 +130 @@
                 if ( functionDecl->get_name() == "" ) return;
                 debugPrint( "Adding function " << functionDecl->get_name() << std::endl );
-                idTable.addDecl( functionDecl );
+                addId( functionDecl );
                 enterScope();
                 maybeAccept( functionDecl->get_functionType(), *this );
@@ -90 +168 @@
                 leaveScope();
                 debugPrint( "Adding type " << typeDecl->get_name() << std::endl );
-                typeTable.add( typeDecl );
+                addType( typeDecl );
                 acceptAll( typeDecl->get_assertions(), *this );
         }
@@ -100 +178 @@
                 leaveScope();
                 debugPrint( "Adding typedef " << typeDecl->get_name() << std::endl );
-                typeTable.add( typeDecl );
+                addType( typeDecl );
         }
 
@@ -108 +186 @@
                 cloneAll( aggregateDecl->get_parameters(), fwdDecl.get_parameters() );
                 debugPrint( "Adding fwd decl for struct " << fwdDecl.get_name() << std::endl );
-                structTable.add( &fwdDecl );
+                addStruct( &fwdDecl );
   
                 enterScope();
@@ -117 +195 @@
                 debugPrint( "Adding struct " << aggregateDecl->get_name() << std::endl );
                 // this addition replaces the forward declaration
-                structTable.add( aggregateDecl );
+                addStruct( aggregateDecl );
         }
 
@@ -125 +203 @@
                 cloneAll( aggregateDecl->get_parameters(), fwdDecl.get_parameters() );
                 debugPrint( "Adding fwd decl for union " << fwdDecl.get_name() << std::endl );
-                unionTable.add( &fwdDecl );
+                addUnion( &fwdDecl );
   
                 enterScope();
@@ -133 +211 @@
   
                 debugPrint( "Adding union " << aggregateDecl->get_name() << std::endl );
-                unionTable.add( aggregateDecl );
+                addUnion( aggregateDecl );
         }
 
         void Indexer::visit( EnumDecl *aggregateDecl ) {
                 debugPrint( "Adding enum " << aggregateDecl->get_name() << std::endl );
-                enumTable.add( aggregateDecl );
+                addEnum( aggregateDecl );
                 // unlike structs, contexts, and unions, enums inject their members into the global scope
                 acceptAll( aggregateDecl->get_members(), *this );
@@ -150 +228 @@
   
                 debugPrint( "Adding context " << aggregateDecl->get_name() << std::endl );
-                contextTable.add( aggregateDecl );
+                addTrait( aggregateDecl );
         }
 
@@ -299 +377 @@
 
         void Indexer::visit( StructInstType *structInst ) {
-                if ( ! structTable.lookup( structInst->get_name() ) ) {
+                if ( ! lookupStruct( structInst->get_name() ) ) {
                         debugPrint( "Adding struct " << structInst->get_name() << " from implicit forward declaration" << std::endl );
-                        structTable.add( structInst->get_name() );
+                        addStruct( structInst->get_name() );
                 }
                 enterScope();
@@ -309 +387 @@
 
         void Indexer::visit( UnionInstType *unionInst ) {
-                if ( ! unionTable.lookup( unionInst->get_name() ) ) {
+                if ( ! lookupUnion( unionInst->get_name() ) ) {
                         debugPrint( "Adding union " << unionInst->get_name() << " from implicit forward declaration" << std::endl );
-                        unionTable.add( unionInst->get_name() );
+                        addUnion( unionInst->get_name() );
                 }
                 enterScope();
@@ -327 +405 @@
 
         void Indexer::lookupId( const std::string &id, std::list< DeclarationWithType* > &list ) const {
-                idTable.lookupId( id, list );
+                if ( ! tables ) return;
+                
+                tables->idTable.lookupId( id, list );
+                tables->base.lookupId( id, list );
         }
 
         DeclarationWithType* Indexer::lookupId( const std::string &id) const {
-                return idTable.lookupId(id);
+                if ( ! tables ) return 0;
+                
+                DeclarationWithType *ret = tables->idTable.lookupId(id);
+                return ret ? ret : tables->base.lookupId(id);
         }
 
         NamedTypeDecl *Indexer::lookupType( const std::string &id ) const {
-                return typeTable.lookup( id );
+                if ( ! tables ) return 0;
+
+                NamedTypeDecl *ret = tables->typeTable.lookup( id );
+                return ret ? ret : tables->base.lookupType( id );
         }
 
         StructDecl *Indexer::lookupStruct( const std::string &id ) const {
-                return structTable.lookup( id );
+                if ( ! tables ) return 0;
+
+                StructDecl *ret = tables->structTable.lookup( id );
+                return ret ? ret : tables->base.lookupStruct( id );
         }
 
         EnumDecl *Indexer::lookupEnum( const std::string &id ) const {
-                return enumTable.lookup( id );
+                if ( ! tables ) return 0;
+
+                EnumDecl *ret = tables->enumTable.lookup( id );
+                return ret ? ret : tables->base.lookupEnum( id );
         }
 
         UnionDecl *Indexer::lookupUnion( const std::string &id ) const {
-                return unionTable.lookup( id );
-        }
-
-        TraitDecl  * Indexer::lookupTrait( const std::string &id ) const {
-                return contextTable.lookup( id );
+                if ( ! tables ) return 0;
+
+                UnionDecl *ret = tables->unionTable.lookup( id );
+                return ret ? ret : tables->base.lookupUnion( id );
+        }
+
+        TraitDecl *Indexer::lookupTrait( const std::string &id ) const {
+                if ( ! tables ) return 0;
+
+                TraitDecl *ret = tables->traitTable.lookup( id );
+                return ret ? ret : tables->base.lookupTrait( id );
+        }
+
+        void Indexer::addId( DeclarationWithType *decl ) {
+                makeWritable();
+                tables->idTable.addDecl( decl );
+                ++tables->size;
+        }
+        
+        void Indexer::addType( NamedTypeDecl *decl ) {
+                makeWritable();
+                tables->typeTable.add( decl );
+                ++tables->size;
+        }
+
+        void Indexer::addStruct( const std::string &id ) {
+                makeWritable();
+                tables->structTable.add( id );
+                ++tables->size;
+        }
+        
+        void Indexer::addStruct( StructDecl *decl ) {
+                makeWritable();
+                tables->structTable.add( decl );
+                ++tables->size;
+        }
+        
+        void Indexer::addEnum( EnumDecl *decl ) {
+                makeWritable();
+                tables->enumTable.add( decl );
+                ++tables->size;
+        }
+
+        void Indexer::addUnion( const std::string &id ) {
+                makeWritable();
+                tables->unionTable.add( id );
+                ++tables->size;
+        }
+        
+        void Indexer::addUnion( UnionDecl *decl ) {
+                makeWritable();
+                tables->unionTable.add( decl );
+                ++tables->size;
+        }
+        
+        void Indexer::addTrait( TraitDecl *decl ) {
+                makeWritable();
+                tables->traitTable.add( decl );
+                ++tables->size;
         }
 
         void Indexer::enterScope() {
+                makeWritable();
+                
                 if ( doDebug ) {
                         std::cout << "--- Entering scope" << std::endl;
                 }
-                idTable.enterScope();
-                typeTable.enterScope();
-                structTable.enterScope();
-                enumTable.enterScope();
-                unionTable.enterScope();
-                contextTable.enterScope();
+
+                tables->idTable.enterScope();
+                tables->typeTable.enterScope();
+                tables->structTable.enterScope();
+                tables->enumTable.enterScope();
+                tables->unionTable.enterScope();
+                tables->traitTable.enterScope();
         }
 
         void Indexer::leaveScope() {
                 using std::cout;
-                using std::endl;
-  
+                
+                makeWritable();
+                
                 if ( doDebug ) {
-                        cout << "--- Leaving scope containing" << endl;
-                        idTable.dump( cout );
-                        typeTable.dump( cout );
-                        structTable.dump( cout );
-                        enumTable.dump( cout );
-                        unionTable.dump( cout );
-                        contextTable.dump( cout );
-                }
-                idTable.leaveScope();
-                typeTable.leaveScope();
-                structTable.leaveScope();
-                enumTable.leaveScope();
-                unionTable.leaveScope();
-                contextTable.leaveScope();
+                        cout << "--- Leaving scope containing" << std::endl;
+                        tables->idTable.dump( cout );
+                        tables->typeTable.dump( cout );
+                        tables->structTable.dump( cout );
+                        tables->enumTable.dump( cout );
+                        tables->unionTable.dump( cout );
+                        tables->traitTable.dump( cout );
+                }
+                tables->idTable.leaveScope();
+                tables->typeTable.leaveScope();
+                tables->structTable.leaveScope();
+                tables->enumTable.leaveScope();
+                tables->unionTable.leaveScope();
+                tables->traitTable.leaveScope();
         }
 
         void Indexer::print( std::ostream &os, int indent ) const {
             using std::cerr;
-            using std::endl;
-
-            cerr << "===idTable===" << endl;
-            idTable.dump( os );
-            cerr << "===typeTable===" << endl;
-            typeTable.dump( os );
-            cerr << "===structTable===" << endl;
-            structTable.dump( os );
-            cerr << "===enumTable===" << endl;
-            enumTable.dump( os );
-            cerr << "===unionTable===" << endl;
-            unionTable.dump( os );
-            cerr << "===contextTable===" << endl;
-            contextTable.dump( os );
-#if 0
-                idTable.dump( os );
-                typeTable.dump( os );
-                structTable.dump( os );
-                enumTable.dump( os );
-                unionTable.dump( os );
-                contextTable.dump( os );
-#endif
+
+            cerr << "===idTable===" << std::endl;
+            if ( tables ) tables->idTable.dump( os );
+            cerr << "===typeTable===" << std::endl;
+            if ( tables ) tables->typeTable.dump( os );
+            cerr << "===structTable===" << std::endl;
+            if ( tables ) tables->structTable.dump( os );
+            cerr << "===enumTable===" << std::endl;
+            if ( tables ) tables->enumTable.dump( os );
+            cerr << "===unionTable===" << std::endl;
+            if ( tables ) tables->unionTable.dump( os );
+            cerr << "===contextTable===" << std::endl;
+            if ( tables ) tables->traitTable.dump( os );
         }
 } // namespace SymTab

src/SymTab/Indexer.h

@@ -21 +21 @@
 
 #include "SynTree/Visitor.h"
-#include "IdTable.h"
-#include "AggregateTable.h"
-#include "TypeTable.h"
 
 namespace SymTab {
@@ -29 +26 @@
           public:
                 Indexer( bool useDebug = false );
+
+                Indexer( const Indexer &that );
+                Indexer( Indexer &&that );
                 virtual ~Indexer();
+                Indexer& operator= ( const Indexer &that );
+                Indexer& operator= ( Indexer &&that );
 
                 //using Visitor::visit;
@@ -78 +80 @@
                 void leaveScope();
 
-                void lookupId( const std::string &id, std::list< DeclarationWithType* >& ) const;
-                DeclarationWithType* lookupId( const std::string &id) const;
+                void lookupId( const std::string &id, std::list< DeclarationWithType* > &out ) const;
+                DeclarationWithType* lookupId( const std::string &id ) const;
                 NamedTypeDecl *lookupType( const std::string &id ) const;
                 StructDecl *lookupStruct( const std::string &id ) const;
@@ -88 +90 @@
                 void print( std::ostream &os, int indent = 0 ) const;
           private:
-                IdTable idTable;
-                TypeTable typeTable;
-                StructTable structTable;
-                EnumTable enumTable;
-                UnionTable unionTable;
-                TraitTable contextTable;
-  
-                bool doDebug;                                   // display debugging trace
+                void addId( DeclarationWithType *decl );
+                void addType( NamedTypeDecl *decl );
+                void addStruct( const std::string &id );
+                void addStruct( StructDecl *decl );
+                void addEnum( EnumDecl *decl );
+                void addUnion( const std::string &id );
+                void addUnion( UnionDecl *decl );
+                void addTrait( TraitDecl *decl );
+                
+                struct Impl;
+                Impl *tables;  ///< Copy-on-write instance of table data structure
+                bool doDebug;  ///< Display debugging trace?
+
+                Indexer( Impl *_tables, bool _doDebug ) : tables( _tables ), doDebug( _doDebug ) {}
+
+                /// Takes a new ref to a table (returns null if null)
+                static Impl *newRef( Impl *toClone );
+                /// Clears a ref to a table (does nothing if null)
+                static void deleteRef( Impl *toFree );
+
+                /// Ensures that tables variable is writable (i.e. allocated and uniquely owned by this Indexer)
+                void makeWritable();
         };
 } // namespace SymTab