Changeset 89173242


Ignore:
Timestamp:
Mar 10, 2016, 4:56:53 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:
b3f9a0cb
Parents:
0531b5d
Message:

Added first draft of use of layout functions

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/GenPoly/Box.cc

    r0531b5d r89173242  
    3030#include "FindFunction.h"
    3131#include "ScopedMap.h"
     32#include "ScopedSet.h"
    3233#include "ScrubTyVars.h"
    3334
     
    118119                        typedef std::vector< Instantiation > ValueList;
    119120                        /// Underlying map type; maps keys to a linear list of corresponding TypeLists and values
    120                         typedef ScopedMap< Key*, std::vector< Instantiation > > InnerMap;
     121                        typedef ScopedMap< Key*, ValueList > InnerMap;
    121122
    122123                        InnerMap instantiations;  ///< instantiations
     
    178179                        virtual void doEndScope();
    179180                  private:
    180                         /// Makes a new temporary array holding the offsets of the fields of `type`, and returns a new variable expression referencing it
    181                         Expression *makeOffsetArray( StructInstType *type );
    182181                        /// Pass the extra type parameters from polymorphic generic arguments or return types into a function application
    183182                        void passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes );
     
    206205                        ObjectDecl *makeTemporary( Type *type );
    207206
    208                         std::map< std::string, DeclarationWithType *> assignOps;
    209                         ResolvExpr::TypeMap< DeclarationWithType > scopedAssignOps;
    210                         ScopedMap< std::string, DeclarationWithType* > adapters;
     207                        std::map< std::string, DeclarationWithType *> assignOps;     ///< Currently known type variable assignment operators
     208                        ResolvExpr::TypeMap< DeclarationWithType > scopedAssignOps;  ///< Currently known assignment operators
     209                        ScopedMap< std::string, DeclarationWithType* > adapters;     ///< Set of adapter functions in the current scope
     210                       
    211211                        DeclarationWithType *retval;
    212212                        bool useRetval;
     
    214214                };
    215215
    216                 /// Moves polymorphic returns in function types to pointer-type parameters, adds type size and assertion parameters to parameter lists as well
     216                class OffsetPackExpr;  // forward declaration so that it can be mutated by Pass2
     217
     218                /// * Moves polymorphic returns in function types to pointer-type parameters
     219                /// * adds type size and assertion parameters to parameter lists
     220                /// * does dynamic calculation of type layouts
    217221                class Pass2 : public PolyMutator {
    218222                  public:
     
    225229                        virtual Type *mutate( PointerType *pointerType );
    226230                        virtual Type *mutate( FunctionType *funcType );
     231                        virtual Expression *mutate( SizeofExpr *sizeofExpr );
     232                        virtual Expression *mutate( AlignofExpr *alignofExpr );
     233                        virtual Expression *mutate( OffsetofExpr *offsetofExpr );
     234                                Expression *mutate( OffsetPackExpr *offsetPackExpr );
     235
     236                        virtual void doBeginScope();
     237                        virtual void doEndScope();
    227238                  private:
    228239                        void addAdapters( FunctionType *functionType );
     240                        /// Makes a new variable in the current scope with the given name, type & optional initializer
     241                        ObjectDecl *makeVar( const std::string &name, Type *type, Initializer *init = 0 );
     242                        /// returns true if the type has a dynamic layout; such a layout will be stored in appropriately-named local variables when the function returns
     243                        bool findGeneric( Type *ty );
     244                        /// adds type parameters to the layout call; will generate the appropriate parameters if needed
     245                        void addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams );
    229246
    230247                        std::map< UniqueId, std::string > adapterName;
     248                        ScopedSet< std::string > knownLayouts;          ///< Set of generic type layouts known in the current scope, indexed by sizeofName
     249                        ScopedSet< std::string > knownOffsets;          ///< Set of non-generic types for which the offset array exists in the current scope, indexed by offsetofName
     250                };
     251
     252                /// Special internal expression for offset arrays inserted by Pass1 and replaced by Pass2
     253                class OffsetPackExpr : public Expression {
     254                public:
     255                        OffsetPackExpr( StructInstType *type_, Expression *aname_ = 0 ) : Expression( aname_ ), type( type_ ) {
     256                                        add_result( new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0, false, false ) );
     257                        }
     258                       
     259                        OffsetPackExpr( const OffsetPackExpr &other ) : Expression( other ), type( maybeClone( other.type ) ) {}
     260                        virtual ~OffsetPackExpr() { delete type; }
     261
     262                        StructInstType *get_type() const { return type; }
     263                        void set_type( StructInstType *newValue ) { type = newValue; }
     264
     265                        virtual OffsetPackExpr *clone() const { return new OffsetPackExpr( *this ); }
     266                        virtual void accept( Visitor &v ) { /* do nothing */ }
     267                        virtual Expression *acceptMutator( Mutator &m ) {
     268                                // only act if the mutator is a Pass2, which knows about this class
     269                                if ( Pass2 *m2 = dynamic_cast< Pass2* >( &m ) ) {
     270                                        return m2->mutate( this );
     271                                } else {
     272                                        return this;
     273                                }
     274                        }
     275
     276                        virtual void print( std::ostream &os, int indent = 0 ) const {
     277                                os << std::string( indent, ' ' ) << "Offset pack expression on ";
     278
     279                                if ( type ) {
     280                                        type->print(os, indent + 2);
     281                                } else {
     282                                        os << "<NULL>";
     283                                }
     284
     285                                os << std::endl;
     286                                Expression::print( os, indent );
     287                        }
     288                       
     289                private:
     290                        StructInstType *type;
    231291                };
    232292
     
    633693
    634694                DeclarationWithType *Pass1::mutate( FunctionDecl *functionDecl ) {
    635                         // if this is a polymorphic assignment function, put it in the map for this scope
     695                        // if this is a assignment function, put it in the map for this scope
    636696                        if ( Type *assignedType = isAssignment( functionDecl ) ) {
    637697                                if ( ! dynamic_cast< TypeInstType* >( assignedType ) ) {
     
    723783                }
    724784
    725                 Expression *Pass1::makeOffsetArray( StructInstType *ty ) {
    726                         std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
    727 
    728                         // make a new temporary array
    729                         Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
    730                         std::stringstream lenGen;
    731                         lenGen << baseMembers.size();
    732                         ConstantExpr *lenExpr = new ConstantExpr( Constant( offsetType->clone(), lenGen.str() ) );
    733                         ObjectDecl *arrayTemp = makeTemporary( new ArrayType( Type::Qualifiers(), offsetType, lenExpr, false, false ) );
    734 
    735                         // build initializer list for temporary
    736                         std::list< Initializer* > inits;
    737                         for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
    738                                 DeclarationWithType *memberDecl;
    739                                 if ( DeclarationWithType *origMember = dynamic_cast< DeclarationWithType* >( *member ) ) {
    740                                         memberDecl = origMember->clone();
    741                                 } else {
    742                                         memberDecl = new ObjectDecl( (*member)->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
    743                                 }
    744                                 inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
    745                         }
    746                         arrayTemp->set_init( new ListInit( inits ) );
    747 
    748                         // return variable pointing to temporary
    749                         return new VariableExpr( arrayTemp );
    750                 }
    751 
    752785                void Pass1::passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes ) {
    753786                        Type *polyBase = hasPolyBase( parmType, exprTyVars );
     
    762795                                if ( dynamic_cast< StructInstType* >( polyBase ) ) {
    763796                                        if ( StructInstType *argBaseStructType = dynamic_cast< StructInstType* >( argBaseType ) ) {
    764                                                 arg = appExpr->get_args().insert( arg, makeOffsetArray( argBaseStructType ) );
    765                                                 arg++;
     797                                                // zero-length arrays are forbidden by C, so don't pass offset for empty struct
     798                                                if ( ! argBaseStructType->get_baseStruct()->get_members().empty() ) {
     799                                                        arg = appExpr->get_args().insert( arg, new OffsetPackExpr( argBaseStructType ) );
     800                                                        arg++;
     801                                                }
    766802                                        } else {
    767803                                                throw SemanticError( "Cannot pass non-struct type for generic struct" );
     
    16101646                                        ++last;
    16111647
    1612                                         if ( dynamic_cast< StructInstType* >( polyBase ) ) {
    1613                                                 offsetParm = newPtr.clone();
    1614                                                 offsetParm->set_name( offsetofName( polyBase ) );
    1615                                                 last = funcType->get_parameters().insert( last, offsetParm );
    1616                                                 ++last;
     1648                                        if ( StructInstType *polyBaseStruct = dynamic_cast< StructInstType* >( polyBase ) ) {
     1649                                                // NOTE zero-length arrays are illegal in C, so empty structs have no offset array
     1650                                                if ( ! polyBaseStruct->get_baseStruct()->get_members().empty() ) {
     1651                                                        offsetParm = newPtr.clone();
     1652                                                        offsetParm->set_name( offsetofName( polyBase ) );
     1653                                                        last = funcType->get_parameters().insert( last, offsetParm );
     1654                                                        ++last;
     1655                                                }
    16171656                                        }
    16181657
    16191658                                        seenTypes.insert( sizeName );
     1659                                        knownLayouts.insert( sizeName );  // make sure that any type information passed into the function is accounted for
    16201660                                }
    16211661                        }
     
    16291669                        scopeTyVars = oldtyVars;
    16301670                        return funcType;
     1671                }
     1672
     1673                ObjectDecl *Pass2::makeVar( const std::string &name, Type *type, Initializer *init ) {
     1674                        ObjectDecl *newObj = new ObjectDecl( name, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, type, init );
     1675                        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
     1676                        return newObj;
     1677                }
     1678
     1679                void Pass2::addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams ) {
     1680                        for ( std::list< Type* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
     1681                                if ( findGeneric( *param ) ) {
     1682                                        // push size/align vars for a generic parameter back
     1683                                        layoutCall->get_args().push_back( new NameExpr( sizeofName( *param ) ) );
     1684                                        layoutCall->get_args().push_back( new NameExpr( alignofName( *param ) ) );
     1685                                } else {
     1686                                        layoutCall->get_args().push_back( new SizeofExpr( *param ) );
     1687                                        layoutCall->get_args().push_back( new AlignofExpr( *param ) );
     1688                                }
     1689                        }
     1690                }
     1691
     1692                /// returns true if any of the otype parameters have a dynamic layout and puts all otype parameters in the output list
     1693                bool findGenericParams( std::list< TypeDecl* > &baseParams, std::list< Expression* > &typeParams, std::list< Type* > &out ) {
     1694                        bool hasDynamicLayout = false;
     1695
     1696                        std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
     1697                        std::list< Expression* >::const_iterator typeParam = typeParams.begin();
     1698                        for ( ; baseParam != baseParams.end() && typeParam != typeParams.end(); ++baseParam, ++typeParam ) {
     1699                                // skip non-otype parameters
     1700                                if ( (*baseParam)->get_kind() != TypeDecl::Any ) continue;
     1701                                TypeExpr *typeExpr = dynamic_cast< TypeExpr* >( *typeParam );
     1702                                assert( typeExpr && "all otype parameters should be type expressions" );
     1703
     1704                                Type *type = typeExpr->get_type();
     1705                                out.push_back( type );
     1706                                if ( isPolyType( type ) ) hasDynamicLayout = true;
     1707                        }
     1708                        assert( baseParam == baseParams.end() && typeParam == typeParams.end() );
     1709
     1710                        return hasDynamicLayout;
     1711                }
     1712               
     1713                bool Pass2::findGeneric( Type *ty ) {
     1714                        if ( dynamic_cast< TypeInstType* >( ty ) ) {
     1715                                // NOTE this assumes that all type variables will be properly bound, and thus have their layouts in scope
     1716                                return true;
     1717                        } else if ( StructInstType *structTy = dynamic_cast< StructInstType* >( ty ) ) {
     1718                                // check if this type already has a layout generated for it
     1719                                std::string sizeName = sizeofName( ty );
     1720                                if ( knownLayouts.find( sizeName ) != knownLayouts.end() ) return true;
     1721                               
     1722                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
     1723                                std::list< Type* > otypeParams;
     1724                                if ( ! findGenericParams( *structTy->get_baseParameters(), structTy->get_parameters(), otypeParams ) ) return false;
     1725
     1726                                // insert local variables for layout and generate call to layout function
     1727                                knownLayouts.insert( sizeName );  // done early so as not to interfere with the later addition of parameters to the layout call
     1728                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
     1729
     1730                                int n_members = structTy->get_baseStruct()->get_members().size();
     1731                                if ( n_members == 0 ) {
     1732                                        // all empty structs have the same layout - size 1, align 1
     1733                                        makeVar( sizeName, layoutType, new SingleInit( new ConstantExpr( Constant::from( (unsigned long)1 ) ) ) );
     1734                                        makeVar( alignofName( ty ), layoutType->clone(), new SingleInit( new ConstantExpr( Constant::from( (unsigned long)1 ) ) ) );
     1735                                        // NOTE zero-length arrays are forbidden in C, so empty structs have no offsetof array
     1736                                } else {
     1737                                        ObjectDecl *sizeVar = makeVar( sizeName, layoutType );
     1738                                        ObjectDecl *alignVar = makeVar( alignofName( ty ), layoutType->clone() );
     1739                                        ObjectDecl *offsetVar = makeVar( offsetofName( ty ), new ArrayType( Type::Qualifiers(), layoutType->clone(), new ConstantExpr( Constant::from( n_members ) ), false, false ) );
     1740
     1741                                        // generate call to layout function
     1742                                        UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( "__layoutof_" + structTy->get_baseStruct()->get_name() ) );
     1743                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
     1744                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
     1745                                        layoutCall->get_args().push_back( new VariableExpr( offsetVar ) );
     1746                                        addOtypeParamsToLayoutCall( layoutCall, otypeParams );
     1747
     1748                                        stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
     1749                                }
     1750                               
     1751                                return true;
     1752                        } else if ( UnionInstType *unionTy = dynamic_cast< UnionInstType* >( ty ) ) {
     1753                                // check if this type already has a layout generated for it
     1754                                std::string sizeName = sizeofName( ty );
     1755                                if ( knownLayouts.find( sizeName ) != knownLayouts.end() ) return true;
     1756                               
     1757                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
     1758                                std::list< Type* > otypeParams;
     1759                                if ( ! findGenericParams( *unionTy->get_baseParameters(), unionTy->get_parameters(), otypeParams ) ) return false;
     1760
     1761                                // insert local variables for layout and generate call to layout function
     1762                                knownLayouts.insert( sizeName );  // done early so as not to interfere with the later addition of parameters to the layout call
     1763                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
     1764
     1765                                ObjectDecl *sizeVar = makeVar( sizeName, layoutType );
     1766                                ObjectDecl *alignVar = makeVar( alignofName( ty ), layoutType->clone() );
     1767                               
     1768                                // generate call to layout function
     1769                                UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( "__layoutof_" + unionTy->get_baseUnion()->get_name() ) );
     1770                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
     1771                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
     1772                                addOtypeParamsToLayoutCall( layoutCall, otypeParams );
     1773
     1774                                stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
     1775
     1776                                return true;
     1777                        }
     1778                       
     1779                        return false;
     1780                }
     1781               
     1782                Expression *Pass2::mutate( SizeofExpr *sizeofExpr ) {
     1783                        Type *ty = sizeofExpr->get_type();
     1784                        if ( findGeneric( ty ) ) {
     1785                                Expression *ret = new NameExpr( sizeofName( ty ) );
     1786                                delete sizeofExpr;
     1787                                return ret;
     1788                        }
     1789                        return sizeofExpr;
     1790                }
     1791
     1792                Expression *Pass2::mutate( AlignofExpr *alignofExpr ) {
     1793                        Type *ty = alignofExpr->get_type();
     1794                        if ( findGeneric( ty ) ) {
     1795                                Expression *ret = new NameExpr( alignofName( ty ) );
     1796                                delete alignofExpr;
     1797                                return ret;
     1798                        }
     1799                        return alignofExpr;
     1800                }
     1801
     1802                Expression *Pass2::mutate( OffsetofExpr *offsetofExpr ) {
     1803                        findGeneric( offsetofExpr->get_type() );
     1804                        return offsetofExpr;
     1805                }
     1806
     1807                Expression *Pass2::mutate( OffsetPackExpr *offsetPackExpr ) {
     1808                        StructInstType *ty = offsetPackExpr->get_type();
     1809
     1810                        Expression *ret = 0;
     1811                        if ( findGeneric( ty ) ) {
     1812                                // pull offset back from generated type information
     1813                                ret = new NameExpr( offsetofName( ty ) );
     1814                        } else {
     1815                                std::string offsetName = offsetofName( ty );
     1816                                if ( knownOffsets.find( offsetName ) != knownOffsets.end() ) {
     1817                                        // use the already-generated offsets for this type
     1818                                        ret = new NameExpr( offsetName );
     1819                                } else {
     1820                                        std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
     1821                                        Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
     1822
     1823                                        // build initializer list for offset array
     1824                                        std::list< Initializer* > inits;
     1825                                        for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
     1826                                                DeclarationWithType *memberDecl;
     1827                                                if ( DeclarationWithType *origMember = dynamic_cast< DeclarationWithType* >( *member ) ) {
     1828                                                        memberDecl = origMember->clone();
     1829                                                } else {
     1830                                                        memberDecl = new ObjectDecl( (*member)->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
     1831                                                }
     1832                                                inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
     1833                                        }
     1834
     1835                                        // build the offset array and replace the pack with a reference to it
     1836                                        ObjectDecl *offsetArray = makeVar( offsetName, new ArrayType( Type::Qualifiers(), offsetType, new ConstantExpr( Constant::from( baseMembers.size() ) ), false, false ),
     1837                                                        new ListInit( inits ) );
     1838                                        ret = new VariableExpr( offsetArray );
     1839                                }
     1840                        }
     1841
     1842                        delete offsetPackExpr;
     1843                        return ret;
     1844                }
     1845
     1846                void Pass2::doBeginScope() {
     1847                        knownLayouts.beginScope();
     1848                        knownOffsets.beginScope();
     1849                }
     1850               
     1851                void Pass2::doEndScope() {
     1852                        knownLayouts.endScope();
     1853                        knownOffsets.beginScope();
    16311854                }
    16321855
Note: See TracChangeset for help on using the changeset viewer.