Changeset e8032b0


Ignore:
Timestamp:
Mar 8, 2016, 1:51:25 PM (6 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, ctor, deferred_resn, demangler, gc_noraii, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, string, with_gc
Children:
52c2a72
Parents:
4e284ea6
Message:

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

Location:
src
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/CodeGen/CodeGenerator.cc

    r4e284ea6 re8032b0  
    2121#include "Parser/ParseNode.h"
    2222
    23 #include "SynTree/Type.h"
     23#include "SynTree/Declaration.h"
    2424#include "SynTree/Expression.h"
    2525#include "SynTree/Initializer.h"
    2626#include "SynTree/Statement.h"
     27#include "SynTree/Type.h"
    2728
    2829#include "Common/utility.h"
  • src/CodeGen/CodeGenerator.h

    r4e284ea6 re8032b0  
    1919#include <list>
    2020
     21#include "SynTree/Declaration.h"
    2122#include "SynTree/SynTree.h"
    2223#include "SynTree/Visitor.h"
     24
    2325#include "SymTab/Indexer.h"
    2426
  • src/CodeGen/GenType.cc

    r4e284ea6 re8032b0  
    1919#include "GenType.h"
    2020#include "CodeGenerator.h"
     21
     22#include "SynTree/Declaration.h"
     23#include "SynTree/Expression.h"
     24#include "SynTree/Type.h"
    2125#include "SynTree/Visitor.h"
    22 #include "SynTree/Type.h"
    23 #include "SynTree/Expression.h"
    2426
    2527namespace CodeGen {
  • src/SymTab/Indexer.cc

    r4e284ea6 re8032b0  
    1414//
    1515
     16#include "Indexer.h"
     17
     18#include "IdTable.h"
     19#include "AggregateTable.h"
     20#include "TypeTable.h"
     21
    1622#include "SynTree/Declaration.h"
    1723#include "SynTree/Type.h"
     
    1925#include "SynTree/Initializer.h"
    2026#include "SynTree/Statement.h"
    21 #include "Indexer.h"
     27
    2228#include <typeinfo>
     29#include <utility>
    2330#include "Common/utility.h"
    2431
     
    3340        }
    3441
    35         Indexer::Indexer( bool useDebug ) : doDebug( useDebug ) {}
    36 
    37         Indexer::~Indexer() {}
     42        struct Indexer::Impl {
     43                Impl() : refCount(1), size(0), base(),
     44                                idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {}
     45                Impl( const Indexer &_base ) : refCount(1), size(0), base( _base ),
     46                                idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {}
     47                unsigned long refCount;   ///< Number of references to these tables
     48                unsigned long size;       ///< Number of elements stored in this table
     49                const Indexer base;       ///< Base indexer this extends
     50               
     51                IdTable idTable;          ///< Identifier namespace
     52                TypeTable typeTable;      ///< Type namespace
     53                StructTable structTable;  ///< Struct namespace
     54                EnumTable enumTable;      ///< Enum namespace
     55                UnionTable unionTable;    ///< Union namespace
     56                TraitTable traitTable;    ///< Trait namespace
     57        };
     58
     59        Indexer::Impl *Indexer::newRef( Indexer::Impl *toClone ) {
     60                if ( ! toClone ) return 0;
     61
     62                // shorten the search chain by skipping empty links
     63                Indexer::Impl *ret = toClone->size == 0 ? toClone->base.tables : toClone;
     64                if ( ret ) { ++ret->refCount; }
     65
     66                return ret;
     67        }
     68
     69        void Indexer::deleteRef( Indexer::Impl *toFree ) {
     70                if ( ! toFree ) return;
     71
     72                if ( --toFree->refCount == 0 ) delete toFree;
     73        }
     74
     75        void Indexer::makeWritable() {
     76                if ( ! tables ) {
     77                        tables = new Indexer::Impl;
     78                } else if ( tables->refCount > 1 ) {
     79                        // tables->base inherits the ref that used to belong to this indexer
     80                        // this is basically equivalent to std::move( *this ) as the argument
     81                        tables = new Indexer::Impl( Indexer( tables, doDebug ) );
     82                }
     83        }
     84
     85        Indexer::Indexer( bool _doDebug ) : tables(0), doDebug( _doDebug ) {}
     86
     87        Indexer::Indexer( const Indexer &that ) : tables( newRef( that.tables ) ), doDebug( that.doDebug ) {}
     88
     89        Indexer::Indexer( Indexer &&that ) : tables( that.tables ), doDebug( that.doDebug ) {
     90                that.tables = 0;
     91        }
     92
     93        Indexer::~Indexer() {
     94                deleteRef( tables );
     95        }
     96
     97        Indexer& Indexer::operator= ( const Indexer &that ) {
     98                deleteRef( tables );
     99
     100                tables = newRef( that.tables );
     101                doDebug = that.doDebug;
     102
     103                return *this;
     104        }
     105
     106        Indexer& Indexer::operator= ( Indexer &&that ) {
     107                deleteRef( tables );
     108
     109                tables = that.tables;
     110                doDebug = that.doDebug;
     111
     112                that.tables = 0;
     113
     114                return *this;
     115        }
    38116
    39117        void Indexer::visit( ObjectDecl *objectDecl ) {
     
    45123                if ( objectDecl->get_name() != "" ) {
    46124                        debugPrint( "Adding object " << objectDecl->get_name() << std::endl );
    47                         idTable.addDecl( objectDecl );
     125                        addId( objectDecl );
    48126                } // if
    49127        }
     
    52130                if ( functionDecl->get_name() == "" ) return;
    53131                debugPrint( "Adding function " << functionDecl->get_name() << std::endl );
    54                 idTable.addDecl( functionDecl );
     132                addId( functionDecl );
    55133                enterScope();
    56134                maybeAccept( functionDecl->get_functionType(), *this );
     
    90168                leaveScope();
    91169                debugPrint( "Adding type " << typeDecl->get_name() << std::endl );
    92                 typeTable.add( typeDecl );
     170                addType( typeDecl );
    93171                acceptAll( typeDecl->get_assertions(), *this );
    94172        }
     
    100178                leaveScope();
    101179                debugPrint( "Adding typedef " << typeDecl->get_name() << std::endl );
    102                 typeTable.add( typeDecl );
     180                addType( typeDecl );
    103181        }
    104182
     
    108186                cloneAll( aggregateDecl->get_parameters(), fwdDecl.get_parameters() );
    109187                debugPrint( "Adding fwd decl for struct " << fwdDecl.get_name() << std::endl );
    110                 structTable.add( &fwdDecl );
     188                addStruct( &fwdDecl );
    111189 
    112190                enterScope();
     
    117195                debugPrint( "Adding struct " << aggregateDecl->get_name() << std::endl );
    118196                // this addition replaces the forward declaration
    119                 structTable.add( aggregateDecl );
     197                addStruct( aggregateDecl );
    120198        }
    121199
     
    125203                cloneAll( aggregateDecl->get_parameters(), fwdDecl.get_parameters() );
    126204                debugPrint( "Adding fwd decl for union " << fwdDecl.get_name() << std::endl );
    127                 unionTable.add( &fwdDecl );
     205                addUnion( &fwdDecl );
    128206 
    129207                enterScope();
     
    133211 
    134212                debugPrint( "Adding union " << aggregateDecl->get_name() << std::endl );
    135                 unionTable.add( aggregateDecl );
     213                addUnion( aggregateDecl );
    136214        }
    137215
    138216        void Indexer::visit( EnumDecl *aggregateDecl ) {
    139217                debugPrint( "Adding enum " << aggregateDecl->get_name() << std::endl );
    140                 enumTable.add( aggregateDecl );
     218                addEnum( aggregateDecl );
    141219                // unlike structs, contexts, and unions, enums inject their members into the global scope
    142220                acceptAll( aggregateDecl->get_members(), *this );
     
    150228 
    151229                debugPrint( "Adding context " << aggregateDecl->get_name() << std::endl );
    152                 contextTable.add( aggregateDecl );
     230                addTrait( aggregateDecl );
    153231        }
    154232
     
    299377
    300378        void Indexer::visit( StructInstType *structInst ) {
    301                 if ( ! structTable.lookup( structInst->get_name() ) ) {
     379                if ( ! lookupStruct( structInst->get_name() ) ) {
    302380                        debugPrint( "Adding struct " << structInst->get_name() << " from implicit forward declaration" << std::endl );
    303                         structTable.add( structInst->get_name() );
     381                        addStruct( structInst->get_name() );
    304382                }
    305383                enterScope();
     
    309387
    310388        void Indexer::visit( UnionInstType *unionInst ) {
    311                 if ( ! unionTable.lookup( unionInst->get_name() ) ) {
     389                if ( ! lookupUnion( unionInst->get_name() ) ) {
    312390                        debugPrint( "Adding union " << unionInst->get_name() << " from implicit forward declaration" << std::endl );
    313                         unionTable.add( unionInst->get_name() );
     391                        addUnion( unionInst->get_name() );
    314392                }
    315393                enterScope();
     
    327405
    328406        void Indexer::lookupId( const std::string &id, std::list< DeclarationWithType* > &list ) const {
    329                 idTable.lookupId( id, list );
     407                if ( ! tables ) return;
     408               
     409                tables->idTable.lookupId( id, list );
     410                tables->base.lookupId( id, list );
    330411        }
    331412
    332413        DeclarationWithType* Indexer::lookupId( const std::string &id) const {
    333                 return idTable.lookupId(id);
     414                if ( ! tables ) return 0;
     415               
     416                DeclarationWithType *ret = tables->idTable.lookupId(id);
     417                return ret ? ret : tables->base.lookupId(id);
    334418        }
    335419
    336420        NamedTypeDecl *Indexer::lookupType( const std::string &id ) const {
    337                 return typeTable.lookup( id );
     421                if ( ! tables ) return 0;
     422
     423                NamedTypeDecl *ret = tables->typeTable.lookup( id );
     424                return ret ? ret : tables->base.lookupType( id );
    338425        }
    339426
    340427        StructDecl *Indexer::lookupStruct( const std::string &id ) const {
    341                 return structTable.lookup( id );
     428                if ( ! tables ) return 0;
     429
     430                StructDecl *ret = tables->structTable.lookup( id );
     431                return ret ? ret : tables->base.lookupStruct( id );
    342432        }
    343433
    344434        EnumDecl *Indexer::lookupEnum( const std::string &id ) const {
    345                 return enumTable.lookup( id );
     435                if ( ! tables ) return 0;
     436
     437                EnumDecl *ret = tables->enumTable.lookup( id );
     438                return ret ? ret : tables->base.lookupEnum( id );
    346439        }
    347440
    348441        UnionDecl *Indexer::lookupUnion( const std::string &id ) const {
    349                 return unionTable.lookup( id );
    350         }
    351 
    352         TraitDecl  * Indexer::lookupTrait( const std::string &id ) const {
    353                 return contextTable.lookup( id );
     442                if ( ! tables ) return 0;
     443
     444                UnionDecl *ret = tables->unionTable.lookup( id );
     445                return ret ? ret : tables->base.lookupUnion( id );
     446        }
     447
     448        TraitDecl *Indexer::lookupTrait( const std::string &id ) const {
     449                if ( ! tables ) return 0;
     450
     451                TraitDecl *ret = tables->traitTable.lookup( id );
     452                return ret ? ret : tables->base.lookupTrait( id );
     453        }
     454
     455        void Indexer::addId( DeclarationWithType *decl ) {
     456                makeWritable();
     457                tables->idTable.addDecl( decl );
     458                ++tables->size;
     459        }
     460       
     461        void Indexer::addType( NamedTypeDecl *decl ) {
     462                makeWritable();
     463                tables->typeTable.add( decl );
     464                ++tables->size;
     465        }
     466
     467        void Indexer::addStruct( const std::string &id ) {
     468                makeWritable();
     469                tables->structTable.add( id );
     470                ++tables->size;
     471        }
     472       
     473        void Indexer::addStruct( StructDecl *decl ) {
     474                makeWritable();
     475                tables->structTable.add( decl );
     476                ++tables->size;
     477        }
     478       
     479        void Indexer::addEnum( EnumDecl *decl ) {
     480                makeWritable();
     481                tables->enumTable.add( decl );
     482                ++tables->size;
     483        }
     484
     485        void Indexer::addUnion( const std::string &id ) {
     486                makeWritable();
     487                tables->unionTable.add( id );
     488                ++tables->size;
     489        }
     490       
     491        void Indexer::addUnion( UnionDecl *decl ) {
     492                makeWritable();
     493                tables->unionTable.add( decl );
     494                ++tables->size;
     495        }
     496       
     497        void Indexer::addTrait( TraitDecl *decl ) {
     498                makeWritable();
     499                tables->traitTable.add( decl );
     500                ++tables->size;
    354501        }
    355502
    356503        void Indexer::enterScope() {
     504                makeWritable();
     505               
    357506                if ( doDebug ) {
    358507                        std::cout << "--- Entering scope" << std::endl;
    359508                }
    360                 idTable.enterScope();
    361                 typeTable.enterScope();
    362                 structTable.enterScope();
    363                 enumTable.enterScope();
    364                 unionTable.enterScope();
    365                 contextTable.enterScope();
     509
     510                tables->idTable.enterScope();
     511                tables->typeTable.enterScope();
     512                tables->structTable.enterScope();
     513                tables->enumTable.enterScope();
     514                tables->unionTable.enterScope();
     515                tables->traitTable.enterScope();
    366516        }
    367517
    368518        void Indexer::leaveScope() {
    369519                using std::cout;
    370                 using std::endl;
    371  
     520               
     521                makeWritable();
     522               
    372523                if ( doDebug ) {
    373                         cout << "--- Leaving scope containing" << endl;
    374                         idTable.dump( cout );
    375                         typeTable.dump( cout );
    376                         structTable.dump( cout );
    377                         enumTable.dump( cout );
    378                         unionTable.dump( cout );
    379                         contextTable.dump( cout );
    380                 }
    381                 idTable.leaveScope();
    382                 typeTable.leaveScope();
    383                 structTable.leaveScope();
    384                 enumTable.leaveScope();
    385                 unionTable.leaveScope();
    386                 contextTable.leaveScope();
     524                        cout << "--- Leaving scope containing" << std::endl;
     525                        tables->idTable.dump( cout );
     526                        tables->typeTable.dump( cout );
     527                        tables->structTable.dump( cout );
     528                        tables->enumTable.dump( cout );
     529                        tables->unionTable.dump( cout );
     530                        tables->traitTable.dump( cout );
     531                }
     532                tables->idTable.leaveScope();
     533                tables->typeTable.leaveScope();
     534                tables->structTable.leaveScope();
     535                tables->enumTable.leaveScope();
     536                tables->unionTable.leaveScope();
     537                tables->traitTable.leaveScope();
    387538        }
    388539
    389540        void Indexer::print( std::ostream &os, int indent ) const {
    390541            using std::cerr;
    391             using std::endl;
    392 
    393             cerr << "===idTable===" << endl;
    394             idTable.dump( os );
    395             cerr << "===typeTable===" << endl;
    396             typeTable.dump( os );
    397             cerr << "===structTable===" << endl;
    398             structTable.dump( os );
    399             cerr << "===enumTable===" << endl;
    400             enumTable.dump( os );
    401             cerr << "===unionTable===" << endl;
    402             unionTable.dump( os );
    403             cerr << "===contextTable===" << endl;
    404             contextTable.dump( os );
    405 #if 0
    406                 idTable.dump( os );
    407                 typeTable.dump( os );
    408                 structTable.dump( os );
    409                 enumTable.dump( os );
    410                 unionTable.dump( os );
    411                 contextTable.dump( os );
    412 #endif
     542
     543            cerr << "===idTable===" << std::endl;
     544            if ( tables ) tables->idTable.dump( os );
     545            cerr << "===typeTable===" << std::endl;
     546            if ( tables ) tables->typeTable.dump( os );
     547            cerr << "===structTable===" << std::endl;
     548            if ( tables ) tables->structTable.dump( os );
     549            cerr << "===enumTable===" << std::endl;
     550            if ( tables ) tables->enumTable.dump( os );
     551            cerr << "===unionTable===" << std::endl;
     552            if ( tables ) tables->unionTable.dump( os );
     553            cerr << "===contextTable===" << std::endl;
     554            if ( tables ) tables->traitTable.dump( os );
    413555        }
    414556} // namespace SymTab
  • src/SymTab/Indexer.h

    r4e284ea6 re8032b0  
    2121
    2222#include "SynTree/Visitor.h"
    23 #include "IdTable.h"
    24 #include "AggregateTable.h"
    25 #include "TypeTable.h"
    2623
    2724namespace SymTab {
     
    2926          public:
    3027                Indexer( bool useDebug = false );
     28
     29                Indexer( const Indexer &that );
     30                Indexer( Indexer &&that );
    3131                virtual ~Indexer();
     32                Indexer& operator= ( const Indexer &that );
     33                Indexer& operator= ( Indexer &&that );
    3234
    3335                //using Visitor::visit;
     
    7880                void leaveScope();
    7981
    80                 void lookupId( const std::string &id, std::list< DeclarationWithType* >& ) const;
    81                 DeclarationWithType* lookupId( const std::string &id) const;
     82                void lookupId( const std::string &id, std::list< DeclarationWithType* > &out ) const;
     83                DeclarationWithType* lookupId( const std::string &id ) const;
    8284                NamedTypeDecl *lookupType( const std::string &id ) const;
    8385                StructDecl *lookupStruct( const std::string &id ) const;
     
    8890                void print( std::ostream &os, int indent = 0 ) const;
    8991          private:
    90                 IdTable idTable;
    91                 TypeTable typeTable;
    92                 StructTable structTable;
    93                 EnumTable enumTable;
    94                 UnionTable unionTable;
    95                 TraitTable contextTable;
    96  
    97                 bool doDebug;                                   // display debugging trace
     92                void addId( DeclarationWithType *decl );
     93                void addType( NamedTypeDecl *decl );
     94                void addStruct( const std::string &id );
     95                void addStruct( StructDecl *decl );
     96                void addEnum( EnumDecl *decl );
     97                void addUnion( const std::string &id );
     98                void addUnion( UnionDecl *decl );
     99                void addTrait( TraitDecl *decl );
     100               
     101                struct Impl;
     102                Impl *tables;  ///< Copy-on-write instance of table data structure
     103                bool doDebug;  ///< Display debugging trace?
     104
     105                Indexer( Impl *_tables, bool _doDebug ) : tables( _tables ), doDebug( _doDebug ) {}
     106
     107                /// Takes a new ref to a table (returns null if null)
     108                static Impl *newRef( Impl *toClone );
     109                /// Clears a ref to a table (does nothing if null)
     110                static void deleteRef( Impl *toFree );
     111
     112                /// Ensures that tables variable is writable (i.e. allocated and uniquely owned by this Indexer)
     113                void makeWritable();
    98114        };
    99115} // namespace SymTab
Note: See TracChangeset for help on using the changeset viewer.