Changeset ea5daeb for src/GenPoly/Box.cc


Ignore:
Timestamp:
Aug 4, 2016, 7:39:46 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, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
5070fe4
Parents:
e93bc13
Message:

Move generic instantiation earlier

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/GenPoly/Box.cc

    re93bc13 rea5daeb  
    6262
    6363                FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars );
    64 
    65                 /// Abstracts type equality for a list of parameter types
    66                 struct TypeList {
    67                         TypeList() : params() {}
    68                         TypeList( const std::list< Type* > &_params ) : params() { cloneAll(_params, params); }
    69                         TypeList( std::list< Type* > &&_params ) : params( _params ) {}
    70 
    71                         TypeList( const TypeList &that ) : params() { cloneAll(that.params, params); }
    72                         TypeList( TypeList &&that ) : params( std::move( that.params ) ) {}
    73 
    74                         /// Extracts types from a list of TypeExpr*
    75                         TypeList( const std::list< TypeExpr* >& _params ) : params() {
    76                                 for ( std::list< TypeExpr* >::const_iterator param = _params.begin(); param != _params.end(); ++param ) {
    77                                         params.push_back( (*param)->get_type()->clone() );
    78                                 }
    79                         }
    80 
    81                         TypeList& operator= ( const TypeList &that ) {
    82                                 deleteAll( params );
    83 
    84                                 params.clear();
    85                                 cloneAll( that.params, params );
    86 
    87                                 return *this;
    88                         }
    89 
    90                         TypeList& operator= ( TypeList &&that ) {
    91                                 deleteAll( params );
    92 
    93                                 params = std::move( that.params );
    94 
    95                                 return *this;
    96                         }
    97 
    98                         ~TypeList() { deleteAll( params ); }
    99 
    100                         bool operator== ( const TypeList& that ) const {
    101                                 if ( params.size() != that.params.size() ) return false;
    102 
    103                                 SymTab::Indexer dummy;
    104                                 for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) {
    105                                         if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false;
    106                                 }
    107                                 return true;
    108                         }
    109 
    110                         std::list< Type* > params;  ///< Instantiation parameters
    111                 };
    112 
    113                 /// Maps a key and a TypeList to the some value, accounting for scope
    114                 template< typename Key, typename Value >
    115                 class InstantiationMap {
    116                         /// Wraps value for a specific (Key, TypeList) combination
    117                         typedef std::pair< TypeList, Value* > Instantiation;
    118                         /// List of TypeLists paired with their appropriate values
    119                         typedef std::vector< Instantiation > ValueList;
    120                         /// Underlying map type; maps keys to a linear list of corresponding TypeLists and values
    121                         typedef ScopedMap< Key*, ValueList > InnerMap;
    122 
    123                         InnerMap instantiations;  ///< instantiations
    124 
    125                 public:
    126                         /// Starts a new scope
    127                         void beginScope() { instantiations.beginScope(); }
    128 
    129                         /// Ends a scope
    130                         void endScope() { instantiations.endScope(); }
    131 
    132                         /// Gets the value for the (key, typeList) pair, returns NULL on none such.
    133                         Value *lookup( Key *key, const std::list< TypeExpr* >& params ) const {
    134                                 TypeList typeList( params );
    135 
    136                                 // scan scopes for matches to the key
    137                                 for ( typename InnerMap::const_iterator insts = instantiations.find( key ); insts != instantiations.end(); insts = instantiations.findNext( insts, key ) ) {
    138                                         for ( typename ValueList::const_reverse_iterator inst = insts->second.rbegin(); inst != insts->second.rend(); ++inst ) {
    139                                                 if ( inst->first == typeList ) return inst->second;
    140                                         }
    141                                 }
    142                                 // no matching instantiations found
    143                                 return 0;
    144                         }
    145 
    146                         /// Adds a value for a (key, typeList) pair to the current scope
    147                         void insert( Key *key, const std::list< TypeExpr* > &params, Value *value ) {
    148                                 instantiations[ key ].push_back( Instantiation( TypeList( params ), value ) );
    149                         }
    150                 };
    15164
    15265                /// Adds layout-generation functions to polymorphic types
    … …  
    239152                };
    240153
    241                 /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately
    242                 class GenericInstantiator : public DeclMutator {
    243                         /// Map of (generic type, parameter list) pairs to concrete type instantiations
    244                         InstantiationMap< AggregateDecl, AggregateDecl > instantiations;
    245                         /// Namer for concrete types
    246                         UniqueName typeNamer;
    247 
    248                 public:
    249                         GenericInstantiator() : DeclMutator(), instantiations(), typeNamer("_conc_") {}
    250 
    251                         virtual Type* mutate( StructInstType *inst );
    252                         virtual Type* mutate( UnionInstType *inst );
    253 
    254         //              virtual Expression* mutate( MemberExpr *memberExpr );
    255 
    256                         virtual void doBeginScope();
    257                         virtual void doEndScope();
    258                 private:
    259                         /// Wrap instantiation lookup for structs
    260                         StructDecl* lookup( StructInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (StructDecl*)instantiations.lookup( inst->get_baseStruct(), typeSubs ); }
    261                         /// Wrap instantiation lookup for unions
    262                         UnionDecl* lookup( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (UnionDecl*)instantiations.lookup( inst->get_baseUnion(), typeSubs ); }
    263                         /// Wrap instantiation insertion for structs
    264                         void insert( StructInstType *inst, const std::list< TypeExpr* > &typeSubs, StructDecl *decl ) { instantiations.insert( inst->get_baseStruct(), typeSubs, decl ); }
    265                         /// Wrap instantiation insertion for unions
    266                         void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { instantiations.insert( inst->get_baseUnion(), typeSubs, decl ); }
    267                 };
    268 
    269154                /// Replaces member and size/align/offsetof expressions on polymorphic generic types with calculated expressions.
    270155                /// * Replaces member expressions for polymorphic types with calculated add-field-offset-and-dereference
    … …  
    354239                Pass1 pass1;
    355240                Pass2 pass2;
    356                 GenericInstantiator instantiator;
    357241                PolyGenericCalculator polyCalculator;
    358242                Pass3 pass3;
    … …  
    361245                mutateTranslationUnit/*All*/( translationUnit, pass1 );
    362246                mutateTranslationUnit/*All*/( translationUnit, pass2 );
    363                 instantiator.mutateDeclarationList( translationUnit );
    364247                mutateTranslationUnit/*All*/( translationUnit, polyCalculator );
    365248                mutateTranslationUnit/*All*/( translationUnit, pass3 );
    … …  
    889772                                                arg++;
    890773                                        } else {
    891                                                 /// xxx - should this be an assertion?
     774                                                // xxx - should this be an assertion?
    892775                                                throw SemanticError( "unbound type variable: " + tyParm->first + " in application ", appExpr );
    893776                                        } // if
    … …  
    902785                        std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin();
    903786                        std::list< Expression* >::const_iterator fnArg = arg;
    904                         std::set< std::string > seenTypes; //< names for generic types we've seen
     787                        std::set< std::string > seenTypes; ///< names for generic types we've seen
    905788
    906789                        // a polymorphic return type may need to be added to the argument list
    … …  
    1042925                /// this gets rid of warnings from gcc.
    1043926                void addCast( Expression *&actual, Type *formal, const TyVarMap &tyVars ) {
    1044                         Type * newType = formal->clone();
    1045                         if ( getFunctionType( newType ) ) {
     927                        if ( getFunctionType( formal ) ) {
     928                                Type * newType = formal->clone();
    1046929                                newType = ScrubTyVars::scrub( newType, tyVars );
    1047930                                actual = new CastExpr( actual, newType );
    … …  
    17751658                }
    17761659
    1777 //////////////////////////////////////// GenericInstantiator //////////////////////////////////////////////////
    1778 
    1779                 /// Makes substitutions of params into baseParams; returns true if all parameters substituted for a concrete type
    1780                 bool makeSubstitutions( const std::list< TypeDecl* >& baseParams, const std::list< Expression* >& params, std::list< TypeExpr* >& out ) {
    1781                         bool allConcrete = true;  // will finish the substitution list even if they're not all concrete
    1782 
    1783                         // substitute concrete types for given parameters, and incomplete types for placeholders
    1784                         std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
    1785                         std::list< Expression* >::const_iterator param = params.begin();
    1786                         for ( ; baseParam != baseParams.end() && param != params.end(); ++baseParam, ++param ) {
    1787         //                      switch ( (*baseParam)->get_kind() ) {
    1788         //                      case TypeDecl::Any: {   // any type is a valid substitution here; complete types can be used to instantiate generics
    1789                                         TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
    1790                                         assert(paramType && "Aggregate parameters should be type expressions");
    1791                                         out.push_back( paramType->clone() );
    1792                                         // check that the substituted type isn't a type variable itself
    1793                                         if ( dynamic_cast< TypeInstType* >( paramType->get_type() ) ) {
    1794                                                 allConcrete = false;
    1795                                         }
    1796         //                              break;
    1797         //                      }
    1798         //                      case TypeDecl::Dtype:  // dtype can be consistently replaced with void [only pointers, which become void*]
    1799         //                              out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) );
    1800         //                              break;
    1801         //                      case TypeDecl::Ftype:  // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype]
    1802         //                              out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) );
    1803         //                              break;
    1804         //                      }
    1805                         }
    1806 
    1807                         // if any parameters left over, not done
    1808                         if ( baseParam != baseParams.end() ) return false;
    1809         //              // if not enough parameters given, substitute remaining incomplete types for placeholders
    1810         //              for ( ; baseParam != baseParams.end(); ++baseParam ) {
    1811         //                      switch ( (*baseParam)->get_kind() ) {
    1812         //                      case TypeDecl::Any:    // no more substitutions here, fail early
    1813         //                              return false;
    1814         //                      case TypeDecl::Dtype:  // dtype can be consistently replaced with void [only pointers, which become void*]
    1815         //                              out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) );
    1816         //                              break;
    1817         //                      case TypeDecl::Ftype:  // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype]
    1818         //                              out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) );
    1819         //                              break;
    1820         //                      }
    1821         //              }
    1822 
    1823                         return allConcrete;
    1824                 }
    1825 
    1826                 /// Substitutes types of members of in according to baseParams => typeSubs, appending the result to out
    1827                 void substituteMembers( const std::list< Declaration* >& in, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs,
    1828                                                                 std::list< Declaration* >& out ) {
    1829                         // substitute types into new members
    1830                         TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() );
    1831                         for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) {
    1832                                 Declaration *newMember = (*member)->clone();
    1833                                 subs.apply(newMember);
    1834                                 out.push_back( newMember );
    1835                         }
    1836                 }
    1837 
    1838                 Type* GenericInstantiator::mutate( StructInstType *inst ) {
    1839                         // mutate subtypes
    1840                         Type *mutated = Mutator::mutate( inst );
    1841                         inst = dynamic_cast< StructInstType* >( mutated );
    1842                         if ( ! inst ) return mutated;
    1843 
    1844                         // exit early if no need for further mutation
    1845                         if ( inst->get_parameters().empty() ) return inst;
    1846                         assert( inst->get_baseParameters() && "Base struct has parameters" );
    1847 
    1848                         // check if type can be concretely instantiated; put substitutions into typeSubs
    1849                         std::list< TypeExpr* > typeSubs;
    1850                         if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) {
    1851                                 deleteAll( typeSubs );
    1852                                 return inst;
    1853                         }
    1854 
    1855                         // make concrete instantiation of generic type
    1856                         StructDecl *concDecl = lookup( inst, typeSubs );
    1857                         if ( ! concDecl ) {
    1858                                 // set concDecl to new type, insert type declaration into statements to add
    1859                                 concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) );
    1860                                 substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs,        concDecl->get_members() );
    1861                                 DeclMutator::addDeclaration( concDecl );
    1862                                 insert( inst, typeSubs, concDecl );
    1863                         }
    1864                         StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() );
    1865                         newInst->set_baseStruct( concDecl );
    1866 
    1867                         deleteAll( typeSubs );
    1868                         delete inst;
    1869                         return newInst;
    1870                 }
    1871 
    1872                 Type* GenericInstantiator::mutate( UnionInstType *inst ) {
    1873                         // mutate subtypes
    1874                         Type *mutated = Mutator::mutate( inst );
    1875                         inst = dynamic_cast< UnionInstType* >( mutated );
    1876                         if ( ! inst ) return mutated;
    1877 
    1878                         // exit early if no need for further mutation
    1879                         if ( inst->get_parameters().empty() ) return inst;
    1880                         assert( inst->get_baseParameters() && "Base union has parameters" );
    1881 
    1882                         // check if type can be concretely instantiated; put substitutions into typeSubs
    1883                         std::list< TypeExpr* > typeSubs;
    1884                         if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) {
    1885                                 deleteAll( typeSubs );
    1886                                 return inst;
    1887                         }
    1888 
    1889                         // make concrete instantiation of generic type
    1890                         UnionDecl *concDecl = lookup( inst, typeSubs );
    1891                         if ( ! concDecl ) {
    1892                                 // set concDecl to new type, insert type declaration into statements to add
    1893                                 concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) );
    1894                                 substituteMembers( inst->get_baseUnion()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() );
    1895                                 DeclMutator::addDeclaration( concDecl );
    1896                                 insert( inst, typeSubs, concDecl );
    1897                         }
    1898                         UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() );
    1899                         newInst->set_baseUnion( concDecl );
    1900 
    1901                         deleteAll( typeSubs );
    1902                         delete inst;
    1903                         return newInst;
    1904                 }
    1905 
    1906         //      /// Gets the base struct or union declaration for a member expression; NULL if not applicable
    1907         //      AggregateDecl* getMemberBaseDecl( MemberExpr *memberExpr ) {
    1908         //              // get variable for member aggregate
    1909         //              VariableExpr *varExpr = dynamic_cast< VariableExpr* >( memberExpr->get_aggregate() );
    1910         //              if ( ! varExpr ) return NULL;
    1911         //
    1912         //              // get object for variable
    1913         //              ObjectDecl *objectDecl = dynamic_cast< ObjectDecl* >( varExpr->get_var() );
    1914         //              if ( ! objectDecl ) return NULL;
    1915         //
    1916         //              // get base declaration from object type
    1917         //              Type *objectType = objectDecl->get_type();
    1918         //              StructInstType *structType = dynamic_cast< StructInstType* >( objectType );
    1919         //              if ( structType ) return structType->get_baseStruct();
    1920         //              UnionInstType *unionType = dynamic_cast< UnionInstType* >( objectType );
    1921         //              if ( unionType ) return unionType->get_baseUnion();
    1922         //
    1923         //              return NULL;
    1924         //      }
    1925         //
    1926         //      /// Finds the declaration with the given name, returning decls.end() if none such
    1927         //      std::list< Declaration* >::const_iterator findDeclNamed( const std::list< Declaration* > &decls, const std::string &name ) {
    1928         //              for( std::list< Declaration* >::const_iterator decl = decls.begin(); decl != decls.end(); ++decl ) {
    1929         //                      if ( (*decl)->get_name() == name ) return decl;
    1930         //              }
    1931         //              return decls.end();
    1932         //      }
    1933         //
    1934         //      Expression* Instantiate::mutate( MemberExpr *memberExpr ) {
    1935         //              // mutate, exiting early if no longer MemberExpr
    1936         //              Expression *expr = Mutator::mutate( memberExpr );
    1937         //              memberExpr = dynamic_cast< MemberExpr* >( expr );
    1938         //              if ( ! memberExpr ) return expr;
    1939         //
    1940         //              // get declaration of member and base declaration of member, exiting early if not found
    1941         //              AggregateDecl *memberBase = getMemberBaseDecl( memberExpr );
    1942         //              if ( ! memberBase ) return memberExpr;
    1943         //              DeclarationWithType *memberDecl = memberExpr->get_member();
    1944         //              std::list< Declaration* >::const_iterator baseIt = findDeclNamed( memberBase->get_members(), memberDecl->get_name() );
    1945         //              if ( baseIt == memberBase->get_members().end() ) return memberExpr;
    1946         //              DeclarationWithType *baseDecl = dynamic_cast< DeclarationWithType* >( *baseIt );
    1947         //              if ( ! baseDecl ) return memberExpr;
    1948         //
    1949         //              // check if stated type of the member is not the type of the member's declaration; if so, need a cast
    1950         //              // this *SHOULD* be safe, I don't think anything but the void-replacements I put in for dtypes would make it past the typechecker
    1951         //              SymTab::Indexer dummy;
    1952         //              if ( ResolvExpr::typesCompatible( memberDecl->get_type(), baseDecl->get_type(), dummy ) ) return memberExpr;
    1953         //              else return new CastExpr( memberExpr, memberDecl->get_type() );
    1954         //      }
    1955 
    1956                 void GenericInstantiator::doBeginScope() {
    1957                         DeclMutator::doBeginScope();
    1958                         instantiations.beginScope();
    1959                 }
    1960 
    1961                 void GenericInstantiator::doEndScope() {
    1962                         DeclMutator::doEndScope();
    1963                         instantiations.endScope();
    1964                 }
    1965 
    19661660////////////////////////////////////////// PolyGenericCalculator ////////////////////////////////////////////////////
    19671661
    … …  
    21071801                        findGeneric( objectType ); // ensure layout for this type is available
    21081802
     1803                        // replace member expression with dynamically-computed layout expression
    21091804                        Expression *newMemberExpr = 0;
    21101805                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( objectType ) ) {
Note: See TracChangeset for help on using the changeset viewer.