Changeset e5c3811


Ignore:
Timestamp:
Nov 25, 2020, 3:12:17 AM (10 months ago)
Author:
Fangren Yu <f37yu@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
4702a2c
Parents:
7192145
Message:

create dedicated symbol tables for big 3 operators
note: arbitrary this param type is not supported; it is currently allowed although never used

Location:
src
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • src/AST/Decl.hpp

    r7192145 re5c3811  
    7575        int scopeLevel = 0;
    7676
     77        /*
     78        ForallDecl foralls {
     79                list<TypeDecl> params
     80                list<ObjectDecl> assns
     81        }
     82        */
     83
    7784        std::vector<ptr<Attribute>> attributes;
    7885        Function::Specs funcSpec;
  • src/AST/SymbolTable.cpp

    r7192145 re5c3811  
    9595}
    9696
     97SymbolTable::SpecialFunctionKind SymbolTable::getSpecialFunctionKind(const std::string & name) {
     98        if (name == "?{}") return CTOR;
     99        if (name == "^?{}") return DTOR;
     100        if (name == "?=?") return ASSIGN;
     101        return NUMBER_OF_KINDS;
     102}
     103
    97104std::vector<SymbolTable::IdData> SymbolTable::lookupId( const std::string &id ) const {
     105        static Stats::Counters::CounterGroup * name_lookup_stats = Stats::Counters::build<Stats::Counters::CounterGroup>("Name Lookup Stats");
     106        static std::map<std::string, Stats::Counters::SimpleCounter *> lookups_by_name;
     107        static std::map<std::string, Stats::Counters::SimpleCounter *> candidates_by_name;
     108
     109        SpecialFunctionKind kind = getSpecialFunctionKind(id);
     110        if (kind != NUMBER_OF_KINDS) return specialLookupId(kind);
     111
    98112        ++*stats().lookup_calls;
    99113        if ( ! idTable ) return {};
     
    107121                out.push_back( decl.second );
    108122        }
     123
     124        if (Stats::Counters::enabled) {
     125                if (! lookups_by_name.count(id)) {
     126                        // leaks some strings, but it is because Counters do not hold them
     127                        auto lookupCounterName = new std::string(id + "%count");
     128                        auto candidatesCounterName = new std::string(id + "%candidate");
     129                        lookups_by_name.emplace(id, new Stats::Counters::SimpleCounter(lookupCounterName->c_str(), name_lookup_stats));
     130                        candidates_by_name.emplace(id, new Stats::Counters::SimpleCounter(candidatesCounterName->c_str(), name_lookup_stats));
     131                }
     132                (*lookups_by_name[id]) ++;
     133                *candidates_by_name[id] += out.size();
     134        }
     135
     136        return out;
     137}
     138
     139std::vector<SymbolTable::IdData> SymbolTable::specialLookupId( SymbolTable::SpecialFunctionKind kind, const std::string & otypeKey ) const {
     140        static Stats::Counters::CounterGroup * special_stats = Stats::Counters::build<Stats::Counters::CounterGroup>("Special Lookups");
     141        static Stats::Counters::SimpleCounter * stat_counts[3] = {
     142                Stats::Counters::build<Stats::Counters::SimpleCounter>("constructor - count", special_stats),
     143                Stats::Counters::build<Stats::Counters::SimpleCounter>("destructor - count", special_stats),
     144                Stats::Counters::build<Stats::Counters::SimpleCounter>("assignment - count", special_stats)
     145        };
     146
     147        static Stats::Counters::SimpleCounter * stat_candidates[3] = {
     148                Stats::Counters::build<Stats::Counters::SimpleCounter>("constructor - candidates", special_stats),
     149                Stats::Counters::build<Stats::Counters::SimpleCounter>("destructor - candidates", special_stats),
     150                Stats::Counters::build<Stats::Counters::SimpleCounter>("assignment - candidates", special_stats)
     151        };
     152
     153        static Stats::Counters::SimpleCounter * num_lookup_with_key
     154                = Stats::Counters::build<Stats::Counters::SimpleCounter>("keyed lookups", special_stats);
     155        static Stats::Counters::SimpleCounter * num_lookup_without_key
     156                = Stats::Counters::build<Stats::Counters::SimpleCounter>("unkeyed lookups", special_stats);
     157
     158        assert (kind != NUMBER_OF_KINDS);
     159        ++*stats().lookup_calls;
     160        if ( ! specialFunctionTable[kind] ) return {};
     161
     162        std::vector<IdData> out;
     163
     164        if (otypeKey.empty()) { // returns everything
     165                ++*num_lookup_without_key;
     166                for (auto & table : *specialFunctionTable[kind]) {
     167                        for (auto & decl : *table.second) {
     168                                out.push_back(decl.second);
     169                        }
     170                }
     171        }
     172        else {
     173                ++*num_lookup_with_key;
     174                ++*stats().map_lookups;
     175                auto decls = specialFunctionTable[kind]->find(otypeKey);
     176                if (decls == specialFunctionTable[kind]->end()) return {};
     177
     178                for (auto decl : *(decls->second)) {
     179                        out.push_back(decl.second);
     180                }
     181        }
     182
     183        ++*stat_counts[kind];
     184        *stat_candidates[kind] += out.size();
     185
    109186        return out;
    110187}
     
    366443namespace {
    367444        /// gets the base type of the first parameter; decl must be a ctor/dtor/assignment function
    368         std::string getOtypeKey( const FunctionDecl * function ) {
    369                 const auto & params = function->type->params;
     445        std::string getOtypeKey( const FunctionType * ftype, bool stripParams = true ) {
     446                const auto & params = ftype->params;
    370447                assert( ! params.empty() );
    371448                // use base type of pointer, so that qualifiers on the pointer type aren't considered.
    372449                const Type * base = InitTweak::getPointerBase( params.front() );
    373450                assert( base );
    374                 return Mangle::mangle( base );
     451                if (stripParams) {
     452                        if (dynamic_cast<const PointerType *>(base)) return Mangle::Encoding::pointer;
     453                        return Mangle::mangle( base, Mangle::Type | Mangle::NoGenericParams );
     454                }
     455                else
     456                        return Mangle::mangle( base ); 
    375457        }
    376458
     
    380462                        const DeclWithType * decl, const std::string & otypeKey ) {
    381463                auto func = dynamic_cast< const FunctionDecl * >( decl );
    382                 if ( ! func || otypeKey != getOtypeKey( func ) ) return nullptr;
     464                if ( ! func || otypeKey != getOtypeKey( func->type, false ) ) return nullptr;
    383465                return func;
    384466        }
     
    405487        bool dataIsUserDefinedFunc = ! function->linkage.is_overrideable;
    406488        bool dataIsCopyFunc = InitTweak::isCopyFunction( function );
    407         std::string dataOtypeKey = getOtypeKey( function );
     489        std::string dataOtypeKey = getOtypeKey( function->type, false ); // requires exact match to override autogen
    408490
    409491        if ( dataIsUserDefinedFunc && dataIsCopyFunc ) {
     
    577659                const DeclWithType * decl, SymbolTable::OnConflict handleConflicts, const Expr * baseExpr,
    578660                const Decl * deleter ) {
     661        SpecialFunctionKind kind = getSpecialFunctionKind(decl->name);
     662        if (kind == NUMBER_OF_KINDS) { // not a special decl
     663                addId(decl, decl->name, idTable, handleConflicts, baseExpr, deleter);
     664        }
     665        else {
     666                std::string key;
     667                if (auto func = dynamic_cast<const FunctionDecl *>(decl)) {
     668                        key = getOtypeKey(func->type);
     669                }
     670                else if (auto obj = dynamic_cast<const ObjectDecl *>(decl)) {
     671                        key = getOtypeKey(obj->type.strict_as<PointerType>()->base.strict_as<FunctionType>());
     672                }
     673                else {
     674                        assertf(false, "special decl with non-function type");
     675                }
     676                addId(decl, key, specialFunctionTable[kind], handleConflicts, baseExpr, deleter);
     677        }
     678}
     679
     680void SymbolTable::addId(
     681                const DeclWithType * decl, const std::string & lookupKey, IdTable::Ptr & table, SymbolTable::OnConflict handleConflicts, const Expr * baseExpr,
     682                const Decl * deleter ) {
    579683        ++*stats().add_calls;
    580684        const std::string &name = decl->name;
     
    607711        // ensure tables exist and add identifier
    608712        MangleTable::Ptr mangleTable;
    609         if ( ! idTable ) {
    610                 idTable = IdTable::new_ptr();
     713        if ( ! table ) {
     714                table = IdTable::new_ptr();
    611715                mangleTable = MangleTable::new_ptr();
    612716        } else {
    613717                ++*stats().map_lookups;
    614                 auto decls = idTable->find( name );
    615                 if ( decls == idTable->end() ) {
     718                auto decls = table->find( lookupKey );
     719                if ( decls == table->end() ) {
    616720                        mangleTable = MangleTable::new_ptr();
    617721                } else {
     
    628732                                                lazyInitScope();
    629733                                                *stats().map_mutations += 2;
    630                                                 idTable = idTable->set(
    631                                                         name,
     734                                                table = table->set(
     735                                                        lookupKey,
    632736                                                        mangleTable->set(
    633737                                                                mangleName,
     
    644748        IdData data{ decl, baseExpr, deleter, scope };
    645749        // Ensure that auto-generated ctor/dtor/assignment are deleted if necessary
    646         if ( ! removeSpecialOverrides( data, mangleTable ) ) return;
     750        if (table != idTable) { // adding to special table
     751                if ( ! removeSpecialOverrides( data, mangleTable ) ) return;
     752        }
    647753        *stats().map_mutations += 2;
    648         idTable = idTable->set( name, mangleTable->set( mangleName, std::move(data) ) );
     754        table = table->set( lookupKey, mangleTable->set( mangleName, std::move(data) ) );
    649755}
    650756
  • src/AST/SymbolTable.hpp

    r7192145 re5c3811  
    3333class SymbolTable final : public std::enable_shared_from_this<ast::SymbolTable> {
    3434public:
     35        /// special functions stored in dedicated tables, with different lookup keys
     36        enum SpecialFunctionKind {CTOR, DTOR, ASSIGN, NUMBER_OF_KINDS};
     37        static SpecialFunctionKind getSpecialFunctionKind(const std::string & name);
     38
    3539        /// Stored information about a declaration
    3640        struct IdData {
     
    7781        UnionTable::Ptr unionTable;    ///< union namespace
    7882        TraitTable::Ptr traitTable;    ///< trait namespace
     83        IdTable::Ptr specialFunctionTable[NUMBER_OF_KINDS];
     84
     85        // using SpecialFuncTable = PersistentMap< std::string, IdTable::Ptr >; // fname (ctor/dtor/assign) - otypekey
     86        // SpecialFuncTable::Ptr specialFuncTable;
    7987
    8088        using Ptr = std::shared_ptr<const SymbolTable>;
     
    95103        /// Gets all declarations with the given ID
    96104        std::vector<IdData> lookupId( const std::string &id ) const;
     105        /// Gets special functions associated with a type; if no key is given, returns everything
     106        std::vector<IdData> specialLookupId( SpecialFunctionKind kind, const std::string & otypeKey = "" ) const;
    97107        /// Gets the top-most type declaration with the given ID
    98108        const NamedTypeDecl * lookupType( const std::string &id ) const;
     
    186196                const Decl * deleter = nullptr );
    187197
     198        /// common code for addId when special decls are placed into separate tables
     199        void addId(
     200                const DeclWithType * decl, const std::string & lookupKey, IdTable::Ptr & idTable, OnConflict handleConflicts,
     201                const Expr * baseExpr = nullptr, const Decl * deleter = nullptr);
     202       
    188203        /// adds all of the members of the Aggregate (addWith helper)
    189204        void addMembers( const AggregateDecl * aggr, const Expr * expr, OnConflict handleConflicts );
  • src/AST/Type.cpp

    r7192145 re5c3811  
    216216}
    217217
     218bool isUnboundType(const Type * type) {
     219        if (auto typeInst = dynamic_cast<const TypeInstType *>(type)) {
     220                // xxx - look for a type name produced by renameTyVars.
     221
     222                // TODO: once TypeInstType representation is updated, it should properly check
     223                // if the context id is filled. this is a temporary hack for now
     224                if (std::count(typeInst->name.begin(), typeInst->name.end(), '_') >= 3) {
     225                        return true;
     226                }
     227        }
     228        return false;
     229}
     230
    218231}
    219232
  • src/AST/Type.hpp

    r7192145 re5c3811  
    274274public:
    275275        using ForallList = std::vector<ptr<TypeDecl>>;
    276 
     276        // using ForallList = std::vector<readonly<TypeDecl>>;
     277
     278        // using ForallList = std::vector<ptr<TypeInstType>>;
    277279        ForallList forall;
     280        // using AssertionList = std::vector<ptr<VariableExpr>>;
     281        // AssertionList assertions;
    278282
    279283        ParameterizedType( ForallList&& fs = {}, CV::Qualifiers q = {},
     
    423427public:
    424428        readonly<TypeDecl> base;
     429        // int context;
    425430        TypeDecl::Kind kind;
    426431
     
    535540};
    536541
     542bool isUnboundType(const Type * type);
     543
    537544}
     545
    538546
    539547#undef MUTATE_FRIEND
     
    541549// Local Variables: //
    542550// tab-width: 4 //
     551
    543552// mode: c++ //
    544553// compile-command: "make install" //
  • src/ResolvExpr/CandidateFinder.cpp

    r7192145 re5c3811  
    4343#include "SymTab/Validate.h"      // for validateType
    4444#include "Tuples/Tuples.h"        // for handleTupleAssignment
     45#include "InitTweak/InitTweak.h"  // for getPointerBase
     46
     47#include "Common/Stats/Counter.h"
    4548
    4649#define PRINT( text ) if ( resolvep ) { text }
     
    864867
    865868                void postvisit( const ast::UntypedExpr * untypedExpr ) {
    866                         CandidateFinder funcFinder{ symtab, tenv };
    867                         funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() );
    868                         // short-circuit if no candidates
    869                         if ( funcFinder.candidates.empty() ) return;
    870 
    871                         reason.code = NoMatch;
    872 
    873869                        std::vector< CandidateFinder > argCandidates =
    874870                                selfFinder.findSubExprs( untypedExpr->args );
     
    877873                        // if not tuple assignment, handled as normal function call
    878874                        Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
     875
     876                        CandidateFinder funcFinder{ symtab, tenv };
     877                        if (auto nameExpr = untypedExpr->func.as<ast::NameExpr>()) {
     878                                auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);
     879                                if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) {
     880                                        assertf(!argCandidates.empty(), "special function call without argument");
     881                                        for (auto & firstArgCand: argCandidates[0]) {
     882                                                ast::ptr<ast::Type> argType = firstArgCand->expr->result;
     883                                                firstArgCand->env.apply(argType);
     884                                                // strip references
     885                                                // xxx - is this correct?
     886                                                while (argType.as<ast::ReferenceType>()) argType = argType.as<ast::ReferenceType>()->base;
     887
     888                                                // convert 1-tuple to plain type
     889                                                if (auto tuple = argType.as<ast::TupleType>()) {
     890                                                        if (tuple->size() == 1) {
     891                                                                argType = tuple->types[0];
     892                                                        }
     893                                                }
     894                                               
     895                                                // if argType is an unbound type parameter, all special functions need to be searched.
     896                                                if (isUnboundType(argType)) {
     897                                                        funcFinder.otypeKeys.clear();
     898                                                        break;
     899                                                }
     900
     901                                                if (argType.as<ast::PointerType>()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer);
     902                                                else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type));
     903                                        }
     904                                }
     905                        }
     906                        // if candidates are already produced, do not fail
     907                        // xxx - is it possible that handleTupleAssignment and main finder both produce candidates?
     908                        // this means there exists ctor/assign functions with a tuple as first parameter.
     909                        funcFinder.find( untypedExpr->func, selfFinder.candidates.empty() ? ResolvMode::withAdjustment() : ResolvMode::withoutFailFast() );
     910                        // short-circuit if no candidates
     911                        // if ( funcFinder.candidates.empty() ) return;
     912
     913                        reason.code = NoMatch;
    879914
    880915                        // find function operators
     
    11871222
    11881223                void postvisit( const ast::NameExpr * nameExpr ) {
    1189                         std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name );
     1224                        std::vector< ast::SymbolTable::IdData > declList;
     1225                        if (!selfFinder.otypeKeys.empty()) {
     1226                                auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);
     1227                                assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str());
     1228
     1229                                for (auto & otypeKey: selfFinder.otypeKeys) {
     1230                                        auto result = symtab.specialLookupId(kind, otypeKey);
     1231                                        declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end()));
     1232                                }
     1233                        }
     1234                        else {
     1235                                declList = symtab.lookupId( nameExpr->name );
     1236                        }
    11901237                        PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
     1238
    11911239                        if( declList.empty() ) return;
    11921240
     
    15581606                                        }
    15591607                                }
     1608
    15601609                        }
    15611610
  • src/ResolvExpr/CandidateFinder.hpp

    r7192145 re5c3811  
    3131        const ast::TypeEnvironment & env;  ///< Substitutions performed in this resolution
    3232        ast::ptr< ast::Type > targetType;  ///< Target type for resolution
     33        std::set< std::string > otypeKeys;  /// different type may map to same key
    3334
    3435        CandidateFinder(
  • src/ResolvExpr/SatisfyAssertions.cpp

    r7192145 re5c3811  
    167167                // find candidates that unify with the desired type
    168168                AssnCandidateList matches;
    169                 for ( const ast::SymbolTable::IdData & cdata : sat.symtab.lookupId( assn.first->name ) ) {
     169
     170                std::vector<ast::SymbolTable::IdData> candidates;
     171                auto kind = ast::SymbolTable::getSpecialFunctionKind(assn.first->name);
     172                if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) {
     173                        // prefilter special decls by argument type, if already known
     174                        ast::ptr<ast::Type> thisArgType = strict_dynamic_cast<const ast::PointerType *>(assn.first->get_type())->base
     175                                .strict_as<ast::FunctionType>()->params[0]
     176                                .strict_as<ast::ReferenceType>()->base;
     177                        sat.cand->env.apply(thisArgType);
     178
     179                        std::string otypeKey = "";
     180                        if (thisArgType.as<ast::PointerType>()) otypeKey = Mangle::Encoding::pointer;
     181                        else if (!isUnboundType(thisArgType)) otypeKey = Mangle::mangle(thisArgType, Mangle::Type | Mangle::NoGenericParams);
     182
     183                        candidates = sat.symtab.specialLookupId(kind, otypeKey);
     184                }
     185                else {
     186                        candidates = sat.symtab.lookupId(assn.first->name);
     187                }
     188                for ( const ast::SymbolTable::IdData & cdata : candidates ) {
    170189                        const ast::DeclWithType * candidate = cdata.id;
    171190
Note: See TracChangeset for help on using the changeset viewer.